Pith. sign in

REVIEW 3 major objections 5 minor 43 references

Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that early-stopped gradient descent on the logistic loss is minimax-optimal for Gaussian mixture classification with label-flipping noise, with optimal rates for polynomial and exponential covariance spectra.

desk verdict Real theory and an honest caveat: the headline minimax result rests on an oracle stopping rule that no implementable algorithm uses. read the letter →

arxiv 2608.06250 v1 pith:W722VHBT submitted 2026-08-06 stat.ML cs.LG

Alex Buna , Shirley Xiaoqi Liu , Patrick Rebeschini This is my paper · ORCID
classification stat.MLcs.LG MSC 62C2062H3068T05
keywords earlystoppinggradientdescentminimaxoptimalityGaussianmixtureclassificationlogisticlosslabel-flippingnoisecovariancespectrumexcesszero-onerisk
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Early stopping can rescue logistic-regression gradient descent from the statistical inefficiency of interpolation. The paper proves that, in a Gaussian mixture model with label-flipping noise, the GD iterate stopped at an oracle time achieves the minimax-optimal excess zero-one risk whenever the covariance spectrum is fast and continuously decaying. For polynomial decay $\lambda_i \sim i^{-2a}$ the optimal rate is $n^{-2a/(2a+1)}$, and for exponential decay $\lambda_i \sim e^{-bi}$ it is $\log n / n$; no arbitrary classifier can do better asymptotically. The same analysis shows that interpolating classifiers, which GD approaches in overparameterised settings, need exponentially more samples to match that excess risk, so early stopping is both sufficient and necessary for optimality.

What carries the argument

The argument turns on the oracle stopping time $\tau = \inf\{t \ge 1 : \|w_t\| \ge 4\|w^*\|\}$, which keeps the iterate in a bounded ball while ensuring the empirical logistic risk at the stopped iterate is no worse than the population logistic minimizer's. The proof then uses a linear-rate calibration inequality (Lemma 4), derived from local strong convexity of the logistic risk around its minimizer $\rho^* w^*$, to reduce excess zero-one risk to excess logistic risk. The stochastic term is controlled by a localized empirical-process bound whose complexity is governed by the effective rank $r_{\mathrm{eff}}(\eta) = \operatorname{tr}(\Sigma(\Sigma + \eta I)^{-1})$, and the lower bound is built from a packing of signal centers combined with a triangle inequality for excess zero-one risk. Under the fast-and-continuously-decaying spectrum assumption, the effective rank and the hard eigenvalue count $N(\eta)$ are of the same order, which is what makes the upper and lower rates match.

What would settle it

For a concrete polynomial spectrum $\lambda_i = i^{-2a}$, evaluate $r_{\mathrm{eff}}(\eta_n^*)$ and $N(\eta_n^*)$ for large $n$; if their ratio is unbounded while the spectrum satisfies the FCD condition, Theorem 3's premise that the two effective dimensions match is violated, and the claimed minimax rate does not follow.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3 with Corollary 1: for Gaussian mixtures with label-flipping noise and a fast-and-continuously-decaying covariance spectrum, the early-stopped GD iterate at $\tau = \inf\{t \ge 1 : \|w_t\| \ge 4\|w^*\|\}$ is minimax-optimal, with excess zero-one risk of order $\eta_n^*$, which equals $n^{-2a/(2a+1)}$ for polynomial spectral decay $\lambda_i \asymp i^{-2a}$ and $\log n/n$ for exponential decay $\lambda_i \asymp e^{-bi}$. The upper bound (Theorem 1) relies on a new calibration lemma that converts excess logistic risk into excess zero-one risk at a linear rate, handling the misspecification created by label flipping, and a matching lower bound (Theorem 2) applies to arbitrary classifiers. The paper also proves that every interpolating linear classifier, including the max-margin direction GD converges to, has excess risk $\gtrsim 1/\log n$ when $d \asymp n\log n$, strictly worse than these minimax rates; thus early stopping is necessary for optimality in that regime.

Load-bearing premise

The load-bearing assumption is an oracle: the stopping time is defined using the unknown true signal direction $\Sigma^{-1}\mu$, so the minimax guarantee is an existence result; without a data-dependent rule that recovers this scale, the stated optimality does not follow.

Editorial extensions

