Early-stopped gradient descent proven minimax-optimal for Gaussian mixture classification

In overparameterized classification, training data can be linearly separable even when the underlying distribution is not. Gradient descent on logistic loss then diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this new arXiv paper by Alex Buna, Shirley Xiaoqi Liu, and Patrick Rebeschini, the authors show that early stopping overcomes this suboptimality: for a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimax-optimal excess zero-one risk for covariance spectra with fast and continuous decay, including both polynomial and exponential spectral decays. The result pairs a sharp upper bound on the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are also validated by experiments.

The central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk. This calibration handles the model misspecification induced by label-flipping noise and removes the square-root rate that appears in standard bounds, making the analysis tight. The authors also establish a lower bound for linear interpolators, showing that interpolation can require exponentially more samples than early stopping to achieve the same excess risk. Practically, this offers a rigorous justification for using early stopping as more than a heuristic regularization trick, and explains why it often works better than letting training run to (near) interpolation in noisy, overparameterized settings.