Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
Authors: Jingfeng Wu
Pierre Marion
Peter Bartlett
Venue: NeurIPS 2025 poster ()
Keywords: GD
large stepsize
logistic regression
EoS
regularization
acceleration
Primary area: optimization

Abstract: We study *gradient descent* (GD) with a constant stepsize for $\ell_2$-regularized logistic regression with linearly separable data. Classical theory suggests small stepsizes to ensure monotonic reduction of the optimization objective, achieving exponential convergence in $\widetilde{\mathcal{O}}(\kappa)$ steps with $\kappa$ being the condition number. Surprisingly, we show that this can be *accelerated* to $\widetilde{\mathcal{O}}(\sqrt{\kappa})$ by simply using a large stepsize---for which the objective evolves *nonmonotonically*. The acceleration brought by large stepsizes extends to minimizing the population risk for separable distributions, improving on the best-known upper bounds on the number of steps to reach a near-optimum. Finally, we characterize the largest stepsize for the local convergence of GD, which also determines the global convergence in special scenarios. Our results extend the analysis of Wu et al. (2024) from convex settings with minimizers at infinity to strongly convex cases with finite minimizers.

Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
Jingfeng Wu' UC Berkeley wuujf@berkeley.cm edu
Pierre Marion Inria, DI ENS, PSL University pierre.marione www.mmmiinii..............
Peter L. Bartlett UC Berkeley & Google DeepMind peterbberkeley edu
Abstract
We study gradient descent (GD) with constant stepsize for ég-regularized logistic regression with linearly separable data. Classical theory suggests small stepsizes to ensure monotonic reduction of the optimization objective, achieving exponential convergence (xx) steps with being the condition number. Surprisingly, we show that this can be accelerated to ((vk) by simply using a large stepsize-for which the objective evolves nonmonotonically. The acceleration brought by large stepsizes extends to minimizing the population risk for separable distributions, improving on the best-known upper bounds on the number steps to reach near- optimum. Finally, we characterize the largest stepsize for the local convergence of GD, which also determines the global convergence in special scenarios. Our results extend the analysis of Wu et al. (2024) from convex settings with minimizers at infinity to strongly convex cases with finite minimizers.
Introduction
Machine learning often involves minimizing regularized empirical risk (see, e.g., Shalev-Shwartz and Ben-David, 2014). An iconic case is logistic regression with fz-regularization, given by
Σ(w) = ((w) + 2 I|wl?, where L(w) = Σ In + exp(- yix, w)).
(1)
2=1
Here, >>0 0 is the regularization hyperparameter, w E H is the trainable parameter, and (x;, y:) E H x (+1} for 1,...,7 n optimization algorithm, gradient descent (GD), defined as
the training data, where HiI is Hilbert space. We consider generic
W
vi(.). 220, Wo H.
(GD)
where > 0 is a constant stepsize and Wo is an initialization, c.g., Wo = 0.
This problem is smooth and strongly convex. Classical optimization theory suggests small stepsize, for which GD decreases the objective Z(w:) monotonically (Nesterov, 2018, Section 1.2.3), which we refer to as the stable regime. In this regime, GD achieves an error in Oxx In (1(1))) steps, where
1 is the condition number of the Hessian of Ć (the smoothness parameter divided by the strong convexity parameter). This step complexity is known to suboptimal and can be improved to O Im(/E)) when GD is modified by Nesterov's momentum (Nesterov, 2018, Section 2.2).
recent line of work shows that GD converges even with large stepsizes that lead oscillation (Wu et al., 2024, other related works will be discussed later in Section 1.1). This is known as the edge of
"Equal contribution. t Work done while P.M. postdoc EPFL, visiting the Simons Institute UC Berkeley.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(1)
θ
θ X1/2
Ami(1AA)
-
A/3
71
CV (deecent lamma)
faster CV (Thm.
faster CV for small À (Thm. 1)
CV locally global behavior unknown
DV under support vector condition (Thm. 7) unknown otherwise
DV
unknown for generic
Figure 1: The effect of the stepsize (1) for GD in logistic regression with & æz-regularization (A). Here, "CV" stands for convergence and "DV" stands for divergence.
stability (EoS) (Cohen et al., 2020) regime, Specifically, Wu et al. (2024) considered (unregularized) logistic regression ((1) with X = 0) with linearly separable data. Their problem is smooth and convex, but not strongly convex. They showed that GD achieves (11VE)) step complexity when operating the EoS regime, which improves the classical (11/e) step complexity when operating the stable regime. However, it is unclear whether large stepsizes would benefit GD in strongly convex problems such as fz-regularized logistic regression, for two reasons. First, with linearly separable data, the minimizer of logistic regression is at infinity. Exploiting this property, Wu et al. (2024) showed that GD converges with an arbitrarily large stepsize. However, this impossible for regularized logistic regression, which is strongly convex and admits unique, finite minimizer. In this case, GD is unstable around the minimizer when the stepsize exceeds a certain threshold (e.g., Hirsch et al., 2013, Section 8), which prevents convergence. Second, Wu et al. (2024) only obtained the accelerated (E) step complexity for E < 1/n, where is the sample size (see their Corollary 2). However, the statistical error (or generalization error) is often larger than 1/n. In these situations, targeting an optimization error of 1/nn seems less practical, as the statistical error already caps the final population error. It remains unclear whether large stepsizes save computation to minimize population error in the presence of statistical uncertainty.
Contributions. We show that large stepsizes accelerate GD for fz-regularized logistic regression with linearly separable data, with the following contributions (summarized in Figure 1).
1. For small regularization hyperparameter (A O(1/n)), show that GD can achieve an e error within (lI(1/ee/v\) steps. This uses an appropriately large stepsize for which GD operates in the EoS regime. Since the condition number of this problem is λ (1/A), GD matches the accelerated step complexity of Nesterov's 's momentum by simply using large stepsizes. We further provide a hard dataset showing that this does not always happen if GD operates in the stable regime.
2. For general À (independent of n). GD still benefits from large stepsizes, achieving an improved step complexity of O(In(1/e)/A299) Assuming a separable data distribution, GD minimizes the (best-known upper bound on) population risk to the statistical bottleneck in (n22/3) steps using large stepsizes and regularization. Without one of these, GD takes (()) steps to achieve the same. This improvement provides evidence that large stepsizes accelerate GD under statistical uncertainty.
3. Finally, under additional data assumptions, we derive a critical threshold (A(1/)))) on the convergent stepsizes for GD in the following sense. With stepsizes that smaller by constant factor, GD converges locally (and globally in 1 1-dimensional cases); with stepsizes that are larger by constant factor, GD diverges with almost every initialization Wg-
Terminology. Formally, we say that GD is in the stable phase at step t when L(w,) decreases monotonically from onwards, and in the EoS phase when it does not. Moreover, we say that a GD run is in the stable regime if GD is in the stable phase at the initial step, and in the EoS regime if it is the EoS phase the beginning but transitions to the stable phase afterward. To give intuition, note that, for a strongly convex and sufficiently differentiable objective, if GD converges, it must enter the stable phase in finite time for a generic initialization. This means that a typical convergent GD run either in the stable regime or the EoS regime.

---

