Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability
Authors: Jingfeng Wu
Vladimir Braverman
Jason D. Lee
Venue: NeurIPS 2023 spotlight (2023)
Keywords: gd; implicit bias; edge of stability
TL;DR: We show the convergence and implicit bias of GD with any constant stepsize for logistic regression on linearly separable data.

Abstract: Recent research has observed that in machine learning optimization, gradient descent (GD) often operates at the edge of stability (EoS) [Cohen et al., 2021], where the stepsizes are set to be large, resulting in non-monotonic losses induced by the GD iterates. This paper studies the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime. Despite the presence of local oscillations, we prove that the logistic loss can be minimized by GD with any constant stepsize over a long time scale. Furthermore, we prove that with any constant stepsize, the GD iterates tend to infinity when projected to a max-margin direction (the hard-margin SVM direction) and converge to a fixed vector that minimizes a strongly convex potential when projected to the orthogonal complement of the max-margin direction. In contrast, we also show that in the EoS regime, GD iterates may diverge catastrophically under the exponential loss, highlighting the superiority of the logistic loss. These theoretical findings are in line with numerical simulations and complement existing theories on the convergence and implicit bias of GD for logistic regression, which are only applicable when the stepsizes are sufficiently small.

Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability
Jingfeng Wu Johns Hopkins University Baltimore, MD 21218 uuujf@jhu.. edu
Vladimir Braverman Rice University Houston, TX 77005 vb21 @rice.
Jason D. Lee Princeton University Princeton, NJ 08544
jasonlee@pprinceton.co
Abstract
Recent research has observed that in machine learning optimization, gradient descent (GD) often operates at the edge of stability (EoS) [Cohen et al. [021]], where the stepsizes are set to be large, resulting in non-monotonic losses induced by the GD iterates. This paper studies the convergence and implicit bias of constant- stepsize GD for logistic regression on linearly separable data in the EoS regime. Despite the presence of local oscillations, we prove that the logistic loss can be minimized by GD with any constant stepsize over long time scale. Furthermore, we prove that with any constant stepsize. the GD iterates tend to infinity when projected max-margin direction (the hard-margin SVM direction) and converge to a fixed vector that minimizes a strongly convex potential when projected to the orthogonal complement of the max-margin direction. In contrast, also show that in the EoS regime, GD iterates may diverge catastrophically under the exponential loss, highlighting the superiority of the logistic loss. These theoretical findings are in line with numerical simulations and complement existing theories the convergence and implicit bias of GD for logistic regression, which only applicable when the stepsizes are sufficiently small.
Introduction
Gradient descent (GD) foundational algorithm for machine learning optimization that motivates many popular algorithms. Theoretically, the behavior of GD is well understood when the stepsize is small. this regard, one of the most classic results the descent lemma (see, e.g., Section 1.2.3 in Nesterov et al. 2018
Lemma (Descent lemma, simplified version). Suppose that supw V (w) || S then
L(w4) I(w) - 1 (1 n//2) ||VL())].. where W - VL(w).
When the targeted function is smooth (such logistic regression) and the stepsize is small (0 17 3/2), the descent lemma ensures a monotonic decrease of the function value by performing each GD step. Building upon this, sequence of iterates produced by GD with small stepsizes provably minimizes the function value in various settings (see, e.g., Lan (020
For a more modern example, a recent line of research has established the implicit bias of GD with small stepsizes (see Soudry et al. [2018), Ji and Telgarsky (2018) and references thereafter). Specifically, they consider GD for optimizing logistic regression (besides other loss functions) on
'The uniformly bounded Hessian norm condition stated simplicity can relaxed in many ways. For example, it can be replaced by requiring L(-) to 8-smooth. For another example, can also replaced with supoSAs1 L w - X) w-)ll
111 8.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

6- 0.3
0.01
175
85-
10'
150
5.0
125
100
75
1015
75
70
50-
n= D.L
25
n- 0.01
10
200
400
650
1000
0.
50
100
150
250
300
60
4.00
600
600 1000
Koration
Itrration
Koration
(a) Training loss
(b) Sharpness
(c) Test accuracy
Figure 1: The behaviors of GD for optimizing a neural network. We randomly sample 1, 000 data from the MNIST dataset and then use GD to train 4-layer fully connected network to fit those data. We use the cross-entropy loss, i.e., the multi-class version of the logistic loss. The sub- sub-figures (a), (b), and (c) report training loss, test accuracy, and sharpness (i.e., || | (w)))ll) along the GD trajectories, respectively. The red curves correspond to GD with a large stepsize 7j = 0.1, where the training losses oscillate locally and the sharpnesses can exceed 2/n 20. The green curves correspond to GD with small stepsize r 0.01, where the training losses decrease monotonically and the sharpnesses
always below 2/11 200. Moreover, (c) suggests that large-stepsize GD achieves better lest accuracy than small-stepsize GD. consistent with larger-scale deep learning experiments [Goyal et al. 2017]. More details of the experiments can be found in Appendix D
linearly separable data. When the stepsizes are sufficiently small, the GD iterates shown to decrease the risk monotonically (by variant of the descent (mmma); moreover, the GD iterates tend to align with a direction that maximizes the my-margin of the data (Soudry et al. 2018 and Telgarsky 2018). The mangginmaaimizztionn bias of small-stepsize GD sheds important light on understanding the statistical benefits of GD, as a large margin solution often generalizes well [Bartlett et al. 2017 Neyshabur et al. 2018).
Nonetheless, in practical machine learning optimization, especially in deep learning, the empirical risk (or training loss) often varies non-monotonically (while being minimized in the long run) - the local risk oscillation is not only caused by the algorithmic randomness but is more effect of using large stepsizes, as it happens for deterministic GD (with large stepsizes) as well (Wu et al. 2018
Xing et al.) 2018 Lewkowyez et al., 2020 Cohen et al. 2021]. This phenomenon is showcased in Figures I (a) and 2 (a), and is referred to by Cohen et al. [2021] as the edge of stability (EoS). The observation sets non-negligible gap between practical and thcoretical GD setups, where in practice, GD is run with large stepsizes that lead to local risk oscillations, but in theory, GD is only considered with sufficiently small stepsizes, predicting monotonic risk descent (with a few exceptions, which will be discussed later in Section 2. A tension remains to be resolved:
Is the convergence of risk under local oscillation merely a "lucky" occurrence, or is it predictable based on theory?
Contributions. this work, we study the behaviors of GD in the EoS regime arguably the simplest setting for machine learning optimization - logistic regression on linearly separable data. We show that with any constant stepsize, while the induced risks may oscillate locally, GD must minimize the risk in the long run at a rate of O(1/t), where t is the number of iterates. In addition, show that the direction of the GD iterates (with any constant stepsize) must align with a max margin direction (the hard mard-margin SVM direction) at rate of O(1/ /o/(())).. These results explain how GD minimizes a risk non-monotonically, and complement existing theories [Soudry et al. 2018 Ji and Telgarsky 2018 on the convergence and implicit bias of GD, which are only applicable when the stepsizes are sufficiently small.
Some additional notable contributions are
1. We also show that, when projected to the orthogonal complement of the max-margin direction, the GD iterates (with any constant stepsize) converge fixed vector that minimizes strongly convex potential at a rate of ((1 log(()). This characterization is conceptually more interpretable than an existing version (Soudry et al., 2018).
2. We show that in the BoS regime, GD can diverge catastrophically if the logistic loss replaced by the exponential loss. This is in stark contrast to the small-stepsize regime, where the behaviors

---

of GD are known to be similar under any sxponentially-tailee losses including both the logistic and exponential losses [Soudry et al. 2018 Ji and Telgarsky 2018]. The difference in the EoS regime provides insights into why the logistic loss is preferable to the exponential loss in practice.
3. From a technical perspective, we develop a new approach for analyzing GD with large stepsizes. Our approach views the GD iterates as coupling of two orthogonal iterates, one along max- margin direction and the other along the orthogonal complement of the max-margin direction. The former iterates tend infinity and the latter iterates approximate "imaginary" GD iterates that minimize a strongly convex potential with a decaying stepsize scheduler, controlled by the former iterates. Our techniques for analyzing large-stepsize GD can be of independent interest.
2 Related Works
In this section, we discuss papers related to our work.
Implicit bias. We first review set of papers on the implicit bias of GD (with small stepsizes).
Along this line. (ouudry et al. 2018) are the very first show that GD converges along max-margin direction when minimizing the empirical risk of an exponentially-tailed loss function (such as the logistic and exponential losses), linear model, and linearly separable data. Then, an alternative analysis is provided by Ji and Telgarsky (018). which also deals with non-separable data. These two works directly motivate for considering GD for logistic regression on linearly separable data. However, there are at least three notable differences between our work and theirs. Firstly, their results only apply GD with small stepsizes, while our results apply GD with any constant stepsize. Secondly, their theories predict no difference between the logistic and exponential losses (as they are limited to the small small-stepsize regime). Quite surprisingly, we prove that in the EoS regime, GD can diverge catastrophically under the exponential loss. Thirdly, from technical viewpoint, their implicit bias analysis is built upon the risk convergence analysis, which further relies on a monotonic risk descent argument, hence only applies to small stepsizes. In comparison, we come up with a new approach that allows analyzing the implicit bias under risk oscillations; the long-term risk convergence is simply consequence of the implicit bias results. Hence our techniques can accommodate any constant stepsize. See Section 3 for more discussions.
Subsequent works have extended the results by Soudry et al. [2018) Ji and Telgarsky 2018 to other algorithms such as momentum-basse GD [Gunasekar al. 80 Ji al. [022]] and SGD Nacson et al. 2019c]. and homogenous but non-linear models [unasekarr et al. 2017 Ji and Telgarsky 2019 Gunasekar et al. 2018b] Nacson al.) 2019a) Lyu and Li 2020] and hon-homogenuus models Nacson et al.) [2119]]. All these theories require the stepsizes to be small or even infinitesimal, in a
regime away from our focus, the EoS regime.
It is worth noting that Nacson et al. [019b) consider GD with an increasing stepsize scheduler that achieves faster margin-maximizztion rate than constant-stepsize GD. However, their stepsize at each iteration is still appropriately small, resulting in monotonic risk descent by variant of the descent lemma.
Edge of stability, The risk oscillation phenomenon has been observed in several deep learning papers [Wu et al.) 2018 Xing al. 2018 Lewkowyez al. 2020). and the work by Cohen et al. [2021] coins the term, edge of stabiliry (EoS), that formally refers to it. In the remainder of this part, focus reviewing the current theoretical progress in understanding EoS.
Zhu al. 2023 rigorously characterize EoS for a two-dimensional function (u, v) + (u20² 1)a Chen and Bruna (022) study EoS for one-dimensional function ->> (u² - 1)2 and for a special
two-layer Lingle-nerron network. Similar to these two works, Kreisler et al. [2023] study EoS
in I-dimensional linear network. Ahn et al. [2022a] consider functions (u, v) + E(uv), where
is assumed to be convex, even, and Lipschitz; notably, they show a statistical gap between the
small-stepsize regime and the EoS regime. Finally, Even et al. (2023] Andriushchenko et al. [0233] consider the regularization effect of large stepsizes in a diagonal linear network. Compared to their settings, our problem, i.e., logistic regression, is natural machine-leaming problem with fewer artifacts (if any).
EoS has also been theoretically investigated for general functions Ma et al. 2022 Ahn et al. 2022b Damian et al. 2022 Wang et al. (022b), but these theories are often subject to subtle assumptions that are hard to interpret verify. Specifically, Ma al. (0222) require the function to grow
3

