Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

2026-08-06 · 16:41 UTC ·Alex Buna, Shirley Xiaoqi Liu, Patrick Rebeschini ·1 min read

Brief

Using a Gaussian-mixture classification model with label-flipping noise, Buna et al. show gradient descent on logistic loss, stopped at an oracle time, achieves minimax-optimal excess zero–one risk for covariance spectra with fast continuous decay (polynomial and exponential). They prove matching upper and lower bounds, introduce a calibration removing the standard square-root loss for converting logistic to zero–one risk, and validate rates empirically.

Why it matters

Early-stopped gradient descent on the logistic loss, stopped at an appropriate oracle time, attains minimax-optimal excess zero–one risk for a Gaussian-mixture classification model with label-flipping noise when the data covariance spectrum has fast, continuous decay (including polynomial and exponential decay).

Key details

The paper develops a new calibration that converts excess logistic risk into excess zero–one risk while handling model misspecification from label-flipping noise and removing the usual square-root loss; the theoretical analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound.

A lower bound for linear interpolators is proved showing interpolation can require exponentially more samples than early stopping to reach the same excess risk; empirical experiments validate the derived optimal rates (Buna, Liu, Rebeschini; arXiv:2608.06250v1, 2026-08-06).

Abstract

In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this work, we show that early stopping can overcome this suboptimality: in 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 polynomial and exponential spectral decays. Our analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are validated by experiments. A central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk; it handles the model misspecification induced by the label-flipping noise, and removes the square-root rate in standard bounds. We 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.