Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Authors: Ruiqi Zhang
Jingfeng Wu
Peter Bartlett
Venue: ICML 2025 poster (2025)
Keywords: gradient descent
logistic regression
convergence
optimization
Primary area: deep_learning->theory
TL;DR: We prove that gradient descent can converge arbitrarily fast for Logistic Regression on linearly separable data with large and adaptive stepsizes.

Abstract: We analyze the convergence of gradient descent (GD) with large, adaptive stepsizes for logistic regression on linearly separable data. The stepsize adapts to the current risk, scaled by a fixed base stepsize \eta. We prove that once the number of iterates t surpasses a margin-dependent threshold, the averaged GD iterate achieves a risk upper bound of \exp(-\Theta(\eta t)), where \eta can be chosen arbitrarily large. This implies that GD attains \emph{arbitrarily fast} convergence rates via large stepsizes, although the risk evolution might not be monotonic. In contrast, prior adaptive stepsize GD analyses require a monotonic risk decrease, limiting their rates to \exp(-\Theta(t)). We further establish a margin-dependent lower bound on the iteration complexity for any first-order method to attain a small risk, justifying the necessity of the burn-in phase in our analysis. Our results generalize to a broad class of loss functions and two-layer networks under additional assumptions.

Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Ruiqi Zhang' Jingfeng Wu
Peter L. Bartlett
Abstract
Classical analyses of GD require the stepsizes to be suffi- ciently small so that the risk decreases monotonically (Nes- terov, 2018). This is often referred to as the descent lemma. Specifically, by the definition of GD and the midpoint theo- rem, there exists v in between w, and W1+1 such that
We analyze the convergence of gradient descent (GD) with large, adaptive stepsizes for logistic regression on linearly separable data. The step- size adapts to the current risk, scaled by fixed base stepsize 1). We prove that once the number of iterates / surpasses a margin-depenndent thresh- old, the averaged GD iterate achieves risk upper bound emp)-)(n()), where 1/ can be chosen arbitrarily large. This implies that GD attains arbitrarily fast convergence rates via large step- sizes, although the risk evolution might not be monotonic. In contrast, prior adaptive stepsize GD analyses require monotonic risk decrease, limiting their rates to exp(-0(t)). We further establish a margin-dependent lower bound on the iteration complexity for any first-order method attain a small risk. justifyyng the necessity of the burn-in phase in our analysis. Our results general- ize to a broad class of loss functions and two-layer networks under additional assumptions.
((w(+1) [(w:) me V
22 + VL(W.) T VVC(v)VL((.)) 2
Thus a small stepsize Th < 2/ guarantees the descent lemma. In this regime, a large volume of theory has been developed to show the convergence of GD variety of settings (see Lan, 2020, for example). We call this the stable regime.
However, in practice, deep learning models trained by GD often converge in the long run while suffering from lo- cally oscillatory risk (Wu et al., 2018; Xing et al., 2018; Lewkowycz et al., 2020; Cohen et al., 2021). This oscil- lation occurs when the stepsizes for GD are too large and the descent lemma is violated. This unstable convergence phenomenon is referred to by Cohen et al. (2021) as the edge of stability (EoS). Moreover, to obtain a reasonable op- timization and generalization performance in deep learning practice, GD usually needs to operate in the EoS regime, instead of remaining in the stable regime (Wu et al., 2018; Cohen et al., 2021).
1. Introduction
Gradient descent (GD) and its variants are popular class of optimization methods in modern machine learning and deep learning. In this paper, we study the convergence of GD with adaptive stepsizes given by
Wo- = 0, W = w. 1/ VLW;;) 1 120.
(GD)
Recently, an interesting line of theoretical works showed the benefits of EoS for accelerating the convergence of GD (see for examples Altschuler & Parrilo, 2024a; Wu et al., 2024, other related works will be discussed later in Section 6). Specifically, Altschuler & Parrilo (2024a) proposed a step- size scheduler for GD, which GD occasionally violates the descent lemma but achieves a faster convergence rate for convex and smooth problems. The work by Wu al. (2024) focused GD with constant stepsize for logistic regres- sion with linearly separable data. They showed that large constant stepsize leads to EoS but also a faster convergence. Note that the stepsizes considered in (Altschuler & Parrilo, 2024a; Wu et al., 2024) are oblivious, which are determined before the GD run and do not adapt to the evolving risk.
where C(-) is the loss objective to be minimized, w, Rd is the trainable parameters, and 1/+ > 0 is the stepsize at the t-th step. In particular, we allow 7) to be a function of the current risk L(w.). Setting the initialization to zero does not cause the loss of generality.
Universitt of California, Berkeley, USA 'Google DeepMind, USA. Correspondence to: Ruigi Zhang <ryzhang @ berkeley.edu>> This work is extended ht pttps:// arxiv.ore / abs /504. 04105, and Licong Lin was included as a co-author.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Exponential (avg iterate)
Logistic lavg iterate)
Polynomial (avg iterate.
10a
10
10-1
10"7-
10"
Training LoGa
10
Traniing Loss
10-1
10"11
10
10-41
10
27
10
10-30
0
5
10
15
20
23
30
5
10
15
20
30
10
20
30
lteration (1)
Ieeraion (1)
Iteration (O)
IRm0.1 1Rm0.5 IR=1.5 1Rm3.0
1Be5..0
1R=10.00 1R=25.0 10=50.00
11R-100.0
Figure 1. Simulation Results. We run gradient descent with stepsize scheduler (2) on exponential loss (left). logistic loss (middle), and polynomial loss (right) with linearly separable data. Here, we set n 100, 7 = 0.25, = 5. We w" IR ||w 1Il = and sample E I independently and uniformly from the unit sphere and accept it if (x,, w") 2 Otherwise, reject the data point. We keep sampling until we have n = 100 data. The y y-axis in log scale for figures.
Our results. This work complements the prior theory by considering the convergence of GD with adaptive stepsizes the EoS regime. Specifically, we consider logistic regres- sion with linearly separable data, that is,
Benefits of large and adaptive stepsizes. When v is small, GD stays in the stable regime and achieves a conver- gence rate of ex)())(t)), where is the number of steps (Ji & Telgarsky, 2021) (see also Proposition 2.1 in Section 2). However, we show GD can achieve an arbitrarily fast con- vergence rate by entering the EoS regime. Specifically, we show that for every to, the average of the first t GD iterates achieves risk upper bound of exp(-O(ntt) for every 1/. Here, to function of the data margin but is independent ry. Therefore, one can use an arbitrarily large r obtain an arbitrarily small risk when 2 to. By doing so, however, GD) may enter the EoS regime.
n Ee Ey w), E flesps llog)- n
((w):
Here, the loss function can be the exponential loss or the logistic loss,
(exp(2) == (xx())==x(((=)) (10 = In(1 exp(-2)),
and the dataset (x,, 31) is linearly separable, formalized by the following assumption.
Lower bounds. We then establish two lower bounds to complement our upper bounds. First, we provide an ex- ample of logistic regression with linearly separable data, where adaptive stepsize GD suffers from a risk lower bound of (eex(--t) if it does not enter the EoS regime. This, together with our upper bounds, demonstrates the benefits of EoS for accelerating the convergence of adaptive step- size GD. Furthermore, which every first-order gradient-based method must run for margin-depennee number of steps to attain small risk. This demonstrates the margin-dependent number of burn-in steps in our upper bound cannot be avoided in general.
Assumption 1.1 (Linear separability). Assume that dataset (x;; us) satisfies the following.
A. Assume, without loss of generality, that ||x:|12 S 1 and y: for .7.
construct hard example, in
B. Assume there exists y > 0 and unit vector w such that y:x, w" 2 for i = I.
In this problem, it is known that the curvature becomes flatter as the risk decays. To compensate for this effect, we consider an adaptive stepsize scheduler (Ji & Telgarsky, 2021: Nacson et al., 2019; Wang al., 2023a),
General losses and two-layer networks. We also extend our results to a general class loss functions, including polynomial loss (Ji & Telgarsky, 2021) and probit negative log-likelihood (Neal, 1997; Chib & Greenberg, 1998; Albert & Chib, 1993; Liu, 2004). Additionally, we show the same results hold for a two-layer network with leaky ReLU acti- vation (Brutzkus et al., 2018). Notably, our analysis can be easily adapted other common leaky activation functions
Th = (- o L(w,) = ///////l [(w:),
where > is fixed base stepsize. We make the following significant contributions.
2

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
(Cai et al., 2024).
Prior analyses. All the prior analyses for this adaptive stepsize GD relies on the descent lemma (Nacson al., 2019; Ji & Telgarsky, 2021), hence they require the base stepsize > O be small so that the risk decreases monotoni- cally. The following proposition, a consequence of the main result in (Ji & Telgarsky, 2021), characterizes the best rate they can obtain this regime.
Notation. We use lowercase bold letters to denote vectors and I1-112 to denote the Euclidean & norm for vectors. For positive integer n, we write [n] == (1, 2.......) n). Let Og denote the zero vector in IR. We write f(t) = (g(()) to mean that there exists a universal constant c > such that [t)] I c- lg(( for sufficiently large Likewise, f(t) = (g(()) means there exists a universal constant c, 02 > 0 and lo such that Ci [g(()) S [S(()) S c [l(()) for 2 to We also use O and θ to suppress constant and polylogarithnic factors. We let C' or denote universal constants, whose exact values may vary from line to line. s-an(-) denotes the subspace spaned by a set of vectors. For a E _d and B C R2, the Minkowski sum is defined as a + B = [a bb:
Proposition 2.1 (Consequences of (Ji & Telgarsky, 2021)).
Consider (GD) with adaptive stepsizes (2) for logistic re- gression (I), Suppose that Assumption 1.1 holds. Then & is 3-smooth with respect to -oorrm where 5 = 1 for exponential loss and 3 S n for logistic loss. Moreover, for every n S 1/8, the risk C (we) decreases monotonically and satisfies
L S exp (-7Pmp)
where C >> 1 is universal constant.
2. Logistic Regression
An improved convergence rate. Our first main result is an improved analysis of GD with adaptive stepsizes for logistic regression with linearly separable data, in which we allow GD to enter the EoS regime using large stepsize. This is presented as the following theorem.
In this section, we present our improved analysis for GD with large and adaptive stepsizes for logistic regression with linearly separable data.
Adaptive stepsizes. We first explain the benefits of using adaptive stepsizes over a constant stepsize. Note that for logistic regression, the local sharpness [[)[l is con- trolled by the risk [(w). Therefore as the risk decreases to zero (note that the dataset is separable), the local curvature becomes flatter. As a consequence, GD with a constant stepsize is less as less effective in the later stage. This obser- vation has been exploited to show large stepsize GD enters a stable phase by Wu et al. (2024).
Theorem 2.2 (An improved convergence rate). Suppose that Assumption 1.1 holds. Consider (GD) with adaptive step- sizes (2) for logistic regression (1). Let W. := 1 Et= We be the averaged iterates. Then every 17 > 0, we have
exp
4 2nt nt +
4,2t
f = lexps
L (wi) S
exp
4 2 +
11
f= R1og
72t
This issue can be mitigated by using the following adaptive stepsizes,
In particular, let the number of burn-in steps be
"
[v2/72 l leeps
t= lesps
((we) 17 (rexp((((w)) Th 1 (-t-1)oo((w))
to = 2V2/122 E = llog:
t= blog.
exp (C((w))
(2) then for every t 2 tu, we have
1 (-5(²m))
When the risk L(w) becomes smaller, the stepsize becomes large to compensate for the flattened curvature. In this way, GD with adaptive stepsizes achieves a fast convergence rate exp( exp(-O(t)) compared that of GD with a constant step- size, ((1/t), when both are in the stable regime (Nacson et al., 2019; Ji & Telgarsky, 2021; Wu et al., 2024).
[(w)) S exp
exx
where the base stepsize can be arbitrarily large.
Our Theorem 2.2 improves Proposition 2.1 by allowing the base stepsize 1j to be arbitrarily large, where GD may not stay in the stable regime and is allowed to enter the EoS regime. More surprisingly, Theorem 2.2 implies that as soon as f 2 to = O(1/r2) we have
Alternatively, (GD) with adaptive stepsizes (2) can be equiv- alently viewed as
Wr+1 w. - voWws)
(3)
lim L(W,) 0. +
that is, a constant-stepsize GD for a modified loss @(w).
This viewpoint is from (Ji & Telgarsky, 2021), where they utilized this idea to establish a primal-dual analysis of GD, obtaining an improved margin maximization rate.
This means GD with adaptive and large stepsizes converges arbitrarily fast for logistic regression with linearly separable data.
3

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
In sharp contrast our result, for the same problem, GD with a constant stepsize can only achieve (1) rate even when operating in the EoS regime (Wu et al., 2024), and GD with adaptive stepsizes can only achieve a exp(-O(1) rate when operating in the stable regime (see Proposition 2.1). Therefore, the improved rate fun- damentally arises from combining both large and adaptive stepsizes.
plies that
1
[uj + U2 u2l1
Σ
((w))
- -7
2nyl
k=
- 4 2 Pn
1
11
t= leeps
4,2t
4 2 nt
91
== liog-
7Pt
It is also worth pointing that GD with adaptive stepsizes can converge with an arbitrarily large based stepsize even under the exponential loss. In comparison, the work by Wu et al. (2023) provided an example where GD with a large constant stepsize cannot converge under the exponential loss, even when the dataset is linearly separable.
We complete the proof by applying the convexity of ((.) and using that L(-) = ((-o(.)).
3. Lower Bounds
In this section, we establish two lower bounds on the con- vergence rate of GD for logistic regression with linearly separable data.
In the remaining part of this section, we provide the proof of Theorem 2.2.
A lower bound for GD in the stable regime. Our next theorem provides lower bound on the convergence rate of adaptive stepsize GD that stays in the stable regime.
Proof of Theorem 2.2. The proof of Theorem 5.2 uses the convexity of Φ(-) and split optimization technique de- veloped by Wu et al. (2024). Consider comparator u U1 + Ug E Rd, then by (3) we have
Theorem 3.1 (A lower bound for GD in the stable regime). Consider (GD) with udaptive stepsizes (2) for logistic re- gression (1) with the following dataset
|wr+ - -u11
W: u1/2 2n (Vo(w;), wi) + n7 (
X1 = -1 (1.v1e -2), x2 =
|W, ull2 + 2n (V (w;,, u1 we)
where 0 < < 0.1. It is clear that this dataset satisfies Assumption 1.1. If the base stepsize n is such that (GD) induces a monotonically decreasing risk, then we have
+ 17 2 V d6 w.), u2) + V
< W: 1| + 21 (V w.), un ww)
(4)
((w.),f(w) 2 exp(-ct), t 221,
< |W:- 1| 2n (Ø(u:) <(w:)),
(5)
where e. 0 is a quantity depending on ry but is independent of t and n.
where (4) is by properly setting u2 according to the follow- ing Lemma 2.3 and (5) is from the convexity of o(.) (see Theorem 5.2 in (Ji & Telgarsky, 2021), also Lemma G.1 in Appendix G).
Theorem 3.1 suggests that for adaptive stepsize GD that stays in the stable phase, the exp(-O(L)) rate from Propo- sition 2.1 is tight. Theorem 3.1 also demonstrates that to get the arbitrarily fast rate in Theorem 2.2, entering the EoS regime unavoidable for adaptive stepsize GD.
Lemma 2.3. Let u2 == (n/(2))) for exponential loss and u2 : (n//)w"" for logistic loss. Under Assumption 1.1, we have
The proof of Theorem 3.1 is motivated by lower bound for constant-stepsize GD that stays in the stable phase in (Wu et al., 2024). We sketch the proof next. The proof is deferred to Appendix B.
2 ((V((w), u2) + [Voo()] 5.
The proof Lemma 2.3 is deferred to Appendix A. Going back to the proof, by rearranging (5) and telescoping the sum, obtain
Proof sketch of Theorem 3.1. One can show that on the con- structed datasct, if L(wi) ) I L(wo), then the base stepsize r must be upper bounded by some constant C1 which de- pends on E(-). Moreover, the split optimization bound im- plies upper bound for both |/well2 and ||Well2 of order (nt)). Combining these two parts shows
W.
112
2
|u|] 2
((w)) S ((u1)
+
(6)
2nt
2nt
Set ij := (ynt/2) /2",,, then we have ((u)) < -y //|uullo using Assumption 1.1 and the definition of (()). This im-
1 Σ l (x; W.) 2 2(([we))))) 2 E(ct) ((w.)

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
for some constant e that does not depend on L or 7. The lower bound for [(w,) holds analogously.
orthogonal directions, where d is the dimension of the pa- rameter. Consequently, starting from zero initialization, any first-order optimization algorithm requires at least (d)) it- erations to reduce the loss below {(0)/2. Finally, exploiting both the boundedness and linear separability (with a positive margin 7) of the dataset, we derive an upper bound on y in terms of d. This bound implies a corresponding lower bound on the burn-in phase before the loss can drop below constant fraction of its initial value.
A lower bound for the number of burn-in steps. We next provide lower bound to show certain number of burn-in steps are necessary for any first-order method.
Theorem 3.2 (A lower bound for the number of burn-in steps), Let E(-) 2 0 be right-diffenn diffeeeeieeee..... Let (w,)120 be given by a first-order method with Wo == 0, that is,
W E W. span (V[(wo)..... V((w,)), 1 O,
4. Two-Layer Networks
where span is the linear span of a vector set, and + is the Minkowski sum. Here, if (.) is non- con-differeniable at some point, we use its right derivative at that point. Then there exists universal constants C1 > O such that for every 0 < 7 < C1, there exists a dataset (xi, i=) satisfying Assumption 1.1, in which the following holds. If
In this section, we extend our results from a linear model to a two-layer network. Specifically, we consider a two-layer network with leaky ReL.U activation (Brutzkus et al., 2018) defined
f (W: =
Σ ajo x Twll),, w(i) E RR.j E [m].
Eajo
[(w1) S 2(0)/2 or [(W,)= S (())22
where m is the number of neurons, Oj E {+1} are fixed parameters, w (w(1), w/2), ...., w(()) Rm is the trainable parameter, and (.) is the leaky ReLU activation defined
for some 220 0, then
2 02? 2/3
Recall that in Theorem 2.2, adaptive stepsize GD needs ((1/>²) number of burn-in steps to obtain the arbitrarily fast convergence rate. As a complement, our Theorem 3.2 number of burn-in steps are nec-
(z) = max az), a E (0,
We assume d'(0) = 1 for convenience. The objective func- tion is then given by
suggests that an essary for every first-order method.
1 [(w) = n Σ (v:f((:;
Note that our Theorem 3.2 applies general loss function L, which does not have to be convex or differentiable. In particular, Theorem 3.2 can be applied to the Perceptron loss {(2) == max(0, } implying a lower bound on the number of steps for the Perceptron algorithm to converge (Novikoff, 1962). Although Perceptron is known to con- verge in at most 1/7² steps (Novikoff, 1962), our lower bound is the first of its kind to the best of our knowledge.
(8)
where E(-) is exponential loss or logistic loss. Similarly, we consider (GD) with adaptive stepsizes (2). Recall that (3) also applies here.
Similarly to logistic regression, we provide convergence rate of adaptive stepsize GD for training two-layer networks with linearly separable data in the following theorem.
Although our Theorem 3.2 suggests a y-dependent number of burn-in steps is unavoidable, we believe our lower bound is not tight. Specifically, we conjecture our lower bound can be improved to 11) This is left for future investigation.
Theorem 4.1 (A convergence rate for networks). Suppose that Assumption I.I holds. Consider (GD) with adaptive stepsizes (2) for objective (8), where the loss function E(.) is exponential loss or logistic loss. Then for every base stepsize 1) O, we have
The proof of Theorem 3.2 motivated by the classical lower bound construction for first-order methods for convex and smooth optimization (Nesterov, 2018). We sketch its proof below. A full proof is deferred to Appendix C.
exp
4
1
ntt
1721
"
f = Lexps
min ((we) ket
S
1 a P
"
Proof sketch of Theorem 3.2. We use dimensionality ar- gument (Nesterov, 2018) (01)))))ifficallyy we construct high- dimensional dataset such that for each gradient query, any first-order method can only collect information in one di- rection However, to decrease the loss below a constant, the algorithm must acquire information from (d) distinct,
exp
4
72t)
{ = l1og:
Let the number of burn-in steps be
(V2((?²a)
( t= Leeps
t0
12V2/(?20)
{ 8= loog:
5

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Then for any 1 2 lo: we have
Under Assumption I.I, we have for every w Rd that
12(w) := 2 (m Vo(w), u2) + 17 1|m v - 0.
1 (-ga?>?mt) min ((ws) S exp k<t
(9)
Lemma 4.3. For j E [m], define uf == o zamtt w
Then, under Assumption I.I,for any w E RR,, we have
Our result in Theorem 4.1 provides a convergence rate simi- lar to that of Theorem 2.2. By employing large and adaptive step sizes, GD can enter the EoS phase, which allows for faster convergence. In particular, once 2 to = θ (1/??), we have
((()) = (Vo(w), w) 07
01 11 (w).
The proof of two lemmas above is deferred to Appendix D. Going back to the proof, we invoke the two lemmas above, rearrange (10), and telescope the sum, we get
lim min L(Wa)) = 0.
77000 kCt
Note that for two-layer networks, we do not guarantee corresponding loss upper bound for the averaged weights because xf-) need not to be convex. Instead, our guarantee holds for the best network along the GD trajectory, whose loss converges exponentially fast.
W ull
Φ (w))
2nmnt
f
k=
09
m
(
1
+
(11)
m
2
2mmt
j=1
The work by Cai et al. (2024) provided a convergence rate for GD with constant stepsize for training two-layer net- works with linearly separable data. They only obtained (LL(P) rate even if the constant-stepsize GD enters the EoS regime. By contrast, as shown in Theorem 4.1, adap- tive stepsize GD can obtain an arbitrarily fast convergence.
This implies
1
7
"1
t leep
1 E ((ww)) 5
4721
k==
i = loog:
4
72t
We complete the proof by using the definition of to in both cases and applying that [()) = (-)(-)).
Note that Theorem 4.1 can be extended to allow leaky vari- ants of near-homone sear-homogeneous activation functions, including leaky GeLU, leaky Softplus, and leaky SiLU (see Cai et al., 2024, for more examples). This is done in Appendix D.
5. A General Framework for GD Acceleration
The proof of Theorem 4.1 is motivated by (Wu et al., 2024; Cai et al., 2024) and is provided next.
In this section, we extend our results in Section 2 from expo- nential and logistic losses to a broad class of classification loss functions.
Proof of Theorem 4.1. Consider a comparator u = u1 +
We begin by formulating general conditions for classifica- tion loss functions under which an accelerated convergence result like Theorem 2.2 can be established.
U2 E Rdm
Denote
(2)
(
Assumption 5.1 (Loss function conditions). Let E(-) IR + R be continuously differentiable. Assume that satisfies the following.
2
U1
U2
(m)
(m)
Up
A. Assume that: The loss is positive, strictly decreasing, and convex. Its inverse (=) exists and is differen- tiable for > O. Moreover, (z)) < 0 for & > 0.
From (3) we have
|ee1 u1/
= || - u112 + 2mm (Vo(w.). u1 -
B. Assume that (b))) defined as following is convex:
1
+ (2)==-
((x)) , = -(11, 22 .... kn)
(2 (m Vo(wi), us) + Ilmm- vo(w))l?)
(12)
Ta(ws)
(10)
C. Assume that: For any vector z = (21, (21,22, 22, ...ry Zn.) E R?""
1 E (
(
1 Σ
We use the following two lemmas to complete the proof.
((2))
S SCr
Lemma 4.2. For j [m], define u 27 w" for the exponential loss and ub (5)
1=1
(13)
= a, w" for the logistic loss.
for some constant C2 > 0.
6

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Clearly, exponential and logistic losses satisfy Assump- tion 5.1A. They also satisfy Assumption 5.1B accord-
1. Polynomial loss. For fixed k 0, we define (Ji & Telgarsky, 2021)
ing to Theorem 5.1 in (Ji & Telgarsky, 2021) ( see also Lemma G.I). Moreover, they satisfy Assumption 5.1C with
for 2 2 0
(1 + 2)
C2 = 1 for the exponential loss and C₂ = 2 for the logistic loss (See Appendix A) Note that for ø in (3) we have
((z) =
22z + (1 (1- 2)4
for z S 0
<(w)= 26 ((w) X1, w X x)
One can show it satisfies Assumption 5.1C in Assump- tion 5.1 with C₁ = n//k, Therefore, for any t z
so ob-) is a composition between a linear mapping and (.))). Therefore. the convexity of (-) directly implies the convexity of o)-). Condition (C) above indicates the self- boundedness of f()), in the sense that the magnitude of [e'()) can be properly controlled by function of E(-) itself, up to some constant multiplier.
/2n 1/k 1/2////>? /72, it holds that
[(w,) S (1 (1+g)(m))
We show the simulation results for polynomial loss with A = 2 in Figure 1.
Theorem 5.2 shows the acceleration brought by using large and adaptive stepsizes can happen for a broad class of clas- sification losses. More surprisingly, Theorem 5.2 implies that for general losses, soon t 2 to ((1/?)) we also have
2. Probit negative log- log-likelihood loss. Let F(z) denote the cumulative density function of niedimensional standard Gaussian distribution. Then, we define (Albert & Chib, 1993; Neal, 1997; Chib & Greenberg, 1998; Liu, 2004)
lim L(we) = O. 9-200
(()) == - In (F(=))
It satisfies Assumption 5.1C with Ce = 1. Therefore, Theorem 5.2 implies that when / 2 v2/n², it holds that
In particular, if {(-) has an exponential tail, i.e., ((x) x exp(-2) for large enough 0, then we can obtain rate of O (exp (n)))) for large enough t.
[(w,)
S -nn F
8 3
Improved convergence rate for general losses. Now we present the acceleration for GD on the general classification losses that satisfy Assumption 5.1.
$ - In
Ci
exp (-o27
72
S 0
exp (-o27
Theorem 5.2 (An improved rate for general loss fune- tions). Suppose that Assumptions 1.1 and 5.1 hold. Con- sider (GD) with adaptive stepsizes (2) for objective function [(w) = E l (1:2, w). Let W. == "k= Wx be the averaged iterates. Then for every 11 > O, we have
ntt
for universal constants C1 and C2. The last inequality comes from classical Mill's ratio (See Lemma G.4).
6. Related Works
((w,)= S SE
1 2 (
Cen 4-2t
In this section, we discuss related papers.
Edge of stability. A growing body of theoretical work investigates edge of stability (EoS) under various scenarios. This includes quadratic functions (Zhu et al., 2022), certain non-convex functions (Wang et al., 2023b), single-neuron linear networks (Ahn et al., 2023), scalar neural networks (Kreisler et al., 2023), two-layer neural networks (Chen et al., 2023), scaled-Invariant networks (Lyu et al., 2022), diagonal linear networks (Even et al., 2023; Andriushchenko et al., 2023), and matrix factorization (Wang et al., 2021; Chen & Bruna, 2023). Several general frameworks have also been proposed to explain the EoS behavior, though they often rely on delicate assumptions (Kong & Tao, 2020; Ahn et al., 2022; Damian et al., 2022; Ma et al., 2022; Wang et al., 2022; Lu et al., 2023). In comparison, we focus on studying the benefits of EoS for improving optimization efficiency logistic regression.
where Ct is the constant in Assumption 5. In particular, let the number of burn-in steps be
to = V20//
then for every t 2 to: we have
[(w.) S e (-$)²m))
where the base stepsize 17 can be arbitrarily large.
Below we list two classification losses that satisfy Assump- tion 5.1 beyond exponential and logistic loss. The proof for these loss functions satisfying Assumption 5.1 is deferred to Appendix
7

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Aggresive stepsize scheduler. A recent line of work con- sidered GD with an aggressive stepsize scheduler (Malitsky & Mishchenko, 2019; Altschuler & Parrilo, 2024a;b; Grim- mer. 2024; Zhang et al., 2024). As their stepsize scheduler violates the descent lemma occasionally, they obtained an improved rate for GD in convex and smooth optimization (assuming the minimizer is finite), Instead, we consider GD with adaptive stepsizes that depend on the current risk, with focus on logistic regression with linearly separable data.
This demonstrates burn-in phase is necessary. Finally, we extend our results from logistic regression large class of loss functions and two-layer networks.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential socictal consequences of our work, none of which we feel must be specifically highlighted here.
Logistic regression. There is large body of literature on the convergence and implicit bias of GD for logistic regres- sion with linearly separable data. The work by Soudry et al. 20: Ji & Telgarsky (2018) showed that small stepsize GD converges to the maximum margin direction. Their re- sults also imply a risk convergence rate of (1//t) (Soudry et al., 2018 8). Their results are extended to GD with a large constant stepsize by (Wu et al.. 2023). In comparison, we focus on the effect of adaptive stepsizes.
A Acknowledgement
We thank Yuhang Cai, Hossein Mobahi, and Matus Tel- garsky for their helpful comments. We thank Qiuyu Ren for his significant help in improving the minimax lower bound. We thank Guy Kornowski and Ohad Shamir for pointing out missing references the optimality of Per- ceptron. We gratefully acknowledge the NSF's support of FODSI through grant DMS- and of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-203188 2031883 and #81 #814639 and of the ONR through MURI award 00001421124311
Regarding this, Nacson et al. (2019) obtained a risk conver- gence rate of Ô (exp(-vv) - -t) by using adaptive stepsizes, and this is improved to ((exp(-t) by the results in (Ji & Telgarsky, 2021),, also using adaptive stepsizes. However, the adaptive stepsizes considered in (Nacson et al., 2019; Jii & Telgarsky, 2021) are relatively small, in which GD stays in the stable regime. In comparison, consider GD with large and adaptive stepsizes, where GD is allowed to enter the EoS regime.
References
Ahn, K., Zhang, J., and Sra, S. Understanding the unsta- ble convergence of gradient descent. In International Conference on Machine Learning, pp. 247-257. PMLR, 2022.
The works by (Wu et al., 2024; Cai et al., 2024) are also related to ours, where they studied GD with large constant stepsize logistic regression and in two-layer networks, re- spectively. Although their GD can enter the EoS regime, the best risk convergence rate they obtained is ((1tt). In com- parison, we considered GD with large and adaptive stepsizes for both cases, and we obtained an arbitrarily fast conver- gence rate. Finally, the work by Tyurin (2024) showed the equivalence between logistic regression with large fixed stepsize and batched Perceptron algorithm as the stepsize grows unboundedly. Their results are related to, but are not directly comparable with ours.
Ahn, K., Bubeck, S., Chewi, S., Lee, Y. T., Suarez, F., and Zhang, Y. Learning threshold neurons via edge of stability. Advances in Neural Information Processing Systems, 36: 19540-19569, 2023.
Albert, J. H. and Chib, S. Bayesian analysis of binary and polychotomous response data. Journal of the American statistical Association, 88(422):669-677 1993.
Altschuler, J. M. and Parrilo, P. A. Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex opti- mization. Mathematical Programming, pp. 1-14, 2024a.
7. Conclusion
Altschuler, J. M. and Parrilo, P. A. Acceleration by random stepsizes: Hedging, equalization, and the arcsine stepsize schedule. arXiv preprint arXiv:2412.05799. 2024b.
In this paper, we show that GD with large and adaptive stepsizes achieves an arbitrarily fast convergence rate for logistic regression with linearly separable data. This holds as long as the number of steps larger than a fixed threshold depending the data margin. We also show the above is impossible if adaptive stepsize GD induces monotonically decreasing risk, thereby demonstrating the benefit of unsta- ble convergence. Moreover, we provide a lower bound, in which to achieve a small risk, every first-order method has to pay a number of steps as a function of the data margin.
Andrüushchenko, M., Varre, A. V., Pillaud-Vivien, I.., and Flammarion, N. Sgd with large step sizes learns sparse features. In International Conference on Machine Learn- ing. pp. 903-925. PMLR, 2023.
Brutzkus, A., Globerson, A., Malach, E., and Shalev- Shwartz, S. Sgd learns wver-parameterized networks
8

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
that provably generalize on linearly separable data. In International Conference Learning Representations, 2018.
Lewkowyez, A., Bahri, Y., Dyer, E., Sohl-Dickstein, J., and Gur-Ari, G. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02211 2020.
Cai, Y., Wu, J., Mei, S., Lindsey, M., and Bartlett, L. Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast opti- mization. arXiv preprint urXiv:2406.0866 2024.
Liu, C. Robit regression: a simple robust alternative to logistic and probit regression. Applied Bayesian Modeling and Casual Inference from Incomplete- DeattteteeeDaaa Perspectives, pp. 227-238. 2004.
Chen, L. and Bruna, J. Beyond the edge of stability via two-step gradient updates. In International Conference on Machine Learning, pp. 4330-4391. PMLR, 2023.
Lu, M., Wu, B., Yang, X., and Zou, D. Benign oscillation of stochastic gradient descent with large learning rates. arXiv preprint arXiv:2310. 17774 2023.
Chen, X., Balasubramanian, K., Ghosal, P., and Agrawalla, B. From stability chaos: Analyzing gradient de- scent dynamics in quadratic regression. arXiv preprint arXiv:2310.01651 2023.
Lyu, K., Li, Z., and Arora, S. Understanding the generaliza- tion benefit of normalization layers: Sharpness reduction. Advances in Neural Information Processing Systems, 35: 34689-34708. 2022.
Chib, and Greenberg, E. Analysis of multivariate probit models. Biometrika, 85(2)347-361, 1998.
Ma, C., Kunin, D., Wu, L., and Ying. L. Beyond the quadratic approximation: the multiscale structure of neural network loss landscapes. arXiv preprint arXi::220.111266 2022.
Cohen, J. M., Kaur, S., Li, Y., Kolter, J. Z., and Talwalkar, A. Gradient descent on neural networks typically occurs at the edge of stability. arXiv preprint arXiv:2103.0000 2021.
Malitsky, Y. and Mishchenko, K. Adaptive gradient descent without descent. arXiv preprint arXiv:1910.09529) 2019.
Damian, A., Nichani, E., and Lee, J. D. Self-stabilization:: The implicit bias of gradient descent at the edge of stabil- ity. arXiv preprint 250 2022.
Mukherjee, S. scheme for proving mill's ratio inequal- ities. https://oumenndu44..gge wtt.ttttaaaiioooos////...... 2016.
Even, M., Pesme, S., Gunasekar, S., and Flammarion, N. (s) gd over diagonal linear networks: Implicit regularisa- tion, large stepsizes and edge of stability, arXiv preprint arXiv:2302.008 08982, 2023.
Nacson, M. S., Lee, J., Gunasekar, S., Savarese, P. H. P., Srebro, N., and Soudry, D. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3420-3428. PMLR, 2019.
Grimmer, B. Provably faster gradient descent via long steps. SIAM Journal on Optimization, 34(3):2588-2608, 2024.
Neal, R. M. Monte carlo implementation of gaussian process models for bayesian regression and classification. arXiv preprint physics/9701026, 1997.
Ji, Z. and Telgarsky, M. Risk and parameter convergence of logistic regression. arXiv preprint 1rXiv:1803.07300 2018.
Nesterov, Y. Lectures Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770.
Ji, Z. and Telgarsky, M. Characterizing the implicit bias via a primal-dual analysis. Algorithmic Learning Theory, pp. 772 22-- PMLR, 2021.
Kong, L. and Tao, M. Stochasticity of deterministic gradient descent: Large learning rate for multiscale objective func- tion. Advances in neural information processing systems, 33:2625-2638, 2020.
Novikoff, A. B. On convergence proofs on perceptrons. Proceedings of the Symposium on the Mathematical Theory of Automata, volume 12, pp. 615-622, New York, NY, 1962.
Kreisler, I., Nacson, M. S., Soudry, D., and Carmon, Y. Gradient descent monotonically decreases the sharpness of gradient flow solutions in scalar networks and beyond. In International Conference on Machine Learning, pp- 17684-17744, PMLR, 2023.
Soudry, D., Hoffer, E., Nacson, M. S.,, Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on sep- arable data. Journal of Machine Learning Research, 19 (70):1-57, 2018.
Tyurin, A. From logistic regression to the perceptron algo- rithm: Exploring gradient descent with large step sizes. arXiv preprint arXiv:2412 12.0:242.008244 2024.
Lan, G. First-order and stochastic optimization methods for machine learning, volume Springer, 2020.

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Wainwright, M. J. High-dimensional stafistics: A asymptotic viewpoint, volume 48. Cambridge university press, 2019.
Wang. G., Hu, Z., Muthukumar, V., and Abernethy, Faster margin maximization rates for generic optimization meth- ods. In Thirty-seventh Conference on Neural Information Processing Systems, 2023a.
Wang, Y., Chen, M., Zhao, T., and Tao, M. Large learn- ing rate tames homogeneity: Convergence and balancing effect. arXiv preprini 1 2021.
Wang, Y. Xu, Z., Zhao, T., and Tao, M. Good regularity cre- afes large learning rate implicit biases: edge of stability, balancing, and catapult. arXiv preprint arXiv:2310.17087, 2023b.
Wang, Z., Li, Z., and Li, J. Analyzing sharpness along gd trajectory: Progressive sharpening and edge of stability. Advances in Neural Information Processing Systems, 35: 9983-9994, 2022.
Wu, J., Braverman, V., and Lee, J. D. Implicit bias of gradi- ent descent for logistic regression at the edge stability. In Thirty-sevnnth Conference on Neural Information Pro- cessing Systems, 2023.
Wu, J., Bartlett, P. L., Telgarsky, M., and Yu, B. Large step- size gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. Conference on Learning Theory. 2024.
Wu, L., Ma, C., et al. How sgd selects the global minima in over-vvvvaaeee pre-paaammterizee learning: dynamical stability perspective. Advances Neural Information Processing Systems, 31, 2018.
Xing, C., Arpit, D., Tsirigotis, C., and Bengio, Y. A walk with sgd. arXiv preprint arXiv:1802.08870, 2018.
Zhang, Z., Lee, J. D., Du, S. S., and Chen, Y. Any- time acceleration of gradient descent. arXiv preprint arXiv:2411.17668, 2024.
Zhu, X., Wang, 7., Wang, X., Zhou, M., and Ge, R. Un- derstanding edge-of-stability training dynamics with minimalist example, arXiv preprini arXiv:2210.03294. 2022.
10

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
A. Omitted Proofs for Theorem 2.2 in Section 2
Properties of Loss Functions
First, let's consider the properties of the exponential and logistic loss functions:
Lexp = exp(-(), (1o =- In (1 exp(-1))-
We have:
For 8 lexp or f hog; we have l > 0, < 0, l" > 0. Moreover, we have |8"1 = -l' S l, and the equation holds for exponential loss.
For t = Elogs (e) < for any & R. This does not hold for the exponential loss.
For é = lesp or l Elog. the inverse function E- E-) exists and is continuously differentiable, and (t)) < for
>> 0.
For e feep or E = bog we define (00)=(((-)) ( Ei (zz)) is convex for z (21, 22, ... 2n) =n) so d(.)
defined in (3) is also convex.
The first three arguments are easy check, while the last one is direct corollary of Theorem 5.1 in (Ji & Telgarsky, 2021).
Proof of Lemma 2.3. When & lexps we have d(w) In L(w). Plug in U2, we have
2 V ((W),) U2) + + Vl =2. Eim Eexp (w xx;) (Xi, u2)
Σ i= exp (w xx)x;
+
Di=1 Lexp(w' xxx)
i= Lexp (w x.)
Ex=1 leepp (w" (x]) xi)
Σ n
i= Leex (w (WTxx) xxi]
2
<2y || 12
+ 17
((w), 2 y and |xx|12 S for any 1 S i S n)
Ei=1 leepl (w] x,)
2i=1 lexpl (exp(w]) xi) xxi)
=0.
(Cexp() = -Lexp( and /2ll| = 27
When f = flog. we set U12 = w -Then
2 ((V)(w), u2) + 1 (
- n
(1-2) (6-) (E(w)) Σ C(w xx)
xx:) (uz, xx) + ((-))((((W))
(f(w))
1 Σ ('(w') [wxxx)xx x;)x;
n
< y Lellla . ((-)) ([(w)) Σ (w xx)l +n (((=r)(((w))
- Σ 1((wTxx xxi
1=1
(1x:l12 S 1 and (xi, w²) 2n)
1 ['(w [[(Tx))) (e ([(w))
-2y ||uulll22 + n
1
['(w' xxi] ((11)) (c(w))
n
Now focus on the term I. Consider two cases. If L(w) 2 In 2, then
exp(L(w))
I ((T))(((())) exp([(w)) -1 2 (LC(()) < 1 and
exp(() (xp is monotonically decreasing at [In 2, oo).)
Otherwise, we have L(W) < 2n Since [e((1) s E(t), we have
exx:(t
5 ((w) (61)) = -k([(w)), where h(t)) == exp(!)

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
We know
M(()) exp(t) (exp(() - - 2 0, lim h(() = (exp(t) - -1)2 So h(-) is monotonically increasing and hence, S h([(w)) - h(l In Therefore, we have I 2 and
(14)
f--0-
2 (Vo(w), u2) + [VV(()) f'(w T ((w]xx)) - (0=1) (c(w)) 11-27 ||u2||2 - 2ny] s 0.
(15)
B. Omitted Proof for Theorem 3.1 in Section 3
Before proving Theorem 3.1, let's first delve into technical lemmas. First, we have the following lemma, which shows that for some special datasets, the stepsize must be small if the loss is non-monotonical.
Lemma B.1 (Stepsize has to be small if the loss drops monotonically). Lel Wo 0a and x 1./n E X Assume
there exist constants > 0 and q E (0, 1) such that
{i E [n] x, -rl
2 4.
n
Assume we perform the gradient descent (GD), If [(w,) S L(wo), then we must have
n - qr
(16)
E(O)
Proof of Lemma B.I. Since wo = OJ, we know C(wo) (0) and VL(wo) (0) & and
Vo(wo) = () (e(0)) - (0) x, wi = (-e (e(0)) (())
We know- - (----1) (e())) (0)) = 1 for both exponential loss and logistic loss. So for both losses, we have W1 = 7/8.
Therefore, if 1) > 200) this implies
gr
((w1) =
|mx x
[Txx x)T (x] x.5 < -r)
Tx [x]x<<<> 2 ((-1r))
(From the assumption)
q In (1 + exp(1r))
(For both exponential loss and logistic loss)
nhr 2 {(0) C(wo).
(From our assumption)
This is contradiction with assumption of the stable phase, i.e., L(wi) S L(wo). Therefore, we conclude
Then, we have the following lemma, which controls the upper bound of ||well2 along the optimization path (GD). Lemma B.2 (Upper Bound of [[well)). Consider the gradient descent in (GD) for exponential loss or logistic loss starting from Od, suppose the Assumption 1.1 holds, then for any > 1 and nj > one has
||wll2 y+ 2 nt.
(17)
Proof of Lemma B.2, We start from the split optimization bound (6). For both losses, from the proof of Theorem 2.2, we know the right-hand side of (6) upper bounded by - 21 + - We also notice that ||x|l2 S 1 implies that for any
E ddd
11 ( l (x] w)
-1/w/1/ S ((w)) = (-
< /w/l2-
im1
12

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Combining this fact with (6) gives
W
[wwll2 + 7 S 7 72 2nt +
Φ wx)
726
Here, u (1/2ynt + n/2)) w" for the exponential loss and u = (1/2mm + n/7)) w for the logistic loss, where w E Rd is the unit vector defined in Assumption 1.1. This implies for either loss and 2 1,
21² 1
3n ?
[wall2 ww ull2 + ||ull2 $
2m
walll2
+ + mh +
2n
wwlll + 2 +
72 2
7
k=
k=0
where the last inequality above uses the fact that va b I va + vb for any a, b > 0. Obviously, (17) holds for If
holds for 0, 1, 2, 1 with 2 1, then for t, one has
|eell2 z (V(++)) + (1+ n s (1+-) 6 nt.
So (17) also holds for t. Invoking a simple induction completes the proof.
Now we prove the Theorem 3.1 by combining Lemma B.1 and Lemma B.2.
Proof of Theorem 3.1. One easily check that the dataset in Theorem 3.1 satisfies the assumptions in Lemma B. with 0.1 and q 0.5. So Lemma B.1 implies 77 S сд where c₁ is constant that depends the loss function. Combining this upper bound for the stepsize, triangle inequality and Lemma B.2, we get ||well2 S C2 I, where C2 is constant that
does not depend on & or 17 (but it can depend on 7). Therefore, invoking the assumption that ||x||| S 1, 1 S i S n, we have
1 Σ
((w,)
((w x,) 2 ( -0) = exp -),
where the last equivalence holds when t is large due to the exponential tails of both losses. The guarantee for L(w.) holds analogously.
C. Omitted Proofs for Theorem 3.2 in Section 3
Proof of Theorem 3.2. Without loss of generality, we can assume the dimension and n 2 4. We define e; as the unit basis in ddd where the i-th entry and others are zero. Then, we construct hard dataset D. We set y/: 1 for and
1 < i
V2
V2
V2
V2
V2
X1 =
X2
e1 +
e2
Xn-1
2 Cn 22 +
en-1. X, en-1-
This dataset satisfies the first condition in the theorem. For each small enough >> 0, we construct a problem instance as follows. We set such that 5 M[+1112d+1] and w := Ed i 22. Then, we know
|| ll V2
and (y,x;, w*) 2 y for 1 < i S We denote (w(1), (2) ...., (2)) Rd The loss function the constructed dataset is
V2 (w(()) + w((tt)) +1 (- V2 (-2 w((n-)) ).
((w) e (wr(2)
+ Σe 8
2
2m 1
13

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
This implies
V2
V2
(-w(2) m((l)) )) i=
E'
(
2
@[(w)
V
V2
(ww(t-1) + m(()) - ( (-w(t) + w w((t))
V2
e'
2 2
Ow(+)
2n
2
V/
l'
V2
(-w(a-2)
w(n ( l'
(- v2 (-2 w(( (->2w(r--1)
i= n 1.
2n
2
Since wo Oa, we know the initial time, only the derivative of L(w) the first entry non-zero. We define R as the subset in Rd such that the last d - k entries are all zero for 0 S k S d. Specially, know Tyj (02) and Ry Rd A simple induction argument indicates that for any first-order gradient optimization algorithm, it holds that
We
R
ostsd d.
For any 0 Ssts n, if w RR, the the last d t entries of are all zero, which implies
C(w)= 2 d-1 n
From the definition of 7, we know
3
2
V d(d 1))2d 1)
(n
1) 2n 1)
2n
which implies that 3
27
Therefore, ift s
(2y²)
1 ~ x- then for all 0 S k S since we E Rd it holds
3
d
[(Wa)
71
72
Moreover, for the average iterate W. = Ei= Wk, since w. E IR 1 we also have the same lower bound guarantee. Therefore, we conclude.
D. Omitted Proofs for Theorem 4.1 in Section 4
D.1. Assumptions and Examples the Activation Functions
Assumptions. First, provide general assumptions the activation functions.
Assumption D.1 (Activation Function). In (7), let the activation function o(2) R be differentiable at 2 * 0 and right-lifferentiaable
With little abuse of notation, let (2) be its derivative at + and the right derivative 0). Moreover, assume
a' (z) is continuous for = * 0 and right-continuous for 0. There exists 0 < a < such that d'(z) E (a, 1].
For any E RR. it holds that (a()) - a'z| < for some 0.
Examples of activation functions. one of the following:
Assumption D.I holds for a broad class of leaky activations. For instance, let ax(-) be
GeLU: (x) x x- F(x). Here, F(x) is the cumulative density function of standard Gaussian distribution.
Softplus: Softplus (x: = log (1 exp(x)).
SiLU: (z) 1+exp(-x)
14

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
ReLU: (R)L == max {a, 0}.
Then, we fix some constant 0.5 < c < and define
1-c
o(z) c x oz())
(18)
where d, can be any activation function above. It is straightforward to check that such "leaky" variant satisfies Assump- tion D.1 with a uniform a = 0.25, K = 1.
Proof the examples of activation functions. Now we prove the leaky activation functions above satisty Assumption D.I.
GeLU:
One can easily show that (G) ==(2) and (c) = F(x) + =f(x), (Luu()
(2 ==2)
where F and f are the cumulative density function and probability density function of standard Gaussian distribution, respectively. Since f 2 O, we know the global maximum of GGLL(() is taken at either x + -0 or x 1/v2, while the global minimum is taken at either x + 0o or x = 12 One can easily show that lim (aL
1, lim &GeLu (x) = O, and d'eL (v2/2) < 1.2, ( > -0.2. Therefore, 0 = cx + 1-
4 (z)
satisfies the first condition in Assumption D.I with a = 0.25. Moreover, since |oG-Lu (I) CCLL (x) x/| = x² ((x) S
0.3, we know that it satisfies the second condition in Assumption D.I with _ 0.3 0.3.
Softplus: One can easily know 0 < dSsttpluu (x) exp(ar
< 1, so the first condition in Assumption D.1 holds with a exp(z))
[z]
a 0.25. Define h(x) = Softtlus (I) - 2 Softplus (x) log [1 + exp(x)) i+exp(x)) we have h h'(z) (1+cxp(=)) so
-rexp(a)
we have h(x) 2 lima->iox h(z)) 0 and M(z) S 1())) ln( < 1. So the second condition holds with k - 1-c < 1.
SiLU: : For Swish function with a fixed B > 0, one can easily show that S'wish (x) = 1+exp(- (1)(1_zz) E [0, 1]. since (1+exp(- -
0 s + exp(-3z))1 - 3x) < 1 + exp( 228z). So the first condition in Assumption D.1 holds with 0.25. For 8x2 expl -Bx)
the second condition, one has Swish (I) - x Swich (x)
(1+cxpl Bxr)) E [0, 1/ So the second condition holds
with k
1-c 122 23
ReLU: Since 0 S (z) < 1. one has the first condition in Assumption D.1 holds with a = -..5. The second condition holds with x. = 1 trivially.
D.2. Omitted Proof of Theorem 4.1
Before proving Theorem 4.1, we first present the general versions of two lemmas in Section 4.
Lemma D.2. We take un? e,Cmn w" for j 1,,,... m, where Ct > 0 is the constant in Condition (C) in the Assumption 5.1. Ct = 1 for the exponential loss and Ct = for the logistic loss. Then, for every w E Rd, one has
27
12(w): == 2 (m Vo(w), uz) + 77 |Im vo(w)]l = O.
Proof of Lemma D.2. We define
9.. = E' (vif (w, o' (x: wl!) 0o,
then we have
2 T2(w)= 2 (-1-1) (f(w)) Σ Σ
m
n
gi.j
11
yxxx w- + 17.
Σ
m
n aj (-t-)(((()) Σ
(C(w))
gi, yxx
n2
n
3=1 i=1
1=1
Since Pij < 0 for any
S < n,
S S m. and yix wn 2イ> 0, ||xx1|1 S 1, one has
2
Iz(w]= <
27 1- (C(w))
Σ ΣΣ
m
+ n
" (- (C(w))
Σ
m
Σ
x
gii
n
j=1
j=1
=(-r-)) (C(w))
Σ
1
(-27
u2
(
+n (-E-1)
(-El)((((w)))
1
Σ g
(19)
2
i=
k=1
15

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
For any 1 < k < n, from the Assumption 5.1, have
n
(-("))(C(w))
(C(w))
(-e"")(((w)) 1e (f (w,x,)) d' (x² w*)
72
11
k=1
n
Σ (-e-1) (C(w)) (1 (w,,))
(a (+')) 2 1)
"
C₁.
where C2 > is the constant in Assumption 5.1. Therefore, combining the above upper bound, equation (19), and the definition of u2, we conclude.
Lemma D.3. We take ul aj | w Then, we have for any w E TR it holds that
61)
m
(ww) = (Vo(w). un w) S a7
6)
x (w)
Proof of Lemma D.3. From the definition of Φ(-), one has
(w) = (V)(w), u1 -w)
= -----t) (c(w)) 1
Σ
"
l' (yif (w:x,))
1
Σ
yrajo' w()) x (uf) - w())
m
5=1
= -- (c(w))
1
Σ
El (yr (w;x:)) -ecl (w,
i=1
where
1 Σ
O
x w/))) yix; Tu(s)
1 Σ yıaj [
x, x wl)) - o (xx wh)))
x wll))
J: =
oj
+
m j=1
1 j=1
aj oo' (xx w() vxx uxxTul]]]
1
o'
x w(()
-/xx, w-
27
Za
m
77
k.
m
2
/=1
Notice e'(-) S O, we define z = (fr (w:x1), (xxx))y2f y2f (w, x2). .... ynf (w, x,)) and 1, = =01, 1,., 1)T R.. Then, from the definition of (b),, one has
[(w) S (-t-t) (C(w))
1 Σ
(yif (w:xi))
ary
Σ
u
- yif (w,xi)
j=1
= (16(2) (2),
a7
Σ
1,
z
$ き
a7
Σ
(3)
K
1,
+ (z)
2
1=1
j=1
(Since (-)- is convex)
a7
(ww
(From the definition of (b)) and ((-))
m
16

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Now present the proof for Theorem 4.1.
Proof of Thhorrem 4.1. We consider comparator 11
U2, where
u
u2
(2)
(2)
u2
U1
u1 (m)
(m)
Consider the following decomposition:
W -ul2 l|: -l2 2mm (VL(w),, u Wi) + m2 VL(w,)ll
l| u12 21m (Vo(w.,, wo) +n (m Vo((w)), u2) + + IIm Vo(w.))l))
f1(ws)
(w(w))
Following Lemma D.3 and Lemma D.2 and inserting wo Oa, we get a split optimization bound:
2
2
W.
ar
(
11
u
w(
S k
u1
+
(20)
21ymt
2
2ymt
k=0
j=1
This implies
|u2 12
7 Σ
o wx) x
+
2
+
Tprat
vymnt
k==
j=1
Taking
(1) 1
u
agCen
amm w",
w", 1 15 $ m,
2
24
get
[-
Cin
Σ )(ws) s KK
1 a +
2n
Therefore, complete the proof of Theorem 4.1 by invoking the convexity of (-).
E. Omitted Proof of Theorem 5.2 in Section 5
The entire proof follows the proof of Theorem 2.2. First, we have the following key lemma which is an analogue of Lemma 2.3
Lemma E.1 (Key Lemma). We define u =
Can w for a loss function satisfying Assumption 5.1 with loss specific 2y
constant Cg 0. Under the definition of ((-). for any E Rdd and any 17 0, it holds that
(VVl()) u2) + Vo( O.
(21)
17

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Proof of Lemma E.I. Note that
(Vo(w), u2) + 11 [/ll///())l
=- 2 - (e (e (L(w)) Σ (((w x:) (x) (u2, xx) + +1 - - (L(w)) (((W)
1
Σ
n
l'
(w NIwTx
x; X3
n
2
2y
n |(-t) ([(w))
Σ (e' xx)] +1 (1e-))(c(0 (C(w))
1
['(w' Nowxx/] xx)
n
n
(1x1l12 1 and (x,, w²) 2)
1
(' xx)] .5)1.(66 ((01)) (C(W))((W))))))
-27 |1 +
1 Σ (((w [[[]Tx)]|= (0-2) (c(W)
7
n
1 ((((Txxx) ((<)))(((w))
(C(w))
1- |2ll| nCi].
(From Assumption D.1)
71
Invoking the definition of uy completes the proof.
Now we prove the Theorem 5.2.
Proof of Theorem 5.2. Denote u = u1 + U2 where u2
Cm w* E Rd. Then, we have Recall the gradient descent 27
iterate (GD), the learning rate scheduler (2), and the definition for o()). Then, following the proof of Theorem 2.2, we have
We+1 ul/
|W: - -ul2 + 2n (Vo(w,). wi) + + V Po((w))l
|/w, u112 + 2n (Vo(w.), un w.) + 2 u2) + + ) [VVool
IA3 Ms
|/w; u1l2 + 2n (Vo(w.). -1-w,,
||, - wwl2 + 2n (6 (u,) - o( ww))
(22)
Here, (a) is from Lemma 1. and (b) is from the convexity of di-) from Condition (B) in Assumption 5.1. Telescoping (22)
from k= = to k = t = yields
I: u1l2
((wx) S ((u)) + Wo u 2
(23)
2nl
7 R=O
2nyl
We take
u1 nTd w", Wn = 0a-
Recall (w',x,) 2 7 and the definition of ((-), we have d(u)) 5 -7 In lll.- This implies
Σ p(wx) < -7 ||111l2+ [nj + +uull 2
-? ||u1 112
[1 12 + n/
|u2 1
2
1
+ +
Cm
27tt
4-2t'
Therefore, when t 2 to = V2C//72
1 Σ o(wx) S
7 7
Invoking the convexity of ((-) completes the proof.
18

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
F. Examples of Loss Functions
Example: polynomial loss.
We consider the polynomial loss (Ji & Telgarsky, 2021), For fixed A >> O, we define
1
for 2
(1+ + 2)
((z)
(24)
1
2k +
for S 0
(1 11=
Then, we have
k:(k: 11
for 2 2 0
for 2
(1 + 2)
(1+2)
(=)== =
(=)=)=
h
k(k +1)
2k +
for 0
for S
(1-2)et1
(1 2)A+2
and
(2) = 1/1 -1, 22
From Theorem 5.1 in (Ji & Telgarsky, 2021), we know o(w) - (C(w)) is convex. Therefore, Condition (A)
and (B) in Assumption 5.1 hold. Now we verify Condition (C) in the Assumption 5.1. For 2 0, it is obvious that [e() (1+23=
A k {(=)
* For = S 0, we define
((2)= = [e(2)]
2k- [1=2)+FT
ko {(2)
2k + [1-s)²
We know lim,-o- h(2) = 1, and lim----oo h(z) = 0, and h(z) is continuously differentiable in (-o0, Moreover, simple computation shows that l1(2) is increasing for 2 S 0. So h(z) for S O, which implies [e'(=) S ke (+=) + for < Therefore, for any sequence zz, i < n, holds that
( ((2))
1 1 [1(x))]
k A. ((1) 4
(zx))
(1-1)
k+I S
72
h- (1 Ei ((2,))
k. C ((zi))
1 EL ((2))) maxiiiin ((2)
(1 ER ((2)))
4
maxi ((z))
< 1/k 1/k
HΣ ((2))
Therefore, the Condition (C) in Assumption 5.1 is satisfied with Ce n//k, Then, Theorem 5.2 indicates that when t 2 la = 1/k /22, it holds that
((W))=((-(()))(1111
(25)
Example: Probit Negative Log-Likelihood Loss.
We consider the Probit Negative Lok-Liieli Loss, defined as
{(z) = - In (F(z)),
(26)
where
F(:) = 1 - exp
52
ds
V2T
is the cumulative density function of standard Gaussian distribution. We also define f(z) F2)2 as the probability density function of standard Gaussian distribution. Then, we have
f(2) F(z)'
('(x)= : (xF(2) + f()))
f(x)=-2) f(z), (((x)
F(z)²
19

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Therefore, can easily verify the condition A in assumption 5.1 and compute
(2)
3(2) == In ((z))((2) In (f(=)) In (- In - (2(
In
which implies
f(z)
F(z) =F(2) + f())
g'(2) (F(())
Lemma G.5 shows that this function is always negative. Therefore, from Lemma G.I, we know ()(-) is convex and hence, <(w) is convex. Next, we verify condition C in Assumption 5.1. From the definition, we know
exp( exp(-t)
= = (exp(-t)) (z) (t) f f (exp(-tt)
We denote L = 1/2 Di=1 (2)) and 4 = =(z,) = - (m((F(z;))) then
n ((+)) (()) = 1 (F- (exp(-Ex))
exp(-L)
exp(-li)
[F (exp(-L)))
We define
h(2) == f (FF-1 (exp(-22)
exp(-2)
Then, compute
(=) = f(x)
F(x) F(x) f(x)²
+ x
where x= x= (exp(
This quantity is strictly negative for all 2 0. So h is concave. Therefore, know
n Σ ((x))) (6)) $
Therefore, as in the analysis above, we show that when t 2 == v2/r2, it holds
In ( --In F (1 (m)) )) s =0(11 1
((w,) = e (-)((w)) s
exp (-o27
(27)
8
72tt
where the last inequality comes from Lemma G.4.
G. Technical Lemmas
G.1. Convexity of (b())
We have the following lemma, which is similar to Lemma 5.2 in (Ji & Telgarsky, 2021). We present the proof here for completeness.
(1)2 Lemma G.1. If (())-e(()) is decreasing on R, then vi(2) = - (2 Σn ((2;)) is convex
Proof. For z = (Z1: 72, ... Tn)T E RR", we have
Veb(2;; = nL (z)(
(z)
(2b(2)== - diag
(z12) (22) ("((n)
(z)) 'T' nl' n(((~v(z))) )+
+ e" (-(-)(())
e ((-((z))) (z)
nl' (=(()(())) nl (
suffices to show that for any v E R"
Σ (((2)) } 2
8" (zi)
8d (-(-)((z))
2/2 2
nl (- vb 2z)
8 ((()((z))
nl' (-)(z))
20

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Recall that (z) < for any z R. Combined with -nnahy--SShwazzzeeeuuiiiggg this gives
(zi) nel (-b( U4
(z)) up ne' (z))
(-)(2))) Tel' (-b(z)) (z)
So it suffices to prove
(-((==)))
(-((-~(2))
(zi)
(z))
which is equivalent to
(Z)))
(zi)
t" ( (1 Ei=
We define h(2) (=).. This is equivalent to
n (tt)))
(-h' (h (1-1 (2 h(x)))))²
S h1" (h 12 ((z))))
(h(i))))
We consider the function y: (0) + R::
((8) = (-h' (h (s))
h" (h-1(s))
Then,
g(*) (M))))²
where L (=h-
8
(())
Since h (s) is decreasing and (M()))2
(c()))
(c) is decreasing in we know g is increasing 00). This bb which implies
(()
indicates for any a, b O, we have 2(++b)
gla) and g(a+b)
a+b
a+b
b g(a + b) 2 (a + b) g(b). a. a( + b) 2 (a + b) g(a),
Adding these two equations and normalizing it, we have g(a + b) 2 g(a) + g(b), which shows g(-) is super-additive on (s, po). This gives
Σ s(h(z)) 5 Σm(zz)
which concludes the proof.
G.2. Lemmas Regarding Gaussian Distribution and Mill's Ratio
Lemma G.2 (Proposition 1.1 in (Mukherjee, 2016)). Let X be a random variable with distribution function F. Set mx(x) = [x > z)] Assume IE |X| < co. Then, for all I n S N, we have
( 20. 0.
k=
Proof. Note that the left hand side is just IE(X 2) where (a)+ = max 0}.
Lemma G.3 (Proposition 1.2 in (Mukherjee, 2016)). Suppose E X k+1 < co. Define ma(x) = E [X*I((X > x)] Then,
mx+1(0) xI L mu)ddu.
21

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
Proof. Note that
mu(u)du= = {
E (X*I(X> u)) du E x { { [[X u)du = mx+1(2) xm (z).
Lemma G.A. We define Fz) and f(z) as the cumulative density function and probubility density function for one- dimensional standard Gaussian distribution. Then,
For any z > O, one has
=f(=) $ - <1=F(=) [(=) 22+1
(28)
2
For any E IR, one has
+ 2. 2=F()) 20
(29)
For any > O, one has
1 1
3
f(z)
F f(2)
+
(30)
2
23
23
25
For any 2 > 0, one has
23 + 5z
1 1-F(2z)
2² +2 2=22 +3)
(31)
24 62
3
f(z)
Proof. The first inequality comes from the standard Mill's ratio for Gaussian distribution. To see the second claim, the first inequality gives =F(2) + f(2) 2 z > for any 2 > 0. For 2 = 0, this is obvious. For 2 < 0, we apply the first claim on - get
F(z) = 1 F( ((=2) f(z)
which implies the second claim directly. The third inequality comes from Exercise 2.2 in (Wainwright, 2019). The last inequality a refinement of the classical Mill's ratio and comes from a notes (Mukherjee, 2016). However, the results from that notes are incorrect. So we give the correct version here for completeness. Lemma G.3 gives
m=(=) = 1 mg(2) = + 2f(2), m²(=) ==) + f= 3(1 F(z)).
- F(=), m=(=) = f(z), m²(=) =f(=) (1 111-F(5 F(z)),
Taking n = 3 in Lemma G.2 gives the right side of (31), while = 4 gives the left side.
The following result shows a standard result for standard Gaussian distribution.
Lemma G.5. We define F22) and f() as the cumulative density function and probability density function for one- dimensional standard Gaussian distribution. Then, for any IR, one has
f(z) 2 (F())((((2)
F(z) 2F(2)+ + f())
2
(32)
Proof. The claim holds trivially for 0. Let's then consider > 0. We write F and for F(z) and f(z), respectively. The claim is equivalent with
(22 + 11) F2 F
50. 50.
(33)
22

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
z f(2)/(F(2) In(F(z))) + F(z)/(z F(z) f(z))
0.10
Value
0.06
0.04
0.02
Figure 2. The Objective function in Lemma G.5 when =
Since In P F for any = F()), when z 2 2, we have
(22 + 1) F2 In F +F +2Ff fz s (F +Ff+
(+2+1) +1 1) 222
F -
+
x2
+1) s (s
2F
(From (31))
23 +3+62+3/2
2. 0.977
S/.
(F 2 0.97 when = 2 2)
23 + 62 +3/2
1
0.977
<f.
(exp(- --22) S ++
2t
14 2/
+ x²
23 + 62 + 3/2
K0
(From numerical computation)
Therefore, the claim holds for z 2 2. Next, we will deal with the case when 2 < -5. We denote x = -2. Since
F(-z)= = 1- 1=) and f(-2) = f()), (33) is equivalent with
2x² + 1) (())= ((=F())) F(+)) x (1 - F(x)) f(x) (1 - F(x)) - x (1 F(x)) + f(x)² so. (34)
Now we write F and f for short of F(x) and (xx), respectively. denote m(x) = F(x) [(x)
This is equivalent with
(x² + 1)m(x)))22((()))))) In In(1)))) F(x))
- F(x)) In)
m(x) + 0.
When z < -5, and x 2 5, from (31), one has
f(x) ln(x
1 1² -ln(x),
In(1 - F(x)) < In
2
2
23

---

Gradient Deseent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes
which implies
(o + In -
x- =((])
I mmxx). 1) + 5x)
+ +3 In(1 - F(x)) - 2 - m() F(x)) - x m(x) +1
2x
x² + 6x +3 m 1n(1 - F(x)) - x m(x) +1
x² 21n(x) - In (2xx
-1 m(x) +1
(35)
x 6x² + 3
x² 2ln(x) - (2
5x²
x+ 6r +3 +1
(From (31) in Lemma G.4)
x4+62* +3 3
-n x² + (21 5lm(2m) 10 +9
(x²² + 6x² +3)²
0
(When x 2 5 from numerical computation)
Therefore, we have proven the claim for S -5 and 2 2. For -5 S 2 S 2, we numerically show the claim holds in Figure 2.
24


Reviews:
[{"review_id": "17aZEI5J8M", "reviewer": "Reviewer_xEgy", "summary": "The authors analyze the gradient descent optimization procedure for logistic regression in the large-stepsize regime. Their upper bounds lead to a \"soft-perceptron\" view of logistic regression, which extends to two-layer leaky ReLU networks and other loss functions with regularity properties similar to exponential and logistic losses. Since their upper bounds are for average-iterate or best-iterate convergence, both in large-stepsize regimes, they also provide a lower bound in the stable regime, manifesting that large stepsizes is essential for arbitrarily fast convergence after the burn-in stage. They also provide a lower bound manifesting that the burn-in stage is necessarily if the last-iterate or the average-iterate convergence is well.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for pointing out the typos. We will make sure to fix all typos in the revision. We address your questions as follows.\n\n---\nQ1: “It is widely accepted that the average-iterate convergence and the last-iterate convergence are not directly comparable in general. Thus, the authors' comment that \"Theorem 2.2 improves Proposition 2.1\" is not accurate, since Theorem 2.2 is not about the last-iterate convergence.”\n\nA1: When treating the output as part of the algorithm design, it is fair to compare GD with large adaptive stepsizes that outputs the averaged iterate and GD with small adaptive stepsizes that outputs the last iterate. Moreover, GD in Proposition 2.1 satisfies the descent lemma, so their averaged iterate would only be slower than their last iterate—so Theorem 2.2 improves Proposition 2.1. We will clarify this in the revision. \n\n---\nQ2: “The evidence provided by simulations and upper bounds actually motivates the following two intuitive points: 1. For the \"large-stepsize\" regime, the last-iterate convergence is not good in general, even with high burn-in cost. 2. … However, Theorem 3.2 only manifest the second point above. This might not be fatal, but the discussion about the first point I mentioned here is indeed missing in the main text.”\n\nA2: We would like to point out that our Figure 1 does not seem to imply that “the last-iterate convergence is not good in general”. Our paper is limited to averaged iterate, and it remains open to analyze the performance of the last-iterate. We will comment on this in the revision. \n\n---\nQ3: “For linearly separable binary classification, …perceptron is able to find the separating hyperplane in the \"last-iterate\" sense after 1/\\gamma^2 iterations, while the simulations and upper bounds in this paper intuitively suggest an evidence that logistic regression is only able to do so in an \"average-iterate\" or even \"best-iterate\" sense. This subtlety make logistic regression sounds like a method even worse than perceptron, at least for this task. The authors should elaborate more on this point.”\n\nA3: When viewing output design as part of the algorithm, our algorithm (GD with large stepsizes and outputs the averaged iterate) matches perceptron in terms of step complexity. So it seems unfair to say our algorithm is “worse” than perceptron. Additionally, we have improved our lower bound construction, showing that our algorithm is minimax optimal among all first-order methods in this problem (see our response to Reviewer QkHV). We will make a detailed comparison with Perceptron in the revision. \n\n---\nQ4: “.... Even in the i.i.d. case, if the support of the data distribution is decently non-trivial, i.e., regions near the boundary are not null sets, \\gamma will decrease as the sample size n increases, which will in turn amplify the burn-in cost $\\gamma^{−2}$ in this paper. Thus, Assumption 1.1 has a significant oversight even for the optimization results in this paper.”\n\nA4: This is a good question. First, we would like to emphasize that this is a standard assumption in binary classification problems and has been widely adopted in literature. We agree that under certain distributional assumptions, the margin of the empirical dataset might be a decreasing function of the sample size. However there are also other cases where the margin of the empirical data remains large. For example, this is the case if the population distribution is (almost) separable with a margin $\\gamma$. We will discuss this in the revision. \n\n---\nQ5: “By the way, yi=1 in Assumption 1.1 is mathematically not a typo since all proofs go through even all labels are positive, but it makes the readers realize that the implication of the upper bounds (when all labels are positive) is not very interesting.”\n\nA5: Note that our results apply to the case where $y_i \\in \\{\\pm 1 \\}$. In this case, we can replace $y_i$ by $1$ and $x_i$ by $y_i x_i$ respectively, then apply our current analysis. So our assumption that $y_i=1$ does not cause any loss of generality. We will clarify this in the revision.", "claims_and_evidence": "See the Section \"Theoretical Claims\".", "methods_and_evaluation_criteria": "Not quite applicable for this theoretical paper. The only subtlety is that while Assumption 1.1 did not model the randomness of the data, the authors random sample features from the unit hypersphere to do simulations. This subtlety leads to a weakness about Assumption 1.1. See Section \"Other Strengths And Weaknesses\" for details.", "theoretical_claims": "The Theorems stated in the paper are correct and the proofs are largely correct. However, several point are worth noting.\n\n- It is widely accepted that the average-iterate convergence and the last-iterate convergence are not directly comparable in general. Thus, the authors' comment that \"Theorem 2.2 improves Proposition 2.1\" is not accurate, since Theorem 2.2 is not about the last-iterate convergence.\n- Clarity: In the proof of Theorem 3.2, around the $\\geq$ on Line 733-734, the implicit assumption $\\ell(0) = 1$ should be explicitly stated in the proof, as well as in the statement of this theorem, which is in the main text.\n- Math typo: The numerator and the denominator in Equation (16) are upside down, though the consequence of which is not fatal.\n- Minor math typo: The $\\leq$ in Line 708-709 should be $\\asymp$ to make the margin condition go smoothly.\n- Typo on Line 981-982: $C_{\\ell}$ -> $C_{\\ell}^2$ (as well the subsequent typos derived from it)\n- Minor typo on Line 184: \"Theorem 5.2\" -> \"Theorem 2.2\"\n- Minor typo in the last sentence of Section 5: \"last\" -> \"penultimate\"\n- Minor typo on Line 951: \"Assumption D.1\" -> \"Assumption 5.C\"\n- Minor comment: The 1st equation block of the statement of Theorem 3.1 is *in a verbatim way* highly similar to that in [1, Theorem 3]. In this case, instead of saying \"movinated by\", I would suggest saying \"following the construction\". Otherwise, the \"edit distance\" between the two equations is too small.\n\nReferences\n\n[1] Wu, Jingfeng, et al. \"Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency.\" The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.", "experimental_designs_or_analyses": "The intuition behind the simulation is coherent with the upper bounds.", "relation_to_broader_scientific_literature": "This paper falls into the line of \"large-stepsize gradient descent for linearly separable logistic regression\" papers. Direct predecessors of this paper include\n- Wu, Jingfeng, et al. \"Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency.\" The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.\n- Cai, Yuhang, et al. \"Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast optimization.\" Advances in Neural Information Processing Systems 37 (2024): 71306-71351.", "essential_references_not_discussed": "To be best of my knowledge, most essential references are discussed.", "other_strengths_and_weaknesses": "### On the Lower Bounds\n\nThe evidence provided by simulations and upper bounds actually motivates the following two intuitive points:\n1. For the \"large-stepsize\" regime, the last-iterate convergence is not good in general, even with high burn-in cost.\n2. For the \"large-stepsize\" regime, if the burn-in cost is not high enough, the average-iterate convergence is also not good.\n\nHowever, Theorem 3.2 only manifest the second point above. This might not be fatal, but the discussion about the first point I mentioned here is indeed missing in the main text.\n\n### Other Subtleties\n- For linearly separable binary classification, the burn-in cost in this paper corresponds to the exact iteration complexity of perceptron on the very same task. This connection between logistic regression and \"soft perceptron\" is interesting. However, perceptron is able to find the separating hyperplane in the \"last-iterate\" sense after $1/\\gamma^2$ iterations, while the simulations and upper bounds in this paper intuitively suggest an evidence that logistic regression is only able to do so in an \"average-iterate\" or even \"best-iterate\" sense. This subtlety make logistic regression sounds like a method even worse than perceptron, at least for this task. The authors should elaborate more on this point.\n- As the authors did in the simulations, sampling data in real-world scenarios often involves randomness. Even in the i.i.d. case, if the support of the data distribution is decently non-trivial, i.e., regions near the boundary are not null sets, $\\gamma$ will decrease as the sample size $n$ increases, which will in turn amplify the burn-in cost $\\gamma^{-2}$ in this paper. Thus, Assumption 1.1 has a significant oversight even for the optimization results in this paper.\n- By the way, $y_i = 1$ in Assumption 1.1 is mathematically not a typo since all proofs go through even all labels are positive, but it makes the readers realize that the implication of the upper bounds (when all labels are positive) is not very interesting.", "other_comments_or_suggestions": "See the Section \"Theoretical Claims\" for the comments on typos in the paper.", "questions_for_authors": "See \"Theoretical Claims\" and \"Other Strengths And Weaknesses\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7K3uI0zGwx", "reviewer": "Reviewer_VFUd", "summary": "The paper shows that in logistic regression with linearly separable data, gradient descent can achieve arbitrarily fast convergence through large and adaptive stepsizes for exponential and logistic loss. This occurs in the edge of stability regime and does not require monotonic risk decrease to occur. Additionally, lower bounds for stable regime adaptive stepsize GD convergence is established, along with a general lower bound for the number of burn-in steps. Finally, with additional assumptions on the loss allows for an improved convergence rate for other losses.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our paper! We will make sure to correct all the typos in the revision.", "claims_and_evidence": "Yes, overall the claims made here seem to be supported by sufficient proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I checked the proofs of the theoretical claims to the best of my ability and found no significant issues.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "These contributions are related to analysis of gradient descent and logistic regression. To the best of my understanding, these results improve on the existing literature beyond step size scheduling and monotonicity assumptions.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Overall, the paper is well developed, concise, and sufficiently rigorous for a theory paper. It builds on an existing body of work and provides novel and significant results.", "other_comments_or_suggestions": "Lines 269-270 - Spacing for \".Specifically\" is messed up\n\nLine 272-273 - Missing period before \"However, ...\"", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vyxn8DEXNp", "reviewer": "Reviewer_YHGM", "summary": "This paper considers using GD to optimize linear classification losses, primarily the exp and logistic losses, but also extended to certain qualitatively similar losses. They show that GD using a particular adaptive stepsize schedule which is roughly proportional to the reciprocal of the loss value (for the logistic and exp losses at least) can converge arbitrarily fast on realizable problems after a short, margin-dependent burn in period. The loss typically does not decrease monotonically while using their schedule, and in fact, they show that if the stepsizes are such that the loss does decrease monotonically, then the rate of convergence is necessarily slower. They extend these results to training the bottom layer of a two layer network with leaky relu activations which has similar behavior. Finally, they show qualitatively similar results for a broader class of losses satisfying certain conditions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our paper! You are correct that there is a typo in the statement of Theorem 5.2. We will make sure to fix it (and all other typos) in the revision. We address your other questions as follows. \n\n---\nQ1: “...Is this type of adaptive stepsize useful for non-separable linear classification problems? Does it help when training both layers of a 2 layer MLP (in theory or practice)? Does it help when training more realistic neural networks in practice?”\n\nA1: Good question. Our main focus is understanding the benefits of EoS/large stepsizes. It is unclear to what extent our results generalize to other cases, such as non-separable linear classification, two-layer networks with non-linearly separable data, or even practical network training. We will comment on this as a future direction.  \n\n---\nQ2: “eq (13): what is $(-\\ell^{-1}(z))'$ referring to? What is z? Is this supposed to be the derivative of the inverse of negative ell evaluated at 1/n sum_i \\ell(z_i)? If so, the \"(z)\" is a little confusing here.”\n\nA2: Here $(-\\ell^{-1}(z))$ should be replaced by $-\\ell^{-1}$. This is a typo and we will fix it in the revision.", "claims_and_evidence": "Yes, the claims are well supported by the evidence they provide in the form of theoretical analysis.", "methods_and_evaluation_criteria": "This is a theory paper, and they address the questions they consider through theoretical analysis, so yes.", "theoretical_claims": "I read through the proofs and they appear to be accurate as best I can tell. The only exception is what I believe is simply a typo in the statement of Theorem 5.2: I think the rhs of the last displayed equation should be \\mathcal{L}(\\bar{w}_t) \\leq \\ell(\\frac{1}{8}\\gamma^2 \\eta t), i.e. without the minus sign (otherwise, it gets worse with larger t since \\ell is assumed to be decreasing).", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The main contribution of this paper seems to be to extend the results of Ji and Telgarsky 2021, who studied the same adaptive stepsizes, but using a much smaller \\eta such that the convergence was monotonic. Due to the monotonicity, their result was weaker, and this paper shows that you still have fast convergence, even when \\eta is chosen much larger than what would be needed for stability, and in fact the larger \\eta is the faster convergence is without limit.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "Strengths: This is a very nicely written paper, which clearly explains the why and the how. The proof sketches (and proofs themselves) are nicely written and give a solid intuition of how the results were established. Of the papers I am reviewing in ICML this year, this is easily the most readable.\n\nWeaknesses: This is an interesting set of results, but it does feel a little bit like it runs the risk of \"overfitting\" to separable logistic/exp loss classification. These problems are a little bit unusual in that reducing the loss from a very small value to substantially smaller value requires using an extremely large stepsize. This doesn't invalidate this (very nice) paper, but I would like to see some evidence that this type of approach / mode of analysis can tell us something about other more difficult problems. I don't mean to say that separable linear classification is an unimportant problem---it's not---but I would say that at this point, we are not desperately in need of new methods for solving separable linear classification problems. Is this type of adaptive stepsize useful for non-separable linear classification problems? Does it help when training both layers of a 2 layer MLP (in theory or practice)? Does it help when training more realistic neural networks in practice?", "other_comments_or_suggestions": "pg 3: \"less as less effective\" -> \"less and less effective\"\neq (13): what is (-\\ell^{-1}(z))' referring to? What is z? Is this supposed to be the derivative of the inverse of negative ell evaluated at 1/n sum_i \\ell(z_i)? If so, the \"(z)\" is a little confusing here.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "mSqSDFTiUQ", "reviewer": "Reviewer_QkHV", "summary": "The paper investigates the convergence of gradient-based methods with large and adaptive step sizes on logistic regression with linearly separable data. The main result establishes that GD can achieve arbitrarily fast convergence rates by using an adaptive step-size schedule.\nFurthermore, the authors prove a lower bound on the iteration complexity for any first-order method. The results are extended to a broader class of loss functions and two-layer neural networks.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and pointing out missing references. We will cite and discuss them in the revision. We address your questions below. \n\n---\n\nQ1: “The arbitrarily fast convergence rate is trivial in this setting…..”\n\nA1: We respectfully disagree. Note that the algorithm you proposed is much slower than ours. This is because in Stage I, GD needs to attain a risk smaller than $\\Theta(1/n)$, which requires $O(n/\\gamma^2)$ steps for a constant stepsize or $O(\\ln(n)/\\gamma^2)$ for small adaptive stepsizes. In comparison, we show that GD with large adaptive stepsizes only needs $\\Theta(1/\\gamma^2)$ steps. \n\nMoreover, we can improve our lower bounds construction to show that $\\Theta(1/\\gamma^2)$ steps is minimax optimal for any first-order batch method to find a linear separator for a separable dataset with margin $\\gamma$. The proof is provided at the end of our response. Thus our algorithm is minimax optimal, while the algorithm you proposed is suboptimal by a $n$ or $\\ln (n)$ factor. We hope this clarifies your concern! \n\n---\n\nQ2: “Unclear connection to Edge of stability (EoS). Although this work frequently references EoS, it does not establish a clear link to it. For GD, EoS typically refers to the phenomenon where $\\lambda_{max}(\\nabla^2 L(w_t))$ oscillates around $2/\\eta_t$. However, this article does not analyze $\\lambda_{max}(\\nabla^2 L(w_t))$ or its relationship with $2/\\eta_t$.”\n\nA2: This seems to be a misunderstanding. Note that [Cohen et al., 2020] described EoS by\n\n“...gradient descent enters a regime we call the Edge of Stability, in which (1) the sharpness hovers right at, or just above, the value $2/\\eta$; and (2) the train loss behaves nonmonotonically over short timescales, yet decreases consistently over long timescales….”\n\nThe second bullet is exactly our definition of EoS, and is arguably more fundamental than the first bullet, since a key surprising feature of EoS is its inconsistency with the descent lemma (see their abstract). We believe our references to EoS are justified. \n\n---\n\nWe formally define first-order batch methods: Let $\\ell(\\cdot)$ be a locally Lipschitz function. \nWe say $w_t$ is the output of a first-order batch method in $t$ steps with initialization $w_0$ on dataset $(x_i, y_i)\\_\\{i=1\\}\\^\\{n\\}$, if it can be generated by $w_{k} \\in w_0 +Lin \\\\\\{\\nabla L(w_0),  \\dots, \\nabla L(w_{k-1})\\\\\\},k= 1,\\dots, t,$\nwhere $Lin$ is the linear span of a vector set and $+$ is the Minkowski addition.\n\nThe improved lower bound: For every $0 < \\gamma < 1/6$, $n>16$, and $w_0$,\nthere exists a dataset $(x_i,y_i)\\_\\{i=1\\}\\^n$ satisfying Assumption 1.1 such that the following holds.\nFor any $w_t$ output by a first-order batch method in $t$-steps with initialization $w_0$ on this dataset, we have\n$\\min_{i\\in[n]} y_i x_i^\\top  w_t> 0 $ implies that $t \\geq \\min\\\\\\{\\ln(n)/(8 \\ln 2), 1/(30 \\gamma^2)\\\\\\}.$\n\nProof: We define $d := \\lfloor 1/5\\gamma^2 \\rfloor \\geq 6,$ where $\\lfloor \\cdot \\rfloor$ is the floor function. Let $(e_i)\\_\\{i=1\\}\\^d$ be a set of standard basis vectors. Note that all defined first order methods defined are rotational invariants. Therefore, we can without loss of generality assume $w_0$ is propotional to $e_1$. Let $k := \\min\\\\{\\lfloor \\log_2 n \\rfloor, d-2\\\\} \\geq 4.$ We construct $(x_i, y_i)\\_\\{i=1\\}\\^n$ as follows. Let $y_i=1$ for all $i\\in[n]$. For $j=1,\\dots,k$, let $x_i := (2/\\sqrt{5})e_{j+1} - (1/\\sqrt{5}) e_{j+2}$ for $2^{k}-2^{k-j+1}+1 \\leq i \\leq 2^{k}-2^{k-j}$. Let the remaining $x_i$'s be $x_i:= (1/\\sqrt{5}) e_{k+2}$ for $2^k \\le i\\le n$. Note that $\\|x_i\\|\\le 1$ for $i=1,\\dots,n$. Moreover, for the unit vector $w^* = (1/\\sqrt{d})  (1,1,\\dots,1)^{\\top}$, we have $y_i x_i^\\top w^* \\geq \\gamma$ for every $i$. Thus, the dataset satisfies Assumption 1.1.\n\nFor a vector $w$, we also write it as $w := (w^{(1)}, w^{(2)},\\dots,w^{(d)})^\\top$.\nThen, the objective function can be written as\n$$\n    L(w) \n    = \\frac{1}{n} \\Bigg[\\sum\\_\\{j=1\\}\\^k 2^{k-j}   \\ell\\bigg(\\frac{2}{\\sqrt{5}} w^{(j+1)} - \\frac{1}{\\sqrt{5}} w^{(j+2)}\\bigg) + \\big(n-2^{k}+1\\big)  \\ell\\bigg(\\frac{1}{\\sqrt{5}} w^{(k+2)}\\bigg)\\Bigg].\n$$\nConsider a sequence $(w_s)\\_\\{s=0\\}\\^t$ generated by a first-order method. We know the gradient at $w_0$ vanishes in all coordinates except the second and the $(k+2)$-th coordinates. By induction, we conclude that for $t \\leq t_0-2$ for $t_0:= \\lfloor (k+1)/2\\rfloor,$ it holds that $w_t \\in Lin\\\\{e_1, \\dots, e_{t+1}, e_{k+3-t}, \\dots, e_{k+2}\\\\}$. So for all $(w_s)_\\{s=0\\}\\^t$, their $t_0$-th and $(t_0+1)$-th coordinates must be zero. By our dataset construction, there exists $i\\le 2^k-1$ such that $y_i x_i^\\top w_k= 0$ for $k=0,\\dots,t.$ This means that the dataset cannot be separated by any of $(w_k)\\_\\{k=0\\}\\^t$. Thus, for the first-order method to output a linear separator, we must have $t \\geq t_0-1 \\geq \\lfloor(k-1)/2\\rfloor\\geq \\min\\\\{\\ln n/(8 \\ln 2), 1/(30 \\gamma^2)\\\\}$.\n\nWe will elaborate on this lower bound and its proof in the revision.", "claims_and_evidence": "See Summary.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Partially.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "See Summary.", "essential_references_not_discussed": "Theoretical analysis on the implicit bias and convergence of logistic regression:\n\n[1] Ji et al. Fast Margin Maximization via Dual Acceleration. (ICML 2022)\n\n[2] Wang et al. On accelerated perceptrons and beyond. (ICLR 2023)\n\n[3] Wang et al. Achieving margin maximization exponentially fast via progressive norm rescaling. (ICML 2024)", "other_strengths_and_weaknesses": "**Strengths.**\n- This paper proves that GD can achieve arbitrarily fast convergence rates via large stepsizes, surpassing previously established rates.\n\n**Weaknesses.**\n\nI have two primary concerns regarding the analysis in the setting of linear regression on linearly separable data.\n\n- **The arbitrarily fast convergence rate is trivial in this setting.** For simplicity, consider the exp-loss $\\ell(z)=e^{-z}$ and let $L(w)=\\frac{1}{n}\\sum_{i=1}^n\\ell(y_i f(w;x_i))$. Let {$w_t$} be trained by GD with either a constant or adaptive step size. The proof proceeds as follows:\n  - *Stage I:  Correct classification*. Prior works [Soudry et al. (2018); Ji & Telgarsky (2021)] establish that there exists a time $T_0$ such that $L(w_{T_0})<\\frac{1}{n}$, ensuring all data points are correctly classified: $\\min_{i\\in[n]}y_i f(w_{T_0};x_i) >0$.  \n  - *Stage II: Naively scaling the parameter norm.* Notice thatthe linear model satisfies $f(Cw;x)=Cf(w;x)$ for any $C>0$, implying that $\\min_{i\\in[n]} y_i f(C w_{T_0};x_i) = C \\min_{i\\in[n]} y_i f(w_{T_0};x_i)$. Therefore, increasing the norm $C\\to+\\infty$ can lead to $\\min_{i\\in[n]} y_i f(C w_{T_0};x_i) \\to+\\infty$, implying $L(Cw_{T_0})\\to 0$.\n\n\n- **Unclear connection to Edge of stability (EoS).** Although this work frequently references EoS, it does not establish a clear link to it. For GD, EoS typically refers to the phenomenon where $\\lambda_{\\max}(\\nabla^2 L(w_t))$ oscillates around $\\frac{2}{\\eta_t}$. However, this article does not analyze $\\lambda_{\\max}(\\nabla^2 L(w_t))$ or its relationship with $2/\\eta_t$.", "other_comments_or_suggestions": "See Weaknesses.", "questions_for_authors": "Can the proposed step size find the max-margin classifier in the logistic regression setting, similar to standard GD? Additionally, what is the max-margin rate?\n\nNotably, while arbitrarily fast convergence can be trivially achieved in linear regression on linearly separable data (see Weaknesses), fast margin maximization is not as straightforward.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a theoretical study on the convergence behavior of gradient descent with large adaptive stepsizes for logistic regression in the linearly separable regime. The central result is that arbitrarily fast convergence can be achieved after the burn-in stage, without requiring monotonic loss decrease. The analysis further generalizes to certain two-layer neural network settings and other loss functions.

Reviewers acknowledged the novelty, clarity, and theoretical strength of the paper. While there is a concern regarding the significance of the main result (arguing that fast convergence may be trivial), this paper’s value lies in its explicit and rigorous characterization of how large-step GD operates in this setting.

Overall, this paper makes a clear, technically solid contribution to the theoretical understanding of gradient dynamics under large stepsizes. I recommend acceptance.
Decision: Accept (poster)