If this is right

  • In the overparameterised regime $d \ge n$, the minimax rates are achieved by early stopping, so no classifier trained from $n$ samples can have asymptotically smaller excess zero-one risk for FCD spectra.
  • For $d \asymp n \log n$, interpolation is strictly suboptimal: the max-margin classifier's excess risk is at least $\gtrsim 1/\log n$, whereas early stopping reaches $n^{-2a/(2a+1)}$ or $\log n/n$, so interpolation needs exponentially more samples.
  • The new calibration result makes excess logistic risk directly comparable to excess zero-one risk for linear classifiers, eliminating the square-root gap and the irreducible misspecification term in standard bounds.
  • The FCD framework broadens the spectral regimes covered beyond polynomial decay, so the same minimax conclusion holds for exponentially decaying covariances.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The oracle rule could plausibly be replaced by a holdout-based estimate of $\|w^*\|$ in practice; the paper does not analyze such a rule, so the minimax guarantee currently stops at existence.
  • The linear-rate calibration likely extends to other smooth convex surrogates with local strong convexity around their population minimizers, which would make similar minimax statements available for squared-hinge or other losses.
  • The FCD condition is stated for continuous decay; boundary cases such as $a = 1/2$ or slowly varying factors would require a separate calculation and may show different rates.
  • Empirically, the iterate with lowest hindsight excess risk tracks the oracle-time rate (Figure 2), suggesting a feasible data-dependent selection may preserve optimality, but that remains to be proven.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies gradient descent on the logistic loss for Gaussian mixture classification with label-flipping noise, in the overparameterised regime d≥n. It proves an upper bound on the excess zero-one risk of GD stopped at the oracle time τ=inf{t≥1: ||w_t||≥4||w*||}, where w*=Σ^{-1}μ is the population Bayes direction; the bound is expressed through the effective rank of the covariance. It then proves a statistical lower bound over arbitrary classifiers, and shows that for covariance spectra satisfying the FCD assumption (including polynomial and exponential decay) the two bounds match, giving rates n^{-2a/(2a+1)} and log n/n respectively. A separate result lower-bounds the excess risk of all interpolating linear classifiers, showing that interpolation can be much less sample-efficient than early stopping. A new calibration lemma converts excess logistic risk into excess zero-one risk at a linear rate under local strong convexity.

Significance. If the claims are taken as stated, the paper would be a substantial contribution: it provides a sharp calibration result for misspecified logistic loss, a refined effective-rank-based concentration analysis, and matching spectral lower bounds. The appendix is detailed and the proofs use standard tools (local strong convexity, effective rank concentration, peeling, Fano, packing), with explicit constants in several lemmas. The empirical rates in Figures 1 and 2 are consistent with the theoretical rates. However, the central upper-bound procedure depends on the unknown population quantity w* through the stopping rule (2), so the paper does not actually prove minimax optimality of an implementable early-stopped GD algorithm. This is a load-bearing gap between the theorems and the abstract/title, even though Section 5 honestly acknowledges the oracle nature of the stopping time.

major comments (3)
  1. [§2, Eq. (2); §3.3, Theorem 3; §5] The stopping rule τ=inf{t≥1: ||w_t||≥4||w*||} depends on the unknown population signal w*=Σ^{-1}μ. The statistical lower bound in Theorem 2 is over all sample-based procedures b_h(S), and the upper-bound construction is not of this form: it is an oracle-tuned trajectory indexed by μ. Consequently, the chain 'upper bound ≤ CΨ, lower bound ≥ cΨ' does not imply that early-stopped GD is minimax-optimal among valid procedures; it implies an oracle-rate upper bound. Section 5 concedes that the rule is oracle-based, but the abstract, Theorem 3, and the conclusion state the stronger claim. This is not merely a practical limitation, because a sample-measurable stopping rule is exactly what is needed to place the upper bound in the same class of procedures as the lower bound. The paper should either provide a data-dependent stopping rule with the same rate, or consistently reframe the results as an oracle-rate matching result and state explicitly that the minimax-optimality of a deployable early-stopped GD procedure remains open.
  2. [§3.3, Theorem 3; Appendix E, Step 4] Theorem 3 states that the upper bound and the statistical lower bound 'match' with common rate ≍η_n*, but the upper bound in Theorem 1 is high-probability for a fixed confidence δ, while Theorem 2 is a worst-case expectation lower bound. To conclude a minimax statement one must convert the high-probability upper bound into an expectation bound uniformly over the parameter class. Since excess zero-one risk is bounded by 1, the conversion adds at most a δ term, and choosing δ=n^{-2} would be harmless for the rates, but this conversion is not performed or stated. The paper should make this step explicit when claiming that the minimax rate is achieved.
  3. [§1 and §5; Figure 2] The finite-sample experiments in Figure 2 use either the oracle stopping time from the theory or the hindsight best-iterate along the trajectory. Neither curve corresponds to a sample-measurable stopping rule. The caption should state this limitation, and the text should avoid implying that the experiments validate an implementable minimax-optimal procedure. As with the theory, the experiments are consistent with an oracle-rate result, but they do not demonstrate that a deployable early-stopping rule attains the lower bound.