---

"subquadratically"" Ahn et al. [202b]] assume the existence of a "forward invariant subset" near the set of mimima the function. Damian al. [2022] assume negative correlation between the gradient direction and the largest eigenvalue direction of the Hessian. Wang et al. [022b] consider two-layer neural network but require the norm of the last layer parameter and the sharpness change in the same direction along the GD trajectory. Indirectly connected to EoS, the work by Kong and
Tao [020] shows a chaotic behavior of GD with non-small stepsize when optimizing a "multi-scale" loss function. In comparison, our assumptions are more natural and interpretable.
loss, e.g., network with normalization layers and weight decay, and the work by Wang et al. [2022a] shows balancing effect matrix factorization induced by GD with constant stepsize that is nearly 4/ 4/IV>L((woll) 2 and is larger than 2/1 V Lww)lll.. The objectives in their works are different from ours, i.e., logistic regression.
Besides, the work by Lyu et 2022 considers EoS induced by GD for
The unstable convergence has also been studied for normalized GD [Arora et al. 2022] and regularized GD Bartlett al. 2022]. These algorithms are apart from our focus on the vanilla GD.
Finally, the work by Liu et al. 2023] considers logistic regression with non-separable data (such that the objective is strongly convex), where GD with sufficiently large stepsize diverges. In contrast, we consider logistic regression with separable data, where GD with an arbitrarily large stepsize still converges.
Preliminaries
We Rdd denote feature vector and y (+1) denote binary label, respectively. Let (x); be a set of training data. Throughout the paper, we assume that (x;,3:)) is linearly separable (Soudry et al. 2018).
Assumption 1 (Linear separability). Assume there is Rdd such that yıx] 0 0f i 1,...,n.
Let w E R be the parameter of a linear model. In logistic regression, aim minimize the following empirical risk
L(w): = Σ log (1 [ exp( -yp (x,, w))). W E
We study sequence of iterates (we)e20 produced by constant-stepsize gradient descent (GD), where Wo denotes the initialization and the remaining iterates are sequentially generated by:
W. = W - (L(W.-)): 2 1,
(GD)
where 17 > 0 is a constant stepsize. We are especially interested in a regime where is very large such that L(w,) oscillates a function of For the simplicity of presentation, will assume that Wo = O. Our results can be easily extended to allow general initialization.
The following notations are useful for presenting our results.
Definition 1 (Margins and support vectors). Under Assumption [ define the following notations:
(A) Let be the max-f2-margln (or max-margin in short), i.e.,
max min yi (X;, w). [
(B) Let be the hard hard-margin
(SVM) soluion, i.e.,
= arg min weRd
||w]|2, s.t. yi (x, w) 2 1, I....,
It is clear that exists and uniquely defined (see, e.g., Section 5.2 in Mohri et (0018) Note that | = 1/7 and w/|lw/2 is max-mann margin direction. Also note that by duality. w can be written as (see, e.g., Section 5.2 in Mohri et al. (0188
Σ iES
0 y:Xi,
0; 2 0.

---

(C) Let S be the set of indexes of the support vectors, i.e.
{ S
[nx] yd (x,, w/ (2 m))
(D) If there exists non-support vector (S $ [n]: let the second smallest margin, i.e.,
= min y/ (x,, w/ [ i
is clear from the definitions that 0 > y > 0. In addition, from the definitions we have
Σ iES
= Σ aj y,x, w = | 722
iS
In addition to Assumption 1 we make the following two mild assumptions to facilitate our analysis. Assumption (Regularity conditions). Assume that:
(A) ||x 12 - 1, 1, n =d
(B) rank
x,, X;;
Assumption 2 is only made for the convenience of presentation. In particular, Assumption A be made true for any dataset by scaling the data vectors with factor of max; || |x||2- Without Assumption B) our theorems still hold under a minor revision by replacing all the vectors of interests with their projections span = i= In.....)..
Assumption 3 (Non-degenerate data). In addition to Assumption ! assume that
(A) [x; i E S} rank(xi, i --...,m,, m... (B) There exist o4 > 0, i E S such that w Eies 04 y:x,
Assumption 3 has been used in Soudry et al. [2018] (see their Theorem 4), which requires that the support vectors span the dataset and are associated with strictly positive dual variables. Assumption B almost surely for every linearly separable dataset sampled from continuous distribution according to Appendix B in Soudry et al. (018). Assumption proovidess convenience to our analysis, but we conjecture might not be necessary. Kemoving/relaxing Assumption is left as future work.
3.1 Space Decomposition
Conceptually, our analysis is built on a novel space decomposition viewpoint, which relies on the following lemma.
Lemma 3.1 (Non-seprabbee subspace). Suppose that Assumptions is not linearly separable in the subspace orthogonal the max-margin direction w/ll 1l... That is
I and hold. Then (x,, Yo yi)ses
for every v such that (v, w) 0, there exist i, E S such that y: (x, v) 0, yj (x,, v)
Proof of Lemma 3.1
By Assumption 3 and (v, w) = 0, we have
(v, w) Σ
ar yix v.
iES
By Assumptions and 3 we have
rank (v,X,, i S) = rank i E S} = rank(x,, i= i=....,, nn) =d
so there must exist i E S such that y,x; v + O. Without loss of generality, assume that y,x.T v < 0. Then since a; > for i E by Assumption there must exist j E S such that y,x] v
Lemma 3.1 shows that, although the dataset can be (linearly) separated by w, cannot be separated by any vector orthogonal to w. This motivates us to decompose the d-dimensional ambient space into 1-dimensional "separable" subspace and (d 1)-dimensional meon-separable" subspace. This idea is formally realized as follows.
Fix d - orthogonal vectors fj...., fa-1 E Rd such that
f...., fa-1) forms orthog-
onal basis of the ambient space Rdd. Then define two projection operators:
P: Rd R
given by v Tww.w//w/oo.oo w/l /
5

---

P: Rd - = given by v (v f ,. fd-1).
The two operators together define a natural space decomposition, i.e., Rd = P(R)) @ P(RR)) Moreover, (P(x)),Bi) are linearly separable with an
y according to Definition
I and (P(x;), 36) ieS (hence (P(x;), (1) == are non-separable according Lemma 3.1 So the decomposition of space can also be understood the decomposition of data features into "max- margin features" and "non-separable features".
In what follows, will call PRR") the max-margin subspace and P(R.) the non-separable subspace, respectively. In addition, we define a "margin offset" that quantifies to what extent the 'non-separable features" are not separable.
Definition (Margin offset for the non-separable features). Under Assumptions I that (P(x:). U/) ies is non-separable. Let b be a margin offser such that
2 and it holds
min Vo (P(x:), w)
max [|
Then > 0 due to the non-separability. The definition immediately implies that:
for every v E Rd-1 there exists i S such that y: (P(x.), v) --b |/
Comparison to Ji and Telgarsky (2018). The work by Ji and Telgarsky 2018 also conducts space decomposition (see their Section 2). However, our approach is completely different from theirs. Firstly, they consider a non-separable dataset but we consider linearly separable dataset. Secondly, at higher level, they decompose the "dataset" (into two subsets), while we decompose the "features" (into two kinds of features). More specifically, Ji and Telgarsky (2018) first group the non-separable dataset into the "maximal linearly separable subset" and the complement, non- non-separable subset, then decompose the ambient space according to the subspace spanned by the non-separable subset and its orthogonal complement. In comparison, we consider linearly separable dataset and decompose the ambient space according to a max-margin direction (i.e., P)) and orthogonal complement (i.e., P))
4
Main Results
We are now ready to present our main results. All proofs are deferred to Appendix C we provide the following theorem that captures the behaviors of constant-stepsize GD for logistic regression on linearly separable data.
To begin with,
Theorem 4.1 (The implicit bias of GD for logistic regression). Suppose that Assumptions 7
and 3 hold. Consider (Wz) produced by (GD) with initilization wo = 0 and constant stepsize n O. Then there exist positive constants et, 02, C3 0 that are upper bounded by polynomial of (e", em,, el/,/./1///// 1/(0- - 7), 1/r,e0/1 B/7) but are independent of t, such that:
(A) The risk is upper bounded by
L(w,) S ci/t, 223.
(B) In the max- max-margin subspace,
P(w.) 2 log(t)/7+ log(n? 2/2)/// 12 1.
(C) In the non-separable subspace,
IP(W:)ll2 < c22 82 0.
(D) In addition, in the non-separable subspace,
G(P(w.)) min G(-) S cz/log(t), t23, where G(-) is a strongly convex potential defined by
G(v) = Σ exp (- Vi (P((x), v)), ve

---

10
10a
10
10a
10
Sharpness
10-2
10
0.01
10-4
0.1
10-4
n=0.1
n- 10
0 0-10
10-1
n= 10?
10-5
7 1=10
10:40
10?
0 101
10
25
50 100 125 Iteration
200
10
20 Iteratioo
50
(a) Empirical risk
(b) Sharpness
Figure 2: The behaviors of GD for logistic regression. We randomly sample 1, 000 data with labels "0" and "g" from the MNIST dataset and then GD perform logistic regression those data. The sub-figures (a) and (b) report risk (i.e., logistic loss) and sharpness (i.e.. (L(w))]l22 along GD trajectories, respoeeciiitsssiiiiiiiiii respectively. For with stepsizes y larger than or equal to 0.1, the training losses oscillate locally and the sharpnesses can exceed 2/n. For GD with small stepsize = 0.01, the training losses decrease monotonically and the sharpnesses always below 2/n. More details of the experiments can be found in Appendix
Note that Theorem 4.1 applies GD with any positive constant stepsize, therefore allowing GD be the EoS regime. We next discuss the implications Theorem 4.1 detail.
Risk minimization. Theorem 4. [A) guarantees that the GD iterates minimize the logistic loss at rate of O(1/t) for any constant stepsize, even for those large stepsizes that cause local risk oscillations. This result explains the risk convergence of GD in the EoS regime, illustrated in Figure 2 and also consistent with the observations neural network experiments (see Figure I.
B shows that the GD iterates, when projected to the max- margin direction, tend infinity at a rate (log(t)) Moreover, Theorem [C shoos GD iterates, when projected to the non-separable subspace, are uniformly bounded. These two results together imply that the direction of the GD iterates will tend to max-margin direction, i.e., the
Margin maximization. Theorem 4.
shows that the
SVM direction, at rate of O(1 log(!)). Therefore, the implicit bias of GD that maximizes the f2-margin is consistent in both the EoS regime and the small-stepsize regime (Soudry
al. 2018 Ji and Telgarsky 2018
Iterate convergence in the non-separable subspace. Theorem 4. [.D shows that the GD iterates, when projected to the sepaaabeeb subspace, converge to the minimizer of strongly convex potential G--). Here, G(.) measures the exponential loss parameter on the support vectors with their separabbe features. This provides a more precise characterization of the implicit bias of GD: direction of the GD iterates converges to the hard-margin SVM direction, moreover, the limit of the projections of the GD iterates to the orthogonal complement to the hard-margin SVM direction minimizes the exponential loss on the non-separable features of the support vectors.
Comparison to Theorem 9 in Soudry et al. 20188. Theorem 9, in particular, equation (18), in Soudry et al. (2018) indirectly characterizes the convergence of GD iterates in the non-separable subspace. It reads in our notations that: w == lim, (W: w log(t)) exists and satisfies
for every E S, 1) exp(-wi (x,,
axs where is defined in Assumption 3
(I)
In Appendix A we show that Theorem DD equivalent to condition in terms of describing
P(w..). Despite their equivalence, ① is less interpretable than Theorem 4. (D) as ① entangles
an effect of P( Po with P (..,.), while Theorem completely decouples P( Woo and P(w..)).
In particular, ( seems to suggest P(w..) to be a function of stepsize since w depends
However, this is only an illusion brought by the lack of interpretability of [[) it is clear that P(w.)) independent of according to Theorem 4. D)
Exponential loss. Until now, our theory for GD is consistent for large and small stepsizes. However, this is particular benefit thanks to the design of the logistic loss, and may not hold for other losses. Our next result suggests that, in the EoS regime where the stepsizes are large, GD can diverge catastrophically under the exponential loss.
TThe theorem can be easily extended to allow any wo that has bounded 62 normm.
7

---

Theorem 4.2 (The catastrophic divergence of GD under the exponential loss), Consider dataset of two samples, where
X1 (7i 1),
1/1 1;
X2 = (7: -1), U22 1.
It is clear that (x,; 11) is linearly separable and (1,0) 0) is the max-margin direction. Consider risk defined by the exponential loss:
L(w, w) exp(-yı (x1, w)) + exp w)) = = (e te"), where w = (w, W)
Let (W,, (r), be the iterates produced by GD with constant stepsize 17 for optimizing L(w, w)
0 S wr s
|ma 2 1, 0<><1/4 1 1 4,
then:
(A) L(w,, we)
(B) Wt + 30.
(C) For every 2 [Wel 2 2-y
(D) Moreover, the sign of i. flips every iteration.
As consequence, (wi, 0z):20 diverge in terms of either magnitude direction; in particular, the direction of (we, We)e20 cannot converge to the max-margin direction (which ()).
Theorem 4.2 shows that with large constant stepsize, the GD iterates longer minimize the risk defined by the exponential loss and no longer converge along the max-margin direction. In fact, the directions of the GD iterates flip every step, thus the direction of the GD iterates necessarily diverges, resulting in no meaningful implicit bias at all.
In the EoS regime, strge-stepsize GD still behaves nicely under the logistic loss (Theorem 4.1 but behave catastrophically under the exponential loss (Theorem 4.2 From a mathematical standpoint, this difference is rooted in the fact that the gradient of the logistic loss is uniformly bounded while the gradient of the exponential loss could he extremely large. From a practical standpoint, it provides insights into why the logistics loss (and its multi-class version, the cross-entropy loss) is preferable the exponential loss in practice.
The different behaviors of large-stepsize GD under the logistic and exponential losses also sharply contrast the EoS regime with the small-stepsize regime. Because in small-stepsize regime, the convergence and implicit bias of GD are known to be similar under any exponentially-taleed losses, including the logistic and exponential losses [Soudry et al. 2018 Ji and Telgarsky 2018).
Techniques Overview
The proofs Theorems 4.1 and 4.2 are deferred to Appendix C In this section, we explain the proof
ideas of Theorem 4.1 by analyzing simple dataset considered in Theorem 4.2 (the treatment to the general datasets can be found in Appendix B). But this time we work with the logistic loss instead of the exponential loss, that is,
L(w, w) log(1 + ww-w log(1 -w+
Then the GD iterates can be written
W++1 = 17 gt,
11+1 = T1 17 gt.
where
( T + -r -w )
Ft =7:-
Jt T=:= +ww
@rwetw,
+ @ 12
For simplicity, assume that
w0 0, |wn > 0.
Different from Soudry et al. 2018 Ji and Telgarsky (0018 our approach begins with showing the implicit bias (despite that the risk may oscillate). The long-term risk convergence is then simply consequence of the implicit bias results.

---

Step 1: (20) is uniformly bounded. Observe that Hc and We always share the same sign and that @r S 1, we have
We+1l ||0.1 77
lTell S max { [weel " Øell I max ||,,|1 n).
By induction, we get that (lwe)) is uniformly bounded by max (oll 7) e
Step 2: z log(t)/>- We turn to study the max-margin subspace. It is clear that 9r S 0 for every
t 2 0. So we have Wi by induction. Moreover, we have
91
T Se 7 the + -mn. e S -e- .(1),
7
where the last inequality is because | is uniformly bounded. We also have
e e=
1 - Tuu 1 re 2 0.5 min(1, e Wi + 0.5 min 1w
2 0.5 min(1, (1, e r tie + e e
e m 2 0.5 min (1, e > = 0.5 . e_
where the third inequality because e e + e 2 1 and the last equality is hecause wi 2 0. Putting these together, have
9t ~
(1)) + Wi+1 R We 17 Yw (1) + = log(t)/> (2)
Step 3: 9r exp(-rwx) VG(ū,). We turn back to the non-separable subspace. Note that gr is an odd function of We- Without loss of generality, let us assume i 2 in this part. Notice that
1 1 is decreasing function of t 2 0. for every fixed 1, f(t) = L 1+1/a 1/a
(3)
+ a
Then we have
0t
S 6
=: =
Yeu VG
6 + e e- e->w; + e/
e-
e
where the inequality is by (3) and G(w) = e0 + + is defined as in Theorem 4. D) On the other hand, since |wa] is bounded and w, is increasing (and tends infinity), there must exist time to such that e v S e- for every t 2 to. Then for t to we have
9t y
2 E 7
r + C-
e- e.
2e-mh
e- th
c.a
et
10
-wr e e
1
Y yws
-wr VG(w.),
2e
28. +2
where the first inequality by ( and Tw, e Wy 2 0. Putting these together, and using 2), we obtain that
8. and the last inequality because we assume
for every 2 to, Wx+1 = w. " (GW)), where n R - 0 (4)
Step 4: modified descent lemma. Using and Taylor's expansion, we have
for every 2 to. G(w++1) & G(wr) - [VG(( 2 vi |IVG(()) G(w,) + 0(1)
t²
where 8 = sup m|x (ool).)) ||PG(T)) (11) Taking a telescoping sum from to T, we have for every T 2 12 for G(är) < G(w,) + O(1)/t.
(5)
Step 5: the convergence of w. Choose S. = arg min G(.), then
What remains is adapted from classic convergence arguments.
| v. 2.11 11 = ||;; w. 2n - (w) - -f -VVG(()))
< || 10; w.l3 2n: - C(t))) t t2 to.
-

---

where the equality is by } and the inequality is because of the convexity of G(-), (,yy] S ( and Taking telescoping sum, we have
T
T
2n - (G(w;) - G(w))) & 11:00 1. -1.
11 +
0(1)es
t=to
t= kg
Combing the above with 5 and using N 0(1)/t from
we get
T
T
th (G(wT) - G(w.))
Th (G( G(w.))
Σ
001)15
Am
tmto
tm
Finally, since Σ t=to Nt 2 (1) (log(T) - log(to)) according to we get that G(wT) (((0r)--)(o))) ((L)/(log(T)) log(to)).
Step 6: risk convergence. The long-term risk convergence result can be easily established by making use the implicit bias results we have obtained so far.
Conclusion
We consider constant-stepsize GD for logistic regression on linearly separable data. We show that with any constant stepsize, GD minimizes the logistic loss; moreover, the GD iterates tend to infinity when projected
max-margin direction and tend a fixed minimizer of strongly convex potential when projected to the orthogonal complement of the max- max-margin direction. We also show that GD with large stepsize may diverge catastrophically if the logistic loss replaced by the exponential loss. Our theory explains how GD minimizes risk mo-mooooonicall..
Acknolwdgement
We thank the anonymous reviewers for their helpful comments and Alexander Tsigler for pointing out several typos. VB is partially supported by the Ministry of Trade, Industry and Energy and Korea Institute for Advancement of Technology (KIAT) through the International Cooperative R&D program. JDL acknowledges the support of the ARO under MURI Award W91 INF-1 1-1-004-- the Sloan Research Fellowship, NSF CCF 2002272, NSF IIS 2107304, NSF CIF 2212262, ONR Young Investigator Award, and NSF CAREER Award 2144994.
References
Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi, Yin Tat Lee, Felipe Suarez, and Yi Zhang. Learning threshold neurons via the" edge of stability". arXiv preprint arXiv:2212.07466, 2022a.
Kwangjun Ahn, Jingzhao Zhang, and Suvrit Sra. Understanding the unstable convergence of gradient descent. International Conference on Machine Learning, pages 247-257. PMLR, 2022b.
Maksym Andriushchenko, Aditya Vardhan Varre, Loucas Pillaud- Vivien, and Nicolas Flammarion. Sgd with large step sizes learns sparse features. In International Conference on Machine Learning. pages 903-925. PMLR, 2023.
Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge of stability in deep learning. In International Conference on Machine Learning, pages 948-1024, PMLR, 2022.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally margin bounds for neural networks. Advances neural information processing systems, 30, 2017.
Peter L. Bartlett, Philip M Long, and Olivier Bousquet. The dynamics of sharpness-aware minimiza- tion: Bouncing across ravines and drifting towards wide minima. arXiv preprint arXiv:22 2022.
10

---

Lei Chen and Joan Bruna. On gradient descent convergence beyond the edge of stability. arXiv preprint arXiv:2206. 2411:222... 2022.
Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. International Conference on Learning Representations, 2021. http:: ottp://ppeeeeeeeee.eeerrrraadaad -h-TtkkGe-
Alex Damian, Eshaan Nichani, and Jason D. Lee. Self-stabilizatiion: The implicit bias of gradient descent at the edge of stability. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022
Workshop), 2022. URL http:/ttt///oppeeeiieeee wwwp::/eoooouududdddooooo... Kp7Dz
Mathieu Even, Scott Pesme, Suriya Gunasekar, and Nicolas Flammarion. (s) gd over diagonal linear networks: Implicit regularisation, large stepsizes and edge stability. arXiv preprint arXiv:2302.08992, 2023.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv:1706.0288 006777777007777 2017.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841 PMLR, 2018a.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent linear convolutional networks. Advances in neural information processing systems, 31, 2018b.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 1803v:/803.07300 2018
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019. URL https:// net/
foormmidd=Hffgg000
Ziwei Ji, Nathan Srebro, and Matus Telgarsky. Fast margin maximization via dual acceleration. In International Conference on Machine Learning, pages 4860-4869. PMLR, 2021.
Lingkai Kong and Molei Tao. Stochasticity of deterministic gradient descent: Large learning rate for multiscale objective function. Advances in Neural Information Processing Systems, 33:2625-2638, 2020.
Itai Kreisler, Mor Shpigel Nacson, Daniel Soudry, and Yair Carmon. Gradient descent monotonically decreases the sharpness of gradient flow solutions in scalar networks and beyond. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17684-17744. PMLR, 23-29 Jul 2023.
Guanghui Lan. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein. and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.002215 2020.
Chunrui Liu, Wei Huang, and Richard Yi Da Xu. Implicit bias of deep learning in the large learning rate phase: data separability perspective. Applied Sciences, 13(6):3961, 2023.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020. URI. htt./httts:://pperririe www.oormmdddsedl.....

---

Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the generalization benefit of nor- malization layers: Sharpness reduction. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave. and Kyunghyun Cho, editors. Advances in Neural Information Processing Systems, 2022. URL
https://openrevier net/ http://iiwe.eeeeetmmmidii/aaae aate/fooommmixxp33327322
Chao Ma, Daniel Kunin, Lei Wu, and Lexing Ying. Beyond the quadratic approximation: The multiscale structure of neural network loss landscapes. Journal of Machine Learning, 1(3):247- 267, 2022. ISSN 2790-2004484 doi: https://doi.org/ httg///..400mmll 0..4288/ml..2444444 URLhtttp://glooal-ee ote//nttzo/arricll__tttaallii//
htmll.html html
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexicographic and Septh-seesitivve margins in homogeneous and oon-homogeneous deep models. International Conference on Machine Learning, pages 4683-4692, PMLR, 2019a.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-3428. PMLR, 2019b.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3051-3059. PMLR, 2019c.
Yurii Nesterov al. Lectures on convex optimization, volume 137. Springer, 2018.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PaC-bayesian approach to spectrally-normalzzed margin bounds for neural networks. In International Conference Learning Representations, 2018.
wwt.:eett/ooooee formmf/ Sid=iiid_iiieee WfbCZ
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2872-2878, 2018
Yuging Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate tames homogeneity: Convergence and balancing effect. In International Conference on Learning Representations, 2022a. URL
Zixuan Wang, Zhouzi Li, and Jian Li. Analyzing sharpness along GD trajectory: Progressive sharpening and edge of stability. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022b. URL https://openrevier wwt./eet//ouu wtt.://rmmnidtttIttttrrree.-
Lei Wu, Chao Ma, et al. How sgd selects the global minima in pee-pparaeteriized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 31, 2018.
Chen Xing, Devansh Arpit, Christos Tsirigotis, and Yoshua Bengio. A walk with sgd. arXiv preprint 1802:.8802.081 2018.
Xingyu Zhu, Zixuan Wang, Xiang Wang, Mo Zhou, and Rong Ge. Understanding edge-of-stability training dynamics with minimalist example. In The Eleventh International Conference on Learning Representations, 2023. httthtttt//ppeette pttpppprrroennee/ooooorrtttgaaap
12

---

A On the Equivalence between Theorem 4.1 (.1 and ①
Note that w in ①1) contains components in both the max-margin and non-separable subspaces, and we need to disentangle those two components.
Under the coordinate system that defines P and P. represent vector v E IR as
v (P(v),P(v))
Then for i E S, we have
Vi (x,, w) = y ((P(x)), (P(w), (P(W)
= V1 P(x:) P(w) + + (P(xi), P(w))
since P and P are orthogonal
->P(w) + Vi (P(x:), P(W)).
since y;P((;; for E
So T is equivalent to for every i S 1 exp (- (W)) exp yi (P(x,), P(w))) = as..
Recall that Ess a; 1/>² according to Definition the following condition on P(w):
So focusing P, the above is equivalent to
a x exp ( y (P(x,), P(w))), i
(6)
Here ignore shared normalization factor.
Now, recall from Assumption B that (as)ses are such that
Σ a: DiXi, ag 0.
Note that as long as Eies 1/72, ? we have
P(w)= Σ au viP())
1 72 7
ES
Now consider P. Note that P(w) = by the choice P, then apply P on both sides of the above equation, we get
0 = P(w) Σ a4 P(x:).
(7)
SE
Under 77 6 is equivalent the following condition on P(w):
0 Σ exp V1 (P(x,), P((:).
which is precisely the first-order condition of P(w) E arg min G(.), where G(v) Σ exp yi (P(x:), v)). iES
Hence we have shown that: the condition that w satisfies minimizes the strongly convex potential G(-).
is equivalent to the condition that ((w)
B The Behaviors of Constant-Stepsize GD
B.1 Notation Simplifications
Without loss of generality, we assume that
= 1, i = I,...,n.
Otherwise, we replace ys with 1 and x, with ys x,, respectively, and the following analysis does not change.
Then the risk becomes
L(w) = Σ
log(1 1 + -w- xxx)..
1=1
13

---

Rotating the hard-margin SVM solution. Note that the (GD) iterates (under linear models) are rotation equivariant. Specifically, let R be an orthogonal matrix, then applying on both sides of GDD), we obtain
n
Rw++1 = Rw; +1 77
Σ
(1 - s(x; wi)) Rx,
i=1
Rw, + 1) Σ (1 s((xx)) (Rw:))) Rx;,
which is equivalent the GD iterates under changes of variables, w f- Rw and x Rx. Therefore, without loss of generality, we can apply a rotation to the dataset such that w || e1. Then for v E Rd
Pv
Pv v(2 d] E R=-1
Slightly abusing notations, in what follows we will write
x; (Ia 81) T E EROR-1, I,..., n
where
T x;
8; = of Rd-1
Similarly, we define
w w (w, W) E R R
Then have
x w T; x! W.
So the loss can be written as:
L(w, w) = Σ
log(1 + - &.).
1=1
So GD
can be written as:
WD 0,
W: = Wt-1 - 17- II Wr-1), 82 1;
(8)
Wo 0, W: w.-1 77 (wL(wi11,:--))
t 82 1.
The above two recursions capture the GD iterates projecting to the max-margin and non-separable subspaces, respectively.
B.2 Boundedness GD the Non-Separable Subspace
We first show that (Wi)120 stay bounded for every fixed stepsize 17. Lemma B.1 (Positiveness of wy). Suppose that Assumption holdds holds. Consider (wx):20 defined by (8) with constant stepsize 1j > Then every t. 0, it holds that w, 2 0.
Proof. Recall that
Wig 0, Wi Wt-1 - 77 V (W, 12 1.
We only need to show that L(W, w) < This because
V L( w)
+ t x; 32
0.
since 2; 2 2 0 by Definition
14

---

Lemma B.2 (A recursion of (ele))) Suppose that Assumptions 1 2 and 3 hoold. Consider (We)c2o
defined by (8) with constant stepsize rj O. Then for every 2 there exists j E [m]] such that
b. [[oll2) +
w well
2ne W.7 #ne.
n
+ cn (m² b. (welll)
As a direct consequence,
|well2 2 max mn²/bb implies that || S |wll2--
Proof. We first make a few useful notations. Fix a time index t.
Let le be the index of the "most negatively classified" support sample, i.e.,
== arg min ((w., x:)) ES
then by Definition 2 it holds that
(w,, Xx) S -. ||wlle
(9)
Let j be the index of the "most negatively classified" sample, i.c.
j = arg min {wyn; + (Wr, 8:)) 1si5n
Then
wrZ + (W., S Wpi; + (We, x:) for every E [n]].
(10)
In particular, must have
(w,, S wellw.
(11)
since
WEY + (We,
I wy + (W,, Xz)
by Definition
S min (waz + (W,, x.)]
by T0
w + min (Wr, x;)} iE8
by Definition
< wxy b Wr
by Definition
We remark that it is possible that l Step an iterate norm recursion.
Recall that
W = We 1/ (wr,, we). Ve we) =
Σ euizitW &i x,-
Then
[ |well - 2n (We, V L(w, wil) + +1²
V LwL(we (wL(W,, we)l
Step 1: gradient norm bounds. By definition, we have
VwI[ww, w:)ll2
+ twa x
||&:112
+ e 1 &:
by Assumption 2
+ [ &
7
by 10
(12)
West -W. &
15

---

n.
(13)
Here, we use property of logistic loss that the gradient uniformly bounded. Therefore, we have
[Vw. L(r. will - 1 + (wenstw[xs
Vv,, L(w,, we)ll
by
by
(14)
+ Ew
Step 2: cross-term bounds. We aim to show that the negative parts in the cross-term can cancel both the positve parts in the cross-term and the squared gradient norm term.
Note that the following holds for either j = is or j +
(e: we L(w,, wx))
1
W. X;
+ uiz, w/ x;
1
W &;
+ ewezit w/ x;>0
(15)
1
1
w, xj
We Xg.
2
+ elezy
1 1 ewiskt
The first term in 115 can be bounded by
x;
tw &
W 2,50
Σ
w &;
+ e
w. x,50
Σ
since é 1151
1 1
wizi w.zi
w, x:>0
W. 8,>0
ne -Ym
since n, 2 y for E [x]]
(16)
The second term in 115 can be bounded by
1
-b. Welll
by
(17)
2 + tw, x
2 + + x;
The third term in (15) can be bounded by
b. Well
Rx
by and the choice of A
2 + t
1 1 +w Xx.
-b. Wellz
e wey
2
w- + w. Xx
b ||lll
wxx
since e - --n, w.Txx 2 (18)
2
since
wry 2 O,
by Lemma B.
W; X2 S 0.
by the choice of
Now, bringing (6).
17
and 18
into 15
we obtain
w l|
b |
- -(w,, Vw, L(w, w))
(19)
4
2
I ewerttW. &,
Here, we use a property of logistic loss that the gradients from incorrectly classified samples dominate the gradients from correctly classified samples.
16

---

Step 3: iterate norm recursion bounds.
Using 14 and 19 we can obtain
W 11 = w 21 (We, V L(re, We)) + 1f² V L(wi, wo)ll
1 emany w w + 2ne mey (n- b. b.1(well2) npb |well2
n²
+ r
+ ewerttw; x,
b.
Well2
= =l[wel2 + 2ne 167
n
+
euxzyt (mm b. @[]well2).
4
We have completed the proof.
Lemma B.3 (Boundedness of w). Suppose that Assumptions 7 2 and hold. Consider (We)
defined by (8) with constant stepsize > O. Then for every 2 0, holds that
well2 S W maxx == max(4n/80 npp2 /b} m..
Proof. We prove the claim by induction. Clearly, Wollz = 0 S max (onx(4n//e An/ mm2 + mp. Now suppose that
w.ll2 S max (on/b,, n//
mm² /b} + 1,n
and discuss the following two cases:
1. If [ell2 I max max(4n/ (4m/b, b, qm 2 /b}, then
We+1 12 < [w, 1|2 + ||7 V (wee, w1
by triangle inequality
< [. 17
by 13
max (on/b, nn? /b)//b]] rmn.
Else, we have
max(4n/b, mm² /6} S [elll max(4n/6, mm² mmm//// /6} + mpn,
which implies
Wettlll S Wellz
by Lemma B.2
< maxx44n (n/b, mn²/b} + mm.
This completes the induction.
B.3 Divergence of GD in the Max-Margin Subspace
Definition (Some loss measurements the non-separable subspace). Under Assumptions 1 and define the following notations:
(A) Define two loss functions
G(w)
H(w) Σ
iES
In the case where [n]. we define H(w) = 0.
(B) Define
Gmin == min G(w), weRd-1
It is clear that Gmin 2 since (X:)ies are non-separable by Definition 2
(C) Define
w, arg min G(w). wER4-1
It is clear that G(w.)= Gmin. Moreover, it holds that ||w.|l2 S Wmax by Lemma B.4
17

---

(D) Recall that |elll2 S W mmax according to Lemma B.3 We then define
Gmax
sup S max
G(w),
Hmax
sup
H(w).
W max
It is clear that
G(w)) S Gmax, (we)) S Hmax,
and that Gmax; max are polynomials on e", e", and ez/b, and are independent of L. Lemma B.4, For the w, in Definition
it holds that
log(n)
W 12.l S
W
Proof. By Definition
2 there exists j such that
w Xy -b. 1|,,122
which implies that
G(W.) Σ
c w x; 2 c w. x 2 Ch-1wwllla
iES
On the other hand, by the definition of w., have
G(w.) ) S G(0)) = n.
Therefore, we have eh Iww.lla < n, that is, /wwll 212 - (n)(n)/ I W Waxx.
We now consider (w))220
Lemma B.S. Suppose Assumptions and 3 hold. Then for every 2 0, it holds that 17 min 1, Twx .G(W))
W++1 1 2 W4
w/+1 S wi + 17. min { ym, 7. uwx G(W,) + 17 -wer H(w,)} }
Proof. Recall that
V Tw we) --w We
Wh+11 W/ -1 V.o (wo, Wt).
2,00 w.
We only need to provide upper and lower bounds on- V VuL(W,, w.). The lower bound is because:
w.
- w.)
8 We 1 + 12 W.
since 2 >>>>0 by Definition
1ES
71% x Wi
since 2; = y S
+ T We
i
2
Σ min(1, e -- [([w.
since e'/(1+e') 2 0.5 min(1,e) (1,e')
2
iES
7
min 1, e -w Σe Ex-x We
2
iES
min (1, e ym.
7m G(w.)).
2
The upper bound is because:
n
x.w w.
-ve, W.)
1=1
18

---

4, Wi
1 + -IIW -2 We
+ e 2 - Wr
IES
21
1 + 7-)
+ c -2,1 Wr
i68
igS
since 24 = for E and xy S 1 for [n]
S 7 min [1, -- wo) +
min(1, E e - Wr
ieS
since e² / + S min
S
min 1, e - we +
Σ
min {I, -ws - we
iES
since 21 2 0 for & s
< 7
MWr x Wi + Σ
Pur 8, We
iES
igs
7 -w G(w,) + Our H(w.).
We have completed the proof.
Lemma B.6 (A lower bound on w.). Suppose Assumptions 2 and 3
hold. Then it holds that
We 2 1 log
1
172
O. 2
.1
1)
As a direct consequence, holds that
2
YwE <
t 120 0.
2
1/72
Proof. Observe that
W++1 we +
77
min {1, T.e .((w))
by Lemma B.5
W/ +
m
min {1, 113
by Definition since we 2 0 by Lemma B.1
m Yw0
w/ +
(20)
which implies that we is increasing. Furthermore, we have
TWe-1 7Me Y (e7(we41--a) -1) 1)
2 rw 7(W2+1 w))
since e² - for 0, and W/+1 2 w/
2 17? 2
by 20
2
which implies that
177
ew
2 200
+
t
2
77² 2
1 +
since wo
2
We then get
1 log
m2
.1..
2
1+
t 2 O.
2
19

---

Lemma B.7 (An upper bound on wy). Suppose Assumptions and B
Then it holds that
1 log ((om" max + cryy (t+1)), t2 0.
W/ ?
As a direct consequence, it holds that
t2
Gemx + en7 (t+1)
Proof. Observe that
-Bw: (H(W,) W/+1 We S 11y yut G(),) + 1) E
by Lemma B.5 since 0 > 7 by Definition by Definition
S 117 yu -(W,,) + +17 17.10000 nwe. (w:))
S 1) (7Gmax Hmax)
yu
(21)
Let
to = min {t mn- (7G + H mmxx)
~ 7wh S 1}.
Recall that we increasing according to (20) So have
1
for S to.
" log Gmax + 17, Hux))
(22)
for 2 to. and 23 together imply that
m (mGmax + Hmax) - 714 < 1.
(23)
for t 2 to.
0 S 5 (We+1 w,) $ 1.
(24)
Then for & 2 to, we have
y 11 yw ew (6 -1)
e e ((W++1 - we)
by 24 and that e¹ - -S
I
+ Hmy.
by
which implies
e T + (em + Hmx)) to)
I 2m² + H7 max + (enr?Gmaa + esyy H Hmax) -t - to)
by 22
< ( en Huxx) (t 1).
Therefore, for t to, have
7 log (eem? Gmax enyyy (t (t++)) 1)).
1
Note that the above also holds for S t S to according to
22 We have completed the proof.
B.4 Convergence of GD in the Non-Separable Subspace
We show that the vanilla gradient on the nenssebaab subspace, V (w,, Wt), can be understood as the gradient modified loss with rescaling factor, e vur VG(w,), ignoring higher order errors.
Lemma B.8 (Gradients comparison lemma). Suppose Assumptions that
7 and 3 hold. Then it holds
V L(w,, w.) - - rw.. VG(w))ll S -2rwe Graxx + e Ow. Hmaxs
t t2
As a direct consequence, for every vector v E Rd-1, it holds that
(v, V Lw Wi))
VG(w)) || (e 2ymn P + e Ohei -mma))
-2ym,
20

---

Proof. Recall that
Vwl(wr, = - 1
X;
VG(w,) = Σ
Wi x; X;-
168
By the triangle inequality, we have V w [wr; we) yu VG(::)l
--wey & 1 e We w.
WA W. &
- &
X;
+
West W, x;
IES
igs
-er X1
w
x;
(25)
iES
+ e w
igs
6
W. X,
The ( term can be bounded by
Tu W 22
&
since 2ú = for i E S
ywu w.
iES
&
rw w &c Xi
c ywu W. &
EES
2,
Σ
2w. X;
1 + E -
iE8
< 27wr.
2w &c. |2:112
by triangle inequality
+ e -- W. Xx
iES
2Y
Σ
-e- 2w|xx x;
since ||& S by Assumption
+ e 2-7We--.a
iES
< 2Twr Σe
2w.'x 8;
iES
< 2mw..
Σ
e
w. x
iES
e 2yw, G(w.)²
< e 2Yw..
G2 Gaase.
by Definition S
The (9) term can be bounded by
Wia w. x;
(0) = Σ
W.s w. & 8; 2
iES
Weary w. xx
||x,11
by triangle inequality
wi:: w.
S
We Te. &
since ||x:||2 S 1 by Assumption 2
Wep w.
w.
S
e Bwi
T; 2 0 >>> 2fr i 4
$45
Own
H H(W)
21

---

Se- Owte Mmxx
by Definition
Bringing the bounds on the and (V) into 25 we obtain
V [ww, W.) e - VG( (
S e 2 G e Owr maxx 1 0.
We have shown the first conclusion. The second conclusion follows from the first conclusion: for every IR-1 (v, Ww wi) - (v. VG(w)) + (v, VwL(wr, we) - 7m VG(ww))
Se Se-wwi (V. VG(w)) + || [W W.) E -- .GG(w)llz
S ee (v, VG(w)) + ||vl22 (e-2yur
2y Guax Bwr Hmma))
We have completed the proof.
Lemma B.9 (A gradient norm bound). Suppose Assumptions
and 3 hold. Then it holds that
V Lw,, we)ll2 I ~, (Gmax + Hanx),
t t2 0.
Proof. The inequality is because:
10:: W. &
V w. L(wr, w
Σ
X;
11: WW, W.
Wedt W. X1
|
by triangle inequality
Mi:i w.
Welle W &
since ||x:|22 S by Assumption
10.2 w.
Se-rww
w.
for i for since 2; 2
[n]]
Y
(G(w.) + ((w)))
S 70h (Gmax + Hmax).
The next lemma shows that the function value is "non-increasing" ignoring higher order terms. Lemma 1.10 (A modified descent lemma). Suppose Assumptions
2 and 3 holld Then it holds that
G(W++)) I G(w.) - 2(1 + 172) -max (Grax + H (e 27we + e -0w)), t 0.
As a direct consequence of the above and Lemma B.6 holds that
G(W+++) S G(w.) + co 2(1 + G
((t (t-
k k 0,
where 8/7 > by Definition| and is polynomial on ee,,e",e el!// 1 1 1 independent of f, given by
nn' 8- 7 e17
and is
(
8/7
= 17 (Gunax + H2 H2nx))
0 0-7
max
(1722)
1772
1n
Proof. Note that
[VPG(W)]22 Ee x
2
22

---

xi x w
by triangle inequality
158
W
x;
since |x:||2 S 1 by Assumption 2
iES
G(w).
Recall that [w S Wmax- So we have
sup /
sup
GV
sup wllaSW
G(w)
(26)
w man
Then we can apply Taylor's theorem to obtain that
Gmax
G((e+1) & G(w.) + (VG(W.), W - -w.) +
[We+1 - well2
by 26
2
G Gmax
G(w,) - (VG(w.), V L(we, w.))
|/ L(w,, w.)
Next we use Lemma B.8 with v (w:) to get The cross-term is bounded by
- (VVG(w,), Vw wi))
S -e- |V |VV(( (e-2yur G + e Bwr Hmax)
T --
S --
Gmax (e- 2xurr Gr + te-
Buc Hmax).
by 26
Using the above and the gradient norm bound from Lemma B.9 get that
G(W++1) S ((w:) ne rw; |[VG(w.))l
+ ne 2yw. G + ne Ow: Gmax H + 1/2 2210 (Gmax + Hmax)) )²
2700,
< G(w) + ne 2y G + ne ne- Giuax Hmax + ri²e - (Gmax + H Hmax? )²
- ((,) + 2(7 + 17²) Grax (G + H²max) (e 22y + e e-0wr))
where in the last inequality we use that Gmax 2 Gmin 2 1 by Definition 3 From the above we have
s+t
G(WL+R) S SG(,) + 2(17 + r²²) Gmax (G max
H max
(e 2yw, + +c- -ww...
(27)
s=t
The summation small by Lemma B.6 because
+ A
2yw. + -
2
+
by Lemma B.6
2 + 17?
2
+ 1
2
s=1
s=1
stb
*+
2
2
?
1
2
(t 1)1-3
(t
1)-11
by integral inequality
1
-1
2
2
2
8/4
(t (1-1))-1 (t- (t-1) 9))
< max
1
7
Inserting the above into
27
completes the proof.
We now prove the convergence of the iterates projected on the non-separable subspace.
23

---

Lemma B.11 (Convergence on the non-separable subspace). Suppose Assumptions Then holds that
and 3 hold.
G(WT) - G(W.) S (T)
T 3,
where e₁ > 0 is polynomial on {e", et et/b, ee
- and is independent of 4 1/ 8- e/7
Proof. The proof is conducted in several steps.
Step I: one-step function value bound.
Observe that
Wo+1 w. 12 W: w. + (Wr W., We+1 Wo) + || w.
W: W.
2n (we W.: V Lwu, we)) + +n²² VV Lwr, w. w:)
For the cross-term, apply Lemma B.8 with -(we w.) to obtain
Ww W.: V L(w,, we))
- ruu. (w, w., VG(w:)) + W - -w.12 (c-2yu G e c-Our -maxx)
S ruu. (W: W.. VG(w.)) + (Wimx + || (E 2y G maxx + -- -w.. Hmax)
- - yws (W; - W., -w. VG(W:)) + 2W max (e- G2 max + -0we Hmmxx)
where the second inequality is by Lemma B.3 and the last inequality by Lemma B.4 Using the above and the gradient norm bound from Lemma B.9. we get that
W w. We 1 2qe yo (w, W.. VG(W)))
4n W Wmaxx (e 2ym0s P +e ---0i Oie H max)
(28)
+ 1)2 e 2/we. (Ginax Hmnax)?
By the convexity G(.), we have
(we W., VG(w:)) 2 G(w.) -(W.))
(29)
So we get
2qe 7 (G(w.) - G(w.)) < 2ne 7wat :W, w., VG((w.)
by 29
< W/ w.1l2 - | w w.ll2 112
4n W (e -2-ya G + --we H Hunxx)
172 2yw. (Gruxx + -I
by
< W w. | W. 112
+ 6r W Wmax
(G + Hmax)
(e-2 + e --uw))
(30)
where we use Wmax max/4n/b, m7² m /b} + mmn in the last inequality.
Step the sum of function values stays bounded. Observe that
T
2
2
4
2ym + e -ww) <
+
by Lemma B.6
2+
1
2
17
2
T
T
+
1
1772
1=2
1=2
2
2
-1
1
177
0/7
2
2
0/4
0
< max
(31)
1172
?
24

---

Taking telescope summation over 30). we obtain
2me you (G((ws) - G(W.))
S || W2 w.1l2 ||T+1 w.
T
+ 61 W Waxx (G H Haxx)
(e
2ywe + +c-
by 30
2=
2
2
8/7
$ 2W max + 6n- max (G + H
maxx
max
177/
177
by
2W max
18W max Co
where
0
2
2
8/7
Co := 17 (G + H maxx
max
0 7
1772 ,
m7
a constant (a polynomial on {e", ,e,,, 1/6b ni¹ 8-71 7. e//r and is independent of t) defined in
Lemma B. 10
Step 3: function value decreases, approximately.
For T 2 2 1, we have
G(wT)= & G(w,) + 2(1 + n)) (1t (1--))- + (t - (t-1)² +)²
by Lemma B.10
which implies that
2ne YWk (G(Wr)) G(W.))
2np 7 (G(w:) G(w.) + 2ne >mm .cp 2(1 + G (1-1)-- 1 + (t 1)--
2ne 7 (G(w)) G(w-))
+ 21 2 + mn . 2(1 + G))x
(1--)--++0 + (11-1)=-3
by Lemma B.6
2ne ww. (G(w)) G(w.) (w.) + 8(1 + m)co
(11 (1-1))2+(1-1))
(32)
22
Step 4: the last function value is small. Taking summation of
32 over t 2.... T, we get
2ne 7w.
(G(W))
T
(G(w,) G(w.)) + 8(1 + n)co
<
2ne -ym
(1-1]
(1 1)-
72
1=2
1=2
(G((s)) G(w.)) + 8(1 + n)co
1
<
Y
12+1+
22
0/7
2m
8(1 + 1)c00
30
< 2W max
18W max
+
by 31
72
7-7
We also have
T
T
by Lemma B.7
en G + exyy Hmax
/+1
t=2
1=2
> 2 + Hmyx
(Iog(T 11) log(3))
25

---

Putting these together, we get
8(1 + +1cco
30
en + exjy
G(Wr) - G(W.) $ 2W max + 18W max co +
y2
0 --7
log(T (T + 1) - log(3)
where
0
2
2
2
0/7
cg = 7. (G + H maxx
max
,
is a polynomial on {e", e", e",,/ 1 L 1
E So for T 2 3, we have
" 0-9- 7:
1
G(WT) G(w.) 5 log(T) C15
where 61 is polynomial on {e", e", e2/b 1
"7' 8- 2, 1 } and independent of T.
C Proofs Missing from the Main Paper
C.1 Proof of Theorem
Proof Theorem
Theorem
a consequence of our analysis in Appendix
(
is because of Lemma B.3
B
because of Lemma B.6
D
because of Lemma B.1
A is because of the following:
I(w,)) =
log(1 + eexp-=wxa - w,Tx)) x,))
t=1
<
exp(- - Wit - w, xi)
i=1
< exp( (- 7)
exp( - w x;)
S le/lo(tt),
where the last inequality is because that
2
exp( We
2 2
by Lemma B.6 and that Em= exp( w. x;) uniformly bounded by a constant by Definition 3
C.2 Proof of Theorem
4.2
Proof of Theorem 4.2 The GD iterates can be written as
W++1 w. + my TW: (e- e.,),
(33)
Wt+11 = Wt - B71 7 (e 0 e.))
(34)
We claim that: for every t 2 0,
1. wy 2 0.
2. 17: 1.
3. | > 2
26

---

We prove the claim by induction. For = 0, it holds by assumption. Now suppose that the claim holds for and consider the case t + 1.
1. Wh++1 2 0 holds since wx+11 2 We by (33 and wt by the induction hypothesis.
2. |0 2 1 holds because
W2+11 2 n/
TWe
10
by 34
since [0y] 2 and that ex e-t 2 ol
1/e 1M4
|
for t 12 1
2
(35)
2 2e
16.6 --w
[rr
since 17
2 4
| 2 Y
2 2e 5,1/2
1,1/2
10g
since
2
21.
since 2/2 2 + for e R
3. To prove that |w++1| 2 2y first observe that
WM41 W/ + my e 7m -e-- =
S Wi + 177 - 7 2 22 m11
(36)
Then we have
i++1| - 2yw++1
1/0 7 e |
|Wie| 27
Wt + 177 - 2 elaal
by 35 and 36
2
(1 - 872).
/ --w
|Wxel 2yy
2
2 /0/ 1 | 2
since 1) 2 424 2/(1 8-22)
| -000 |0,1
since W; 2 0
since |0:
A IV 1//1/2 [
2 7
2
since e/2 2 for t IR
We have completed the induction.
Finally, we prove the claims in Theorem 4.2 using the above results.
B
because of
W/-1 2 We + 177. vw
from 33
We have already proved by by induction.
To show (D) without lose of generality, let us assume W7 2 0, then
1t+1
< 00
1/0
7
le v
1
by 34
el m=1
since [ 2 1 and that c¹ -ct e¹
11 17c
for 2
2
S 02 2e
h0 77
since 17 2 4
[wp]]
< W 2e /22/2
since 2
2 700
1.
since
2/ t + 1 for e RR
We repeat the above argument show that 11-1 0 0.
27

---

10
10a
n= 0.1
101
n=
10a
10-4
nomalized
10
10-2
10
9.0.01
2000
4000 Iteration
6000
10
4000
8000
10000
Iteration
(a) Training loss
(b) Normalized margin for homogenous network
Figure 3: The behaviors of GD for optimizing homogenous neural network. The experiment setting follows that of Figure in the main paper, except that disable all hias parameters that the neural network is homogenous (Lyu and 2020]. The sub-figures (a) and (b) report the training loss and the margin along the GD trajectories, respectively. Here, we follow Lyu and Li (2020) and measure the normalized margin by min(x.)) (J(x; w.) y max,''v [xx; wv)lv]] [w where ((::) refers to the homogenous neural network, L = 4 is the depth of the homogenous neural network, w, is the weight at the (-th GD step, and (.,) taken with respect all training data.
To show A
we apply wt - Do and that |atel 2 2ywr:
L(wi, w.) e ~m (e th + me
7u0 el
2 e uh - 00.
We have completed all the proofs.
D Experimental Setups
Neural network experiments. We randomly sample 1, 0000 data from the MNIST dataset as the training set and use the remaining data as the test set. The feature vectors are normalized such that each feature is within [-.
We a fully connected network with the following structure
784 ReLU > 500 + ReLU - 500 ReLU 500 ReLU - 10.
The network is initialized with Kaiming initialization. We use the cross-entropy loss.
We consider constant-stepsize GD with two types of stepsizes, 77 0.1 and r) 0.01.
The results are presented Figure
Logistic regression experiments. We randomly sample 1, 000 data with labels "O" and "g" from the MNIST dataset as the training set. The feature vectors are normalized such that each feature is within [-,,1].
We linear model without bias. So the number of parameters 784. The model is initialized from zero. We use the binary cross-entropy loss, i.e., the logistic loss.
We consider constant-stepsize GD with various stepsizes.
The results are presented in Figure
Additional experiments. We conduct additional experiments on the margin maximization effect of large stepsize GD homogenous neural network. Results are presented in Figure
httt:://yann.. http:///aaa..eea..co/////ee/////
28


Reviews:
[{"review_id": "C8SLa9phg3", "reviewer": "Reviewer_rZLX", "summary": "This work investigates the implicit bias in linear regression with logistic loss with large learning rates. It shows the convergence result of logistic loss for any learning rates, as long as an counter-example of exponential loss to show the gap between these two losses.", "questions": "As above in weakness.\n\nTypos & minor suggestions:\n1. below 299: it is $\\nabla G$ instead of $G$ in the inner product.\n\n2. in Figure 2, the bound of $2/\\eta=0.2$ can be plotted in a more clear way, such as log.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation and setting are good: large learning rates (i.e., Edge of Stability) are a rising topic recently. As pointed out by the authors, it requires reconsideration of previous results of implicit regularization with small learning rates. To my knowledge, this work is the first to redo one of the bias results in the standard setting.\n\n2. The gap between logistic and exponential losses is good: typically implicit-bias works handle these two similarly, but this work shows that logistic loss can contain arbitrarily large learning rates while exponential loss has an upper bound.", "weaknesses": "1. The covered setting is somehow simple in lack of detailed discussions of what impact logistic loss + large learning rates have on more complicated settings possibly. For instance, does the max-margin bias in deep homogenous model (Lyu and Li) hold any more? This kind of impact could be verified with visualized experiments, with the theoretical development left as future works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, suggestions, and positive evaluation. Please find our answers to your questions below.\n\n---\n\n**Q1**. “The covered setting is somehow simple in lack of detailed discussions of what impact logistic loss + large learning rates have on more complicated settings possibly. For instance, does the max-margin bias in deep homogenous model (Lyu and Li) hold any more? This kind of impact could be verified with visualized experiments, with the theoretical development left as future works.”\n\n**A1**. Please see Figure 4 in the attached rebuttal PDF for the suggested experiments on a homogenous deep neural network. Figure 4 is consistent with the results of [Lyu and Li, 2019], showing a margin-maximization tendency of GD with both large and small stepsizes for homogenous models. We will incorporate these into the paper in more detail.\n\nWe agree that extending our results from linear model to more complicated models such as homogenous models is an important future work direction. However, even in the simple logistic regression setting, there is no such kind of result before our work. Without a full understanding of large stepsize GD for the simplest possible problem — linear model under logistic loss — it seems unlikely that one can achieve this in more complicated models. As our work is the first work on the implicit bias of large stepsize GD, we believe we have taken an important step in this direction and the contribution of our work is very significant.\n\n---\n\n**Q2**. “Typos & minor suggestions…”\n\n**A2**. We will fix the typo in the equation below line 299. We have changed the linear scale of the y-axis in Figure 2(b) to a logarithmic scale to improve readability. See Figure 3(b) in the attached rebuttal PDF. We are happy to incorporate any additional suggestions you have to improve our paper!\n"}, {"review_id": "o6oRo94Zel", "reviewer": "Reviewer_pcDT", "summary": "This research investigates the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime. The authors assert that despite local oscillations, the logistic loss can be minimized by GD with constant stepsize over a long time scale. \tExperiments on neural networks and logistic regression verify the theory and illustrate the non-monotonic convergence and implicit bias of GD.", "questions": "How to define linearly separable in neural network literature?\n\nIt is clear that when you use a large learning rate, the neural network goes far away from the linear regime. How can you make a compensation to use the current model to understand the non-linearity in neural networks?\n", "limitations": "This work makes valuable theoretical contributions but has limitations in terms of connection to practice. Extending the analysis to address these limitations remains an open challenge.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Provides novel theoretical analysis of GD allowing constant step sizes, complementing existing theories requiring small step sizes. This better matches practical deep learning where large steps are used.\n- Establishes implicit bias results for GD with any constant step size. Shows GD aims to maximize the margin regardless of step size.\n- The analysis technique of decomposing GD iterates into orthogonal components is innovative. It allows handling large step sizes that cause loss oscillations.\n- Experiments on neural networks and logistic regression align with theory and illustrate non-monotonic convergence and implicit bias.\n- Shows logistic loss is better behaved than exponential loss for large-stepsize GD, providing practical insights.", "weaknesses": "- The analysis is limited to logistic regression on linearly separable data. Extending it to more complex models like neural networks is not clear.\n- Some assumptions made, like linearly separable data and non-degenerate support vectors, may be restrictive and not hold in practice. For example, wrongly labeled samples are common.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating our contributions including a novel theory, new techniques, and practical insights. We address your concerns below. \n\n---\n**Q1**. “The analysis is limited to logistic regression on linearly separable data. Extending it to more complex models like neural networks is not clear.”\n\n**A1**. Extending our results to more complicated models is an important future work direction. However, even in the simple logistic regression setting, there is no such kind of result before our work for GD with large stepsizes. Without a full understanding of large stepsize GD for the simplest possible problem — linear model under logistic loss — it seems unlikely that one can achieve this in more complicated models such as neural networks. As our work is the first work on the implicit bias of large stepsize GD, we believe we have taken an important step in this direction and the contribution of our work is very significant.\n\n---\n**Q2**. “Some assumptions made, like linearly separable data and non-degenerate support vectors, may be restrictive and not hold in practice. For example, wrongly labeled samples are common.”\n\n**A2**. We emphasize that Assumptions 1 and 3 are standard conditions made by prior papers, e.g., the pioneering work on implicit bias by Soudry et al. [2018]. Therefore, our novel theory development is not based on more restrictive assumptions compared to prior works. Extending our results to cover wrongly labeled samples is an interesting direction, which we will comment on in the revision as future work! \n\n---\n**Q3**. “How to define linearly separable in neural network literature?”\n\n**A3**. The linear separability condition can be generalized to a “separability” condition in (homogenous) neural network cases, that is, there exists a (homogenous) neural network that achieves $100\\\\%$ training accuracy (see, e.g., Section 1.1 in [Lyu and Li, 2019]).\n\n---\n**Q4**. “It is clear that when you use a large learning rate, the neural network goes far away from the linear regime. How can you make a compensation to use the current model to understand the non-linearity in neural networks?”\n\n**A4**. For homogenous neural networks, which are far away from a linear model, Lyu and Li [2019] and Nacson et al. [2019a] prove that small stepsize GD converges to a max-margin solution (under a revised definition of “margin”). We conjecture that our results for large stepsize GD for logistic regression can also be extended to homogenous neural networks in a similar way. In Figure 4 in the attached rebuttal PDF, we provide numerical results on a homogenous neural network, which are consistent with Lyu and Li [2019] and support our conjecture. We believe this is an important future direction and will discuss this in detail in the revision.\n"}, {"review_id": "jtOOmyXaAu", "reviewer": "Reviewer_iDYE", "summary": "The paper studies the convergence of gradient descent with large step sizes beyond the classical stepsize suggest by smoothness-based convergence. Across the iterates, the risk here exhibits non-monotonic behaviour and yet converges in the long range.  To show these phenomenon, the paper rigorously studies the gradient descent with large step-size in the case of logistic regression with linearly separable data. ", "questions": "a) In the case of exponential loss, it is shown that it can diverge with a large stepsize for a simple example. Do you think there exists a sub-class of problems where exponential loss can converge with any step size? \n\n", "limitations": " ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "a) The paper studies logistic regression in the case of separable data. Even in this simpler case, the authors prove a very strong result. It is shown that gradient descent with **any** constant stepsize converges. \n\nb) For gradient descent with any step-size, the implicit bias towards the max $\\ell_2$-margin solution is shown. \n\nc) A novel proof technique was introduced to handle any stepsize and it was clearly presented with a simple example. In contrast to existing works, the implicit bias is shown which leads to convergence in risk. ", "weaknesses": "a) The proof is tailor made for linear regression and does not work beyond that for any convex functions. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our paper! We address your comments in the following. \n\n---\n**Q1**. “The proof is tailor made for linear regression and does not work beyond that for any convex functions.”\n\n**A1**. We respectfully point out that our analysis is for logistic regression rather than linear regression. Our analysis can be extended to other (convex) generalized linear models where the loss functions behave similarly to the logistic loss. For example, our proofs hold (with minor revisions on constant factors) when the logistic loss \n$$ \\ell(t) = \\log(1+e^{-t}) $$\nis replaced by a variant of the *Exponential Linear Unit*:\n$$ \\tilde{\\ell}(t) = \\begin{cases} a\\cdot (e^{-t} -1), & t \\ge 0; \\\\\\ -t, & t<0, \\end{cases}$$\nwhere $a>0$ is a constant.\nThe key properties of the logistic loss in our analysis are 1) the gradient is bounded and 2) the function value of a negative input dominates that of a positive input. We will provide a detailed explanation of these alongside our proof in the revision. \n\n---\n**Q2**. “In the case of exponential loss, it is shown that it can diverge with a large stepsize for a simple example. Do you think there exists a sub-class of problems where exponential loss can converge with any step size?”\n\n**A2**. In special situations, GD can converge under exponential loss with any constant stepsize. For example, it holds if the dataset is such that the feature vectors are orthogonal to each other. One can prove this claim by noticing that the parameter updates can be perfectly decoupled along each feature direction."}, {"review_id": "pYdfSI51ca", "reviewer": "Reviewer_PfDy", "summary": "This paper analyzes the convergence and implicit bias of logistic regression on linearly separable datasets with arbitrarily large step sizes.  The paper proves that gradient descent converges _for any_ constant step size, even those which result in non-decreasing loss curves.  Similar to the regime of small step sizes, gradient descent converges along the direction of the max-margin linear separator.\n\nIn contrast to logistic loss, the paper proves that for exponential loss there exist datasets and step sizes where the optimizer fails to converge, shedding light on why logistic loss may be preferable in practice over exponential loss.", "questions": "- Could you include some numerical examples of convergence at extremely large step sizes?  I am curious to see what the loss curve looks like.\n\n- The following recent paper should be discussed: \n\nChunrui Liu, Wei Huang, and Richard Yi Da Xu.  \"Implicit Bias of Deep Learning in the Large Learning Rate Phase: A Data Separability Perspective.\"  Applied Sciences, 2023.  https://www.mdpi.com/2076-3417/13/6/3961\n\nThe paper does not seem to be on arxiv, and the venue is not a standard one ... nevertheless, the paper is quite related.\n\nIn their Proposition 1, that paper argues that for logistic regression on _non-separable datasets_ (or, more generally, for any strongly convex optimization problem), gradient descent fails to converge for large enough step sizes. \n", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- It's interesting (and far from obvious a priori) that GD with _any_ constant step size will converge.\n- The separation between logistic and exponential losses sheds light on why the former is preferred in practice (since both losses are equivalent under the small step size regime studied in previous works)\n- The separable / non-separable orthogonal decomposition seems like it might be useful for other analyses of logistic regression on separable datasets.", "weaknesses": "- Minor: would Assumption 3 hold if the dataset were the last-layer features from a neural net has undergone neural collapse, or would such a dataset not satisfy assumption 3?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your affirmative comments! Thank you for pointing out the paper by [Liu, Huang, and Xu, 2023]. We will properly cite and discuss the paper in the revision. We will address your other questions as follows.\n\n---\n**Q1**. “Minor: would Assumption 3 hold if the dataset were the last-layer features from a neural net has undergone neural collapse, or would such a dataset not satisfy assumption 3?”\n\n**A1**. Under neural collapse, the (last-layer) features tend to be close to their class mean. Even so, Assumption 3 holds under weak conditions, e.g., when features can be viewed as the class-mean feature plus noise from a continuous distribution. This is because Assumption 3 holds with probability 1 as long as the data/feature is generated from a continuous distribution [Soudry et al. 2018]. \n\n---\n**Q2**. “Could you include some numerical examples of convergence at extremely large step sizes? I am curious to see what the loss curve looks like.”\n\n**A2**. Please see Figure 3 in the attached rebuttal PDF for the suggested experiment. We tested two extremely large stepsizes, $\\eta=10^2$ and $\\eta=10^3$ in the logistic regression setting. Figure 3 is consistent with our results.\n"}, {"review_id": "fFSBqGbS2U", "reviewer": "Reviewer_QkkA", "summary": "The authors study gradient descent for logistic regression on linearly separable data, with a focus on large stepsizes, and in particular stepsizes in the edge of stability (EoS) regime.\nWith the logistic loss, they show that for *any* positive stepsize, the empirical loss is minimized as the number of GD steps increases, and the limit direction maximises the margin. Explicit rates are given.\nThe authors also provide counterexamples for the exponential loss: if the stepsize is too large, the loss diverges and the iterates cannot converge to the maxmargin direction.\n\n", "questions": "I have no further questions.", "limitations": "No such limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The authors study a hot topic (Edge of Stability) on an overall very well studied problem (logistic regression). \nIn these lines of work, the results are rather strong: proving convergence for any stepsize, beyond those that provide a nice descent lemma, seemed like a challenging problem, and this forms a strong contribution.\n\nThe other contributions (comparison between logistic and exp. losses, , the technical analysis) are also independently of interest.\n\nOverall, the paper is neatly written and easy to follow.", "weaknesses": "There are no main concerns or weaknesses to this paper, in terms of results or presentation.\nHowever, if I had to give one, I would say that since the implicit bias is the same whatever the stepsize is (it is thus the same for infinitesimal  ones and for stepsizes at the EoS), Theorem 1 extends previous results on the implicit bias of logistic regression, but does not give insight onto what happens at the edge of stability, and what drives generalization to increase. Could this be commented by the authors ?\n\nAlso, here are some recent references that study the EoS phenomenon on other problems, and that should be mentionned in the related works (they are all quite recent):\n\nIn contrast to the logistic regression problem studied in this submission, large stepsizes on regression problem lead to different solutions for GD and SGD when at the edge of stability:\n*(S) GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability*, Even et al. 2022.\n\nThe following paper also studies *scalar* linear networks (a scalar parametered by a product $xy$), as done in Ahn et al. 2022a,b and Zhu et al. 2022 cited in the submission, but in a more precise way: *Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyond*.\n\nFinally, *SGD with Large Step Sizes Learns Sparse Features*, Andriushchenko et al. 2022 study large stepsizes SGD and generalization (more experimental piece of work).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your strong support! Thank you for pointing out additional related papers. We will make sure to cite and discuss them properly in the revision. We address your question below.\n\n---\n**Q1**. “...since the implicit bias is the same whatever the stepsize is (it is thus the same for infinitesimal ones and for stepsizes at the EoS), Theorem 1 extends previous results on the implicit bias of logistic regression, but does not give insight onto what happens at the edge of stability, and what drives generalization to increase. Could this be commented by the authors?”\n\n**A1**. Good question. Indeed, our paper only characterizes the behavior of large stepsize GD after an (exponentially) long time, where its implicit bias is the same as that of small stepsize GD. To understand the (generalization) benefits of large stepsize, we need to further consider the polynomial-time behaviors of large/small stepsize GD and what exactly happens at the edge of stability. We conjecture that there is a different implicit bias induced by large and small stepsize GD when the optimization length is only polynomially large. We also think the new analysis techniques presented in this work will be useful for understanding the polynomial-time implicit bias of constant-stepsize GD. We believe this is an important future direction and will comment on this in the revision. \n"}]

Author rebuttal:
The attached rebuttal PDF contains the results of suggested experiments for logistic regression with extremely large stepsizes and homogenous neural networks.

Meta-review: All reviewers deem the paper interesting. So I recommend accepting the paper as a spotlight.
Decision: Accept (spotlight)