[(me)
||0"[(m]|||
2-
27
28
0-21
2 -20
2
Figure 2: Illustration of large stepsizes accelerating GD. We constant stepsize GD for an (z-regularized logistic regression on a two-dimensional separable dataset. The dataset is given by Xi = (7, 1). X2 (7. 2). 91 1/2 1, where ? = 0.2. The regularization is = 2-12 GD is initialized at wo O. Left: Objective value as a function of training steps. Middle: Sharpness (the largest eigenvalue of the Hessian of the objective) as a function of training steps. Right: GD trajectory in the parameter space, where the black dot is the GD initialization and the black cross is the minimizer. Additional details and plots are given in Appendix E.
Simulations. Our results are illustrated in Figure 2 by running GD for 62-regularized logistic regression on toy two-dimensional separable dataset. Figure suggests that GD converges faster with larger stepsize by entering the FoS regime, in which the sharpness oscillates around 2/1 in the initial phase.
Notation. For two positive-valued functions/ and g, we write S g I 2 g if there exists c such that for every v, [(x & cg(x) or [xx) 2 cg(x), respectively. We write f ~ I S. We use the standard big-O notation, with O and ft to hide polylogarithmic factors within the O and Ω notation, respectively. For two vectors u and v in Hilbert space, we denote their inner product by (u, v) or, equivalently, [T v. We write ||u|| == u u.
1.1 Related work
Edge of stability. In practice, GD often induces an oscillation yet still converges the long run (see Wu et al., 2018; Cohen et al., 2020, and references therein). This is referred to by Cohen et al. (2020) as the edge of stability (EoS). Since gradient flow would never increase the objective, EoS essentially consequence of large stepsizes. Cohen et al. (2020) further pointed out that GD apparently needs to operate the EoS regime to obtain reasonable optimization and generalization performance in practical deep learning settings. Besides the empirical results, the theoretical mechanism of EoS has been investigated in several papers (see, c.g., Damian et al., 2022; Zhu et al., 2022; Arora et al., 2022, and references therein). In particular, Cohen et al. (2025) proposed a modified ODE called centrol flow to approximate the time-averaged GD trajectory in the EoS regime. Instead of focusing on explaining EoS itself, we study the optimization benefits of GD operating in the EoS regime.
Another line of research has focused on the statistical benefits of large stepsizes for neural networks (see, e.g., Mulayoff et al., 2021; Qiao et al., 2024: Wu et al., 2025b), exploiting the observation that GD with larger stepsize constrained to converge to flatter minima (Wu et al., 2018). However, those works assumed the convergence of GD with large stepsizes, which itself is challenging question. this regard, our work makes partial progress by showing the global convergence of GI) with large stepsizes for fz-regularized logistic regression.
Aggresive stepsize schedulers. A recent line of research discovered that a variant of GD with certain aggressive stepsize schedulers yields improved convergence for smooth and (strongly) convex optimization (see Altschuler and Parrilo, 2025; Grimmer, 2024; Zhang et al., 2024, and references therein). As a representative example, Altschuler and Parrilo (2025) showed that their GD variant with the silver stepsize scheduler attains an improved 0.7.77))) step complexity for smooth and strongly convex problems with condition number Similar our work, they obtained acceleration by using large stepsizes that operate outside the classical stable regime. However, there are several notable differences. First, our problem class, rereullar logistic regression, is smaller than theirs.
3

---

However, we obtain a better (Kx-55) step complexity. Moreover, we do so with the simpler approach of constant stepsize GD. Finally, from technical perspective, our analysis is anytime as our stepsize choice does not rely on the target enror (see Theorem I), while the algorithm of Altschuler and Parrilo (2025) needs to know the target error & in advance.
Logistic regression. Logistic regression with linearly separable data is standard class of problems in optimization and statistical learning theory. For GD with small stepsizes in the stable regime, Soudry et al. (2018) and Ji and Telgarsky (2018) 18) showed that GD diverges to infinity while converging in direction to the maximum 22-margin direction. This result was later extended GD with an arbitrarily large stepsize in the EoS regime (Wu et al., 2023). More recently, Wu et al. (2024) showed that GD with large stepsize attains an accelerated (11/ /E) step complexity for logistic regression with linearly separable data, demonstrating the benefits of EoS. For the same problem, Zhang et al. adaptive large-stepsize variant of
(2025) improved the step complexity to 1/7² by considering GD, where y is the margin of the dataset, and they further showed that this is minimax optimal. As discussed earlier, their results rely strongly the minimizer being at infinity. In comparison, focus on logistic regression with ég- fe-regularization, where the minimizer is finite.
For l reguullarieed logistic regression with linearly separable data, Rosset et al. (2004) showed that the regularized empirical risk minimizer converges direction to the maximum f--margin direction as the regularization tends to zero. Our work complements theirs by considering the step complexity of finding the fz-regularized empirical risk minimizer.
For logistic regression with strictly nonseparable data, Meng et al. (2024) constructed examples where GD with large stepsizes does not converge globally (even if the stepsize allows local convergence). Similar to our problem, theirs is also smooth, strictly convex, and admits a unique finite minimizer. However, Meng et (2024) focused on negative results, while we provide positive results with separable data for the global convergence of GD with large stepsizes. Proving positive results in the nonseparable case an interesting direction for future work.
2 Large stepsizes accelerate GD
We make the following standard assumptions (Novikoff, 1962) throughout the paper. Assumption 1 (Bounded and separable data). Assume the training data (x,, W:), satisfies
A. for every = 1,...,n, |xx|| < 1 and y E {+1};
n, B. there is margin 7 E (0, 1] and unit vector w" such that y.x. w" 2 " for every 1.....
Under Assumption 1, the objective function Z(-) defined in (1) is (1 + +) X)-smooth and X-strongly convex. The condition number of this problem is A = (1))), as the regularization hyperparameter À is typically small. For small stepsize 1/(1 + X) = @(1). GD operates in the stable regime, achieving a well-known (In(L/s)/A) step complexity (Nesterov, 2018). Quite surprisingly, we will show that this can be improved to (In(1/=)) /\) when the regularization hyperparameter is small (compared to the reciprocal of the sample size; see Section 2.1), and to (([((1=e)/2/3) for general Ả (Section 2.2). We obtain this acceleration by using large stepsizes, where GD operates in the EoS regime.
The minimizer, WA == arg min Z(-), is unique and finite when À > O.
2.1 Matching Nesterov's acceleration under small regularization
Our first theorem characterizes the convergence of GD in the EoS regime when the regularization is small. The proof is deferred Appendix A.2.
Theorem 1 (Convergence under small regularization). Consider (GD) for lz-reuularized logistic regression (1) under Assumption 1. Assume without loss of generality that wo 0. There exist constants C₁, C2,Cr C3 > such that the following holds. For every n. 2 2,
x2
and 1) S min {
7
72
X 2 Cinlan
VC,x Cnns
we have the following:

---

Phase transition. GD must be in the stable phase at step T for
Inn
max 1 n
that is, [(W,) decreases monotonically for t 122 T.
The stable phase. Moreover, for every 1 2 we have
[(we) - min C S Coge-An(tr) [[w, - wall C3 In((2/2) e- -n((t-r/22
Theorem 1 provides a convergence guarantee for GD with stepsize as large as = O(I/A) (treating other
parameters, Y and as constants). With this stepsize, GD might not decrease the objective monotonically- that is, GD might be in the EoS phase the beginning. Nonetheless, Theorem shows that GD must undergo phase transition to the stable phase in T = (T) steps. In the stable phase, GD benefits from the large stepsize, achieving an e error in O (lI(()c)/(())) subsequent steps.
Theorem I recovers the classical (In(L/=)/A) step complexity when GD operates in the stable regime with 77 = (1). Additionally, Theorem suggests that GD achieves faster convergence the EoS regime when the stepsize is large, but not larger than (A1/VA). Choosing the largest allowed stepsize, GD matches the accelerated step complexity of Nesterov's momentum. This is detailed in the following corollary, with proof deferred to Appendix A.3.
Corollary 2 (Step complexity under small regularization). Under the setting of Theorem 1, by using the largest allowed stepsize,
72
min
VVTx
GnndS
we have [(we)= min E S e for
S C4 max
In(1/e),
< ?2
where C4 > 1 is a constant. Thus for X /n/n,, 11 2 1/ ensures that / In(1/8)/ suffices.
Matching Nesterov's acceleration. Treat y constant. For a small regularization of X S 1/n2. Corollary 2 shows that GD achieves step complexity of (In(1/e)/
/////// VA) using large stepsize. Since the condition number is λ = (1/A), this matches the accelerated step complexity of Nesterov's s momentum, improving the classical (In(1E))/A) step complexity for GD in the stable regime.
For moderately small regularization, 1/n² Z X 1/(n n). Corollary 2 implies a step complexity of On ln(1/e)) for GD with large stepsize, which still improves the classical (ln(11/)/A) step complexity for GD in the stable regime (by at least logarithmic factor). However, it no longer matches Nesterov's 's momentum. It is an open question whether large stepsize GD can match Nesterov's momentum for a moderate (or large) regularization.
lower bound for stable convergence. We have shown that large stepsizes accelerate the con- vergence of GD. This acceleration effect closely tied operating in the EoS regime. To clarify, our next theorem shows that GD in the stable regime suffers from an (21/A) step complexity in the worst case. Its proof is deferred to Appendix B.
Theorem 3 (A lower bound). Consider (GD) for fz-regularized logistic regression (1) with wo and the following dataset (satisfying Assumption 1):
X1 (7, 0.9), X2 (7, -0.5), y1 = =2 << 0.1.
There exist C1, C2, C3 > 1 that only depend on such that the following holds. For every X < 1/C1 and < C2Xln if is such that (E(w,))azo is nonincreasing, then
12 In (1/6)
Z(w.) min E <
In
It is worth noting that Theorem 3 focuses the common asymptotic case of small E; for 2
A In (1/A), the step complexity is ((1/s), which is reflected by its proof in Appendix B.
5

---

A limitation. We conclude this part by discussing a limitation of our Theorem 1. Note that Theorem only allows a small regularization such that S ( A regularization of this order might be suboptimal in the presence of statistical noise. Moreover, the proof of Theorem implies that, in the stable phase, all training data are classified correctly (see Lemma 13 Appendix A.2). Therefore, the allowed regularization is too small to prevent the minimizer from perfectly classifying the training data. A similar limitation is encountered in the prior work of Wu et al. (2024), who showed acceleration with large stepsizes only when targeting optimization error small enough to imply perfect classification of the training data (see their Corollary 2).
Depending on the statistical model, perfect fit to the training data does not necessarily lead to overfitting (a phenomenon known as benign overfitting, see Bartlett al., 2020). Even so, larger regularization such as À 2 1/n often leads to better performance in many statistical models (one such case will be discussed Section 3). Below, we show that GD can still benefit from large stepsizes even with regularization larger than 1/(n m)). This allows large regularization that leads to misclassification of the training data.
2.2 Improved convergence under general regularization
Our next theorem characterizes the convergence of GD for fz-regularized logistic regression in the EoS regime with general regularization hyperparameter X. The proof is deferred to Appendix A.4. Theorem 4 (Convergence under general regularization), Consider (GD) for ez-regularized logistic regression (1) under Assumption 1. Assume without loss of generality that Wo 0. There exist constants C₁ C2 C3 > 1 such that the following holds. For every
72 C 1
72
1/3
A
CiA
we have the following:
Phase transition time. GD must be in the stable phase at step == C2 max(1, /////?
The stable phase. Moreover, for & 2 T, we have
min E Cs Ao(t--), ||w,-wAl] S C33 7 In()9/A) (112--1/2 r
E(w.) min
Similarly to Theorem 1, Theorem 4 allows large stepsize, in which GD might be in the EoS phase at the beginning, then it must transition to the stable phase in finite steps, achieving an exponential convergence subsequently.
Unlike Theorem 1, where the allowed regularization and phase transition time are functions of the sample size n, Theorem 4 is completely independent of the sample size In particular, it allows for a large regularization of order 1/(n n) S X S 1, with which the minimizer of the regularized logistic regression (1) might not correctly classify the training data.
The relaxation of the allowed regularization obtained at the price of a tighter constraint on the allowed stepsize, 1 ((1/x//3), and slower phase transition time, (11)²). Nonetheless, Theorem 4 still implies that large stepsizes lead to acceleration, as explained in the following corollary. Its proof is included in Appendix A.5.
Corollary 5 (Step complexity under general regularization). Under the setting of Theorem 4, by using the largest allowed stepsize, 17 (n22 \))3 we have [(w.) - min L S for
S Cs In(1/s)
(7x)2/3*
where C3 >> 1 is a constant.
Ignoring the dependence on y Corollary shows that GD achieves an error in (1I((1/)//X2/3) steps using a large stepsize. This improves the classical (In((/E)/A)) step complexity for GD the stable regime, although it does not match Nesterov's momentum.
We remark that the predictions of Corollaries and 5 are incomparable even the regime where both are applicable, that is, X & (nlan)-1. Specifically, in this regime, Corollary 5 predicts step

---

complexity of ((x-2/3) 2/33) while Corollary 2 predicts a step complexity of O (max 1// n)). The 1/2
prediction of Corollary is worse for À S n n3/2 but is better for n n-3/2 3/2 Corollaries and 5 are incomparable even in the joint applicable regime, suggesting our analysis is improvable. Technically, this mismatch stems from two distinct approaches for analyzing phase transition (see Section 2.3). We leave it as future work improve our analysis.
S S (n In)) Thus,
In statistical learning contexts, the (optimal) regularization hyperparameter À is often function of the sample size n, for example, À (1/nn)) for some 0. In contrast Corollary which only applies to small regularization (with or > 1), the acceleration implied by Corollary 5 applies to any such À (in particular, with 0 < a S 1). Specifically, Corollary 5 shows an 2n/23 In(1/e)) step complexity for GD when À (11/n") for any a 0. We will revisit this later in Section 3 and show the acceleration of large stepsizes in a statistical learning setting.
2.3 Technical overview
In this part, we discuss key ideas in our analysis and elaborate on our technical innovations compared to the prior work of Wu et al. (2024).
Bounds in the EoS phase. The following lemma provides bounds on the logistic empirical risk and parameter norm for any time; in particular, applies the EoS phase.
Lemma (EoS bounds). Assume that y, S 1/2 and wo 0. Then for every and in particular in the EoS phase, we have
[(w)) S 10 12 + In2 + 72 min mt, 1/A3), 72 min(nt, (nt, 1/2}
||w/|| < 4 4 In(e + 72 min(nt, 1/AJ)
?
k=
Lemma recovers the EoS bounds in (Wu et al., 2024) (see their Lemma 8 in Appendix B) for the special case of = O. The intuition is that, for yt < 1/A, the regularization term is negligible compared to the logistic term. However, these bounds are too crude for large f.
New challenges. The analysis by Wu et al. (2024) relies on the self-boundedness of the logistic loss, [[V][(w)]] S. L(w). and that the minimizers of L() appear at infinity. Although GD with large stepsize oscillates initially, it keeps moving towards infinity along the maximum fz-margin direction, which reduces the objective L(w [[w) in the long run. Once GD hits a small objective value, L(w) S 1/m, it enters the stable phase as the local landscape becomes flat due to the self- saff-bonddedness. In the stable phase, GD continues to move towards infinity along the maximum & margin direction.
However, the situation is significantly different in the presence of an fz-regularization. In this case, the minimizer has small norm, || ((n(11 1/)) (see Lemma 3 in Appendix A. But large stepsizes GD can go as far as (()) = (1))(1/A) in the EoS phase (Lemma 1), which is even more distant from the minimizer than the initialization wo = 0. Instead of moving towards infinity, in our
case, GD must move backwards (if it converges).
Consider flat region defined
{ (w:: 1
[(W)] vo (w: [(w) S 1/n)-
When GD enters this region, we expect Σ(w) to decrease in the next step (see Lemma 12 in Appendix A.1). However, different from Wu et al. (2024), this does not guarantee that GD stays in this region. In fact, the regularization term leads to contraction towards zero, so a decrease of ((w) may cause an increase of L(w), and then GD might leave this region. In Theorems I and 4, we identify two situations where GD stays in the flat region, respectively, as explained below.
Intuition of Theorem 4. When $ 1/21/3, Lemma implies a small regularization term through- out the training, A/ A/w.l|2- ( ) 0(1/)). Thus, the logistic term dominates the whole objective in the EoS phase, and L(w) S 1/r is nearly the same as Z(w) S 1/n, By the decrease of Z(w) within the flat region, we can show GD stays in this region by induction (see Lemma 15 in Appendix A.4).
7

---

Table 1: Step complexities for variants of GD to reach a population risk of ((1/n).
algorithm
# steps
population risk
((n)
0
(1)
o(L((?An))
GD
(n Inn)
1/n
1
o(L((7An))
(((n/)22/8 Inn)
1/n
(((2n))//s)
Ō(L((?Pn))
Nesterov's 's momentum
((n In)) 0(1/9))
1/n
1
Ō(L((?P)))
adaptive GD
@(nn))
Ō(1/(AAn))
Intuition of Theorem 1. For rj - 1/X1/2, the above arguments no longer work, since the regu- larization term could be as large as ((rrp) = O(1) I) in the EoS phase. Alternatively, we compare the size of the gradients from the logistic term || [(w) and the regularization term ||Aw]]. If the former is larger, then the logistic term decreases; the latter larger, then by the exponential tail of the logistic loss, we conclude that ((w) = [[ || & ||Aw|| = ((1/)), where the last equality is by Lemma 1. In both cases, GD stays in the flat region (see Lemma 13 in Appendix A.2).
3 Benefits of large stepsizes under statistical uncertainty
In this section, we apply Theorem 4 in statistical learning setting, showing that the acceleration of large stepsizes continues hold even under statistical uncertainty. We make the following natural assumption on the population data distribution.
Assumption 2 (Bounded and separable distribution). Assume that (x,, Vi are independent copies of (x, 3) that follows a distribution such that
A. the label binary, y E {=1}, and |x|| S 1, almost surely:
B. there exist margin > 0 and a unit vector w such that yx w" 2 Y, almost surely.
The population risk of an estimator w is defined as
Ltest (W) == E In (1 + exp(- yyx w)),
where the expectation is over the distribution of (x, y) satisfying Assumption 2.
The following Proposition gives the best-known population risk upper bound (without assuming enormous burn-in samples) in the setting of Assumption 2. This is direct consequence of the fast rate established by Srebro et al. (2010, Theorem 1) using local Rademacher complexity (Bartlett et al., 2005). A variant of Proposition also appears in Schliserman and Koren (2024, Proposition 1). We include its proof Appendix C.I for completeness.
Proposition 6 (A population risk bound). Suppose that (x;, y: satisfies Assumption 2, Then for every w, with probability at least 1 over the randomness of sampling (x,, y.) have
Leest (w) S C. ( [(W)+ max [|]]]]]] In (nn(())
(n))))))))))) +l((1/0))
7
where C' > is a constant.
Recall that the minimizer of C(.) is at infinity under Assumption 2. However, Proposition 6 suggests that good estimator should balance its fit to the training data (measured by L(w)) and its complexity (measured by ||W]]) []). also worth noting that the upper bound in Proposition bottleneck that stems from the statistical uncertainty. With this in mind, we are ready to discuss the number of steps needed by GD (and variants) minimize the population risk to the statistical bottleneck. Table summarizes the results, which explain in detail below.
at least (2(1n))4

---

Logistic regression with eg-regularization. Let us first consider the minimizer of the fz- fg-regularized logistic regression, WA := arg min [()). With direct calculation, setting À ((1/n) minimizes the upper bound in Proposition 6, resulting in an ((1/(??n)) population risk (see Appendix C.2 for details). This is nearly optimal ignoring the logarithmic factors and dependence on
% Clearly, the same bound applies any approximate minimizer w such that || wall S E = l/poly(n). To obtain such an approximate minimizer,
GD with small stepsize 7 1 needs On in steps by the classical optimization theory;
GD with a large stepsize 11 (((72n)1/3) needs (((n/7)2/3 In n)) steps by Theorem 4; 1 In n)) steps by the classical optimization theory.
Nesterov's 's momentum needs (nn
These suggest that large stepsizes accelerate GD in the presence of statistical uncertainty, although not as fast as Nesterov's 's momentum.
Logistic regression without regularization. Instead of solving regularized logistic regression, one can also apply GD to the unregularized logistic regression with early stopping to obtain a small population risk. For instance, Shamir (2021) showed that GD with a small stepsize rj = 1 achieves a population risk of ((1((22n) in (n) steps. A similar result is obtained by Schliserman and Koren (2024) using different proof technique.
For GD with a larger stepsize, Wu et al. (2024) obtained an empirical risk bound of L(w,) = O(7² + In (mt))/(>)))) and parameter norm bound of ||w.]] = -(( + In(m())/7). Note that we do not consider their accelerated empirical risk bound here, as only applies after ((n) steps. Plugging these bounds into Proposition 6, however, one cannot resolve for stepsize 1y better than the choice of 7) = 1 (ignoring logarithmic factors). That is, without regularization, solely using large stepsize does not accelerate GD in the presence of statistical uncertainty. This sets an interesting gap between our acceleration results and those by Wu et al. (2024).
One can also solve logistic regression via adaptive GD (Ji and Telgarsky, 2021; Zhang et al., 2025), defined We+1 : Wt it adapts to the curvature. Specifically, Zhang et al. (2025) obtained an empirical risk bound of C(w,) S exp(-0(>²17t) for > 1/7² (see their Theorem 2.1) and a parameter norm bound of [well S 1t (see the proof of their Theorem 2.2), where w, is the average of the iterates up to step t. Plugging these bounds into Proposition 6, we minimize the upper bound by setting 7 = O(In n) and t = (1//²),, with which the population risk is (()((>nn) Although the step complexity is much improved, the population risk seems to have a suboptimal dependence on 7.
This is faster for optimization than GD as
limitation. We note that the above discussion based on the hest-known population risk upper bound in statistical setting specified by Assumption 2. Depending on the actual data distribution, the population risk might be smaller than that (although we suspect the upper bound is nearly sharp in the worst case). We leave it for future work to investigate the effect of large stepsizes in broader statistical learning settings.
critical threshold on the convergent stepsizes
We have shown the global convergence of GD with stepsizes as large as O(1/VA) in Section 2. Clearly, if 17 >> 2/A, GD diverges with almost every initialization. But the largest convergent stepsize is unclear yet-this this is the focus of this section. We will show the largest convergent stepsize is (LL/(AIn(1/A) under the following technical condition:
Assumption 3 (Support vectors condition). Let S. be the index set of the support vectors associated with nonzero dual variables (formally defined in Appendix D.1). Assume that rank(x; : E S+} rank(x), "x....,...,,...
Assumption 3 is widely used in the literature of logistic regression (Soudry et al., 2018; Ji and Telgarsky, 2021; Wu et al., 2023), requiring the support vectors to be generie. Under this condition, the features (x,) can be decomposed into separable component and strictly nonseparable component (Wu et al., 2023). Under Assumption 3, our next theorem sharply characterizes the largest convergent stepsizes, with proof deferred to Appendix D.I.

---

Theorem 7 (The critical stepsize). Suppose that H. is finite unite-dimensional and that Assumptions 1 and 3 hold. Consider (GD) for lz-regularized logistic regression (1). Let Merit == 1/(A 1 In(1/X)), Then there exist C1, C2 > 1 that only depend on the dataset (hut not on X) such that the following holds. For every S 1/C1, we have
n S Merit C2. then GD converges locally. That is, there exists > 0 such that, for every wo satisfying w T and every such 13, we have [(we) - min C.
!f 1) 2 C2Merit- then GD) diverges for almost every Wo- That is, there exists e 0 such that, excluding a measure zero set of Wo. we have [(we)- (emi)-min/ C > f infinitely many t.
Theorem 7 suggests that if the stepsize exceeds the critical threshold Merit by constant factor, GD must diverge except with a "lucky" initialization. The critical threshold Teriit. improves the trivial divergent threshold of 2/A by logarithmic factor, and is tight in the sense that GD converges locally for any stepsize smaller than that by constant factor. This is in sharp contrast to unregularized logistic regression, where GD converges globally for any stepsize (Wu et al., 2023, 2024).
It remains open whether GD converges globally with stepsizes of order 1/vV S S Terit- In the special case where HI is 1-dimensional, we provide an affirmative answer Theorem 8 in Appendix D.2 along with a step complexity of O [In(1/(EX) (n(1/A)))/(n)))) reader (Meng et al., 2024, 2025) for fine ane-grained convergence analysis this case. In the general finite-dimensional case, we conjecture that the answer is affirmative in the following sense:
We also refer the
Conjecture 1. Under the setting of Theorem 7, if T S Merit/C2 and Wo is sampled uniformly at random from a unit ball, then GD converges with high probability over the randomness of initialization.
5 Concluding remarks
We consider gradient descent (GD) with constant stepsize applied to fz-regularized logistic regres- sion with linearly separable data. We show that, for small enough regularization, GD can match the acceleration of Nesterov's momentum by simply using an appropriately large stepsize- which the objective evolves nonmonotonically. Furthermore, we show that this acceleration brought by large stepsizes holds even under statistical uncertainty. Finally, we calculate the largest possible stepsize with which GD can converge (locally).
This work focuses on the cleanest setup with logistic loss and linear predictors. However, the results presented are ready to be extended to other loss functions (Wu et al., 2024), neural networks in the lazy regime (Wu et al., 2024), and two-layer networks with linearly separable data and bi-L bisciis activation (Cai et al., 2024). We do not foresee significant new technical challenges here.
There three future directions worth noting. First, in the context of our paper, does GD converge globally with large stepsizes below the proposed critical threshold? Second, is there a natural statistical learning setting such that GD with large stepsizes generalizes better than GD with small ones? Finally, is there a generic optimization theory for the convergence of GD with large stepsizes? Specifically, is there a general framework prove the convergence of constant stepsize GD without relying on the descent lemma?
Acknowledgments
We gratefully acknowledge the NSF's support of FODSI through grant MMS--002355 and of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-203188 and #814639 and of the ONR through MURI award N0001421 P.M. is supported by Google PhD Fellowship. The authors are grateful to the Simons Institute for the Theory of Computing for hosting them during parts of this work.
References
Jason M Altschuler and Pablo Parrilo. Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule. Journal of the ACM, 72(2):1338, 2025.
10

---

Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge of stability in deep learning. In International Conference on Machine Learning, pages 948-1024. PMLR, 2022.
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, pages 1497-1537, 2005.
Peter L. Bartlett, Philip M Long. Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30033-30077 2020.
James Bradbury. Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Mihen and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
atttp://ithute com/ google/jax.
Yuhang Cai, Jingfeng Wu, Song Mei, Michael Lindsey, and Peter Bartlett, Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability, In International Conference on Learning Representations, 2020.
Jeremy Cohen, Alex Damian, Ameet Talwalkar, Zico Kolter, and Jason D. Lee. Understanding optimization in deep learning with central flows. In The Thirteenth International Conference Learning Representations, 2025.
Alex Damian, Eshaan Nichani, and Jason D Lee. Self-stabilization: The implicit bias of gradient descent at the edge of stability. In The Eleventh International Conference on Learning Representa- tions, 2022.
Benjamin Grimmer. Provably faster gradient descent via long steps. SIAM Journal on Optimization, (153):288822603 2024.
Morris W Hirsch, Stephen Smale, and Robert L Devaney, Differential equations, dynamical systems, and an introduction to chaos. Academic press, 2013.
A. Hoorfar and M. Hassani. Inequalities on the Lambert w function and hyperpower function. JIPAM, 9(2), 2008.
Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors in high dimensions. In International Conference on Artificial Intelligence and Statistics, pages 91-99. PMLR, 2021.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint orXiv:1803.0755 2018.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pages 772-804, PMLR, 2021.
Steven Krantz and Harold R Parks. A primer of real analytic functions. Springer Science Business Media, 2002.
Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao, and Christopher De Sa. Gradient descent on logistic regression with non-separable data and large step sizes. arXiv preprint arXiv:2406.05033, 2024.
Si Yi Meng, Baptiste Goujaud, Antonio Orvieto, and Christopher De Sa. Gradient descent on logistic regression: Do large step-sizes work with data on the sphere? arXiv preprint 1221v 2025.
Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability: A view from function space. Advances in Neural Information Processing Systems, 34:17799-17761, 2021.
Yurii Nesterov. Lectures on Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3379915770.

---

Albert BJ Novikoff. On convergence proofs for perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata. New York, NY, 1962.
P. Ponomarev. Submersions and preimages sets measure zero. Siberian Mathematical Journal, 28(1):153-163, 1987. ISSN 1573-9260.
Dan Qiao, Kaiqi Zhang, Esha Singh, Daniel Soudry, and Yu-Xiang Wang. Stable minima cannot overfit in univariate ReLU networks: Generalization by large step sizes. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Saharon Rosset, Ji Zhu, and Trevor Hastie. Boosting regularized path maximum margin classifier. The Journal of Machine Learning Research, 5:941-973, 2004.
Matan Schliserman and Tomer Koren. Tight risk bounds for gradient descent on separable data. Advances in Neural Information Processing Systems, 36, 2024.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Ohad Shamir. Gradient methods never overfit separable data. Journal of Machine Learning Research, 22(85):1 1-20, 2021.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. Advances in neural information processing systems, 23, 2010.
Jingfeng Wu, Vladimir Braverman, and Jason Lee. Implicit bias of gradient descent for logistic regression the edge of stability. Advances in Neural Information Processing Systems, 36: 74229-74256, 2023.
Jingfeng Wu, Peter L Bartlett, Matus Telgarsky, and Bin Yu. Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. In The Thirty Seventh Annual Conference on Learning Theory, pages 5019-5073. PMLR, 2024.
Jingfeng Wu, Peter Bartlett, Matus Telgarsky, and Bin Yu. Benefits of early stopping in gradient descent for overparameterized logistic regression. arXiv preprint 2rXiv:2502.13285 2025a.
Lei Wu, Chao Ma, and Weinan E. How SGD selects the global minima in wer-parameterized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 31, 2018.
Yu-Han Wu, Pierre Marion, Gérard Biau, and Claire Boyer. Taking a big step: Large learning rates in denoising score matching prevent memorization. arXiv preprint (xXXi::2502.033335 2025b.
Ruiqi Zhang, Jingfeng Wu, Licong Lin, and Peter Bartlett. Minimax optimal convergence of gradient descent in logistic regression via large and adaptive stepsizes. arXiv preprint arXiv:2504.04100
2025.
Zihan Zhang, Jason Lee, Simon S Du, and Yuxin Chen. Anytime acceleration of gradient descent. arXiv preprint arXiv:2411.17668, 2024.
Xingyu Zhu, Zixuan Wang, Xiang Wang, Mo Zhou, and Rong Ge. Understanding edge-of-stability training dynamics with minimalist example. In The Eleventh International Conference on Learning Representations, 2022.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction clearly state the paper's contributions regarding the acceleration of gradient descent for regularized logistic regression using large stepsizes. The scope, focusing on linearly separable data and the theoretical analysis of convergence rates and stepsize thresholds, is also well-defined.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper explicitly discusses limitations of each main result.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: The paper clearly states assumptions in each theoretical result, with complete and rigorous proof referenced and presented in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The experimental results are purely illustrative. All necessary information for reproducibility is given in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide an open source implementation our experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
//wpps.ccppubl/// http:ccccpppccccccecceeccccccccc htppuulcccuuuieeessseepppp guides/ /CoeeSubmdeabiii ssi ssisssoolooooooooo oonooiiyyyylolooooooooooomiiiiil for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental results are illustrative; we do not claim any statistical significance.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[No]
Justification: significance.
The experimental results are illustrative; we do not claim any statistical
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments run on consumer laptop a few seconds.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:::////uiipp// cc Appblic/Ethii caabliie/thissuuueeellle ines?
Answer: [Yes]
Justification: The paper is theoretical, with no indication of ethical concerns that would violate the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical, with no indication of having potential positive or negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is theoretical and does not contain experimental results.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper is theoretical and does external code, data, models that would require specific license mentions beyond academic citation practices.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper is theoretical and does not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The paper does not involve LLMs as a component of the core methodology.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttp///erssp/////ee cc/Conferences//2000 /LLM) for what should or should be described.
19

---

A Upper bounds on convergence in the EoS regime
Throughout this section, we assume Assumption holds; we set Wo without loss of generality. Let {(z) In(1 + exp(-2)) be the logistic loss. Define the gradient potential as
1 n2
g(w): = (e
w)]
+ expluxx w)
Recall that WA := arg min 2(-).
We first establish useful lemmas in Appendix A.I. We then prove our first set of upper bounds, Theorem and Corollary 2, in Appendices A.2 and A.3, respectively. Finally, prove second set of upper bounds, Theorem and Corollary 5, in Appendices A.4 and A.5, respectively.
A.1 Basic lemmas
We begin with the seff-boundedness property. Lemma (Self-boundedness of the logistic function). For all a E I. we have
(x)) < f(z).
Proof of Lemma 2. First notice that, for 0,
(1+a) a) a.
(2)
Indeed, the function J(a) (1+ a) In(1 + a) satisfies (0) 0 and J'(a) In(1 + at), which positive for a > O. Now, since (1) = - 1/(1 + exp(2)), we have
exp(2)
(²(2)
(1 + exp(2))²
1 + exp(2) 1e((2))
< In(1 + exp(-x2 = {(z),
where the last inequality uses (2) with a = exp(=x) ()).
The following lemma provides bounds the norm and objective value of wa
Lemma 3 (Bounds the minimizer). For X < ?2, have
|| S V2 + In(>//A) [(wa) 1(2 (12(1//11)
272
Proof of Lemma 3. For
u: In(??/A) w"
we have, by Assumption 1,
= A
In (22/2
C(u) < exp(->/|lul)
72 ||u||
72
Then by definition, we have
A Z(w>) L(wx)
A(2 1n²(?/AA))
T 2 C(u) + 2
This completes the proof.
The following basic facts due to Assumption 1.
Lemma 4 (Basic facts). For all w, have
20

---

1. 70(w) & (- VL(w)) w*) S ((w).
2. 19(w)= & VV(()] 5 (g(w).
3. [|V]L(w)]| < ((w)= 5 <L(w).
If [(w) = (n( n or g(w) - 1/(2m), then L(w) S (g().
Proof of Lemma 4, Since
1 VL(w)
y,
exp( w) 1=1
the first claim is due to 7 S y/X; w' < by Assumption 1. For the second claim, the lower bound is by the first claim, and the upper bound is by the assumption that || x S 1. The third claim due to the seff-boundedness of the logistic function (Lemma 2) and the assumption that ||x,|| S In the last claim, both conditions imply that all data are correctly classified, then the claim follows from the fact that (n(1 + e S e- 2/(1 + e²) for i 2 0.
The following lemma suggests that GD aligns well with w throughout the training.
Lemma (Parameter angle). For Xn < 1, we have
(We, w") >
Proof of Lemma 5, Unrolling (GD) from Wo O, we get
k=0
So we have
t-1
(We, w") (1-mA)) (- w 2 m
Σ (1
-x)=-1-=((wa) >0, 0,
where the first inequality is by Lemma 4. This completes the proof.
The following two lemmas are variants of the split optimization lemma introduced by Wu et al. (2024). Lemma 6 (Split optimization, version 1). Let i1 + u2 u3 for
U2 w u1 |ullw
||/3///
For Any < 1, we have
Wr u||2
|
+
Σ ((w)) + Σ C(wa) < ((u1)
(Kx u)-
2nt
2nt
Proof of Lemma 6. We extended version of the split optimization technique by Wu al. (2024), which involves three comparators.
|/e+1 u/|2 || u + 2ny (rV(Z( u w.) + +
||w u|/² 2n(WV((.. +
- w.) uw,, 1/' VL(w.) V Aw,
||: 2 2n)(V + Aw, -.
2n,² ||
3 < ||: -vl 27)(V[(w,) (.)) + +2).A u) 27y /L(w.))
where the last inequality is because Xnj 1. The choice of u2 and Lemma 4, parts and imply
2Ty( 3n(-VL(w,)) u2) > (w,,) 2 |V(,,) //
21

---

(See also the proof of Lemma 7 in (Wu et al., 2024).) Then we have
|We+1 u|/ 2 - w: - 1 + (7/VV u1 w.) 2n(V[((w)) 11) + 1-2n)/W. u).
By convexity and Lemma 4 part 1, we have
||Wr+1 ull S ||w, - ull + (7((( - ((w.)) - 33/:|/u3//(w, + 21/2(wr, u).
Telescoping the sum, using Wo 0, and rearranging, get
w. ull2 r||uall
1-1 Σ g(wa) + t
1-1
||u|| 2nt
+ 2 (1 E
Σ h=
((wa) s L(u)) +
Wk: u
2tt
R=
h=
which completes the proof.
Lemma (Split optimization, version 2). Let U1 + for
U2
11
w ||u w
27(1 -na)
For An < 1, we have
t-1
|w 2 (1 (1-11)) mA) uul + 2n
Σ (1
1
Proof of Lemma 7. Recall that
Wt+1 - u (1 (/)(w, - u) 17Au - w/V.)(
Taking the squared norm and expanding, we have
|w++1 - u/l = (1- - 1 w. - u112 + (1)))---)))((())).)) w.) + + 2, + = (1 - 1t/p://----2222211001///wwww->-) w.) + +
+ +1 21/2(1 -
V.(w.))
- 2n
+ m222 n>)i|u|12 2n/A(1 (u, wx) + 20 X/u, V((w.))
The sum of the last two terms of the previous identity is negative,
22 (u) w.) + Xu,, VL(w:)) = 2n, wo41) < 0,
where the last incquality is by Lemma 5. Moreover, the choice of un and Lemma 4, parts and imply that (see also the proof of Lemma 7 in (Wu et al., 2024))
2n -
uz) 1 ))1 0..
So have
|| W - u/l2 < (1 - 7/ - u1 + 2n(1 - (V un - w.) + 1/A22 - n/]llul|?
< (1 - (/ |w; u12 + 2m - (()))) - -(ww)) + 1/(22 |/)
< (1 m/^i Wr uul2 + 27
(C)()))))) -(w:)) + 2n//l/u|/².
Unrolling the recursion, we get
f-1
|[ u|| 3 < (1 nAA' + 2n
> (1 -
(1- (1-N)(((())) + Allu|3).
k=
This completes the proof.
Based on these split optimization bounds, the following three lemmas establish bounds on parameter norm, gradient potential, and the logistic empirical risk, respectively.
Lemma 8 (A parameter bound). For n < 1/2, we have
| < 4 7 In(e + x² min mt, 1/A})
22

---

Proof of Lemma 8. By Lemma 7, we have
1-1
lw u/1 S (1- m) ||]
2m Σ (1 71)6 (11 (-)))(()()))) \l|ul(3)
k=0
= (1 - 1| + (1 (1- 1111'
((1-n))((u)) + +
X
1 - (1-11))))
$ 2
X [(u1) + 2||u|²
$ 2 min (n) + 2||u||²
In the final inequality, the proof that - (1 - 1///3 S 17 is by induction. For v/ S $1/1 1/2 and
u1 In(e 72 min(nt, nt, 1/2}) w" U2 2y(1 172)
"1 w"
we have
U2ll
! < ?
L(ui) exp(=>/ exp(->|luil)) 5 72 min, 1/2}
Combining, we have
wwll 1 ww u/ + |||||
2 min (in 1/A) + (V2 + 1) ||u||
22
7 In(e + 7² min(nt, 1/21)
7 + (V2+1)
+ Iinee + 7² min (nt 1/2))
This completes the proof.
Lemma (A gradient potential bound). For n $ 1/2, we have
((w)) 11 77 + In(e + 7² min ntt 1/A))
72 min 1/2}
Proof of Lemma 9. Let u in + us + ug and
In(e 7² min (nt, 1/A))
"1 w'
" n In(e 72 mintftt 1/2))
=1
w U1
ug
Then we have
| 7'
|u|| 2||uall. C(ui) S 72 min 1/A}
Moreover, Lemma 8 yields
max
||all S 4 usll- kst
Using Lemma 6, we have
Σ ((wx) S > 7/|usl1
1
(((u))+
|u||
+
\||u||
max [|wxl]) ASt
27t
1
2||us||
+ sx|[ual)
||u3|// min 1/2}
mp
1
2
+ In(e + 72 min (nt, 1/A))
min (nt, 1/2} +
+ 82
1y
< 11 77 + In(e +22 min min(nt, 1/AH)
22 min min, 1/A)
This completes the proof.
23

---

Lemma 10 (A logistic empirical risk bound). For nn S 1/2, we have
7 ((wx) - 10 n2 + In (e + x² min 1/A1)
72 mil, 1/2}
Proof of Lemma 10. Let u = u1 + u2 + us with
In + 72 min 1t, 1/A))
w" U2 -w* ug = 0.
Then we have
|u|| 7 + In(e + 7² mmnn (11,, 1/AH)
((ui) S 72 min 1/23"
7
By Lemma 8, we have
max ASt
||wll S 4||u||-
Using Lemma 6, we have
||]| 2nyt.
Σ
((wx) S L(u1) +
+ A||u||
max ||wxll kgr
km 0
s L(ui)
+ 41
||u||2
22pt.
172 1I+n2(e + 72 minn 1/A])
$ 72 min (tt 1/2} + 2
+ +.4
2nt
72
10 122 + In (e + 2² min min(1t 1/A1)
72 min((d mt,, 1/2]
This completes the proof.
The next lemma shows that when the gradient potential is small, it remains small under step of GD (even when the stepsize is large).
Lemma (Small gradient potential). Assume that
1 31/ In(e + n)
A
If in the 1-th step have
((w,) S 20211*
then for every v in the line segment between we and Wi+1, we have
g(v) < 2n
Proof of Lemma 11. There exists an a E [0, 1] such that v = awi+1 + (1 a)w,. Then for every 1 < n. we have
vix yix, (a((1 - 1/)l: [/Ww)) + (1 (1-a) a)w:))
(1 adN))xx We OmNix VL(w:)
2 (1 an)))x W. /lWV)(
2 (1 ann) We (w,,)
2 (1 an4)). w: -
24

---

where the second inequality is by Lemma 4 and the last inequality is because ((w,) S 1/n,. So we have
1
1 exp((1 adn))yx We
g(v)
71
1 1= exp((1 adn)yiii we)
n + exp(Uxx (ir] exp(uxx/w:))
Recall the following inequality:
1 1+20
2 x1) for x 2 0 and 0 < < 3B3 <
We this by verifying that the function x + + x (1 + ) is increasing for and maps to O. Applying this inequality and the concavity of the function we obtain
x for 0 < 8 < 1 and > 0.
1-a
g(v)
S
+ exp( w.)
71
i=1
n
I-oAn
S e
+ exp(yxx, ws)
= cg(ww)) 1-an
Using the assumption on G(w.). we get
(1 (1-aAm)
1
1 (2e²n)
g(v)
exp (aAn In(22² < 2n²*
2
2En
2en
where the last inequality is because adn In(2??n) < 1, which is verified by discussing cases. If 2e2n) & 1, this trivial; 2e > 1, this follows from our assumption on À and a S 1:
adn in s 2n)n((2en) In(2??n) S 1. 3ln(e + n)
This completes the proof.
The following lemma shows that if the gradient potential is small, then the objective value decreases after one step of GD.
Lemma 12 (One contraction step). Assume that
1
31 In(e + n)
If in the t-th step we have
1
((w,) -
202n"
then we have
I(w++1) S I(wi) - " [V(((.
Furthermore, we have
E(wr+1) - min m (1 ())(( - -mii:)))m))))) 2) and || - wxll (1 -)))]| w
wall2.
Proof of Lemma 12. There exists v in the line segment between w, and Wx+1 such that
Z(w Ō(w.) (Vī(w.). West w.) } (V2ī(v), (We+) w,)
25

---

n/ V [(v)]
I S((s)) 7/ V.((w:)
2 = =((s)) 7/ Vi(w:))) (1 n(a + [[v)(()))))
Our assumption on À implies that An - 1/2. Then by Lemmas 4 and 11, we have
7 + [vI(v)l)
77 +
7(++9(v)) ((v))
0.5 + 0.5 1
2
2
2
2
which leads
(1 11- 7( + [VvI()
((w141) S [(wi)
- [(w.) ?
(VV((w))
2
The risk contraction follows from the above and the well-known Polyak-Lojasiewiez inequality from the A-strong convexity:
ī(w) min ES 2A |V[(w]]
The norm contraction is because
Wi+1 w2ll
|w wall + 21yl 2 VV(w)) W> we) + n7² V [((w)l
|w: wall + 2n [((w)) -[(w) X
2 -21we-walle) 1² ( (((w)) -((w(+)))
(1 - [-n)\//w; - wall? + 2m( ((((w) - -(we+1))
< (1 - //)l[ (1-7>)]]
10.-wyy w
where the first inequality is by X-strong convexity and the first claim, and the second inequality is because W arg min C(-). This completes our proof.
A.2 Proof of Theorem
The following lemma is crucial for showing that GD remains in the stable phase. Lemma (Stable phase). Assume that n 2 2 and
1 1
min
nlan'
nyj
1
for a large constant Ci 1. If in the s-th step we have
In
((w.) S min
2e2ri n
then for all t 2 s we have
1n2
L(w)) min
22e2n)'
Proof of Lemma 13. The condition on À with C1 2 6 guarantees that
A min (alnn' 172 min {
1
5
1p 3(1 + +1)) 3r In(e + 1))
21j
which satisfies the condition on À required by Lemmas 8, 11 and 12.
We prove the claim by induction. The claim holds for Assume the claim holds for t. We then verify the claim for t + 1. By Taylor's 's theorem, there exists v within the line segment between w; and W such that
((w++1) [(w.) (VL(W,)) W.41 w,) 1 ? ((V)) w.)
26

---

-V((L(:, VL(W,) + Aw;) 1/2 (V) + Aw,)
S -V(((w))) VL((.) + Aww)
((v) + Awell?
2
where the last inequality is because Lemma 4 imply that
[2L(v)] - G(v) by Lemma 4. The induction hypothesis and
((w)) - [(w,) S min 1 In2 2
(3)
22e"n n S which implies G(v) S 2/n - 1/1 by Lemma 11. Then we have
[(we+1) - [(w,) - - - (Vw,,), VL((.) + Aw.) + " VL((:) + Awrll
--2 (I -X11w=1)))
We discuss two cases. If [[.(w))] 2 >//ww/ll, then [(we+1) S [(W:), which together with (3)
verifies the claim for + V < we/l then
[(W(+1)& ( [(w,) 1 w
s 29((w.) +
2
< 2 [VL((::)]
/
wrl
2
Allwell 2+ /n2/|well
2
where the second inequality by Lemma and (3), the third inequality is by Lemma and the fourth inequality is because |/ ((w))) < AlI well By Lemma 8, we have
27 + In(e + 7² mnt, 1/A)) Wwll S 4
I 44" 17 In(e + 72/A) =: M.
Then we have
AM I
MAM 2
AM 3
1n
C(w++1)
min
7
2e"nn
which verifies the claim for t + 1. Here, the last inequality by (4) (proved below), and the second inequality is because 1/i. < 1 by (4).
3AM
12A 17 + In(e + 7/A)
1
In
S min
(4)
7
72
2c
+ In(e In(e
[1 1
5
min
for sufficiently large constant KG
72/2
K1
i7' n
2
2
Ki(1i t + 72 >²/1)) and
2 Ki (nm + nnn(e + +//11)
7
72
72
2 G max(1, n²) and x
2 C1 maxfnn, n nnn for a sufficiently large constant Cj
72
Cm my, 2²
X
This completes the proof.
The next lemma provides bound the phase transition time.
Lemma 14 (Phase transition). Assume that n 2 2 and
A 5
min
C
n Innn
27

---

for a large constant C₁ > 1. Let
C2 7/
=
max
?) n,
for large constant C2 1. Then for all
In
g(w)) - [(w,) - min
2ce21 n
Proof of Lemma 14. The assumption on with C1 2 2 implies 17 - 1/2. Then by Lemma 9 we have
Σ ((wx) S 11 -
+ In(e Infe min my 72 min (1/T, 1/A}
the right-hand side smaller than min min(1/(4e?n)) (2(2)/(22) then there exists S r such that
1n
1
((w,) x min
46
2n
This further implies C(wa) S. 2g( S (in(1/(2e (1) by Lemma 4, and then Lemmas and 13 imply the result. So it suffices to check that
11 7 + In(e + 7² min (yr,, 1/AH)
In 2
S min
72 m 1/A}
4c2r
2n
17 + Infe + 72/1)
min
72/A
Ki
77
+ Infe + 72)))
1
min
2/1
K1
for a sufficiently large constant K1, As shown in (5) in the proof of Lemma 13, the first condition follows from our assumption on A. The second condition is equivalent to
72r 2 Ki (1 In(e + + and 7²r 2 Ki n + n In(e - (ofe-12177) P21T))
{ {")
n ninn' for a sufficiently large constant C2
< 727 2 C2 max n and 7²7 2 C2 max
+ 72 2 C2 max { 77.
n Inn
This completes the proof.
With the above lemmas, we are ready to prove Theorem 1.
Proof of Theorem 1. Our assumption on À and n satisfies the condition on and n required by
Lemma 14. That condition with C 2 6 implies that À < 1/(3(1 + v)²) S 1/(3g In(e + 7)) S
1/(2n), satisfying the condition on À and v required by Lemmas 8 and 12.
The phase transition time bound is by Lemma 14, which further enables Lemma 12 for all & 2 r. Thus have
[(wr+t) - min
min č < (1 - An) (E(()) min Z) S exp(->x1)(E(w,)) min 2),
[ w < (1 - >n)) -wll exp(-Xx)
wall?
remains to bound Z(w,) min Ž and ||w, - wAll
Our assumption on À implies 72 2 C1 2 c. Then by Lemma 8 we have
||,]| || < + In(e + 72 mim (18, 1/A])
< 17 + In2 In(>?/A)
17 + (//2
<
7
28

---

We then use Lemma 3 to bound |[, - -wal by
||- wall - w + [wwl S 7 <
V2+ 1n(2/(2/
71 In(?2/ $ 10
7 This completes our proof for the parameter convergence. Furthermore, the assumption on guarantees that
?
X
À (n 11 11
1, 722
72 S2,
72
Therefore, we have
W
2
< 7
(1+ + 2n (22))/ SC -
for constant C3 1. Also note that L(w,) S min min(11(222))) (n())))))) by Lemma 14. These two bounds together imply that
[(wr) + 2 -/1 C3.
((w,) min E -(w;)=
This completes our proof for the risk convergence.
A.3 Proof of Corollary 2
Proof of Corollary By Theorem 1, GD enters the stable phase in t steps, and then attains an error within an additional
In(L/s) max TVX 72 In(1/e)
7
steps. We can further upper bound the phase transition time by
1
max
?/ n, 1 7
In
max
[7. n}
7 22 nX
7/2
max
min
VX
: m]
max
where the first equality is by the definition of r, the second equality is because
77 min {
An min Inn Inn} 2 Inn,
the third equality is by the choice of 17, and the fourth equality is because max(min d2/b),b) max (a, b} for a, > So the total number of steps t S (ox((//TV,, (n(1/e).
L
A.4 Proof of Theorem
The following lemma shows that GD stays in the stable phase. Lemma 15 (Stable phase, version 2). Assume that
1 1
x Ci
min
173
for a large constant C1. If in the s-th step have
L(w,) S
402n
then all t 12 we have
[(w;) < 20
29

---

Proof of Lemma 15. The condition on À with C1 2 2 implies An - min(n, 1/1 S 1/2. Then by Lemma 8 have
for all i, ||well S 4 | In(e + 72 11n1,,,1111
+ + 72/1)
M.
7
Our assumption À implies that
A M2 8A(n In(e + +2/11))²
I 4e2n
2
y2
To see this, it is sufficient to check that
22 (1)²
+ +ln - Kin
for sufficiently large constant K
(6)
1
X (n +o+++ /2/)) S K27
1
and
for a sufficiently large constant K₂
722
K2np
??
X
1
min
for sufficiently large constant C₁.
C
n
With this, we prove the following stronger claim by induction:
1
for all 8, [(w:) S [(w.) S 202n
the s-th step, we have
[(w.) < E(w.) < [(w.) + | S <((s) + M2 - 2c²1¹'
which satisfies the hypothesis. Next, assume the hypothesis holds for t. Then ((w,) S [(w,) S 1/(2e"n)). Additionally, our assumption on À with C1 2 6 implies À < 1/(3(1+77)) S (3/
7)). Thus we can apply Lemma 12 for f. obtaining that [(w(+1) & [(w.) S 1/(2e2n) This verifies the hypothesis for and completes our induction.
The next lemma provides bound on the phase transition time.
Lemma (Phase transition, version 2). Assume that
s C1
min
1,
173
for a constant C > Let
C2 max n/2
?2
for a constant C2 > Then for all 2 T, we have
g(w.) S L(w.) S 2e2n
Proof of Lemma 16. The condition on À with C₁ > 2 implies An S min(n, 1/123/2 < 1/2. Then by Lemma 10 we have
((wx) S 10 72 In In? 7 min 1/A))
72 min 1/A}
If the right-hand side is smaller than 1/(4e2n). then there exists S 7 such that L(w,) S 1/(422)). By Lemma 15, we have L(w,) S 1/(2e²n) for all 2 s. We then complete the proof by using G(w) < L(w) from Lemma 4.
To see the right-hand side smaller than 1/(4c2 ), suffices to show that
2 + In 2 (e 22/2))
K1n and 1 In I + 7 217))
72 /
K1
30

---

for sufficiently large constant K1 This first condition is implied by our assumption on À as shown by (6) in the proof of Lemma 15. For the second condition to hold, it suffices have
7/r 2 K2n2² and 72r 2 K2 In + m)²r) for sufficiently large constant K₂ 7²r 2 C2 max n/² for a sufficiently large constant C2.
This completes the proof.
The proof of Theorem follows from the above lemmas.
Proof of Theorem 4. Our assumption on À and 7 satisfies the condition À and n required by
Lemma 16. That condition with C₁ 2 6 implies that À < 1/(3(1 + n²)) s 1/(3n In(e + n)), satisfying the condition on and required by Lemma 12.
The phase transition time bound is by Lemma 16, which further enables Lemma 12 for all 2 т.
Thus have
[(wr+1) min č s (1 >n) (ī(w,) min 2) S <exp(->rt) min 2).
|Wr+ wxll v (1 - An) - wall S exp(->nnt)] - wall.
Moreover, from the proof Lemma 15, we know
ī(w,) - min E [(w,) S 262-1
This completes our proof for the risk convergence. We need to bound ||w -w to complete our proof for the parameter convergence, which follows from the same argument in the proof of Theorem in Appendix A.2.
A.5 Proof of Corollary 5
Proof of Corollary 5. Recall that γ 22/3/21/3 By Theorem 4, GD enters the stable phase in steps, and then attains an E-suboptimal error within an additional
In(1/(ne)
ln(1/s)
yn
(7/)2/3
steps. We can further upper bound the phase transition time by
max { 11, 2)
72
(7/)2/3*
So the total number of steps is t $ (n(1/s)/(7A)213,
B A lower bound
The next lemma provides a hard dataset for which GD cannot large stepsize if it operates in the stable regime. The hard dataset construction is motivated by the lower bound of Wu et al. (2024).
Lemma 17 (A stepsize bound). Consider the dataset
X1 0.,),), X2 (7, -0.5), 91 =1 0 0< 0.1.
Then with Wo Z(wi) Z(wo) implies that v < 20.
Proof of Lemma 17. We have Z(wo) = IIn and Vī(wo) = - 1 (7.00.4 0.4) +
7 W = wo wo -VV[ (1 (1,0.)).
So we have
(722 + 0.2)m
Z(wi) 2 [(wi) 2 = In(1 - exp(-x] w)) = In(1 + exp((1² 0.2)n/2)) 2
2
4
Thus Z(wl) E(wo) implies that 17 < 4lm(2)/(7 + 0.2) - 20, which completes the proof.
31

---

The following lemma establishes upper and lower bounds for the logistic empirical risk. For simplicity.
this lemma stated for the special dataset Lemma 17. However, this lemma can be extended to general datasets satisfying Assumptions and 3 using techniques from Wu et al. (2023).
Lemma 18 (Upper and lower bounds on the logistic empirical risk). Assume that Xn < 1. For the dataset in Lemma 17, we have
Cl s ((w)) S -
C
and wwwlll S C'In(t), for 1565 CXIn(1/X))
where C > depends on ry and 1) but is independent of and X.
Proof of Lemma 18. Denote the trainable parameter as w = (w, w) Then we have wo = wp = and
77
1
W/41 = - -1j)j, +
(7)
1 +0.9a,
1 + e -0.500
0.9
0.5
W1+1 = - (1-1j)m0 +
(8)
+ +0.
+ 67 e
Bounds on Wy. Recall that 7 < 1. From (7), we see that (wy))20 are all nonnegative. Then by direct computation, we can verify that the factor within the big bracket in (8) is positive when Wh S and is negative when Wi 2 2. Then (8) implies the following:
if w. 0,
-(1 7)) S (1 77>) S 0++1 S (1 najE, + m
0 < We 2 if ū > 2,
-1 - (1 - n))a 1) S W+41 & (1 - uy + +
-7 S (1 nyjw, - 77 S कt+1 S (1 nyjw, S (1 - n))
In all cases, we have which implies that |wx] 1n + for every 2 0 by induction.
|w++| S max - mm)) " + 2}.
Let
H(w) / [eeep(-000 (ex9()).9w) + exp(0.50)).
Then for every 2 0, we have H(w.)) S exp(1) + 2) = Hmax-
An upper bound on Using the upper bound on H(w:) and (7), we have
I w. Hy 7w:
W++1 S W, +
2
+0.t0,
2 1001--05am 0.5am
Let lg == min(!: 2 max exp( /2 1}. Since we is increasing, to exists. For every S lo. we have w. S 7- In 1n(2221))))
( max 2). Fort t to. we have
< n [+ee 22n max exp( exp(->wx))
S S + ey2n
2 < 70 e²² 2n / /2 2xxpl 7w1)
2
wi S ee72n
for 2 to.
(t - to) + E
(to
2
Putting these two bounds together, we have for every & 2 O.
< 1 In (2 (I (1).
lower bound on wi. From (7), we have
w++1 2 (1
nd)w; +
Tf 2
(min -w. -0.9000 + min(1, -0.0+0.5001
=(1- -1-ndAjw + m
e yw, (minferu, rur, e u.9.. } min u..u.
2
32

---

(1 nmji; +
17 c
(e-"m(minn [min e 0.9%m min(1, e..5m:)) })
2
2 (1 naju; +
e
2
For t such that
An An (t + 1) In H (t + 1))*
from upper bound Wa, have
21
1
Wye The
2
Then for such t, we have
e 2 clt-nA)wit
oe 1-1
u exp
17'
c yu
1 -
2X Wie
2
2 exp
117 c--w
2 2
1
117 ywr
2 e n +
4
So have
17 11+1). 4
Wt
In
for t x 22n
?
Bounds on logistic empirical risk. Notice that
1 2
e-yw++/or 2 C(w,) 2 In(1 + 2w
This, together with our upper and lower bounds on wy and th leads to the promised bounds.
With the above lemmas, we are ready to prove Theorem 3.
Proof of Theorem 3. From Lemma 17 we know 1) S 20. Then from Lemma 18, we have
- Co t and |w/l S C. In()), for t t CoAlm(1/X))
Cot - ((w,)
where Co > 1 is large factor that only depends r but is independent of and X. Here, we can make Co independent of n as s 20. For every sufficiently small X, we can pick
1
= (BAlN?(1/A) <
CoAln(1/A)"
For this т, have
CoAln(11A)) & [(w,) CaAIn and ||, Co
By Lemma 3 and setting Co large enough, get
min is A(2 + In (12(1)))
(1A1n
That is, have
Σ(w,) min 2> L(w,) min 2 I CoAln
Step complexity for a large E. For 2 0.5CoAln (1/A), we have
Z(w) - min 2 =
[(w)) S min E+ + 5 2F
2Che'
where the second line because of the lower bound on L(w,) for 1. S 1/(CoAIn(1/N) and our choice of A.
33

---

Step complexity for a small E. The case of < (1/A) needs some more effort. Since GD operates in the stable regime, we have
for all 1 [(w)) [(w+) ((w+)& [(w-) A 1 =
That is, (We)127 are all within the level set
W {w: S 2C
For parameters in this level set, we have
||V2[( sup
[[W] +
sup
wEW
< sup L(w) + sup L(w,) X 3CAAIn2(1/M) wEW
weW
where the upper bound is given by Lemma 4 and the definition of W. That is, C 3-sohoth for 3C In (1/A) (1/AA) and X-strongly convex for W. By standard convex optimization theory, have
for all w E W, [(w) - min 2 > 1 V[(w)
23
[(w++1) [(w.) + (VL(w;), W++1 - w.) = -[(w)) n mlVV Moreover, our choice of À implies 17 S 20 < 1/(43). Then the above two inequalities imply that for all 2 T, [(w(+1) min 2 (1-2111) (11))) min Z),
which further implies that
E(wi) min ē 2 (1 11-3)) (ī(w,) min 2)
(1 2n/3) - CoAIn (L/A)
2
2 exp 1n3(1 7)) _ CIADn()1A))
For the right-hand side to be smaller than E < 0.5CmA (1/AA,, we need
In In
1
4n/
C1/An + (0.5CoAl12 (1/AA)
This completes our proof.
C Population risk analysis
We provide a proof for Proposition 6 in Appendix C.I, then calculate the optimal regularization hyperparameter in Appendix C.2.
C.1 Proof of Proposition 6
Proof of Proposition 6. It is clear that under Assumption 2, |w| < B implies E w) < <((0) +B. Applying Srebro al. (2010, Theorem 1) the functional class induced by {w [[w]] B), we have the following: with probability -6
Liest (w) L(w) (B) (B + 1)
for every w such that ||w|| < B,
34

---

where (B) is the Rademacher complexity of the functional class induced by {w: ||w/ S B),
(n, = sup (x4-366) 1
E
sup ||
Σ
o w)
i=1
where o = (a:) are n independent Rademacher random varaibles.
We control the Rademacher complexity by (Shalev-Shwarts and Ben- Ben-David, 2014, Lemma 26.10)
1 Σ
B
(B) <
sup
Eg
sup [i SB T2
sup
Eg
Σ
x
(X
n. (x..I)))
B
sup
E Σ
sup n (x.:9))
B
x
B n2
TI (x.99))
where the first inequality is by the I-Lipschitzness E, the second inequality is by Cauchy-Sehwarr Schwarz inequality, and the last inequality is by Assumption 2.
Putting these together, we have: with probability 1
Ba B² In) (B + (n
for every w such that |||| S B, (res(()) 2 ((w) +
7
Now for given w. consider sequence of balls with radius B, e' and a sequence of probabilities 6, = 55((i+ 1)a. It is clear that >, 6 S 6 and w belongs to B; for i = In(] ||| + 1). Applying the above incquality each B; and os, then applying union bound (motivated by the proof of Theorem 26.14 in (Shalev-Shwartz and Ben-David, 2014)), we get: for every w, with probability
8,
L (onn(w)) (w) S L(w) (|/// + 1) In In²(m)) (l|w|l + 1) In(In(( w| + 1)/5))
n x <((w)+ max(1, (In + Im(1/8))
n
n
This completes the proof.
C.2
Optimal regularization
We compute the optimal regularization hyperparameter À such that minimizes the upper bound in Proposition We assume that 1/72. From Lemma we have
|wil < V + In()
[(wx) s Z(wx) < A(2 (2+hi² (n²(/A))))
24²
Pugging these into Proposition 6, we have
(wo)((x)) S [(w>) + In (n) + In(1/8) [wwll 122
X(1 (11+112(7/NN) In²(n) In( (1 (8) 1 1n2
n
72
Choosing À R 1/n minimizes the right-hand side up to constant factors, where we have
Liest (wx) (In (n) + Im(1/8)) In (n) = 5 -6(111) ,22
22n
Note that the upper bound provided in Proposition is at least 92(1 D(1/n). the choice of À = 1/n leads to nearly unimprovable bound, ignoring logarithmic factors and dependence y.
D The critical stepsize threshold
We first prove Theorem Appendix D.1. We then show that the proposed critical threshold also sharply determines the global convergence of GD in Appendix D.2.
35

---

D.1 Proof of Theorem 7
Denote linearly separable dataset in Assumption as
X = (x1) y: (3i...., Un)
X,,),
Consider the following margin maximization program
min
||
s.t. yix; w 2 1, i =1,1,.. n.
weB
Its Lagrangian dual can be written
1 3 3 s.t. y:B, 2 0, i == ,,...,
max
BER 2
where y: is the dual variable associated with the i-th constraint (see, e.g., Hsu et al., 2021). Let f be the solution the above problem. Let
S == f [n] BB > 0}
be the set of support vectors with nonzero dual variables. Then Assumption 3 says that {x; : E S+} spans the same space as {xi,..., x,
We introduce some additional notation following Wu et al. (2023). By the rotational invariance the problem, with the first vector of the canonical basis. Then we can write the dataset and the parameters as
assume without loss of generality that the maximum éz-margin direction is aligned
x = (x), w (w, w), WA = (W), WA),
where yιaz 2 by Assumption I. Let
S {i (::::::;)) y=;;;,,
be the index set of all support vectors (satisfying the constraint with equality). Then Assumption implies that (X; vsves are strictly nonseparable (Wu et al., 2023, Lemma 3.1). Define
H(w) == 1 Σ exp(- w),
iES
then H(-)) is convex, bounded from below, and with a compact level set. Thus, admits a finite minimizer, which is denoted as w, == arg min H(-).
Wu et al. (2025a, Lemma D.2) provided asymptotic characterization of wa, which is restated as the following lemma.
Lemma 19 (Lemma D.2 in (Wu et al., 2025a)). Under Assumption 3, as X + 0, we have
+ 0o,
WX + W..
Without loss of generality, we assume that {xi..... X, spans the whole space H. Otherwise, we project every quantity into the span of sharp characterization of the Hessian at Wx.
Under this convention, have the following
Lemma 20 (Hessian bounds). Under Assumption 3, as - O, we have
V'L(w>) = A1n(1/A) o Σ x exp(- vix, 1exp--ixx-ee w.).
(H((w) iE8
As a direct consequence, for every À 1/Cu, we have
T AII(I/AAI (L((w)) 2 > CIAIIL/AA
where Co, C1 > 1 depend on the dataset but independent of X.
36

---

Proof of Lemma 20. The first-order optimality condition for w implies that
n
Y4zz WA)
Aue
exp(
7
y1
+ exp(rwx yx WA)
exp + yix; wa)
iES
igs
where y: > for i $ S. Then Lemma 19 implies that
Aeyy exp()w>)
-- 1
Σ
7 7exp(1wx)
yo exp(Twa)
n1
1 exp(ruxx + yAR WA
11
1+ exp(y,2, yi w>)
iES
i&S
7exp(wwx)
+ =(+)
+ exp(pxwx + yiX; W.)
iES
(1))
1
7 eexp(rw>)
n
exp(?rux + yix; wa)
iES
(1 =1= = +1 (())
That is,
Yeu exp(7wx) = (1 (
Notice that ywx is the Lambert W function applied to the right-hand side. By the property of the Lambert W function(see, e.g., Hoorfar and Hassani, 2008, Theorem 2.7), we have
(1=)) exp(rwx)= (1 + o()) In ((1 (1 ((1)) (1 + o(1) +))) H(W..
Aln(1/A)
For the Hessian at Wa. we have
x,X + expe y/x, Wx (1 + exp(uix wA))
V2L(w>)
= (1 + (()) 1
x
exp(y;T,wx + yiX, WA)
x,X,
= + o1))
exp(yW, + yı8, WA)
iES
= (1 = o(1) exp(
-
1
Σ exp(- - x
n
iES
= (1 + o(1)) exp(->wx)
1
Σ
exp(- -1X w.)xxx
n
168
Plugging in the bounds for exp()wx), get
VDL(wx) = (m(A1/)) 1 o(1)
Exxx exp(-v18, w.). )
72H((w.)
iES
which concludes the proof.
We are ready to prove Theorem 7.
Proof of Theorem 7. Lemma 20 implies that for every À S 1/C,, we have
C Aln(1/A) v²ī(w>) = + v2 [(wx) = 3 CAAI(L/AAII
Since v²Σ(-) is continuously differentiable, there exists a neighborhood of wa of radius such that for all w such that ||w- -wxll Sr, 20,
A (1/A v²ï(w) = 20 In1AAI
37

---

The first claim. By classical optimization theory, GD with initialization satisfying ww -wll Sr and stepsize satisfying 7 < 1/(C/Aln(1/A) converges to wa-
The second claim.
Recall that Vv(w>>= = O. For every w such that || - -wwll Sr.
VL(w)= L. V + t)wx)) -wxdd
This, together with the above Hessian bound, implies that
Alm(1/A]llw - [V[()]] s 2CC --wll:
2C1
Consider GD with stepsize 17 (0C7/(Xln(1A))) If GD is within that ball in the t-th step, then we have
Wi+1 wall2 = ||w, ww,-walf - 21/ (3/ We - w.)
wall
+ -w>) +
rAln(1/A)) 1/ wall
Wt wAll 47/2Am((1/))11 wall 2C
N W. - wxll + //CAAl((/A)|]) wwll
2 (1 + 20 ||w, wall..
That is, if GD enters the ball centered at w. with radius r but is different from Wa, then it must exit the ball in finite number of steps. However, will show next that the set of the initializations such that GD exactly hits wa has measure zero.
Let d oo be the dimension of IH,, then we can embed H. into Rd Let
g RR + Rd,
w - w - v/((w
be one step of GD. To conclude, it suffices to show that satisfies the Luzin N property, that is, for all subsets S C Rd, if S has measure Indeed, this ensures that (countably infinite times) iterated preimages of {wx} remain of measure zero. Conveniently, showing g satisfies the Luzin N-1 property is equivalent showing that the Jacobian determinant of is nonzero almost everywhere (Ponomarev, 1987, Theorem 1). We denote the Jacobian determinant of g as
then its preimage g -(S) also has measure
A: R w (Ilet(I-a (I-
Observe that A is composition of degree-d polynomial, of the derivatives of the sigmoid function x + 1/(1+e "), and of linear maps of w. Recall that the sigmoid function analytic on I, meaning that it is everywhere equal to its Taylor expansion a ball of positive radius. We conclude that A also analytic on Rd as a composition of analytic functions. By the identity theorem for analytic functions (Krantz and Parks, 2002, Corollary 1.2.7), we conclude that A is either zero everywhere or that its zeros do not have an accumulation point Rdd We show that the latter holds by discussing the following two cases.
If 1/X, then
A det (1 (1-1)AI
1 4n
x
det
1 4n
x
which is nonzero since we assume (xI,..., spans the whole space.
1 * 1/X, then by Assumption 1, as p > oo, we have
A(pw*) = det (1 (1-r)A)
X,X
+ exp(px, w*)) + exp(- w*)) + +1 11- 1-
That is, for every pair of 17 and X such that y f 1, we can pick a sufficiently large such that A(pw*) = yuu o(1) is nonzero.
In sum, for any choices of 7) and X, cannot be zero everywhere. So the zeros of do not have an accumulation point in ı and thus have measure zero. This concludes the proof.
D
38

---

wx D.2 Global convergence in the 1-dimensional case
In the 1-dimensional case, the objective function can be written as
12
Ō(w)=
In(1 + ==== + w²
72
where 7 S 23 S 1 and there exists an such that =
The next theorem shows that in this 1-dimensional case, GD converges globally with stepsizes below the critical threshold by a constant factor. We note that this a very special situation, where GD with large stepsizes oscillates at most once (see the proof). However, in general finite mite--iimensionl cases, GD with large stepsizes can oscillate many times. Thus, it is unclear the results in this theorem generalize to general sitte-dimensional cases.
Theorem 8 (A I-dimensional anlaysis), Suppose that Assumption holds and that H. is 1-dimensional. Then for every À & 1/Co, S L/(C1Aln(1/A) and wo, GD converges, and after
1 In ( |nool + (=Am((1/A)
t=
steps, [(wr)= min 2 S e. Here, Co. C1 > depend on the dataset and on y, but not on or n7.
Proof of Theorem 8. Let first compute the derivatives of the objective,
['(w)= = - Σ
-
1+eu - + Au, ["(w) - Σ
2 (1+ 2w) czw) + A.
Setting (wx) = 0 and using the same argument as the proof of Lemma 20 shows that
72p
exp(ywx) = (1 + o1)) Aln(1/A)
where p == [(i 2 = >//n. Then for any w 2 w/ - 1, we have
n
[w(ww= = (1 + e w (1 + +
71 i=1
+ ) +X
71
+X
S e (xp(->wwx) +
e (1 + o(1)) 72p
X In(A +
S CAIn(1/A),
for sufficiently small À and C' that depends on and 7. Moreover, observe that ["(w) > for all w.
Observe that Z'(-) is increasing and that (wx) = 0, so we have
< 0
E'(ww)
2 0 w wx.
For any w. by Taylor's theorem, since ('xxxx = 0, there exists a between w and wx such that ['(w) = [" (v)(w wx)-
If Tww 2 wx 2 wx and so this implies
A(w wx) < (w) S CAln(1/A)(uu wx)- Alternatively, if wx 1 S w S wx. implies [w(w)) 2 CAIn(1/A)(w wx). Finally, for any S wy, it implies
E' (w) < X(u wx).
Let to be the first time such that we > wx note that to might be infinite.
39

---

Consider < to. By definition, we have - wy for all t < to. Thus
Wh WA Wt-1 1 wA (wr
2 W w2 - n)(ww-1 -Ux) = - (
This implies that |wr wxl 2 (1 - 1/)M/0 wx for < lo- Hence, for
1 In(1wol + wx),
t 2
either & 2 to wi 1 wx In the latter case
Wy = W4-1 - ni - n/((w=1)) s (wi-1 Wx) (1 Cn)AI(1/A)) 00
provided C1 is chosen sufficiently large. And in this case, wi I wx for subsequent That is, either to is infinite, in which case the step complexity is O(In([[wal wx))s)/(nA)).o or
1
to S 1
In(1wo) + wx).
Consider > lo- By definition we have Wto WA. We show w; 2 wx for all / 2 to by induction. Recall stepsize condition that 1) < 1/(2C) (((AA)) Assume that wy wx, then
1 wx) we 2 (wr wxx) 2 (wr + w') wx-
W1++1 wy -nn ui Cn
So by induction, have Wt w/ for all to Also,
=1 0 S Wh+1 - w = wi - w) - n (w:) S w/ - wx n7((w - wx) = (1 ( - -wx)
That is, [e wxl S (1 17))0 Wio - w> for 2 to. Finally, notice that
wx Wto wh
wx 7)
so 11 - wxl S n O(1/(Al(1/AA)), So we have aw - w> S <1 (1- (0(/AAA(A)))))
fort 2 to.
Combining with the bound on l shows that the step complexity is
o (
In (Wol + (n(1/(Am(11AA)))
|wml (
In
EAIn(1/A)
nd
(EXln(1/A)
This completes our proof.
E Experimental details
The dataset is composed on two datapoints on the regularized logistic regression for = 2-12, a logarithmic range of stepsizes from 2 to 2 and 2 steps. Additional plots are given in Figure 3. Two comments of interest. First, we observe that the dynamics converge for stepsizes up to 25. This is consistent with the local stability threshold given by 2/ //I[[((w)) l|2 R 44.8. Second, we observe in the case of 7 = 2 that even after L stops oscillating for 2 (start of the stable phase), both the regularization and the logistic components continue to evolve nonmonotonically This is connected to the discussion in Section 2.3, where we outline that decrease of Z(w) may cause an increase of L(w), and then GD might leave the stable region.
(7, and x2 (1, for 0.2. We run GD
The code was implemented in JAX (Bradbury et al., 2018) and takes few seconds to run on a consumer laptop. Our code is available https:/ bstps://github. /ggghttt......./// com comm/ieerreMarion//// aarreesttppsie-rggglrireeee-eep
40

---

[(we)
[(w()
2
1 n=2
n 2
25
n = 2
17 2
n=
2
n=
1) 2
2
n=2²
Bayes
29
n = 2
Bayes Risk
2
2
2
2
11
2
2
2
2
2
2
2
2
2
R(we)
L(We)
2
n=
2
2²
2
n=
n=
2
Bayes Risk
2
2
2
2"
2
n=
n=
n 2
n 21
2 -4
n == 2
Bayes Risk
10
2
2
2
Figure 3: Additional plots for the 2-dimensional experiment. Top left: Objective value as a function of training steps. Top right: Objective value as function of training steps for even larger stepsizes. Bottom left: Value of the regularization component function of training steps. Bottom right: Value of the logistic component function of training steps.
41


Reviews:
[{"review_id": "EvPOCYzKqy", "reviewer": "Reviewer_9WKU", "summary": "This manuscript analyzes gradient descent with large constant step sizes for $\\ell_2$-regularized logistic regression on linearly separable data. Building on a series of “edge-of-stability” (EoS) works that studied the unregularized case, the authors show that the same unstable dynamics can accelerate convergence in the strongly convex setting induced by $\\ell_2$ regularization. Their choice of stepsize and regularization scaling is motivated by minimizing the generalization bound presented in Proposition 6.\n\nSpecifically, the manuscript shows that the iteration complexity depends on the scale of the regularization parameter $\\lambda$. When $\\lambda \\leq O(n^{-2})$, gradient descent achieves $O(1/\\sqrt{\\lambda})$ iteration complexity, matching the convergence guarantee of Nesterov’s accelerated gradient method. For general $\\lambda$, they obtain an iteration complexity of $O(\\lambda^{-2/3})$.\n\nIn addition, the authors establish a lower bound on the iteration complexity when the loss function is monotone, showing that this regime requires $\\Omega(1/\\lambda)$ iterations, which demonstrates a separation between non monotonic and monotonic dynamics of GD.", "questions": "**Some discussions:**\n\n* Both learning rates in Theorem 1 and Theorem 4 require a priori knowledge of the margin parameter $\\gamma$. I would expect that if this parameter is not known, the generalization bounds in Table 1 could become suboptimal. Could you discuss how realistic this assumption is in practice? Additionally, it would be helpful to compare the results to adaptive gradient methods (e.g., Zhang et al. \\[2025]) in the scenario where $\\gamma$ is unavailable.\n* The convergence rate predicted by\\ Theorem 1 is worse than that of Theorem 4 in the range $O(n^{-3/2}) \\leq \\lambda \\leq O(n^{-1})$, suggesting there may be room for improving the analysis of Theorem 1. What causes this discrepancy? Clarifying this point could be helpful for readers.\n\n**Suggestions for improving the presentation:**\n\n* It would be helpful to cite the original sources and formally state the results of the baseline methods referenced in Table 1. In its current form, it is not immediately clear that “GD” refers to the results developed in this manuscript.\n* In the last sentence of the conclusion,  [1] could be a good reference to include.\n\n[1] Cohen, J., Damian, A., Talwalkar, A., Kolter, Z., & Lee, J.D. (2024). Understanding Optimization in Deep Learning with Central Flows. ArXiv, abs/2410.24206.", "limitations": "See my points in Weaknesses and Questions part.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n* The manuscript extends an existing line of work to a relevant and practically motivated setting. Unlike the unregularized case, where the minimizer lies at infinity, this setup requires genuinely new technical arguments to handle the $\\ell_2$-regularized objective.\n\n**Weaknesses:**\n* I find the way the contributions are introduced in the abstract somewhat misleading. While it is true that the proposed method can match Nesterov’s accelerated gradient convergence rate, as discussed in Section 6, this happens only in the regime $\\lambda \\leq O(n^{-2})$, which is arguably not the most practically relevant case. In contrast, in the more interesting regime $\\lambda = O(n^{-1})$, the result yields an iteration complexity of $O(\\lambda^{-2/3})$, which remains slower than Nesterov’s method. I would recommend revising the abstract and introduction to clarify this distinction.\n* More broadly, although the overall result is slower than a known baseline (Nesterov’s momentum), the paper still offers an interesting contribution given the emerging relevance of edge-of-stability dynamics in practice.\n* Finally, the presentation and discussion of the results could be improved for clarity; see my questions and comments below.", "was_revised": true, "final_justification": "Technically interesting work although the presentation could be improved. I keep my score unchanged.", "rebuttal": "Thank you for your instructive comments. We will add references for the prior results discussed in Table 1. We address your other questions as follows. \n\n---\n**Q1.** “I find the way the contributions are introduced in the abstract somewhat misleading. While it is true that the proposed method can match Nesterov’s accelerated gradient convergence rate, … this happens only in the regime $\\lambda\\le O(n^{-2})$ … I would recommend revising the abstract and introduction to clarify this distinction.”\n\n**A1.** We respectfully disagree that our abstract is misleading. According to the standard definition of big-O notation, $O(\\sqrt{\\kappa})$ refers to a quantity that grows no faster than $\\sqrt{\\kappa}$ as $\\kappa$ goes to infinity, which corresponds to $\\lambda$ goes to zero, everything else being fixed. As the big-O notation is about asymptotics, we do not think there is a misleading statement in our abstract.\n\nIn the introduction, we give details on the regime where large stepsize GD matches Nesterov’s acceleration (see the “Contributions” paragraph). We will make this part even clearer by including the precise conditions on $\\lambda$. However, we do not think that our abstract or introduction requires significant revision. \n\n---\n**Q2.** “Both learning rates in Theorem 1 and Theorem 4 require a priori knowledge of the margin parameter gamma. I would expect that if this parameter is not known, the generalization bounds in Table 1 could become suboptimal. Could you discuss how realistic this assumption is in practice? Additionally, it would be helpful to compare the results to adaptive gradient methods (e.g., Zhang et al. [2025]) in the scenario where gamma is unavailable.”\n\n**A2.** You’re correct that the optimal stepsize in Theorems 1 and 4 depends on $\\gamma$. However, adaptive GD considered by Zhang et al. [2025] also requires a prior knowledge of $\\gamma$ to set the optimal stopping time $1/\\gamma\\^2$. Therefore our comparison is fair. \n\nIn practice, full knowledge of $\\gamma$ is not necessary. A lower bound on $\\gamma$ (denoted by $\\bar\\gamma$) together with a validation set are sufficient to determine a near-optimal stepsize. This is because we can set up a multiplicative grid of candidate $\\gamma$’s ranging from $\\bar\\gamma$ to $1$, run GD with the corresponding stepsizes, and choose the optimal run according to its performance on a validation set. Since there are $\\Theta(\\ln(1/\\bar \\gamma))$ many candidate $\\gamma$’s, this procedure adds at most a logarithmic factor in the total step complexity and in the risk bound.\n\n---\n**Q3.** “The convergence rate predicted by Theorem 1 is worse than that of Theorem  4 in the range $O(n^{-3/2}) \\le \\lambda \\le O(n^{-1})$, suggesting there may be room for improving the analysis of Theorem 1. What causes this discrepancy?...”\n\n**A3.** This discrepancy exists because we use different approaches to control the stable phase of GD for small and large $\\lambda$’s. We refer the reviewer to Lines 249-259 in Section 2.3 for a detailed discussion. We agree that there is room to improve our current analysis, which is a challenging technical problem and would require significant technical innovations upon our current approaches. We will comment on this as an important open problem in the revision. \n\n---\n**Q4.** “In the last sentence of the conclusion, [1] could be a good reference to include...”\n\n**A4.** We are happy to cite and discuss [1] in our “Related work” section. However, we don’t see a clear connection between the last sentence of our conclusion, which suggests developing mathematical tools to prove the convergence of GD with large stepsizes, and [1], which proposed central flow as a qualitative approximation of large stepsize GD. Due to the existence of a non-vanishing approximation error, central flow does not seem to be directly helpful for our question of rigorously proving the convergence of large stepsize GD. We appreciate further elaboration."}, {"review_id": "XBQVuZ3EFy", "reviewer": "Reviewer_q9wR", "summary": "In the paper (Cohen et al., 2020), a phenomenon ``edge of stability’’ (EoS) regime is\ninvestigated under the training of neural networks (NN). The EoS indicates that the NN\ntraining can still converge if using a relatively large learning rate.\n\nAnother paper (Wu et al., 2024) utilizes a non-regularized logistic regression to investigate the\nEoS regime. The current paper expand the results to regularized logistic regression\nproblems.", "questions": "See \"weaknesses\"", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "#### Strengths\n\n- This paper is written clearly.\n- This paper utilizes a simpler problem (logistic regression) to explain the Eos regime issue.\n\n#### Weaknesses\n\n- A concern is that this paper may have only theoretical values. For logistic regression, gradient descent is not an effective method. People have shown that quasi Newton (e.g., LBFGS), truncated Newton (via conjugat gradient methods) or even coordiate descent methods are better choices in different scenarios. Moreover, the paper concerns about linearly separable data, a situation not common in practice.\n\n- The proofs in the appendices skip many details. \n  Thus, it is hard to verify the correctness of the proofs.\n  For example,\n  a) In line 818, it seems that the right hand side lacks the term $$ -4 \\eta \\nabla L(w_t)^T w_t. $$\n  b) In line 828, the left hand side is equal to $$ \\eta^2 [ \\nabla L (w_t)^T w^* + \\| \\nabla L(w_t) \\|^2 ], $$\n     but why this term is less than zero?\n  c) In line 864, why do we have the second inequality\n     $$ \\frac{e}{n} \\sum_{i=1}^{n} \\left( \\frac{1}{1+exp(y_i x_{i}^{T} w_t )} \\right)^{1-\\alpha \\lambda \\eta} \\leq e \\left( \\frac{1}{n} \\sum_{i=1}^{n} \\frac{1}{1+exp(y_i x_{i}^{T} w_t)} \\right)^{1-\\alpha \\lambda \\eta} ? $$\n  \n- The paper does not contain any experiment to verify their proofs.", "was_revised": true, "final_justification": "A solid theoretical contribution though I have some concerns about the practical impact.", "rebuttal": "We appreciate your detailed comments. We address your concerns below. \n\n---\n**Q1.** “A concern is that this paper may have only theoretical values. For logistic regression, gradient descent is not an effective method. People have shown that quasi Newton (e.g., LBFGS), truncated Newton (via conjugat gradient methods) or even coordiate descent methods are better choices in different scenarios. Moreover, the paper concerns about linearly separable data, a situation not common in practice.”\n\n**A1.** We respectfully disagree with the assertion that “this paper may have only theoretical values”. Note that large stepsizes are the typical choice for using GD in machine learning, especially deep learning, as discussed in Lines 72-80. Our paper, by rigorously characterizing the benefits of large stepsizes in a natural setting, provides important insights into understanding why large stepsizes work so well in practice. \n\nWe don’t think linearly separable data is restrictive, as logistic regression with linearly separable data is a standard setting in machine learning literature as discussed in Lines 99-113. Additionally, our results can be extended to neural networks in the lazy regime (see Line 362), in which the linear separability assumption is relaxed to separability in RKHS given by the neural tangent kernel, which holds for any finite number of data in general position. \n\nFinally, we emphasize that our goal is to understand the benefits of large stepsizes (over smaller ones) for GD. Although we use regularized logistic regression as a testbed, studying the fastest method for this problem is orthogonal to the topic of this paper. \n\n---\n**Q2.** “The proofs in the appendices skip many details. Thus, it is hard to verify the correctness of the proofs…”\n\n**A2.** We’re fully confident with the correctness of our proof. We address each of your concerns below. Should the reviewer have any further questions, we’re happy to provide clarifications. \n\n* a) There is no missing term in the display below Line 818. Note that we have $u := u_1 + u_2 + u_3$, which implies that \n$$ 2 \\eta \\langle \\nabla L(w_t), u - w_t \\rangle = 2 \\eta \\langle \\nabla L(w_t), u_1 - w_t \\rangle + 2 \\eta \\langle \\nabla L(w_t), u_2 \\rangle + 2 \\eta \\langle \\nabla L(w_t), u_3  \\rangle$$\nThe term with $ u_2$ cancels the gradient squared term, while the terms with $ u_1$ and $u_3$ are left.\n\n* b) The inequality below Line 828 is due to the same argument as the display below Line 817. We will clarify this in the revision. \n\n* c) The second step in the display below Line 864 is by Jensen’s inequality and the concavity of $x \\mapsto x^{1 - \\alpha \\lambda \\eta}$ as mentioned in Line 863.\n\n\n---\n**Q3.** “The paper does not contain any experiment to verify their proofs.”\n\n**A3.** Our paper is of theoretical nature. All necessary assumptions and proofs are included for verifying the correctness of our theorems. It does not seem necessary to further verify our theorems with experiments. With that said, we are happy to include simulations in the revision to better illustrate our theory."}, {"review_id": "Cck6dlg3LF", "reviewer": "Reviewer_ieJz", "summary": "This paper shows that gradient descent (GD) with a properly chosen large constant step size achieves fast convergence for $\\ell_2$-regularized logistic regression when the data is linearly separable. This thereby extends our understanding of the optimization benefit of GD operating at the edge of stability regime. In particular, this work builds on a recent result by Wu et al. (2024), which showed that a large constant step size can accelerate GD in the unregularized logistic regression setting. Although the two results appear related, the proof techniques developed in the unregularized setting do not directly extend to the regularized case considered here, due to the presence of a finite minimizer. \n\nFor a small regularization parameter $\\lambda = O(1/n^2)$, Theorem 1 establishes that large step GD achieves a convergence rate of $O(\\ln(1/\\epsilon)/\\sqrt{\\lambda})$ matching that of Nesterov's momentum. Moreover, the analysis shows that GD enters a stable phase with linear convergence after a finite number of steps. While the acceleration is theoretically appealing, the authors correctly note that such a small regularization level may be inadequate in the presence of statistical noise. \n\nTo address this limitation, this paper further investigates the regime of larger regularization and statistical uncertainty. When $\\lambda=O(1)$ and the step size is set to $\\eta=O(1/\\lambda^{1/3})$, GD achieves the complexity of $O\\(\\ln(1/\\epsilon)/\\lambda^{2/3})$, which improves over small-step GD but remains slower than Nesterov's momentum. In Section 3, the authors further investigate the benefits of large step under statistical uncertainty. Based on the best-known population risk upper bound in Proposition 6, the authors argue that the largest reduction in population risk is obtained when choosing $\\lambda=1/n$ and $\\eta=(\\gamma^2n)^{1/3}$. However, under this setup, the rate does not match the fast rate provided by Nesterov's momentum.\n\nFinally, this paper completes its analysis by establishing that $1/\\sqrt{\\lambda}$ is the critical threshold between (local) convergence and divergence of large-step GD, under a mild support vectors condition.", "questions": "- Page 2 line 64: Is there a reference that supports this statement? If this claim is supported by this paper, I think it would be helpful to add a brief explanation or clarification at this point.\n- Page 3 line 117: Why is there a gap in the large step size analysis between the separable and non-separable cases? Is it due to logistic regression being strictly convex but not strongly convex under strictly non-separable data? What would happen if one adds regularization in the strictly non-separable case?\n- Page 4 line 151: Could you provide some intuition behind the transition in behavior at the step size $1/\\sqrt{\\lambda}$?\n- Page 8 Table 1: Do the theoretical comparisons in Table 1 align with the empirical observations?\n- Page 9 line 365: Could you clarify the last two future directions? They were somewhat vague and difficult to interpret.\n\n- Minor comments: Unlike the main texts, the conclusion does not explicitly mention the requirement of small regularization for matching the rate of Nesterov's momentum. I suggest including this. In addition, when referring to (Cai et al., 2024), something other than linearly separable data should be mentioned.", "limitations": "The paper clearly states its limitations at the end of each section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- S1: As noted in Section 2.3, while the main claims resemble those of Wu et al. (2024), the proof technique developed in this paper for the regularized setting is novel and nontrivial.\n- S2: Despite the limited benefit of large step size under strong regularization and statistical uncertainty, this paper offers a comprehensive theoretical analysis of large step GD for regularized logistic regression.\n- S3: This paper is clearly written and well-structured. The main results appear technically sound, although I have not carefully checked the proofs.\n\n- W1: Related to S2, the rate matching the optimal rate of Nesterov's momentum is achieved only in the small regularization regime, which limits the practical relevance of the result under statistical uncertainty.", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for supporting our submission! Please find our answers to your comments below.\n\n---\n**Q1.** “Related to S2, the rate matching the optimal rate of Nesterov's momentum is achieved only in the small regularization regime, which limits the practical relevance of the result under statistical uncertainty.”\n\n**A1.** We emphasize that for a large regularization, we have also shown an improvement of using large stepsizes over small ones for GD. Although the improvement does not match Nesterov’s acceleration, we don’t feel this limits the practical relevance of our theory. In fact, it is unclear to us if large stepsizes GD can also match Nesterov’s acceleration for a large regularization. We will comment on this as a concrete open problem in the revision. \n\n---\n**Q2.** “Page 2 line 64: Is there a reference that supports this statement? If this claim is supported by this paper, I think it would be helpful to add a brief explanation or clarification at this point.”\n\n**A2.** This is an informal statement for providing intuition for categorizing convergent GD runs into the stable regime and the EoS regime. This statement holds under weak regularity assumptions, e.g., when the objective is second-order continuously differentiable and strongly convex, and the stepsize satisfies a minimum condition for local stability, $\\\\eta < 2/ \\\\\\| \\\\nabla\\^2 L(\\\\hat w) \\\\\\|$, where $\\\\hat w$ is the global minimizer. In this case, there exists a neighbor of $\\\\hat w$ such that GD is stable within this neighborhood. As any convergent GD run has to enter this neighbor, it has to enter a stable phase in finite steps. We will clarify this in the revision.\n\n---\n**Q3.** “Page 3 line 117: Why is there a gap in the large step size analysis between the separable and non-separable cases? Is it due to logistic regression being strictly convex but not strongly convex under strictly non-separable data? What would happen if one adds regularization in the strictly non-separable case?”\n\n**A3.** Firstly, we’d like to clarify that for both separable data and strictly non-separable data, logistic regression is strictly convex but non-strongly-convex, as the domain is unbounded. \n\nSecondly, our results are not directly comparable to those of Meng et al. (2024). Indeed, their counter example is for stepsizes in the order of $1/\\\\\\|\\\\nabla\\^2 L(\\\\hat w)\\\\\\|$, where $\\hat w$ is the global minimizer. This corresponds to $\\eta = \\Theta(1 / (\\lambda \\ln(1/\\lambda) ) )$ in our settings. In comparison, our theory requires $\\eta = O(1/\\sqrt{\\lambda})$, which is much smaller. \n\nFinally, it is unclear to us if GD always converges with $\\eta = \\Theta(1 / (\\lambda \\ln(1/\\lambda) ) )$ even under separable data. We have commented on this as Conjecture 1 in Lines 350-352. \n\n---\n**Q4.** “Page 4 line 151: Could you provide some intuition behind the transition in behavior at the step size 1/sqrt(lambda) ?”\n\n**A4.** The stepsize $\\eta = \\Theta(1/\\sqrt{\\lambda})$ is the largest one for which our proof is valid. However, preliminary experiments suggest that convergence may still occur for larger stepsizes, and characterizing this behavior is an interesting open problem (as we emphasize at the end of Section 4). Technically, our proof fails at Lemma 13. While pinpointing the exact place of failure requires getting into somewhat technical computations, the critical scaling $\\eta = \\Theta(1/\\sqrt{\\lambda})$ can be seen by inspecting Line 895: the squared gradient norm inside the parenthesis is less than 1, while $\\\\\\|w\\_t\\\\\\|\\^2$ can be of order $\\eta^2$. Then, if $\\eta$ exceeds the critical scaling, the expression in the parentheses becomes strictly negative, rendering the inequality uninformative.\n\n---\n**Q5.** “Page 8 Table 1: Do the theoretical comparisons in Table 1 align with the empirical observations?”\n\n**A5.** As discussed in Lines 315-319, the comparison in Table 1 relies on the best-known margin-based (worst-case) population risk bound in our setting. While we believe this bound is fairly tight for moderately large $n$, this bound could be loose for exponentially large $n$ (in terms of dimension and/or margin), as the population distribution is realizable (i.e., Bayes risk is zero). Furthermore, the bound might be also loose for average-case problems encountered in practice. We acknowledge this limitation of Table 1. We will conduct experiments to empirically compare the generalization of each method, and include our findings in the revision. \n\n---\n**Q6.** “Page 9 line 365: Could you clarify the last two future directions? They were somewhat vague and difficult to interpret.”\n\n**A6.** In the second to the last future direction, we ask if there exists a natural statistical learning setting where large stepsizes lead to smaller population risk than small stepsizes. Note that we only show large stepsizes attain the same population risk faster than small stepsizes, but we haven’t shown large stepsizes attain a smaller population risk.  \n\nIn the last future direction, we ask if there is a generic approach to prove the convergence of large stepsize GD, without relying on the descent lemma. Note that our analysis is specific to logistic regression with linearly separable data (while it can be relaxed in certain ways), and fails to hold for a more general class of optimization problems. \n\n---\n**Q7.** “Minor comments: Unlike the main texts, the conclusion does not explicitly mention the requirement of small regularization for matching the rate of Nesterov's momentum. I suggest including this. In addition, when referring to (Cai et al., 2024), something other than linearly separable data should be mentioned.”\n\n**A7.** Thank you for your suggestions. We will revise the conclusion to explicitly mention that we only match Nesterov’s acceleration when the regularization is small, and that (Cai et al., 2024) required linearly separable data and two-layer networks with fixed outer weights and strictly increasing activations such as leaky-ReLU."}, {"review_id": "tqd1vGJoj8", "reviewer": "Reviewer_Lvra", "summary": "This paper studies gradient descent (GD) for $\\ell_2$-regularized logistic regression with linearly separable data under a large constant stepsize. Considering different regimes of the regularization strength, this paper shows various accelerating behavior induced by the large stepsize, particularly about the jump between stable phase (where the loss decreases monotonically) and edge of stability (EoS) phase (the loss does not decrease monotonically) where phase transition points are indentified. Moreover, the critical threshold on the convergent stepsizes is also discussed.", "questions": "1. Can you discuss more on the assumptions? Does similar result hold if the separability condition is not satisfied?\n\n2. What is the explicit dependence of the constants $C_1,C_2,C_3$ in the theorems 1, 4 and 7 on the dataset? How large will they be?\n\n3. Can the result and techniques be extended to other models such as generalized linear regression?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n* This paper is well written and clear to read.\n* This paper studies the interplay of large stepsize and EoS for $\\ell_2$-regularized logistic regression, which is novel.\nThe result on the different regimes of stepsizes is very interesting and provide more understandings for the study of EoS.\n* The theorems in this paper are clear and seem to be well supported by the proofs (though I haven't checked all the details).\n\n\n### Weaknesses\n\n* Numerical experiments can be included to further justify the theoretical results. Demonstrating a training path can provide readers with more intuitions.\n* Filling out the missing parts of the full picture of the theoretical results as shown in Figure 1 would make the theory more complete.", "was_revised": true, "final_justification": "This paper is technically solid and provides novel and interesting theoretical results.", "rebuttal": "Thank you for supporting our paper! We address your comments as follows. \n\n---\n**Q1.** “Numerical experiments can be included to further justify the theoretical results. Demonstrating a training path can provide readers with more intuitions.”\n\n**A1.** As our results are of theoretical nature, we don’t think experiments are necessary for justifying our results. With that being said, we agree with the reviewer that the suggested simulations are helpful for providing intuitions. We will add simulations, including visualizations of a training path, in the revision. \n\n---\n**Q2.** “Filling out the missing parts of the full picture of the theoretical results as shown in Figure 1 would make the theory more complete.”\n\n**A2.** We agree that there are open problems to be solved as commented throughout the paper. Yet, our current results, which show the benefits of large stepsizes for GD for regularized logistic regression, are already significant. \n\n---\n**Q3.** “Can you discuss more on the assumptions? Does similar result hold if the separability condition is not satisfied?”\n\n**A3.** As mentioned in Lines 99-109, linear separability is a standard assumption in the theoretical literature, so it is not restrictive. \n\nMoreover, our results can be extended to certain cases with non-linearly-separable data. For example, our results can be extended to wide neural networks in the lazy regime for any finite number data in the general position (see the discussion in Lines 361-362). Note that any finite number data in the general position is guaranteed to be separable in the RKHS given by the neural tangent kernel, even if they are not linearly separable. \n\nFor linear predictors with general non-linearly-separable dataset, it is unclear if our results hold. We will comment on this as a future work in the revision. \n\n---\n**Q4.** “What is the explicit dependence of the constants $C_1, C_2, C_3$  in the theorems 1, 4 and 7 on the dataset? How large will they be?”\n\n**A4.** In Theorems 1 and 4, the constants are all numerical and do not depend on anything including the dataset. In Theorem 7, the quantities $C_1$ and $C_2$ depend on the dataset through the margin $\\gamma$ and the second derivative of the loss at the minimizer (detailed in Lemma 20 in Appendix D.1).\n\n---\n**Q5.** “Can the result and techniques be extended to other models such as generalized linear regression?”\n\n**A5.** Part of our results and analysis can be extended to certain generalized linear models. For example, for linear predictors with general loss functions given by Assumption 3 in (Wu et al. 2024). We have commented on this and some other possible extensions in Lines 360-363."}]

Author rebuttal:

Meta-review: The paper studies gradient descent with large constant stepsizes for regularized logistic regression with linearly separable data. It shows that acceleration is possible in the small regularization regime, and provides detailed theoretical analysis of the edge-of-stability dynamics.

The proofs develop new arguments not present in earlier unregularized analyses. The work deepens our understanding of large-stepsize dynamics and is of relevance to NeurIPS audience. 

The main concerns raised are about practical relevance and presentation. The strongest acceleration result holds under small regularization, which may be less realistic in noisy settings. Several reviewers asked for simple experiments or simulations to illustrate the dynamics. These smaller issues can be addressed when preparing camera ready version.
Decision: Accept (poster)