Shirley Liu

When to Stop Gradient Descent: Minimax Optimal Early Stopping for Binary Classification

We study gradient descent (GD) with logistic loss for binary linear classification, across a range of single-index models. For highly parameterised models, running GD to convergence can produce a linear classifier that interpolates the training data, even when the population data distribution is not linearly separable. Such a classifier incurs high excess zero-one risk. In this work, we show that the statistical suboptimality of interpolation can be overcome by stopping GD early: a heuristic widely used in machine learning practice.

Specifically, for single-index models with subgaussian covariates, we construct a novel stopping time and establish that GD stopped at this time achieves minimax-optimal excess zero-one risk under two conditions: (i) the covariance spectrum satisfies a fast and continuously decaying condition, and (ii) the Bayes classifier is sufficiently well aligned with the covariance spectrum. A key technical contribution is an oracle inequality that underpins our excess-risk upper bound, which matches the minimax lower bound. We also prove a lower bound showing that, in the same models, linear interpolation can require exponentially more samples than early stopping to achieve the same excess risk.

This is ongoing joint work with Alex Buna and Patrick Rebeschini, building on our preprint https://arxiv.org/abs/2608.06250. I’ll focus on intuition and high-level ideas, with the aim of making the interesting topic of early stopping accessible and engaging to a broad audience.