Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Authors: Jingfeng Wu
Peter Bartlett
Matus Telgarsky
Bin Yu
Venue: ICML 2025 poster (2025)
Keywords: Implicit Regularization
GD
Early Stopping
Logistic Regression
Overparameterization
Primary area: theory->deep_learning
TL;DR: We show the statistical benefits of early stopping in GD for high-dimensional logistic regression

Abstract: In overparameterized logistic regression, gradient descent (GD) iterates diverge in norm while converging in direction to the maximum $\ell_2$-margin solution---a phenomenon known as the implicit bias of GD. This work investigates additional regularization effects induced by early stopping in well-specified high-dimensional logistic regression. We first demonstrate that the excess logistic risk vanishes for early stopped GD but diverges to infinity for GD iterates at convergence. This suggests that early stopped GD is well-calibrated, whereas asymptotic GD is statistically inconsistent. Second, we show that to attain a small excess zero-one risk, polynomially many samples are sufficient for early stopped GD, while exponentially many samples are necessary for any interpolating estimator, including asymptotic GD. This separation underscores the statistical benefits of early stopping in the overparameterized regime. Finally, we establish nonasymptotic bounds on the norm and angular differences between early stopped GD and $\ell_2$-regularized empirical risk minimizer, thereby connecting the implicit regularization of GD with explicit $\ell_2$-regularization.

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Jingfeng Wu' Peter L. Bartlett "1 12 Matus Telgarsky" 3 Bin Yu "1
Abstract
explanation is that GD exhibits certain implicit regulariza- rion effects that prevent overfitting.
In overparameterized logistic regression, gradient descent (GD) iterates diverge in norm while con- verging in direction to the maximum marmann solution-4 phenomenon known as the implicit bias of GD. This work investigates additional reg- ularization effects induced by early stopping in well-specified high-die nigh-dimensional logistic regres- sion. We first demonstrate that the excess logistic risk vanishes for strype GD but diverges to infinity for GD iterates at convergence. This suggests that carly-stopped GD is well-calibrated, whereas asymptotic GD is statistically inconsis- tent. Second, we show that to attain small excess zero-one risk, polynomially many samples are sufficient for carly-stopped GD, while exponen- tially many samples are necessary for any interpo- lating estimator, including asymptotic GD. This separation underscores the statistical benefits of early stopping in the overparameterized regime. Finally. we establish nonasymptotic bounds on the norm and angular differences between early- stopped GD and fz-regularized empirical risk minimizer, thereby connecting the implicit regu- larization of GD with explicit Ez-regularization.
The implicit regularization of GD is relatively well under- stood in regression settings. Using overparameterized linear regression as an example, amongst all interpolators, GD asymptotically converges the minimum fo-norm inter- polator (Zhang al., 2021). Moreover, when the data variance satisfies certain conditions, the minimum f--norm interpolator achieves vanishing excess risk while fitting training data with constant amount noise, a phenomenon known as benign overfitting (see Bartlett et al., 2020; Tsigler & Bartlett, 2023, and references therein). When the data covariance is general, although benign overfitting may not occur, early-stopped GD (and one-pass stochastic GD) still achieve vanishing excess risk (Bühlmann & Yu, 2003; Yao et al., 2007; Lin & Rosasco, 2017; Dieuleveut & Bach, 2016; Zou et al., 2023; 2022; Wu et al., 2022a). This sug- gests early stopping provides an additional regularization effect for GD in linear regression. Moreover, the statistical effects of early stopping are known to be comparable to that of e-reguularization linear regression (Suggala al., 2018; Ali et al., 2019; Zou al., 2021; Sonthalia et al., 2024).
However, the picture is less complete for classification, where the risk is measured by the logistic loss and the zero- one loss instead of the squared loss. In overparameterized logistic regression, GD diverges in norm while converging in direction to the maximum f2-margin solution (see Soudry et al., 2018; ; Ji & Telgarsky, 2018, and Proposition 2.2 in Section 2), which is in contrast with GD's convergence to the (bounded!) minimum 22-norm solution in the linear regression setting. In standard (fnite-dimensional, low- noise, large margin) classification settings, the asymptotic implicit bias of GD implies generalization via classical mar- gin theory (Bartlett & Shawe- 1999). More recently, certain high-dimensional settings exhibit well-behaved max- imum margin solutions and benign overfitting (see Mon- tanari et al., 2019, for example), but it is unclear if these results apply more broadly or represent special cases. More- over, if the maximum ma-margin solution generalizes poorly, new techniques are required, as the aforementioned least squares techniques cannot be easily adapted owing their
1. Introduction
Modern machine learning often operates in the overparam- eterized regime, where the number of parameters exceeds the number of training data. Despite this, models trained by gradient descent (GD) often generalize well even in the absence of explicit regularization (Zhang et al., 2021; Neyshabur et al., 2017; Bartlett et al., 2021). The common
'Equal contribution University of California, Berkeley Google DeepMind 'New York University. Correspondence to: Jingseng Wu <uuujf@ berkeley.edu>> Peter L. Bartlett <pe- ter@ berkeley..duu>, Matus Telgarsky <mjt10041 @nyu.edu>, Bin Yu <binyu berkclcy.edu>..
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Benefits of Early Stopping in Gradient Descent for Overperameterized Logistic Regression
heavy dependence upon the explicit linear algebraic form of GI's path specific to least squares.
constant c 0 such that f(x) cg(x) or (x) 2 cg(ar) for every x, respectively. We write f(x) g(x) if f(x) S g(x) x f(x). We use the standard big-O nota- tion. For two vectors u and v in Hilbert space, we denote their inner product by (u, v) or equivalently, u v. For two matrices and B of appropriate dimension, we define their inner product as (A, B) := tr(A B). For a positive semi-definite (PSD) matrix A and vector V of appropri- ate dimension, write ||v v Av. In particular, we write ||v|| := ||v||I. For positive integer n, we write [n] == -1.........
Contributions. This work investigates the beneficial regu- larization effects of early stopping in GD for overparameter- ized logistic regression. We focus on a well-specified setting where the feature vector follows an anisotropic Gaussian de- sign and the binary label conditional on the feature is given by a logistic model (see Assumption I in Section 2). We are particularly interested in the regime where the label contains constant level of noise. We establish the following results.
1. Calibration via early stopping. We first derive risk upper bounds for early-stopped GD that can be applied in the overparameterized regime. With an oracle-chosen stopping time, stoly-s GD achieves vanishing ex- cess logistic risk and excess zero-one error (as the sample size grows) for every well-specified logistic regression problem. Furthermore, its naturally induced conditional probability approaches the true underlying conditional probability model. These properties suggest that early- stopped GD is consistent and calibrated for every well- specified logistic regression problem, even in the over- parameterized regime.
2. Preliminaries
Let (x, E [H @ (+1) be a pair of features and the corre- sponding binary label sampled from an unknown population distribution. Here HH is finite or countably infinite dimen- sional Hilbert space. For parameter w E H, define its population logistic risk as
[(w) = Et(yx Tw),
w)) where E(l) == In(I ln(1+
and define its population zero-one error as
E(w) = E1 yyx T w S 0j = Pr(yx w S),
Advantages over interpolation. We then provide neg- ative results for GD without early stopping. We show that GD at convergence, in contrast the typical suc- cesses of maximum margin predictors, suffers from unbounded logistic risk and constant calibration error in the overparameterizeed regime. Moreover, for broad class of overparameterized logistic regression problems, to attain a small excess zero-one error, early-stopped GD only needs polynomially many samples, whereas any interpolating estimators, including asymptotic GD, re- quires at least exponentially many samples. These results underscore the statistical benefits of early stopping.
where the expectation is over the population distribution of (x, y). It is worth noting that, different from the logistic risk C(w), the zero-one error {(w) is insensitive to the parameter norm. Moreover, measure the calibration error of parameter w E HI by
C(w) == Elp((w ((w:)) - Pr(y = 1/x)
where p(w:x) is a naturally induced conditional probability given by
1
p(w:x) 1 +xxeppxxx w)
3. Connections é--reguaarization. Finally, we compare the GD path (formed by GD iterates with all possible stopping times) with the fz-regularization path (formed by fz-regularized empirical risk minimizers with all pos- sible regularization strengths). For general convex and smooth problems, including logistic regression, these two paths differ in norm by a factor between 0.585 and 3.415, and differ in direction by an angle no more than /4. Specific to overparameterized logistic regression, the fz-distance of the two paths is asymptotically zero in widely considered situation but may diverge to infinity in the worst case. These findings partially explain the im- plicit regularization of early stopping via its connections with the explicit lg fg-regularization
We say an estimator w is consistent (for classification) if it attains the Bayes zero-one error asymptotically, that is, E( ((w) min E + O. We say an estimator w is calibrated if its induced conditional probability predicts the true one asymptotically (Foster & Vohra, 1998), that is, C(w) + O.
Gradient descent. Let (xi, be n independent copics of yx. Define the empirical risk as
k(w) = 1 n n
Σ 1yxxx w),
we H.
Then the iterates of gradient descent (GD) are given by
For two positive-valued functions f(z) and g(x), we write f(x) S g(x) or f(x) Z g(x) if there exists
Notation.
Wp = 0, Wi+1 = W. - -1/VD(wss) 12 0, (GD)
2

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
0.40
20
0.35
2-1
logistic risk
zero-one error
0.25
training test
training
2-7
0.20
test
bayes risk
bayes risk
2-3
0.15
0.30
2-
R50
0.10
0.29
0.45
0.05
0.20
2-3
0.00
10a
102
10a
10
10
10c
107
10
102
10a
10
10a
10
107
opt length
opt lenghhtth
(a) Empirical and population logistic risk
(b) Empirical and population zero-one error
Figure 1. The logistic risk and zero-one error along the GD path for an overparamcterized logistic regression problem. Here d = 2000, v 1000, X 2 W6:100 1 and w100: 0. The optimization length measured by ntt. The plots show that the excess logistic risk and excess zero-one error are both small for GD with appropriate early stopping, and both grow larger when GD enters the interpolation regime. These demonstrate the regularization early stopping GD.
where 17 > is a fixed stepsize. We consider zero initial- ization to simplify the presentation, which does not cause the loss of generality. We aim compare asymptotic GD, that Woo. with carly-stopped GD, that is, Wt at certain finite stopping time t oc.
Proposition 2.1 suggests that the Bayes logistic risk and Bayes zero-one error are attained by the true model param- eter w Moreover, the excess zero-one error is controlled by the calibration error, which further controlled by the excess logistic risk. Thus under Assumption estimator is also consistent for classification, and an estima- tor is calibrated if it attains the Bayes logistic risk asymp- totically. However, the reverse might not be true. As we will show later, for overparameterized logistic regression, early- early-stopped GD calibrated and consistent for both lo- gistic risk and zero-one error. In contrast, asymptotic GD is poorly calibrated and attains an unbounded logistic risk, although it could be consistent for zero-one error.
calibrated
Data model. We mainly focus well-specifted setting formalized by the following conditions. However, part of our results can also be applied to misspecified cases.
Assumption (Well-specificatioo)) Let Σ E H be posi- tive semi-defiitte (PSD) and tr(E) oc. Lef w HH be such that ||w" xx Assume that (x, y) H & {+1) is given by
x NO, Pr(ylx) I+ exp( yo w*)
Noise and overparameterization. Most of our results should be interpreted in the noisy and overparameterized regime. Specifically, this means
Under this data model, have the following standard prop- erties for the logistic risk, zero-one error, and calibration eтror (see for example (Ji et al., 2021) or Section 4.7 in (Mohri et al., 2018)). The proof is included in Appendix A.1 for completeness.
l/w" || S 1 and rank Σ 2 n.
The first condition ensures the population distribution car- ries a constant amount of noise, as the Bayes logistic risk and Bayes zero-one error are lower bounded by a constant according to Proposition 2.1. In other words, the popula- tion distribution is strictly not linearly separable. Despite so, the second condition ensures the linear separability of the training data almost surely, the number of effective parameters exceeds the number of training data. In this regime, estimators can interpolate the training data, yet this interpolation inherently carries the risk of overfitting and poor calibration. Our setting aligns well with the prior setting for studying benign overfitting in linear regression (Bartlett al., 2020; Tsigler Bartlett, 2023).
Proposition 2.1 (Basic properties). Under Assumption 1, we have
A. w' = arg min C(-) and w E arg min E-));
B. for every w E H., it holds that
E(w) - min - E s 2/C(w) S V2. v [(w) min L;
additionally we have |w" || x 1, then
min Z min 2
3

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Asymptotic implicit bias. When the training data is lin- early separable (implied by overparameteriiationn) prior works show that GD diverges to infinite in norm while con- verging in direction to the maximum l2 mm-man direction (Soudry et al., 2018; Ji & Telgarsky, 2018) 8). This character- izes the asymptotic implicit bias of GD. See the following proposition for a precise statement.
3. Upper Bounds for Early-Stopped GD
In this section, we present two risk bounds for early-stopped GD for overparameterized logistic regression and charac- terization of the implicit bias of early stopping in GD.
3.1. Bias-Dominating Bound
Proposition 2.2 (Asymptotic implicit bias). Assume that rank(xx xi...... .x,,x))) 2 n. Then the training data (x4, 86)==1 linearly separable, that is,
We first provide a bias- dosinaaiinngg excess logistic risk bound for early-stopped GD in overparameterized logistic regres- sion. The proof is deferred to Appendix B.1.
Theorem 3.1 (A "bias ditasddominatigg" risk bound). Suppose that Assumption holds. Let be an arbitrary index. Sup- pose that the stepsize for (GD) satisfies
max min yi W > 0. |
Let w be the maximum 22-margin direction, that is,
11 6r + X In(1/0)/n))
arg max min y:x;
[ [1
where Co > 1 is a universal constant. Then with probability at least 1 8, there exists stopping time t such that
Then w is unique and the following holds for (GD) with any stepsize 17 > 0:
[(wi) S [(wo:k) S ((w.-1).
|wel + 00,
W
w,
Moreover, for (GD) with this stopping time we have
||
((we) - min L S
Proof of Proposition 2.2. Let X == (x....., x,) xn) and
max {1, tr E
[ Ozk
[2] In (n/5) +
= (.1,..., yn) Since rank(X) (X) 2 n, the ordinary least squares estimator
k:oe
The existence of the desired stopping time is because GD minimizes the empirical risk monotonically (Ji & Telgarsky, 2018). In Theorem 3.1, choose k minimize the upper bounds. Intuitively, & determines the number of dimensions in which early-stopped GD is able to learn the true param- eter. Moreover, early-stopped GD ignores the remaining dimensions and pays an "approximation" error. few more remarks on Theorem 3.1 are in order.
w = X (XX
is well-defined. This implies the linear separability of the training data as Xw = y. If two distinct directions W and Wa achieve the maximum & la-margin, the direction of their average achieves a larger margin, which is a contradiction. So w must be unique.
For logistic regression with linearly separable data, the im- plicit bias of GD is established by Soudry al. (2018); Ji & Telgarsky (2018) when the stepsizes are small such that [(w:) decreases monotonically. The same results can be extended to GD with any fixed stepsize using techniques from (Wu et al., 2023; 2024).
Calibration and consistency. Theorem 3.1 implies that strly-stopped GD attains the Bayes logistic risk asymptoti- cally for any logistic regression problem satisfying Assump- tion 1. To see this, we pick k as increasing function of n such that ||w = o(n). Then || l/> = o(1) since k increases as n increases (recall that |[w" || is finite by As- sumption 1). Hence the risk bound Theorem 3.1 implies that
L
Additional notation. The following notations are handy for presenting our results. Let (Ax)221 be the eigenvalues of the data covariance Σ, sorted in non-increasing order. Let be the eigenvector of Σ corresponding to A; Let (m(1)) 121 be resorted indexes such that (a()) (uT(o) w*)? is non-increasing as a function of i. Define
[(w.) min L o(1) as increases.
By Proposition 2.1, this also ensures that early-stopped GD induces conditional probability that approaches the true one and achieves vanishing excess zero-one error. Hence early-stopped GD is calibrated and consistent for any well- specified logistic regression problem.
Work
Σ Cu (() iSk
W w
W
Σ E (() w
1>4
As a concrete example, let us consider the following source and capacity conditions (Caponnetto & De Vito, 2007),
is clear that ||w'||> < oc implies that w = o(1) as l increases.
X -iT Au(u, wTT ~
a
(1)
4

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Then Theorem 3.1 implies
arbitrary index. Suppose that the stepsize for GD satisfies the same condition as in Theorem 3.1 and the stopping time t is such that
{ [0(n > a +1 (((
[(w)) - min C
b b a
[(w,) S [(w") S ((w.-)).
This provides an explicit rate on the excess risk. Note that the obtained rate might not be the sharpest. An improved rate under stronger conditions is provided later in Theo- rem 3.2. Note that our main purpose here is to show the calibration and consistency of early-stopped GD for every well-specified logistic regression problem.
Assume for simplicity that || 2 A1 E 1, and tr tr(E) 2 1. Then with probability at least - 6, we have
((
+V Eise de
[(w)) min C S.1lw"
+
72
n2
tr tr(z) In (n I tr (r())//))
Stopping time. Note that the stopping time relies on the oracle information of the true parameter w Therefore the "early-stopped GD" in Theorem 3.1 is not a practical algo- rithm. Instead, we should view Theorem 3.1 as a guarantee for GD with an optimally tuned stopping time. It will also be clear later in Section 4 that the optimal stopping time t must be finite for overparameterized logistic regression. Moreover, we point out that the stopping time t is a function of l and thus also depends on the sample size n.
Comparing Theorems 3.1 and 3.2. Compared to The- orem 3.1, Theorem 3.2 achieves faster rate, but only applicable when ||w*|] < co. Specifically, in the classical setting where ||w*|| || ~ and Σ La- the excess risk bound in Theorem 3.2 decreases at the rate of O (d/n) while that in Theorem 3.1 decreases at the rate of ((V//n). For another example, under the source and ca- pacity conditions of (1), Theorem 3.2 provides an improved excess risk bound of (n=a/(1+e)) when b a + 1, but not applicable when b S a a++1. 1.
Although the stopping time in Theorem 3.1 is implicit, one can compute an upper bound on it using standard optimiza- tion and concentration tools. Specifically, GD converges in (1/(l) rate as the empirical risk is convex and smooth. Moreover, we can compute [(wo.k) using concentration bounds. These lead to an upper bound on the stopping time.
The stopping time in Theorem 3.1 is designed to handle more general high-dimensional situations that even allow |w''|| = xc. It tends to stop "earlier" so that the bias error tends to dominate the variance error. In comparison, Theorem 3.2 is limited to simpler cases where ||w*]| < oo and sets a "later" stopping time so that the variance error tends to dominate the bias error. Therefore Theorem 3.2 achieves faster rate.
Misspecification. For the simplicity of discussion, we state Theorem 3.1 in well-specified case formalized by As- sumption 1. Nonetheless, from its proof in Appendix B. it clear that the same results also hold in misspecified cases, where we define w* E arg min L and assume Σ is subGaussian. Here, we do not need to make assumptions the true conditional probability Pr(y|x). In those misspec- ified cases, however, Proposition 2.1 may not hold. Thus Theorem 3.1 only provides a logistic risk bound but does not yield any bounds on calibration error or zero-one error.
Future directions. Theorems 3.1 and 3.2 are sufficiently powerful for our purpose of demonstrating the benefits of early stopping. However, we point out that neither The- orems 3.1 nor 3.2 reveal the true trade-off between the bias and variance errors induced by early stopping. This is unsatisfactory given that in linear regression, the exact trade-off between bias and variance errors has been settled for one-pass SGD (Zou al., 2023; Wu al., 2022a;b) and fz-regularization (Tsigler & Bartlett, 2023), and has been partially settled for early-stopped GD (Zou et al., 2022, as- suming a Gaussian prior). We leave the improvement of these bounds for future work.
We also note that the proof of Theorem 3.1 can be adapted to other loss functions that are convex, smooth, and Lipschitz.
3.2. A Domiinatn Bound
From Theorem 3.1, we see that early-stopped GD is con- sistent and calibrated under the arguably weakest condition on the true parameter, ||w || < co. However, the attained bound decays at rate no faster than ((1/vn)
From a technical perspective, the gap in analysis between linear regression and logistic regression is significant. All the prior sharp analyses of GD in linear regression make heavy use of explicit calculations with chains of equalities and closed-form solutions. But these fail to hold for GD in logistic regression since the Hessian is no longer fixed. While one might suspect that a limiting analogy can be made where least squares ideas are applied locally around
long as [[w'lx ||x Z 1. In the simpler case where |w"l| < co, we can tune the stopping time to achieve an improved bound. This is presented in the following theorem. The proof is deferred to Appendix B.2.
Theorem 3.2 (A pariiacce-dmmiattion risk bound). Sup-
pose that Assumption holds with ||w*|| < co. Let be an
5

---

Cz. Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
an optimum, priori there is no reason to believe that the GD path, which diverges to infinity, even passes near the population optimum, let alone spends reasonable amount of time there. Moreover, as our lower bounds in Section 4 attest, the GD path exhibits significant curvature. Due to these issues, we believe tools from linear regression can not be merely ported over, and new approaches are required. While we have provided some tools to this end, as above Theorems 3.1 and 3.2 do not tightly characterize the GD path, and much is left to future work.
4.1. Logistic Risk and Calibration Error
The following theorem shows that GD without early stop- ping must induce unbounded logistic risk and positive calibration error in the overparameteriized regime. The proof is deferred to Appendix C.I.
Theorem 4.1 (Lower bounds for logistic risk and calibration error). Suppose that Assumption holds. Let w be a unit vector such that || >> and let (We)120 be a sequence of vectors such that
3.3. Implicit Bias of Early Stopping
[well - 0C,
|wwl
We
+ w.
In this part, we briefly discuss the proof ideas by introduc- ing the following key lemma in our analysis. Variants of this lemma have appeared in (Ji & Telgarsky, 2018; 2019; Shamir, 2021; Telgarsky, 2022; Wu et al., 2024) for analyz- ing different aspects of GD. For completeness, we include a proof of Appendix A.2.
Then we have
lim C(w:) 2 exp(-C([w""Ix)) 1-
lim L(W:) = Oc., t000
where C > 1 is constant.
Theorem 4.1 shows that for every sequence of estimators that diverges in norm but converges in direction, their in- duced logistic risk must grow unboundedly and their in- duced calibration error must be bounded away from zero by constant. Therefore, their limit is inconsistent (for logistic risk) and poorty calibrated. According to Proposition 2.2, this applies to GD iterates in the overparameterized regime.
Lemma 3.3 (Implicit bias of early stopping). Let [()) be convex and B-smooth. Lef (We)120 be given by (GD) with stepsize 1) S 1/3. Then every u, we have
W. - ull
|ul
+ [(w,) < E(u)+ +
1>0.
2xyl
2np
This lemma reveals an implicit bias of carly-stopping, in which early-stopped GD attains a small empirical risk while maintaining a relatively small norm. Specifically, consider a comparator u and a stopping time t such that
Combining this with our preceding discussion, we see that for every well-specified but overparameterized logistic re- gression problem, GD is calibrated and consistent (for lo- gistic risk) when early stopped, but is poorly calibrated and inconsistent (for logistic risk) at convergence. This contrast demonstrates the benefit of early stopping.
((w)) S E(u)= S ((w.-1).
This stopping time together with Lemma 3.3 (applied to t 1) leads to
4.2. Zero-One Error
[(w, S [()). and ||w-- ul| < ||u]]
The preceding lower bounds Theorem 4.1 are tied the divergence the norm of the estimators. In this part, we show that even when properly normalized, interpolating estimators are still inferior to early-stopped GD. To this end, we consider the zero-one error that is insensitive to the estimator norm. We provide a lower bound on that for interpolating estimators in the next theorem. The proof is deferred to Appendix C.2.
By optimizing the choice of the comparator we see that early-stopped GD achieves a small empirical risk with a relatively small norm.
Besides Lemma 3.3, the remaining efforts for proving The- orems 3.1 and 3.2 using classical tools of Rademacher complexity (Bartlett & Mendelson, 2002; Kakade et al., 2008) and local Rademacher complexity (Bartlett et al., 2005), respectively. More details can be found in Appen- dices B.1 and B.2.
Theorem 4.2 (A lower bound for zero-one error). Suppose that Assumption I holds. Let C2 C > be two suffi- ciently large constants. Assume that ///ww" is k-sparse and 1/C, < [| CC. Assume that
Later in Section 5, we will use Lemma 3.3 to show connec- tions between early stopping and eg-regularization. We also note that the proof of Theorems 3.1 and 3.2 can be easily adapted to Ey-regularized empirical risk minimizes.
rank(E)
n > Ckln((/00, C. n (nnnn)]n(11))
Then with probability at least 1 6, for every interpolating estimator V such that minee(m) V. w > 0. we have
4. Lower Bounds for Interpolating Estimators
In this section, we provide negative results for interpolating estimators by establishing risk lower bounds for them.
1
E(w) min
v MIn(n) In(1/8)
6

---

Benefits of Early Stopping in Gradient Descent for Overparameterixed Logistic Regression
Theorem 4.2 characterizes a class of overparameterized logistic regression problems where every interpolating es- timator needs at least an exponential number of training data to achieve a small excess zero-one error. This ap- plies to asymptotic GD as it converges to the maximum ma-margin solution by Proposition 2.2. In contrast, Theo- rems 3.1 and 3.2 suggests that early-stopped GD can achieve small excess zero-one error using at most a polynomial number of training data under weak conditions. These weak conditions can be, for example, ||w*| < oo or the sparsity parameter k does not grow with (see also the examples given by (1)). This separation underscores the benefits of early stopping for reducing sample complexity.
connection in convex (not necessarily strongly convex) and smooth problems, then establish an asymptotic but ab- solute connection in overparameterized logistic regression problems.
5.1. A Global Connection
The following theorem presents global comparison of the norm and angle between the GD and ég-regularization paths. The proof exploits the implicit regularization results in Lemma 3.3 and is included in Appendix D.I.
Theorem 5.1 (A global bound). Let E()) be convex and
B- B-smooth. Consider (wi)e20 given by (GD) with stepsize S 1/8 and (ux)220 given by (2). Set X == 1/())). Then we have
The intuition behind Theorem 4.2 is that there are informa- tive dimensions and a lot more uninformative dimensions. Since > k the training set cannot be separated purely using the k informative dimensions. Thus, interpolators must use the uninformative dimensions to separate the data, leading to the risk lower bound.
1
for every t > 0, - S lwwlll
/2
As direct consequence, the following holds everyt > 0:
Future direcition. Note that Theorem 4.2 applies to every interpolating estimator. When restricted to the maximum &-- margin estimator, the one that GD converges to in direction, we conjecture that a constant lower bound on the excess zero-one error be proved, especially when the spectrum of the data covariance matrix decays fast. This is left for future investigation.
1
COs (W,, U1) 2
V22
v2
V2
| S
well S v2 - ||ux||-
1 1 V2
Theorem 5.1 establish a global but relative connection be- tween the GD and fz-regularization paths for all convex and smooth problems. Specifically, starting from the same zero initialization, the angle between the two paths is no more than π 7/4, and the norm of the two paths differs by factor within 0.585 and 3.415. We point out this relative connection holds globally for every stopping time (with its corresponding regularization strength) and for every convex and smooth problem. In particular, it applies to overparam- eterized logistic regression, which is smooth and convex but not strongly convex. We also note that using the norm bounds in Theorem 5.1, the upper bounds in Theorems 3.1 and 3.2 for early-stopped GD can be casily adapted to E-- regularized ERM.
5. Early Stopping and l2- Gg-Reuularization
Sections and 4 demonstrate that early stopping carries certain regularization effect that benefits its statistical performance. This regularization is, however, implicit. In this section, we attempt to provide some intuitions of the implicit regularization of early stopping by establishing its connections to an explicit, l-rrgulaatization. An lz- regularized empirical risk minimizer (ERM) is defined as
X 2 I|lli
uy := arg mig L(u)
(2)
where À > 0 is the regularization strength. Note that uy is unique and well-defined as long as [(-) is convex, whereas Z(+) does not have to have a finite minimizer. We refer to (ux)aso given by (2) as the fz-regularization path. Simi- larly, we refer to (wi)eso given by (GD) as the GD path.
Theorem 5.1 cannot be improved without making further assumptions. This is because the GD and E--reullarization paths could converge two distinct limits (as - oc and A 0) in convex but non-strongly convex problems (see Suggala et al., 2018, Section 4). So in general, we cannot expect their distance to be small in the absolute sense.
In linear regression, prior works showed that the excess risk of carly-stopped GD (and one-pass SGD) is compa- rable to that of Ez-regularized ERM (Ali et al., 2019; Zou et al., 2021). For strongly convex and smooth problems, Suggala et al. (2018) provided bounds on the fz-distance be- tween the GD and fzrrguularizatin paths. In what follows, we establish more connections between the GD and lg- regularization paths. We first establish relative but global
5.2. An Asymptotic Comparison
We have established a global but relative connection be- tween the GD and lz-reuularization paths in Theorem 1. We now turn to logistic regression with linearly separable data and establish an absolute but asymptotic connection between the two paths.
7

---

Benefits of Early Stopping in Gradient Descent for Overperameterixed Logistic Regression
In logistic regression with linearly separable data, both GD and f--regularization paths diverge infinite in norm (as t xo and À + 0) while converging in direction to the maximum ma-mari solution (Rosset et al., 2004; Soudry et al., 2018; Ji & Telgarsky, 2018; Ji et al., 2020). Therefore their angle tends to zero asymptotically (Suggala et al., 2018; Ji et al., 2020). This characterization is more precise than the 4/4 global angle bound from Theorem 5.1.
that this implies their angle converges to zero, and is more precise than the relative norm bound from Theorem 5.1.
However, this sharp asymptotic connection is strongly tied to Assumption 2. Surprisingly, when Assumption 2 fails to hold, the lz-distance between the GD and lz-regularization paths could tend to infinity instead. This is shown in the following theorem. The proof is deferred to Appendix D.3.
Theorem 5.3 (A counter example). Consider the following dataset
However, it remains unclear how the fz-distance between the two paths evolves in logistic regression with linearly separable data. Quite surprisingly, we will show that their fg-distance tends to zero under a widely used condition (Soudry et al., 2018; Ji & Telgarsky, 2021; Wu et al., 2023), but could diverge to infinity in the worst case.
X1 = (7: 91 11 X2 == (2: 1/2 == 1,
where 0 < 72 <7 < 1. Then (x,, is linearly sepa- rable but violates Assumption 2. Let (We)120 and (ux)x20 be the GD and fz-regularization paths respectively for lo- gistic regression with (x,, yi) Then ||well + oo as cc. Moreover, for every map X R220 + R22, we have
Let X = (Xi....,,,,, x T and y == (yi,...., yn) T be set of linearly separable data. Then the Lagrangian dual of the margin maximization program in Proposition 2.2 is given by (see Hsu et al., 2021, for example)
l| - ux(1)l -x())l 2 In + 00.
s.t. y:B, 2 0, i E [n]. 1 xx - -
This simple yet strong counter-example suggests that the ly-distance between the GD and fz-regularization path can diverge to infinity when Assumption 2 fails to hold.
max BER
Here, 33 are the dual variables multiplied by y entry-wise. Let ,3 be the solution to the above problem. Let S+ = {i E [n] 3, > 0} be the set of support vectors (with strictly positive dual variables). The following condition assumes the coverage of the support vectors.
Future directions. We conjecture that for logistic regres- sion with linearly separable data, the limit of the d--dsttacce between the GD and fz-regularized paths is either zero or infinity, and the phase transition is determined by a certain geometric property of the dataset (for example, Assump- tion 2). The reasoning behind this conjecture is as follows. Note that Assumption implies that the dataset projected perpendicular to the max-margin direction (called "pro- jected dataset") strietly nonseparable (Wu et al., 2023, Lemma 3.1). This is the main property used in Theorem 5.2. Moreover, in Theorem 5.3, the "projected dataset" is non- separable but with margin zero we conjecture this property is sufficient for Theorem 5.3 to hold. Now for a generic separable dataset, we check the "projected dataset": if it is strictly nonseparable, Theorem 5.2 holds; if it is nonsep- arable but with margin zero, we conjecture Theorem 5.3 holds; otherwise, it is separable (with positive margin), we decompose the dataset recursively. This is the reasoning behind our conjecture.
Assumption 2 (Support vectors condition). Assume that rank(x; : i E S+] = rank/x; : [n]]
Assumption 2 has been widely used in the analysis of the implicit bias (Soudry et al., 2018; Ji & Telgarsky, 2021; Wu al., 2023). In particular, Assumption 2 holds if every data is support vector, which is common in high-dimensional situations (Hsu et al., 2021; Wang & Thrampoulidis, 2022; Cao et al., 2021).
The following theorem provides an asymptotic bound on the Ez-distance between the GD and l fgrrgularrization paths under Assumption 2. The proof deferred to Appendix D.2.
Theorem 5.2 (An asymptotic bound). Let (x4, y.);= be a linearly separable dataset that satisfies Assumption 2.
Let (we) and (ux)x>o be the GD and re-rgaalaiinaiion paths, respectively, for logistic regression with (xi, yi Y= Then there exists X as a function of t such that
It also remains unclear to what extent early stopping repli- cates the effects of explicit regularization for logistic re- gression. Specifically, is there a logistic regression example such that carly-stopped GD has a better calibration/logistic risk rate than ezreeuulaizzatin vice-versa? This is left for future investigation, as our current bounds are not sharp enough to yield concrete answer.
W uxxell + 0, while [wells [|xx|])] + oo,
as f-----00- + 20.
For logistic regression with linearly separable data under Assumption 2, Theorem 5.2 shows that the Ey-distance be- tween the GD and l fzrreulaarization paths tends to zero, de- spite that both paths diverge to infinity in their norm. Note
6. Related Works
We now discuss additional related works.
8

---

Benefits of Early Stopping in Gradient Descent for Overperameterized Logistic Regression
Benign overfitting in logistic regression. A line of work shows the benign overfitting of the asymptotic GD (or the maximum mg-margin estimator) in overparameterized logis- tic regression under variety of assumptions (Montanari et al., 2019; Chatterji & Long, 2021; Cao et al., 2021; Wang & Thrampoulidis, 2022; Muthukumar et al., 2021; Shamir, 2023). Our results are not a violation of theirs, instead, we show an additional regularization of early-stopping, which brings statistical advantages of early-stopped GD over asymptotic GD such as calibration and a smaller sam- ple complexity.
comparison, we consider overparameterrized logistic regres- sion with strictly non-separable population distribution, where the risk of overfitting is prominent. In this case, our results suggest that early stopping plays a significant role in preventing overfitting.
Early stopping for classification. In the boosting liter- ature, an early work by Zhang & Yu (2005) showed that boosting methods (that can be interpreted as coordinate de- scent) with early stopping are consistent in the classification sense; related refined studies for boosting with the squared loss with early stopping were also provided by Bühlmann & Yu (2003). The paper is also notable for giving the first proof of boosting methods converging the maximum mar- gin solution (Zhang & Yu, 2005, Appendix D), which was later refined with rates by (Telgarsky, 2013). Their results can be converted to GD. In particular, related concepts were used to prove consistency of early-stopped GD for shallow networks in the lazy regime (Ji et al., 2021). In contrast with the present work that focuses on high- high-dimensional cases, the preceding works only deal with inite-dimensional settings. Moreover, none of those works provide lower bounds for interpolating estimators and tight links to the regularization path which are provided in the present work.
M-estimators for logistic regression. In the classical fi- nite d-dimensional setting, the sample complexity of the empirical risk minimizer (ERM) for logistic regression is well-studied (Ostrovskii & Bach, 2021; Kuchelmeister & van de Geer, 2024; Hsu & Mazumdar, 2024; Chardon et al., 2024), where the minimax rate is known to be (d/nn). Different from theirs, we focus on an overparameterized regime, where the ERM of logistic regression does not even exist. When specialized to their setting, our Theorem 3.2 recovers the comparable (d/nz) rate.
In the nonparametric setting, the works by (Bach, 2010; Marteau-Ferey et al., 2019) provided logistic risk bounds for fz-regularized ERM. Bach (2010) only considered a fixed design setting, whereas Marteau-Ferey et al. (2019) required that ||w*|] < co. Different from theirs, we aim to understand the benefits of the implicit regularization of early-stopping. instead of that of explicit &2 f-regulaarizatonn Moreover, we show that early-stopped GD achieves a van- ishing excess logistic risk as long as |ww || < co, without assuming a finite || In the regimes where our results are directly comparable, however, our risk bounds might be less tight than theirs. We leave as a future work to improve our current bounds.
Classification calibration. Proposition 2.1 captures a very nice consequence of logistic loss minimization: cali- bration and classiiictionncaaiiratii of the optimal conditional probability model and of the opti- mal classifier. For more general convex losses, the ability to construct a general conditional probability model was devel- oped by Zhang (2004) as a conceptual tool in establishing classification calibration, but without explicitly controlling calibration error. A further abstract treatment of classifica- tion calibratoin was later presented by Bartlett et al. (2006). The refined statistical rates, separations, and early-stopping consequences studied in the present work were not consid- ered in those works.
respectively recovery
The work by Bach (2014) considered one-pass SGD for logistic regression assuming strong convexity around the true model parameter. This strong convexity assumption, however, is prohibitive in our high-dimensional settings.
7. Conclusion
There is a line of works (Sur& Candès, 2019; Candès & Sur, 2020) focused on the existence of ERM for logistic regres- sion in propotional limit setting (assuming that n, d + in fixed ratio, see also (Chardon et al., 2024) in the finite- dimensional setting). This is quite apart from our focus, where ERM never exists due to overparameterization.
We show the benefits of early stopping in GD for overpa- rameterized and well-specified logistic regression. We show that for every well-specified logistic regression problem, early-stopped GD is calibrated while asymptotic GD is not. Furthermore, we show that early-stopped GD achieves a small excess zero-one error with only a polynomial number of samples. in contrast to interpolating estimators, includ- ing asymptotic GD, which require an exponential num- ber of samples to achieve the same. Finally, we establish nonasymptotic bounds on the differences between the GD and the lg E-regularizzttio paths. Altogether, we underscore the statistical benefits of early stopping, partially explained by its connection with ez-rguulaiization.
Separable distribution. There are logistic risk bounds of early-stopped GD (and one-pass SGD) developed in the noiseless cases, assuming separable population distribu- tion (Ji& & Telgarsky, 2018; Shamir, 2021; Telgarsky, 2022; Schliserman & Koren, 2024). These results do not imply any benefits of early stopping, as their setting noiseless. In

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Acknowledgments
National Academy of Sciences, 117(48):30033-3007) 2020.
We gratefully acknowledge the support of the NSF for FODSI through grant DMS-2023505, of the NSF and the Simons Foundation for the Collaboration on the Theoreti- cal Foundations of Deep Learning through awards DMS- 2031883 and #8 14639, of the NSF through grants DMS- 2209975 and
Bartlett, P. L.,, Montanari, A., and Rakhlin, A. Deep learn- ing: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
and of the ONR through MURI award N0001421 12431. The authors are also grate- ful to the Simons Institute for hosting them during parts of this work.
Bühlmann, P. and Yu, B. Boosting with the 1 2 loss: regres- sion and classification. Journal of the American Statisti- cal Association, 98(46))3224333) 2003.
Candès, E. J. and Sur, P. The phase transition for the existence of the maximum likelihood estimate in high- dimensional logistic regression. The Annuls of Statistics, 48(():27-42, 2020.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Cao, Y., Gu, Q., and Belkin, M. Risk bounds for over- parameterized maximum margin classification on sub- gaussian mixtures. Advances in Neural Information Pro- cessing Systems, 34:8407-84 -4188, 2021.
References
Caponnetto, A. and De Vito, E. Optimal rates for the regu- larized least-squares algorithm. Foundations of Compu- tational Mathematics, 7:331-368, 2007.
Abramowitz, M. and Stegun, I. Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables. Applied mathematics series. Dover Publications, 1965. ISBN 9780486612720.
Chardon, H., Lerasle, M., and Mourtada, J. Finite-sample performance of the maximum likelihood estimator in logistic regression. arXiv preprint arXiv:2411.02137, 2024.
Ali, A., Kolter, Z., and Tibshirani, A continuous time view of early stopping for least squares regression. In The 22nd international conference on artificial intelligence and statistics, pp. 1370-1378. PMLR, 2019.
Chatterji, N. S. and Long, P. M. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22 (12:: 1-30, 2021.
Bach, F. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:384 414,, 2010.
Bach, F. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. The Journal of Machine Learning Research, 15(1):595-627, 2014.
Diculeveut, A. and Bach, F. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4):1363 1399, 2016. doi: 10.1214/ 15-AOS1391.
Bartlett, P. and Shawe-Taylor, J. Generalization perfor- mance of support vector machines and other pattern clas- sifiers. Advances in Kernel methods-suppon vector learning, pp. 43-54, 1999.
Foster, D. P. and Vohra, R. V. Asymptotic calibration. Biometrika, 85(2):379-390, 1998.
Hsu, D. and Mazumdar, A. On the sample complexity of parameter estimation in logistic regression with normal design. In Agrawal. and Roth, A. (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp- 2418-2437. PMLR, 30 Jun-03 Jul 2024.
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Bartlett, P. L.,, Bousquet, O., and Mendelson, S. Local rademacher complexities. Annals of Statistics, pp. 1497- 1537, 2005.
Hsu, D., Muthukumar, V., and Xu, J. On the proliferation of support vectors in high dimensions. In International Conference on Artificial Intelligence and Statistics, pp. 91-99. PMLR, 2021.
Bartlett, P. L., Jordan, M. L., and McAuliffe, J. D. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156 2006.
Ji, Z. and Telgarsky, M. Risk and parameter convergence logistic regression. arXiv preprint 2018.
Bartlett, L., Long, P. M., Lugosi, G., and Tsigler, A. Benign overfitting linear regression. Proceedings of the
10

---

Benefits of Early Stopping in Gradient Descent for Overperameterized Logistic Regression
Ji, Z. and Telgarsky, M. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. In International Conference Learning Represeniations, 2019.
Rosset, S., Zhu, J., and Hastie, T. Boosting as regularized path to maximum margin classifier. The Journal of Machine Learning Research, 5:941-973, 2004.
Schliserman, M. and Koren, T. Tight risk bounds for gra- dient descent separable data. Advances in Neural Information Processing Systems, 36, 2024.
Ji, Z. and Telgarsky, M. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pp. 772 804. PMLR, 2021.
Shamir, O. Gradient methods never overfit separable data Journal of Machine Learning Research, 22(85): 1-20, 2021.
Ji, Z.,, Dudík, M., Schapire, R. F.,, and Telgarsky, M. Gra- dient descent follows the regularization path for general losses. Conference on Learning Theory, pp. 2109- 2136. PMLR, 2020.
Shamir, O. The implicit bias of benign overfitting. Journal of Machine Learning Research, 24(1 13):1-40, 2023.
Ji, Z., Li, J., and Telgarsky, M. Early-stopped neural net- works are consistent. Advances in Neural Information Processing Systems, 34: 111880051111 2021.
Sonthalia, R., Lok, J., and Rebrova, E. On regularization via early stopping for least squares regression, arXiv preprint arXiv:2406.044: 2024.
Kakade, S. M., Sridharan, K., and Tewari, A. On the com- plexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in neural information pro- cessing systems, 21, 2008.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on sepa- rable data. The Journal of Machine Learning Research, 19(1):282--2788, 2018.
Kuchelmeister, F. and van de Geer, Finite sample rates for logistic regression with small noise or few samples. Sankhya A, pp. 1-70, 2024.
Suggala, A., Prasad, A., and Ravikumar, P. K. Connect- ing optimization and regularization paths. Advances in Neural Information Processing Systems, 31, 2018.
Lin, J. and Rosasco, L. Optimal rates for multi-pass stochas- tic gradient methods. Journal of Machine Learning Re- search, 18(97):1-47, 2017.
Sur, P. and Candès, E. J. A modern maximum-likelihunn theory for high nigh-dimensional logistic regression. Pro- ceedings of the National Academy of Sciences, 116(29); 14516-14525, 2019.
Marteau-Ferey. U., Ostrovskii, D., Bach, F., and Rudi, A. Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance. In Confer- ence on learning theory, pp. 2244-2340. PMLR, 2019.
Telgarsky, M. Margins, shrinkage, and boosting. In Inter- national Conference on Machine Learning. pp. 307-315. PMLR, 2013.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of machine learning. MIT press, 2018.
Telgarsky, M. Stochastic linear optimization never overfits with uundraticall-bboundee losses on general data. In Conference on Learning Theory, pp. 5453-5488. PMLR, 2022.
Montanari, A., Ruan, F., Sohn, Y., and Yan, The gener- alization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the over- parametrized regime. arXiv preprint arXiv: 1911001411, 2019.
Tsigler. A. and Bartlett, L. Benign overfitting in ridge regression. Journal of Machine Learning Research. 24 (123):1-76, 2023.
Muthukumar, V.. Narang, A., Subramanian, V., Belkin, M., Hsu, D., and Sahai, A. Classification vs regression in overparameterized regimes: Does the loss function matter? Journal of Machine Learning Research, 22(222); 1-69, 2021.
Wang, K. and Thrampoulidis, C. Binary classification of gaussian mixtures: Abundance of support vectors, be- nign overfitting, and regularization. SIAM Journal on Mathematics of Data Science, 4(1):260-284, 2022.
Neyshabur, B., Bhojanapalli, S., McAllester, D.,, and Srebro, N. Exploring generalization in deep learning. Advances in neural information processing systems, 30, 2017.
Wu, J., Zou, D., Braverman, V., Gu, Q., and Kakade, S. Last iterate risk bounds of sgd with decaying stepsize for over- parameterized linear regression. In International Con- ference on Machine Learning, pp. 14288024431 PMLR, 2022a.
Ostrovskii, D. M. and Bach, F. Finite-sample analysis of m-estimators using conf-cconc Electronic Journal of Statistics, 15:326-391, 391, 2021.

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Wu, J., Zou, D., Braverman, V., Gu, Q. and Kakade, S. M. The power and limitation of pretraining peetraining-fnetuninng for lin- regression under covariate shift. The 36th Conference on Neural Information Processing Systems, 2022b.
Wu, J., Braverman, V., and Lee, D. Implicit bias of gradi- ent descent for logistic regression the edge of stability. In seiett- Conference Neural Information Pro- cessing Systems, 2023.
Wu, J., Bartlett, P. L., Telgarsky, M., and Yu, B. Large step- size gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. Conference on Learning Theory, 2024.
Yao, Y., Rosasco, L., and Caponnetto, A. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289-31 315, 2007.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Zhang, T.
Statistical behavior and consistency of clas- sification methods based on convex risk minimization. The Annals of Statistics, 32(1):56 85, 2004. doi: 10.
Zhang, T. and Yu, B. Boosting with early stopping: Con- vergence and consistency. Annals of Staristies, pp. 1538- 1579, 2005.
Zou, D., Wu, J., Braverman, V., Gu, Q. Foster, D. P., and Kakade, The benefits implicit regularization from sgd in least squares problems. Advances in Neural Infor- mation Processing Systems, 34:5456-5468, 2021.
Zou, D., Wu, J., Braverman, V., Gu, Q., and Kakade, S. Risk bounds of multi-pass sgd for least squares in the interpolation regime. Advances in Neural Information Processing Systems, 35: 15:11999-12920 2022.
Zou, D., Wu, J., Braverman, V., Gu, Q. and Kakade, S. M. Benign overfitting constant constant-stepsize sgd for linear re- gression. Journal of Muchine Learning Research, (326):1-58, 2023.
12

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
A. Basic Results
A.1. Proof of Proposition 2.1
Proof of Proposition 2.1. We first compute the logistic loss. Define
Px(w)= = 1 1 cxxplxxTw Px 1 ++ expl-xx' w*)
Then under Assumption 1 we have
[(w)= = Ex,y In(1 + exp( exp w)) [y]]]
Ex P In P> (w) + (1 1 In) (1- (x()))
Ex (H(*) + KL (p* Px(w))),
where the first term is the entropy of a Bernoulli distribution with a head probability of p and the second term is the KL divergence between two Bernoulli distributions with head probabilities of px and p> (w(w), respectively. It is then clear that w" the unique minimizer of [(w).
We then compute the zero-one error under Assumption similar calculation can be found in, for example, Lemma 4.5 in (Mohri al., 2018). Note that E(0) 1. If 0, then for every w,
E(w) Ex,y [UX s 0] = Ex0.5(11 x w 0] +1 2 0]) 21 E(w"),
so w" arg min E()) If w # O, we have xTw> Tw" = 0 is measure zero. Then have
E(w") = Ex (px xx w I 20 + (1 p²) x w 2 0]) = Ex min (pxn 1- --x 0.5 < E(O).
It remains to check that E(w*) I E(w) for all *f 0. When w and w are both non-zero, we have x ww 0 and
x w are measure zero, then we have
E(w) - E(w") = Ex.yI [yx w $ 20]
1X T w' s
ExPX [x w S <0]
11 X w' < 0] ) + - (x) x T w 20 - x w 2 0]
ExP2(1 (1 [x w s 0]
x w' <0 + ( +11 [x w" <0] - 1 < 0]
Ex(2p= - 1)(11 [x w - - 1 x w" '00))
Ex(2px 1)1l [x w 5 0] 1 x w > 0] +(1 2p [x w > 0] w <
Ex/21 - 1I [x wx w'
which is always non-negative. Therefore have w' E arg min Eww). We complete the proof of the first claim.
The second claim follows from the following. The calculation is similar to the proof of Theorem 4.7 in (Mohri et al., 2018).
E(w) E(w") = 21 - 1/2 wx Tw w" S 0
$ 2E Ipx - (
[x wx w I 0]
< 21 lp' - Px(w)]
$ 2 Exlp3 Px Px(
2/ ExKL (pt (x())
22- /L(w)= L(w*),
where the last inequality is by Pinsker's inequality. We complete the proof of the second claim.
We now prove the third claim under Assumption 1. Notice that
((w) In + exp(- w)) 2 E2 [yx TyxTw w S 0j In(()) E(w), for all w.
13

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Therefore lower bound Eww)) implies lower bound L(w*). We lower bound (w") by
E(w") = E1
yxx w" 0
E1 [x T w" S 0]
+ expl -x -x( +1 [x] w' 2 0] 1 + exp(x w*)
20g exp(g) w* xx)
1 20
2
exp( /2 /2) dg
1 exp w- |x)
V2
(o
000
exp(-g) (2) exp( ( w/w wl))dg
2π
V2
exp (Iw' /2 / exp ( + |w" 1>) dg
2
/2
v2
[wwllx/V
w /
22T(|/"11 +1)
where we use the following error bounds (Abramowitz & Stegun, 1965),
00
+2 S 0²
- dt
x
x
x + v2
4/T
This completes the proof.
A.2. Proof of Lemma 3.3
Proof of Lemma 3.3. For v 1/9, have the descent lemma, that
1/23
2(w++1) s Z(w.) - w/. + s.w.))l?sssww - VIV2[(:))1
Then for the quadratic potential centered at u, we have
W u//2 = |w u|l² + 2n) (((:() u w + +
W: 11|2+ (((( [(w:)) + 2n ([(.)) - [(we+1))
Iw: u|l² + (n((( -(w++1)),
where the inequality is due to the convexity and the descent lemma. Telescoping the sum and rearranging, have
W: ul2
|wo 1
Σ ((wk) Z(u)
27y
2nyt
Using the descent lemma and the initial condition wo O. we have
W: u11
|/u|2
+ Z(w)) s Z(u) +
2nt
2nt
This completes the proof.
B. Upper Bounds for Early-Stopped GD
B.1. Proof of Theorem 3.1
Lemma B.I. Let B = Co(1 (r()) A (1(16)//), where Co > 1 is sufficiently large constant. Assume that n S 1/3 and is such that L(w2x) S [(w:-1). Then with probability at least 5, we have ||w, wi + || ll-
14

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Proof of Lemma B.I. We first show that the following holds with probability at least 6:
||ž[()]| s VB, ||>[[())]| s.
This is because
vV[w)]] = - Σ e' (vix, w)yixi -
1
| 5
x 113
and
1 Σ (,xx, [)x,xx))xx]]]]
S Σ
n
|
So it remains bound Ei= Bernstein's 's inequality, we have the following with probability at least 1 - 5:
||x Let 2,y be independent Gaussian random variables, then by Assumption 1 and
x
X 2 S ntt((2)) + C1
+c((1 n Σ X3 ln(1/0)+ A ln(1/))
V
S Co(nttr(E) + A In(1/))) EB,
where Co. C1 > 1 are constants.
So far we have shown É is B-smooth and v /B-Lischhiz for 3 > By the stopping criterion, we have [(w S D(we-1). Then by applying Lemma 3.3 W,-1 and Wos we have
W 1 < 2m(( 1))((())) - [(w,-1) + || S 1|
|w-1 - w S | ww
Then by the Lipschitzness, we get
||w, workl S ||w,- wr- ||-11 worl S En
B +
||
S v3 + || S + ||woxell
where we use [B(()]] S VB, 1j S 1/3, and 1. This completes the proof.
Lemma B.2. Let w E arg min C(w), then for every w, we have
((w) < L(w") w w" 11
Proof of Lemma B.2. Notice that
xX T
V2L(w)= = RE" (yx w)xx = (1 + exp(x T w1) + exp(-xTmp
Fxx T = E.
Moreover, we have VL(w*) O. Then by the midpoint theorem, there exists a such that
((w) - L(w*) = (VL(w"), w w*) + 1 (w - VWW - w*) s || w
This completes the proof.
Lemma B.3. Let C1 > be a sufficiently large constant. Then with probability at least -
(1 (1+ tr 3 ln(n/n) In In(1/8)
|C(w)- -[()] S.W)
sup [w Zw
7
15

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Proof of Lemma B.3. This by standard Rademacher complexity arguments for 1-Lipschitz loss and linear function class (Bartlett & Mendelson, 2002; Kakade et al., 2008).
Similarly to the proof of Theorem 3.2, let & := x1 [|| S X] where X is a constant to be determined. Then for x and hypothesis class {w : /w S W the loss f(yx w) is bounded by 1yx w| I WX. By Corollary 4 in (Kakade et al., 2008), the following holds with probability at least 8: for all w such that W S W.
n
V 1
In(1 (28)
El w)
Σ
{ w) S2XW
XW
72
2n
For
x² = C(1 (r())) In(n/o).
by Lemma B.9, we have
L(w) El w) W
sup ||
Moreover, have with probability 1- 6,
x; for -,...,, no which implies
[(w)
( w).
Putting things together with union bound, with probability at least 1 8, we have
W -[(w)
2XW / XW
In(1/(30))
sup (L(w)= || SW
n
2n
(r+t) In(n/d) ln(1/0)
$ C.W
where C > 1 a constant.
Proof of Theorem 3.1. By the stopping condition and Lemma B.1, with probability at least 1 - 8, we have
E(w,) & [(wax), ||w; - w || S 1 + ||
Let W = 1 2|| wo.el |l. Then by Lemmas B.2 and B.3, with probability at least 1 8, we have
[(w:) - L(w")
C(w.) [(we) + [(we) Z(wō..) + Z((wrk) -(woxk) + ((wo:)) L(ww)
(1+
(1+tr(E) (n(n/5) In(1/8) In(1/))
1
$ C
WW
+
113
n
n
2
(1+
In(n/0) In(1/)) ((+))()) tr()))
C(1+ [/aallly
n
This completes the proof.
B.2. Proof of Theorem 3.2
Suppose that Assumption 1 holds throughout this subsection. In this subsection, we define
W 1 2/ w/
x² = 2tr(2) + 20 A1) (4C 3
L. W:=,X,
16

---

Benefits of Early Stopping in Gradient Descent for Overparameterizee Logistic Regression
:== 4C A W3
I VWW,
W
where Co2 Ci > 1 sufficiently large constants. We aim to tools from (Bartlett al., 2005). To this end, consider the following random variables, function class, and loss function:
x = x1 ||| S X], F: x
|w]
S W kW)
8:t ((W
WX
f.
clear that ||x|| S X and f(x) E |-1, 1] for every f E Recall that Rademacher complexity is defined as
R.F = sup fxx))
fEF
where 's are independent Rademacher random variables. The following lemma is Corollary 5.3 in (Bartlett et al., 2005) restated in our context.
Lemma B.4 (Corollary 5.3 in (Bartlett al., 2005)). Let F be class of functions with ranges in [-1, and let & be loss function satisfying
1. There exists f E F such that (E((yf(())) = inf jer (x)))(
2. There exists such that i is L-Lipschitz.
There exists B 2 such that for every f F.
-f s B((E(vf(()) (((x((()))
Let e F be such that
{(nf(x;)) 1 Σ (xx))
1=1
Let & be sub-root function functionn for
which
((r) BLER EF: (2E(( (*(3)) sr..
Then for any v(r), with probability at least 1 -- 8,
(11L 27B) 17
E((yf(()) - (x)) < 705
B +
n
The following lemma provides classical upper bound the Rademacher complexity for the linear function class. Lemma B.5 (Theorem 6.5 in (Bartlett al., 2005)). We have
2k
Σist A
ERA : (2)) Sr]s
nX2
where k is arbitrary index.
Proof of Lemma B.5. The proof is adaptation of the proof of Theorem 6.5 in (Bartlett et al., 2005) in context. We include it here for completeness. Assume Σ is diagonal without loss of generality. Let
= max
W2
2r
2r
where max(:.) is applied entry wise. Recall that 0.5E 3 E&XT = Σ by Lemma B.6. Then by definition, we have
ER, E F I(E( - (x)) sr}
17

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
E
sup
E
sup [w]ss:
,
|w
W:W
w2xx
22
WX
WX
12
R
W
E
71
xxXi
Σ11
WX
0 x
Σ
WX
E X
I-1
1=1
Σ
min
2r
W
2k: nI?
Σist di n.X2
WX
WX
L
where & is an arbitrary index. This completes the proof.
The following lemma establishes several basic effects of clipping the random variable x. Lemma B.6. There exists constant C > such that for every X² 2 2tr(E) + C(1 + A1)t, we have
Pr (r[ 2 x) - exp(-(), (), 1> 1.
In addition, for every C1 by setting 1. 2 2ln(4C1( + X W))) we have
Exx 11 |||x||
X]
1
Σ I
2 E.
201 (1 + X1
3/2 W3)
In particular, this implies Exx T
Exx 1 |||
X| 2 0.5E
Proof of Lemma B.6. By Bernstein's 's inequality, there is a constant such that
tr [) > 2) S exp (- --emin
22 2
Pr ([xx((-ttrEE
tr Σ) An
We then obtain the first claim by setting x tr Σ and adjusting the constant.
To prove the second claim, for any unit vector u. we have
E(x u) ||||||
2 x] s E /E1 ||x 2 X]
S v3E(x u)² / 2 X)
Eu v3exp(-1/2)
The above implies
Exx T 1 |||||| 2 X| /3cxp(-t//23
Setting / 2 1n(44 + Ar W3)) completes the proof.
The following lemma is from (Chardon et al., 2024).
Lemma B.7, There exists a constant C1 > 0 such that for every w, we have
1
1
1 E.
B 1 + exp(x T w) + exp(- w)
C1(1 + w 3.
Proof of Lemma B.7. Let s(t) 1/(1 te t). Define
:: |||] |/>
u
1/22
Σ
z: 1/1 1))
8
18

---

Benefits of Early Stopping in Gradient Descent for Overperameterized Logistic Regression
Then we only need to verify that
Es u1 '1)zzz
C(1+ 8
Hitting the left-hand side of the above with u1, get
23
min {
x(2) e² z
Es' (3z J (z) T u2 Bg (3g)g V
π 3
c1(1+
where the first inequality is by Lemma 25 in Chardon et al. (2024), Hitting that again with a unit vector u2 such that / U2 0, we get
2
5((2)
Es' Tu (z) u2)²² (a (3g) 2 V
min
π
4
Ci
Ci(1+ + 33)
where the first inequality is again by Lemma 25 in Chardon et al. (2024). Together, these two lower bounds and the properties of Gaussian complete the proof.
The following lemma verifies a key condition in Lemma B.4.
Lemma B.8. Let X² 2 2rr(E)= 20(1+ + A1) In (4C1(1+ X W3)) and B 401(1 every ||w|| S W, we have
X2333) 4 Then for
B(x w - x w²)² S W w) - El(yx (w)))
Proof of Lemma B.8. Since Exx 3 E, it suffices to show that
3 < W w) - RE( Tw")).
Recall that w' is the minimizer of Eyx w) (where the expectation is conditional on X, see the proof of Proposition 2.1 in Appendix A. By the midpoint theorem, there exists v between and w (thus ||v|| S W) such that
El(yx w) El(yx w") 2
EL" (yx TaxTval v)(x (w w w²)02)).
Thus it suffices to show
for every v such that ||v|| S W, (yxxxxv)xxX 2 W2X2B E.
This is because
1
Be T v))x
E
1 exp(x T v) 1 exp( Tv) Xx T
I + exp(x v) 1 + exp( -x [v) xx 1 ||x/| S XX]
1 + exp((x v) exp(-xx xx Exx 1 ||x|| > X].
By Lemma B.7, we have
1
E
1+ exp(x v) 1 exp(- - xx 1
Σ
E.
C1(1 |
C1 + x W3)
where C1 > 1 is constant. By Lemma B.6, we have
Exx 1 ||||||
> x -
2C + w33 E.
19

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
So have
Ey v)Xx
E.
3/2 W3) 20 + A1
W/3)
We complete the proof by noting that W 2 401(1+ X W3).
The following lemma controls the effect of clipping on population risk. Lemma B.9. Let X² 2 2tr((r))) + C(1 + A1) 21n tr()). Then for every w such that ||w] S W, we have
[(w) - El(yx Tw) s
Proof of Lemma B.9. By definition and 1-Lipschitzness of é, we have
L(w) EE(yx w)] |Eé(ux w) W w1 [||x|
X])
S 1B] yx wIl |||x|| > X]
| | > X]
W R
X
Pr[[| X)
W tr exp( - t/2) -
where we use Lemma 8.6 and the choice of X. This completes the proof.
The following lemma shows the early-stopped GD has small norm.
Lemma B.10. Let Co (1 + tr(E) A ln/1/)//)), where Co 1 is a sufficiently large constant. Assume that S 1/8 and is such that [(w")= < ((w:-1). Then with probability at least 1 - 8, we have || will S 1 + ||w/].
Proof of Lemma B.10. This is the same the proof of Lemma B.I.
We are now ready to proof Theorem 3.2 using Lemma B.4.
Proof of Theorem 3.2. It is clear that is L-Lipschitz and that ;= :====w",>>> (w*,)/((WX) satisfies
f arg inf ()((( JEF
Moreover, for every f = (w.))/(WX) E F. by Lemma B.8, we have
((((()) W2XE Elyx w -yx Tx
B (El w) - Ee w'))
B((ss(
So far, we have verified the conditions on F and for applying Lemma B.4. Consider the function
j== (WW.))
By Lemma 1.10 we have ||w.|| < W, thus E F. Moreover, by the choice of X and Lemma B.6, with probability 1 1-6, 8, we have X; = x; for all i = 1,..., n. Thus the stopping criterion implies
- n
Ey (x+))
Σ
(xx w.) Z(ww) Z(w") -
71
n
20

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
So we can apply Lemma B.4 to f. With probability at least 1 6, we have
(V(((())) - ((())(()) - 705 r +
(1LL + 27B) ln(1/5)
B
where, by Lemmas B.4 and B.5, r is such that
2k:
Eisk A nx²
2 (())) /LV
nl22
Choosing
4kB²
2B2LL Eisk A nx²
r
n
have
B((vf(()) - Ex(
x
r
+
(L + B) In(11))
B
n1
Bk
T
Eisk d
(I+ B) 1n(1/0 (1)
<
n
X
n
Then applying Lemma B.9, we get
2W
T(w.)= I(w") s ((( - (())
n
Bk
I, X
Ei
(I+ B)
2W
n
n
n
n
(1+ In(1/8) (1 (r()) In ((1 + tr( 11/
(1)
kx1 1/2
Eisede di
S [axx//
+
n
In(1/8) (111/8)/((() (r(2) In (nll || (6)
+ + Eish A
S [Iw')((
n2
n
where we assume ||w*|] 2 1, < 1. and (r(E) 2 This completes the proof.
C. Lower Bounds for Interpolating Estimators
C.1. Proof of Theorem 4.1
Proof of Theorem 4.1. Consider sequence of estimators (Wr)120 such that
||w/l + 00, ws/ w + w,
where is fixed unit vector. Fix small constant y > Define an event
F (x: wo1 S 10 x, ||x||| 1r)(r(E), [x w/ 2 73.
Since x ~ NO, Σ) and [W|] | > O, we have Pr(F)= > O. Let to be such that
We
w
for every t to.
well
20 21r())
Then for every x E F and
2 to. we have
x T We
w ||
2
xx
w
|||||
[w]]
w
||
W
27
10 tr (
2 7 20 /trttrE))
2'
21

---

Benefits of Early Stopping in Gradient Descent for Overperameterized Logistic Regression
Then the population risk of We is
[(w.) = Ex In(1 + exp( w:))
E Σ
1 exp(-yxx wr) In(1 + exp(-1xx wi))
(E
2 Σ
In(1 + exp(-1pp yx wi)l (X 1 exp(pppppp yx (x='"=)))))))) w*)
vE(+1)
In(1 + exp([x wil))
11 F
1 1+exp w'l)
||wel///
2 1 + exp(10/|w" (|x) 1 F
||well//2
[xp(10][w*1]) Pr(F) - oc,
where the last inequality is because |well + xc.
Now we consider the calibration error. Under event F, we have
pxw";x)= 1 exp(-eppp w+)
+ cxp(100 w |1>)' 1 exp(-10||ve w |
exp(-10/ [|))) cxp((100|ww
1-cpp1/))00 11x)
Moreover, under event F, for t to, have
1 + exp(>||w,)l/2) S Sexp(->/lw.l//)
x xTw, w. < 0,
1
p(wrix)= 1 exp( xww)
2 -xp((>//wml//))
x xTw, 2'w, 0.
+ exxp(<>/|ww/1/
These together imply that
Ip(w;;)) p(w";x)] exp(-10] w0)l|
exp(-10/lw" (|)x)
Then for the calibration error, we have
C(w,) = Elp(w;;)) - p(w":x))
2 Elp((w;;)) - p(w": xx] 121 [x
2 [1x) exp(->/lw:ll/ 1/)) Pr(F)
-
Pr(F) > 0.
This completes the proof.
C.2. Proof of Theorem 4.2
Lemma C.1. For a non-zero vector w, let 0 be the angle between 1//2 w and I" Then
π
< 0 S n,
4 2m w' w
2
E(w)- - E(w')
||w
π 2
cos(O))
0 < 0 <
48 max
[ ]
Proof of Lemma C.I. Let s(t) = 1/(1 ett.
Notice that for > 0.
s(t) 1/2 - exp(-tt
1 exp(
1 1
1/(t+1)
t
2
2(1 + exp( -t))
4
22

---

Benefits of Early Stopping in Gradient Descent for Overperameterized Logistic Regression
Since and are identically distributed, have
Pr(yx T w I 0) - Pr(yx T w" 50)
2E1 [x w 0, x w' > 0| [s T w') ) 1/2|
2F1 [x xTw w 0, x=w> > 0| (s(x') T w²) 1/2)
Ex w= [x w <0, 0 w" <1]
4
Without loss of generality, assume that |/|/ 1. We can write / 22/2w* ///l/////"l>> cos v. sin 0, where L
unit vector such that (v1, w²/²w") 0. Since x NO, E), have
Pr(yx w 1 0) Pr T w - 00)
Iw "II
Egg 991 [g cos( - 92 sin (0) < 0, < 91 < 1//|/"/lz> [|x]
|//l
exp ( - (of + / (23/2)dggl dggdgg-
8x
/ogi<<//lw<lbs/r cos g sin
To proceed, we discuss two cases.
. TT2 < O S n, we have cos 0 < 0 and sin 0 2 O. So we have
91 exp ( (- (-(i + /2) d92
Oo91<1/1lw> 0c92
2m
91 exp (- /2f22)ds
Joce <1/]<//
V - -exp(-1//lw"|3
V2T
|| |w*
So we have
Pr(yx] T 5) - Pr(yx
Tolxxxww>> w
50) w I
1
8T
4V2T w |
0 < 0 S 7/2, we have cos 2 0. By changing of variables, we get
91 exp (- (- + /))/2) dg2
<ocn<<//ll>> a1 <99 tan
rsin tepp ( (- y² /2/22) rdrd
Jocr sin Cecrsiinel///ww/e.eesss
1 sin wb
Jocres//ww11> (Sbercy/i-1a
2 ( //2² )r deb
JuCie
/ sin v
1 1 dr dv
2
Jocwico
1
sin v
)d db
2 JocrrcinnL../////
1
sin tbdb
6max (1, |
Jocso
(1
-lscost0
cos 0).
6 6axx |
23

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
So have
1w'/ 1
w M (1
Pr(yx T w S -) " w" 00 2
0
(Os.
8T
48T max
E
This completes the proof.
Lemma C.2. Letz IO,,I) and Pr(ylz) = s(yz=v'). Then for any unit vector v, we have
0.25
Pr(yz
v< Louuzvv-- -0.5) 1 exp([lv=ll)
Proof of Lemma C.2. This is by direct calculation.
E1 [V 1, 2 -0.5] + [y -1 z v 0.5] E1 yz T v < 0.5]
= -Es(z T v²)1 1 v < -0.5] + +s(-z 2 2 0.5]
1
[|/v|> > 0.5]
+ expl 2 v+1)
||zTv| 0.5, Iz w*<|||>")
1 exp([[v*11)
(1 Pr(12 T v = 0.5) - Pr(1z v' 2 |[v
exp
(0.0.5) (1-(4(0.5) -055)) 2(1 o(1))
exp((I| ((
0.25
+ exp([lv*1]
where O is the cumulative distribution function of normal distribution. We complete the proof.
Lemma C.3. Let (yt, D be independent copies of (y, z). Assume that
n 2 C(1 + exp( |v kl))/nk(k/))) Let = {v Vosk = 1, VA: = 0}. Then
for a sufficiently large constant
n/8
Pr for every e S, #li E [n] y.2, T S 0.4] 1 vxxp([(v+11)
21-8.
Proof of Lemma C.3. For each unit vector v, define binary random variable
{(v) = [yz T < 0.5] E 1).
Let (5x(v)) be independent copies of {(v). By the multiplicative Chernoff bound, we have
n
Pr
Σ
(v) s 0.5nEg(v)) S exp ( (-nEE((v)/8)
By Lemma C.2, we have Bg(v)= 2 0.25/ (1 + exp ||) Thus we have
n/8
n/32
Pr Σ < S 1 exp ||v
exp
1
exp([vv*1])
[|
Let C be e-lz-covering of the k-dimensional unit sphere S. Then |C| = (((L/))*). By union bound, we get
nz/8
)
(-
n/32 [ + Ckkn((/e))
Pr for every every VEC,
Σ
<vv)
exp
exp([Iv*[]]
24

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Here C > 1 is sufficiently large constant and may vary line by line. Moreover, with probability least 1 0.56, we have
Pr
max VE(N)
CVkln(n/0) 2 - 0.56. 0.k
Under the joint of the two events, for every E S, there is a v' & such that
for every E [n], yizz v S y:z, T max *E|n]
ooxele l|l S youk v' C Cykln(n/ō)e Suz 0.1,
where we set 00.1/CC Therefore we must have
n/8
for every v ES,
Σ 1 v -0.4] 2 + exp([[v*1])
21 exp
(- 14
n232 cxp([v*11) 1
+ CC
0.50 2 1 1 6,
where in the last inequality we use the assumption that
n > C(1 + exp(e In)
for sufficiently large constant C 1. We have completed the proof.
Lemma C.4. Assume that v* is k-sparse and
n 2 C(1 + exxelxl( ()))(l((")))))(((/00 d2 On In(1//))
where C is a large constant. Then with probability least 6, we have
for every unit such that max y: < O, 1 (v)
VV c(1 exp(llv*())) VV n
sE|n]
||v||
Proof of Lemma C.4. Let be an arbitrarily unit vector such that max4e[n] yizz v O. Since v is k-sparse, without loss of generality, assume Vi 0, then
V. v*) |+
(Vocky Vorke
=1
V
2 1 - -|/ooll
It suffices to establish an upper bound on Vo..
Define set of indexes of the data that significantly incorrectly classified by Vosk-
I: = {i E [m] y.atT Vo.k S -0.44/ vox
Then for each E I, we must have
(8) ya v yiZual Vo:k + yiok Vi: S -0.4|| + yizi Visea
(2)
By Lemma C.3, have
n/8
Pr [I]
21 -1-6 8.
1 1 exp([Iv+[[])
According to (Hsu et al., 2021), we have
Pr all (yer (1) is support vector
21-8
25

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
assuming that C [Z) (n)) Under this event, the max-margin direction is given by V ko:o (Z 2k:00) (8) where Z1: (2 1:00 Jiez. It is clear that for every i E I, we have V
Yi- So we have
k:00
1
ZA: Z 1100 1l2
Zo Z Ziso ll2
max min yeu ||||=| BEZ
|
Vy (Z Z 2,00 y
12
n
By Hoeffding's inequality, have
Pr (Z 2h:00 3 2dInn) 2 1 1-xepp( -C(d n)) 21-6 8.
Under this event, we have max/ minger yr y1
k:00
u
/2d/II. Then we get
0.4//vo:kl|
I min y:a k:00 Vk: S V |l Id/ SET
(4)
Since ||v|| 1, we must have
Vo S
V1 (22)
Under the joint of the three events, which happens with probability least 1 35, we have
v,
(Vok, Vork)
V
2 1 1 ||
2
V1 + 0.44Z)/((2)
CV
d
n d
2 C
1 exp( [v
Here C >> 1 is large constant and may vary line by line. We complete the proof by rescaling d.
Proof of Theorem 4.2. Define
v 11/2 w, v'= 1'/2", == 1-12 d: rank(2n2 E).
Then <w== =T=vvvv and x T wn z Tv. Without loss of generality, let ||v| 1. Let be the angle between v and v*. We
apply Lemma C.4 to get
(V,
1 - cos =1
|
MI(() ln(1/5)
We complete the proof by calling Lemma C.I.
D. Early Stopping and lg-Regulaiization
D.1. Proof of Theorem 5.1
Proof of Theorem 5.1. We apply the fz-regularized ERM uy with = 1/(nt) as a comparator in Lemma 3.3. Recall that by the first-order stationary point condition, we have
V((()) = Yuy u
17l
26

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Then have
2 w. uzl1² 1 |lu.l1l S (1((u)u)= E(w:))
S <n((V[(ue) ur w.)
-u, u, WW1),
where the two inequalities are by Lemma 3.3 and convexity, respectively. The above is equivalent to
1
2 w.
uxll wny w.)
l|w uxl? 2
/w,1
(3)
2
To get the angle bound, we reformulate (3) as
1 2(u,, we) 2 [/well l/uel12.
Then we get
l w. 112 + |uu||
cos( We. uz) = (u, we)
2
| w.al
Well
/22
where we use (a + b)/2 2 vab for a, b 2 0 in the last inequality. To get the norm bounds, use triangle inequalities with (3) to get
[well
[u ||
Well |wo uxll
|uxl
[we]
which implies
V2 V2 +
v2
|xx|| S |woll 5
||u
/2
We complete the proof.
D.2. Proof of Theorem 5.2
Recall that the dataset (x;, vs) is linearly separable. Define the margin and the maximum Ey-margin direction
max min y;x; [|]]]=1 iE|n]
0, arg max min y:x, w. [w||=b>e(ul
Both GD and fz-regularization paths rational invariant. Without loss of generality, (e.) denotes the canonical basis (Wu al., 2023). That is to say, will use the first coordinate of vector refer its projection along the w direction. Under this convention, we use (w,, wi)ezo and (u,, ū,)=20 to denote the optimization and regularization paths, respectively. We denote the data by
can assume w e1, where
(r;, x:),
yi 27
X; E E
Let the set of support vectors be
S = fi E [n] xix w = 7 By (Wu al., 2023), the dataset (X,, y/ kes is strictly non-separable under Assumption 2. In particular, by Definition 2 in (Wu et al., 2023), there exists h > 0 such that
for every E Rd-1 there exists i E S such that y:x, = bbl
(4)
Define
G(w)
Σ
w).
iES
Then G(.) is convex and G(w) 2 1. By (4), the level set of G(w) is compact and w == arg min G(w) finite.
The following lemma for the limiting GD path is from (Wu et al., 2023).
27

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Lemma D.I. Let W, (w,, We) 2 0 be the GD path with any fixed stepsize vj > O. Then under Assumption we have Wa is increasing and
lim Wt 00,
lim Wr
The following lemma characterizes the limiting ez-reuularization path.
Lemma D.2. Let Uy (ux, a2) for be the Ez-regularization path. Then under Assumption we have
lim uy 00; 2
lim u, W
2
Proof of Lemma D.2. By the first order condition, we have
d
Di
Auy
L(ux)=
du
1 exp(y1 + yix; ú,)'
i=1
y/
λūy
L(ux)
dü
+ exp (x + Ux ūx)*
We first show that UA - cc. Recall that yeu. 2 7.
Then we have
1
y; + exp(yaTTUA yxx, ūs)
Aua
n
2
1 exp (xppu) y1 ū,)
exp( -iu - -2187 (n)
2n
2
Σ
exp( y:uuux - yxx Tun)
2n
iES
7
exp( -Tux G(ūx))
2n
z exp( -
7
2n
where the last inequality is because G(-)) 2 1. The above bound implies that 4y + 00 as A + 0.
We next show that ú, bounded. Define
: (i E [m] 8 a < <0}, P: fi 88R a사 2 0}.
Then N' is nonempty by (4), Moreover, there exists 1' E E S such that y uU < bb||ū|| by (4). Note that yi+ 25- by the definition of S. Then by definition, we have
n
\||a|
+ exp U. + 8:X ūA)
y
y u exp(pxxpuuupppooo + vi is)
71 VEN
+
y ū2))
n
iEP
y 1
Σ iep
vi Eexp( cexp(-yaaAA yar.MA 92 us)
exp(y)
VEN
<
1
Xx i
Σ
exp(-y;I,u)
n 1
exp(
Zz. uz)
n iEP
28

---

Benefits of Early Stopping in Gradient Descent for Overperameterized Logistic Regression
1 b + exp(-rux), n 1 + exp()ux)
where the second inequality is by e't S 1. The above inequality implies
bl uuul S (1 + exp(rux)) exp(->ux) S 2n,
where the last inequality is because 0. This shows that ü, is bounded.
Now we prove an upper bound on ux. Since ū, is bounded, we know Σi=
ū2)) bounded by a constant
Fraxx Let X = max; ||x||- Then we have
n n 1 + explyxauux + y: ux)
y1
Auy
X
N
1 exp(ytt + y: ux)
expl y,t;Uy 118, ax)
i=1
X n
exp( -PUA - y1 {
M i=1
X F max
exp( (??u))
n
which implies that
X Fmax
Aexp(rux)
(5)
nuu
Finally, we show ūx w" Recall the definition of u, Let us take À - 0 and use (5), the boundedness of ü, and that
y, > y for & S, yaz; = for S
then we get
0 lim λüy exp(yux) X-0
y exp((rux)
lim
X n
u + y18, ūt))
y; exp(71x)
lim
X-0 71
exp(?ιι + y1st ūx))
Y exp(?u>)
lim
X-0 n
exp(Tux + & ūn})
lim X-0 n
exp ū2)
Thus un satisfies the first-order stationary condition of G(.). So must have ún w*. This completes our proof.
Proof of Theorem 5.2. The proof is direct consequence of the above lemmas.
Note that is continous, u.o = 0, and limx-1 UA = oc. Moreover wo = O, w, is increasing, and we - cc. Thus for each t we can choose A(t) such that un = we and X(t) - 0. Then we have
[xx well ax(e) well (x(e)
will + lw w'll + 0.
This completes the proof.
29

---

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
D.3. Proof of Theorem 5.3
Proof of Theorem 5.3. As the dataset is linearly separable and we only care about the asymptotic, without loss of generality, consider the exponential loss instead of the logistic loss. In what follows, focus analyzing gradient flow. Our argument applies to gradient descent with any fixed stepsize 77 0.
Denote w = (w()), w(2)). Then the empirical risk can be written as
E(w(t), (2) ) exp(->w(()) + exp(-ru(1) )2w(2)))
Note that the GF and fg-regularization paths under the C are the same as those under in E up rescaling of the time and regularization strength. It suffices to compared the GF and ee-eeuulaiization paths under In L, where
In ((w (0 --w In (1 + exp((72w(2))) l2(.).
The GF path is given by
exp( 12 (2))
dwp ( = ydt,
dw(²) 72 + exp( - (2)
dl,
(o wh
Solving the ODEs, we get
In(1 + +720)
wi (1)
-t,
wi
(2)
t 12 0, S C,
72
for some constant C <>0 0. The regglaaariniiinn path is given by
exp( (pp(222((1)
-7 + Au =0, -72 + exp (2))
+ Au (2)
Then we get
4 X
11)
2 0
In( /A) In In())/A)
(2) 2x
SC, X S 2
722
As and - the two paths tend to infinity in both directions. However, due to the rate mismatch, it impossible to match with uX in both directions at the same time. So their dadistaacc has to be infinite asymptotically.
30


Reviews:
[{"review_id": "NAOxKg85Ha", "reviewer": "Reviewer_ViYA", "summary": "The authors examined high-dimensional logistic regression scenarios where p could be finite or infinite. They analyzed the gradient flow dynamics of logistic regression, discussed the generalization capabilities of early stopping estimators and interpolators, and provided comparisons between the gradient descent (GD) path and the L2 penalty path. This topic is particularly interesting for its theoretical insights into optimization and generalization in high-dimensional settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your support! We address your concerns as follows. \n\n---\n\n**Q1.** “Though the settings are different, I am not sure if the authors ignored the line of work on logistic regression by E. Candes et al.”\n\n**A1.**  We will cite and discuss these works you pointed out in the revision. They focused on the existence of MLE and its behavior if it exists, which is quite apart from our focus where MLE never exists (see paragraph “Noise and overparameterization.” in Section 2 and Proposition 2.2).\n\n---\n\n**Q2.** “...it would be better if the author could provide a more concrete comparison between their work and those from linear regression using square loss. This would help readers better understand the key differences between square loss and logistic loss.”\n\n**A2.** Risk bounds for logistic regression and linear regression are not directly comparable, as these two problems are different in nature: they have different data assumptions and different risk measurements. \n\nIn Lines 244-257 of the right column, we provide a high level comparison on the techniques for analyzing GD in logistic regression and linear regression. One immediate issue is that we cannot directly use tools from linear regression, which relies on the chains of equalities that needs the Hessian to be constant. \n\nWe will make these discussions more detailed in the revision to better clarify the key difference between squared loss and logistic loss.", "claims_and_evidence": "I have not checked the proofs carefully, but most of the claims sound reasonable for me.", "methods_and_evaluation_criteria": "This is a theoretical paper and no method was proposed.", "theoretical_claims": "I have not checked the proofs carefully. Most of the claims sound reasonable for me.", "experimental_designs_or_analyses": "No experiments have been reported.", "relation_to_broader_scientific_literature": "Most of the current work focuses on regression under square loss. In contrast, regarding logistic regression, most research focuses on empirical minimal loss rather than analyzing gradient descent with early stopping. This work would be of interest to other theoretical groups.", "essential_references_not_discussed": "Though the settings are different, I am not sure if the authors ignored the line of work on logistic regression by E. Candes et al. For example: modern maximum-likelihood theory for high-dimensional logistic regression.", "other_strengths_and_weaknesses": "The results sound reasonable to me. However, it would be better if the author could provide a more concrete comparison between their work and those from linear regression using square loss. This would help readers better understand the key differences between square loss and logistic loss.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please see the \"Other Strengths And Weaknesses\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "HMwV744Goh", "reviewer": "Reviewer_Vcgf", "summary": "This paper theoretically examines the additional regularization bias introduced by early stopping in logistic regression. The authors first demonstrate that for any well-specified logistic regression problem, gradient descent (GD) with oracle-based early stopping is well-calibrated and statistically consistent. They then establish lower bounds on test risk, calibration error, and zero-one error for asymptotic GD, showing that it is inconsistent and has worse sample complexity compared to early-stopped GD. Additionally, they derive bounds on the angular differences between the regularization path and the GD path for any convex and smooth objective. Finally, they analyze asymptotic bounds for logistic regression with linearly separable data, showing that under a sufficient condition on the data, both paths converge.\n\n**Update after rebuttal**\n\nI thank the authors for engaging during the rebuttal period. They addressed most of my key questions and agreed to make appropriate additions to the paper. Overall, I believe that it is a good paper, and improves our understanding of early-stopped gradient descent, and I maintain my positive rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed comments. We address your questions below.\n\n---\n**Q1.** “...Lines 266-273, discuss application of these bounds to a trivial, under-parameterized case. How do these bounds perform in the overparameterized case?... For a meaningful comparison with the negative results in Section 4 on asymptotic GD, it would be useful to determine when Thm 3.1 and Thm 3.2 provide non-vacuous bounds and how common these settings are.”\n\n**A1.** In Lines 205-214 of the right column and Lines 272-274, we discuss our bounds in an overparameterized setting satisfying the standard source and capacity conditions, where our bounds are non-vacuous.\n\nOur comparison holds in general and common settings. In what follows, we explain this using Theorems 3.1 and 4.1 as examples. For every well-specified logistic regression problem (see Assumption 1), Theorem 3.1 yields a vanishing excess risk for early stopped GD as discussed in Lines 190-203 right. For the same set of problems, Theorem 4.1 implies GD without early stopping is inconsistent for logistic loss and poorly calibrated, as discussed in Lines 279-283 of the right column. Note that this comparison is agnostic to dimension and holds in the overparameterized regime as well. \n\n---\n**Q2.** “For Thm 4.2, what role does the $k$-sparsity condition play? Is this the key condition needed to prove inconsistency? Please provide some intuition based on the proof. … can you provide an example (or a class of examples based on data covariance) where Thm 3.1 and Thm 3.2 yield non-vacuous bounds while the negative results in Thm 4.2 still hold?”\n\n**A2.** The $k$-sparsity is a sufficient condition to establish the sample complexity lower bound in Theorem 4.2. Note that Theorem 4.2 provides a lower bound on the excess zero-one error, but this does not imply inconsistency. For the inconsistency results in Theorem 4.1, we do not need the $k$-sparsity condition. \n\nThe intuition behind Theorem 4.2 is that there are $k$ informative dimensions and a lot more uninformative dimensions. Since $n\\gg k$, the training set cannot be separated purely using the $k$ informative dimensions. Thus, interpolators must use the uninformative dimensions to separate the data, leading to the risk lower bound. This explains the role of the $k$-sparsity in Theorem 4.2.  \n\nWe discuss in Lines 313-319 for situations where Theorems 3.1 and 3.2 yield non-vacuous bounds while the negative results in Thm 4.2 still hold. Moreover, the example discussed in Lines 205-214 of the right column and Lines 272-274 also suffices. We will make this clear in the revision. \n\n---\n**Q3.** “Regarding conjectures at the end of page 6 and page 8 (left column end)—what justifies these claims? For the first, do you have any empirical results supporting it? For the second, Thm 5.2 and Thm 5.3 merely represent convergence under a sufficient condition and a counter example, the conjecture seems strong—do you have additional reasoning to support it?”\n\n**A3.** We discuss evidence/intuitions for the two conjectures as follows. \n\nFor the first one, note that in Figure 1(b), the test zero-one error keeps increasing even after reaching interpolation (training zero-one error becomes zero). This suggests that the zero-one error of the maximum $\\\\ell\\_2$-margin interpolator (this is when $t\\to\\\\infty$) should be higher than an oblivious interpolator. Our conjecture is partly motivated by this observation.  \n\nThe reasoning behind the second conjecture is as follows. Note that Assumption 2 implies that the dataset projected perpendicular to the max-margin directions (called “projected dataset”) is strictly nonseparable (see Lemma 3.1 in Wu et al., 2023). This is the only property used in Theorem 5.2. Moreover, in Theorem 5.3, the “projected dataset” is nonseparable but with margin zero – we conjecture this property is sufficient for Theorem 5.3 to hold. Now for a generic separable dataset, we check the “projected dataset”: \n- if it is strictly non-separable, Theorem 5.2 holds; \n- if it is non-separable but with margin zero, we conjecture Theorem 5.3 holds; \n- otherwise it is separable (with positive margin), we decompose the dataset recursively. \nThis is the reasoning behind our conjecture.  \n\nWe will add these discussions in the revision.", "claims_and_evidence": "The claim on calibration via early stopping is well supported by Theorems 3.1 and 3.2. The negative results on poor calibration and the inconsistency of asymptotic GD are also established in Theorems 4.1 and 4.2, along with the need for exponential sample complexity for achieving zero-one error. However, I have some concerns regarding the comparison between Theorems 3.1 (3.2) and Theorems 4.1 and 4.2—see the questions section. Finally, Theorems 5.1 and 5.2 establish the global and asymptotic connection between GD and the regularization path.", "methods_and_evaluation_criteria": "It’s mainly a theory paper. I don’t think this question is very valid, but the toy experiment in Figure 1 matches the theoretical claims in the paper.", "theoretical_claims": "No, I did not read the proofs of the theorems.", "experimental_designs_or_analyses": "N/A, Look at the response to Methods and Evaluation Criteria.", "relation_to_broader_scientific_literature": "The paper builds on the well-established theory of implicit regularization in GD for logistic regression by theoretically demonstrating the additional benefits of early stopping. While the generalization benefits of early-stopped GD have been studied in much greater detail for linear regression (for example, vanishing excess risk with early stopped GD despite no benign overfitting with $\\ell_2$ norm interpolator (see references on column 1, page 2)), they are less well understood for logistic regression. This work addresses an important gap in the literature by showing that early stopped GD can achieve good generalization (vanishing excess risk), despite a statistically inconsistent interpolator, similar to results in linear regression.", "essential_references_not_discussed": "Looks good and thorough to me.", "other_strengths_and_weaknesses": "The paper studies a very important (and understudied) problem from a theoretical point of view. It is well-written in general, easy to read and follow.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Thm 3.1 and 3.2 provide early stopping risk bounds for any (including overparameterized) well-specified logistic regression problem. Lines 266-273, discuss application of these bounds to a trivial, under-parameterized case. How do these bounds perform in the overparameterized case? $\\Sigma$ needs to be carefully chosen to control the tail of EVs and the trace. For a meaningful comparison with the negative results in Section 4 on asymptotic GD, it would be useful to determine when Thm 3.1 and Thm 3.2 provide non-vacuous bounds and how common these settings are.\n\n\n2. For Thm 4.2, what role does the $k$-sparsity condition play? Is this the key condition needed to prove inconsistency? Please provide some intuition based on the proof. Additionally, linking it to the previous question, can you provide an example (or a class of examples based on data covariance) where Thm 3.1 and Thm 3.2 yield non-vacuous bounds while the negative results in Thm 4.2 still hold?\n\n\n\n3. Regarding conjectures at the end of page 6 and page 8 (left column end)—what justifies these claims? For the first, do you have any empirical results supporting it? For the second, Thm 5.2 and Thm 5.3 merely represent convergence under a sufficient condition and a counter example, the conjecture seems strong—do you have additional reasoning to support it?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hI43xvgv0X", "reviewer": "Reviewer_MdqZ", "summary": "This paper studies the problem of early stopping in logistic regression. It considers two metrics: the zero classification accuracy and the logistic loss. The paper shows that the excess zero one loss is bounded by the excess logistic loss. Building on this the paper shows that there exists an early stopped model that has zero excess logistic loss (asymptotically). Hence the model is well calibrated and consistent as well. On the other hand the paper also shows the existence of a setup where the converged solution has infinite excess logistic loss and that the excess zero one loss is at least a constant.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We address your concerns as follows.\n\n---\n**Q1.** “My current score is primarily due to the exists of $t$ such that $\\\\hat L(w\\_t) \\\\le \\\\hat L(w\\_\\{0:k\\}\\^\\*)$. I believe that the existence of such a $t$ needs to be proven to complete the story.”\n\n**A1.** The existence of a $t$ such that $\\\\hat L(w\\_t) \\\\le \\\\hat L(w\\_\\{0:k\\}\\^\\*)$ is guaranteed because \n* GD converges to a minimizer of the empirical risk $\\\\hat L(\\\\cdot)$; \n* and $\\\\min \\\\hat L(\\\\cdot)  < \\\\hat L(w\\_\\{0:k\\}\\^\\*)$.\n\nSo there exists a $t$ such that $\\\\hat L(w\\_t) \\\\le \\\\hat L(w\\_\\{0:k\\}\\^\\*)$. \nThe second bullet is clear. We explain the first bullet as follows. \n\nNote that $\\\\hat L(\\\\cdot)$ is smooth and convex. Classical optimization theory guarantees the global convergence of GD in this case. Specific to logistic regression, this is proved in, for example, Theorem 1.1 in [Ji & Telgarsky 2018], with a precise convergence rate. We also see this by applying Lemma 3.3 with suitable $u$ and large enough $t$.\n\nThis explanation should address your concerns. But let us know if you have further questions regarding this. We will add these discussions in the revision.\n\n---\n**Q2.** “I think the paper [A] is an important recent paper that is quite relevant to many of the ideas discussed in the paper (early stopping, implicit regularisation, connection to explicit regularization) is missing”\n\n**A2.** Thanks for pointing out the missing reference. We will cite and discuss it in the revision.\n\n---\n**Q3.** “I think the theorem statements could be sharper. Words like - thus should not appear in a theorem statement.”\n\n**A3.** We will polish our theorem statements according to your suggestions. Thanks. \n\n---\n**Q4.** “All of the current analyses are for the case when we initialize at zero. What if we initialized somewhere else, or did it have a random initialization?”\n\n**A4.** When the initialization $w\\_0$ is nonzero, in the bounds, $w\\^\\*$ should be replaced by $w\\^\\* - w\\_0$. This can be seen from the proof of the theorems. We will clarify this in the revision. \n\n---\n**Q5.** “just to confirm the probabilities in Theorems 3.1 and 3.2 agree with respect to the sampling of the data?”\n\n**A5.** Yes.", "claims_and_evidence": "The paper is a theory paper and presents a variety of theoretical statements that support their claims. However, I have some questions about some of the statements and their proofs. \n\nQuoting from the paper, it says that \"The empirical risk $\\hat{\\mathcal{L}}(w_t) decreases monotonically for $t \\ge 0$. Thus there exists a stopping time $t$ such that $\\hat{\\mathcal{L}}(w_t) \\le  \\hat{\\mathcal{L}} (w^∗_{0:k} \\le \\hat{\\mathcal{L}}(w_{t-1})$.\"\n\nHowever, being monotonically decreasing does not mean that $\\hat{\\mathcal{L}}(w_t)$ is eventually smaller than $\\hat{\\mathcal{L}} (w^∗_{0:k}$. I tried checking the proof, but I could not find the part of the proof where the assertion that there exists a $t$ such that $\\hat{\\mathcal{L}}(w_t) \\le  \\hat{\\mathcal{L}} (w^∗_{0:k} $ is proven. \n\nTheorem 3.2 then assume the existence of such a time $t$. But the description in the paper seems to assume that such a time $t$ must exist. \n\n\n--------\n\nMy current score is primarily due to the exists of $t$ such that $\\hat{\\mathcal{L}}(w_t) \\le  \\hat{\\mathcal{L}} (w^∗_{0:k} $. I believe that the exietnce of such a $t$ needs to be proven to complete the story. Otherwise the current story is if there is a good early stopping point it is good to stop because the cobverged solution can be bad versus early stopping is good.", "methods_and_evaluation_criteria": "There are no experiments.", "theoretical_claims": "There are a variety of theoretical claims. I did not check any of the proofs except for reading the lemma statements in Section C.1 and then the proof of Theorem 3.1 given the lemmas. \n\nHowever, I think there is an issue with the proof. Please see my comments in the claims and evidence section.", "experimental_designs_or_analyses": "No Experiments.", "relation_to_broader_scientific_literature": "The relationship to the broader scientific literature is well established, and understanding the simplicit bias of gradient descent and early stopping in different scenarios is an important problem. \n\nEarlying stopping and GD have been mostly studied for linear regression. The case for logistic regression is less well understood. Hence the duality of Theorems 3.1 and 4.1 is quite interesting in the loogistic regression setting.", "essential_references_not_discussed": "I think the paper [A] is an important recent paper that is quite relevant to many of the ideas discussed in the paper (early stopping, implicit regularisation, connection to explicit regularization) is missing \n\n[A] Sonthalia, Rishi, Jackie Lok, and Elizaveta Rebrova. \"On regularization via early stopping for least squares regression.\" arXiv preprint arXiv:2406.04425 (2024).", "other_strengths_and_weaknesses": "**Strengths**\n\nThe prose in between theorem statements is very well written. In fact, it is amongst the best I have ever seen.\n\nThe duality of Theorem 3.1 and 4.1 is quite surprising. In particular, in light of Theorem 4.2. One would imagine that things break down in the limit due to the norm going to infinity. However, Theorem 4.2 says that is not the case. \n\nThe conenction to ridge regularized version is also interesting. \n\n**Weakness**\n\nI think the theorem statements could be sharper. Words like - thus should not appear in a theorem statement.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "All of the current analyses are for the case when we initialize at zero. What if we initialized somewhere else, or did it have a random initialization? \n\njust to confirm the probabilities in Theorems 3.1 and 3.2 aree with respect to the sampling of the data?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Slnq2lPvd6", "reviewer": "Reviewer_KGpn", "summary": "The paper studies the impact of early stopping in gradient descent (GD) for overparameterized logistic regression. It demonstrates that, in this setting, early-stopped GD is well-calibrated and achieves lower risk and zero-one risk compared to GD at convergence. Additionally, the paper establishes a connection between the implicit regularization of GD and explicit regularization.\n\n# Update after rebuttal\n\nThe authors have addressed my concerns. I keep my positive score", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address your questions below. \n\n---\n**Q1.** “The technique used to derive the logistic risk upper bounds relies heavily on the prior work of Telgarsky (2022).”\n\n**A1.** While our Lemma 3.3 appears in [Telgarsky 2022] (and other prior works as mentioned), it seems unfair to call it a “weakness”, as new research builds upon existing results. We would also like to point out that our logistic risk upper bounds require careful statistical control around the population optimum since we work in an overparameterized regime, which is beyond [Telgarsky 2022]. Besides, we show how early stopped GD separates from asymptotic GD and how it explicitly connects to $\\ell_2$-regularization. None of these results appears in [Telgarsky 2022].\n\n---\n**Q2.** “...It would be beneficial to present results that explicitly depend on the stopping time or provide an example of a stopping time for which the bounds hold.”\n\n**A2.** One can compute an upper bound on the stopping time using standard optimization and concentration tools. Specifically, $\\\\hat L$ is smooth and convex, so GD converges in $O(1/t)$ rate. Moreover, we can compute $\\\\hat L(w\\^*\\_{0:k})$ using concentration bounds. In this way we can compute a stopping time upper bound. \n\nOnce we obtain the upper bound on the stopping time, we can state the theorem as “there exists a $t$ no larger than XX, such that…”. This gives examples of stopping time for our bounds to hold. We will comment on this in the revision. However, we prefer to maintain our original theorem statement as it is cleaner. \n\n---\n**Q3.** “In cases where the results are comparable to prior work, the bounds obtained in this paper are sometimes weaker.”\n\n**A3.** As discussed in Lines 397-425, no prior results strictly dominates our results; the work that obtained sharper rates also needs stronger assumptions than ours. While there is still room to improve our upper bounds (as discussed in the end of Section 3.2), we believe our contribution is already very significant by establishing the benefits of early stopping in logistic regression. \n\n---\n**Q4.** “Are there scenarios where the optimal stopping time is impractically large, such as exponential in $d$ or $n$? If so, what happens to the risk of GD when it is stopped after $\\mathsf{poly}(d,n)$ iterations? Does it still benefit from early stopping in such cases?”\n\n**A4.** Note that our results allow $d=\\infty$, but the optimal stopping time is always finite as hinted by our negative results for asymptotic GD. Therefore, the stopping time is generally small compared to $d=\\infty$, and it is meaningless to discuss “exponential or polynomial in $d$”, which is infinite.\n\nMoreover, as discussed in **A2**, the stopping time is at most polynomial in $n$ by optimization and concentration arguments. Note that the hidden constant factors might be instance-dependent. Again, there is no exponential dependence.", "claims_and_evidence": "Yes, the authors prove all of their results.", "methods_and_evaluation_criteria": "N.A", "theoretical_claims": "No. I focused on reading the main text.", "experimental_designs_or_analyses": "N.A", "relation_to_broader_scientific_literature": "Most of the paper's main contributions are not directly comparable to previous work. The most relevant studies primarily focus on asymptotic GD, the setting of separable data, or scenarios where the loss function is the squared loss.", "essential_references_not_discussed": "The paper discusses all of the essential references.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and clearly structured.\n\n2. It thoroughly discusses related work and provides detailed comparisons with its own results.\n\n3. The findings on well-calibration and improved generalization with respect to 0-1 risk, compared to interpolating GD, are both interesting and somewhat surprising.\n\n4. The paper extensively discusses the limitations of its results.\n\nWeaknesses:\n\n1.The technique used to derive the logistic risk upper bounds relies heavily on the prior work of Telgarsky (2022).\n\n2.The results are based on an optimal stopping time. In particular, the authors acknowledge that \"early-stopped GD in Theorem 3.1 is not a practical algorithm\". It would be beneficial to present results that explicitly depend on the stopping time or provide an example of a stopping time for which the bounds hold.\n\n3. In cases where the results are comparable to prior work, the bounds obtained in this paper are sometimes weaker.", "other_comments_or_suggestions": "N.A", "questions_for_authors": "Are there scenarios where the optimal stopping time is impractically large, such as exponential in $ d $ or $ n $? If so, what happens to the risk of GD when it is stopped after $\\text{poly}(d,n)$ iterations? Does it still benefit from early stopping in such cases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cfSNotK1ZD", "reviewer": "Reviewer_Ryys", "summary": "This paper investigate the importance of early stopping in well-specified high-dimensional logistic regression. They demonstrate that the early stopping ensures generalization in terms of excess logistic risk, while interpolator diverges. These results emphasize the need of early stopping in overparameterized models.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our paper. We answer your questions as follows.\n\n---\n**Q1.** “The early-stopping time is oracle-based and lacks explicit bounds, which will limit the practical utility of the results.”\n\n**A1.** Our aim is to understand the benefits of early stopping. We believe designing a practical criterion for early stopping, despite being an important question, is beyond the scope of this paper. \n\n\n---\n**Q2.** “What are the insights of selecting $k$ in the main theorems? How the \"variance\" and the \"bias\" are connected to $k$?”\n\n**A2.** Intuitively, $k$ determines the number of dimensions in which early stopped GD is able to learn the true parameter $w\\^\\*$. Moreover, early stopped GD ignores the remaining dimensions and pays an “approximation” error. We choose $k$ to minimize the upper bounds.\n\nIn Theorem 3.1, the stopping time is relatively small, at which point GD first hits an empirical risk of $\\\\hat L(w\\_{0:k}\\^\\*)$. Thus, the total parameter movement is relatively small, and the bias error tends to be large. In Theorem 3.2, the stopping time is relatively large, at which point GD hits an empirical risk of $\\\\hat L(w\\^*)$. Thus, the total parameter movement is large, and the variance error tends to be large. \n\nWe will clarify these in the revision.\n\n---\n**Q3.** “Can the results in this paper be extended to generalized linear models or M-estimators?”\n\n**A3.** We believe that part of our results can be extended beyond logistic regression. For example, the proof of Theorem 3.1 can be adapted to other loss functions that are convex, smooth, and Lipschitz. We will comment on this as a future direction.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The proofs seem to be solid, but I have not checked all the details.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "This paper considers early-stopped gradient descent in logistic regression, while most of the previous works focus on linear regression.\nThe results in this paper extend the previous results to the setting of logistic regression, which is novel.\nThese results contribute to understandings of early stopping in over-parameterized statistical problems.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "###  Strengths\n\nThe paper is well-written and easy to follow.\nThe techinical results are comprehensive that both upper bounds for early-stopped GD and lower bounds for interpolators are given, which are persuasive.\nMoreover, the connection between early stopping and explicit $l^2$ regularization is discussed.\n\n### Weakness\n\nThe early-stopping time is oracle-based and lacks explicit bounds, which will limit the practical utility of the results.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. What are the insights of selecting $k$ in the main theorems? How the \"variance\" and the \"bias\" are connected to $k$?\n\n2. Can the results in this paper be extended to generalized linear models or M-estimators?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This article studies the effect of early stopped gradient descent (GD) on overparametrized logistic regression models, constituting a significant extension to previous works mostly focused on linear regression. Under anisotropic Gaussian feature vectors with bounded covariance trace, and class labels generated from a logistic model with constant misclassification rate, the statistical advantages of early stopped GD are demonstrated in terms of estimation error (measured by logistic loss and calibration error) and classification error. Two upper bounds are established for early stopped GD,  describing first a bias-dominating phase, followed by a variance dominating regime, where a sharp bound is obtained under the stronger condition of bounded parameter vector in norm, These upper bounds implies a polynomial sample complexity for early stopped GD, whereas the derived lower bound for interpolating estimators indicates that asymptotic GD requires at least a exponential number of training samples.

The significance and the novelty of this analysis were appreciated by the reviewers, in addition to other positive points including the clearly structured manuscript, the well-interpreted theoretical results, and the informative discussion of the limitations. The authors adequately answered the reviewers’ questions during rebuttal, resulting in an unanimous recognition of this contribution.
Decision: Accept (poster)