Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks
Authors: Nikolaos Tsilivis
Gal Vardi
Julia Kempe
Venue: ICLR 2025 Poster (2025)
Keywords: implicit bias
steepest descent
deep neural networks
Primary area: learning theory
TL;DR: We analyse the implicit bias of steepest descent algorithms in deep homogeneous neural networks, extending prior results about gradient descent.

Abstract: We study the implicit bias of the family of steepest descent algorithms with infinitesimal learning rate, including gradient descent, sign gradient descent and coordinate descent, in deep homogeneous neural networks. We prove that an algorithm-dependent geometric margin increases during training and characterize the late-stage bias of the algorithms. In particular, we define a generalized notion of stationarity for optimization problems and show that the algorithms progressively reduce a (generalized) Bregman divergence, which quantifies proximity to such stationary points of a margin-maximization problem. We then experimentally zoom into the trajectories of neural networks optimized with various steepest descent algorithms, highlighting connections to the implicit bias of Adam.

Published as a conference paper at ICLR 2025
FLAVORS OF MARGIN: IMPLICIT BIAS OF STEEPEST
DESCENT IN HOMOGENEOUS NEURAL NETWORKS
Nikolaos Tsilivis
Gal Vardi
New York University nt2231 @nyu.edu edu
Weizmann Institute of Science ga 1 rard @we zma nn. ac. i1
Julia Kempe
New York University
Meta FAIR
ABSTRACT
We study the implicit bias of the family of steepest descent algorithms with in- finitesimal learning rate, including gradient descent, sign gradient descent and coordinate descent, in deep homogeneous neural networks. We prove that an iigorithm--epenndern geometric margin increases during training and character- ize the late-stage bias of the algorithms. In particular, we define a generalized notion of stationarity for optimization problems and show that the algorithms pro- gressively reduce a (generalized) Bregman divergence, which quantifies proximity such stationary points of margin-man maximization problem. We then experimen- tally zoom into the trajectories of neural networks optimized with various steepest descent algorithms, highlighting connections to the implicit bias of Adam.
INTRODUCTION
Overparameterized neural networks excel in many natural supervised learning applications. A the- ory that aims to explain their strong generalization performance places optimization the forefront: in problems where many candidate models are available, the optimization algorithm implicitly se- lects well gell-genera ones (Neyshabur et al.] 2015b). The term "implicitly" indicates that neither the unregularized loss function nor the architecture explicitly favors simple, well well-generallzing lutions, but this occurs due to the choice of the optimization algorithm. Most existing theoretical results this so-called implicit bias of optimization demonstrate, to some extent, that gradient de- scent in overparameterized problems biases the solution to be the simplest, in terms of the lowest
possible & norm of the weights (Soudry et al., 2018 Ji & Telgarsky 2019 2020 Lyu & Li 2020
Nacson et al. 2019).
Simplicity, however, lies in the eyes of the beholder. For instance, in logistic regression with many ir- relevant features, an f ferreullarized solution is simpler than an fg-regularized one (Ng] 2004). More- over, in contemporary deep learning, Adam (Kingma & Ba 2015), AdamW (Loshchilov & Hutter 2019), and related optimization algorithms are preferred for language modeling (Zhang et al.) 2020). as their implicit biases seem better suited for such applications than gradient descent. It is therefore important to understand the types of solutions favored by optimization algorithms beyond (stochas- tic) gradient descent, order to address the current (and future) applications of deep learning.
[Ng]
In this work, we contribute to this line of research by studying the large family of steepest descent algorithms with respect to an arbitrary norm ||-|| in deep, non-linear, homogeneous neural networks. This class of methods generalizes gradient descent optimization geometries other than the Eu- clidean, allowing the update rule to operate under a different norm. includes coordinate descent (which has strong ties to boosting (Mason al. 1999)) and sign gradient descent (which is closely related to Adam (Kunstner et al. 2023) as special cases.
Our contributions. We provide unifying. rigorous analysis of any steepest descent algorithm in classification settings with tocally-Lipschite homogeneous neural networks trained using an exponentially-tailed loss. Specifically, focus the late stage of training (after the network

---

Published as a conference paper at ICLR 2025
has achieved perfect training accuracy) in the limit of an infinitesimal learning rate. Our first result characterizes the algorithm's 's tendency to increase an algorihmn-dependen margin (Theorem : similar to prior work on gradient descent (Lyu & Li 2020), we show that a soft version of the geometric margin starts increasing immediately after fitting the training data.
We then turn attention to the asymptotic properties of the algorithm. In attempt to find idence of margin maximization, we define a notion of stationary points for optimization problems, which generalizes the usual Marush-Kuhn-Tuckeee one (Definition (.4), along with approximate ver- sions (Definition A..)) As we show, during training, the algorithms make implicit progress towards such stationary points of a margin maximization problem a specific, geometric sense: they pro- gressively reduce a (generalized) Bregman divergence (Definition [.6]. which quantifies how well the stationarity condition is satisfied. As this process concludes, the limit points of training are along the direction of a generalized KKT point of the
geometric margin maximiza- tion problem (Theorem (.8)) For algorithms whose squared norm is a smooth function (for example, any lp norm for p 2 2). Theorem 3.8 further implies directional convergence to KKT points of the same margin maximization problem (Corollary 3.8.T)
In total, these results provide evidence for (geometric) margin-maximizann in any steepest descent algorithm and significantly generalize prior results that were about gradient descent only (Lyu & Li, 2020 Nacson al.) 2019). Moreover, the generalized divergence can be interpreted as measure of proximity to stationarity for optimization problems, similarly to what was proposed in prior def- initions of approximate KKT points in the literature (Dutta et al., (203)), and could be of broader interest to the optimization community. We find it appealing and theoretically intriguing that, de- spite the non-convexity of the loss landscape of deep neural networks, such simple convex structures emerge once the data points separate.
Finally, in Section 4 we train neural networks with the three main steepest descent algorithms (gradient descent, sign gradient descent and coordinate descent). We perform experiments in: (a) teacher-student tasks, to assess the connection between implicit bias and generalization and (b) image classification tasks, to study the relationship between Adam and steepest descent algorithms.
1.1 RELATED WORK
There have been numerous works studying the implicit biases of optimization in supervised learning and their relationship to geometric margin maximization see (Vardil (023) for a survey.
Steepest descent algorithms with respect to non- -uc-Euclid geometries have been explored before, both in supervised (e.g. (Neyshabur et al. 2015a| Large et al. 2024)) and non-supervised (e.g. (Carl-) son et al. 2015)) machine learning problems. The implicit bias of this family of optimization meth- ods was first studied in generality in (Gunasekar et al., 2018)) in the context of linear models for separable data, where margin maximization was established. Their proof is based on a result on Ad- aboost due to Telgarsky (2013). Our results generalize the analysis of steepest descent algorithms to any homogeneous neural network. Most related to paper the works of Nacson et al. (0019); Lyu & Li (2020) and Ji & Telgarsky| (2020). Nacson et al. (2019) studied infinitesimal regulariza- tion and its connection to margin maximization in both homogeneous and non-homogeneous deep models, while also proving (directional) convergence of gradient descent to a first order point of an f2-margin maximization problem for homogeneous models under strong technical assumptions. Lyu & Li (2220), whose theoretical setup we mainly follow, significantly weakened the assump- tions, under which such a result holds, and Lyu & Li (2020) further demonstrated the experimental benefits of margin maximization in terms of robustness. Kunin et al. (2023) generalized these results to broader class of networks with varying degree of homogeneity, while (Cai et 2024) analyzed
non-homogeneous 2-layer networks trained with a large learning rate. Vardi et al. 2022) identified cases where the KKT points of the & margin maximization problems are not (even locally) optimal.
The implicit bias of Adam (Kingma & Ba 2015) has been previously studied in the works of Wang ctt al. [2021] 2022) for homogeneous networks, where it is proven that it shares the same asymptotic properties gradient descent (62 margin maximization). Recently, Zhang et al. (2024) analyzed version of the algorithm in linear models, without a numerical precision constant, which arguably better captures realistic training runs and found bias towards l margin maximization the same as in the case of sign gradient descent. This makes us optimistic that insights from our analysis, which covers sign gradient descent (steepest descent with respect to the for norm), can shed light the
2

---