minor comments (5)
  1. [§2, Lemma 7] There is a typo: 'Lipshitz' should be 'Lipschitz'.
  2. [Appendix C.3] In the sentence 'For each w∈R, define g_w', the domain should be R^d, not R.
  3. [Appendix C.3.2, Step 3] The phrase 'One the empirical side' should be 'On the empirical side'.
  4. [Figure 2 caption] The caption should explicitly state that the orange curve is selected in hindsight and the blue curve uses the oracle stopping time, so neither curve represents a sample-based procedure.
  5. [§1.1, bullet list] The phrasing 'there exists an oracle stopping time at which the GD iterate achieves minimax-optimal excess zero-one risk' is accurate as a statement about the oracle, but it is in tension with the abstract's unqualified 'minimax-optimal' claim; the discrepancy should be resolved in the revised text.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper and lower bounds are derived independently; the acknowledged oracle stopping rule is a feasibility gap, not a self-definitional or fitted-input circularity.

full rationale

The central derivation is not circular. Theorem 1 is proved by direct empirical-process and local strong-convexity arguments (Lemmas 9–15) on the GD trajectory; its rate is governed by the effective rank r_eff(eta_n), not by any fitted constant. Theorem 2 is an independent minimax lower bound over arbitrary classifiers, built from a Sigma-geometric triangle inequality, a dense packing in mu-space, and Fano's inequality; it does not use the GD trajectory or the upper-bound constants. Theorem 3 and Corollary 1 merely equate r_eff(eta) and N(eta) under the FCD Assumption 1 and solve eta*_n from N(eta) ~ n eta, so the polynomial and log(n)/n rates are analytic consequences of the spectrum. No load-bearing self-citation is present: [39] and [40] are independent prior works cited for context and terminology, and the interpolation lower bound Theorem 4 is proved in Appendix F, not imported. The only in-scope caveat is Eq. (2) and Section 5: the stopping time tau = inf{t >= 1: ||w_t|| >= 4||w*||} depends on the unknown w*, so Theorem 1 gives an oracle upper bound rather than the risk of a sample-based estimator; the 'minimax optimality' wording is therefore stronger than what is proven. This is a correctness and feasibility limitation, explicitly disclosed by the authors, and it does not make any derivation equal to its inputs by construction.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the Gaussian mixture model, the FCD spectral assumption, overparameterization, and the oracle stopping rule. No new physical or mathematical entities are introduced, and no parameters are fitted to data; the only hand-chosen constant is the factor 4 in the stopping time.

free parameters (1)
  • stopping threshold 4 in tau
    The oracle stopping rule uses a hand-chosen factor 4 in inf{t >= 1 : ||w_t|| >= 4||w*||}. Any constant > 2 would likely work; it is not fitted to data and does not affect the asymptotic rate.
