Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
Authors: Yuhang Cai
Kangjie Zhou
Jingfeng Wu
Song Mei
Michael Lindsey
Peter Bartlett
Venue: ICML 2025 poster (2025)
Keywords: Implicit bias
Non-homogeneous model
Deep neural networks
Gradient descent
Primary area: deep_learning->theory

Abstract: We establish the asymptotic implicit bias of gradient descent (GD) for generic non-homogeneous deep networks under exponential loss. Specifically, we characterize three key properties of GD iterates starting from a sufficiently small empirical risk, where the threshold is determined by a measure of the network's non-homogeneity. First, we show that a normalized margin induced by the GD iterates increases nearly monotonically. Second, we prove that while the norm of the GD iterates diverges to infinity, the iterates themselves converge in direction. Finally, we establish that this directional limit satisfies the Karush–Kuhn–Tucker (KKT) conditions of a margin maximization problem. Prior works on implicit bias have focused exclusively on homogeneous networks; in contrast, our results apply to a broad class of non-homogeneous networks satisfying a mild near-homogeneity condition. In particular, our results apply to networks with residual connections and non-homogeneous activation functions, thereby resolving an open problem posed byJi & Telgarsky (2020).

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
Yuhang Cai" Kangjie Zhou 22 Jingfeng Wu
Song Mei
Michael Lindsey 13 Peter L. Bartlett 14
Abstract
The implicit bias of GD is relatively well-understood when the network is homogeneous (see Soudry et al., 2018; Ji & Telgarsky, 2018 8; Lyu & Li, 2020; Ji & Telgarsky, 2020; Wu et al., 2023, and references therein). For linear networks trained on linearly separable data, GD diverges in norm while converging in direction to the maximum margin solu- tion (Soudry al., 2018; Ji & Telgarsky, 2018; Wu et al., 2023). Similar results have been established for generic ho- mogeneous networks that include class of deep networks, assuming that the network at initialization can separate the training data. Specifically, Lyu & Li (2020) showed that the normalized margin induced by GD increases nearly mono- tonically, and that the limiting direction of a subsequence of the GD iterates satisfies the condition of a margin maximization problem. Moreover, if the network is definable in o-minimal structure (see Section 2, which is satisfied for most networks), Ji & Telgar- sky (2020) showed that gradient flow (GF, that is, GD with infinitesimal stepsizes) converges in direction and that the limiting direction aligns with the direction of the gradient.
We establish the asymptotic implicit bias of gradi- ent descent (GD) for generic hon-eooggsnsuus deep networks under exponential loss. Specifi- cally, we characterize three key properties of GD iterates starting from sufficiently small empirical risk, where the threshold is determined by mea- sure of the network's 's non-homogeneity. First, we show that a normalized margin induced by the GD iterates increases nearly monotonically. Second, we prove that while the norm of the GD iterates di- verges to infinity, the iterates themselves converge in direction. Finally,
establish that this di- rectional limit satisfies the Karush (KKT) conditions of a margin maximization prob- lem. Prior works on implicit bias have focused exclusively on homogeneous networks; in con- trast, our results apply to broad class of non- homogeneous networks satisfying a mild near- homogeneity condition. In particular, our results apply to networks with residual connections and non-homogeneous activation functions, thereby resolving an open problem posed by Ji & Telgar- sky (2020).
(KKT)
However, the implicit bias of GD remains largely unknown when the network is non-homogeneous, an arguably more common case in deep learning (there are a few exceptions, which will be discussed later in Section 1.1). For instance, networks with residual connections or non-homogeneous activation functions are inherently non-homogeneous, As posted as an open problem by Ji & Telgarsky (2020), is unclear whether the implicit bias results developed for ho- mogeneous networks can be extended to non-homogeneous networks.
1. Introduction
Deep networks often have an enormous amount of parame- ters and are theoretically capable of overfitting the training data. However, in practice, deep networks trained via gradi- ent descent (GD) or its variants often generalize well. This is commonly attributed to the implicit bias of GD, in which GD finds certain solution that prevents overfitting (Zhang et al., 2021; Neyshabur et al., 2017; Bartlett et al., 2021). Understanding the implicit bias of GD is one of the central topics in deep learning theory.
In this work, we establish the implicit bias of GD for broad of non-homogeneous but definable net- works under exponential loss. Starting from the simpler case of gradient flow (GF), we identify two natural conditions of near-homogeneity and strong separability, respectively. The former condition requires the homogeneous error to grow slower than the output of the network, and the latter condition requires GF attain a sufficiently small empirical risk depending on the homogeneous error of the network. Under these two conditions, we prove the following implicit bias results of GF for non-homogeneous networks:
Contributions.
'Equal contribution 'University of California, Berkeley "Columbia University 'Lawrence Berkeley National Laboratory Yuhang Cai <will- cai@ berkeley..ddu, Kangjie Zhou <kz2326 2xx23260@olumiaaccds columbia.cdu>. Peter L. Bartlett <peter @ bere@@bbbrlee..d.....
Google DeepMind. Correspondence
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
1. GF induces a normalized margin that increases nearly

---

