EvoBatch: A Mini-Batch, Compute-Constrained Evolutionary Algorithm Reduces the Generalization Gap in Deep Learning
Stochastic Gradient Descent (SGD) and its variants are single-objective optimizers focused on minimizing training loss, often failing to address the generalization gap in deep learning. In this paper we introduce EvoBatch, a novel Hybrid Evolutionary Algorithm (HEA) that re-frames deep network optimization as an explicitly multi-objective problem. EvoBatch leverages a two-stage selection process, guided by both training loss and validation performance, to directly optimize for generalization. To overcome the historical computational barrier of EAs, EvoBatch uses mini-batch evolutionary local search, restricting each individual to local updates on unique, random data subsets. Theoretically, this M-ELS mechanism acts as a robust implicit regularizer by injecting heterogeneous noise, promoting the discovery of broader, flatter minima. This stability is the necessary condition that allows the explicit multi-objective selection to systematically and monotonically reduce the generalization gap. Empirically, EvoBatch demonstrates superior generalization profiles and consistently outperforms gradient-based baselines across image classification (ResNet, ViT) and language understanding (BERT) benchmarks. Our findings establish that compute-constrained, multi-objective evolutionary optimization offers both an effective and an efficient alternative to single-objective gradient methods when generalization is critical.