assumptions (6)
  • domain assumption Gaussian mixture model (1): X = eY mu + epsilon, epsilon ~ N(0, Sigma), with label-flip probability p in [0, 0.5).
    The entire analysis is carried out under this model, stated in Section 1. The Bayes classifier is linear w* = Sigma^{-1}mu.
  • domain assumption Fast and continuously decaying (FCD) spectrum, Assumption 1: (1/eta) sum_{lambda_i < eta} lambda_i <= N(eta) for small eta.
    This spectral regularity is what makes r_eff(eta) ~ N(eta), allowing upper and lower bounds to match (Theorem 3). Without it the minimax equivalence is not established.
  • domain assumption Overparameterization n <= d.
    Needed for Lemma 2 (linear separability and divergence of GD iterates) and for the interpolation lower bound in Theorem 4.
  • ad hoc to paper Oracle stopping rule tau = inf{t >= 1 : ||w_t|| >= 4||w*||} uses the unknown population signal w*.
    The upper bound relies on this oracle to localize the iterate to B = {w: ||w|| <= 4||w*|| + 1} and to ensure the empirical logistic risk at tau is no larger than at the population minimizer. This is acknowledged as an existence result, not a deployable algorithm.
  • domain assumption Implicit bias of GD on separable data: on linearly separable data, logistic-loss GD iterates diverge in norm and converge in direction to the max-margin classifier.
    Used in Lemma 2 and to motivate the interpolation lower bound; cited from Soudry et al. (2018) and Ji and Telgarsky (2019).
  • standard math Standard concentration and information-theoretic tools (Koltchinskii-Lounici, Fano, Chernoff, Rademacher contraction) are used without reproof.
    These are cited and invoked in the appendix (e.g., [21], [3], [4]).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification." pith.science (2026). https://pith.science/paper/W722VHBT

@misc{pith2026260806250,
  author       = {Pith},
  title        = {Pith review of: Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W722VHBT}},
  note         = {Machine review of arXiv:2608.06250}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2608.06250 by the authors.

