Research map / Optimization / Implicit bias and generalization

Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

NeurIPS 2026 · Optimization › Implicit bias and generalization · approach: Low-rank and single-index recovery · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows early-stopped GD on the logistic loss is minimax-optimal for excess zero-one risk in a label-flip Gaussian mixture under fast-continuous-decay spectra, while interpolating classifiers are provably suboptimal.

Problem

Overparameterised linear classification with logistic loss: GD converges to the max-margin interpolator, which can be statistically suboptimal; it is unknown whether early-stopped GD is statistically optimal in Gaussian mixtures with label-flipping noise.

Approach

An oracle stopping time (when ||w_t|| reaches 4||w*||) gives an upper bound on excess zero-one risk via a new linear-rate calibration lemma (replacing square-root calibration) and effective-rank localisation; matched by a minimax lower bound over all classifiers, and an interpolation lower bound over all linear interpolators.

Key results

• Early-stopped GD at oracle time achieves excess zero-one risk asymptotically n^{-2a/(2a+1)} for polynomial spectra lambda_i ~ i^{-2a}, a>1/2, matching the minimax lower bound.
• For exponential spectra lambda_i ~ e^{-bi}, early-stopped GD achieves excess zero-one risk of order log(n)/n, matching the minimax lower bound.
• Interpolation lower bound: when d ~ n log n, every linear interpolator (including the max-margin classifier) has excess zero-one risk at least order 1/log n, which vanishes strictly slower than the early-stopping rates.

Surprising findings

• Standard square-root calibration bounds yield rates that do not vanish with n in the misspecified label-flip setting, requiring a new linear-rate calibration.

Limitations

• The stopping time is oracle-based and not a data-dependent algorithm.
• Analysis of GD uses the logistic loss as surrogate for zero-one risk.
• Interpolation lower bound comparison is shown mainly in regimes such as d ~ n log n.

Experimental setup

Datasets: synthetic Gaussian mixture with label-flip noise

Metrics: excess zero-one risk excess logistic risk

Baselines: max-margin interpolator minimum l2-norm interpolator

Builds on: max-margin implicit bias of GD Zhou et al. (2026) interpolation lower bound Proposition 2.1.B calibration (Bartlett et al.) effective rank analyses of ridge regression early-stopped GD minimax regression results

Closest papers by meaning

• Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models (NeurIPS 2024 · similarity 0.88)
• Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression (ICML 2025 · similarity 0.88)
• The Effect of Optimal Self-Distillation in Noisy Gaussian Mixture Model (NeurIPS 2025 · similarity 0.87)
• Sublinear Variational Optimization of Gaussian Mixture Models with Millions to Billions of Parameters (NeurIPS 2026 · similarity 0.87)
• Out-Of-Domain Unlabeled Data Improves Generalization (ICLR 2024 · similarity 0.87)
• The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures (ICLR 2025 · similarity 0.86)