Implicit Bias of Gradient Descent for Non-Homogenecous Deep Networks
monotonically.
problem. Part of these results are generalized to steepest descent by Tsilivis et al. (2024). Using the notion of defin- ability, Ji & Telgarsky (2020) further showed the directional convergence and alignment for gradient flow. In the spe- cial case of two-layer homogeneous networks, Chizat & Bach (2020) characterized the limiting direction of (Wasser- stein) gradient flow in the large-width limit. For a two-layer Leaky ReLU network with symmetric data, Lyu et al. (2021) showed that gradient flow eventually converges to linear classifier. Different from these works, we aim to establish implicit bias of GD for non-homogeneous deep networks.
2. GF converges in its direction while diverging in its norm.
3. The limiting direction of GF satisfies the KKT conditions of margin maximization problem.
Our near-homogeneity condition covers many commonly used deep networks. In particular, it applies to networks with residual connections and nearly homogeneous activa- tion functions. In addition, we provide structural rules for computing the homoeeetogyn order of a network based on that of each layer in the network.
Non-homogeneous Networks. Before our work, there are few papers that extend the implicit bias results from ho- mogeneous cases to certain special non-homogeneous cases (Nacson et al., 2019; Chatterji et al., 2021; Kunin et al., 2023; Cai et al., 2025). The works by Nacson et al. (2019); Kunin et al. (2023) considered special non-howe non-homogeneous network, which is homogeneous when viewed as a func- tion of a subset of the trainable parameters while other parameters are fixed. The homogeneity orders for differ- ent subsets of parameters might be different. However, their results cannot cover networks with many commonly used non homogeneous activation functions. The work by Chatterji et al. (2021) showed the margin improvement for GD with small stepsizes for MLPs with a special type of heau-homogeneous activation functions. As a consequence, their results do not allow networks that use general non- homogeneous activation functions residual connections. In comparison, we handle large class of non-homogeneous networks satisfying a natural definition of near- hear-homogeneity, covering far more commonly used deep networks.
Our strong separability condition is a generalization of the separability condition used in the prior homogeneous anal- ysis (Lyu Li, 2020; Ji & Telgarsky, 2020). In particular, reduces the separability condition when the network is homogeneous. Later in Section 5, we demonstrate that this condition is satisfiable by any non-degenerate near- homogeneous network. Moreover, we show that GF reaches this strong separability condition from zero initialization for training a two-layer network with residual connections.
Finally, we extend the above results from GF to GD with an arbitrarily large stepsize under additional technical condi- tions. Altogether, we extend the implicit bias of GD from homogeneous cases (Lyu & Li, 2020; Ji & Telgarsky, 2020) to non-homogencous cases, thereby addressing the open problem posted by Ji & Telgarsky (2020).
Notation. For two positive-valued functions f(x) and g(z), we write f(x) S g(x) (or f(x) Z 9(x)) if fxx)= I cg(x) (or f(x) 2 cg(x)) for some constant e E (0, +00).
We write f(z)= g(x) if f(z) S g(x)= S f(x). We use Rgo[z] to denote the set of all univariate polynomials with non-negative real coefficients. For polynomial p. we use deg p to denote its degree. We use V to denote the gradi- ent of a scalar function or the Jacobian of a vector-valued function. We use || || to denote the e e-norm of a vector or the operator norm of a matrix. We use [n] to denote the set {1, 2...,... n]. We use conv.A to denote the convex hull of set A in Euclidean space. Throughout the paper, we de- fine o(z): = (og(1/(nz)) and b(x) = log 6(x) 22/((x). where n is the number of samples.
The work by Cai et al. (2025) is most relevant to us, in which they proved the margin improvement of GD for near- 1-homogeneous networks (see their Assumption 1 and our Definition I in Section 2). Our work can be viewed as an extension of theirs by handling near-M near-M-homogent M-homogeneouss networks for general M > 1, as well as proving that GF and large-stepsiee GD converge in direction to the KKT point of a margin maximization problem.
2. Preliminaries
In this section, we set up the problem and introduce basic mathematical tools used in our analysis.
1.1. Related Works
We discuss related papers in the remainder of this section.
Locally Lipschitz Functions and Clarke Subdifferential. For a function f D IR defined say I is locully Lipschitz if, for every E D. there exists a neighborhood U of æ such that flu is Lipschitz continuous. By Rademacher's theorem, a locally Lipschitz function is differentiable almost everywhere (Borwein et al., 2000). The Clarke subdifferential of locally Lipschitz function f
Homogeneous Networks. We first review prior implicit bias results for deep homogeneous networks. In this case, Lyu & Li (2020) showed that GD induces a nearly increas- ing normalized margin, and the direction of a subsequence of GD iterates converges, the limit of which can be charac- terized by the KKT conditions of a margin maximization
open set D, we
2

---

Implicit Bias of Gradient Descent for Non-Homogenecus Deep Networks
D is defined
(A2). [|h]] < ((10)))
(A3). |/(0; x) S ((100)).
@f(x)= = conv
lim Vf(zz) x E-100
lim Ti.
X-600
We make a few remarks on Definition 1. First, our near- homogeneity condition is modified from (3) instead of (2). In this way, our heaa-hooogeneity condition implicitly puts regularity conditions on the subgradient of the network, which will be useful in our analysis.
where ny E D and (1;) exists
which nonempty, convex, and compact (Clarke, 1975). In particular, if f'is continuously differentiable at x, then (1()) = (V)( Elements of (3) are called subgra- dients.
Second, every M ---homogeneous (see (2)) network for M 2 is also near-M homoogeeooous.. We see this by setting p 0 and (zx) C(x + 1) for sufficiently large constant C > 1 in Definition 1.
Gradient Flow. Let (x,, 14) )= be a binary classification dataset, where E Rd and yi E { for all i E [n]]. We denote a network by (0;-) : R²= - IR, where 0 E RR are the trainable parameters. Thoughout the paper, we assume f(0; x,) is locally Lipschitz with respect to I for every E [n.. We focus on the empirical risk under the exponential loss defined as
Third, a near- M -oy-hooggenouus network is also near- (M + 1) 1)-homogeneous according to Definition 1. Thus when we say network near- Saar-M-homogeneour the degree M should be interpreted the minimum degree M such that Definition 1 is satisfied. We will see that this interpreta- tion is necessary when we introduce the strong separability condition in Section 3.
= 1 Σ ((.f(O:xi)), (x):==
(())
Finally, we point out that many commonly used deep net- works are hear-homogeneous but not homogeneous. Exam- ples include networks using residual connections or non- homogeneous activation functions. This will be further elaborated in Section 4.
A curve = from an interval I to some Euclidean space T is called an are if is absolutely continuous on any compact subinterval of J. Clearly, the composition of an are and a locally Lipschitz function is still an arc. Following Lyu & Li (2020); Ji & Telgarsky (2020), we define gradient flow as are from [0, +00) RD that satisfies
O-minimal Structure and Definable Functions. The o- minimal structure and definable functions were introduced to deep learning theory by Davis et al. (2020); Ji & Telgarsky (2020) for studying the convergence and implicit bias of subgradient methods. We briefly review these notions below.
d0, dt E - for almost every t 2 O.
(GF)
Homogeneity and Neao-Homogeneity. Let M 2 1 be an integer. Recall that a locally Lipschitz network f00:x) is
An o-minimal structure is a collection S = (S,))= where each S, is collection of subsets of Iº" that satisfies the following properties. First, S, contains all algebraic sets in R", i.e., zero sets of coeffcceff polynomials on R". Second, S, is closed under finite union, finite intersection, complement, Cartesian product, and projection. Third, Si consists of finite unions of open intervals and points in R.. A set A C R. is definable if A E Sn-- A function D Rm with D C RR" is definable if its graph is in Sn4m. See Appendix A for a more detailed introduction.
M -t-hommgeeeous (Lyu & Li, 2020; Ji & Telgarsky, 2020) if
for every x E (x:)==.
for all a > 0 and 0 E IR,, f(a0;x) = aM x(0:)).
(2)
One can verify that the above is equivalent to: for every
x E (x,) 0 E R,P, and E x0;
(h. 0) - Mf = 0.
(3)
By the definition of o-minimal structure, the set of definable functions is closed under algebraic operations, composition, inversion, and taking maxima or minima. The work by Wilkie (1996) established the existence of an o-minimal structure in which polynomials and the exponential function are definable. By the closure property, commonly used mappings in deep learning are all definable with respect to this o-minimal structure, including fully connected layers, convolutional layers, ReLU activation, max-pooling layers, residual connections, and cross-entropy loss. We refer the readers to Ji Telgarsky (2020) for more discussion.
We generalize this definition by introducing the follow- ing near-homogeneous condition, which provides a natural quantification of the homogeneity error of the network f:
Definition 1 (Near-A4 - h.-oooogeneity). Let M 2 be an integer. A network f(0;x) x) is called near-M Morr--MMMoooeeeuee if there exist p, q E Rzo[æ] with degp, p, degq < M such that the following holds for every x (x:) 0 RD.
and h E (0:
(A1). (h, 0) - Mf(0; S (((10))):
3

---

Implicit Bias of Gradient Descent for Non-Hoomoeencous Deep Networks
Throughout this paper, we assume that there exists an O- minimal structure such that + exp(t) and the network 0 + x(); i = 1,.... n, are all definable. This as- sumption, together with the local Lipschitzness, allows us to apply the chain rule (see Lemma A.6 in Appendix A)
our innovation, which controls the homogeneous error when the network is non-homogeneous. Note that as ||0]| grows, the offset term Pa (I101) grows slower than the main term Φf (())) according to Definition 1. Therefore our modified margin is good approximation of the normalized margin.
to GF defined by subgradients. Moreover, this assumption allows us to leverage the desingularizing function (see Def- inition 6 in Appendix C.6, and Ji & Telgarsky (2020)) to show the directional convergence. Specifically, we apply inequalities (See Lemmas C.19 and C.20) under the o-minimal structure to establish the existence of the desingularizing function.
Our second assumption ensures GF can reach a state in which the network strongly separates the data.
Assumption 2 (Strong separabilityy condition). Let f(0:x) be network satisfying Assumption I. Assume that there exists time > 0 such that O2 given by (GF) satisfies
two
[(0.) < < <Pa(lll) /n.
(7)
3. Implicit Bias of Gradient Flow
where Pa is defined in (4) and n is the number of samples.
In this section, we establish the implicit bias of gradient flow for near-homogeneous networks. Our first assumption is
Our Assumption 2 is natural extension of the separability condition (that is, ((O.) < 1/n for some s) used in the analysis of homogeneous networks (Lyu & Li, 2020; Ji & Telgarsky, 2020). Specifically, for homogeneous networks, we can set p = O. in which P. = 0 by its definition in (4). Then Assumption reduces to the separability condition.
that the network is near-M-homogeneote (see Definition 1).
Assumption hoag-eooogeneuus network). Let M 2 1. We assume that the network| f is near-M-hout homoononeesuus with polynomials p(-) and q(-), as described in Definition 1.
For non-homogeneeus networks, Assumption 2 requires GF to attain empirical risk that is sufficiently small com- pared to function of the homogeneous error. Note that this condition can be satisfied by any non-degenerate near- homogeneous network that is able to separate the training data, which will be discussed further in Section 5.
Under Assumption 1, let p(z) := Ei=u azat. The follow- ing function is handy for our presentation:
M
M-1 1)a+11 x²
(a(x) Σ
01
M
M - 1/2'
In detail, Assumptions and 2, and the choice of pa together force the "leading term" in the network to be exactly M- homogencous. Therefore, the near- wear-homogeneity order in Definition 1 must be understood as the minimum possible one. This is precisely explained in the following lemma, whose proof is deferred to Appendix C.2.
One intuition behind the choice of Pa is that, for any f satisfying Assumption 9 = f - Pa satisfies a one-sided inequality of the homogeneous condition (3). This is demon- strated in Appendix C.2.
Normalized and Modified Margins. Under Assump-
Lemma 3.1 (Ncar-homogents order). Let f be such that
tion 1, we define the normalized margin (Lyu & Li, 2020)
as
(0;x0)
f(0;x) = f (0;x),
(0) min rE(n] ||0||a
(5)
The normalized margin is hard to analyze directly, due to the hard minimum in its definition. Instead, we analyze a modified margin, which increases monotonically and ap- proximates the normalized margin well. Specifically, the modified margin for gradient flow is defined as
where (0;x) is i-homogeneous with respect to 0. If satisfies Assumptions I and 2, then for every j E [n], we must have
= 0, if>> M.
(xxx))
#0, ifi= = M.
(0) = (C(()) Pa (110 |
7 (F(())
(6)
Furthermore, have f ((M) 0 for all E [m].
where d(x) := log (1/(nx)) and Pa is given by (4).
Margin Improvement. main theorem on the margin improvement of GF. The proof is deferred to Appendix C.I.
We are ready to present our first
In the definition of the modified margin, the (()) term produces a soft minimum of (0: x))= which ap- proximates the hard margin minie(m) y. (0: This idea appears in prior analysis for homogeneous networks (Lyu & Li, 2020; Ji & Telgarsky, 2020). The offset term ([]0 is
Theorem 3.2 (Risk convergence and margin improvement).
Suppose that Assumptions 1 and 2 hold. For (0)) given by (GF), we have:

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
For all L 8, the risk and the parameter norm satisfy
KKT Convergence. Provided with the directional conver- gence of GF, our next step is to characterize the limiting direction. To this end, we need understand the asymptotic behavior of the near-homogeneout network ff as ||@]| + cc. Since f is hear-M www.----ooggeeouss one can expect that f is close to an M M--homogenoous function for large 0. Motivated by this, we define the homogenization of f as
((O,) < P.((0)))))) /n.
Furthermore, we have
[(O()= ~ t(log 2)2-2/M
1
||0||| ~ (log t) tt,
2/M
where = hides constants that depend on M, y GF (Os), and coefficients qf
[(r0;
fH(0:x) == lim +-+00 y-M
(8)
The modified margin 7 GF (0.) is positive, increasing, and
The well-definedness, continuity, and differentiability of fH are guaranteed by the near-homogeneity of f (see Propo- sition 5.1 in Section 5). We will show that the limiting direction of GF satisfies the KKT conditions of the follow- ing margin maximization problem:
upper bounded. Moreover, 7 (G.) is an c-mmulippicatiive approximation of (0t), that is,
GF (0.) S (0))) < (1 + ct) , (0.), for all t s,
where
minimize |0]2, s.t. min f. 1. (P)
log n Pa ())
iEIm
O (llggt) + O. (C((O)) - 0ll
E ==
This generalizes the margin maximization problem in (Lyu & Li, 2020) from homogeneous to non-homogeneous cases. It is worth noting that when f is already homogeneous, (P) reduces to the same optimization problem as that in (Lyu Li, 2020).
This result generalizes Theorem 4.1 in Lyu & Li (2020) from homogeneous networks to near-M homogeneouu networks for M 2 1. In particular, recover their results when the network is of-hommgeneous, in which we set (a(x:) O. When the network is non-homogeneous, our Assumption 2 is stronger than the separability condition in Lyu & Li (2020). This is one of the key conditions that enables our analysis for non-homogeneous networks. In fact, Assump- tion 2 is necessary for generic homogenogessu model to exhibit implicit bias. We illustrate this point via the follow- ing example, whose proof is deferred to Appendix C.5.
To ensure the limiting direction satisfies the KKT conditions of (P), we need to compare the gradients of f and fH. This comparison requires an additional regularity assumption.
Assumption 3 Weeak-homogeneore gradient). Assume that the network f(0;x) is continuously differentiable with respect to 0 for x (x,)==1 and that lim (1)0:))/Tm) exists for all I and (xx)==r Assume that the limit
Example 3.3 (Necessity of Assumption 2). Assume we only have one sample: (I. = (1,1) E R² and our model is (()) = MM + M | 1 for A E R and some odd integer M 2 3. Then, f satisfies Assumption I with p(0) = | |
(V])(0;;)) = lim VS(00:))
M-
7-000
satisfies
If I does not satisfy Assumption 2 at 8, we have
V)(0:)) (VDn(0;)) S ((10))))
0, 5 0,
y 0:1 S 0 and [(,,) 2 1,
where r: R20 + R20 is a function such that
for all t 2 and O, following (GF).
r(x)
lim 2 2-++00
0.
Directional Convergence. Our next theorem establishes the directional convergence of GF for non-homogeneous networks. The proof is deferred to Appendix C.6.
MM
It is worth noting that for M 2 2, Assumptions and are satisfied as long as Ve (ef(0:x) x) component (M - homooggeesssss. See Lemma D.3 for a precise state- ment. In comparison, our Assumption 3 is less restrictive and allows for M = 1. The next theorem shows that the limiting direction of GF satisfies the KKT conditions of (P), with its proof included in Appendix C.8.
near-
Theorem 3.4 (Directional convergence). Under the setting of Theorem 3.2, let 0,- = 0,/[[e, be the direction of (GF). Then the curve swept by 0, has finite length. Therefore, the directional limit 0. oom O, exists.
Our Theorem 3.4 extends Theorem 3.1 in Ji & Telgar- sky (2020) from M-homogeneous networks to near-M- M homogencous networks for M 2 1. Our Assumptions and allow the application of tools (specifically the desingu- larizing functions) from Ji & Telgarsky (2020) for showing the direction convergence in the non-homogeneous cases.
Theorem 3.5 (KKT convergence). Under the same setting of Theorem 3.4, and additionally assume Assumption 3 hold. Then the rescaled limiting direction
0 min (0.;xx); 1/M
(E(n)
5

---

Implicit Bias of Gradient Descent for Non-Homogeneouu Deep Networks
satisfies the KKT conditions of (P), where O2 is the direc- tional limit in Theorem 3.4.
A block s(0;x): RR Rd + Rdd is called near-(M, NN- homogeneous if all of its components, x(0;x); for E [dy]. are near-(M, homogeneuus with the same polynomials Pa. 9s: ray ts.
This theorem is a generalization of Theorem 4.4 in Lyu & Li
(2020) from homogeneous networks to non- non-homoge non-homogeneous networks. Note that our margin maximization problem (P) is defined for the homogenization of the non-homogeneous network. This is because, asymptotically, every near- homogeneous network f can be approximated by its ho- mogenization SH (see Proposition 5.1 in Section 5). As an important implication, understanding the implicit bias of near homogeneous network can be reduced to understand- ing that of its homogenization. It is worth noting that Ji & Telgarsky (2020) also established the asymptotic alignment between parameters and gradients, which we leave as future work.
From Definition 2, it is easily seen that near- (0, N)- homogeneous block s(0; x) must be independent of 0 and near-N Bear-N-homogeneou in x, and vice versa. Below are few examples of near houur-ooooeeeuuus blocks used in practice.
Example 4.1. The following blocks are near-homogeneous:
A. For 0 b), the linear mapping s(0:x) Ax + b is near- (1, homooenooss..
B. Let M 2 be an integer. Then for 0 (A,,), the per- ceptron layer s(0:x)= = (Ax + b) is near-(M, M)- homogeneous, where the activation function à is one of the following: ReLU, Softplus, GELU, Swish, SiLU, and Leaky ReLU.
We have presented our results on the implicit bias for non- homogeneous networks. In the next two sections, we discuss the satisfiability of Assumptions and 2, respectively.
C. Max pooling layer, average pooling layer, convolu- tion layer, and residual connection are near-(0, 1)- homogeneous.
4. Near-Homogeneity Condition
In this section, we verify that a large class of building blocks used in deep learning are sea--homogeneous, and, by a composition rule, networks constructed using these blocks also hear-homogeneous. homooeoog......
D. The SwiGLU activation (Shazeer, 2020) is near- 2)-
homogeneous.
E. The linear self-attention (Zhang et al., 2024) is near- (2, -J-omooggenuus and the ReLU attention (Wortsman et al., 2023) is near-(4, homogenssssss
We denote block by x(0;x), where O are the trainable parameters in this block and x is the input (and the output of the preceding block). We use (x) as a shorthand for s(0; x). Then, a network is defined as
The following lemma suggests that near-homogeneity is preserved under functional composition and tensor product. Note the residual connection mentioned in Example 4. is not a specific block mapping, but a way to enhance an ex- isting block by adding the input from the previous block to the output of this block. Part C of Lemma 4.2 can thus be applied to compute the near-homogeneout order of net- works with residual connections. The proof of Lemma 4.2 is deferred to Appendix D.2.
f(0;x) =
=bb, o 2 o O 80
(x):
(9)
where 0 = (1 and s² is the i-th block. Here and in sequel, we assume all the blocks are locally Lipschitz and definable with respect to some o-minimal structure.
To deal with the compositional structure of networks, we need to introduce the following generalized definition of near-homogeneity, which takes both trainable parameters and input into account.
Lemma 4.2 (Composition and multiplication rules). Let the blocks =01;x) : RR: x R2 + Rdd and s2(0;; TRds x Rd + Rdo be near-(M, Ma)-honmggenouus and near- (Ma, M1) homogeneos,,, respectively. Then, the followings hold:
Definition 2 (Near- N Jhomoggeniity). Let M, N be two non-negative integers such that M + N 1. A func- tion s(0; x) is called near-(M, Noooogggessus if there exist Pa, 9a, ra. to E R [r] with deg p., deg 9 < . and deg a, deg t2 I N such that the following holds for every x LE (x4)= 0, and (he, hx) E x0;
(x) is near-(Mi + A. Let d2 = da. then sb o o MyMs, homoogeooom
(B1). (ho, 0) Ms)0:x) < ([
B. The tensor product s x): is near- (M1 +
[hx, x) Ns(O:x) S Pa [[)(0
My. M2 + -oooognnoesssuuss.
C. Let (d1, dz) = (d4, dz. de). then s s'(0;; + (00;x) is near- Ms), max(M2, M,))- homogeneous.
(B2). ||aa|| < (10 (|x| ). ||x || - (110)))
(B3). []s(0; x)| -
6

---

Implicit Bias of Gradient Descent for Non-Hoomoeescous Deep Networks
D. Let T Rdd + Re be linear mapping, then
5. Strong Separability Condition
T(s (01;))) is near-(M1, M2) homogeneouu..
In this section, we discuss the satisfiability of Assumption 2. We first give an intuitive explanation of why Assumption should be expected hold. Note that Assumption 2 equivalent to
E. Let f: R2 + ad be near-M5- h-oooogennne as a function of 03. then so, [(02; is near-(M1 + M2Ms)) homogeneuus.
log (1/((n((0)) ((O.) < E =Pa(ll0)))) /n + (a(1)
The following corollary establishes the near-homogeneity of network composed of hear-homogeneous blocks. We defer its proof to Appendix D.3.
> 1.
Recall that deg Pa S M - by Assumption 1. Thus As- sumption 2 can be understood as requiring GF to induce "lower-order" smoothed margin which is least 1. If the normalized margin (5) is asymptotically positive (as 0 grows), then the "lower-order" smoothed margin must diverge, hence Assumption must hold at some point.
Corollary 4.3 (Near-homogeneous networks). Consider a network defined as (9). If the block s' x0) is near- (M M hoo-ogneoosssssoeeeeeeeeeeeoouse for i E [L], then the network f is near-(M1, Ma)hhomngeneous with
In what follows, we establish a sufficient condition under which a non-honee non-homogeneous network satisfies Assumption 2. To this end, we establish below several important properties of the homogenization of non-homogeneous network.
Mi
Σ
M II M2
M2 = II M2.
(10)
In particular, J mear-Mi-hon neur-M--homoggeenu as f.function of for any fixed
Homogenization. The idea of homogenization appears in Section for constructing the margin maximization prob- lem, where its KKT conditions characterize the limiting direction of GF. Our next theorem rigorously controls the approximation error between a non-homogeneous network and its homogenization.
Based on Example 4.1, Lemma 4.2 and Corollary 4.3, we can show that broad class of commonly used networks are near-homogeneous, including the following examples:
Example 4.4. The following networks are near- homogeneous:
Proposition 5.1 (Homogenization)) Suppose that f satisfies Assumption 1. Then for every x E (x,) the homogeniza- tion of (0;
A. An L-layer MLP with k-th power of ReLU activation is near-(k" - (I 1) homogeneouss or near-I- homogeneous when k = The same holds when ReLU is replaced by other activation functions in Example 4.1 (B).
fH(0;x) = lim f(r0;x) + T.
exists and well-defined. Moreover as a function of x) is continuous, differentiable almost everywhere, and M hoooogennnou.. We also have
B. VGG-L (Simonyan & Zisserman, 2015) is near-L- homogeneous where LE {11, 13, 19}.
for every O, [f(0;)) fn(0:x)] (I(0))
C. Without batch normalization, ResNet-L (He et al.. 2016) is near-L-home Lear-L-homogeneous where L E {18, 34, 50, 101),52), and DenseNet-L. (Huang et al., 2017) is near- near-L-homogeneous where I. E {121, 169, 201, 264).
where Pa given by (4).
If. in addition, [(0: x) satisfies Assumption then JH (0; x) is continuously differentiable for every nonzero O, and that = [x]((==)))
To conclude this section, we comment that normaliza- tion layers and softmax map violate our near-homogeneity definitions. Intuitively, these blocks should be "near-0- homogeneous" as their outputs are bounded. However, near- heae-hhomgeeeity definitions only non-trivial for M > 1. As consequence, the softmax attention architec- ture also violates our definitions of near- hoao-nooggenitty. thus requiring a different treatment. We believe that our notion of near near-homon homogenetyy can be generalized to include those components, which we leave future work.
Proposition 5.1 ensures the well-definedness, continuity, and diffcrentiability of fH- Consequently, the following theorem guarantees that the strong separability condition can be satisfied by a near-homogeneous network, as long as its homogenization satisfies the (weak) separability condition of (Lyu Li, 2020).
Proposition 5.2 (A sufficient condition). Suppose that f satisfies Assumption 1. Then f admits a homogenization, de- noted by JH. Assume that JH satisfies the weak separability

---

Implicit Bias of Gradient Descent for Non- Non-Hoomoesssous Deep Networks
condition, that is,
6. Implicit Bias of Gradient Descent
[ for some O'.
In this section, we extend our previous results for GF to gradient descent (GD), which is defined as
Then, there exists constant c >>00000000 0 such that f with O₂ cl'' satisfies Assumption 2.
D++1 == 0 1)V)(
(GD)
where > 0 is fixed stepsize. Similarly, we will assume the network f is near- hear-M--omoogeneuus with and (see Assumption 1). For GD, the definition of Pa needs to be slightly modified. Let p(x) = Σn aax", For M 2 2, we define
To further elaborate the idea of homogenization, we provide the following compositional rule.
Proposition 5.3 (Homogenization of networks). Consider network given by (9), where each block s0 is near- (Mi M2) homomeneoss (see Definition 2). i = 1..... L. Then each block 8² (0;;x) x) admits a well-defined homoge- nization
M
(i + 1)at+1
x²
01 M - M//2
if 2 1,
-i
s' (r(10,;;22)
H4 (0,x)) == lim "1-
M1 Mi 71
22
Pa(x): =
M
(i + 1)a++1
M -
x²
1=2
Moreover, the homogenization network (9) is well- and satisfies
202
x.2 +
01
+
if <
M -1 2
M - 1/2²
x) = sh,0. o sH. o ...... shi (x).
(12) For M 1, we define Pa (a(x) = a 1/2). Compared to (4), (12) replaces the linear term with quadratic poly-
A Two-Layer Network. We next provide a two-layer net- work example where GF with zero initialization can prov- ably reach a point that satisfies Assumption 2. The two-layer network is defined
nomial (x + +1/22. This is purely for circumventing a tech- nical issue when ||@]| is small (see the proof of Lemma F.7 in Appendix F.1).
f(0:x) = w] x w/ x an x) a2 W2 x):
To handle the discretization error introduced by GD, we need stronger version of the strong separability condition. Assumption 5 (Strong separability condition for GD). Let f(0: ; x) be a network satisfying Assumption 1. Assume that f is twicely differentiable for @ and that for some constant
(11)
where 0 == (W1. W2, 01, a2) are the trainable parameters, and yp is the leaky ReLU activation function,
<(x)= == max(x,
0 asa <.
A > 0, we have
Our example (11) is motived by the two-layer network con- sidered in Lyu et al. (2021). However, their network is homogeneous, while ours non-homogeneous (but near- 2-homogenoous) due to the residual connections. Similar to Lyu et al. (2021), we consider symmetric and linearly separable dataset.
if 2 2 A (100 A
Vaf(0:))]| <
if = 1
for every X E (xx) For Pa given by (12), assume that
deg Pa 2 1 if M 2 2, and that there exists a time s > O such that
Assumption& 4 (Dataset conditions). Assume that the dataset (x,, y. satisfies max; ||x||| for some unit vector w. and margin 7 > O; moreover, n is even and (1i+n/2, Xitn/2) (1,, x:) for 1, ... n//2.
|| I 1 and min, y: w, 2 Y
1 1) _
((0.) < min
e
ne² Bn
where B is constant depending only on (M, P. q) and A.
Note that the network (11) is not Lipschitz continuous, thus (GF) is not well-defined. Instead, we study the small step- size limit of gradient descent for (11), which well-defined under our assumptions. In the next theorem, we establish that the stall-stepsize limit of gradient descent with zero initialization for (11) satisfy Assumption 2.
Note that in Assumption 5, the stepsize 17 can be arbitrarily large as long as the empirical risk L(O.) is of the order of (11r)). We note that Proposition 5.2 can also be adapted to guarantee the satisfiability of Assumption 5.
We consider the following modified margin for GD:
Theorem 5.4 (A two-layer network example). Consider the network f given by (11) and a dataset satisfying As- sumption 4. Let (0)) be the limit of GD iterates with initialization Ou = 0 as the stepsize tends to zero. Then there exists $ > 0 such that f with O, satisfies Assumption
exp ( (e (I @11) (())))
GD (0)
(13)
| M
where 4(x) == log nx Tor(
8

---

Implicit Bias of Gradient Descent for Non- Hon-Hoomoesssous Deep Networks
In the following two theorems, we extend our results for GF to GD. The proofs are included in Appendix F.2.
Applied Mathematics Competitive Portfolios program under Contract No. AC02-05CH1 1231,, of the NSF and the Simons Foundation for the Collaboration the Theoretical Founda- tions of Deep Learning through awards DMS-205 #8 4639, DMS-22108277, CCF-2315725, and of the ONR through MURI award N00014211243 and N00014-24-S- B001.
Theorem 6.1 (Risk convergence and margin improvement for GD). Suppose that Assumptions and hold. For (0z) given by (GD) with any stepsize > O, we have:
and
For all t t>> 8, the risk and parameter norm satisfy
[(O,) < min {
1
1
Pa(ll0.1))
Impact Statement
nE?
Brj
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Furthermore, 00, have
1 ((6,) nt(log 2
|0 ~ (log n
where = hides constants that depend on M, y GD (0.). and coefficients of q. but not n).
References
Bartlett, P. L., Montanari, A., and Rakhlin, A. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
The modified margin 7. (.D((,) in (13) is increasing and bounded. Moreover, 7 (0.) an e-muliiplicative ap- proximation of (0t). that is, for all s,
Borwein, J. M., Lewis, A. S., et al. Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer Publishing Company, Incorporated,, 2000.
CG (0:) S (0.) s (1+
where c + 0 as t co.
Cai, Y., Wu, J., Mei, S., Lindsey,
M., and Bartlett, P. L. Large stepsize gradient descent for homooooggsssus two-layer networks: Margin improvement and fast opti- mization. Advances in Neural Information Processing Systems, 2025.
Theorem 6.2 (Directional and KKT convergence for GD). Under Assumptions and the same results in Theorem 3.4 hold (GD) with any stepsize nj >> O. Under Assumptions 3 and 5, the same results in Theorem 3.5 hold for (GD) with any stepsize > O.
Chatterji, N. S., Long, P. M., and Bartlett, P. When does gradient descent with logistic loss interpolate using deep networks with smoothed relu activations? In Conference Learning Theory, pp. 927-1027. PMLR, 2021.
7. Conclusion
We show the implicit bias of gradient descent (GD) for training generic non-homogeneous deep networks under ponential loss. We show that the normalized margin induced by GD increases nearly monotonically. Moreover, GD con- verges in direction, with the limiting direction satisfying the KKT conditions of a margin maximization problem. Our results rely on homogenittt condition and strong separability condition, both of which are natural generaliza- tions of the conditions used in prior implicit bias analysis for homogeneous networks. In particular, our results apply to networks with residual connections and non honhoomggeeous activation functions.
Chizat, L. and Bach, F. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on learning theory, pp. 1305 1338. PMLR, 2020.
Clarke, F. H. Generalized gradients and applications. Trans- actions of the American Mathematical Society, 205:247- 262, 1975.
Clarke, F. H. Optimization and nonsmooth analysis. SIAM, 1990.
Coste, M. An introduction to o-minimal geometry. Istituti editoriali e poligrafici internazionali Pisa, 2000.
Acknowledgements
We thank Fabian Pedregosa, Nathan Srebro, and Matus Telgarsky for their helpful comments and discussion. We gratefully acknowledge the support of the NSF for FODSI through grant DMS5-023505, of the Founder's Postdoctoral Fellowship in Statistics at Columbia University, of the Sloan Fellowship by the U.S. Department of Energy, Office of Sci- ence, Office of Advanced Scientific Computing Research's
Davis, D., Drusvyatskiy, D., Kakade, S., and Lee. D.
Stochastic subgradient method converges tame func- tions. Foundations of computational mathematics, 20(1): 119-154, 2020.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual leam- ing for image recognition. Proceedings of the IEFE

---

Implicit Bias of Gradient Descent for Non- Non-Hommgessous Deep Networks
conference on compuler vision and pallern recognition, pp. 770-778, 2016.
Tsilivis, N., Vardi, G., and Kempe, Flavors of margin: Implicit bias of steepest descent in homogeneous neural networks. In NeurlPS 2024 Workshop Mathematics of Modern Machine Learning, 2024.
Huang, G., Liu, Z.,, Van Der Maaten, I.., and Weinberger, K. Q. Densely connected convolutional networks. In the Proceedings the IEEE conference on computer vision and pattern recognition, pp. 4700-4705 2017.
van den Dries, L. and Miller, C. Geometric categories and o-minimal structures. Duke Mathematical Journal, 84(2), 1996.
Ji, Z. and Telgarsky, M. Risk and parameter convergence of logistic regression. arXiv preprint arXiv: 2018.
Wilkie, A. Model completeness results for expansions of the ordered field of real numbers by restricted pfaffian functions and the exponential function. Journal of the American Mathematical Society, 94))105111094, 1996.
Ji, Z. and Telgarsky, M. Directional convergence and align- ment in deep learning. Advances in Neural Information Processing Systems, 13:1717--17186 2020.
Wortsman, M., Lee, J., Gilmer, J., and Korbblihh, S. Re- placing softmax with relu in vision transformers. arXiv 2023.
Kunin, D., Yamamura, A., Ma, C., and Ganguli, S. The asymmetric maximum margin bias of quasi- homogeneous neural networks. In The Eleventh Interna- tional Conference on Learning Representations, 2023.
preprint arXiv:2309.083:
Wu, J., Braverman, V., and Lee, J. D. Implicit bias of gradi- ent descent for logistic regression at the edge of stability, In seirty-seventh Conference on Neural Information Pro- cessing Systems, 2023.
Loi, L. Lecture 1: O-minimal structures. The Japanese- Australian Workshop on Real and Complex Singularities: JARCS III, volume 43, pp. 19-31, Australian National University, Mathematical Sciences Institute, 2010.
Zhang, C.,, Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Lyu, K. and Li, J. Gradient descent maximizes the mar- gin of homogeneous neural networks. International Conference on Learning Representations, 2020.
Zhang, R., Frei, S., and Bartlett, P. L. Trained transform- ers learn linear models in-context. Journal of Machine Learning Research, 25(49):1-555 2024.
Lyu, K., Li, Z.,, Wang, R., and Arora, S. Gradient descent two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34: 12978-12991, 2021.
Nacson, M. S., Gunasekar, S., Lee, J.. Srebro, N., and Soudry, D. Lexicographic and depth-sensitive margins in homogeneous and non non-homogeneous deep models. In International Conference on Machine Learning, pp. 4683- 4692. PMLR, 2019.
Neyshabur, B., Bhojanapalli, S., and Srebro, N. A pac-bayesian approach to npectrally-nommalzzed mar- gin bounds for neural networks. arXiv preprint arXiv: 1707.09640 2017.
Shazeer, N. Glu variants improve transformer. arXiv preprint arX2:2000..05202, 2020.
Simonyan, K. and Zisserman, A. Very deep convolutional networks for large-scale image recognition. 3rd Interna- tional Conference on Learning Representations (ICLR 2015), pp. 1-14, 2015.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on sepa- rable data. The Journal of Machine Learning Research, 19(1):2822 282222878..22 2018
10

---

Implicit Bias of Gradient Descent for Non-Hoomogencous Deep Networks
A. O-minimal Structure
this section, we give a brief introduction to the o-minimal structure. mainly follow the notation and definitions in Telgarsky (2020).
Definition (O-minimal structure). An O-minimal structure is collection = (Sn) where S, is a subset of IR" that
satisfies the following properties:
1. Sj is the collection of all finite unions of open intervals and points.
2. S, includes the zero sets of all polynomials (algebraic sets) on R if RI Fnl, then for E R p())(x)) 03
Sn-
3. S, closed under finite union, finite intersection, and complement.
4. S is closed under Cartesian product: if A E S.. and B E Sn, then A x B E Smin-
5. S is closed under projection II, onto the first n coordinates: if A E S,41, then II, (4) E Sn.
Then define the definable functions.
Definition 4 (Definable sets and functions). Given an o-minimal structure function f D + R with D I" is definable if its graph is in Sn+m-
A C RR is definable A E Sn
The following properties of definable sets and functions can then be derived (check Coste (2000); Loi (2010); van den Dries & Miller (1996)).
Proposition A.1 (Property of definable functions). We fix an arbitrary o-minimal structure S. Then the following properties hold:
1. Given any a E R and any definable functions f.g: : D I. we have a.f + 3g and fg are definable. If g + 0 on D, then f/g definable. If
D, then fü definable for any positive integer L.
2. Given a function f : D + R", let fr denote the i-th coordinate of its output. Then f is definable if and only if all ft are definable.
3. Any composition of definable functions is definable.
4. Any coordinate permutation of definable set is definable. Consequently, if the inverse of a definable function exists, it's also definable.
4. The image and preimage of defianble set by definable function is definable. Particulatry, given any real-valued definable function f, all of (0), and f ((0, oc)) definable.
5. Any combination of finitely many definable functions with disjoint domains definable. For example, the pointwise maximum and minimum of definable functions are definable.
Once we have these properties, we can observe that almost all the network structures are definable.
Lemma A.2 (Definable network structures, Lemma B.2 in Ji & Telgarsky (2020)). Suppose there exist ki do, di,... .... di >> O and L definable functions (g1.....9L. where Rd x x Rdd x R - Rd; Let h (x; (): = 91 91(2, w) and for 2 I
h,(x,w) w) = (z, w)... h- w).
then all hj are definable. It suffices if each output coordinate of gj is the minimum or maximum over some finite set of polynomials, which allows for linear, convolutional, ReLU, max-pooling layers, and skip connections.
One important corollary that this allows us composite and multiply the near-homogeous blocks.
Corollary A.3 (Composition and multiplication of definable blocks). Given two definable block mappings: s1(01;x)
Rd. TRi - T&'s and (2(0; x) Rdd x Rdd Rd, then,

---

Implicit Bias of Gradient Descent for Non-oonmoesssous Deep Networks
d2 d3. the composition (0;3) x) 81 80(0:82((0))) x)) is definable.
s x0:x) 51 (0 x) 52 (2 x) definable.
If = d3. x(01;x)) x) 81 (0 x s2(01;x) is definable.
Proof. This a direct consequence Lemma A.2 and Proposition A.1.
Definable functions have good properties, especially there is some stratification which makes them piecewise differentiable. However, the gradient, even the Clarke subdifferential, of definable function, is not well-defined everywhere. To overcome this issue, we need the local Lipschitz continuity.
Definition 5 (Local Lipschitz continuity). Given function f D + I with an open domain D, we say f is locally Lipschitz continuous if for any x E D, there exists a neighborhood of x such that f is Lipschitz continuous on U.
Similar to the definability, the local Lipschitz continuity preserved under composition and multiplication. It's worth noting that the Clarke subdifferential of locally Lipschitz function is well-defined everywhere.
Lemma A.4 (Clarke subdifferential of locally Lipschitz functions, Corollary 6.1.2 in Borwein et al. (2000)). Given locally fimctinn f D + R with an open domain D, the Clarke subdifferential (z(z) is nonempty, compact, and convex for all x E D.
Now we will assume all the models and block mappings are definable and locally Lipschitz. Since block mappings are multivalue functions, we can use the Clarke general Jacobian for them. Similarly, for locally Lipschitz functions to R", the general Jacobian is well-defined for all points.
Corollary A.5 (Clarke Jacobian of locally Lipschitz functions, Proposition 2.6.2 in Clarke (1990)). Given a locally Lipschitz function f D + TR. with an open domain D C Rm, the Clarke Jacobian (f(x) is nonemply, compact, and convex for all I B D.
Following the notation in Ji & Telgarsky (2020), let (z) denote the unique minimum-norn subgradient:
0f(x) = arg min c(f(2)
||*"||
(14)
Another important property is that for definable functions, it admits chain rule almost everywhere. Lemma A.6 (Chain rule, Lemma B.9 in Ji & Telgarsky (2020)). Given locally Lipschitz definable f: D R with an open domain D. for any interval I and any are z + D, it holds that for almost every E I that
df((z) di
de z dl /
for all = E 02())
Moreover, for (GF), we have for almost every
2 0,
d0,
dLi
Jh.,
1106o11
dt
dt
dpž JLi), dt
d (0.) -F Oc.).
dt
Clarke has the following lemma to characterize the subgradient of the composition of functions.
Theorem A.7 (Clark chain rule, Theorems 2.3.9 and 2.3.0 in Clarke (1990)). Let 21,..., Zn Rdd R and f R2 - be locally Lipschitz functions. Let (f =)) ((=1 .. (x)x) be the composition of and z. Then,
a, :0 a (f) h 02s(1)) }
a(f o (x) S conv Σ
Recall that:
1 n n Σ (0xx.)
((0)
We have the following corollary which characterizes the min-norm subgradient of the exponential loss.
12

---

Implicit Bias of Gradient Descent for Non-Hommgeescous Deep Networks
Corollary A.8 (Subgradient of the exponential loss). For the exponential loss ((O), there exists h, x0((0x;)) such that
OC(0)
1
(0.x)))))) y
e
1=1
Proof of Corollary A.8. This a direct consequence of Theorem A.7 and the definition of the exponential loss.
Similarly, we can characterize the subgradient of the composition of block functions.
Corollary A.9 (Subgradient of the composition of block functions), Given two locally Lipschitz block functions 81 (01; x)
RR d2 Rdda and 82 (2(02; x) Rd x Rd + R2, we have
0øsi (0 $2 ( 02;x; x)) c (ai, 02 hi): (2), E x01((1 hi E (2,52(02;)))
0x (01, S2 (02;)) C conv oz h2 02 E 8x (01;x), h2 E (x x))
Proof of Corollary A.9. It follows from Theorem A.7 and the definition of the block functions.
Here we use 0g (0 to denote the corresponding Jacobian. Note that 01 E Rd 02 E Ra h1 E Rdaxds, h2 E Rd2xds, Once we have this, to verify some properties of Jacobian of 81 a 82, we can focus on the Ja- cobian of 81 and 82.
The o-minimal structure eliminates many bad geometry. allowing us focus on the good part of the optimization landscape.
B. Proof Overview
In the main text, we present several results on the implicit bias of GF/GD for hear-homogeneous networks. Below we briefly describe the approaches we use to prove these results, with actual proofs deferred to the subsequent appendices.
Margin Improvement and Convergence Rates. We first sketch the proof of Theorem 3.2 (GF), and then highlight the major technical innovations the proof of Theorem 6.1 (GD), as compared to the case of GF. The key ingredient for proving Theorem 3.2 the following lemma, which establishes the monotonicity of the modified margin under the strong separability condition.
Lemma B.1 (Restatement of Theorem C.5). Denote L, [((s) and Pt = ||O,]| Under Assumptions I and we have L, < Pa(pe) / for all 2 and
dlog Glog><5((B) (F())) dl
|5c,112P (0C,, 0,),
p Co - PP(())) 2 0.
(15)
The proof of Lemma B.1 is similar to the proof of Lyu & Li (2020, Lemma 5.1). Since G (0.) only depends on L, and Pr. its growth rate can be attributed to two quantities: dLt/ /dl and dpt/dt. We use the same argument as that in Lyu & Li (2020, Proof sketch of Lemma 5.1) to estimate each of these two quantities, which finally leads to the lower bound (15) on (O.))(())))))))) Further since
(CC,) -.c.)-p(pp)) 0 - C. - (P((e),
we know that the strong separability condition is necessary for the lower bound (15) at = 8, and can be established for t 1 s using continuous induction. noteworthy that while we follow a similar proof scheme as (Lyu Li, 2020), the design of the modified margin GF is completely novel and highly non-trivial.
From this lower bound, the "margin improvement" part of Theorem 3.2 directly follows. For the "convergence rates" part, we use the monotonicity of modified margin to upper and lower bound -dL:/dl, thus establishing convergence rates for L.- The claim for P: can be proved similarly.
For the proof of Theorem 1. we need to establish a lower bound on log y GD (0.+.) ) lo similar to (15). Due to the discrete nature of GD, the Hessian of log GD should also be taken into account when dealing with log as function of f.. To address this challenge, we analyze modified loss (()) = exp(pa exp(pa(()@l))) (I))))))(( that is closely related to log GD.
13

---

Implicit Bias of Gradient Descent for Non-Hoomgeencous Deep Networks
We establish tight upper bounds the Hessian of ((O,) in terms of L, and Pt, thus leading to a tight lower bound on (0+). Notably, our lower bound allows for arbitrarily large step size 7/, as long as g(0,) 0 /n), which is guaranteed by Assumption 5. In contrast, Lyu & Li (2020) assumes that the step size is upper bounded by function of the initial margin, preventing it to be large. The proof of other parts in Theorem 6.1 is completely analogous to the case of GF.
log (0 l
Convergence to the KKT Direction. The proofs of Theorems 3.4 and 6.2 largely rely on the techniques developed in Ji Telgarsky (2020). As before, we will first sketch the proof for GF, and then explain how to adapt it to establish KKT convergence for GD. For GF, define the are length swept by the direction of 0,:
f
ao
Ge
du.
du
Similar to Ji & Telgarsky (2020), we construct a desingularizing function Y that controls the growth rate of S. using that of (7- 7f (0+)), where 7 = lim, 7 (0,):
Lemma B.2 (Restatement of Lemma C. 14). There exist R > 0, > O and a definable d V on [0, [0,
such that for a.e. large enough with [ > R and 7 (0t) > 7 v, it holds that
dçt dv (7. - GF (0.))
(16)
dt
dt
for some constant c >> 0.
The proof of the above lemma is similar to that of Ji & Telgarsky (2020, Lemma 3.1). Integrating both sides of (16), we deduce that lim Se < co. Therefore, 0, must converge to some O.. This establishes directional convergence of GF path.
To go further and show that 0, satisfies the KKT conditions (P), the key ingredient is to show the asymptotic alignment between Og and hM (0,) for subsequence of t, i.c..
(0 hys (0 ))
lim ((tm) lim
fm 000
fm +00
|0 | (0.)]
where we define
hy = Σ e (..xx.)))) (H((;;;
as a proxy of xO. We establish the following bound by looking further into the first inequality in (15).
Lemma B.3 (Restatement of Corollary C.26). For any 1o > t large enough, there exists t, E (f1, such that
1 (l.) - 1 S M log 0r,1 log (0,,1
log 7 GF (0.,) - log 7 MFGGFOO)) (0.,)
(8(1))
where pı (2)) + 0 as + co.
As y (0)) converges and ||ee]] diverges, the right-hand side of the above inequality converges to O. Hence, there must exist a subsequence { converging to 1. This shows that 0g and h (0,) asymptotically aligns along this subsequence, and consequently verifies that 0, a KKT point.
To establish directional convergence for GD, need show that the discrete are length swept by 0 is finite, i.e.,
Σ 0 - -0.l < <0.
(17)
Similar to the proof of GF, we construct a desingularizing function V. and show that there exists constant c > 0, such that for all large enough
@ 0.1 <c(V (V (r. (0)) - v - GD (0.--c0(00.)) (0((0++)))
(18)
14

---

Implicit Bias of Gradient Descent for Non-Homogeneeous Deep Networks
where 7 GD is the modified margin for GD and 7, + 7 GD (0,). To this end, construct are connecting all GD iterates using line segments, and carefully estimate the spherical and the radial parts of this arc, addressing several new technical challenges that arise in the analysis of GD.
Finally, summing up both sides of (18) immediately leads to (17), thus proving directional convergence of 0, along the GD path. The proof of KKT convergence is completely similar to the case of GF.
C. Proofs for Section
In this section, we will provide the proofs of the results for (GF) in Section 3. Recall that have the following notation:
1
((x) log
V Vo.
Pe |00ll f1 L(Os),
nz
f((0) = f(0:x,), f((0)
fmin(0) min f((0). sE(n)
For function of the time, h(t), we use h (t) shorthand of h
C.1. Margin Improvement
In this section, we always assume /(0; x) satisfies Assumption with Pa defined (4). We can directly verify the following property of p and Pa- Lemma C.1 (Property of Pa). For p and Pa. defined in (4), we have
for every z, (x)x p'(x) S (z)
M Proof of Lemma C.I. Recall that p(x) 0 axx and
(i + 1)a++1
Pa(x)
M
M 1/2
Hence,
M-1
i(1 + 1)a;+1
Ma
Ma
+p'()) - (pa(x)= = Σ
x² +
+((i+ (i+ 1)44112
M x +
M -
M - 1/2
==1
a1/2
M 1/2 < O.
This completes the proof of Lemma C.I.
The following bounds from Lyu & Li (2020) connect fminn(r) and Le-
Lemma C.2 (property of Jmin (0)). For the Loss function L defined in (I), we have
for every 0, log nL(0) Fmia (0) < log (())
Proof of Lemma C.2. Recall that we consider the exponential loss
((0) = F((0)
1=1
Therefore, get that
1
1 Jmma (0) < (())
(())
< n
log nL(0)
< Smin S log
n
[())
This completes the proof of Lemma C.2.
15

---

Implicit Bias of Gradient Descent for Non-Homogenecous Deep Networks
We have the following fundamental lemma from Lyu & Li (2020) about the dynamics of the GF.
Lemma C.3 (Decrease of the risk). For (GF), we have for a.e. t 2 S.
dcp
( dp
dlog
| (0C,, 0.)
1 2 0.
dt
2 di
dt
Pi
Proof of Lemma C.3. By lemma A.6, we have for a.e. 12
dh,
=1
by lemma A.6
dt
(dC,,02)
|1 (0C,, 02)²
Projecting 0 to spherical and radical parts
dpt
|| - 116,, 0,)
1 d
+
Since
(dLi, O&)
p
dt
P
2 dt
1
dp
d
llo
|| p3 (b 0,)
d Pt
1
1 dpp
Since dt
p..
dt
dt
pi
Pt
2pp dt
We have completed the proof of Lemma C.3.
The next lemma shows the parameter norm is increasing under the strong separability condition.
Lemma C.4 (Increase of the parameter norm). Under Assumption I, for almost every 2 8, we have
dpp (Mø(L.) Cp >0.
Li e /
dt
Proof of Lemma C.4. By Lemma C.2, we have
1
f.(0,) 2 Jmin (0.) 2 log nL:
= (Le))
Then we have for almost every / 2 8,
1 dpp
(-ŌL,, 0i)
by Lemma A.6
2 dt
1
(((0))
y/ (b; 0z)
By Corollary A.8
1=1
2 M
c
f.(0.) f.((.) - L. ('()))
By Assumption 1
n
i=1
M 1
1100.) d(C)) C. p'.))
Since f.(0.) 2(C))
n
ML. Lr.
Note that
C. Pele /n Mδ(C.) Mpp(P.).
Additionally, Lemma C.1 implies (p)(x) 2 ('( p(()). As consequence of these two inequalities, we have
1 dpp 2 Mo(C.)C, C'))) -'(p))) 2 0.
dt
We have completed the proof of Lemma C.4.
16

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
Theorem C.5 (Monotonicity of the modified margin). Under Assumptions and 2, we have La Pa(oe) /n for
8.
Moreover, we have
1og?
GF (0:)
| - -0
2 0, for almost every 2
(19)
dt
Pf ( -
As a consequence, the modified margin 7 GF (0.) is increasing for 8.
Proof of Theorem C.5. We first show that L, < pa((p)) /n implies 7f (0.) is positive and increasing. Then we show L, < palll)) for all t 2 by contradiction.
Step 1: the condition that La < <e palpp) /n implies that (0,) is positive and increasing. Recall that
L. < Palle)) /n
+ Mő(C,) > (Pt(
Under this condition, the modified margin yf (0.) defined in (6) is positive. Moreover, we have for almost every 2 s, d dlog y GF (0.)
d log (o(L)) Pa(pt)) M log Pr. dt M log Pt dt
dt
dt
ac, LiP'(Pe)Pp L. (ő((,) - Pa(pt))
By Lemma C.4 we have Pr. increasing, which implies log pt/ pr/dlt > 0 almost everywhere. Then we have for almost every
t 2 s.
dh.
1 dep
d dlog Pt. dt
|06. - 186,, 0,)3
+
By Lemma C.3
dt
2 dt
p
p'(pe) M
alog Pt
|/ (,L,, P
Lu ((L))
M
By Lemma C.4
dt
Furthermore,
P'(lt))
d d Pt dt
d
log
P Pr.
C.p' L.
M M
By
dt
Applying the above two bounds in the derivative of log GF (O.), we get for almost every 2 8.
dogg GF (Ft)) dt
dc, (pec(p MM
d Po
de
(o(()) -Pa(ee)) (o(C)) (p))p p'(P)) M 11
dt
d log Pt
|0 - - 0,)2
d dlog Pt.
.M
+
M
(,(((C)) PP((p))
dt
(g((( Pa()))
dt By Lemma C.I
(((((i)) Pa(p:)) -M
dloggt
d log Pt
|0 "oL,,0,)"
M
((((L))) Pp(()))
dt
dt
P. (f((C) - -Pa(P))
|00, 12p2 - (ŌC,, 0,)
(o(C.) - Pp():) 2 0.
That is, (0:) is increasing.
Step 2: proving L, < palle)) /n for all / by contradiction. For L 8, L, satisfies the condition by Assumption 2.
Let 81 be the first time where Le, violates the condition, that is,
81 = sup ( La < c Pa(ed) /n, for all s <t< 8'}.
We need to show 81 = +00. If not, we have 81 < oc. Note that
Palpi)
exp (log (1/nC,) Pa(pi) exp() -M)))))M)))))))))))
n,r,
17

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
Since Lu < <E-Pa(Pe)/m for L < 81, by Step I we have (F,) and Pj are both positive and increasing. Hence increasing for St. < 81. So we have
Pa (ee) n2,
e
Po(pe)
Palp))
851<8
nhe
nh..s
Since O, forms an are and the left-hand side is a continuous function of Or, it is continuous as function of (. As a consequence, we have
P-Palee))
Pa(p))
C., < e pa(en))) nn.
nC2,
nC.
Since Le and (Pte) are both continuous functions with respect to & (0, is arc), this leads to that there exists 82 > and for all < t $2, L₁- < Palpp)) /n. This is contradiction. So we have Ls < e polpe) )) /n for all 2 This completes the proof of Theorem C.5.
C.2. Proof of Lemma 3.1
Proof of Lemma 3.1. Recall that we have the decomposition:
x(0x))=
(0) (0;x), x (x:)
where (0; x) is i-homogeneous with respect to 0. Then Assumption implies that (0; x) = 0 for all <> M. By Lemma C.1 we have
Mpa(c) - ('(e))-p((()))) (3 p(x))
Let (0;x) f(0;x) (l())) Then have
(0, Veg(O; Mg(0;:)
(0, vof(O:x)) - Mf(0xx) (0, VP. (I + ((0))
(0, x)) - -MS(0;x) -P)((10)) + ((O0))
2 -P'([[0)) P', [1)0 + MPP(() 2 0.
Let h(a;)) = g(00.: (0)1110,)
Then we have
dh(ax))
1 dg(a0,;:)
M g()0,;x)) (a 00 M
da
(a) da
(a0,, Vo(afg;x)) M g(a0,;x) a M+1
00 |
(a0,, vo(ad,;x)) Mg(a0g;x)) a+ 1211
0.
Since L(O.) < PP((((0))))) /n, we have h(1;x) = g(0,:))//i)) (((a:)\(aa(ll..]) > 0. As + co, h(a;x) > 0. Note that
lim x)a:x) = lim g(a0,;x) lim a-000
f(a0,:x) - (a 0..1) ((:)
> 0.
000
a0000
(a
|00 M
This leads ((a)) (0;x) # 0. This completes the proof of Lemma 3.1.
C.3. Convergence Rates
We will show that (F(()) is good approximation of (0.). Before proceed, need one auxiliary margin.
((,)) = ((L.)
(20)
Pt
18

---

Implicit Bias of Gradient Descent for Non-Hoomoesscous Deep Networks
Lemma C.6 (Modified margin is good approximation), Under Assumption and Lu Paloo)) /n, for the (GF), we have
GF (0)) S (0)) <0(0)) - (1+ log + (a() 7 (0t).
((C,) Pa(
Proof of Lemma C.6. Note that we have fmin 2 o(C,) from the proof of Lemma C.4. Then, we have
y (0.) = o(C,) - Palpe)
o(L.)
(0,))) S Jmmn (0.) = ((.).
Pi S
Pt
Pt
For the last inequality, note that (0) S log 1 from Lemma C.2, then using the definition of o(-) we have Z,
(0,)
((xr) - -P((p)) S ((fr) - Pa(()) -1+ log Pa (pr)
(mi)
log 1 E.
(G,)
((Lx) - Pa(pt)
This completes the proof of Lemma C.6.
We will later show that
log + (pt)
log n + (P()t) 0. log E
(L.)) - Pa(At)
This implies that (F() is good multiplicative approximation of 7(+)). We need to characterize the behaviors of L, and
Lemma C.7 (Upper bound of the risk). Under Assumptions and for (GF), we have
L. = 2 1)2-2/M
where the hidden constant depends 7 (0.)
Proof of Lemma C.7. Recall that in Lemma C.3, we have shown that
dLt dt
1 dpt
p
dt
By Theorem C.5, L. < e Pa(pp) /n for all 2 s. Note that when Ls < Paalpe) / /n, we have for M 2 2.
(M 1/1))6((C.) > (M - (/2)
(M - 1/2)(i + 1)0st1
(M - 11/2)a1 M 11/2
M-i Pi +
M-1
Σ
+ 1)a14101 + -aa-pppll =p(t)(
This leads
Mo(L.) - p((x)) ((C)) > 0.
(21)
2
By Lemma C.4, we have
dC,,
1
(MC-d(C))
2
dt
1
(Cro(C)))²
By the inequality above
407
19

---

Implicit Bias of Gradient Descent for Non-Hoomoesscous Deep Networks
(0)))) a
4()(C))) (C(o(C)))
By the definition of (0,))
1
GF (0,)
(o(C))))
Since 7
4
GF (0.) 7
f. (M(e))) 2/M
By Theorem C.5
clt (o(L))) 2-2/M
where c= (..( Equivalently, have
d 1
2 c
(d(L.)) 2/M
dt nLt
Let G. == ni, and S(x)) Sg. (logr)2 27 dt. Then we have
g
S(9i) 2 - (t s).
(log 9,) +
Note that
1
exp pa(pa)) > 1.
Go
2
nh.
nC,
We can invoke Lemma G.2 to get
G. 2 5-1 c (1 (t)
12(t(logtt)--33 = La ([(ooo(()))
()10gt))-2/M 2/M
12
This completes the proof of Lemma C.7.
Then we control the rate of the parameter norm with respect to the risk. The following lemma characterizes the M-near homogeneity.
Lemma C.8 (Near homogeneity). Let f(0;x.) be locally Lipschitz and M M-mear-homogeneuus then for ||@]| 2 there exists a constant B, such that
If(0: x;)l S B, 110,1| for all i E [n].
Proof of Lemma C.8. We can fix an index and let c = max -e|=r ( x/)l/MMM. For any ||0|| 2 r, we let 0 = r0/1|0] Consider g(t) = f(0; x,) Since f is locally Lipschitz, g(t) is also Locally Lipschitz and its derivative exists almost everywhere. Then we have for almost every > 0,
(t() (Vof x;), 10,) Mf((t.x,))
0
M-1
a-
+1+
t2
We can also show that (() M-1 Note that [g(1) S crr.M. Since g(() is locally Lipschitz, it's also absolutely continuous. Hence we can apply the fundamental theorem of calculus to get
(f xx) x.
0(10))/)))
1
= + J. |01lrr
g()t)
S cs + $ʃ 1001//
Ig (t(())dtt
S Sar + a-
20

---

Implicit Bias of Gradient Descent for Non-Homogenecou Deep Networks
This is equivalent
|f(0;x,) (a/r c) +.) 1101
Let B, a/r c1- We complete the proof of Lemma C.8.
With this Lemma, we show that y and y GF are both bounded. Lemma C.9 (Boundedness of margins). Under Assumptions and 2. we have
GF (0.) S <0,) & Bllp.
Proof of Lemma C.9. Note that Pr is increasing. Therefore, Pt Ps. Then we can apply Lemma C.8 to get
(0,) min (; x.)
S B
Therefore, 7 (0.) S (0.) S Billl
Lemma C.10 (Rate of the parameter norm). Under Assumptions 1 and for (GF), we have
p = 0 (118 1 2
where the hidden constant depends on 7 GF and q.
Proof of Lemma 1. Recall that
((())) 2 gf (F((). 2f
Then we have
PM S 7 (0,)
(Le) 0(108
log 1n] D
On the other hand, by Lemmas C.2 and C.8 we have
1 nL:
p..¹ 22 log (
B Fmin(0.) 2 log
Combining these two bounds, we have
M = (111 - D
We complete the proof of Lemma C.
Lemma C.11 (Lower bound the risk). Under Assumptions and 2, for (GF), we have
C, = 22
1(log 1)2-2/M
where the hidden constant depends on (F.)) and q(x).
Proof of Lemma C.I.I Note that by Lemma A.6 and corollary A.8,
d0,
OC(O.)
Σ
f (0xx.. yph
di
i=1
where @ (14) denotes the minimal norm subgradient and h; 00((0; x;). Therefore under Assumption have
|| S e fu(xxx)) |bsl S C. (').)....
21

---

Implicit Bias of Gradient Descent for Non-Hoomgesseous Deep Networks
By Assumption and increase of Pt we can bound (p() by bllpe||a-=1 for some constant b. Then have
dc,
S c o
o( (108 E.
2-2/34
|0c,ل| - C3 Pt
2M-
di
By the definition of 5()) in the proof of Lemma C.7, this implies that
d
S
Sc. c.
dt C,
Therefore we have
1
sc - 5)) (1t(log ()20///)))2/ = L. =2=
L,
[llog 1)2 1)2-2/M
This completes the proof of Lemma C.11.
Theorem C.12 (Rates of the risk and the parameter norm). Under Assumptions I and 2, for (GF), have
c. = 0 = E(llgg 1)2-2/M )-
P: = =(logt)) &)
where the hidden constant depends on (F(O)) (0.) and q(x))
Proof of Theorem C.12. By Lemmas C.7 and C.11, we have
L. 2
E(log 1)2-2/M8
By Lemma C.10, have
M 0 (10g log ( [,
Ologt) P: == (1ogt)
We complete the proof of Theorem C2
Lemma C.13 (Multiplicative error). The multiplicative error of (F(()) satisfies
log n + (pe) (LL)) (pt) - 0.
Proof of Lemma C.13. Applying Theorem C.12, we have
log C,
= O(log(), Pa(pt) = -0MM- O(log () 111M/))
Therefore we have
log n + (pt)
( (log (o2gt)/2///
= - (log t)
- 0.
log Σ. log (p()
logt
This completes the proof of Lemma C.13.
C.4. Proof of Theorem 3.2
Proof of Theorem 3.2. By Theorem C.5, we know that y 7F (F,)). is increasing and L, < PPolPi) for all 2 s. By Theorem C.12, we get the rates of p and L, By Lemma C.13, we know GF is good approximator of y. This completes the proof of Theoormm 3.2.
22

---

Implicit Bias of Gradient Descent for Non-Hoomgenncous Deep Networks
C.5. Proof of Example 3.3
Proof of Example 3.3. Note that for this example have p(0) =10| Po(() M M-1 and f(0) 0* + +p)(
This means Assumption 2 is equivalent to:
((0.) exp(-f(0.))
+ 0ºd
02 0.
If the above condition does not hold, then 0₂ - Note that is a stationary point for ((0). So if (GF) initialized from o,, it cannot produce positive parameters in the future, that is, 0, S for every t s. Hence, (GF) cannot minimize the loss exhibit any implicit bias. This completes the proof of Example 3.3.
C.6. Directional Convergence
The main idea of the proof show that the curve swept by O, has finite length, thus 0, converges. We use Ce to denote the curve swept by O.. Another important quantity in our proof the modified margin 7 GF defined in (6).
In Theorem 3.2, we show that 7 (0t) is nondecreasing with some limit y+ (0, +00) and ||0:|| oc.
Motivated by Ji & Telgarsky (2020), we will invoke sophisticated but standard tool in the analysis of definable functions, the desingularizing function. A desingularizing function will witness the flow is well-behaved and the curve swept by Og has a finite length.
Definition (Desingularizing functionn. function v (0, + is called a desingularizing function when v is continuous on [0, v) with (0) = O, and continuously differentiable on (0, with V > 0.
The following Lemma plays a key role in proving the directional convergence of params. Lemma C.14 (Existence of desingularizing function). There exist R >> 0, > 0 and definable desingularizing function W on [0, v), such that for a.e. large enough t with ||0,1| > R and 7 (F()) > * v, it holds that
dc dt
< dv (7. - 7 (0.))
dt
for some constant e >> 0.
The central part of this subsection is to prove Lemma C.14, and then we will use this lemma to prove Theorem 3.4 in Appendix C.7. To prove Lemma C.14, we need many valuable tools. We present the tools first.
Following the notation in Ji & Telgarsky (2020), given any f that is locally Lipschitz around a nonzero 0, let f (ōf(0), and 0.f(0) = Ōf( 0,
-
be the radial and spherical parts of (0) respectively. We use
a, o(C) (p()
to denote the numerator of (F.). Before we dive into the proof of Lemma C.14, need to characterize the Clarke subdifferential of (.)).
Lemma C.15 (Subdifferential of GF.) For (GF), we have
VL:
forany any VL, E aci
Oa:
L.
VL.
Ma,
GF (. (0.)
for any vL. E Oh.
Laph
PM
M+I
pr
Proof of Lemma C.I5. The proof of these two results is direct consequence of the definition of Clarke subdifferentials.
Recall that
0f(x) = conv
lim Vf(x)) : lim Fy where E D and Vf(x;) exists
(-000
23

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
Recall that a, and (0,(),) are differentiable functions of Lt- Next, we prove that: for a locally Lipschitz function a(x:) Rd IR and differentiable function b(.) R R, we have
@2(b(((x)) {6laata la(a) h for any h E dga(x))
By Theorem A.7, we know that
@2]b(a(x)) C (bla(s)) h for any h E d,a(x)).
remains to show the other direction. For every h E (,)(2), there exists lim; 2, = x: such that h lim,-soc Va(z;). Since lim;->oo a(x;) = a(x), we have
lim ((a(z:))=
lim b'(()))
1-000
Here, use the facts that b is differentiable at axx;) and that is differentiable 24, which implies that b(a(-)) is also differentiable 24. Hence we have
{t' (ax) h for any h E 0_a(x)) c 0.(b(a(x)))
The above result completes the proof of Lemma C.15.
Consider the following two special elements within the set of subdiffcrentials,
da. = HL.
L. P'((:)))..
(22)
UL, P)((:)):
Ma. M+1
0- (0,)
(23)
L.p. PM
These two elements are crucial for our analysis, enabling us to deal with the non-hom non-homogeneity. Specifically, this together with Lemma A.6 leads to Lemma C.17. Another remarkable point is that Ji & Telgarsky (2020) did not consider these special elements, instead, they considered da, and GF.GF (0:). This is because their model is homogeneous so Pa = 0 in their analysis. is straightforward to check that da,, and -d. are all in the same direction for homogeneous models. However, for non-eooogess models, we need to consider the above elements. Thanks Lemma A.6, we can use any element of Oa, and O- GF (0.) with the chain rule, that is, have
(o.))) (5o(0)).-5c.))
(F.) (000)=600) (0,), -ōC.).
dt
dt
This helps us to understand the increase of 7. (0:) in terms of the spherical and the radial change of dc,. To further elaborate this, we define:
0, (da, 0.)0.,
i Ea. - 0,ac,, (F,) = Ô- GF (0.) - -F (0.).
(24)
0, OF (0.) = (Ô, GF (0.), 0.)
(25)
With simple calculations, we get the following inequalities. Lemma C.16 (Decomposition tilde subdifferential). Under Assumptions and for (,,)F(,,) and , (O.) in (24). we have
Ma 2 0, 014; = d.C.
(ō 0,) 2
(26)
Pr
L,
( GF (0.), 0,) 2 0, 81 GF (0.) = d,C,
(27)
L.p.
Proof of Lemma C.16. We prove the results for and 7 GF (0.) separately.
The first inequality for at. We have
24

---

Implicit Bias of Gradient Descent for Non-Hommgenscuu Deep Networks
(b,a,, 0.) (dC,, 01)
(-) P(((t))
P'((pt)
ft
Lipt
1
e 11(0.) (VF.())). 0.) - P(()
iml
1
n
(.00))(M p' P'((tt)
PLipt
1
f((0.) (M (Mlog(1/nf)) - p'(p)) (pe)pe)))
Plpp
i=1
1
f((01) Ma;
Ma: = Ma 2 0.
e
nLipt
Pt
1=1
The second inequality for a, We have
01a;
0L.
(p.))
10--- 8h.
- -r.(
o.
Lt
Lt
0,C,
Uic.
L,
L
L1
The first inequality for (O..). We have
(0c,, 0,)
((()
Map
01)
P(((Pt)
Ma
(0.)) (0.), 0.)
Lipl
M+T
Lip.
P/
M+T
Pt
P'((Pt)
Mar
nLept M+1
Pb:
PM-11
i=1
f.00.) (M)((0.) pp(())
P(((
Mor
nhipt
M+I
Pt
1+1
im
Ma
f.(0.) (Mlog( (1/n.)) - p'(()) - (p()))))))
nLipe
M+I
M41
f((0.) Ma;
Mai
0.
nhipt
M+1
Pt
M+1
The second inequality for 7 GF (0.). We have
HC.
Ma..r
HL,
().().)
Ma.0,
0.) 0.)0,
L.p.
PM
M+1
C.p.
P.M
Pt M+1
Pi
OC,
D,C.
D.C.
C.p.
C.p.
MT
C.ph
This completes the proof of Lemma C.16.
After detailed characterization of òo,, we can give a decomposition of the increase of margin. This decomposition will help us construct the desired desingularizing function.
Lemma C.17 (Decomposition of radial and spherical parts). Under Assumptions and for almost every 1. 2 8, we have
d GF (0.) = (,0
GF (0.) 0,
(B))]
(28)
dt
25

---

Implicit Bias of Gradient Descent for Non-Homogenseous Deep Networks
and
|0, a,l Pt
dşp
|| C.ll
and
(29)
dt
Pr.
Proof of Lemma C.17. We prove the two equations separately.
Proof of (28). By Lemma A.6, we have for almost every t 2 5.
d- (0.) (0.) -d..) = (0,, (0.), -d,L.) ( -
dt
To prove (28), we need to show two arguments:
( (0.), 0z) and (-d,fe, 0.) share the same sign.
) and -i Lt point the same direction.
The first argument. By Lemma C.16 we have that (F.) 2 0. On the other hand, we have
n 1 A(0 [OO (Vi(()))))
(-V,,,, 01)
n
f(00.) Mf.)0.) (p:)
By Assumption
ML)((C) (p))
By Lemma C.2
MoM
By Lemma C.1
20.
GF By monotonicity of 7 (0.) in Theorem 3.2
Therefore (0 GF (0,). 01) and (-d,L,, 0₂) share the same sign. This completes the proof of the first argument.
The second argument. This is direct result Lemma C.16.
Proof of (29). The first part is also direction result of Lemma C.16. For the second part, since O, is an are and ||0,|| 2
|0,1| > 0, it follows that 0 is also are. Moreover, for almost every t 2 0,
dē, d0, 1/d0, do. 0,
U1C.
0
dt dt dt
Pr.
Since 0, is an are, dó./d/ /d/ and |d[l are both integrable. By definition of the curve length,
dd,
Se
dt.
dt
and for almost every 2 s, we have
dc(t)
d0,
|0_C Cill
dt
dt
Pt.
This completes the proof of (29). Therefore, we have proved Lemma C.17.
Then we need some inequalities to connect (0, 0, L.) and (0 (F,,), -F The main idea is to show that their ratios are close, that is,
| |0
(F (A,))l
GF GF.))
The technique use a to bridge these two ratios.
26

---

Implicit Bias of Gradient Descent for Non-Hoomogencous Deep Networks
Lemma C.18 (Inequalities between de and oF (0t)). Under Assumption 1 and the condition L. Paloa) /n, for almost every & have
||8,aell 2 (0 M-1
(30)
and
M log + 2M Pa
1 GF (0.)ll v
(31)
Pt Af+1
Combining these two inequalities, there exists a threshold 81 > > 0, for almost every t 2 81, we have
|| 2 GF (0.)pt M+ (0
(32)
Proof of Lemma C.18. We prove the three inequalities separately.
Proof of (30), We expand the formula. For almost every 2 we have
[| = (day, 0.) 2 Mat Pt -M M-1 2 (0.)))
By Lemma C.16
By definition of 7 (0.)
By monotonicity in Theorem 3.2
Proof of (31). For almost every 2 8, we have
(dL, 0.) Cipt
(Pt)
Ma.
(daz, Oi)
Ma
(F ( GF (0.), 0,)
(33)
P
Pa
M+1
Pt M+1
Now we derive an upper bound for (da,, O1). For almost every 2 we have
n
(dac, 01) L,
F(O.)) (V.. 0.) - (pt'
f((0.) (.00MM]((0)) (..0).) (pr) L.P's (pt)
By Assumption
F:(0.) f(((.) + (od + (pt)))
f.(0.) + Mp.(Pt).
By Lemma C.I.
nL: im1
By Lemma G.I, we have - Vx(u)e= = VT(U)(( v) s T TT)). Applying this to the above inequality, we have (dur, 0.) S M log(1/L.) + (p.)
Therefore,
(oa, 0.) - Ma; < M log(m) + 2M (pt).
Plugging this into (33), we have proved
M logn + 2M
M+1
This completes the proof of (31).
Proof of (32). To prove (32), we combine (30) and (31) to get
GF (0t)p?
||0,a:11 2 -. (0:)p. M- >
10, GF (0.))l.
(0.))l
log n + (p.)
27

---

Implicit Bias of Gradient Descent for Non-Homogeneoou Deep Networks
Since Po(Pt) is a polynomial of Pt with degree (M 1) and Pt is increasing with rate ([log(()) dx) (by Theorem 3.2). there exists threhold 81 such that for almost every & 2 81, we have
M M- log 2pa(pt) S Pt
Therefore for almost every 2 81, we have
| 2 - (0.)pt A+ 10, ,1 (0,)
This completes the proof of (32). We have proved Lemma C.18.
We proceed prove Lemma C.14. The following two us construct the desired desingularizing function. We refer the readers Appendix B in Ji & Telgarsky (2020) for the proofs of them.
inequalities in Telgarsky (2020) will help
Lemma C.19 (Lemma 3.6 in Ji & Telgarsky (2020)). Given a locally Lipschitz definable function with an open domain
D {or ||]|||| for any e, 0, there exists > O and a definable desingularizing function Va on [0,v) such that
[((0))=-10000)0
ff)) E v) and | 2 c||=||| [|,
Lemma C.20 (Lemma 3.7 in Ji & Telgarsky (2020)). Given a locally Lipschitz definable function f with an open domain D {o ||]||| > for any X > 0, there exists v > 0 and a definable desingularizing function W on [0, v) such that
2 VI max (1
if(()) (0,
Proof of Lemma C.14. Recall that we have the following decomposition by (28):
dr GF (0)) = 10,, 000] (0.) 4.Il.
dt
Two cases will be considered in this proof:
Case 1: | GF (e.)) is larger, and we will apply Lemma C.20 for construction.
Case 2: - (0:) [0 is larger, and we will apply Lemma C.19 for construction.
The two cases will be determined by the ratio of || (F(,))((0))))) (0:) and ( Specifically, case corresponds
|Ø GF (0:) - p. (l
(34)
and case 2 corresponds to
| (0,)1l 2 pž 1 (F,,,c((0)) (0.)))
(35)
Case 1. By (32), we have
1 2 (F(()) 1+1 (F
2 (0.)p)
M+ |10b GFe.ll
By (34)
= (0,) | arll-
By Lemma C.17
(36)
Now we transfer this inequality to the ratio of ||ō Cell and [e Note that
1 (day, 01)
(ōC,, 0z)
| (da,, 0,)
(P()
Pc
Lipt
28

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
(1)
(0C,, Q.)
Cell-
(37)
Lipt
Li
L2
On the other hand, we have
1 |0_ _ cil.
(38)
C,
Plugging (37) and (38) into (36), have
| 2 GF (0.)p, -
(39)
On the other hand, we know that there exists $2
such that for almost every 2 82. have Pr 1. Hence we have
((,1Il - | GF (0,) + 1 GF (0+)
(1 + p || GF (0:)
By (34)
2p | ( (0.)
By Pr
(40)
Therefore by (28), we have
d (0.)
2 110, (0.)1
dt
, GF (0)) GF (0,
2 PP ?
By (39) and (40)
2 2 76
or (0.) OF (0)) 01 G.ll
By 1 GF (0:) 2 1 (0.)
dG
1F (0))
By Lemma C.17
(41)
dt
Now we invoke Lemma C.20 to construct the desingularizing function. We apply it to the definable function % - (F,,) with x= = Then there exists v >> O and definable desingularizing function v on [0, v1) such that
8 (7. GF (0:))p: 118, GF (0.) 1, if (0,) 2 7 V/1
Plugging (41) into the above inequality, we have
d7 (F,)) (7 -7 (F())))((0))
dG.
if (F.)) 2 % V2-
dt
dt
This completes the proof for case 1.
Case 2. By (28), we have
dy GF (0.)
dgp dt
dt 2 10 (0))11|014 Cell = of
(42)
For almost every t 81 > s>> 0, we have P: 2 1 and
| CF (0.)) Z P ||0, GF (F(())) 2 11 (0.))l
This leads to
1 (11_ GF (0))) + 11
||_ ( (0,) 2 2
GF (0,))) 2 2 1 GF (0,))
Plugging this into (42), we have
GF (0.)
2
Pt
P1 110
(0.)
dG.
>
Pt 11 (0.)
dc
(43)
df
2
dt
2
dt
We invoke Lemma C. to construct the desingularizing function. We apply to the definable function 7. 7 GF (0.) with 1 and 17- = 1 Then there exists 1/2 >> and definable desingularizing function V on [0, 242) such that
(7 - - (0.( GF (0.) 2 1, if (F.))) 2 74 122
29

---

Implicit Bias of Gradient Descent for Non-Hoomogencous Deep Networks
Plugging (43) into the above inequality, we have
dy (0.) dt
dg dt
2 GF (0,)) (0,))
if (f,0((,) (0,) 2 7+ U2-
This completes the proof for case 2.
Combining the two cases. Since 11 - 2 is definable function, it is nonnegative or nonpositive on some interval (0, v). Let v = max { 1, }2)- Then we have for almost every large enough such that Pt 2 and 7 (0,)) 2 7s - V, and holds that
M
log n + (pr S Pe
dy Or.G((0.) (0.)
dc.
dt
cl -f (0,)) dt
for constant 0. This completes the proof of Lemma C.14.
C.7. Proof of Theorem 3.4
Now are ready to prove Theorem 3.4 with the powerful tool, Lemma C.14.
Proof of Theorem 3.4. Let to be large enough that the condition in Lemma C.14 holds. Then we have
lim St S Soo + cV 7 (0t.)) S cc.
This completes the proof of Theorem 3.4.
C.8. KKT convergence
We now prove Theorem 3.5 by verifying the KKT conditions. Recall that the optimization problem (P) is defined follows:
min |012 s.t. y: x:) 2 1 for all [n].
Recall that f() (0;x) and Fmin ( = min.e(n] f(()). We use (H) to denote y: x0, and fH.min to denote minseja] (0). Recall that by Proposition 5.1, fH,i is continuously differentiable on E /(0]. We also assume that is continuous differentiable with respect to 0 on /²/(()) in Assumption 3. For simplicity, we use h, to denote f and hH to denote V fH, We define
5.00b bi hH
Σe e Fe(0.) F.(0.)H.ii 1=1
Notice that h and hи weighted sum of hy's and hH,''s respectively, where the weights the same. Actually, this ha very tricky. Unlike h V., hH is not the negative version of gradient of
n1
(H)
(0:x..
It is just a weighted sum of V fH.s. Next, we define the KKT conditions and approximate KKT conditions for the optimization problem (P).
Definition (KKT conditions). A feasible point 0 of (P) is KKT point if there exist A,,..., An 2 0 such that
1. 0 Σ A,HHi; = for some hH,1...., hH satisfying hH = f(.:(0) for every i E [n]]
2. For every i [n). A₁ (0) 1) 0.
Definition (Approximate KKT conditions). A feasible point 0 of (P) is an (e, point if ther exists A1...., An 2 such that
1. ||0 ΣT AchHiill S e for some hH.,,... h satisfying bH,; fH,((0) for every e [n]:
30

---

Implicit Bias of Gradient Descent for Non-Hoomoeencous Deep Networks
2. For every E [n]] A4 (H. (0) 1| S 8.
The first step is bound the difference between f and fH,min- Lemma C.21 (Bound between fmin and fH,min). Under Assumptions I and for any c, there exists $2 0 such that
0,
0e
for almost every 2 82,
Sc.
(min((.)) 2/ar
(JH.min (0)) 1/M
Proof of Lemma C.21. By Theorem 3.4, we have O, converges to O.. Then we are going to show that f(().)/ converges
for all i. Recall that in Proposition 5.1, we have
1f(0;x) - [H(0s; S (1(0:.))
Therefore we have
F((O.)
FH.((.))
Pa(pt)
7 0, as l + co.
P
Pt
Pi
M
Hence we have
J((O,)
(H,,(O.) pt
lim
lim
(0.)
10000
Pi
As consequence, we have
Pt
Pt
1
lim
lim
(f((0))
1/M
t-000
(OH)) 1/M
(0). 1/M
Because we only have finite number of we must have
Pt
lim
lim (fH.min (0.)) (0.)) 1/M
(Juin (0)))
1/M
((..mi((0)) 1/M
Therefore, for every e, there exists 82 > > 0 such that for almost every 2 82, we have
0,
0, Se E.
(fmin (0)) 1/M
(0.)) 1/M
This completes the proof of Lemma C.21.
Due to the above lemma, we can focus on
0, = 02/ (f/(fmmin((0)) 1/M
and verify it satisfies the (e, 8)KK) conditions. The key construct the coefficients A;
JH.min (O:)pee-fice f(().)
(e,)
(44)
n ||bH]
We define the following key quantity for our proof.
B(t) = (., hu hn)))
(45)
|00.1| |
Lemma C.22 (Lower bound of the homogeneous margin). Under Assumptions and 2, we have
SH.min (0.)
GF GF(()) 0.
0 M
Specifically, there exists B. such that for all t,
JA. / (0.) ||0.1| < B.
(46)
31

---

Implicit Bias of Gradient Descent for Non-Hoomogeseous Deep Networks
Proof. Note that
JH,min (0.) 2 Sini (0.) Pp(pt)
by Proposition 5.1
2 log
Li Palpe).
by Lemma C.2
Hence,
HH.min (0c)
2F.) 2 27 > 0.
00 M
And,
FA 1/M
(1el- S (0))) - B.
This completes the proof of Lemma C.22.
Lemma C.23 (0 satisfies the (c, 6)- conditions). Under Assumptions 1 and 2, there exists 82 > >> 0 such that for a.e.
t 12 82, O, is an (e, point of (P), where
= 1- and == nB² + (pr
M fH.uin (0:)
Proof of Lemma C.23. We need to verify:
1. 1. - E d S e for some h.. h satisfying hH [H,((0) for all i [n].
2. For any i E [n]. > (0) S.
Note that we only verify one side condition 2, since by the definition é, we have (H. 2 1 for all i.
Condition 1. We expand the left side of the inequality:
(O:)pee- f((0,)
0,
X hH.
H,min (0,)p: O,
F-1/M
-
JHmmin (0.)
7-1/M
1
H.min
fH..
hhll
1=1
i=1
e (((O))
T-1/M 1/M
(0c)p: 0, - -J,
1/M (0c)
[m,((0.)
H,min
hH
-11 (Oe)p: (o. (o.- [hall [hT]]
hH
where the second equation is by the definition of Ô and the homogeneity Jn,,, and the last equation by the definition of hy. Hence we have
hH
0,
A
s B2
0
= 2 - B(t))
This completes the proof of Condition 1.
Condition 2. For condition 2, we have shown that C, e palo)) /n. This leads to
T.(O.) Pa(pt) Jn.((0.) Jc(O.) Pa(pt) 0.
Therefore we have (0.) 2 1 since 0, 01/ (F. I/M It suffices to show Σ (HH.. -1) s 8. This because
2-2/M (0.)
( - -1)
Pt.H.min
1
Σ
c (.(0)) (fH,.(0,) FH.miu (6:))
h4
iml
32

---

Implicit Bias of Gradient Descent for Non-Hoomgeencous Deep Networks
Pt Ht.H, (0t)
2/M
(1:(0:)--mmm01)) (fH,)(0)) (M.))
|| (0.)
i=1
PeJH.miu 2/M (0e)
n
(1i(0)) (
fmin (0.) + 2pa (pt))
||Ha|] Sonillemmmme (0+)
i=1
By (0t)
- f(((:)) - Pa(pt) in Proposition 5.1
Pt. Pt.H,min
2/M (0+)
(1 (p)(
(47)
| emin (Oc)
By ((.)
Tmin(())) 2 and --x S when 2:
The remaining part is to lower bound [Нl] We have
hH. 0.)
ball
0,1l Il
Σ - f.((.) (O.)
n|
0
Me (0.) JH. (0))
by fH, 2 and Lemma C.21
nttt
Plugging this into (47), we get
(fH,,(0))-1))
-1)
n1
2/M (0:)
+ (pr)
by (46)
M
fH. (0.)
nB²
1 (p)
s M (H.min(()))
This completes the proof of Lemma C.23.
LI
It remains show that and ō are both close zero. The second is easy verify because SH,min is M-homogeneous. Lemma C.24 (6 goes 0). Under Assumptions and we have
8 = nB2 1 (pr)
- O, as t + co.
M fH, (O.)
Proof of Lemma C.24. Recall that
fm,(O.))
lim 1000
(O.)
PM
Denote the limit 7. Then there exists 83 O such that for almost every 2 83, we have
(H.(
2/./2 = fn.((0.) 2 7. /2. P.
Then we have
nB² 1+ 2p 2p (pt)
lim 05 lim
0. My.pl /2
1000
This completes the proof of Lemma C.24.
We next show O ((V1-)(()) is close zero. However, ((1) might not converge it is given by
(0, h4)
B(t) = |0:
hH e f((0.) (H.,
b
33

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
where hy might not converge in direction. To address this issue, our strategy is to show that there exists subsequence (4x (20 such that ((tx) - 1. To this end, need to characterize ((t) using the stronger Assumption 3. By Assumption and Proposition 5.1, there is function r(z) o(x=M-1 as + co, such that for almost every O, and any E [n]] we have
V (. - fn,, (0,) - r(l = r(p:).
Lemma C.25 (Characterization of B(t)). Under Assumptions 2 and 3, there exists ss > > 0 such that for almost every
12 > 4 2 85, we have
(B(1)+ +2(())) 11
1- Pi)(())
d
log p(T) dr
1
log 2 (0t2) (G
dr
M
where
2r(p:) pi (1) = MyGF (p))p
P2(1) (p)(
(0,(),) 1r
Proof of Lemma C.25. Recall that we have (19), that is.
dlog (O((O))
10 - (0 0,)
dt
(L (pt))
||1120p 02
( Pa (pr))
hl -2(h, 0,)
d llog Pt
dlog Pt
dpp 2p
By
do2 Laa di
/
dt
dt
Note that for almost every 2 s,
dpp
1
f(().) (V.())))
2 di
1=1
(..)) [M + P(([0]])]]
n
==1
By Assumption
n
(..))) (H. + (1 + p' ([()
n
By (0; - fH(0,; x S (10
(0.) ( Jn, (0,), 0.) 2MM
n
By Mp. 2 p(xx) for 00
(hr 02) + 2.
(48)
Similarly, we have
La, = L(((C) (p))
S L Le/ By Mpa (x) 2 pxx) for >
1 dp}
2M dt
By Lemma C.4
< M
(bg 0,) + (P))
(49)
34

---

Implicit Bias of Gradient Descent for Non-Homogenecou Deep Networks
The remaining part is to bound the term
||h]|² 0 in the numerator. Recall that
(0,) V (0.)l - r(1@ for all i E [n]]
Hence we have
|| hAll S
[h ha,il S Car(110.1))- [(0),)
We get
|h|| [Hll
||h hull 2 [haal -rr
Since ||0=1l + oc, for all sufficiently large 6, we have
(hH, 0.)
[h || 2
(50)
Pt M E J:(O.) (0.)
Tipt
M -i=1 e (-(.)))) (F.(O)) - (p)()))
by Proposition 5.1
npr
MLr log I nLe PPa(pt)
by Lemma C.2
(51)
Pt. MLL GF (0t)
By the definition o
2 ML,,
GF (0.))t M-1
by Theorem 3.2
(52)
2 3M ()(p))
Since the degree of r M
Therefore, there exists 85 > > 0 such that for almost every t 22 85, have
Iv
|h 1
+ (rr(11,11)2
IV
bhll Cir(p))
(53)
I
ball h3M ()r((( 20.
by (52)
Moreover, we have
dp
(h. 0,)
S (hH. 0.) + (PM)palp)/pp
by (49)
(54)
P: 2 dt
Combining (48), (49), (53) and (54), when 2 85, we have
2 2|| 2 2(h, 02)²
hH (1lhH/Car( - ((hH, 0.) + +MM Capa))(
M
L, di
dož
/pē
((HH θ.) pp))
1 2| hH (((r(pp) (3(1) 2M Ca (pnn))))
M
1- 1- (12 (0.)p--)
2
(B(1) + (px (7
1 (t()
(B(t) + +t)))) -1)
where
2r(p:)
Pe(t) = 2pa(Pt)
(t(t) = GF ) M-11
7F ,F((..))))
This completes the proof of Lemma C.25.
35

---

Implicit Bias of Gradient Descent for Non-Homogenecous Deep Networks
Corollary C.26 (3 bound). Under Assumptions I and 2, there exists 85 such that for almost every 12 2 85. there exists ta (21 satisfying
1 Pt.t)
1 M
log (f (0.,) - log 7 (0t.)
(3(t.) p2((t))
log Pt2 - log Pt,
Proof of Corollary C.26. Denote the RHS as C. Assume to the contrary that
1 (1p)(t.) 1> C
for all t, E (t1, t2).
(o((.) + pa(t.))
By Lemma C.25, we have
1 GF (00z) M
I" C-
22
d dr
7 GF (0i.) M GF (0..)
log
log p(T) dr = C(log Pt2 - log pt.) log
GF
which leads to contradiction. This completes the proof of Corollary C.26.
Lemma C.27 (9 converges to 1). Under Assumptions and and V f is near-(M - 1) - homoogeneous, there exists a sequence tg such that lim 31g + 1.
Proof of Lemma C.27. By Corollary C.26, there exists 85 > s >> 0 such that for almost every t2 > t1 2 85, there exists t. E (11,4) satisfying
p1 (t.)
3(t-) 2
Ing 7 GF (0x,) log GF (0.,) P2(t=).
log Ptv log Pt.
We know that as t. co, Pi (t.). there exists t2 to 85 such that
O. Besides, we know that log P. - and log (F(,) %o. For any Cms
pi(l.) S cm f log(p(12) log(p(41))
M lllog (F(z)) 7 (0.,) S em/ and p2 em/
Hence we have
1 mm/2
3(t.)
V 1
cm/ 2 6m
Cm/
Hence, for each we can find a corresponding tm such that 3(tm) 2 1- Em This completes the proof of Lemma C.27.
It's worthy noting that Lemma C.27 shows that subsequence of (h,(),), 0,) aligns, which matches the result in Lyu & Li (2020). However, & Telgarsky (2020) showed that (h.( 02) aligns assuming that f is homogeneous. We leave investigating gradient alignment for near-homogeneous functions as future direction.
Lemma C.28 (approximate KKT point). Under Assumptions and and V is (M - 1) near-homogenene there exists a sequence tę such that 0, is an (ER, -KKT point of (P) for all k N, where + 0 and 6 + 0 as k - oc.
Proof of Lemma C.28. We just apply Lemma C.23, Lemma C.24, and Lemma C.27. This completes the proof of Lemma C.28.
Now we can prove the main theorem.
C.9. Proof of Theorem 3.5
Proof of Theorem 3.5. Appplying Lemma C.28, we have a sequence {tx} such that 0,, is an (ck. KKT point of (P) for all k E N, where EN + and 6₂ + 0 as k + co. Since 0, and share the same direction, 0,, will converge to the same direction as one of the KKT points of (P). By Theorem 3.4, we know 0,, also converges to the limit 0.. Hence, 0./ (..))(
1/M KKT point of (P). This completes the proof of Theorem 3.5.
36

---

Implicit Bias of Gradient Descent for Non-Hoomogencous Deep Networks
D. Proofs for Section 4
The proofs in this section are divided into two parts. In the first part, we provide some basic results about near- near-homogeneous block functions. In the second part, we verify that many commonly used neural network architectures are near-homogeneous block functions.
D.1. Near- Hoa--eoongessuus Networks
The first thing we want to show in this section is that if we want verify a model (block map) near-homogeneous (dual-homogeneouus) we only need to verify the first two conditions. This is because the frist condition will imply the the last condition.
Lemma D.1 (M-near homogeneity bound), Given a locally funccinn s(0), M E E+ and pa(x) [+ with deg Ps = M, we assume that for all 0.
(V).0)) .M ((0]l (((0))
Then, there exists pt RR+ [x]] such that deg p M and
||s()] (10)).
We skip the proof here is almost the same the proof of Lemma C.8. Indeed, note that in the proof of Lemma C.8 only Assumption (A1). However, this lemma indicates that the near homogeneity will lead to the boundedness of the block function. In other words, we have
(A1) - (A3), (B1) (B3).
In detail, we have the following corollary.
Corollary D.2 (From near homogeneity to boundedness). Given model (0;x) satisfying (AI) and (A2) in Definition 1, then x(); satisfies (AI), (A2) and (A3) in Definition 1. Similarly, given a block function s(f:x) satisfying (BI) and (B2) in Definition 2, then it satisfies (B1), (B2) and (B3) in Definition 2.
Once we have this corollary, we must only verify the first two conditions in the dual homogeneity definition. The first result we want to verify is that horaehomogeeouus gradients lead to homogeeoggs functions.
Lemma D.3 (Near-homogenent) gradient leads to near-homogeneous function). Assume that f00;) is continuously differentiable and V f is locally Lipschitz and satisfies Assumption 3 with parameter M - for some M 2 2. Then, f is near-M M-hooogenooouuu.s
Proof. Since f is locally Lipschitz, 2 exists almost everywhere. Here, we focus on showing (A1) in Assumption since (A2) is straightforward. For simplicity, we omit the x the function. Note (A1) is to show there exists p s.t. deg p S M and
KV 0) - Mf) s p'([1]))
Here we assume there a p1 E R4, [x] such that deg P1 S 1 and
(V)),, 0) (M l) < (((O))
Since ff is a continuous function, we can assume for all E B(0, 1).
(V 0) - M (0)) s
For general 0, let == 0|||0|| and
((r) = (V)(r)), r0) Mf(rr).
We aim show that 19(r) - g(1)] bounded by some polynomial r. Note that
Ig (r) = _ (2) Vf(r)) MVf(r0) To
37

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
(M [V((( - -MM
s -M-
S pi()).
Hence, we have
g(r) S [o(1)) + (0(r) 9(1) s C+ J sp()
+ sp)))
Therefore, we can set p = f((p + CC). This verifies (A1). Hence, f is near-M-homogeneous. This completes the proof.
Now we can prove Lemma 4.2.
D.2. Proof of Proposition 4.2
Proof of Proposition 4.2. For this proposition, we will only present proofs for argument and 2. For argument 4 and 5, they are direct consequences of argument and 2.
Argument 1 for s(O, x) sg. s (x).
By Corollary A.5, we know the existence of the Clarke Jacobian of 5² (0,; s2 (02; x)), since it's locally Lipschitz. Right now, for s(0; (0; x) s² s0 (02: x)), we want to verify (B1) and (B2). Since they are some convex constraints, we only need verify the constraints at the boundary.
To prove this, need invoke Corollary A.9. Recall that the statement in Corollary A.9 is:
Given two locally Lipschitz block functions s¹ (01;x) Rd Rd + Rs and (02; Rd x Rd R&, have
00s (02; C conv (a11, 02 h1): (a), 02) 0g xs (01;x), h1 E 0Ø s2 (02;x))
0xs (02; x)) C conv Q2 h2 ag E dgs (01; x), h2 E (02;
This indicates if suffices to verify (B1) and (B2) for all combinations of (a11. a2 h1, h2), where (a11, az)) E do (01;x) and (h,, h2) E 20 x).
Recall that we already know (ar1, 02 h1, h2) satisfy the following conditions:
KK 0 - Mi s0; x) S Pb: ((00))r,=(IIII)
[K x) M2 s (0:x)] S p. ([00))),,(((())))
||ai]| < d. (( ([xx]))
||a2|| I 9. ((0]))t
||s (0:x) S 9. ((xx))
For s2, we have
[b, 0) M3 5² (0:x)) I ((=((100)) [r ([|x|),
[bg, x) M4 5² (0,x)] S p.a ()=( ([x[))
[hi]] ([1(((])))=>>
[/2/| 9.= (1])))))))))
2 (0:x)] _ ((=(())))
38

---

Implicit Bias of Gradient Descent for Non-oonmogsssous Deep Networks
Then, will verify the conditions (B1) and (B2). Verify (B1) in Definition 2. As for (B1), we have
(0x1 01) (ox2 h1, 02)
= (011 O1) + (022, Mase, (x)) + (a2,, 02) - M390
Therefore,
sup 81 (0000()))
(8), 0) - (M1 + M2,M3)s(0:x)1l
sup (he [| 01) M1=(0;x)] Mallo, M2s(0;x)]
+ (1 (h1, 02) - M3se (x))
$ p/ (1001))rr (x) + Map. (1 (1 (x)ll) p.d (1011))r (xb]
S P/ (1]01l)) .r. oq.- [2]l) .r, or, + Map. ( (|0]1) (ipl)))- -r 09.- 1) r.- (1|x])
+ p.. (1) (12
o q.-
([xx)
< (1 q. (21]
01) r (1=1))))))p
order MM
x Tr txe + Mar o t. (||x|]) + tr, o (1xx( rga (1|x
SM
We can prove something similar for (g..x) (0:M,sO:xx), where g2 xx) Then the orders for (g2.
M2M will be bound by (M1 + M2, M2M4 1). Combining them, there exist Ps. E R [xr] and deg S Mi + M2, degr, S M2M4 such that
sup Ri (0
(g O) (M1 + MgMMss < (((())
(| x) - (M2Ma)s((: x| S (110 ((
sup (0xx)
Verify (B2) in Definition 2.
Before we proceed, we have the following two inequalities:
t₂ (11+,, (x)]l) < t, (()]) s [ta o q.= ([(1)) [t, o t((((())))
t, (1 (x)l)) < t (q.a (121)) [t's o ([]1)] [t/ (x(((())))]]
Note that
sup
|g 1/ <
sup (an a2)s (hi haleas
||a|||2 + ||a2 h,
gi E00e
94,, (1|0, t, &1 (x) ((0O (11=3, (x)a)) [1,,()))a((Ix
By (B2) and Lemma D.1
< (4,, (1|0) II) tu. q,a O2ll) t. txxx((x)]]) 2
+ Iq (1|@)l) tt (I000) the x[]( ((0(11)) -ta(([)x))]]
By two inequalities above
39

---

Implicit Bias of Gradient Descent for Non-Hoomgenncous Deep Networks
9 (1)0: t (. 1) + 9. (1|0)l)) t. o ((0()))) q/a (1121)))
of order 5M1 Ma
t o t, ([xx]) th o ([ [[x
of order M.
Therefore, there exist qs. ts R_ [x] and deg 9, M1 M2M23 degt, M2M4 such that
|g 2 (((1))))
sup Edes
On the other hand,
sup Ed2s
g2 x
sup
||02 h2|
(z) E082
I 9.¹ ( (x) (102)))())()))))))))(())
- q, (|) f/2 o q.= fy2 o t,2 ([x([] q,a (1102ll) t/ (1xx
[q. (I]0 tt q.a (1122l) 9.- (1102]] x [t/ t, (|xx|) thas ([xx1)]
order <M1+
of order 2 <MaM4-1
Therefore, there exist qs, to E R. [x] and deg q, < M1 + M2 degt. S M2M4 such that
sup g Edea
|g Σ d(((
sup grEd.s
|g
< (=(()))))(((((()))
We have shown that satisfies (B1) and (B2) with parameter (M1 + M2 M2.4).. Since (B1) and (B2) lead to (B3), This indicates that s0;; x) is near-(M (M1 + M3, Jhoooo--omgeeeouus
Argument 2 for s( x) = sb, @ a (x). Without loss of generality, we can focus on just one entry of the output like:
[s(0, x),, = [sb, (x)]; [ (x)]]-
To simplify the notation, we can assume 5 s2 are both scalar functions. Then, by Lemma A.6, we have
a(s 5²) C conv conv(( (s s² h1 sa + s h2): (ar, 022) Os?, (h1, ds² J. We will also use (gi, g2) to denote the Jacobian of Then, we can verify (B1) and (B2).
Verify (B1) in Definition 2. As for g1 E Öøs, we have
sup (gi, 0) (M1 + M3)s||
gi E0
sup
|1(52a1. 01) + (sth1, 02) (M1 Ms)s|l
a1E0ss Ed
sup
||s || (1,, 01) - M1s' - sup hi s
||s [] 02) - M3ss
q.a q. It, (Ixx (1 (||x|)
qu (1 |t, (1|x (1 م- (1x|
q O1)p) t.= ((r ([xx|]) + q. (1 1)) (101)) t₂ (|(=
order (M++Ma-1 order 2(M2+
order MM
S Ma)
Similarly, we can get that
sup
(g2, x) - (M₂ + M1)s|
Ra Ed
40

---

Implicit Bias of Gradient Descent for Non-Hoomoesscous Deep Networks
sup 0g sd
as2 x) (s x2, (M1 + MM)asl
sup
||>2||
x)) -M + sup
||$ [b2. - M2s²1
azEd,s!
(10 (ppx (1101))rg ([|x + 9. (1l0
9.2 ( (100))pppppp (1)01) tga (||x () ([x+l) 9a (110 p (1111) f. (1|x ()
of order (M +Ma) of order (Ma M order S (M + Ma) order SMM M1
Combining these two inequalities, we can see that there exists 9ss r E R2 [a] such that deg q, S (M1 M3), degr, S (M2 + Ma), and
sup g (0,))
(g)) 0) (M + Ma)s(0;x) S ((((
[gg. x) (M2 + (2) - (() (1x[))
sup (0xx)
Verify (B2) in Definition 2.
As for gi, we have
sup RiEdgs
|gg 1 2
sup
||s² 12 + h1l1
edos ad
< -.a [[] (1)@)) [[ [[|x||)] + [q.. (100))t,a ( ([|x|))
q.= [1)((())))
([xx])) of order S MM)+
+ 9.. (110 @1
t.2 (txx
order S(M Ma-1) 1)
onder S (M + 1M
of order S.2 M44)
Similarly, we have
sup g
1|ga <
sup
|s2az + s
a 62
2 211s2azz/1 a221 + 211s h22l 1
sup
age0,s h. heE0, 2
< ((]])))) (10))) (1|=1)) + (q (I()))) qq qu ((10)) ((xx)) ([x[]])
(1=
1 9. (1
(Ix ([x[]) ]
order Ms) order MoM2+
order S(M++Mss order S Mo-1)
Therefore, there exist 9,, to R_ [x] and deg q, S Mi + M2,M3, degt. S M2M4 such that
sup
||: S d[((1))))
81 Eda
||aa I q.((101)){
sup R2C02
We have shown that s satisfies (B1) and (B2) with parameter (M₁ + M3, M2 + M4). Since (B1) and (B2) lead to (B3), this leads to that s(0; x) is near-(M, + M3, M2 + M4)-hhomogeneous.
This completes the proof of Lemma 4.2.
D.3. Proof of Corollary 4.3
Proof of Corollary 4.3. This is a direct consequence of Lemma 4.2 and induction on the number of layers. To prove this, we need stronger result. For
f(0: x) = =t, o 2
sg. (x);

---

Implicit Bias of Gradient Descent for Non-Homogensoou Deep Networks
it's
Σ
M2
dual-homogeneous. When L. 1, the result trivial. We assume holds for L layers. Then we have f4-1(0: oz- (x) is dual-homogeneous with parameters
$b 00 88 1-1
Σ
M
Then we apply Lemma 4.2 to f(0:x) = 10:
sgg (x), we have f is hual-homogeneous with parameters
I-11
Σ
Mi
Mf II
M2
II
M3
Σ
M2
M2
1=1
i=1
This completes the proof of Corollary 4.3.
D.4. Dual-Homogeneou Examples
In this subsection, we will try to provide some examples of dual-homogeeeous blocks. The frist example we want to verify the linear layers in neural networks.
Example D.4 (Linear transform). Let the linear transform block function s00; Ax + b. Then, 8 is near-homogeneous of parameter (1, 1). We assume that x E RR,,, A E xds and b E TRd
Proof. Note that
V A3 Ldaxds Xx, VB Ldaxds:
Vxs= A.
Therefore, we have
V s (oos, 0) ==
Furthermore, if we define the norm on A as the ||vec(A)]]2 then we have
Vesll2 V /d2l|x|l2 + Vd,, || & ||A||2
Then we can choose
p(x) = x
r(x)
q(x) = I
t(x) vdzx + Vdi.
Therefore, satisfics (B1), (B2) and (B3) in Definition with parameter (1, 1).
The second kind of block functions is the activation functions o(x). Note that the activation function doesn't 't have parameter 0. Therefore, we can reduce the dual homogeneity assumptions (B1), (B2) and (B3) to:
Definition 9 (Near- hooooeoomogessuus activation function). M-homogeneous activation assumptions. Given a definable and
locally Lipschitz activation function (xx), we assume that there exists M E 24 and p. E IR,, [x] with deg r, deg t S M, such that for all x E (x) and all E 0x(x):
(CI) M-Near homogeneity.
[h. - Mx(x)) (([[x]))
(C2) M-bounded gradient.
|h| s(([|())
42

---

Implicit Bias of Gradient Descent for Non-Hoomgenncous Deep Networks
(C3) M-bounded value.
[x(()]] S t[[[x|))
In this case, we say that ((x) satisfies (CI), (C2) and (C3) with parameter M.
direct property of this definition that:
Corollary D.5 (Near-homo activation as dual homo block). Given a near-homogeneous activation function o(x) with parameter M, then it's dual homogeneous with parameters (0,M)
We can easily verify the following results:
Example D.6 (Activation functions). The following activation functions are near-homogenneons uctivations with parameter 1: ReLU, Leaky ReLU, Softplus, Huberized ReLU, Swish, GELU, SiLU.
Another important property of the activation function is that:
Lemma D.7 (Power of activation functions). Given an activation function s of parameter (0, M). sh is of parameter (0, kM).
Proof. Similar Lemma D.I, we can show that (CI) implies (C3). Therefore, it suffices to prove (CI) and (C2) for s with M replaced by k.M. By the definition of Clarke subdifferential, we have
(x) (s*-1 aa:a ds(x))
By direct calculation, obtain for any h (x),
(1, x) - kMs* (x)]l = |k:s 1k:sk11 (x) V sx()) x) Ms(x)ll
k t ([] ([|x
of arder S(h 1))
which implies (CI). For (C2), note that
|h| = kks (x)) ||l|| S ktt (1xx()) (1)x)
of order (1
completing the proof.
With this lemma, can understand the near homogeneity of the polynomial activation functions. Then have the following result for a layer of the neural network, i.e.,
s s0:x) = +(Ax+b).
Corollary D.8 (Near homogeneity layer). Given layer of the neural network s0;:x) = d(AAx + b), where & is near-homogeneous activation with parameter M, then s is dual-homogeneous with parameter ()).
Proof. Apply Lemma 4.2 to sqj (x) =(x) and 2 (x) = Ax b.
With all the tools we build here, we can now understand the near homogeneity of many commonly used network architectures.
D.5. Proof of Example 4.1
Proof of Example 4.1. There multiple arguments in this example. We will prove them one by one.
Argument This is the result of Example D.4.
Argument This is the result of Corollary D.8.
43

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
Argument Max pooling layer, convolution layer, layer, average layer 1-homogeneous operations. Hence, they
dual-homogeneouu with parameter (0, 1). For the residual connection, we just keep the input as the output. Therefore, it's dual-homogeneous with parameter (0, 1).
Argument 4. Recall that the SwiGLU is defined as:
SwiGLU(2, W,, V,b. (wi + b) (zV + c),
where is one hyperparameter and W, V,b, e are trainable. We homogencous functions. In terms of Corollary D.8, S + 6) is dual- dual-homogeneous with parameter (1, (rV +c) is also hual-homogeneone with parameter (1, 1). Then by Lemma 4.2, we have SwiGLU is dual-homogeneous with parameter (2, 2).
that SwiGLU is tensor product of two
Argument 5. The self-linean attention (Zhang al., 2024) is defined
1(0: H) H WPTH H H WWOH
P
where H is the input token matrix and 0 (WPV WKQ). We can observe the dominating term in the linear attention layer is WPV w Therefore, the self-linear attention layer is hual-homogeneous with parameter (2, 3).
The ReLU attention (Wortsman et al., 2023) is defined as:
H W
s(0: H. H wwwwwp ReLU
VdL
where H is the input token matrix, L is the contextual length, and 0 (WP, WV, w wo). The dominating term here
is
H W
w H ReLU
VdL
which is (4, 3) dhaal-homogeneous. Hence, the ReL.U attention layer is dual-homogeneous with parameter (4,3). This completes the proof of Example 4.1.
D.6. Proof of Example 4.4
Proof of Example 4.4, We will prove the following arguments one by one.
Argument
This is direct result Corollary 4.3 and Example 4. 1. Now we have
f(0:x) sb, o 0sg (x).
and
(Mj, M2) = (1,
Wi E [T.].
Hence, by Corollary 4.3, we have f(0;x) x) is near-homope sea-hhomggencuss with parameter
L
M = Σ M
M = L.
1=1
Argument 2.
For this case, we have
(M,, M3) (1,1),
Vi E (T..
44

---

Implicit Bias of Gradient Descent for Non-Hoomoesseous Deep Networks
Hence, by Corollary 4.3, we have f(0;x) x) is near-homogeneous with parameter
kb
-
M
M
M
k
-=1
j=1
Argument 3.
For VGG networks, all the layers are average pooling, max pooling, and convolutional layers followed by a ReLU activation. Since convolutional layers are -i--duul-homogeeeuu and ReLU activation is (0,1)- dull-duu--ooooeeeuuuu we can apply Corollary 4.3 to VGG networks and get VGG-i is near-homogeneous with parameter i.
Argument
For ResNet and DenseNet without batch normalization, all the layers are average pooling, max pooling, convolutional layers followed by a ReLU, and residual connections. By argument C in Lemma 4.2, residual connections won't influence the homogeneous degree of the network. Since convolutional layers are (1, hoooogooolooooeeeouuu and ReLU activation (o.l)-dual-homogeneee homogeneous, we can apply Corollary 4.3 to ResNet and DenseNet and get ResNet-L and DenseNet-L near-homogeneous with parameter T..
E. Proofs for Section 5
The proofs in this section also has two parts. In Part I, we introduce the homogeneization of models and show the existence of parmeter which satisfies the initial condition. In Part II, we focus on toy example and show that initial condition can be reached in the GF.
E.1. Homogenization
For those Homogenization results, the most important idea is to analysis:
f(00:x) y.M
g(r)
Since f is locally Lipschitz and definable, we know that is also locally Lipschitz and definable in any open subset of IR (0). Hence, is differentiable almost everywhere. Actually, the best thing is that is M--homogeneous.
E.2. Proof of Proposition 5.1
Proof of Proposition 5.1. By direct calculation, we get (see also the proof of Lemma C.8) that for a.e. r > 0:
g'(r) M (0, (of(r(;x)) Mr
(ro, Vof(rO: x)) Mr(r0;x)
22M
which leads the following estimate
0((r M+1
M-1
(r(())
Σ (i + 1)r 1)r- (1+
where the equality follows that p(x) = EM aax. This further implies that for any < rı < r2:
19(r)) - 9((2)) < ["1o (r)( &
M-1
a++1 (i + 1) -MM 01 < Pa 0
Σ
M -
Note that dog Pa = M 1, and this leads to Pa (ri))00)/MM + as ri + oc. As a consequence, for any sequence {rx} such that F& + +oo as & + co, {g(rx)} } is Cauchy sequence. Therefore, lim, (() exists, and (H(0x)) x) is well-defined. From its definition, easily seen that [n(0; x) is --homogeneouss
45

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
We next show that x) is continuous and a.e. differentiable in 0 for fixed To this end, it suffices show that [H(O; (00;x))less-- is Lipschitz continuous. For any 0 and 01, 02 E S we have the following estimate:
f(r01xx) PM
x(r02;x) y.
1 rM [f(r01xx) f(r02;x)
(()) TM
||00 - r021l S CM.p 110 101l:2l1.
where (i) follows from Assumption (A2) in Definition 1, and CM.p is constant depending on M and p. Taking + 00 yields
[ fn( & CM.. ||0 02ll
i... fH(0;x) is locally Lipschitz continuous. The error bound follows directly from our previous calculation:
[s(0; x) - -H(0 x)] = (g(1) - x(+x)) S Pa (I
At last, we show that if f is differentiable and V satisfies Assumption 3, fH is differentiable. This is equivalent to showing that the following limit exists for any and E [d]:
fH(O x);; - fH(0:x)
lim t00
For simplicity, we omit the x in the function. Note that
lim fu(O + te,) - fH((0)
f(rn0 + rates) - f(rn0)
lim lim 20
r.M
due to the definition fH. We
(n(1) [r + +rllee) S(r,0)
J+(1)= SH(O + (ey)) SH(0)
t
And we want to invoke Lemma G.5 to finish this. To invoke Lemma G.5, we need to verify two conditions.
Condition 1: There exists an open interval (-a, a) such that (f) converges uniformly to fn(t).
Condition 2: Dor any fixed n, as > 0, (1) converges to (r
Once these two conditions are verified, we can exchange the limit and get
[V)b(r))) lim lim (n) lim lim [a( lim fn(1). t-50
lim -
M M-1
t00 t000 n-
By Assumption 3, this will lead to:
lH(O te,) - SH(0) (O)
(V))), = lim [H())) = lim
t-+
t
This indicates that (fH) exists and is equal to (Vf)H. Now we focus on verifying the two conditions.
Verify condition 1. Here fix some 0 (0) and pick some special such that
arg max jE[-
||0 + Leyll S P.,
arg min (E(-a.o).jE(d
| + Leyll 2 E.
for some Fr,T, > 0. Then we will show that for any t E [a. ft) converges uniformly to
(V/H(( + te,)) te,) ds.
46

---

Implicit Bias of Gradient Descent for Non-Homogenncous Deep Networks
The first thing to do is show this intergral is well-defined. Note that V is measurable. Hence, the limit (VSH is also measurable. Furthermore, have |V s (3: where degq S M. We must have
Vf(r0)
(((r11011)
(0) = lim y-00 M- S lim
r-000 - < C
Since arg max, 0 + 8 -eyll is bounded, the integral is well-defined.
Now, we will show the uniform convergence. By Assumption 3, we know for any e:
((z) M- 0 - 3M, i 2 M, M,r(x) S (F.)M-I x M-1
lim
Furthermore, since In - 0o, there exists an M' such that for any n > M
In 2 M/r. = arg
rnl leyll 2 rnt. 2 M.
je[-a.o).E|d]
Therefore, for any t E [-a, a) and n > M'.
Fa(t) / ((V)) + s- s-tg) tey) ds
[(nO [1nn+ (rlle) ((,,,) 1 (VVS)+(++ s. teg), stt)) ds
tt
(V + rale)) rnle)) do ((VS)(() + s. le,) ds
ff(r 0 + s- rnt,,, (V (V)))(( + 8 s-tte,, es ds
M
Tn
[s(nn + 8. rnles) - (VS)H(T (. .ej ds
([Ira + +.S.re sstntt,ll)
M-1
||, 0 + s. rnt M-1
E
ds
00 (F. M-
rn M-1
By arg min On + teil 2 M
16 [c(-
(F.) M-1 10 2...teell M-1 Ml ds
M-1 M-1 =6.
At last, since we already know that fa (t) pointwise converges to ft)(t) and fi(t) uniformly converges to So (VV) + s x tez), tez) ds, we must have (t) uniformly converges to (t) and
fn(t)= 1. ((V s s-t,),, te,) ds.
Verify condition 2. Recall that is differentiable. Hence, for any fixed n, as + 0, we have
f(r,0 + +rtte,) (r,
lim (t) lim +
M - (r),))),))..
1-0
M
(rnt)
Therefore, fH is continuously differentiable on Rd/(0). Note that this further shows that V(fH) = (Vf)..
This completes the proof of Proposition 5.1.
47

---

Implicit Bias of Gradient Descent for Non-Hoomoesssous Deep Networks
E.3. Proof of Proposition 5.3
Proof of Proposition 5.3. This proof mainly has two parts.
Part I: We show that
f(r10:12x) Mi M2 ri
lim 71,22-000
12
is well-defined, continuous, almost everywhere differentiable and (2), homogeenoss.
Part II: We show that
[n(0: =sh. *HH
s4.0, (x).
(55)
Part I. Similar to the proof of Proposition 5.1, we define for fixed 0 and
8(11,12) = 8(110, M, r2
By Assumption (B1), obtain the following estimates the partial derivatives of g:
Pr((1 (r((r||00)) (r2(|x)))
0,19(1,,22)
M1s(11;77xx I Vos((10:
1 11 Ma 12
ri 1
Pa(ri (0)r)(1))rr// [|x[]
0rgg(r,, r/tl 12 M V
M25(110r22)111
M1 M
2
As consequence, for r3 > ri and r4 > T2, we have
r4) (2) - lg(r,, ra)
g(r3,,2))+ 19(1, g(11,12) r2))
Or(ral(01))
(r|
dr (a(r2||x|])
(r(((011))
dr
M2+1
M1+
3
12
[x([|
M dr + ra(r2||x[)
PL (0
dr.
Ma
M
where (i) follows from the fact that the coefficients of ps (resp. r₂) are all non-negative, so r + P. (r(())) (resp. + (01)//000//// is non-increasing. Further, we can check that the right hand side goes to 0 as 11.72 co. Using deduce that sH (f:x) lim, r2), exists, and is M1- -ommoooogen in 0 and Mg-homogeneous in This completes the proof of well-definedness. The proof of local Lipschitz is completely the same as that in the proof of Proposition 5.1.
similar argument as in the proof of Proposition 5.1,
Part II We prove via induction on L. For L (55) holds automatically since f(0;x) s'(0 and 0 00, Now
assume the conclusion holds for L - 1, then we can write
[(0:x) s000 (0'-1
where 04-1- (02.... ,0,), and
f (0 = 60
sg (x).
Therefore,
f(r r2x)
s fl-10 00-1:-111 r22x)
fn(0;x) = lim
lim
11 Mi r2
Define M = E/ M II-11 2 M and M22 = II M By our induction assumption.
8b (r - =r - Ny
( + o(1))
48

---

Implicit Bias of Gradient Descent for Non-Hoomogencous Deep Networks
Mi M2 22 (sH.0, o ................................ (x)+
Use a similar estimate as in the proof of Proposition 5.1, we obtain that
st (ri00: (1100 st (r,0
Mi M1 (00-1100-11)0)) :x)
12
( I C(p, q, 0, x)r Mi (rAfi 12 -
Mi p mi
(ii)
ol N6 r22)) r2 A
where (2) follows from Assumption (B2), and the constant C(p, 8, x) might depend on the polynomials (a,.ra) associated
r.)
with se, and (0, x), but not 11 and r2, and in (ii) we use the identity M1 M1 + M2 M2 = M2M2. This implies that
S7 (ri01i7)
Mi Mr f4 (0--)))))
fH(0:x)-
lim 71,22-000
r 1/
(ri01i7
Mi, M2
r2
lim
10:
11
Mf (r1
12
M1 )
= =sy (10-1(0"),xx)) xx)
-HH, sH. o.. 5H,00 (x):
completing the proof of Proposition 5.3.
E.4. Proof of Proposition 5.2
Proof of Proposition 5.2. First, we let
7 arg min fH('(('; O. sE|n|
If replace O with cf', then have
arg min sn(f'' 70 xE(n]
Therefore,
arg min y. f.f('''; xx) 2 arg min y: f:fn(c0': (c(((()))) -0 (c((0')))) ie(n]
ve(n]
Hence,
[(cl') S exp(-7c" M + (c)(
To satisfy the initial condition in Assumption 2, need to find e such that
-y + (cc(00() < (cl(ell)l) logn + ga (c((e( + logn.
Since de S . --1, we can find such that the above inequality holds. Similar argument can be applied to the case in Assumption 5. This completes the proof Proposition 5.2.
E.5. Two-Layer Example
The following subsections are devoted to the proof of the two-layer example in Section We first show that the GD dynamics symmetric and the limit solution of the GD dynamics is the solution to the ODE (56). Then, we show that the loss is of rate (1/tt) and the parameter norm ||e,]] || is of rate O))oot)). Combining these two rates, we have
((O.)
= 2(Vlog t) - 20.
|0
The first thing we are going to show here is that due to symmetry, the limit of GD can be reduced to a GF with the following dynamics.
49

---

Implicit Bias of Gradient Descent for Non-Homogenscous Deep Networks
Lemma E.1 (Symmetry of the parameters). We assume the dataset satisfies Assumption 4, and the model is (11) with initial
condition W1,0 W2,0 0 and 61,0 02.0 O. Then, W1,t W2.t Wt and 61,t 022t at is solution to the
gradient flow dynamics (GF), where and de satifies the following ODE:
W = 1. n
-i= e v...(0))))) (1 + cca)yxX;
(56)
de Ei= (1,,xx) W::
initialized at (Wo, an) = (0,0) 0), with en = (1 + a2) Furthermore, (We, az) is the limit of the GD dynamics (GD) with respect to (11), as the step size goes to O:
(w,, ar) lim (Wye autt)
7-
Proof of Lemma E.I. Step 1. We show that the GD dynamics (GD) is symmetric.
We can prove this by induction. We use the following notation for GD: 0g = (a1,1, 02,t, W1,1, W2,1). For = 0, we have W1.0 = W2,0 = and 01,0 02.0 = 0. Assume that W1,r = W2, and 01,t 02, for some t. Under these induction assumptions,
(0,;), = T. + 2, + (P - 1102, (0_,,,
=2y, + 9: ,1))
Since ppx) ((-=)= =11 (1++0 at)
1itn/22 X
By assumption
i ,,...,,/............. n/2. Then, we have
V Ww. (():) =
wiiil0i11 + cLaLep (w],x:)))us
1=1
-f(0044//2) (1 (-an
By the symmetry of the dataset and the paremeter
W2 (().).
Therefore, we have W1,441 W2,4+1 for l. Similarly, we can show that d1,r41 = 02 for 4.
Step 2. We show that the limit solution of the GD dynamics is the solution to (56).
Since the GD dynamics is symmetric, we can treat (a1,,, wi.r) the result of Euler method with time step the ODE (56). Since the ODE is locally Lipschitz continuous, there exists a unique solution (a,, w.) to the ODE (56), and the limit of results of Euler method as goes to zero is the solution. At last, it's easy to verify that (a,, ae W., w.) satifies the (GF) for the model in (11) with respect to the zero initialization.
This completes the proof of Lemma F.I.
E.6. Loss Convergence
Therefore, we can focus on the ODE (56). We will show that the loss is of rate O(1/t) and the parameter norm ||O,]| is of rate ( /log 1). The main trick we use here the balancing of the parameters.
Lemma E.2 (Parameter balancing). Consider the dynamic of the parameters in (56) with initialization wo Ô and og 0. Then we have
1 1 = | oz a1 +
(57)
CL
Proof. Note that
d
1 1)²
2
1
+ )
=
2ht
+
dt
CL
50

---

Implicit Bias of Gradient Descent for Non-Hoomoeencous Deep Networks
M. yix, w, (2c,,, + +2)
n
d
2(We, Wx) [ 1wrrl2
Therefore, have
2 ||w,| == ao
- ) -l|woll
1
Gt -
6T.
CT.
C7.
This completes the proof of Lemma E.2.
Then, we can show that de for all I. Lemma E.3 (Positiveness of at). Consider the dynamic of the parameters in (56) with initialization wo Ô and do 0. We have ag for all t.
Proof. Note that
1 2 at + -
2
W. -
a. S
a 20.
CL
if there exits T such that de -2/eL. Due the continuity of at and ag 0, there exists < T" T, such that a(T') -1/eL- Then, it contradicts with the condition that de -2/c1 a 0. This completes the proof of Lemma E.3.
Now can already write a, as function of wt, i.c.
1 0t /|w/l12+
1
of,
CL
We will show that the the loss is of rate O(1tt).
Lemma E.4 (Loss upper bound). Given the dataset satisfying Assumption and the model in (11) with initial condition W1,0 W2,0 = 0 and 01.0 0220 O. Then must have
1 log" 2 (T)/4-2
[(0r)= -
T
Proof. Let w = =,w..
Note that
d
|w
w 2(Wr, W. -w)
dl
2
91((0i) (1 c (we w
2
[(()()))))) 1 [u]((0xx)) (1 + cLa) W.
By f(0:)) = (2+ + 22 Tx
(((iii)
(1,((0;:)) - 2(1 31.a),yxx7 W.
1
():((0:x,) 2.8%)
by y/x7 w. 27. and a 2 0
1
v.((0xx))) (2 (0:((xx,))
i=1
29T.
L(O)).
By convexity of -
51

---

Implicit Bias of Gradient Descent for Non-Hoomogencous Deep Networks
This implies that
WWT w0|l //" ((0.) T + w| w=ll
Note that [(),) is decreasing, Wo 0 and we can set log (T)/(2²)) We have
TL(0,) - (T)
This completes the proof of Lemma E.4.
E.7. Parameter Norm Bounds
Now we can use the loss bound to achieve bound for the parameter norm.
Lemma E.5 (Parameter norm bound). Under the same assumptions of Lemma E.4, when
2 max(16, (4/7, log(4/7=))))
we have
log
l/ [w.|12c2 +1
(58)
Proof. Applying the balancing equation (57), have
1 (0eex.)
n2
((O,)
n
1
x.x 21w.1c/
71
2 2/|
[|w
12c
By ||x S 1.
Combining this with the Loss upper bound in Lemma E.4, we have
2/|welly //.l 20 + 1 >> - -log(C(0.))
log* 4
log(t) log 1
(59)
Since t max (4/7, log(4/7))))), we have 5 log² 1/473. Therefore, we have
log²
2 log" 2
< logg + 2og (log / 2%
log
1
log
4
4
< log + 2 log(t+)
By Lemma G.4
= log +
logt < logt.
By t 2 16
2
Plugging in this into (59), we have
log 1. S 2 2//w//
|2 + +15
(|/w,
2 + 1).
C7
At last, we use that c₁ > 1/2 and we have
1
/w + +12 logt t.
16
This completes the proof of Lemma E.5.
Now we turn back to the analysis of the loss and try to extract the upper bound of the norm. Now we use to to denote max max (4/y, log(4/7))))
52

---

Implicit Bias of Gradient Descent for Non- Non-Honmgessous Deep Networks
Lemma E.6 (Parameter norm upper bound).
Under the same
assumptions of Lemma E.4, let to
max (4/7, lo))4/ Then we have
|well2 1 (14 +1 Vlogt + l/wlll2 v 2 to.
(60)
Proof. Just like the proof of Lemma E.4, we let w Bw.. Note that
d
W. w011 = 2((w,) w. w.-w", w")
dl
2
0 (1 + cLa)yxx (wr -wo)
(..x)))
[u. (1 Byx, w.
By f(0;x) = (2 + 2cra) w Tx
Σ x0(x))) x,,(00x,) - 2 /wollle2 +1y11x W.
By (57)
(v.f(0xx)) 1 Voo log 1,77)
By (58)
11
S6 Bo. (()))
By convexity of e
We integral the above inequality from to to t and we have
|WT w/ < ||wro - - + / e -Brrvllog//2
Here we set B = 2/oog T //5, then we have
WT - woll - |/ - w +
-voo log
e
to
I
1
W ww9l2 +
dl
By log T Tog 1 2 log²
to
Ww - w011 + log T.
Hence,
wwlll < || WT w/ll + ||w*|
Wto w + vlog T ||
Weoll + 2//ww + / IlgTT
4
Weall 1 + VlogT + VlogT.
%
This completes the proof of Lemma E.6.
Now can give theorem about the margin.
E.8. Proof Theorem 5.4
Proof of Theorem 5.4. By Lemma E.4 and Lemma E.6, we have
logt t - log
1 +
lag²1 472
log 1/)
CO, as -
|00:12
| |l + (1 4/%, Vlgg
Therefore, there exists 7 such that the initial bound achieved. Now we complete the proof of Theorem 5.4.
53

---

Implicit Bias of Gradient Descent for Non-Hoomogencous Deep Networks
F. Proofs for Section 6
In this section, we will provide the proofs omitted in Section Recall the gradient descent dynamics:
0 02 - -))(())) for t 2 0.
(61)
In order analyze the convergence of the GD, need focus the modified loss. We define
((,)) == ( [(O.);
(62)
where we recall the definition of p. from Eq. (12). Note that we assume deg((a)) 2 1 if M 2 2. For notational simplicity, we denote
== ((,.), VL,- = VeL(O,),
G. = ((,), vg. = Vog(0,)
We recall the definitions of the link functions
((x)= = log
(xx) = log (xx) d(x)
(63)
and the modified margin:
((g(0))
GD 0))
(64)
1
We also recall GF, the modified margin defined for gradient flow:
((((
GF
(0)
log nC(O) - Pa (101))
(65)
10 |
Finally, unless otherwise stated, the constants B and B,'s 's in this section only depend on (M, p. A) and (r, in Assump- tions
and
F.I Preliminary Results
We collect below some important properties of Pa that will be used in this section.
Lemma F.1. For all M 2 1, the function Pa [0, +oo) + [0, +oo) increasing, and satisfies the followings:
(i) (x) p'(x) S Mp.(x).
(ii) M 2 2, there exists constant B₁, such that for all 2 0:
Pa(x) < B, (a +1). (z) s B (rl(z < 13 + xM 222 > 1}),
(66)
(x s B (11 13 + M-3 fx 1}))
(67)
Proof. The conclusion of part (i) for M 1 can be directly verified, since Pa(x) a1/(M - 1/2). From now
assume M 2 For part (i), recall that p(z) En azæ and
M
M ((+1)a.11
M of
x x 1,
(x(x)= =
M-1/2:
M-1 (0+1).11g)
202 r
2i=2
M
M-1
M-1/2'
x 05r<1.
Hence,
(x) + pp((x) MPp(x))
i(i + 1)a++1 It + +i+ 1)a4413
Maj+1 x²) +a
Møj
f x21
M -
M -
M - 1/2'
i(i + 1)a++1
Mai+1 M x²]
1' + (i 1)44111
M -i
050<1
20z 2 2azz
2Maz
x² +1
Maj
+
M 1 M
M 1/2
54

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
a1
I x21
M - 11/2"
(x 1)²
01
-202
0
<1
2
M 1/2'
01
S 0.
M 1/2
Part (ii) can be verified via direct calculation.
The next lemma characterizes the derivatives of functions related to 6(x).
Lemma F2 (Derivatives of functions related to ((x)). Given the function Φ(x) = log(1/(nz)), we have
1
(
1 (0(z))
and ( (o(2)))
2
(log ((x))( =Φ(x)²
o(x)xx'
o(x)xx'
Lemma F3 (Convexity of b). For x E (0, 1/ne?). (xx) is convex.
Proof. By direct calculation, we get
2
('(x)
+
d'(x),
((x))
and
2
v'(x) (x) =
+
(0(x) +
0'(x)²
(xx)
Φ(x)²
x(x)3
(
1
+
x2
(
(x)²
6(x)3
(10 1
1
xxr} )) 0,
2
((x)
(x))
xx))
where (i) follows from the fact that ("(x) = 1/0² = 0' (x) (ii) is due to ((x) > whenever x < 1/ne?. This completes the proof.
Lemma F4. For any 0 satisfying ((0) < 1/n, we have y (0) > (0).
Proof. Recall that
(0) exp()(G(0))) ||0||M
7 7F (0) o(G(0))
||0|
The result follows directly from the fact that < log when ng( 1.
We next give some a priori estimates on f and Pa- Lemma F,5 (Homogeneous constant). Under Assumption 5, there exists some constant B2, such that for any O:
| < By ([00)=+++)) |()]( < B2 (1 +1).
(68)
Lemma F.6 (Gradient and Hessian bound for L). Under Assumption 5, there exists some constant By:
VV( s (.( - [[V)( < B₂C(O) 210 + +1).
(69)
Proof. According to Lemma F.5, we obtain that
| = Σ - 1. (.(1)
< B2C(() M1 +1).
55

---

Implicit Bias of Gradient Descent for Non-Homogenccus Deep Networks
- [ = f: )
<C()) (10 1)² + B2(110)(MM)) + +1)
Using AM-GM inequality, the desired result follows immediately.
Lemma E.7 (Gradient and Hessian bound for g). Under Assumption 5, there exists constant B4 such that for any A:
[Q(( B,9(0)
(110) +1), || B49(0) (110)2 + +1).
(70)
Proof. We first upper bound [/( By Lemma E.5 and Lemma F.6, have
[Q((0)| pp. (110)) VV ((0) (101)) P. (101)))
S (Pa(1l))) [
< B2) (101| + Bi) (10))
$ Bi) (|01||-1+11 1),
where B, only depends on B3 and B1. For V note that
|(26(0)]
| PL (101)) V² + 2. (((11)))
+ (P.( ((()) (P" [1I) + (((0))))) 00 + ((e)((100))(0))pp(((( (1 (1- 00T) /|01|||
<eP.(101D) ||> + (1101 P'. (101)) [V]
+ ((0) (P)( P'. (1101))²) + 9()) -0000) (((0))
|0|
< Bag(0) (101 22 + 1) + 2B, B,9(() M10
+ 1) (10 +1)
+ G()) [B (M0 +1) + Bi (M (10
+1)²) + Bis(0) (101 +1)
Hence, there exists constant B, only depending B1 and B3, such that
||*)(())] < B49(0) [10 222 1).
(71)
This completes the proof.
We introduce a crucial quantity, in defined as the inner product of the gradient and the negative weight vector:
U1 == (V.(),) 0,).
(72)
We have the following bound for vr, recall that = =|O,1l-
Lemma ES (Bound of v.). Under Assumption for any O satisfying C(O,) < (1/n)e (1/n)e-Pa(nn) -u(o)), we have
MC.).) log L(0.) ((())) 2 v ML(0,) log nC(O.) - p'(a))((0.)) 0.
Proof. We first prove the first ">" Note that
4 -- 0,) Σ c -((0a) (V.. 0,)
Since - VL, = Σ -udil y v.((t
56

---

Implicit Bias of Gradient Descent for Non-Hoomoesscous Deep Networks
n
((01)) (..) +
By Assumption 1
T1
M (0,) f((0i) + (()))
n
i=1
(l, log ((,,) (()))
By Jensen's inequality
For the second "2", by Lemma C.2, we have
(a,),) 2 (0)) log 1
(73)
n.((,))
Furthermore,
1 n 71
8 Since VVC,
1/ = (-V((()) 0₂)
Σe
(.0).)
y (V.) 0.)
v.f(00 y f.(tt
M 1
f.(0.) f(),))
I.10.) -.10)) p' ((()
By Assumption 1
M (()))) f(())) ((0)))((p))
1
f((0,) log nC(O,)
((0.)p'(pt)
By Eq. (73)
ML())) log nC(O.)
((.)))
Note that since Pr 2 O, we have
C(0,) -aloo) /n + M log nL(O,)
(Pt)
By Lemma F.1, we have
MPp(z)-p'(o) - 2 xx) > O.
As consequence,
log n.C(O)) > MPa(pt) 2 p((p.) Vz 0.
This completes the proof of Lemma F.8.
F2. Margin Improvement: Proof of Theorem 6.1
This section is devoted to the proof of the margin improvement part of Theorem 6.1. We first establish the desired result under another set of assumptions in the following theorem, and then show that Assumption 5 implies this set of assumptions.
Theorem F.9. Let (0;x) be twice--diferentiable network (with respect to 0) satisfying Assumption 1 with (M, p, q). and that
v2f(0:x)]] s A (M +
for some constant A 0. Further, assume that
G.
C. < ne²
exp (ppa(ps)).
(74)
ne²
Recall By and Ba from Lemma F.6 and Lemma F.7, we define for 17, r > 0:
Bs(y.r) = (r- v/ Bze Pa(r) M1 + 1) 2M
+ 1,
57

---

Implicit Bias of Gradient Descent for Non-Homogenncou Deep Networks
for 2
(t) (pp 1)2, R=(t)= (.)=BBBB)n.))((((()))
Further, assume that
1 sup M...0.
1
sup P:2P..0.5.
Ri(t)
2'
R2(t)= - 2
For all 2 8, 1 E N, we interpolate between 0g and 0,+1 by defining
Ozta = 02 + a (0c+1 - = -.-annVC(())
for a E [0, 1]. Then, we have for all t 2 and a E [0, U/ > 0, and
(1) o (0cta) > (0++a)>>00() (0.)
(2) 2nov S Pita - P8 s 2nom (1 2M10103)
(3) Gi-a 11 S -am (1 an))((1) M9(0(9)) IV
(4) log T (OLta) - log bogg,GD/ (D) 2 Mp3 1
Pt-a log
PL
To prove Theorem F.9, we use a similar strategy as the proof of Lemma E.8 in (Lyu & Li, 2020). To this end, suffices to prove the following lemma (analogous to Lemma E.9 (Lyu Li, 2020)):
Lemma F10. Fix an integer T 2 s. Suppose that (1), (2), (3), (4) hold for any t + a < T. Then if (1) holds for (1,0) E (T} x [0, for some (0, 1), then all (1), (2), (3), (4) hold for (1, (T) x [0, A].
Proof. By our assumption, we know that G. S 9. < 1/ne² for all t < T, hence Lemma F.8 implics oy >> 0. Further, we have P: 2 Ps and (0.) 2 GF (0.) for all t S T.
Now we fix T. Since 7 GF (0.ta) 7 (0.) for all [0, A), by continuity of GF know that 7F 2 (0.) for a = A.
Proof of (2) for A. By definition, we have
[| Pita o: ===oa 0,) 17 IVVL
=2nav + a²² |V 2 2nao, 0,
where the last inequality is due Lemma F.8. According Lemma F.6, we have
|VC(0) S (()) By (1101) M- + 1).
namely
|GC|| S BgC. (p: MM + 1).
Further, applying Lemma F.8 leads
14 2 (L)
We finally obtain that
1+ n7.l1 V
Pi p 2mavv
2v:
+ 13 M 1)2
S 2navv
2M Le((Ge)
Cx M- 11M + 1)2
2nov
1 1
2M²(g.)
58

---

Implicit Bias of Gradient Descent for Non- Non-Hoomoesscous Deep Networks
21jar 1
naRl(1)
2Mx(G.)
where we denote
(1) = Bp M-1 +)2
This completes the proof of (2) for a = A.
Proof of (3) for a = A. Using Taylor expansion, we know that there exists e E (0, a)) such that
1
ac+a G. -6, (0t+a 0.) 2/ 10ta - 01) gige+e ( 0e)
(0.,
VVi)
a²11 +
و anpe (pc)
/2 + ma
gieell //
Pt
2
16 anpealon (m))
V2 + (0
21
n2
1V2 || ||
2
< G Pale))
VC, (p
L
a² a²12BB Ba
2 Getc(Pet 2M
|2,12
By Cauchy- Sehhhy-S and Lemma F.7
G. on [cpaled (:P'((:)pp - 0n Bageto 2M- + 1)04
|L,11
2
To estimate the right hand side of the above equation, we first note that
2M-2 Pi+c
+1 115 (p. + + v|V 2M +1 S (p: + +BBBLi (PM--1 + 1)) 2M-
+1
- (p: + BB Pa(p:) (pr M- (0t-1++1)
2M-22
+1
2N1-2
$ (p + Bge palp)) (pi M-1 + 1)
+ 1 = (s....t).
Next we show that Gete < Ge for all E (0, If this is true, then we get
Getc (p2tt-2 + +1) s G,Bs(n p.).
and consequently
Geta S G. an [opalo)o: - -Gpp) an B49, B.G.Ba(1).P)))
|V
0t
By Lemma F.8, we have
poo(P))
Pe (px) Bs (MC - C(())) GiP'(Pd)
(p)) Bs ML.)(E.) - (p) + (p.(p))
(ePO(N) Bs ML. - MG.Pa(P))
MGrd(G.) -M9 an 2
BaC, (s(n..))(()))
M.. MG. ad R2(l) 2 MG.d(G.) (1- (17)n
(4))
where in (1) we define
(2(() Ba (T
59

---

Implicit Bias of Gradient Descent for Non-Homogeneoos Deep Networks
and (ii) is because G. Gs 1/ne² implies (Gt) 2 It finally follows that
944 9 S -07 on))(() (e
Now it suffices to show that Site 9e for all (0, To this end, assume that 6 inf (0, 944e 2 91) exists.
Note that
dgi+e dc
(-7)CC)
l==0
-
V / + (pPd)p
S --mepaler /f / + naP''
S -((n//R))nMGiolGG <0,
which implies 6o > 0. Therefore, Gite < 9, for all E (0, 60), thus leading to
Geteo & 9: 607) (1 - Ro R2) (1)) (G
<
which contradicts Geteo 2 Gt. Hence, we must have Gi+c < Ge for all c E (0, o... This concludes the proof of (3).
Proof of (4) for a = A. We only need to show that (2) and (3) together imply (4). Note that
Gita - Gr I -an (1 - an M VVC.1.
Hence,
Gita - Ge
S -1
Multiplying +
ga (t) (M.) on both sides, we have
1 + (1)22M))
(Gtta 9t)
[1 (1)
$ naMe," | 1+ naR((() (t)
2Mx()))
(
< Mc,
P2)/2
(18) 1 (pita - pi:)
M
M 110 call3
+
2
20ō
where (1) follows from part (2), and (ii) is because we know that:
2² V 10 100 + 1.02..11.
Note that since Pe 2 Ps: our assumption implies that
1 anRi(t) S (Bi(() < z. anRe(t) S nB2((t) S
Therefore,
+ nauR (1)22 (n)
1 + (1022/M0()))
<
(1 ()(2(t))G.OGG)
1 + (Ri(t)/2M (f
G
60

---

Implicit Bias of Gradient Descent for Non- Non-oonmoesssous Deep Networks
(1+
+
G.)(G.)
Mő(Gi)
((G.)
2
(9)),
grO(G,)
g,0(9,)²
where we recall that
(x) = log ((x)
((xx)
By convexity of o get that
Mpilld.cll
((G+t)) - (p())) (log Ph+a - -lg
M
of
2 (9())) - 9c) (Pita - -pt)
1
M
M
1 Cell3
2
Pi
20/
This leads
log (ogg0((0(a)) -log) 6D (0.) ((9-a)) ((())
M Mlog Pi+a log
M |1 1e
Pr+o
log
completing the proof of (4).
Proof of (1) for A. By Lemma F.4 and (4), we have
7 GF (0++a) > GD (0 (0)),,
which proves (I) for a = A. This completes the proof of Theorem E.,
We next show that Assumption 5 verifies the conditions in Theorem F.9. Lemma F11. There exists a constant B that only depends on (M, p. 9, A) and (r,s) in Assumptions 3 and 5, such that for any step size 1j >
Gs < min
n By
implies
1 (1(1) S 2'
1 R2(1) S
sup &.S.
sup
D.Ss.
2
As a consequence, the conclusions of Theorem F.9 hold.
Proof. In this proof, we will use B to denote generic constant that depends on (M, p. r)s, while the meaning of B can change from line to line. We begin with estimating R1 (t). Since deg(p.) 2 when M 2 2, we know that there exists a constant such that
M-1 + < Bexp 1 (pa(r))
2 O.
Therefore, if P: Ps:gs S G., we have
(1) =
1)² B² exp(pa((.)) nBG, S nBC..
For estimating Ry(t), we first note that Vr 0:
2M-2
Bs(n.r)= (r+ BGe Pa(t) (1- +1)
+
< + 1/9, BBBe Pa(l)/22
2M-2
+1
61

---

Implicit Bias of Gradient Descent for Non-Hooogenncus Deep Networks
<22M-3 2M +1 2M BB2 2 - -2M 2)pu(T)/2) (22))22))p(() + 1
<B p2M-2 +
-1)
Second, since O. S Gs. we have
Le((Lr) = exp((Pa((A)) (0(9)) + Pa(pt)
(1
S cxp((Pa(pi))G.066 + P exp( cxp(pp(())p
(00)
1 I B Bex (-5pa(e)) g20(9.).
where (i) follows from the fact that + zΦ(x) increasing, and (ii) is because that there exists a constant B such that
Pa(p:) & (x)p(p(())/2)) and d(G.) 2 2. We thus obtain that
R2(1)= B4 p.) S B (0.M
22 2M 2 + +1) (i((Ce)
S exp
- Pa
(22 + ,2 222 8 -aler) + +1) gro(9,)
$ Bex
22M--202M-20 (.)().).
To further estimate this term, the following naive bound Gs:
Gx (pp(pa(ps) q(p)))
which further implies
log 9, I a(ps) B Bexp (pacor) s B exx (palor))
(G+) log
for some constant B, since the degree of q is at most M 1. In the above display, the last step is due to Pa S Pt. It finally follows that
R2(t) S Bngg, (22 +1).
Therefore, the requirements (1) $ 1/2 and Rt - 1/2 are satisfied as long as
19. 2M 2 -2 + 1) S 2B
which is equivalent
9 -
B
for some constant B only depending on (M, r,s. This completes the proof.
We have completed the proof of margin improvement. The proof of
GD (0.) < (0.) < (1 (1))
+ 0
is the same as the gradient flow case, so we omit it here for simplicity.
E33 Convergence Rates: Proof of Theorem 6.1
In this section, give refined bounds on the decrease rate of L, C(O,) and the increase rate of pr = ||O completing the proof of the convergence rates part of Theorem 6.1. In similar spirit to Lemma F.11, we can show that the conditions of the following Lemma F.12 are satisfied as long as
g, < min { n Bn
which holds under Assumption
62

---

Implicit Bias of Gradient Descent for Non-Homogenecou Deep Networks
Lemma F.12 (Decrease of the loss function). Under the same ussumptions Theorem F.,, and further assume that
(BaLs (0: + 2
1
sup P.20..0.0.
Then, we have for all t 2 8:
2-2/M
2-2/M
C2n (((())
S La -Cnnf ((fi))
(75)
where Ci C2 are some constants depending on ()D())), Par A and (M, P. q:r,s).
Proof. Using Taylor expansion, we get that for some E []:
172 VCJ L Lite VL..
L441 -
2
Note that by assumption,
172 VCJ
V Lote VL, - 7
V2 Lite ||,111
2
2
(
17
/2,l? BBLttt (pite-3 1)
|V
where (1) follows from Lemma F.6, and (ii) is due to our assumption. This implies that
5
3 - V2.
VL. < fe+1 L. S -
We now establish lower and upper bounds on VVC, On the one hand, we have
((G.)
1-1/M
|V < BaCe (0b
- +1) < C2Cipt C2Le
(FF().
((L+)
1-1/M
SC2c
&C2Lid(C.)--1/M
(DD(O.)
where C2 depends 7 (O,), Ps. and (M, 9. s). On the other hand,
Ut
MLr p'
By Lemma F.8
Pt
Pt
GF 1 (M(((C. - P((P)) (o(C,) - PM
By definition of GF
GF
-p'()))))p())))))))) (((())
2 2M/MM
By Lemma C.I
(MØ(C.) - P/
C(MOC))) -
1-1/M
MMIM, (F(M (0.) C. (O(C.)
By Eq. (21)
1-1/A4
-///M CO (D,)) 10. L, ((C.))
By monotonicity of of GF
== Cc =C (((.))
1-1/M
This completes the proof of (75).
63

---

Implicit Bias of Gradient Descent for Non-Hoomoeencous Deep Networks
We first show that L, converges zero and derive its convergence rate.
Lemma F.13 (Loss convergence for GD). Under the same assumptions Lemma F.12, we have
C.
ni(log 221)2-2/M - O,
(76)
as - Do. Here, the constants hided by θ only depend on (00(0s), Ps. and (M, p, 9. r,r,))
Proof. With Lemma F.12, we know that
L44 - Ct L7 (d((i)
2-2/M S -Cm
Now consider the function,
S(z) = f
C, 2z log nu
1
2-22/ 2/M du, ('xx) =-
2-2/M
x² log
1 no
I When S La < nez, we have (zx is increasing and S(x:) is convex. Hence,
S(C,+1)- - S(C,) (c,))( - -.,) 2 Cnn.
This leads
= S(C,) - S(C,) 2 Cin(1 8) = -(c,)=
Hence, we must have S(2) - +00 as + co. This leads L. + 0. Hence, there exists > s such that La L.//2 To get an upper bound S(C,), show that L1+1 2 C for s. Note that
16++1 2.l < | 0 0el = /
5 11B3C... (0t -1- + 1) (ptte +1)
(6)
x nLBBLLtte (pe-e + 1)) n c) c) S 5 Lr.
where (i) follows from Lemma F6,, (it) because of Pute 2 Pt, and the last inequality due to our assumption. Hence, we have (note that Lt+1 $ f.)
<3 (o(C))
2-2/M
< <45Z+1 (l0g nL1+1
1 2-2/M
Therefore,
L141 - Lt
2 -4C2m
2 2-2/M
C7+1 log n
Now since C++1 S Ci+e S Li, we have
S(C++1) - S(C.) S'(H+) - L.) (CC))) L.) s 4C2n.
This leads to
S(C,) -(C)) < 4C2n(t s) = S(C.) Omt)).
Therefore, S(C.) = O(n(), where θ only hides constant depending on C₁ and C2. By Lemma G.3, we know that
s s-((x)= - - 1
(((lo((zz))22111
Hence,
C. 0
(log 2-MM 0.
This completes the proof of Lemma F.13.
64

---

Implicit Bias of Gradient Descent for Non-Homogeneoos Deep Networks
Lemma F.14 (Parameter convergence for GD), Under the same assumptions Lemma F.12, we have
Pt (1)gn)))
(77)
as 1 + oc. Here, the constants hided by θ only depend on 7 (00())), Ps. and (M, P, r.r,)
Proof. Note that by definition
Pt M (
((r,)
Ologntt)
7 (0.)
7 (0,)
On the other hand, by the near-homogeneity f, we have
Bpt M 2 Jmin(()))) 2 log
7 Pt -t)
nLt
This completes the proof of Lemma F.14.
Combining Lemmas F.13 and F.14 concludes the proof convergence rates Theorem 6.1.
F.4. Directional Convergence: Proof of Theorem 6.2 (Part 1)
Similar to the proof Appendix C.6, the main idea is to construct the desingularizing function O. For GD, we use (0.) denote 7 GD (D.) and Ç. denote |0,+1 0.ll- Our goal is to show that Σ.z. St < o0. This leads to that the curve swept by O, has finite length, and that 0, converges to limit, thus proving Theorem 6.2.
The rest of this section will be devoted to the proof of Σ 12 < cc. Since ()60():))22))) is increasing and bounded from above, we know that
(D.)))
7+ +000
exists. To show that Eizo < oo, prove the following lemma.
Lemma F.15 (Desingularizing function for GD). There exist R 0, and definable desingularizing function Yi
[0, v). such that for all large enough with ||Oz]| R and 7 (0,) 7 v, and all E [0, 1]. it holds that
&e S cvL (7+ - 7D (0r(0))) GD (0+1))))))
for some constant 0. As a consequence, have
S S c( (7+ - (0) - (7+ (00(0(+)))
Once we have this lemma, we immediately know that
Essc T (7= - (0,) 1 (7- - (0(())))) to0.
The remainder of this section will be devoted to the proof of Lemma F.155
Recall that we defined the spherical parts and radial parts of Ōf(0) = v for a differentiable function f. In this section,
we also use a, to denote e (Gi), where we recall that
2
2
s (xx) ((x) ((x))
v'(x)
xΦ(x))
(x)(
will first show that Lemma E.16 (Decomposition of radial and spherical parts for GD). Under Assumption 5, we have for all sufficiently large
t t2s s.
GD -000 -7 2 on c0 (0.)))
10,, (0.)11)10
(78)
and
60 = | all
11 f.ll
and G S 1
(79)
Pt
65

---

Implicit Bias of Gradient Descent for Non-Hoomgeencous Deep Networks
Proof. Recall from our definition that
Otta = 0, - VnnVVLi, atta = g(0++a);
aeta exp(((((taa) Pt+a = 100-all: 7 (Octa)
a1+a M
Pita
We first show that
dy 0 (1+a)
dy (0,)
( 7 fill).
da
a=0
dt
To this end, we follow the proof scheme of Lemma C.17. Note that
dy (0,) (O.), VV) (18,7 (0.)) - - - (0, - (.)))
dt
it suffices to prove the following two statements:
(a) (0, (0,),
(0:), 0₂) and (-0,L,, 0.) have the same sign.
(b) 01 ( and - f. point to the same direction.
Proof of (a). It suffices to show that (V GD (0.). and - (VL,, 0,) have the same sign. By Lemma E8,, we have
-(V,, 0₂) = it 2 O. Next, we show that (V> GD (O.), 0₂) 2 O. Note that
Va
Ma.et
(O.)
Ph
M+1
Pt
which implies
(Vay 0.)
Ma
V (0,0,
Pt
M
Pi
Through direct calculation, obtain that
(Va,, 0,) 0. = 0,)
a. (CpaLPo) - G.Pa
+ = a. (
From the proof of Lemma F.3, we know that
Φ (z) < xΦ(x) <0, 0 x < ne?
Further since (see, e.g., the proof of Theorem F.9)
eoolod 2 MG.
we obtain that
(arr 01) =G) (-1G))(colllnn) (ealvii++++pple Gop' (-
2 at G.O(G.)
MGro(Ge) = Man.
which leads to (V.)D 0.) 2 This proves part (a).
66

---

Implicit Bias of Gradient Descent for Non-Hoomoeencous Deep Networks
Proof of (b). Straightforward calculation leads to
Var - (Va,, 0,)
01,.0(0.) = (0)) 60 (VV,))))VVV(),,)0,000) (0,,
= =a.4'(G (VL, - NVC,00)00,
=. (mi) 011)
which points to the same direction as Ci since & (9())) < 0. To complete the proof, only need to show that
7 7 (0++1) (0+1))-750(0) 2 (0,)
dt
for some constant c. We first compute
(0,)
df
Marpl
dt
M Pt
Further since z + e (xx and + Pita = 110: aV
M are all convex, it follows that
6D ( (0.+1) - (0,)
a++1
P + (pttl Pt M)
MM
411 a1
Pif 0. O. (9.)
- Gt)
Masp pert1
(1) a. (9.9%
Mash Pt Marp PC PM--
a (C))ll9
Pf
M-T
2pt4
(10) a (9)))
(GDS as
PM
Pi M+1
2p
d- (0.)
Ma (G.))l
at (G)
dt
p M+1
2
where (1) follows from Taylor expansion: proceed, we first give a lower bound on de By definition,
E [0, 11, and (ii) follows again from the fact that + Pita is convex. To (D
M
(D.))
Taat patt1 (a.p) Mapp') M (cpaler)/ -.pp'(p) (1) pC
1
(G(G (VGc, -VC, - -M
df
nai
(-D'(G))
M ut
PM
To deal with this term, we note that
('.).)
(RL()))/VE.1 (p.'
M U1
Pt)
Pt
1
( - (P)'
1/2
M
Pr)
Pt
( - (pt)
Pt)
(1)
(Pc(os) V (pp)( 1t )
96699)2
P:
67

---

Implicit Bias of Gradient Descent for Non-Homogenecous Deep Networks
where (1) is due to (xx) -1/20((1) 2/x) and (xi) follows from the fact that
VL ePalor) "i
"
(p)' "t Pt (eelloi ((P'(PP)Pec)
By Cauchy-Schwarz
Pr
Pi
4
Pf
2t
(MG,0(Li) P'(n.) p'(n-)ee- -GP(((p)pp)
By Lemma F.8
Pf
2t
(M,) - Mpa(p:)9.)
By Lemma F.1
pf
ps
We thus obtain that
dr (0.)
ajt
2
(Palee) VL - (ep'a(t)) dt
(80)
df
Pad 9
PE
7/4
2
(Palle) 2 Gpoa( |V Ut
By Cauchy-Schward
P gio(gi)²
na, 2
V ( Sup'(le))pt)
Pt (g)()
1t.
Ijar 2
|V (9))(9))
Similar the proof of (ti) above
Pt (g)(),)
14
nMa |V
PM ((G,)
We next prove two useful claims:
(c) There exists a constant 61 < 1/2, such that
ar (.( (9.))
nMa 2
(0,)
< 61 PM ((G,)
S c
2pM1
dt
(d) There exists a constant 02 < 1/2, such that
Ma. Ma.4(GG))9
(9.)
ag 1r19
2
(0,)
Pt
M+1
02
p G.0(g,)2
S 02
dl
Proof of (c). According to Lemma F.6 and Lemma F.7, we have
g <
<
+ 2M-2 2M- Bet
1)
for sufficiently large t. This implies
at 1 (G.)11HH
Laa a. 4 (G M- + 1)
2p
2
<Cn 2 aj 4 (0)
M5 +
1 M-2
<C>21V a, (GG))
where the last line follows from the fact
C
x (G(G)))
G.)(G.) +
<
g,
g.)(G.)
68

---

Implicit Bias of Gradient Descent for Non-Hoomgenncous Deep Networks
when 91 1/ne2. Hence, it suffices show that
nda, 2
|VC,11
M-2 - c1
Cmpt
2M -2 S C1
((G,) Pt
Pt ((G.)
Vt
where C' depends on Go and M. Using Lemma F.6, we know that for sufficiently large t,
VClll BaCa(p + +1) S CLiP
thus leading to
Cnpt S
S Cnpt 3-M-2 Lts
which can be arbitrarily small as t + oo due to our result on convergence rates of P: and C.. This proves part (c). Note that our proof works for any v and sufficiently large I, and the constant ej can be arbitrarily small.
Proof of (d). Eq. (80), we already proved that
d7:D((0))
a4a 2 9,0(9,)
- 2h Pz. 1
dt
pt
p. glo(G.)²
Therefore, suffices to show that
Mad (9)))
ac [
2 Gro(G.)²
M+1
02
M
Pt
which reduces to
M MG)'(G))ll
2
C2 Gr)(Ge)²
Since
(G)))
p = 1| Ut
n
G.O(G,)'
Pt
we deduce that
MID'(
CM Vi < " GG)(G)) pt
Pt
It remains to show
p Cnu S C2 (GG))
Using our estimates on v, from the proof of part (c), we know that
Cıju, < Cap L.-
To complete the proof, we need upper bound on (GG). By definition,
((G.) log 1 nePu Ce
S llgg L.
We thus obtain that
1 Cm),,((G)) S Cmp.a M Le log < p C,
as + co, which is easily seen from the converges rates of L, and Pt. Similarly, 02 can be arbitrarily small and our proof works for any >> 0.
Combining parts (c) and (d), it follows immediately that
GD (0.+))+) -0, (0.) (1 - -1
69

---

Implicit Bias of Gradient Descent for Non-Hoomgeencous Deep Networks
completing the proof of (78). The first part of (79) can be shown by direct calculation. For the second part, have
%
d0 +=
d0
C: = |10++1 0cll =
-
b+
dz.
dz
d=
We will show that [|0++=ll= d0.+2
is non-increasing function of z, that
Se S |0: 1
Pt
where the last equality follows from the proof of lemma C.17. Note that by direct calculation,
d0r+z
1
d00-
0 +++
0
PL+=
dz
PL+:
de
VL(O.)
01+z
0 0
Pt
V.(0.)
VL(O.), 0,
0
0.
Pt
since Pt+z 2 Pt and (- VC()), 0,) 2 0. This proves (79).
Then, need some inequalities connect (0,Ce, 01 Li) and (0,7 (1.) (0) The main idea is to show that their ratios are close. i.e.,
||0 L.|l | ||
, (0.]
|D (0:)
The technique is to use ae to bridge these two ratios. To this end, we need the following auxiliary result:
Lemma F.17, There exists a constant C > 0 such that for all sufficiently large 2 8 and a E [0, 1}. (0)
||
C/|@,|1,
(10,,0(0
(81)
Proof. We first prove |0t+all I 0/ By definition,
10++al S ||0,1| + +
From the proof of Lemma F.16, we get the following estimate:
B (p M M-1 S P
|[L())) B.Cept M-
for large enough t. Hence, |0.+all - Cl|.. For the second part of (81), we have for any O
0
G0 (0)
Va(() (200)-Ma((00 Ma(
| M
10
where a(0) ex))) It suffices to show that
va(O Ma(O(+a)
Qita
S C
0 Va(O.) Ma(e))
0
1
00 12
To this end, we first give lower bound on the right hand side. By Cauchy Schwwar inequality,
O,
1 kVa,, 0.) Mar
Va(O.) Ma(O.)
10.12
P:
(',))
(-opalee) u2 + (.p'( Ma; .GG
(82)
P1
2
Ma. 2
Pr.
G.6(9,)²
Pr ((G.)*
70

---

Implicit Bias of Gradient Descent for Non-Hoomgesseous Deep Networks
where (i) follows similarly in the proof of Lemma F.16. Denoting
A( = Va(0) Ma
|101
then we have for some a).
[|A(0(+a) - -00 0.l
We now upper bound | A((++))) in the above display. For any 0,
(V)
[101|21 00 T
|(A[))] = v2a(0) M
Ma(0)
10
||0||
<|[2aa(0)] + M |a
(a
|01
We estimate these terms respectively. For ||| large enough:
|0 )c(()))(()))(((((()))))))))))))) (0000)0000000 M-
=
<0,0()) 10| - Ca( |0011-11
((G(e)
O(G()))
<
<cfa(() (100 + (ia(()
(11))*+++1) + Cza(0) 1
((C(0))
((S(O))
o(9(0))
1)
|
<Ca(E) o(G(O))
I Ca(
(GG())
Here, the upper bounds on [g(0)] and [+) are due to Lemma F.7. We thus obtain that
| C 0 2M-
M a())
+ Ma(0)
Ca(0))10122-2
((G(0))
((G(0))
1
for sufficiently large ||@|]. Further since (g(0++e) C(0,) = o((9(0:))) as t + co, we know that for sufficiently large t, a(O++c) < (f.), thus leading to
A < 24- M2-0
finally follows that
[|A(0...) A(O.)II 5n 5=] CnllVCo 2M--
< <C 3M-
3M-3 < Cn9ia exp(-Pa (pt) 3
Ma
(GG) S A
for sufficiently large t, where the last inequality is just (82), and the second- sccond-to-lass one is because of G.O(G.) S C' for any G. < 1/ne?. This finally leads to
O
O,
va(O(4a) Ma(O+ta)
2 Va(O.) Ma(O.)
10
110.112
completing the proof of Lemma F.17.

---

Implicit Bias of Gradient Descent for Non-ooomoesscous Deep Networks
Lemma F.18 (Inequalities between d, and y (00((0))) Under Assumption 5, for all sufficiently large 2
||ā,ael| 2 My (0.)pt (0.)pr -1
(83)
and
10,,)0 C1M log + (21)
(84)
Pt
Combining these two inequalities, there exists threhold > >>> 0, for all sufficiently large t 2 81, we have
10 2 7 (0.)p: M 10,- (0,
(85)
Proof. First, note that from the proof of Lemma F.16, have
|1 = 1 (Var 01) 2
Ma
(000(0))) M7 (0))p M-1
(86)
Pr.
Pr
which proves (83).
Second, again from the proof of Lemma F.16, we get
1
||0,7 GD
(0:)
((Va,, 0.) Mar)
M+1
Pi (e))
1
(e - Gap's - -Mat)
M L.
+ p'((p) P(((e)pe) - Maa
M++1
Pi
1
(ac) (M log + Mo(G.) + 2p'( -Ma))
M+I
Pi
(
logn + log (p:)) + Ma. ( 1))
M+I
Pi
1
(G1 (M (M 2p' (p:)) +
M+1
M+T (Ggl + C))'(
where
C = sup é ( C2
(a) ((0(())<δδ()) - 1)
sup 0<a<i/nee
0<rc1/ne3
positive constants (easily seen from the definition of b), and (i) follows from lemma F.8.
Finally, the proof of (85) follows the same way as (32).
Now we will use Lemmas C.19 and C.20 to prove Lemma F.15.
Proof of Lemma F.15. Recall that we have the following decompisiton in (78):
(0+4)) - (.) on (100, (())),(())))))). 10l (00)]]@)A))))
Two cases will be considered in this proof:
Case 1: | GD (0,) is larger, and we will apply Lemma C.20 for construction.
Case 2: (00.)ll(0 C,] larger, and we will apply Lemma C.19 for construction.
72

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
The cases will be determined by the ratio of ||_>> (0,)l and (10,)5000,]] In assume that:
|0 GD (0)] S p 100,,
(87)
For case 2, the condition is:
((1100(0)) 2 pf [10,,,0
(88)
Case 1. By (85), have
||0,aell 2 (00())))))) M+ 10, (0)1l
2 7 6D (02)p M+ 1دا GD (0.)
By (34)
2 7 GD (0. ) 0 azll-
By Lemma F.16.
(89)
Now we need to transfer this inequality to the ratio of ||__C || and ||a,C.ll. Note that
1
(VL,, 0.)
|0 = (aa, 0₂)
(Pv)
Pt
LiPt
S (V,, O1)
110.Coll-
LiPt L.
On the other hand, we have
10
L. Cell
Combining these two inequalities and pluging them into (89), we have
|1a,C,1 2 GD ( 1 Cell.
(90)
On the other hand, we know that there exists $2 > such that for a.e. t t $2, we have P: > 1. Hence, we have
(0,,0( - 10,, + 1 (0))) < 10
(91)
Therefore, in terms of (78), have
y (0(40))) - (0((0))) (0.) (0)0))n00(0)))))....)
7 (0.)) on 2 Pt (0, |,1
By (90) and (91)
w cpt 10, (0,
By Lemma F.16
(92)
Now we invoke Lemma C.20 to construct the desingularizing function. We apply it to the definable function 7 with A 7. Then there exists 21 0 and definable desingularizing function V on [0, v1) such that
(0)
8V (7. GD (0) 5/ (0) 2 1,
if GD (0) 2 V/-
Further, Lemma F.17 implies that there exists constant 0, such that for all [0.
8V8 (7-- ())) 110 60.)ll (0.)l GD 2 %
(93)
Plugging (92) into the above inequality, we have
8V -
(0+)))))),,0000 cli (f) > 7/ M1
This completes the proof for case
73

---

Implicit Bias of Gradient Descent for Non-Homogenecou Deep Networks
Case 2. By lemma F.16, have
(0tt1))-770000 (100)>0(00))ll)))) 4.ll 2 cprll01 ?
(94)
For a.c. 12 81 28> O, we have
[0,)00(0))1 2 02 100,, 2
This leads to
[0,>c0(0.)) 2 5 11,
Plugging this into (94), we have
- 2
cpt 2
|0 6D (k.)
(95)
We invoke Lemma C.19 construct the desingularizing function. We apply it to the definable function % GD with c 1 andd) 17 1. Then there exists 1/2 >> and definable desingularizing function 2/2 on [0, 22) such that
V2 - GD ()) | 01 GD (0)1 2 if GD (0)
2 7 V2-
Further, Lemma F.17 implies that there exists a constant e > 0, such that for all a E [0. 1].
22 7 60 a))p:110+ 6D (0)) 2 c,
if GD 0,) 2 7o - -V2
(96)
Plugging (95) into the above inequality, we have
2 - 7 (Oc+aa) (7 6D - (0=0))))))) 2 dft, if (0,) 2 7/+ 1/2
This completes the proof for case 2.
Combining the two cases. Since VI 122 is definable function, it's nonnegative or nonpositive some interval (0, v). Let V = max 1, 122. Then, we have for a.e. large enought t such that Pi 2 1 and (G((e,) 2 Ys v, and log n + (pt) S Pt it holds that
M
GD (0 (0 - - -00()) 2 Gt+ eV 7
for some constant с 0. The final conclusion follows directly from the Lagrange mean value theorem. This completes the proof Lemma F.15.
F.5. KKT Convergence: Proof of Theorem 6.2 (Part 2)
The main idea is to verify the KKT conditions. Recall that the optimization problem (P) is defined as follows:
min 1012. s.t. (0; x,) 2 1 for all e [n]].
Following the notations in Appendix C.8, we have
f((0) (0xx)) ( min fO), iE|n) fu.(0) = y0;H(0;),), x:), JA (0)
min (0), scim]
h,) (0). h(0) F.(0) h (0)
i=1
(+) = (0), hH
F((0) (0).
We are going to verify that 0, = O..((fH,mmm.) (0.)) 1/M satisfies the two conditions in Definition i.e.
74

---

Implicit Bias of Gradient Descent for Non-Homogenscuu Deep Networks
1. 110 - Ei= A,HH. (0) where (0) (0) for all E [n];
2. For any i E [n]. X; (0) - 1) 6.
Recall that ) and 3 are constructed as follows:
21-2/M Pre f:(0)
(0,, ho((
(0) n 14 (0)
B.
0 (H((),)
Since our model assumptions are the same as those of the GF case, Lemma C.21, Lemma C.23 and Lemma C.24 hold here. Hence, the second condition is satisfied. All we need to show is that
(0,, (H.) B. 00 hH (0.)ll
1.
Similarly, we will only show subsequence of 3 goes to O. Note that by Assumption 3 and Proposition 5.1, there is function r(z) = o(x"~1) as z + cc, such that for almost every 0, and any i [m], we have
(..))) SH. (0.) & r(1 Oxll = r(p))-
Lemma F.19 (Bound of 3 in GD). Under Assumptions 3 and 5, we have any 12 >> t > 8,
(12(1) B,) 1
1 (1(
loo
P++1 S Pt
1
log
2 (0
(97)
M
GD (0.))
where
(0,D(0,)pp)) M-1' Pz(t) Pa(pt)
2r(pt)
(t( =
(o,)(0,)
Proof. Note that in Theorem F.9, we have shown:
GD (0++1) (D,)) 2 log
Pt+1
0 LelB
Pt uî
We will give a lower bound of Mppl 2,13, For the numerator, we have
For the denominator, we have
= (-VL, 0,)
I.(0,) (V]( 0.) S (hH(0.), 0.) + L.P.ppap.))
(98)
1=1
|0 /V2.3 (VL., [b(00)122 (h(O,), 0.)
(99)
Similarly, we have
1 Σ [h(0.) hn()l)l S
- (.))) (1,(0.))) hn.) & Car(pt)-
==
And we can get In what follows, we will use h and h4 as shorthands for h(O,) and h4 (0,), repsectively. As Pt - 00,
[h(0.)] 2 (0.)l [l. h2) > | Lrr(p.).
(bH, 0.)
M ME E - f.(0.) (H.)
hhl
Pt
nppt
M -i=1 J.(0.) (f((0)) Pa (pr)
np:
75

---

Implicit Bias of Gradient Descent for Non-Homogenecuus Deep Networks
ML(
2 MML,00(0))))
Pt
GD 2 M (0.)pt M-1 2 2Lr((p:)
(100)
for sufficiently large Pt, since r(p:) o(p! t co. Therefore, there exists 85 >> >> 0 such that for a.e. t 2 $5, have
|b|l
|ball + (hH, h - ha) + || 1h-ll hall
|hill + +22(24 (1, h - hH)
| - 2|| L Cer
|aill ( (1- My60 (0.)pt 15
2r(pt)
(101)
At last, we have
(h 0.) = ve/pt S (hH, 0.) + LiPa (pt)/Pr
(102)
Plugging (101) and (102) into (99), we can give lower bound for ||0 L:
2r(p:)
|
hH 11 1-
M-1 ((hH, 01) + Cppa(Po)/pp)=
(103)
(0,5(00))22--
Combining (98) and (103), we have
[|H|1 1 101--2(nn) (r(00) (0.)p/ }1] - ((hH, O.) + pcpa(pt)/pb)
P
Cal1
up
((h. 0.) (PPa(P))
[BHll (
"
((bH, 0,) + (PP
Mr [1
(3, + (ppa 11)
1 1 (M7
B3 + (M7
1- (1)
1.
(Be p2()))
This completes the proof of Lemma F.19.
Once we have this, we can show the following analogous results. We omit their proofs since they are completely similar to those of Lemma C.27 and Lemma C.28.
Lemma F.20 (3 converges to 1). Under Assumptions 3 and 5, there exists sequence ia such that limgg 3tx 1. Lemma F21 (Approximate KKT point). Under Assumptions 3 and 5, there exists a sequence tk such that θ is an 5K) point of for all N, where e -> and 5z -> l- - co.
We are now in position to prove the KKT convergence. Appplying Lemma F.21, we have sequence {t& } such that 0, is an (ex, KKT point of (P) for all & E N, where e - 0 and ôş - 0 as k + co. Since Or, converges in direction. O,, will converge to the same direction as one of the KKT points of (P). By Theorem 6.2, we know 0,, also converges to the KKT point of (P). This completes the proof of Theorem 6.2.
limit 0., Hence, (JHHm.in, (0.)) 1/M
76

---

Implicit Bias of Gradient Descent for Non-Hoomoesssous Deep Networks
G. Additional Lemmas Lemma G.1. The function π IR
1 11
a(U)= log
Σ
exp(-ti)
convex.
Proof. Let e= 0; vi So
T(0x + (1 - O)vi) = log
1 Σ
exp(-0x; fx; - (1 - ()wk)) (1-8)ua) = log
Σ
1=1
1=1
From Hölder's inequality, we have
x.- )
(Σui
(1-0)
Σ
Σ
Ditl S
1=1
i=1
Therefore,
log
u
1-0
s log
Σ
n
Ui
0.
1
n
(1
(1-0) 03
1
1-0
71
The right formula can be reduced to:
Blog
1 Σ Ui (1 log
1 (1
Σ
1
Therefore, we get:
π (fr + (1 - 0)y) s (x(x)) + (1 ()))
This completes the proof of Lemma G.I.
Lemma G.2. Let and S(x) S
(log 2270 dl. Then,
S(x)= 0
x (log 2-M2 2/M
s-'(y)= = =((v(ogy))22))
Proof. First, bound the rate of S(x).. Note that
S(x) = J." 1
(log z)2 2/M di 1."
(log 2)/M (log t)2
di S (logæ)2/M 2/M f."
=0 -0 (log 2-
x
(log 1)2 1)2 dl =
On the other hand, we have
S(x) 2 va (log 2)2-2/15
dt 2 ((log ((log=)/2))) 22/22
va (logt)2 dt = Ω
x
(20gx)222/M
Now we bound the rate of S- (y). Let r S (y)( for y 2 0. By the previous results, we have + 00 as y - co. Besides, we know that y S(x) θ (1ogz)=-2737
Taking logarithm on both sides, we have log O(log Therefore,
2 O(y(logz) 3/22// (
This implies that x = 222/M) This completes the proof of Lemma G.2.
77

---

Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks
Lemma G.3. Given two inlegers m, TO 24 and constant -mz let S(x) S (loggna))--aa dl for 2. Then,
S (z) (y) = 0 (loo((ny))) 2-1M
S(x) θ
(<((oog(na))>>////
(<loo((x)))222)
Proof. We prove the LHS rate first. Now we can bound the rate S(x). Note that
5(x) J[ P(oog(tt)) 2/15 dt
2/M (log(nz))) 2-M/M [r dt
82
---1) :)
1
(log(nx)))2- 2/M 2-1()
x 8)
( 2-2/
Besides, we know that
S(x) ["
1
(log(n)t)) 2-221 dt 2/M8
s (log(nz))3//M) 2/15
(log((n())2 dt
{llg((nt)) 1t)
3
(nzg()z))22/4)
(2zg))))))2/1))) x (log(nx))²
0
(x(log((n))))-
Combine them, we get that
S(z) = 0 (looo((x)))22211
Let S(x). Then, we have log(x) = O 1-0-llop log(g))) Hence, we have
(log(nx)))22211 2/M = (1log(nn)))22244
This completes the proof of Lemma G.3.
Lemma G.4. Given < < 1, when L. 2 (4/7(log(4/7))) we have
logt t 27
< t7
Proof. Let 2 1i, Then, we want to show:
((2) = 72 22og = 2 0.
Note that (2) = y
- -. When 2 2 2/7, g(2) increasing. Furthermore, we have
= 4log(4/7) 2log(4/7) - 2og log(4/7) = 21og 4/7
1og(4/7) > 0.
Since 4/7 (o.loog((//))) > 2/7, we have finished the proof of Lemma G.4.
Lemma G.5 (Moore-Osgode Theorem). Assume that series of functions (fx(z)) converge uniformly f(x) in (-a,a) a) for some 0, and for any lim fn(x) = Im exists. Then, both lim f(x and lim I exist and are equal, namely
lim Ln = lim lim Sa (x) = lim lim fn = lim ʃ fxx). -- m-
=+000
x- n000
z-40
78

---

Implicit Bias of Gradient Descent for Non-Homogenecou Deep Networks
Proof. Due uniform convergence, for any > 0 there exist ((e) E N, such that: for all æ (-a, (()))(())))))))))) n,m > N implies [xx) [x)] < 3. As x converges to limit L. In addition,
have [T,, Tun! < 3 which means that In is a Cauchy sequence which oo, we have Ln, L 3. On the other hand, if we take + first, we 3. By the existence of pointwise limit, for any > 0 and > N, there exist 8(c, n) > 0, such that 0 < |x| < δ implies [ - T.a < 3- Then for that fixed n, < |ar| < 5 implies (f(x) L.| s (f(x) fa (x)] +
have (x) - f(z)]
(f, - L.l + 14, L S e. This proves that lim f(x) l L..
79


Reviews:
[{"review_id": "P9SdC5Faaq", "reviewer": "Reviewer_Uxz2", "summary": "This paper establishes the asymptotic implicit bias of gradient descent for generic non-homogeneous deep networks under exponential loss. Specifically, the authors show that (1) the normalized margin increases nearly monotonically, (2) the direction of the parameters converges, and (3) the directional limit satisfies the KKT conditions of the margin maximization problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and suggestions on the writing style. We will include more discussions on intuitions and technical innovations for our theorems in the revision. For the technical novelty, please refer to the section **Technical novelty** in our response to the reviewer R5kD. For insights of our results, please refer to the section **Insights of our results** in our response to the reviewer NQfK. Below, we address your other questions.\n\n---\n\n**Q1.** “I am wondering whether the upper bound on the degree of the polynomial in Definition 1 can be relaxed…why does the upper bound have to be $M$, and is there any intuition behind this choice?”\n\n**A1.** In Definition 1, the upper bound of the degrees of the polynomials have to be $M$. We justify this from the following two aspects.\n\nFirst, we discuss its importance. If we relax the degree upper bound from $M$ to $M+1$, then every sufficiently smooth function $f(\\theta; x)$ that is uniformly bounded by $O(\\\\\\| \\\\theta \\\\\\|\\_2\\^M)$ for large $\\\\\\| \\\\theta \\\\\\|\\_2$ satisfies Definition 1. This includes predictors that do not admit a homogenization (see Theorem 5.1). Note that homogenization plays a crucial role in our analysis. For instance, without homogenization, it seems impossible to even define a KKT problem, let alone prove the implicit bias of KKT directional convergence of GF/GD. \n\nSecond, we explain the intuition for choosing $M$ as the degree upper bound. In Definition 1, the polynomial $p’$ quantifies the deviation of $f$ from an $M$-homogeneous function (see $f_M$ in Theorem 5.1). Given that we require $f$ to be “near-homogeneous”, it is natural to assume that the discrepancy between $f$ and $f_M$ (quantified by $p’$) is of an order lower than $f_M$. The natural assumption, $\\deg p \\leq M$, suffices for this purpose.\n\nWe will clarify these in the revision.\n\n---\n\n**Q2.** “Why is it helpful to define the upper bound as a polynomial of the weight norm? Did you use any specific tools for handling polynomials? If not, why not simply set the upper bound as $O( \\\\| \\\\theta \\\\|_2^M)$ instead of introducing the polynomial concept $p' ( \\\\| \\\\theta \\\\|_2) $?”\n\n**A2.** Good question. But before we address it, we would like to point out that the error upper bound is $p' ( \\\\| \\\\theta \\\\|\\_2) = O(\\\\| \\\\theta \\\\|\\_2^{M-1})$ in our Definition 1. So in your question, the error upper bound should be replaced by $o( \\\\| \\\\theta \\\\|_2^{M})$ instead of $O( \\\\| \\\\theta \\\\|_2^{M})$. We suspect this is a typo. But please let us know if we misunderstood your question. \n\nWe choose to define the upper bound as $p’$ in Definition 1, primarily for the simplicity of the exposition. This choice allows us to explicitly define the function $p_a$ (see Eq. (4)), which streamlines the theorem statements and their proof by making the inequalities more explicit and tractable.\n\nNote that our results are not limited to this specific polynomial form. If the upper bound in Definition 1 is replaced by a function uniformly bounded by $O(\\\\\\| \\\\theta \\\\\\|\\_2^{M-1})$ for large $\\\\\\| \\\\theta \\\\\\|\\_2$, our analysis still goes through when Assumption 2 is adjusted accordingly. However, we do not feel this provides new information compared to our current version.\n\nIn general, if the error upper bound is only controlled by $o( \\\\\\| θ \\\\\\|\\_2\\^{M})$, we expect additional regularity conditions are needed to carry out the analysis. As our main focus is neural networks, we feel our current definition is both clean and sufficiently broad. We leave it as future work to further extend our results.\nWe will include these discussions in the revision.\n\n---", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No, but the results look reasonable to me.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "The major contribution of this paper is to generalize previous results on simpler models to similar conclusions for a more general model. Additionally, I find the near-homogeneity definition (Definition 1) somewhat interesting, though I am unsure whether it was designed to make the proof more tractable or if it provides deeper insight.", "essential_references_not_discussed": "In the subarea of implicit bias, the key contribution of this paper is its consideration of a more general non-homogeneous model instead of a homogeneous one. Regarding the related work on homogeneous predictors, there are also special cases, such as shallow neural networks, with similar results. I think it would be helpful if the authors also referenced those papers.", "other_strengths_and_weaknesses": "Strengths:\n1. Generalization to Non-Homogeneous Models: The paper extends prior results from homogeneous models to a more general non-homogeneous setting, contributing to a broader understanding of implicit bias.\n2. Interesting Definition of Near-Homogeneity: The introduction of the near-homogeneity measure (Definition 1) is novel and could provide insights into implicit bias, depending on its broader applicability.\n\nWeaknesses:\n1. Limited Insight into Key Design Choices: While the paper presents generalizations of existing results, the motivation behind certain technical definitions—such as the choice of a polynomial upper bound—could be better justified. Explaining how this choice impacts proof tractability or brings new analytical tools would strengthen the contribution.", "other_comments_or_suggestions": "A small suggestion about the writing style: Since most people in this subarea are already familiar with the key results and proof techniques from previous works, I find the explanation of the implications of the theorems in this paper somewhat plain and less informative. In many places, the paper simply states that the results generalize previous work, but that is something the audience likely already knows. Personally, I would appreciate more discussion on the key insights and motivation behind introducing the near-homogeneity measure. For example, how does defining a polynomial upper bound make the proof more tractable compared to previous works? This kind of explanation would help readers better assess the contribution of this paper—specifically, whether the introduction of this new concept brings any novel analytical tools to the field.", "questions_for_authors": "1. I am wondering whether the upper bound on the degree of the polynomial in Definition 1 can be relaxed—either to some function of M,  or even made independent of M. If not, why does the upper bound have to be M, and is there any intuition behind this choice?\n2. Why is it helpful to define the upper bound as a polynomial of the weight norm? Did you use any specific tools for handling polynomials? If not, why not simply set the upper bound as $O(||\\theta||_2^M)$ instead of introducing the polynomial concept $p'(||\\theta||_2)$?", "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": "IqhQDrS2pj", "reviewer": "Reviewer_NQfK", "summary": "The paper characterizes the implicit bias of non-homogeneous deep models trained with gradient-flow or gradient-descent to minimize an exponential loss, under some seperability and near-homogeneity conditions. The results are extensions of previous works that found similar implicit bias in strictly homogeneous models.\n\n\n## Update After Rebuttal\nI have increased my score, assuming that the authors will incorporate the changes discussed during the rebuttal into the final version of the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments and will fix all grammar issues and typos in the revision. For the technical novelty, please refer to the section **Technical novelty** in our response to the reviewer R5kD. For insights of our results, please refer to the end of this response. Below, we address your other questions.\n\n---\n\n**Q1.** \"Is there an intuitive meaning to $p_a$? If so, it should be discussed briefly in the main paper.\"\n\n**A1.** $p_a$ is used in our Assumption 2. This choice of $p_a$ guarantees that the class of near-homogeneous functions under Assumptions 1 and 2 all behave close enough to a homogeneous function along the GF path for $t\\ge s$. Concretely, as shown in Lines 945-950, $p_a$ is chosen such that $g:= f - p_a$ satisfies a one-sided inequality of the homogeneous condition (see equation (3) in Line 152). This is a crucial design choice that enables our proof.\n\n---\n\n**Q2.** \"Possible typo in line 136-l, line 885 and line 1043.\"\n\n**A2.** Thanks for pointing these out. These are all typos. (i) The period in line 136-l should be a comma; (ii) $\\log \\phi$ in line 885 should be replaced by $\\phi$; (iii) In line 1043, $G$ in the denominator should be $G_t$. We will make sure to correct them and other typos in the revision.\n\n---\n\n**Q3.** Starting from page 35, there seems to be a change in the naming of the assumptions, e.g. (A1)-(A3), (B1)-(B3), which does not match the main text and is not clearly addressed.\n\n**A3.** We will fix this in the revision.\n\n---\n\n**Q4.** “Line 1212 — which proof does “We skip the proof here” refer to? Seems to be regarding Lemma C.14 which is proved later on, in page 27.”\n\n**A4.** You are correct. The proof of Lemma C.14 is on page 27. We will polish this part (and all the appendix) carefully in the revision.\n\n---\n\n**Q5.** “Line 1624 — what does “for all $i \\in [n]$” refer to? Is the supremum also being taken over $i$?”\n\n**A5.** This is a typo. In this place, we define $B\\coloneqq [ (\\gamma^{GF}(\\theta_s)]^{-1/M}$. Then we can verify that \n$$\n \\sup_{t \\ge s, i \\in [n]} \\bar{f}_{M,i}^{-1/M} (\\theta_t) \\cdot \\\\|\\theta_t\\\\|_2 \\le B. \n$$\nThis suffices for the remaining proof. We will fix this in the revision. \n\n---\n\n**Q6.** \"Proof of Lemma C.22 — there is a mismatch between the value of  in line 1630, and the RHS in line 1681.\"\n\n**A6.** This is a typo. The correct formula for $\\delta$ is \n$$\n\\delta :=  n B^2 \\frac{1+2 p_a(\\rho_t)}{M \\bar f_{M,\\min }(\\theta_t)}.\n$$\n\n---\n\n**Q7.** \"In light of this, the contributions of the paper given previous results seem marginal, as, in addition, and as far as I noticed, there is no significant technical novelty beyond that of [1, 2]. \"\n\n**A7.** We respectfully disagree with your assertions that our contributions are marginal and our technical novelty is not significant. For the technical novelty, please refer to the section **Technical novelty** in our response to the reviewer R5kD. For insights of our results, please refer to the end of this response.\n\n---\n---\n\n## **Insights of our results**\n\nWe highlight insights from our results in the following three aspects. \n\n**1. A good definition = good insights.** As a first step towards understanding implicit bias for non-homogeneous models, identifying the proper function classes for which meaningful theoretical insights can be extracted is already a challenging task. There are a few attempts in prior literature, but they seem to be far less fundamental than ours (see paragraph “Non-homogeneous Predictors” in Section 1.1). Our Definition 1 provides a natural quantification of the homogeneity error, covers a large class of networks, and has rich implications on the implicit bias. Such a powerful definition is rare, which already carries significant insights in our opinion. \n\n**2. Insights for understanding implicit bias.** Our results suggest that a near-homogeneous predictor has the same implicit bias as its companion homogenization (see Theorem 3.4 and 5.1). This provides an important insight: understanding the implicit bias of a non-homogenous predictor can be reduced to understanding that of its homogenization. Compared to a generic non-homogenous model, its homogenization is much simpler to study (despite still being challenging). \n\n**3. Broader implications beyond DL theory.** To the best of our knowledge, our near-homogeneity definition is novel and cannot be found even in pure math literature. As homogeneity is a fundamental math concept, widely used in many areas (such as PDE, harmonic analysis, and semi-algebraic geometry), our notion of near-homogeneity could motivate broader mathematical research beyond deep learning theory. In this regard, we believe technical tools established in our paper, integrating the near-homogeneity with o-minimal structures and non-smooth analysis (see also section **Technical novelty** in our response to reviewer R5kD), might be of broader interest. \nWe will include these discussions in the revision.", "claims_and_evidence": "The paper is theoretical in nature, and supports its claims with clear and convincing proofs.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the proofs in Sections C.1-C.4, only briefly read the proofs in the other appendices, and did not find any fundamental issues.", "experimental_designs_or_analyses": "There are no experiments in the paper.", "relation_to_broader_scientific_literature": "The paper contributes to the study of the implicit bias of gradient-based training of deep neural networks. Specifically, the paper extends previous results from the strictly-homogeneous setting to the nearly-homogeneous setting, thus extending the types of models to which the results apply.", "essential_references_not_discussed": "I do not think that there are any essential references not discussed.", "other_strengths_and_weaknesses": "The paper is well organized, and clearly written.", "other_comments_or_suggestions": "1. Possible typo in line 136-l.\n\n2. Typo in line 557.\n\n3. Typo in line 598.\n\n4. Typo in line 344-r.\n\n5. Possible typo in line 885.\n\n6. Is there an intuitive meaning to $p_a$? If so, it should be discussed briefly in the main paper. \n\n7. Possible typo in line 1043.\n\n8. Typo in line 4008.\n\n9. Line 1187 — $\\zeta_t$ is not the curve swept by the normalized parameters, but its length.\n\n10. Line 1212 — which proof does “We skip the proof here” refer to? Seems to be regarding Lemma C.14 \nwhich is proved later on, in page 27.\n\n11. Line 1624 — what does “for all $i \\in [n]$” refer to? Is the supremum also being taken over $i$?\n\n12. Proof of Lemma C.22 — there is a mismatch between the value of $\\delta$ in line 1630, and the RHS in line 1681.\n\n13. Starting from page 35, there seems to be a change in the naming of the assumptions, e.g. (A1)-(A3), (B1)-(B3), which does not match the main text and is not clearly addressed.\n\n14. Line 1925 — “Proposition” should be “Lemma”.", "questions_for_authors": "As shown in Theorem 5.1, Assumption 1 implies that the model is asymptotically $M$-homogeneous, and gives conditions for the increase of the norm of the parameters in Lemma C.4. In light of this, Assumption 2 seems to be “assuming what needs to be proven”. Specifically, it assumes that the parameters are already in a regime where (1) the dominant term is of order $>M-1$ (since $deg (p_a) = M-1$, and this exponent bounds the loss), and (2) due to Lemma C.4, that the norm of the parameters shall increase such that this behavior persists. Together, this implies that the main result applies only in the regime where the model is already “practically” homogeneous.\n\nThis is explicitly said in line 198-r.\n\nIn light of this, the contributions of the paper given previous results seem marginal, as, in addition, and as far as I noticed, there is no significant technical novelty beyond that of [1, 2]. \n\nCan you please clarify whether this observation is correct? Is there some delicate technical issue that I am missing?\n\n[1] Lyu, Kaifeng, and Jian Li. \"Gradient Descent Maximizes the Margin of Homogeneous Neural Networks.\" International Conference on Learning Representations.\n\n[2] Ji, Ziwei, and Matus Telgarsky. \"Directional convergence and alignment in deep learning.\" Advances in Neural Information Processing Systems 33 (2020): 17176-17186.", "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": "j0IEKI58X0", "reviewer": "Reviewer_R5kD", "summary": "The main contribution of this work is a generalization of previous theoretical results on the implicit bias of gradient descent for homogeneous networks to the case including non-homogeneous networks that satisfy a mild near-homogeneous condition, such as linear layers with an additional bias term (i.e., $Ax + b$) which are not homogeneous but empirically shown to converge to max-margin solution in previous works.\n\nIn general, I think the theoretical results in this paper are significant, in the sense that they make the study of implicit bias of gradient descent for classification problem (this topic has been studied for a long time) more comprehensive.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our paper! We address your questions first and then discuss our technical novelty at the end of this response. \n\n---\n\n**Q1.** “...my question is whether the formulation of exponential loss is necessary. Can the results still be valid for multi-classification with cross-entropy loss?...”\n\n**A1.** Our results can be extended to other loss functions with an exponential tail such as logistic loss. This is because our analysis focuses on the late training regime assuming that the predictor already classifies all data very well. In this regime, only the tail property of the loss function matters. Additionally, using arguments in [Lyu & Li 2020, Appendix G], there is no mathematical difficulty extending our results to multi-class settings using cross entropy loss. We will explain these in detail in the revision.\n\n---\n---\n\n## **Technical novelty**\nWe make significant technical innovations in our analysis. Below, we discuss them in our GF and GD analysis, respectively. \n\n\n### A. Technical novelty in GF analysis \n\nIn our gradient flow analysis, we make the following innovations rather than simply combining our near-homogeneity conditions and techniques from [Lyu and Li 2020, Ji and Telgarsky 2020]\n\n**1. Margin improvement.** [Lyu and Li 2020] directly analyzed the smoothed margin (see their equation (3)). This does not work for non-homogenous predictors. Instead, we have to analyze a modified margin (see (6) in lines 213-215). Identifying the correct modification of the margin involves a sharp balance of many error terms. This is quite technical as we aim to cover as many non-homogeneous functions as possible; behind the scenes, we solve multiple ODEs to identify the right formula. Coming up with this modified margin is a significant technical contribution. \n\n**2.Directional convergence.** The analysis in [Ji and Telgarsky 2020] heavily relies on a specific form of GF defined using the minimal norm subgradient; they then analyzed the corresponding spherical and radial components (see their Lemms C.2 and C.3)). This again fails to work for non-homogenous predictors. To address this issue, we have to consider a different form of GF defined with a special subgradient, which enables a special spherical and radial decomposition as shown in equations (21) and (22) and Lemma C.17. Moreover, we have to use an advanced property of the o-minimal structure to show that the choice of sub-gradient does not affect the global path property of GF (see Lemma A.6). \n\n**3.KKT convergence.** Our KKT convergence proof for non-homogenous predictors is new. Although KKT conditions are well established for a homogeneous predictor that maximizes the margin, it is a priori unclear why an optimal non-homogenous predictor admits KKT conditions. To address this issue, we first need to prove the existence of a sufficiently good homogenization of a near-homogeneous predictor (see Theorem 5.1). Then we come up with a set of KKT conditions of a margin maximization program — however, this is not defined using the original predictor — this is defined using its homogenization. Because of this discrepancy, we have to design and analyze new dual variables that involve both the non-homogenous predictor and its homogenization (see equation (44)).\n\n\n### B. Technical novelty in GD analysis\n\nWe solve many additional technical challenges when extending our GF analysis to GD. Due to the space limit, we highlight two of them:\n\n**4.Stepsize condition.** Although [Lyu and Li 2020] handled GD in the homogenous case, their stepsize assumption depends on a “constant” $C_{\\eta}$ (see their Assumption (S5) in Appendix E.1), which turns out to be function of the initial margin (see their Page 32), preventing the stepsize to be large. In comparison, our assumptions on the stepsize are weak, determined by an explicit and interpretable separability condition (see Assumption 5). To achieve this, we have to conduct a technical, yet much tighter, analysis of the GD path (see our Theorem F.9 and Lemma F.10). This is beyond the techniques from [Lyu and Li 2020]. \n\n**5.Directional convergence.** Our directional convergence analysis for GD is new. Note that [Ji and Telgarsky 2020] only analyzed GF but not GD, where tools from differential equations are unavailable. To address this issue, we construct an arc by connecting all GD iterates using line segments. Even so, analyzing the directional limit of this arc is extremely technical, involving careful estimations of the spherical and the radial parts of this arc (see Lemmas F.16 and F.17, which are not needed for GF). These additional technical challenges do not exist in the GF analysis but must be addressed in the GD analysis. \nWe will highlight these in the revision.", "claims_and_evidence": "The claims are supported by the mathematical proof.", "methods_and_evaluation_criteria": "Not applicable, as this paper does not have experimental results.", "theoretical_claims": "I checked the outline of the proofs, which appears to be correct to me.", "experimental_designs_or_analyses": "This paper does not contain experimental results.", "relation_to_broader_scientific_literature": "The contributions are mainly related to the implicit bias of gradient descent, where the most prominent results in my view are the convergence to a KKT of margin-maximization problem (Lyu & Li, 2019) and the alignment and directional convergence (Ji & Telgarsky, 2020) for homogeneous deep neural networks.", "essential_references_not_discussed": "The discussion of essential references is sufficient.", "other_strengths_and_weaknesses": "A minor weakness is that there lacks experimental evidence in this paper. \n\nIn addition, as many techniques have already been discussed in previous works (since the implicit bias of gradient descent is an important topic), I think the core contribution of this work is how to handle the difficulties brought by the non-homogeneity, hence it would be better for the authors to have a section to discuss the technical novelty.", "other_comments_or_suggestions": "1. The main results are using exponential loss only, while through the whole paper it is replaced implicitly by the notation $\\ell$. Then my question is whether the formulation of exponential loss is necessary.  Can the results still be valid for multi-classification with cross-entropy loss? This is the case for homogeneous networks. Will the non-homogeneity bring any additional difficulties? \n\n2. I think it would be best to have some experimental results to make this paper more complete, but I understand that the current version is also fine.", "questions_for_authors": "What are the main difficulties when solving the non-homogeneity compared to previous works and how do the authors introduce new techniques to solve them?", "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": "yXaQsuZwJn", "reviewer": "Reviewer_ueC9", "summary": "This paper studies the implicit bias of gradient descent for separable classification task and non-homogeneous model. The class of non-homogeneous models studied in this paper is quite general and covers many of the common deep learning models. The results of this paper shows that, if the model's difference to a homogeneous function is bounded, then the iterates of gradient flow/descent converges in direction to a maximum-margin solution. Most importantly, this paper extends the analysis of implicit bias from homogeneous models to a much more general class of non-homogeneous models that are relevant to deep learning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. For the technical novelty, please refer to the section **Technical novelty** in our response to the reviewer R5kD. For insights of our results, please refer to the section **Insights of our results** in our response to the reviewer NQfK. Below, we address your other questions.\n\n---\n\n**Q1.** “One big issue, but I think it can be fixed easily: In the definition of (M,N)-nearly-homogeneous functions, M,N are assumed to be positive, but Example 4.1.C has M=0?”\n\n**A1.** Thank you for pointing this out. This issue can be solved by relaxing our near-(M,N)-homogeneity definition to allow $M=0$. Specifically, we call a block s(θ; x) near-(0, N)-homogeneous, if it is independent of θ and near-N-homogeneous in $x$. We will clarify this in the revision.\n\n---\n\n**Q2.** “Some of the ‘theorems,’ such as 5.1, 5.2, and 5.3, should be downgraded to a lemma or proposition. … The definitions and assumptions are a bit scattered, so an index of notations/definitions would be a good addition to the appendix.”\n\n**A2.**  We will revise the paper according to your suggestions. Thank you. \n\n---\n\n**Q3.** “I would like to see M-nearly-homogeneous and (M, N)-nearly-homogeneous be unified into one definition.”\n\n**A3.** While these two definitions can be unified, we prefer to keep them separate for the sake of clarity. Since our main results in Sections 3, 5, and 6 only make use of near-M-homogeneity, unifying these two definitions would make these results harder to unpack for the readers. \n\n---\n\n**Q4.** “I do not quite get how the discussion on o-minimal structure connects with the rest of the paper. The author should elaborate on this.”\n\n**A4.** We will add a paragraph to clarify the role of o-minimal structures. Specifically, the o-minimal structure enables the chain rule of Clarke’s subdifferentials (see Lemma A.6), the existence of a desingularizing function (see Lemma C.14), and Kurdyka–Łojasiewicz inequalities (see Lemmas C.19 and C.20). These are crucial tools in our analysis. \n\n---\n\n**Q5.** “As I previously discussed, the technical work of this paper is very profound, but the high-level strategy is already present in the literature. So, I don't think this work offers new insights on the understanding of implicit bias.”\n\n**A5.** We respectfully disagree with these comments. For the technical novelty, please refer to the section **Technical novelty** in our response to the reviewer R5kD. For insights of our results, please refer to the section **Insights of our results** in our response to the reviewer NQfK. \n\n---\n\n**Q6.** “I believe that author should also mention this work … ‘Gradient descent finds global minima of deep neural networks.’....” \n\n**A6.** We will consider discussing this work in the revision. Based on our understanding, the paper you mentioned mainly uses neural tangent kernel (NTK) style techniques to study global convergence. This seems to be quite different from our focus: characterizing the asymptotic implicit bias of GD/GF in near-homogeneous models assuming a strong separability condition. We appreciate it if the reviewer could further elaborate on the connections between this work and ours.\n\n---", "claims_and_evidence": "The theorem statements are clear and easy to understand. And the paper devotes significant length into illustrating the relevance and generality of its results. I do not have any major issue regarding the claims of the paper.\n\nThe main results are not too surprising because they are intuitively the direct extension of the results on homogeneous models. And the high-level proof strategy seems to follow the existing literature. But of course the generalization to these \"nearly-homogenous\" function class would be very technically involved. In light of this, the theorems all make sense and are solid contribution to the literature.\n\nOne big issue, but I think can be fixed easily:\nIn the definition of $(M, N)$-nearly-homogeneous functions, $M, N$ are assumed to be positive, but Example 4.1.C has $M = 0$?\n\nA few small issues:\n1. some of the \"theorems,\" such 5.1, 5.2 and 5.3, should be downgraded to a lemma or proposition. Otherwise the results look too crowded. 2. the definitions and assumptions are bit scattered and so an index of notations/definitions would be a good addition to the appendix.\n3. I would like to see $M$-nearly-homogeneous and $(M, N)$-nearly-homogeneous be unified into one definition. \n4. I do not quite get how the discussion on o-minimal structure connects with rest of the paper, the author should elaborate on this.", "methods_and_evaluation_criteria": "n/a, this is a theory paper", "theoretical_claims": "see above", "experimental_designs_or_analyses": "n/a, this is a theory paper", "relation_to_broader_scientific_literature": "This work shows the implicit bias of gradient descent for a large class deep learning models. Many of the existing work in this topic only apply to limited settings such as linear models, deep linear networks, or 2-layer relu networks, etc, so this paper is definitely a very valuable addition.\n\nAs I previously discussed, the technical work of this paper is very profound but the high-level strategy is already present in the literature. So, I don' think this work offers new insights on the understanding of implicit bias. But given that the technically work is clearly a step above the current literature, I think a weak accept would be most appropriate for this paper.", "essential_references_not_discussed": "I believe that author should also mention this work:\n\nDu, Simon, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. \"Gradient descent finds global minima of deep neural networks.\" In International conference on machine learning, pp. 1675-1685. PMLR, 2019.", "other_strengths_and_weaknesses": "see ab", "other_comments_or_suggestions": "see above", "questions_for_authors": "see above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the implicit bias of non-homogeneous deep networks under exponential loss, and it provides a generalization of earlier results for homogeneous networks leveraging a near-homogeneity condition. In particular, the main results are that the normalized margin increases almost monotonically, the parameter direction converges and KKT conditions are satisfied by the directional limit.

All the reviewers agree that the results are interesting, novel and rather strong. The generalization to non-homogeneous networks is relevant, even with the caveat of a near-homogeneity requirement that may be a bit artificial. The authors' feedback has resolved most issues and all reviewers are positive about accepting the paper (with varying levels of enthusiasm). I concur: this is clearly a paper that should be accepted to ICML and will be a nice contribution to the conference. I would like to encourage the authors to incorporate the feedback received throughout the review process in the camera ready.
Decision: Accept (poster)