Figure 1
Figure 1. Early stopping along the GD trajectory. Excess zero-one population risk along GD iterates trained on n = 972 samples from the d = 3888-dimensional Gaussian mixture model X ∼ N (±µ, Σ) with label-flip probability p = 0.1 (see (1)). The centres µ satisfy ∥Σ−1µ∥ ≲ 1. Left: polynomial spectrum λi(Σ) ≍ i −2a with a = 1. Right: exponential spectrum λi(Σ) ≍ e −bi with b = 0.12. The solid curve shows the median over indepen… view at source ↗
Figure 2
Figure 2. Empirical rates for early-stopped GD. Excess zero-one population risk as a function of the sample size n, under the same experimental setting as [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 32 canonical work pages

  1. [1]

    Support vector machines and linear regression coincide with very high-dimensional features.Advances in Neural Information Processing Systems, 34: 4907–4918, 2021

    Navid Ardeshir, Clayton Sanford, and Daniel J Hsu. Support vector machines and linear regression coincide with very high-dimensional features.Advances in Neural Information Processing Systems, 34: 4907–4918, 2021

    work page 2021

  2. [2]

    Early stopping and polynomial smoothing in regression with reproducing kernels.arXiv preprint arXiv:2007.06827, 2020

    Yaroslav Averyanov and Alain Celisse. Early stopping and polynomial smoothing in regression with reproducing kernels.arXiv preprint arXiv:2007.06827, 2020

    arXiv 2007

  3. [3]

    MIT press, 2024

    Francis Bach.Learning theory from first principles. MIT press, 2024

    2024

  4. [4]

    Bartlett, Olivier Bousquet, and Shahar Mendelson

    Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities.The Annals of Statistics, 33(4), August 2005

    work page 2005

  5. [5]

    Convexity, classification, and risk bounds

    Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138–156, 2006

    2006

  6. [6]

    Benign overfitting in linear regression.Proceedings of the National Academy of Sciences, 117(48):30063–30070, 2020

    Peter L Bartlett, Philip M Long, G´ abor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression.Proceedings of the National Academy of Sciences, 117(48):30063–30070, 2020

    work page 2020

  7. [7]

    Two models of double descent for weak features.SIAM Journal on Mathematics of Data Science, 2(4):1167–1180, 2020

    Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features.SIAM Journal on Mathematics of Data Science, 2(4):1167–1180, 2020

    2020

  8. [8]

    Boosting With the L2 Loss.Journal of the American Statistical Associ- ation, 98(462):324–339, 2003

    Peter B¨ uhlmann and Bin Yu. Boosting With the L2 Loss.Journal of the American Statistical Associ- ation, 98(462):324–339, 2003

    work page 2003

Show all 43 references
  1. [9]

    Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures

    Yuan Cao, Quanquan Gu, and Misha Belkin. Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures. InAdvances in Neural Information Processing Systems, 2021

    2021

  2. [10]

    Caponnetto and E

    A. Caponnetto and E. De Vito. Optimal Rates for the Regularized Least-Squares Algorithm.Founda- tions of Computational Mathematics, 7(3):331–368, July 2007

    2007

  3. [11]

    Chatterji and Philip M

    Niladri S. Chatterji and Philip M. Long. Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime.Journal of Machine Learning Research, 22(129):1–30, 2021

    2021

  4. [12]

    A model of double descent for high- dimensional binary linear classification.Information and Inference: A Journal of the IMA, 11(2): 435–495, 2022

    Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification.Information and Inference: A Journal of the IMA, 11(2): 435–495, 2022

    2022

  5. [13]

    Universality of benign overfitting in binary linear classification.arXiv preprint arXiv:2501.10538, 2025

    Ichiro Hashimoto, Stanislav Volgushev, and Piotr Zwiernik. Universality of benign overfitting in binary linear classification.arXiv preprint arXiv:2501.10538, 2025

    2025 arXiv

  6. [14]

    Springer Series in Statistics

    Trevor Hastie, Robert Tibshirani, and Jerome Friedman.The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Springer, 2 edition, 2009

    2009

  7. [15]

    Surprises in high-dimensional ridgeless least squares interpolation.Annals of statistics, 50(2):949, 2022

    Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation.Annals of statistics, 50(2):949, 2022

    2022

  8. [16]

    On the proliferation of support vectors in high dimensions

    Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors in high dimensions. InInternational Conference on Artificial Intelligence and Statistics, pages 91–99. PMLR, 2021

    2021

  9. [17]

    The implicit bias of gradient descent on nonseparable data

    Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu, editors,Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 ofProceedings of Machine Learning Research, pages 1772–1798. PMLR, 2...

    2019

  10. [18]

    On the precise error analysis of support vector machines

    Abla Kammoun and Mohamed-Slim Alouini. On the precise error analysis of support vector machines. IEEE Open Journal of Signal Processing, 2:99–118, 2021. 12

    2021

  11. [19]

    The statistical complexity of early-stopped mirror descent.Information and Inference: A Journal of the IMA, 12(4):3010–3041, 2023

    Varun Kanade, Patrick Rebeschini, and Tomas Vaˇ skeviˇ cius. The statistical complexity of early-stopped mirror descent.Information and Inference: A Journal of the IMA, 12(4):3010–3041, 2023

    2023

  12. [20]

    Analytic study of double descent in binary classification: The impact of loss

    Ganesh Ramachandra Kini and Christos Thrampoulidis. Analytic study of double descent in binary classification: The impact of loss. InInternational Symposium on Information Theory, pages 2527–2532. IEEE, 2020

    2020

  13. [21]

    Concentration inequalities and moment bounds for sample covariance operators.Bernoulli, pages 110–133, 2017

    Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators.Bernoulli, pages 110–133, 2017

    2017

  14. [22]

    Optimal rates for multi-pass stochastic gradient methods.Journal of Machine Learning Research, 18(97):1–47, 2017

    Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods.Journal of Machine Learning Research, 18(97):1–47, 2017

    2017

  15. [23]

    The role of regularization in classification of high-dimensional noisy gaussian mixture

    Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization in classification of high-dimensional noisy gaussian mixture. InInternational conference on machine learning, pages 6874–6883. PMLR, 2020

    2020

  16. [24]

    The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime

    Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime. The Annals of Statistics, 53(2):822 – 853, 2025

    2025

  17. [25]

    Harmless interpolation of noisy data in regression.IEEE Journal on Selected Areas in Information Theory, 1(1):67–83, 2020

    Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression.IEEE Journal on Selected Areas in Information Theory, 1(1):67–83, 2020

    2020

  18. [26]

    Classification vs regression in overparameterized regimes: does the loss function matter?J

    Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: does the loss function matter?J. Mach. Learn. Res., 22(1), January 2021

    2021

  19. [27]

    Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes.Advances in Neural Information Processing Systems, 31, 2018

    Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes.Advances in Neural Information Processing Systems, 31, 2018

    2018

  20. [28]

    Early stopping and non-parametric regression: an optimal data-dependent stopping rule.The Journal of Machine Learning Research, 15(1):335–366, 2014

    Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early stopping and non-parametric regression: an optimal data-dependent stopping rule.The Journal of Machine Learning Research, 15(1):335–366, 2014

    2014

  21. [29]

    The Impact of Regularization on High-dimensional Logistic Regression

    Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The Impact of Regularization on High-dimensional Logistic Regression. InAdvances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019

    2019

  22. [30]

    The performance analysis of generalized margin maximizers on separable data

    Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The performance analysis of generalized margin maximizers on separable data. InInternational conference on machine learning, pages 8417–8426. PMLR, 2020

    2020

  23. [31]

    Gradient methods never overfit on separable data.Journal of Machine Learning Research, 22(85):1–20, 2021

    Ohad Shamir. Gradient methods never overfit on separable data.Journal of Machine Learning Research, 22(85):1–20, 2021

    2021

  24. [32]

    The implicit bias of gradient descent on separable data.Journal of Machine Learning Research, 19(70):1–57, 2018

    Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data.Journal of Machine Learning Research, 19(70):1–57, 2018

    2018

  25. [33]

    Connecting optimization and regularization paths

    Arun Sai Suggala, Adarsh Prasad, and Pradeep Ravikumar. Connecting optimization and regularization paths. InProceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 10631–10641, Red Hook, NY, USA, 2018. Curran Associates Inc

    2018

  26. [34]

    Cand` es

    Pragya Sur and Emmanuel J. Cand` es. A modern maximum-likelihood theory for high-dimensional logistic regression.Proceedings of the National Academy of Sciences, 116(29):14516–14525, 2019. 13

    2019

  27. [35]

    Benign overfitting in ridge regression.Journal of Machine Learning Research, 24(123):1–76, 2023

    Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression.Journal of Machine Learning Research, 24(123):1–76, 2023

    2023

  28. [36]

    Benign overfitting and the geometry of the ridge regression solution in binary classification.arXiv preprint arXiv:2503.07966, 2025

    Alexander Tsigler, Luiz FO Chamon, Spencer Frei, and Peter L Bartlett. Benign overfitting and the geometry of the ridge regression solution in binary classification.arXiv preprint arXiv:2503.07966, 2025

    2025 arXiv

  29. [37]

    Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization.SIAM Journal on Mathematics of Data Science, 4(1):260–284, 2022

    Ke Wang and Christos Thrampoulidis. Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization.SIAM Journal on Mathematics of Data Science, 4(1):260–284, 2022

    2022

  30. [38]

    Early stopping for kernel boosting algorithms: A general analysis with localized complexities.IEEE Transactions on Information Theory, 65(10): 6685–6703, 2019

    Yuting Wei, Fanny Yang, and Martin J Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities.IEEE Transactions on Information Theory, 65(10): 6685–6703, 2019

    2019

  31. [39]

    Risk comparisons in linear regression: Implicit regularization dominates explicit regularization.arXiv preprint arXiv:2509.17251, 2025

    Jingfeng Wu, Peter L Bartlett, Jason D Lee, Sham M Kakade, and Bin Yu. Risk comparisons in linear regression: Implicit regularization dominates explicit regularization.arXiv preprint arXiv:2509.17251, 2025

    2025 arXiv

  32. [40]

    Bartlett, Matus Telgarsky, and Bin Yu

    Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, and Bin Yu. Benefits of early stopping in gradient descent for overparameterized logistic regression. InProceedings of the 42nd International Conference on Machine Learning. JMLR.org, 2025

    2025

  33. [41]

    On Early Stopping in Gradient Descent Learning

    Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On Early Stopping in Gradient Descent Learning. Constructive Approximation, 26(2):289–315, August 2007

    2007

  34. [42]

    Z |Tu|/ρ −|Tu|/ρ |t|fT ∗ (t)dt # ≤ 1−2p√ 2π∥µ∥ Σ−1 E

    Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk mini- mization.The Annals of Statistics, 32(1):56–85, 2004. 14 Technical Appendices Contents A Gaussian Mixtures Model Properties 16 B Proofs Omitted from Section 2 17 B.1 Populatio...

    2004

  35. [43]

    Triangle inequality

    which will be used in the sequel. C.2.1 Effective Rank of Population Covariances Recall that in our Gaussian mixture model, the population covariance of the noise variableεisΣ, while that of the covariatesXisΓ=Σ+µµ ⊤. Both matrices induce geometries that play a role in our ana...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.