这篇论文告诉你，训练到过拟合之前提前停一下，GD在带噪声的高斯混合分类上能拿到理论最优错误率，比插值器省指数级样本。
该论文研究过参数化分类中，线性可分数据下梯度下降（GD）在逻辑损失上范数发散但方向收敛到最大间隔分类器，其隐式偏差在统计上可能次优。作者证明在带标签翻转噪声的高斯混合模型下，于适当oracle时间早停的GD可对具有快速连续衰减协方差谱（包括多项式与指数衰减）实现极小极大最优的excess zero-one风险。分析结合了早停迭代的尖锐上界与任意分类器的匹配统计下界，并通过实验验证了最优速率。核心技术贡献是一个新的校准结果，将excess logistic风险转换为excess zero-one风险，去除了标准界中的平方根速率。此外，线性插值器达到相同excess风险所需样本量可能指数级多于早停。
Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification
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.