Published as a conference paper at ICLR 2025
poorly understood implicit bias of Adam in deep neural networks. See also (Xie & Li 2024 for a recently established connection between Adam W (Loshchilov Hutter 2019) and sign gradient descent. An additional motivation for studying steepest descent algorithms in improving the robustness of deep neural networks: Tsilivis et al. (2024), recently, provided experimental evidence and theoretical arguments that deep networks adversarially trained with different steepest descent algorithms exhibit significant differences in their (robust) generalization error.
2 BACKGROUND
Learning Setup We consider binary classification problems with deep. homogeneous, neural net- works. Formally, let S = (x,, M4 )am be a dataset of i..d. points sampled from unknown distribution D with x; E Fd and yt {+1} for all i E [m]] and let ((:0) F R de- note a neural network parameterized by E IR. The vector contains all the parameters of the neural network, concatenated into single vector. We study training under exponential loss C()) m -. (x(:)))) We focus on this setting for simplicity in the main text, but our results should readily generalize to more common losses, such as the logistic loss, as well as its multi-class generalization the cross-entropy loss. See Section A.3 for details and extensions of our main result.
The family of steepest descent algorithms generalizes gradient descent to different optimization geometries, allowing the update rule operate under arbitrary norm (instead of the usual Euclidean one) (Boyd & Vandenberghe 2014). Formally, the update rule for steepest descent
Algorithms
with respect to a norm |-
0.+1 0: + n,,0,, where 20, satisfies arg min
VL(O))) A0: ||
(I)
where the dual norm ||-1|~ of ||-|| is defined as || max (1 v) a learning rate. Gradient descent can be derived from Equation with ||-Il = 11-1|2- See Appendix C
||v|| = for any and 7); is
for details on how steepest descent algorithms are closely related to popular adaptive methods, such
as Adam Kingma & Ba 2015) and Shampoo (Gupta et al. 2018).
Assumptions & Technical Points In order to formally allow commonly used activation functions, such as the ReLU, we theoretically analyze loss landscapes that are not necessarily differentiable. That is, consider Clarke's subdifferentials (Clarke 1975) in analysis:
0 conv
vf(xx)) : X2 > x, differentiable at k-+00
lim
where conv(-) (-) stands for the convex hull of a set. Furthermore, we analyze steepest descent in the limit of infinitesimal step size, i.e. steepest flow:
d0
{
arg min (u,g.) gg E aC((..)
di
||u| dill.
This choice simplifies the analysis while still capturing the essence of the biases of the algorithms. Finally, make the following assumptions:
(A1) Local Lipschitzness: For any x, E RR,, f(x;:): : + R is locally Lipschitz (and admits chain rule- see Theorem A.2p.
(A2) L- L-Hooggeneity: We assume that f is L-homogeneous in the parameters, i.e. f(;c0) = f(; 0) for any >
(A3) Realizabbliiyy. There is a to > 0, such that L(Org) < 1.
Assumption ( is a minimal assumption on the regularity of the network, while assumption (A2) includes many commonly used architectures. For instance, ReLU networks with arbitrary number of layers, but without bias terms, satisfy (AT (A.).. Assumption (A3) ensures that the algorithm will succeed in classifying the training points and allows us focus what happens beyond that point of separation. Indeed, we are particularly interested in understanding the geometric properties of the model f(:; 0.) as f. oo (at convergence) the so-called implicit biases of the learning algorithms.
3

---

Published as a conference paper at ICLR 2025
3 THEORY
We analyze the behavior of steepest descent algorithms in the late stage of training and study their geometric properties and how these relate to geometric, algorithm-specific, margins.
3.1 ALGOORTHM--DEEEDDER MARGIN INCREASES
In linear models, where f(x; 0) = (0, x), the concept of Il-ll-ggeometri margin min 2;(0.x,) plays a central and fundamental role in the analysis of the convergence of train- ing (Novikoff 1963) as well as the generalization of the final model (Vapnik) 1998). Ideally, we would like to track similar quantity when training general, homogeneous, non-linear networks f(: 0) with steepest descent with respect to the ||-|| norm:
(0) [ Vof (x 0)
min yif xc(m)
X;i
|01|
[0]]
where recall that L is the level of homogeneity of the model. As it turns out, it is easier to follow the evolution of the following, soft, geometric margin:
70)) log (())
(5)
|
The characterisation of "soft" comes from the definition of "softmax" (a.k.a log-sum-exp), which is often used in machine learning. The same idea is used here to approximate the numerator of Equa- tion 4 The soft margin (00 is at most an additive log m away from (()) and converges to (()) as t xO see Lemma A.7 and Corollary |A.7.I
We show next that, given the algorithm has reached small value in the loss, the soft margin is non-decreasing. This theorem is similar to part of Lemma 5.1 in (Lyu & Li (020), which is the key lemma in their result. Ours is admittedly simpler, avoiding a bcautiful polar decomposition which was crucial in their analysis, yet, unfortunately, pertinent to the l2 case only.
Theorem 3.1 (Soft margin increases). For almost any to, holds:
d log dt
d0
2
L
2 0.
dt
LC(O,) log Z(O.)
00,
dØ
di
Proof of simplified version. We present proof for simplified version of this theorem here, cov- ering differentiable networks f. while we defer the full proof to Appendix A.2 For differentiable losses, steepest flow corresponds to:
d0 dt
E arg min (u, VL((.))
(6)
By the definition of the dual norm and chain rule, have for any / 0:
de
[VC)), and dC(O.)
d0
dt
dt
dt
'In this paper, we diverge from the established terminology when it comes to naming margins, by calling ||-Il- gelomercc margin (instead of ||+|| -goometcc margin) when it is defined with respect to the ||+I| norm of the parameters. We helieve this is proper, since the Il-omeegcott margin in linear models maximizes the metric induced by the ||+ norm (and not its dual, I|-
4

---

Published as a conference paper at ICLR 2025
Let n,
0
(recall that norm
||-|| might not be differentiable everywhere). For any > to.
have:
dlog 7
d
1
d
log log
L
log
||0|]]
dl
dl
[(O,)
di
d
n1.
d0
log log
L
(Chain rule)
dt
[(O;)
||011
dt
d
log log
1
dt
de
(def. of dual norm and ||m=|| S 1, Lemma A.4
di
[(O,)
||0.11
(8)
d((())
(Chain rule)
dt
((O,) log 2(0.)
|0,
d0 2
(Equation
di
C(O,) log 2(0.)
|00|| do
The first term inside the parenthesis can be related to the second one via the following calculation:
m
( VVC())))
O,,
[x((x;;
Σ Mi f 0z) (x.
(0 f 0.))
(9)
L
fx;((x
y: fxx; 0z),
1=1
where the last equality follows from Euler's theorem for homogeneous functions. Now, observe that this last term can be lower bounded
0 VL-
O..(xx min ye (x;; 0.) T.C(O.) log L(O.)*
(10)
(E(m)
where we used the fact e min:e[m] 3i (x.
fx. 0c) L(O.). We have made the first
term of Equation 8 appear. By plugging Equation 10 into Equation g we get:
d log 7 dt
d0
L (0,
L
dt
VL((.))
||0|1| at L
(11)
d0
1
I.
(definition of dual norm)
dt
|ooll de
Noticing that |L(,0)) = de
(from Equation concludes the proof.
Remark 3.2. Observe that it is the geometric margin induced by the dual norm of the algorithm that is non-decreasing, and not any geometric margin. The proof crucially relies on the fact that [()))) dt
de
3.2 CONVERGENCE TO GENERALIZED STATIONARY POINTS OF THE MAX-MARGIN PROBLEM
The previous theorem provides evidence and is a first indication that steepest flow implicitly maxi- mizes the -geommrci margin in deep neural networks. However, the monotonicity of the (soft) margin alone does not imply anything about its final value and its optimality.
this section, we
provide a concrete characterization of the asymptotic behavior of steepest flow: we show that any limit point of the iterates produced by steepest flow is along the direction of generalized KKT point of the following margin maximization (MM) optimization problem:
|
min OER
(MM)
s.t. (xf 0) 1, Vi [m].
5

---

Published as a conference paper at ICLR 2025
Let us recall the definition of a Karush- Kuhn- Tucker point (Karush 1939 Kuhn, H. W. and Tucker, A. W. 1951).
Definition 3.3. (KKT point) A feasible point 0 E RP of MM is a Karush-Kuhn- Kain--uuhueeeee (KKT)
point, if there exist xI...., Am 2 0 such that:
1. 0 |11 E X (1 yxf(x;;)) 3
2. A,(1 - y, 0) = 0, vi E [m]]
Notice that the first so-called stationarity condition is defined using addition, since we dealing with non con-differentialee functions. See (Dutta et al. 2013) for more details on optimization problems with non-smooth objectives/constrains.. Under some regularity assumptions, the KKT conditions become necessary conditions for global optimality and for non-convex problems like (MM) they might be the best characterization of optimality we can hope for. See Lemma AA.IT for details.
In the following definition of generalized KKT points, we relax the stationarity condition and pa- rameterize by a non-nege non-negative function.
Definition 3.4. (d-generalized KKT point) Let d 129 x RD + R4. A feasible point R2 of (M
is called a d-generalized KKT point if there exist A1...., Am 2 0, h, E 0f(x; 0) and k E 0 0 such that:
1. d (E Agy,,, k) O.
2. A, yxf 0)) 0, V [m].
Remark 3.5. When d in the definition of a d- d--generalized KKT point is any metric, we readily recover the original definition of KKT point.
demonstrate how to construct progress measure for optimization problems leveraging the above notion of stationarity (as well as its approximate version see Definition A.9).
In Appendix B
As will show, the function d, which in our case measures proximity of steepest flow to stationar- ity, is a generalized Bregman divergence induced by the dual norm of the algorithm (squared).
Definition 3.6. (Generalized Bregman divergence) Let up IRP - R with ()()) 3 1011 for all E R We define the (generalized) Bregman divergence D (3, R. R iR induced by sb as follows:
1 yll (y,
D E1I
|1 (m. z)
(12)
where m E 602 |z]3.
(()) 0111 is differentiable, then the subdifferental defined at any point collapses to single element: the gradient of vb If. further, v is strictly convex, then Equation 12 coincides with the usual Bregmun divergence induced by v., defined as ( z)
Remark 3.7. Notice that if the function
v(y) (2(z) (Vb(Zz) z). Bregman divergences (Bregman) 1967] generalize the Euclidean squared distance in different geometries and have found numerous applications in machine learning
A. Nemirovskii and Yudin 1983 Banerjee et al. 2005).
We are, now, ready to state main result.
Theorem 3.8. Under assumptions (A7, A2 A3
consider steepest flow with respect to norm -
|1-1l (Equation 3 on the exponential loss (
Then, any limit point of I generalized KKT point, of the following optimization
Emsee
is along the direction of Dē
[ToTI] J 120 problem:
min 3 011
(13)
s.t. (x;; 0) 1, Vi [m],
where D $11111 is (generalized) Bregman divergence induced by 111:112 and Ø
(minge/m) vi (x 0)) - tg.

---

Published as a conference paper at ICLR 2025
Theorem 3.8 states that the iterates induced by steepest flow have very specific, geometric proper- ties: not only do they asymptotically approach (in direction) a generalized KKT point of a margin maximization problem, but also, the proof of this theorem and, in particular, Proposition A.13 tells us, they implicitly make progress towards stationarity by decreasing Bregman divergence be- tween the gradient of the objective function and the gradient of the constraints of (MM). The full proof can be found in Appendix [A] The notion of generalized stationarity (Definition 3.4). as well as its approximate version (Definition A.9) introduced order exactly capture the geometric progress of the algorithm.
While the previous result is not strong enough to guarantee convergence a KKT point for any case of algorithm norm I1-II, it immediately implies it in the case of a norm whose square is smooth function. We can prove the following corollary for this special class of steepest flows.
Corollary 3.8.1. Under assumptions (A) . A22, A3 any limit point 0 of
produced by steepest flow (Equation 3 with respect to a norm Il.l. whose square is smooth function, on the exponential loss, is along the direction of a KKT point of the optimization problem (MM)
0. Telll (20
The proof relies vexity of its convex conjugate (Proposition 1A11). and can be found in Appendix [A] The main con- tribution of & Li (2020), which characterizes the implicit bias of gradient flow homogencous deep networks, can be recovered by the above result when |-|| II-I12- Additionally, Corollary 3.8.
fundamental relationship between smoothness of function and strong
generalizes this result in least the following cases of algorithm norms:
Any Ep norm with p (2) see, for example, Lemma 17 in Shalev-Shwarts (2077) for a proof on their smoothness.
Any norm induced by a positive definite symmetric matrix - i.e. f(x) = (x, Ax) x E
RR A E Rddd
Any (2, D)-smooth norm see Kakade et al. 20088 for details.
To the best of our knowledge, this is first result about the implicit bias of an algorithm in the param- eter space homogeneous neural networks which is not about fz-geometric margin maximization.
EXPERIMENTS
In this section, we train neural networks with various steepest descent algorithms (gradient descent- GD, coordinate descent-CD, sign descent-SD) to confirm the validity and measure the robustness of the theoretical claims, and to discuss the connection between Adam and steepest descent algorithms. Amongst other quantities, measure the three relevant geometric margins during training, which, in the context of onn-hidden layer neural networks with homogeneous activations and without biases, become:
yi [x;; 1x;;00 0)
y/ [x
yi (x;; 0)
71 min
=E[m]
|
72
min (m(m)
|00|
Yoo min xE(m]
0
(14)
4.1 STUDENT - TEACHER EXPERIMENTS
We first perform experiments in controlled environment, where the generative process consists of Gaussian data passed through a one-hidden layer neural network, which is sparse. Specifically:
((jo((w(,)))
x ~ La)
= sgn (freacher (x; 0*)) = sgn
(15)
where (u)) max u, 0) is the ReLU activation, sgn(-) returns the sign of a number, and | is assumed be small. We train neural networks of the same architecture, but of larger width and with randomly initialized weights: fscudent (x; 0) Σj uyo ((w,.))) with width K' > k and wy d' a] $J. [KT, E [d] uy u 1-g. g, g1. E [K]] (for we use: Wat U $. # .J [K]] ] I d in order to keep all the individual parameters to the scale initialization). The
7

---

Published as a conference paper at ICLR 2025
10a
min y.forc
10a
90
10-1
10a
10a
104
10
Test Accuracy (%)
min yifuoo
10
10
10a
10
10a
10a
60
min y/
191
10-6
-50
10-8
102
10a
10
10
10-9
10
10
Epochs
margin
CD
CD
CD
a=0.01
GD
GD
GD SD
0=0.1
SD
SD
a=0.001
Figure 1: Evaluation of steepest descent algorithms in teacher-student setup. Left: Geometric margins (71, 72, Toe in Equation 14) over the course of training (average over 20 different seeds). dif-
Right: Final test accuracy vs final Eo margin (Too). Each point in the 2d space corresponds ferent run (only showing runs that did not diverge). Larger points correspond to larger initialization scales a. The points are produced by switching from GD to CD (red) or (green), right after the point of perfect train accuracy.
magnitude of initialization can control how fast the implicit bias of the algorithm kicks in, with smaller values entering this so-called "rich" regime faster (Woodworth et al. 20200) We compare the
performance of (full batch) CD, CD and SD in minimizing the empirical, exponential, loss, consisting
of m independent points sampled from the generative process Equation 15 Section D contains full experimental details.
we expect GD to favor solutions with small l norm. This is equivalent small sum of the product of the magnitude of incoming and outcoming weights across all neurons (Theorem in (Neyshabur et al. 20155)). On the other hand, CD will seek to minimize the norm of the parameters, which translates to narrow network with sparse Ist-layer weights. Finally, SD's 's bias towards small ||O]| oo solutions does not appear to be useful for generalizing from few samples in this task. Therefore, we expect CD GD > SD in terms of generalization.
According to Theorems
3.1 3.8
Figure displays our main findings. We summarize our key findings below:
(i) Margins increase past lo- As expected from Lemma 3.1 we observe that, right after the point of separation, each algorithm implicitly increases its corresponding geometric margin (Figure left). Furthermore, we observe that the ordering of the algorithms is as expected for each margin (SD attains larger & margin than and CD, etc.), despite the fact that Theorem 3.8 only guarantees convergence to a KKT point (at best) of the margin maximization problem note the log-log plot.
(ii) Smaller initialization produces larger geometric margin. A smaller magnitude of ini- tialization a causes larger eventual value of the geometric margin (see Figure I rrihht for CD and 7sc. where this effect stronger, and Figure in Appendix D for 71, 72).
(iii) Importance of carly-stage dynamics for generalization. Figure I right shows the final test accuracy of the networks (20 different runs) vs the value of their final lo margin (%oo). We observe that, while there exist more CD runs with good generalization (red circles), these do not always coincide with larger 7 Furthermore, intervening the algorithms encourage or discourage Yoo maximizaatio does result in significant generalization
8

---

Published as a conference paper at ICLR 2025
changes: after running GD until the point of perfect train accuracy. switch either SD (green stars) or CD (red stars) to directly control the late stage geometric properties of the model. Switching to CD seems to bear marginal benefits in terms of generalization, even though all the switched runs reach smaller values of fee margins compared to the full, no-switching, GD runs. These benefits, however, pale in comparison runs. Switching to SD, on the other hand, results in smaller Yoe and similar or marginally worse test accuracy. See also Figure for test accuracy vs the other two geometric margins. We conclude that it is unlikely that large generalization benefits can solely and causally be linked to larger geometric margins in this setup, and appears that the early stage dynamics play an important role for generalization.
the full CD
4.2 CONNECTION BETWEEN ADAM AND SIGN-GD
Adaptive optimization methods like Adam (Kingma & Ba 2013) have been popular in deep learn- ing applications, yet theoretically their value has been questioned (Wilson et al.) (017) and their properties remain poorly understood. Wann et al. (2021 2022) studied the implicit bias of Adam in homogeneous networks and concluded that Adam shares the same asymptotic properties as GD. More recently, this conclusion has been challenged, in the sense that this asymptotic property cru- cially depends on a precision parameter of the algorithm and does not capture realistic runs of the algorithm (see Section C.T for details). In particular, was shown that, in linear models, Adam, with- out this precision parameter, implicitly maximizes the fi-gemmttiic margin (Zhang et al. 2024). a property shared with SD and not GD. Indeed, Adam without momentum, and ignoring the precision parameters, is equivalent to SD. Setting the precision parameter to O, on the other hand, is not useful in practical applications, as small initial values of the gradient result in divergence of the loss. A question arises: what, then, are the relevant geometric properties of Adam in practice?
Figure provides some experimental an- swers to this question, in light of Theo- We train two-layer neural networks on pair of digits extracted from MNIST with GD, SD and Adam, with small initialization. See Section D for experimen- tal details. We observe that, as soon as the algorithms reach 100% train accuracy, the margins start to increase (as Theorem 3.1 suggests); SD reaches larger value of 71. while GD reaches a larger value of 72. In- terestingly, Adam with the default hyperpa- rameters (precision momentum), initially, behaves similar to SD, increasing 71. before it starts decreasing it, in order to slowly start increasing ?2! Cu- riously, larger values of increase 71 even further and start the second phase slower, but more aggressively. Notice, however, that train and test accuracies have long con- verged, so it is unlikely that a typical run would have lasted long enough to see the second phase of fa-margin maximization (in particular, the loss value needs to be smaller than 10-7 7 in order to observe such behay- ior). Similar observations hold for Adam without momentum (recall that without mo- mentum and for + O. we recover SD). Therefore, it appears that the & bias of SD (Theorems 3.1 3.8 for ||+I| = ll=) more faithfully describes a typical run of Adam in neural networks.
1.00
rems 3.1 3.8.
Accuracy
0.58
0.96
10
30
1000
margin
500
-500
16
361
15
10
10 and non-zero
0.50
to margin
0.25
0,50
16P
16
Eacchu
Adam, e-10 (5, A.--0.0..0000 0.99)
50
Adam. - (R.A))1033.033 0.355
Adam - 10 R//000 0.0)
Figure 2: Relationship between Adam and steep- est descent algorithms. Aceuracy, and l1, & mar- gins during training for GD, SD and Adam on MNIST (3 random seeds). Adam is parameterized by a numerical precision constant and two momen- tum parameters (51, 32) (defaulting to 10-8 and (0.9, 0.99), respectively). We observe that Adam be- haves similar to SD for the period right after the point of perfect train accuracy.
9

---

Published as a conference paper at ICLR 2025
5 CONCLUSION
In our work, we considered the large family of steepest descent algorithms with respect to an ar- bitrary norm ||-I| and provided unifying theoretical analysis of their late-stage implicit bias when training homogeneous neural networks. Furthermore, we introduced a notion of stationarity for op- timization problems (defined with respect Bregman divergence induced by the algorithm norm), which, as we showed, captures the implicit progress of the algorithms and might be of indepen- dent interest. Theorem 3.8 does not preclude the possibility that any steepest descent algorithm will converge to a KKT point; yet our positive result (Corollary 3.8.1) shows this in the case where the algorithm squared norm smooth. would be interesting to generalize this result to any norm or show counterexample, well to generalize our proof for a discrete time analysis.
Our results can reinforce several recent efforts that attempt to understand deep learning through the lens of implicit bias. In particular, questions about generalization, robustness, and privacy can now be asked more broadly: (a) can we extract training samples from neural networks optimized with Adam, leveraging its connection to sign gradient descent, in similar fashion to what has been shown to be possible for gradient descent (Haim et al. 2022)? (b) can we leverage our implicit bias results to design more sample-efficient algorithms for robust training, argued by [Tiilivis et al. (202)) (c) is benign overfitting a general property of first-order methods, or are current results (e.g. (Frii al. 2022 Shamir 2023 specifically tailored for gradient descent?
ACKNOWLEDGEMENTS
NT and JK acknowledge support through the NSF NRT training grant award 1922658. GV is sup- ported by a research grant from Mortimer Zuckerman, the Zuckerman STEM Leadership Program, and by research grants from the Center for New Scientists at the Weizmann Institute of Science, and the Shimon and Golde Picker Weizmann Annual Grant. We would like to thank Zhiyuan Li and Kaifeng Lyu for useful discussion. Part of this work done while NT was visiting the Toyota Technological Institute of Chicago (TTIC) during the winter of 2024, and NT would like to thank everyone TTIC for their hospitality, which enabled this work. Part of this work was done while JK and NT were hosted by the Centre Sciences de Donnees at the École Normale Supérieure (ENS) in 2023/24, whose hospitality we gratefully acknowledge. This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise.
REFERENCES
A. Nemirovskii and D. Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983.
Arindam Banerjec, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with Breg- man Divergences. J. Mach. Learn. Res., 6:1705-17445 1749, 2005.
Amir Beck, First-Order Methods Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017.
Jeremy Bernstein and Laker Newhouse. Old Optimizer, New Norm: An Anthology. 2bs/2409 2024.
Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014. ISBN 978-0-521-83378-3.
L.M. Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200-27,, 1967. ISSN 0041-5553.
Yuhang Cai, Jingfeng Wu, Song Mei, Michael Lindsey, and Peter Bartlett. Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast optimization. CoRR, abs/2406.08654, 2024.
David E. Carlson, Edo Collins, Ya-Ping Hsich, Lawrence Carin, and Volkan Cevher. Preconditioned Spectral Descent for Deep Learning. In Advances in Neural Information Processing Systems
10

---

Published as a conference paper at ICLR 2025
28: Annual Conference Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec. Canada, pp. 2971-2979, 2015.
Frank H. Clarke. Generalized gradients and applications. Transactions of the American Mathemal- ical Society, 205:247-262, 1975.
Frank Clarke. Optimization and Nonsmooth Analysis. Society for Industrial and Applied Math- ematics, 1990.
Damek Davis, Dmitriy Drusvyatskiy, Sham M. Kakade, and Jason D. Lee. Stochastic Subgradient Method Converges Tame Functions. Found. Comput. Math., 20(1):119-154, 2020.
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate KKT points and a proximity measure for termination. Glob. Optim., 56(4), 2013.
Fenchel. On Conjugate Convex Functions. Canadian Journal of Mathematics, 1(1):73-77, 1949.
Spencer Frei, Niladri S. Chatterji, and Peter L.. Bartlett. Benign Overfitting without Linearity: Neu- ral Network Classifiers Trained by Gradient Descent for Noisy Linear Data. In Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pp. 2668 2703. PMLR, 2022.
Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Characterizing Implicit Bias in Terms of Optimization Geometry. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, vol- ume 80 Proceedings of Machine Learning Research, pp. 1827-1836. PMLR, 2018.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned Stochastic Tensor Opti- mization. In Proceedings the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmmsssan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1837-1845. PMLR, 2018.
Niv Haim, Gal Vardi, Gilad Ychudai, Ohad Shamir, and Michal Irani. Reconstructing Training Data From Trained Neural Networks. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 2022, 2022.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 62, 2020, virtual, 2020.
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization. In Advances in Neural Information Process- ing Systems 21, Proceedings of the Sventy-Secone Annual Conference on Neural Information Processing Systems, Vancouver, Brätish Columbia, Canada, December 8-1 2008, pp. 793-800. Curran Associates, Inc., 2008
William Karush. Minima of Functions of Several Variables with Inequalities Side Conditions. Master's 's thesis, Department of Mathematics, University of Chicago, 1939.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Truck Proceedings, 2015.
Kuhn, H. W. and Tucker, A. W. Nonlinear programming. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950, pp. 481 181- University of Cali- fornia Press, 1951.
11

---

Published as a conference paper at ICLR 2025
Daniel Kunin, Atsushi Yamamura, Chao Ma, and Surya Ganguli. The Asymmetric Maximum Mar- gin Bias Homogenous Neural Networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, 2023.
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise Is Not the Main Factor Behind the Gap Between Sgd and Adam on Transformers, But Sign Descent Might Be. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, 2023.
Tim Large. Yang Liu, Minyoung Huh, Hyojin Bahng, Phillip Isola. and Jeremy Bernstein. Scalable Optimization in the Modular Norm. abs/2405.1488 14813, 2024. URL https:///oi. org/10.
48550/arXiv 24055. 14813
Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Kaifeng Lyu and Jian Li. Gradient Descent Maximizes the Margin of Homogeneous Neural Net- works. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting Algorithms as Gradient Descent. In Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.
Mor Shpigel Nacson, Suriya Gunasekar, Jason D. Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and Depth Sensiiive Margins in Homogeneous and Non- Non-Homogeneous Deep Models. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Califormia, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4683 4692. PMLR, 2019.
Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro. Path-SGD: Barh-Normalized Op- timization in Deep Neural Networks. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2422-2422222 2430, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning In 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015b.
Andrew Y. Ng. Feature selection, L1 vs. 1.2 regularization, and rotational invariance. In Proceedings of the Twenty-Fine International Conference on Machine Learning, ICML '04, pp. 78, New York, NY, USA, 2004. Association for Computing Machinery. ISBN 1581138383
Albert B. J. Novikoff. On Convergence Proofs For Perceptrons. 1963.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS 2017 Workshop on Autodiff, 2017.
R. Tyrrell Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics and Physics. Prince- ton University Press, 1970.
Shai Shalev-Shwartz. Online learning: theory, algorithms and applications. PhD thesis, Hebrew University of Jerusalem, Israel, 2007.
Ohad Shamir. The Implicit Bias of Benign Overfitting. J. Mach. Learn. Res., 24:113:1-113:40 2023. http://ppsss//..r.crrr/////s////
html
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The Im- plicit Bias of Gradient Descent on Separable Data. J. Mach. Learn. Res., 19:70:1-70:51 2018.
12

---

Published as a conference paper at ICLR 2025
Matus Telgarsky. Margins, Shrinkage, and Boosting. In Proceedings of the 30th International Conference on Machine Learning. volume 28 of Proceedings of Machine Learning Research, pp- 307-315, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Nikolaos Tsilivis, Natalie Frank, Nathan Srebro, and Julia Kempe. The Price of Implicit Bias in Adversarially Robust Generalization. (bs/2406.04981, 2024. URL https://arxx>>> org/
04s/2400604981
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003--4
Gal Vardi. On the Implicit Bias in Deep-Learning Algorithms. Commun. ACM, 66(6):86-93,22 2023.
Gal Vardi, Ohad Shamir, and Nati Srebro. On Margin Maximization in Linear and ReLU Net- works. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Bohan Wang, Qi Meng. Wei Chen, and Tie- Yan Liu. The Implicit Bias for Adaptive Optimiza- tion Algorithms on Homogeneous Neural Networks. In Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 10849-11858, PMLR, 2021.
Bohan Wang, Qi Meng, Huishuai Zhang, Ruoyu Sun, Wei Chen, Zhi-Ming Ma, and Tie- Yan Liu. Does Momentum Change the Implicit Regularization on Separable Data? In Advances in Neu- ral Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The Marginal Value of Adaptive Gradient Methods in Machine Learning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1114841558, 2017.
Blake E. Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and Rich Regimes in Overparametrized Mod- els. In Conference on Learning Theory, COL. 2020, 9-12 July 2020, Virtual Event |Graz, Aus- tria], volume 125 of Proceedings of Machine Learning Research, pp. 3635-3673. PMLR, 2020.
Shuo Xie and Zhiyuan Li. Implicit Bias of AdamW: -Norm Constrained Optimization. In Forty- first International Conference on Machine Learning, ICMI. 2024, Vienna, Austria, July 21-27, 2024, 2024.
Chenyang Zhang, Difan Zou, and Yuan Cao. The Implicit Bias of Adam on Separable Data. abs/2406. 10650, 2024.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J. Reddi, Sanjiv Kumar, and Suvrit Sra. Why are Adaptive Methods Good for Attention Models? In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NewrlPS 2020. December 6-12. 2020, virtual, 2020.
13

---

Published as a conference paper at ICLR 2025
A
MISSING PROOFS
In this section, we provide proofs for the results stated in the main text.
A.1 STEEPEST FLOW
We first present series of technical results, which are about steepest flow in the case of non- In what follows, will denote with g? any loss subderivative with ||u]].. In the case of subdifferentials, chain rule
differentiable loss functions. minimum Il-ll, norm, i.c. gi E arg mimmueacce))
holds as an inclusion:
Theorem A.I (Theorem 2.3.9 and 2.3.10 in Clarke (1900). Let 21,..,, -R. R" R be locally Lipschitz functions and define = (z1....,,2n) Let (foz)(x) = f(21(x) 2n (x))
be the composition of z with f. Then, holds:
0(f xx) S conv Σ aa a (f(2((x)...,,, h, Deals)
(16)
To further analyze steepest flows and guarantee loss monotonicity, need stronger chain rule result. This can be achieved for a large class of locally Lipschitz functions, as per the following theorem which is due to Davis al. (2020).
Theorem A.2. (Theorem 5.8 in Davis et al. (2020)) If R - R is locally Lipschitz and Whitney C -stratifiable, then admits a chain rule: for all ares (functions which are absolutely contimuous on every compact subinterval) u [0, 00) + R$ almost all t 2 0, and all g & (F(u(t)). it holds:
dF dF(((() dt
du(l) dt
g:
(17)
Whitney -i-straiiiaability includes a large family of functions, including functions defined in an o-minimal structure which has been a standard assumption in the literature Ji & Telgarsky (2019). excludes some pathological functions see, for instance, Appendix J in Lyu Li (2020). This version of chain rule allows to derive the following central properties of steepest flows.
Proposition A.3. Let L : TRP - TR and assume that C admits chain rule. Then, for the steepest
flow iterates of Equation 7 it holds for almost any 2
dC
d0
S 0,
(18)
dl
dl
and
d0
do
g7
= ||g.
(19)
dt
dt
where Bi E min ||u|]..
Proof. From Theorem A.2 for almost any 2 0, holds V ge ac(O,):
dC
d0
gis
(20)
dt
di
Applying this for the element of OL,),) g/. that corresponds to ar from the definition of steepest
flow Equation get:
dC
d0
d0
g
(21)
dt
dt
dt
where the last equality follows from the definition of the dual norm. But, Equation 20 for g e arg min ||u|] yields:
dC
d0
d0
=
8
S
||.
(22)
dt
dt
dt
14

---

Published as a conference paper at ICLR 2025
Thus, combining Equation
21
Equation
22 obtain:
d0
< || ||+
(23)
dt
which implies that the update rule Equation 3 iq equivalent to:
d0
E arg min (u, g.) g7 E arg min ||u||
(24)
di
||
we)c(0.)
Therefore, from the definition of the dual norm, we have:
d0
d0
gi
= ll
(25)
dt
dt
Hence, under the mild assumptions of Theorem A.2 the loss non-increasing during training.
A.2 LATE PHASE IMPLICIT BIAS
A useful standard characterization of the subdifferential of a norm is the following:
Lemma A.4.
0|||| {v: (v,x) = ||x|| |vl+ S 11
We present the proof's for results about the late stage of training in steepest flow algorithms. The next lemma quantifies the behavior of the smooth margin past the point to (where, recall, zero classification error is achieved).
Theorem A.5 (Soft margin increases full version). For almost any to, it holds:
d dogg
d0
1
0.
dt
dt
LC(O,) log Z(O.)
|8
d0
dt
Proof. Let n, 0.|..| We have:
dlogg d
1
L d
log log
log ||0ell
dt
dt
[(0,)
dt
d
1
d0
log log
L
(Chain rule)
dt
[(O,)
||0.1l
di
2 d
1
log log C(O,)
L
(definition dual norm and ||n ||+ I 1)
dt
||0:1l
(26)
dC()))
1
de
L
at 0|l
(Chain rule)
dt
L(0,) log Z(O,J
1
d0
dt ?
L
(eq. Equation 18
C(O.) log Z
|0,
d0 dt
But, the first term inside the parenthesis can be related to the second one via the following calcula-
tion. Recall that, by Theorem A.2 for any g: E @C(O.) there exist h; E &y (x1;; 0.),..,, hn
Jym (Xm: 0.) such that g: En e (x.:))) Thus, for minimum norm subderivative g;. we have:
m
-8))
Or,
(x.
(x.:ee))e) (0.. h,)
(27)
L
vL (x(()))))) yi (xx;
15

---

Published as a conference paper at ICLR 2025
where the last equality follows from Euler's theorem for homogeneous functions (whose general- ization for subderivatives can found Theorem B.2 in Lyu Li 2020)). Now, observe that this last term can be lower bounded as:
m
(0.. - 2
L O..());).) min (xf 0,) 2 LL(0,) log (
(28)
iE m
where we used the fact e min (x. S eq. Equation 68 appear. By plugging eq. Equation
16 (x) We have made the first term of 28 into eq. Equation 68 we get:
dlogg ?
de
|
L
L
dt
dt
(O::
87)
|0:01
de
ar
(29)
de
|
L
L
(definition of dual norm).
dt
| lllllg ||+
||0:1| dr
de
Noticing that |/
||
de dt
(from eq. Equation 19
concludes the proof.
By extending Lemma B.6 of Lyu & Li (2020), we can further prove that the loss converges to and, thus, the norm of the iterates diverges to infinity.
Lemma A.6. As + oo, _(,,) + and |0,1| + oc.
Proof. We suppress the dependence of the loss and the iterates from time I, when obvious from the context.
From the definition the steepest flow update and chain rule (eq. Equation 18
we have
dC
d0
O (0--
(30)
dt
di
|
where we applied eqs. Equation 19 Equation 18 and the definition of the dual norm. But, as we showed in eq. Equation [88 the above inner product can be upper bounded by function of the loss, so, by plugging in, we get:
dC
L
1 2)= Coo
L
Clog ))
L
2
2
(t)
(to)
(to)
(Clg C .
dt
1012
(log 1)
2/L
(log 1
2/L
(31)
which follows from the definition of the margin Equation 5 and its monotonicity (Lemma A.5 By
rearranging:
dL log
1
2/1-2
2 (27
(32)
dt L
C
and integrating over time from to to t > to. we further have:
[1105 log
1 I
2/1--2 d
dt > (2
(33)
di
L
or, by a change of variables.
1/C(t) (log ()og 2/1-2 du 2 L2 to).
(34)
1/C(to)
The RHS diverges to infinity as hence does the LHS, which can only happen if L + 0. In order for L(O,) = Emi (xx(()) ||O.1| +
Em= -1 2 (xx;))))) e,
to go to zero, it must be
The following Lemma quantifies the connection between soft and hard margin.
Lemma A.7. For any 0, it holds:
min.e(m) Bi.f (x; 0) log m
minie(m)] Yif (x;; 0)
(35)
|
|
16

---

Published as a conference paper at ICLR 2025
Proof. Follows from:
min (x]() <(() s me min (x,
(36)
From the previous two Lemmata, we deduce that the soft margin converges to the hard margin as
( + co.
Corollary A.7.1. For any > to O, RP, ler ((t)) minselml (xx;)))))) Then, it holds:
0
lim (=(0.) (0,) = 0.
(37)
Proof. By taking limits in Equation 35
we have:
lim minse[m] (x;;0x
log
min.e[m] [x;; 0)
lim (0,)) < lim
|00
00| T
1-200
|
(38)
log m
lim (0,))
lim +0000
S lim ((,)) S lim (0.).
(0000
00|
t-000
t-000
But, from Lemma A.6 know that ||O||| oc. Thus,
lim 70,) S lim 7(0)) I lim 7(,). 1-000
(39)
t1000
(-000
which proves the claim.
The last part of the proof consists of characterizing the (directional) convergence the iterates in relation to stationary points of the following optimization problem (re-introduced here for conve- nience):
min 1101 0
(40)
s.t. yf 0) 1, Vi [m].
Under some regularity assumptions, the KKT conditions (Definition global optimality (yet, not sufficient):
3.3) become necessary for
Definition A.8. We say that a feasible point of Equation 40 satisfies the Mangasarian-Froon Constraint Qualifications if there exists Tº such that for all i [m] with (xf( 0) and for all h E (1 [x;; 0)), it holds:
(v. b) > 0.
(41)
Our proof uses the following relaxed notion of stationarity.
Definition A.9. ((d,e, 8)- approximate KKT point) Let d P RD
R.. feasible point
of equation 40 is called an (d, c, 0f 0f ; 8) and aapleeddnn..a))papppnni appproxmiiee KKT point if there exist A1...., Am 2 0, h, 0112 such that:
1. d (E k, c
2. E Ax(if 1) 1) 6.
We first show that can always construct feasible point of Equation 40 from a scaled version of Or-
Lemma A.10. For any t > 0, 0, (minuelm) Mi (x)))))
6.
is a feasssbble point of Equation 40
Proof. From the homogeneity of f, we have:
0.
Ix O.)
yxf(xx; 0.) y.f x;i
2
(42)
(min y. (x, 0.))*
min Fi (x;; 0.)
for all [m]. So 0, is feasible point of Equation 40
17

