Search papers, labs, and topics across Lattice.
This paper addresses the challenge of overparameterized classification where gradient descent on logistic loss can lead to suboptimal classifiers due to label-flipping noise. By employing early stopping at an oracle time, the authors demonstrate that it is possible to achieve minimax-optimal excess zero-one risk in Gaussian mixture models with specific covariance spectra. Their findings are supported by both theoretical upper and lower bounds, as well as experimental validation, highlighting the effectiveness of early stopping in overcoming the limitations of traditional gradient descent methods.
Early stopping can transform gradient descent from a source of suboptimality into a strategy for achieving minimax-optimal classification performance in noisy settings.
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.