---

Published as a conference paper at ICLR 2025
The next Lemma shows that Problem satisfies the Baingasarian-Fromovvie Constraint Qualifica- tions:
Lemma A.11. Problem 40 satisfies the Mungasarian--rromviiz Constraint Qualifications at every feasible point 0.
Proof. Let h, 0 [x;; 0)) and 0 then for all i [m]] satisfying ys fx;( have from Euler's theorem for homogeneous functions:
(v, h:) Ly. 0) 0.
(43)
Our proof uses core ideas from the theory of conjugate functions and Fenchel's duality. Definition A.12 (Convex conjugate). Let ()):):
R" R. We denote by (-) the convex conjugate of
s (w) sup {w, 0) (()))-
(44)
oekr
We will make use of the following properties of conjugate functions.
Proposition A.13. (Conjugate subgradient theorem Theorem 23.5 in Rockafellar (1770) Theorem 4.20 Beck (2017)) Let v R² + R be convex and closed. For any 0 (0) holds Oib (0*) O
Lemma A.14. (Fenchel-Yourgy inequality) (Fenchel 1949 For any RP R and w, 0 E RP, holds:
(w.w) S (0) 60 (w).
(45)
Next, we show that the scaled version of the iterates from Lemma A.10 O.. is (De. 21IH (()),(()) -approximate KKT point for e(t) and 8(1) that vanish as / increases.
Proposition A.15. For any I > lo. O.
an (D (
21 (0) (0,5())
(min.g Mi f Ox))
approximate KKT point of Equation 40 with:
1
gt
<(t) 7(t))
0
l|g: ||
(46)
m
8(t) =
et 7. log ~z
with gi E arg miggeenc)))))) |u]l..
Proof. We suppress the dependence of the loss and the iterates from the time index 4, when obvious from the context. From Lemma A.10 we know that a feasible point. To simplify the notation, let Jmin = min (x; 0). We will denote by 0 ||0 any subgradient of 111111 O. Let, as previously stated, gi E arg minnueeeece,) ||u||+ and h E 0f(x; i),i [m]] such that g: - e v= yx (whose existence is guaranteed from chain rule - Theorem A.
1. Finally, we define h = qmin h for all i [m]] for which it holds: h E 0x 0) from Theorem B.2(a) in Lyu & Li 2020).
||o 1- e (xx:00)
Given all these definitions, we set A; (d, e, -statioonay definition can be simplified to:
|| l. 9min
The dual vector from the
m
1 Aeg ych
A
(Thm B.2(a) Lyu Li 2020
|||||
(47)
q
[g ||+
(=1
[0|g;
18

---

Published as a conference paper at ICLR 2025
which is scaled version of the (minimum norm) subderivative of the loss.
Let (0) = 2/2 0 be the potential function that we shall use order to define our divergence. For this specific 1h, it holds: s (w) = 2. |wl (see for instance Example 3.27 in Boyd & Vandenberghe (2014) for derivation). Recall that in the definition of Dm (Equation 12 there
extra choice that we have to make; the one of the subderivative m. In what follows, we will specifically measure "distance" between E Ayy:h, and k using D
#11-113
0. This is possible, since from Proposition A.13 it holds that 0 E 0 [k] Finally, let E a| 0| be the subgradient of ||-|| that stems from the chain rule of 2 -1-112 evaluated 0. We calculate the divergence between the two vectors:
* +1-111 (t++), i.e. by picking
DØ I1-112
Σ
Aivi k
2
|01|8/
|10
k
2
2
Amin
1i
Amin
mmin
gi
|0112
0
|10||
gg
0
1|0
(Chain rule)
2
4min
||
|
1
g2
2
0
|[
II.
||0||
Amin
||011
|=12
0
82
+
0
+
||=12
(Equation 45
2
2
|101|
gg
2
2
Arnin
|
0
g2
||||
Amin
1
g2
0
8:
||ll|'
lgg
7tto)
|00
gg
(48)
where the last 2 incqualities follow from the relation between smooth and hard margin (Lemma
A.7 and the monotonicity of the former. For the second condition of an approximate KKT point, we have:
m
(ux((x;0)-1)
m
1-
(
( (V.f(x;; 0)
Amin
gi
|
Omin
(49)
|
(yi (x;; (min).
t min
|g
From eq. Equation 30 and Equation 28
we can lower bound the dual norm of the subderivate:
1
g
ll Z
C log
Swin log I
(50)
C
By plugging in back eq. Equation 49
obtain
|
A (x,((x;:
-1) S
e (x(();0)) (viJ 0) [minn]
Omin Le Qui log 1=1
1012
(x.;0) gmm) (vif(x;;0) 0) Qmin)
Amin L log
(51)
(vi (x: (vif(x;; gmin)
(Lemmata A.7 A.5
7(1o) 2. Llog Z 1=1
m
c5(10) 2 log
19

---

Published as a conference paper at ICLR 2025
since the function u e "u, has maximum value of e-!
Before we proceed with the main result, we state and prove two useful Lemmata. The first one lower bounds the alignment between normalized iterates and normalized loss gradients. This Lemma is key for showing that the alignment goes to as + oo.
Lemma A.16. For all L2 >> h 2 to. there exists 1, E (41,2) such that:
1
log
7
((taa)
(52)
0..
-R Bi.
L
22
10..11
|R., 11.
|0
dt
for all gi, mig ||u/].
Proof.
From Lemma A.5
we have for all gē E arg unicue, ||u]].:
dlog dt
d0,
2
(0,
g/
0
d0c
dt
(53)
d0, dt
||
1
00
0.
(0,)
[0:11
We then integrate the two sides from 1 to 12 > 1 >
to:
1
|
dA
7(12)
dt
dt
S
log
(54)
0.
0
L
(t1))
|0
The desired existential statement follows from proof by contradiction.
Next, we bound the rate of change of the normalized iterates.
Lemma A.17. For any t 0, it holds:
0
de,
9:
dt
(55)
Proof. The rate of change of the normalized iterates can be written as follows:
d 0
d0,
1
dlloell
0,
dt
|0:1| dl
||
00.11
(56)
d0,
n d0," )) ))
0,
(Chain rule)
| ||
dt
|00.11
dt
where n, E 0/ll. So, by the triangle inequality, its norm is bounded by:
d 0,
|
d0, dt
1
d0,
<
Dr: di
dt
[0.|]
0
(57)
d0;
< 2
(definition of dual norm and ||//]l S 1)
We are, now, ready to state and prove main result.
20

---

Published as a conference paper at ICLR 2025
Theorem A.18. For steepest flow (eq. Equation the exponential loss, under assumptions A7
A2
A3
any limit point 0 of 10:11 120
is along the direction of a D
4 +11-11; - generalizee KKT point,
0 =
(minuetm) Vi () of the following optimization problem:
0
min 2 101
0
(58)
s.1. V (x;; 0) 21. 1, Vi E [m].
Proof. Our strategy will be consider any limit point 0 and construct fi (0))(1)) approximate KKT points that converge to it, with vanishing e(t), 8(t).
(0,
Let Em = 1 for any m 0. We construct a sequence [1mJm20 by induction, the following m
sense. Suppose t1 <.. < tm-1 have been constructed already. Since 0 is a limit point of the normalized iterates and log + log 750- oo (as Vt. is non-decreasing and bounded from above),
there exists 8m > 1m-1 such that:
0 pm
1 m
700 7sm
1 m2
S Cm
and T.
log
S S
(59)
d0,, dt
Since dlog [[0
de,
we have that lime
di' oc for LA > Thus, there
de
[0.
|
ddg
1
exists s'm
9m such that
Now, from Lemma A.16 we know there exists
10.1
m
I- E (8m; s'm)
with:
3 log
1
<
m2
(60)
P
Rx
m
d0
m
[o..
|
dt
[0
8m
which implies
To..
0.,
lis7 II.
-B²
1+
as m
+ oc. On the other hand, for the normalized
iterates have:
0
0:.
0 pm
eq. Equation 59
θ,.
0 pm
1
<
(61)
00.
0..1
0
0
10.,1
00.m.
To deal with the first term, we can leverage Lemma A.17 normalized iterates:
which bounds the rate of change of the
0.
do dt
d0:
3
2
dt
0.
(62)
01_
0
m
|0,|
m
m
Hence, by picking t.m as t., constructed time sequence such that, for any limit point 0, i and also
o....
Oim
(0 (0 [[: (0....
1.
MT
Then, from Proposition
A.
we know that Orm
an
(minec(m)) 31 fx Pr...)
(Do.
(ill 11:11 (1mm), approximate KKT point of Equation 40 But 6(1m) - O (since the align-
ment goes to 1) and 6(t,.) + 0 as the loss goes to zero (Lemma A.6), thus the sequence satisfies the conditions of Proposition [A.20] which shows that the limit point of the sequence a generalized KKT point. This concludes the proof of our claim.
While the previous result is not strong enough to guarantee convergence to an approximate KKT point for general algorithm norm ||+1], it immediately implies it in the case of smooth norm. The proof relies on a fundamental relationship between smoothness of a function and strong convexity of its convex conjugate.
21

---

Published as a conference paper at ICLR 2025
Proposition A.19. (Conjugate Correspondence Theorem Thm. 5.26 in Beck (017)) Let 0. s/ a smooth convex function, then its conjugate v² is o-strongly convex.
We can prove the following corollary for special class of steepest flows.
Corollary A.19.1. For steepest flow (eq. Equation 3) with respect to norm ||- whose square
smooth function, on the exponential loss, under assumptions A7 A2 A3 any limit point 0 of
0
is along the direction of a KKT point of optimization problem Equation 40
| 120
Proof. From Proposition A.19 if 111-112 1 smooth w.r.t ||-1|, then the function ] -l1-11 is o-strongly convex w.r.t |1-I1-- Thus, the function D 11-11 is defined with respect to strongly convex function and becomes a proper Bregman divergence. Hence, from Theorem 5.24 in [eck (2017). for h = mmin
- h;, where hy 0f(x;;)) 0) [m] such that g? > e /xx y: and
k E 0 01 it holds:
D +HI
Σ A 2 A.y k
(63)
In other words, if DO & I1 (a, 3) is O, so is the difference a b for any at, b. As result, and from the equivalence of the norms, the sequence om.m.
(minge (.. from the proof of Theorem A.18 induces a sequence of (e(tm)) 8(tm) ((tm)))-aprn appproximae KKT points, which converges to KKT point of Equation 40 By Theorem C.4 in Lyu & Li (2020) (which is itself based result due to Dutta al. (2013)), get that
is KKT point of Equation 40
[minge mm] (xx;))))
The following technical result was used the proof of Theorem A.18 Proposition A.20. Let (MM) be the following optimization problem:
min 1011 BER 2
(MM)
s.t. yif (x;; 0) 1, Vi [m].
Let (0:)22 a sequence of feasible, (d, et; aap-appro KKT points, with d Do & 4 0, 0 and 0, + Assume that the Mangasarian-Fion Fromovvvtt---- Constraint Qualifications hold at O. Then, is a Dd I1-11: generalized KKT point of (MM).
211-12 with
Proof. Our proof closely follows the proof of Theorem 3.6 (Dutta al. 2013). which the direct analog for (e, appproxmmate KKT points.
By the definition the (d, ex, 5,) stationarity, for each / 0, there exist bf E 0f(x; 0.), [m],k' 0 and X 0, [m]] such that:
(i) 00. I1lll EE Ky k2) s a.
ii) Σ" X (wffxx 0.) 1) 8
We will show that the sequence (X) 1:20 is bounded. Assume on the contrary that is not. Consider A ' . which is bounded and wlog, it is: Å + Ā with |ЛÅl| 1. Note that the sequences [h:}, [k') are bounded, as elements of a subdifferential, by the Lipschitz constant of the corre- sponding function. Hence, they also converge to, say, h, for all E [m] and k, respectively. From
22

---

Published as a conference paper at ICLR 2025
d
E A. (O'), VS(0))
02
0
E1
62
63
0
Proximity stationarity
Figure 3: An illustration of the reduction of the Bregman proximity measure. Once separates the training points, steepest descent homogeneous networks implicitly makes progress towards generalized stationary points 0 of margin maximization problem (Theorem A.18)
condition (i), we have:
1
Do. &
Nynhh kt
|
I1-112
A
(64)
yih
kt
O,
U h
k'
Et
2
2
|
|
|||
|
|
||
hence, by taking t + 00, we get:
1 2
N. h
S O,
(65)
which implies that there exists À 전 such that D Anth where recall h, (x(;; 0) An existence of such vector is prohibited by the Srtgaaaariann-ommoiii-----oo which hold at O. Thus, {X* is bounded and A À for some À _ Hence, by taking the limit f - 20, we have:
Qualifications
m
D
Σ
Auu.,,kk k
S O,
(66)
where h, (x;;;; 0), E [m] and k 0 10). 101. From (ii). we obtain Σm A (vif(x;;; 0) 1) <
O. However, yi (x;; 0) 1 0 (0 is feasible point of (P)) and X 2 0 for all E [m], thus it holds:
Σ Xe (mif(x;; - =0,
(67)
which concludes the proof that 0 is D ||:1 generalized KKT point.
A.3 GENERALIZATION TO OTHER LOSSES
The previous results can be generalized to any loss with exponential tails. In particular, let us proceed to the following definition:
23

---

Published as a conference paper at ICLR 2025
Definition A.21. Let 4 R R. Assume that [(0) "E= e -(. 0 E R", where f: IR y, (+1). We call the function I IR IR, [R, e-b(u) exponentially tailed, if the following conditions hold:
(i) O is continuously differentiable.
(ii) &' ('(u) for all u E R.
(iii) The function g(u) & (u)u non-decreasing in [0, 00).
Notice that the definition above covers the exponential loss for o(u) u and the logistic loss for
(u)) log log(1 e)) To accommodate different loss functions, Assumption A3 needs to be
adjusted as follows:
There to > 0, such that ((O..) < -00)
See Section A in (Lyu & Li 2020 for more general, albeit technical, definition that allows the extension of the full analysis general exponentially
losses.
Under these conditions, we can define the soft margin as follows:
(2)
-- "loog 2
|0||
|
and prove strict generalization of Theorem
3.1
Theorem A.22 (Soft margin increases
general loss function). For almost any > to. it holds:
( (x-1) (log Z(O.J
dlog 7 dl
d0 1
L
0.
di
LC(0)) (log 2(0.)
10cl
de
dt
Proof. Let n, E 0z|l.
We have:
dlog d
L d
4* -1
log [(0.)
log 0
dl
dl
dt
d
Φ -1
log C(0.)
L
n1
d0
(Chain rule)
dl
|0.11
di.
d ④
do
-1
log ((0.)
L ||0,1l
di
(definition of dual norm and ||n:||+ S 1)
dl
(68)
(Φ-1)'
log c(03)
d.,)))
ar
(Chain rule)
dt
((0:)4-1
(log Z(O.)
d0 2
(I--))
(log c(o.)
(eq. Equation I8].
dt [(0.) (log c(O.))
|0.1|
[|
d9 de
But, the first term inside the parenthesis can be related to the second one via the following calculation. Recall that, by the chain rule for locally Lipschitz functions (Theorem A.2]. for any ge E AL(O,) there exist h1 E 0y1f(x1; (x). o.)...,,h hm fxm 0.) such that gr Thus, for minimum norm subderivative gf. we have:
m e -x( (.)) "', Dm
0c. Σ
+(nf(xx0:)) D' (y:](x;; 0.))h?
(y fx..f(xx (f)) 0.)) (0 h;)
(69)
i=1
1=
24

---

Published as a conference paper at ICLR 2025
GD-SD
CD
GD-S0
90
90
d-0. .0001
SD
a=0.01
SD
a= 0.01
d-0:1
Text Accurary 2%6
Test Accuracy (%6
70
70
50
50
10
A margin
4 margin
Figure 4: Geometric margins test accuracy in teacher-student setup. Left: & margin. Right: 82 margin. Each point corresponds to a different run (different random seed).
where the last equality follows from Euler's theorem for homogeneous functions (whose generaliza- tion for subderivatives can be found in Theorem B.2 in Lyu & Li (2020). But, now observe that as per assumption, -> (u()) is non-decreasing and this last term can be lower bounded as:
( Φ [og C(O.)
Φ-1 8-1 log C(O.))
1
0 g. 2 L
(70)
where we used the fact ysf (x;; 0.) -- (1og z(O,) for all [m] (by the monotonicity of + the definition of L). Leveraging the fundamental property between the derivative of function and its inverse's, s, we further get:
& Φ- (log E(O.)
T-1 Z(O.s)
(0,, gi)
L.
((,1(x;;0)))
I.C(O,)
(71)
(x-1)' (log Z(O,)
(Φ-1) logg Zío,
We have made the first term of eq. Equation 68 appear. By plugging eq. Equation 71 into eq. Equa- tion 68
we get:
dlog 7
d0
L
IV
dt
dt
(
-gi)
||0:1|
(72)
d0
L
L
IV
(definition of dual norm).
dt
0
11
||0:1|
|| dØ
Noticing that ||//||
de
(from eq. Equation
19 concludes the proof.
B BREGMAN PROXIMITY MEASURE
In the proof of our main result (Theorem A.18), we constructed sequence of approximate general- ized KKT points (Definition However, in many cases, while solving (non-convex) optimization problems, we only have feasible points without any evidence of optimality or stationarity. In such cases, it is useful to up with a progress measure of approximate stationarity that also serve as stopping criterion for the optimization algorithm. Consider an optimization problem:
min f(0)
DERd
(P)
s.t. g: S 1 [m],
25

---

Published as a conference paper at ICLR 2025
where we assume that f. f9: )== differentiable for the sake of brevity. For feasible point O' of P and a non -enaatievve function d R" x Rº + R.,, we define the d- d-Bregman proximity measure as the solution of the following optimization problem:
min G prrss
d
AV Sc
(73)
A -,
1
A 2 0 Vi [m].
This definition mirrors and generalizes the definitions of (Dutta et al. (013). which were inspired by approximate KKT points (whose proximity is mcasured using the Euclidean distance as d). How- in analysis, there many cases of problems where a proximity measure would be better defined using alternatives functions. Figure conceptually illustrates the reduction of the Bregman divergence in possible converging path. The relaxation of the slackness constraints in the i=1
form of >x= A.ga (0') 2 -e is essential for ensuring that the proximity measure captures proximity stationarity see Section 3.2 in (Dutta al. 2013) for discussion.
C RELATIONSHIP TO ADAM AND SHAMPOO
The family of steepest descent algorithms includes simplified versions (momentum turned-off) of two adaptive methods, Adam and Shampoo, which have been very popular for training deep neural networks.
C.I ADAM
Adam (Kingma & Ba 2015) is popular adaptive optimization method, which is frequently used in deep learning. Following our previous notation, the update rule of Adam amounts to:
m, 31 m, + - -1-1 V
V. 82V;-1 + (1 (1-B2))Vi -2)
m
Ve
m, - B
V, 1 B
(74)
m
0, 0 TJ
where the 2 operations are overloaded to operate elementwise vectors. Parameters 31, B2 control the memory of the update rule, while a numerical precision parameter. Notice that for O, we recover sign-gradient descent.
31 B2
Wang et al. stuuiedd the implicit bias of (74) for 0 in linear networks establishing bias towards &, margin maximization, while Zhang et al. (2024) analyzed the case of 0 and generic 91.82 3g [0, 1) also in linear networks and showed bias towards & margin maximization.
C.2 SHAMPOO
Shampoo (Gupta et al. 2018) is adaptive optimization algorithm, which has recently gained popularity in deep learning applications. For each weight matrix W, and its corresponding gradient matrix G the update rule of Shampoo without momentum amounts to (Bernstein & Newhouse
2024]:
W W. W.- U.V..
(75)
where U. V, contain the left and right singular vectors of G., i.e. -.-,V,,V Bernstein & Newhouse (2024) recently noticed that this update corresponds to steepest descent (in matrix space) Eeaiitecture-dppendeee
norm in parameter space. For instance, if 0 = (W,, ......, W,), then Shampoo without momentum corre- sponds steepest descent with respect the norm |00 ||s max (amax (W,) (W1),- i)).... maxx (W t.))
with respect the spectral norm max (-). This is equivalent to
26

---

Published as a conference paper at ICLR 2025
1.00
Accuracy
0.98
0.96
0.94
0.92
10a
10
102
10a
500
SD
Adam, 10- -00 (8,, 02)=
f margin
Adam, = 3, (8), (2)= 0.0)
Adam, = 10 (8), (2)=(0.9, 0.99)
-500
Adam, 10-2, (8,, (2)-(0.9, 0.99)
train acc
-1000
test acc
100
10A
0.5
E, margin
-1.0
10a
101
10²
10a
Epochs
Figure 5: Relationship between Adam and steepest descent algorithms. Digits '2' and '7'
D EXPERIMENTAL DETAILS
All experiments are implemented Py PoTorch (Paszke et al. 2017).
Teacher-student experiments We use the following hyperparameters: d = k 64, K' 1024, m = 250, learning rate = 10 and density k((++1) = 0.0001 (3 coordinates active per |
neuron). We vary the scale of initialization in 10.1, 0.01, 0.001 and train for 10 epochs. Each random seed affects the draw of the datasets and the initialization of the parameters of the network. Test accuracy is estimated using 20,000 unseen data drawn from the same generative process.
MNIST
We use a constant learning rate of 3 x 10-3 and 1-hidden layer neural networks of width 128, optimizing the logistic loss. The digits that we extract are '3' and '6' (100 training points). Each random seed corresponds to a different draw of the training dataset and different initialization. Sign gradient descent runs were very effective in minimizing the training loss, and we stopped the training early after the loss reached value smaller than 10-7 in order to avoid numerical issues. We depict the final value, repeated for as many epochs as shown the figures (as if the model has indeed converged).
Figure 5 shows accuracy and margins for a different pair of digits (22 vs '7').
27


Reviews:
[{"review_id": "nbn1nQrDab", "reviewer": "Reviewer_Bpd2", "summary": "The paper investigates the implicit bias of the family of steepest descent algorithms, including gradient descent, sign gradient descent, and coordinate descent, for deep homogeneous neural networks. The authors aim to understand how these optimization algorithms implicitly select solutions from the perspective of margin maximization. The main contributions of the paper are:\n\n1. A rigorous analysis of the implicit bias of steepest descent algorithms in non-linear, homogeneous neural networks, showing that an algorithm-dependent geometric margin increases during training, under the same set of assumptions made in Lyu&Li.\n2. The definition and characterization of a generalized notion of stationarity for optimization problems, demonstrating that these algorithms reduce a generalized Bregman divergence, which quantifies proximity to stationary points of a margin-maximization problem.\n3. Experimental validation of the theoretical findings by training neural networks with various steepest descent algorithms, highlighting connections to the implicit bias of Adam.\n\n\nI think the class of the optimization problems studied in this paper is general and the theoretical results of the paper are quite clean. Although the main proofs follow the framework developed by Lyu and Li, the proofs are nontrivial (I read most of the proofs in the main text and a few in the appendix). Overall, I am leaning towards accepting the paper. With additional clarifications of the relation with prior work, this paper would be a valuable addition to the literature on deep learning theory.", "questions": "minor comment: \n1. The sentence before Theorem 3.1. The proof is quite similar to that in Lyu&Li. It seems to me that this paper used Cauchy-shwartz but Lyu&Li explicitly used the Pythagorean theorem (which only holds in inner prod space but not general normed space). If I am correct, then there is not much difference.\n\n2. I think it would be better to discuss briefly the relation between D-generalized KKT and ordinary KKT between Theorem 3.8 and Cor 3.8.1. and why not to prove something like Cor 3.8.1. directly.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "**Strong Points:**\n\n1. The paper provides rigorous theoretical analysis of the implicit bias of steepest descent algorithms. The results and proofs extend the l2 norm case (gradient descent) by Lyu&Li to general norms. The theoretical results are clean and some of the extension are nontrivial. \n\n2. The class of optimization algorithms studied in this paper is very general and include several important optimization algorithms as special cases.\n\n3. The paper connects theoretical insights to practical optimization methods like Adam, which is widely used in the deep learning community. This connection may help to understand the benefit of Adam.", "weaknesses": "**Weak Points:**\nThe authors briefly discuss some prior work on implicit bias of optimization algorithms other than GD in the related work section. But I found the inclusion of related work and the discussion here is somewhat insufficient. For example, Gunasckar et al. 18 already studied the implicit bias of several class of optimization algorithms. However, the citation here is very superficial and it is unclear to me how the results in this paper supercede (or compared with) their results. It is also unclear to me how the results by Wang et al. on Adam is related to the results of this paper. If we simplify Adam to signGD, it seems that the results in Wang et al. is inconsistent with this paper? I think more detailed discussion is necessary.\n\nMoreover, the following papers also obtain implicit bias results towards L_p margin with p different from 2 (for special models). Is there any concrete relation between these results and the results in this paper.  \nKernel and Rich Regimes in Overparametrized Models (already cited but not discussed in details)\nImplicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "uaoLg6QYXU", "reviewer": "Reviewer_APGr", "summary": "This paper studies the implicit bias of steepest descent methods with infinitesimal step size (i.e., steepest flow) and presents an interesting generalization of Lyu & Li (2020)'s result on gradient flow (steepest flow with L2 norm). Similar to gradient flow, it is shown that steepest flow has a bias towards KKT solutions to a margin maximization problem, but the margin being maximized here is normalized properly according to the norm used in steepest flow, which may not be the L2 norm in general.", "questions": "This paper only proves the convergence to generalized KKT solutions for sign gradient flow, which is an important case of steepest descent. I wonder if the authors have any thoughts on whether failing to prove KKT in this case is an artifact due to the proof techniques or if some tricky hard cases actually exist.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Understanding the implicit bias of optimization methods is an important problem in deep learning theory, and the paper takes a margin-based view of implicit bias and sheds light on how different methods may optimize different notions of margin for deep models.\n2. It is a bit surprising that such an implicit bias of steepest descent can be rigorously proved in the general case. Previously, it is known that this can be proved for linear models, and for deep homogeneous networks, Lyu & Li (2020) generalized the result for GD. It is reasonable to imagine that one could somehow generalize Lyu & Li (2020)'s result to steepest gradient, but their proof apparently has a lot of dependence on the L2 geometry induced by GD. After having a careful read of the proof (though I skipped a few details), I believe the authors found the right way to do this generalization and worked out all the technical issues, including those related to non-smoothness.\n3. The paper is well-written and easy to follow.\n4. Experiments in simple settings validated the theoretical results.", "weaknesses": "1. While I really appreciate that the authors worked out every technical detail to generalize the proof of Lyu & Li (2020), I also noted that the overall proof outline has not changed much from Lyu & Li (2020), which means this paper does not actually bring a brand new high-level proof idea. This is reasonable since any implicit bias analysis of steepest flow automatically implies an analysis of gradient flow, but the fact that the paper fails to prove the real KKT conditions and only manage to prove a weaker notion (generalized KKT) suggests that a perfect generalization from gradient flow to steepest flow may indeed need a completely new proof strategy.\n2. Same as all previous works studying the max-margin bias, this paper only analyzes the late phase, where the training loss is already very small. While the asymptotic analysis of implicit bias is interesting, this also makes the phenomenon less relevant to the practice.\n\nMinor issue: there are large blanks on some pages in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "IsQuBe0kDp", "reviewer": "Reviewer_By2M", "summary": "This paper studies the implicit bias of  steepest flow with general norm in homogeneous neural networks. It shows that the soft-margin is monotonically increasing after the loss is below a threshold. Furthermore, it shows that the steepest flow converges to the generalized KKT point. Finally, experiments demonstrate the similarity of Adam algorithm and Signed-steepest descent algorithm, in terms of implicit bias.", "questions": "See weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The convergence of the general steepest descent to the general maximum margin solution is novel. \n2. The connection between the implicit bias of Signed steepest descent with Adam is interesting.", "weaknesses": "The set of results and proofs seem to be a straightforward generalization of [Lyu and Li, 2019]. The technical contribution is not strong.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "j7Xrw1wMsj", "reviewer": "Reviewer_2hLy", "summary": "This work studies how the prediction margin changes as the training proceeds in a homogeneous network", "questions": "How close is the steepest descent to actual GD? Does the theory hold for GD?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem of prediction margin is important and of fundamental importance", "weaknesses": "I am not sure if I understand the meaning of the result. Also, I find the setting of the theory too restrictive\n\n1. I do not understand Figure 1-right. What does it imply? How does this relate to the theory?\n2. The theory only applies to the \"exponential loss,\" which does not make much sense to me.  \n\nLastly, I feel I should comment that I do not have the related background knowledge to assess the technical advancement made by this work", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "iqkvyZMpIc", "reviewer": "Reviewer_pCcn", "summary": "This paper studies the implicit bias of the steepest flow with respect to a general norm in deep homogeneous neural networks. Theoretically, they present two major results. 1) The soft margin will increase 2) The limit points of the parameter directions are general KKT points of the margin maximization optimization problem under some assumption of the norm. They also show some experimental results concerning the trajectories of different steepest descent algorithms and the connection to the implicit bias of Adam.", "questions": "- Can the authors extend the existing results on steepest flow to steepest descent? If not, it would be more accurate to clarify that the current theoretical results apply solely to steepest flow.\n\n- Is it feasible to demonstrate KKT point convergence for the general loss function?\n\n- In Lyu & Li (2020), tight convergence rates for both the loss function and parameter norms were established. Are there any mathematical challenges in achieving similar results here? Additionally, they showed that the soft margin approximates the normalized margin. Could you provide a similar analysis in this context?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper extends the result in [Lyu & Li 2020] to steepest flow for general norms with the lightest extra assumption on the norm. While previous papers focused on gradient descent and other variants of gradient descent, this paper gives a general result for any steepest flow.\nThe claimed results seem sound and the paper is nicely written.", "weaknesses": "The paper asserts that it presents results for the steepest descent; however, the theoretical results in Section 3 are limited to steepest flow. According to Lyu & Li (2020), additional work is required to extend the findings from flow to descent.\n\nRegarding the general loss function, the paper demonstrates that the soft margin is monotonically increasing but fails to address the convergence of KKT points.\n\nMoreover, the paper overlooks several relevant references, including:\n\n1. Chatterji, N.S., Long, P.M., & Bartlett, P. (2021). \"When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?\"\n\n2. Cai, Y., Wu, J., Mei, S., Lindsey, M., & Bartlett, P.L. (2024). \"Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization.\"\n\n3. Nacson, M.S., Srebro, N., & Soudry, D. (2019, April). \"Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate.\"\n\n4. Ji, Z., Srebro, N., & Telgarsky, M. (2021, July). \"Fast margin maximization via dual acceleration.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)