PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Descent Maximizes the Margin of Homogeneous Neural Networks

Kaifeng Lyu, Jian Li

arXiv:1906.05890v4cs.LGcs.NEstat.ML

TL;DR

Gradient descent’s implicit bias in deep homogeneous neural networks remains an open question beyond linear models. This paper analyzes gradient descent and gradient flow, showing that normalized margins increase in a smoothed sense and converge to KKT points of a natural max-margin problem.

  • Problem

    It remains unclear whether gradient descent has a comparable implicit margin-maximization bias in modern homogeneous deep neural networks as in linear classifiers.

    Source: §1 · p. 1

  • Method

    The paper analyzes gradient descent and gradient flow for homogeneous networks by deriving smoothed-margin dynamics using radial and tangential velocity decompositions and homogeneity identities.

    Source: §5 · p. 9

  • Results

    Normalized margins become non-decreasing after sufficient training loss reduction and converge to the objective value at a KKT point of a natural max-margin problem.

    Source: §1.1 · p. 2, §4.4 · p. 8

  • Takeaways & Limitations

    Gradient descent implicitly performs margin maximization in homogeneous neural networks, with potential robustness benefits from longer training.

    Source: §1.1 · pp. 2–3

    For deep homogeneous networks, KKT conditions need not ensure global optimality, so the analysis establishes convergence to KKT points rather than globally optimal margins.

    Source: §4.3 · p. 7

Abstract

from arXiv · show

In this paper, we study the implicit regularization of the gradient descent algorithm in homogeneous neural networks, including fully-connected and convolutional neural networks with ReLU or LeakyReLU activations. In particular, we study the gradient descent or gradient flow (i.e., gradient descent with infinitesimal step size) optimizing the logistic loss or cross-entropy loss of any homogeneous model (possibly non-smooth), and show that if the training loss decreases below a certain threshold, then we can define a smoothed version of the normalized margin which increases over time. We also formulate a natural constrained optimization problem related to margin maximization, and prove that both the normalized margin and its smoothed version converge to the objective value at a KKT point of the optimization problem. Our results generalize the previous results for logistic regression with one-layer or multi-layer linear networks, and provide more quantitative convergence results with weaker assumptions than previous results for homogeneous smooth neural networks. We conduct several experiments to justify our theoretical finding on MNIST and CIFAR-10 datasets. Finally, as margin is closely related to robustness, we discuss potential benefits of training longer for improving the robustness of the model.

1 INTRODUCTION

The paper studies why gradient-based training in homogeneous neural networks implicitly favors large-margin solutions, extending linear-classifier results to deep models. Under exponential-type losses and separability, it shows that normalized margins increase asymptotically, converge toward KKT directions of a max-margin problem, and yield practical gains from longer training.

1 INTRODUCTION

  • Homogeneous neural networks extend linear logistic regression’s implicit-bias setting because predictions depend only on parameter direction, while gradient descent drives linear models toward the L2-max-margin direction.The framework includes bias-free fully connected and convolutional networks with ReLU or LeakyReLU activations, whose homogeneity order equals their number of layers.Source: §1 · pp. 1–2

1.1 MAIN RESULTS

  • The theory assumes homogeneity, an exponential-tail loss such as exponential, logistic, or cross-entropy loss, and training separability, operationalized by loss below a threshold such as ln 2.The threshold guarantees 100% training accuracy, which is necessary for a positive margin; it does not imply zero training loss.Source: §1.1 · p. 2
  • After the loss falls below the threshold, a smoothed normalized margin becomes non-decreasing and converges to the ordinary normalized margin asymptotically.The ordinary normalized margin divides the margin by the parameter norm raised to the homogeneity order, while the smoothed version can capture short-term fluctuations.Source: §1.1 · p. 2
  • Every limit point of the normalized parameter trajectory lies along a KKT direction of a constrained max-margin problem, showing that gradient descent and gradient flow implicitly maximize margin in deep homogeneous networks.This generalizes prior implicit-bias results from linear classifiers to homogeneous classifiers.Source: §1.1 · p. 2
  • The loss decreases as O(1/(t(log t)2−2/L)) while the weight norm grows as O((log t)1/L) for homogeneous networks trained with exponential-type losses.These rates generalize the O(1/t) loss decay and O(log t) weight growth known for linear logistic regression.Source: §1.1 · p. 3
  • Training longer increases normalized margins in CNN experiments, and loss-based learning-rate scheduling accelerates both loss decrease and margin growth compared with constant-step SGD.On MNIST, the normalized-margin growth after 10000 epochs is approximately 1.2×10^-3 with scheduling versus approximately 1.8×10^-4 with constant learning rate; experiments also report noticeable L2-robustness improvements on training and test sets.Source: §1.1 · p. 3, Figure 1 · p. 3

2 RELATED WORK

Prior work established max-margin implicit bias for linear and deep linear models, while later studies extended the phenomenon to nonlinear homogeneous classifiers. This paper differentiates itself through weaker assumptions, broader smooth and nonsmooth settings, and stronger convergence and monotonicity results.

Implicit Bias in Training Linear Classifiers

  • Linear logistic-regression gradient descent converges toward the hard-margin SVM’s max-L2-margin direction, with extensions to stochastic optimization, other losses, and nons separable data (Soudry et al., 2018a;b; Nacson et al., 2019c; Nacson et al., 2019b; Ji & Telgarsky, 2018; 2019c; Ji & Telgarsky, 2019b).These results were subsequently generalized to deep linear networks and to fully connected and convolutional linear networks under exponential loss (Ji & Telgarsky, 2019a; Gunasekar et al., 2018b).Source: §2 · pp. 3–4
  • Margin maximization has also been studied for boosting methods and the Normalized Perceptron (Schapire et al., 1998; Rudin et al., 2004; 2007; Schapire & Freund, 2012; Shalev-Shwartz & Singer, 2010; Telgarsky, 2013; Ramdas & Pena, 2016).Source: §2 · p. 4

Implicit Bias in Training Nonlinear Classifiers

  • For nonlinear classifiers, prior work analyzed one-trainable-layer and single-unit ReLU models, while Nacson et al. (2019a) studied smooth homogeneous models and convergence toward KKT points of the max-margin problem.Source: §2 · p. 4

Comparison with (Nacson et al., 2019a)

  • Compared with Nacson et al. (2019a), this work requires only a temporarily small training loss, proves KKT conditions for every parameter-direction limit point, and avoids loss-direction convergence and LICQ assumptions.It also establishes loss convergence rates and normalized-margin monotonicity.Source: §2 · p. 4
  • Unlike Nacson et al. (2019a), which analyzes discrete gradient descent on smooth models, this work also studies gradient flow for potentially nonsmooth homogeneous models such as ReLU networks.Source: §2 · p. 4

Other Works on Implicit Bias

3 PRELIMINARIES

This section establishes the notation, binary-classification setup, and optimization dynamics used throughout the paper. It also introduces Clarke-based nonsmooth analysis and notes that parameter-direction convergence can fail even for smooth homogeneous functions.

Basic Notations

  • The paper uses standard notation for norms, logarithms, gradients, smoothness, and local Lipschitz continuity.Source: §3 · p. 4

Non-smooth Analysis

  • For locally Lipschitz objectives, Clarke’s subdifferential and its chain-rule framework support analysis of nonsmooth trajectories.The chain rule applies along absolutely continuous arcs for almost every time.Source: §3 · pp. 4–5

Limitation

  • Even for a smooth homogeneous function, gradient flow need not make the parameter direction converge; it can instead move around a circle over time.Source: §3 · p. 4

Binary Classification

  • Binary classification uses real-valued neural-network outputs whose signs determine predictions, with labels y_n ∈ {±1} and training loss L(θ) defined over the dataset.Source: §3 · p. 5

Gradient Descent and Gradient Flow

  • Gradient descent follows θ(t+1) = θ(t) − η(t)∇L(θ(t)) under C2 smoothness, whereas gradient flow permits locally Lipschitz losses and follows a Clarke-subdifferential differential inclusion.For C1-smooth losses, the inclusion reduces to the usual equation dθ(t)/dt = −∇L(θ(t)).Source: §3 · p. 5

4 GRADIENT DESCENT / GRADIENT FLOW ON HOMOGENEOUS MODEL

Under regularity, homogeneity, separability, and suitable smoothness or learning-rate conditions, gradient flow and gradient descent monotonically improve smoothed normalized margins and converge directionally to KKT points of a margin-related problem. The framework extends to broader losses, cross-entropy, and multi-homogeneous models.

4.1 ASSUMPTIONS

  • Under regularity, L-homogeneity, and separability assumptions, gradient flow requires a chain rule while gradient descent additionally requires C2 smoothness and a sufficiently small learning rate.Separability means the loss falls below 1 at some time, ensuring positive margins and correct classification; the learning rate may also be as large as O(L(t)^−1 polylog 1/L(t)).Source: §4.1 · p. 5

4.2 MAIN THEOREM: MONOTONICITY OF NORMALIZED MARGINS

  • Smoothed normalized margins are non-decreasing during training: gradient flow improves them almost everywhere, while gradient descent improves them each step unless the parameter direction is unchanged.The gradient-flow surrogate is an O(∥θ∥^−L)-additive approximation, whereas the gradient-descent surrogate is a (1−O(1/log 1/L))-multiplicative approximation.Source: §4.2 · p. 6
  • Training drives the loss to zero and the weight norm to infinity, while the normalized margin and its smoothed surrogate converge to the same limiting value.The paper also derives tight convergence rates for training loss and weight growth from normalized-margin monotonicity.Source: §4.2 · p. 7, §4.3 · p. 7

4.3 MAIN THEOREM: CONVERGENCE TO KKT POINTS

  • Every limit direction is a scaled KKT point of a constrained optimization problem equivalent to maximizing normalized margin, with finite-time approximate-KKT guarantees.Because deep-network margins can be non-convex, KKT convergence is not generally global optimality, unlike the linear-model case.Source: §4.3 · p. 7

4.4 OTHER MAIN RESULTS

  • The results extend to logistic and other exponential-tail binary losses, cross-entropy, and multi-homogeneous networks, where suitably defined smoothed margins remain non-decreasing when the loss is sufficiently small.With smoothness, limit directions also correspond to hard-margin SVM solutions using the neural tangent kernel, while the nonsmooth case uses generalized derivatives.Source: §4.3 · p. 7, §4.4 · p. 8

5 PROOF SKETCH: GRADIENT FLOW ON HOMOGENEOUS MODEL WITH EXPONENTIAL LOSS

This section sketches the gradient-flow proof for homogeneous models with exponential loss, centering on a lemma that links radial growth to increasing smoothed normalized margin. It then uses this lemma and approximate-KKT arguments to establish the main convergence claims.

Key lemma

  • Lemma 5.1 decomposes smoothed normalized-margin growth into radial and tangential dynamics, yielding d/dt log ρ > 0 and d/dt log ˜γ ≥ L for almost every t > t0.The lemma is identified as the key proof ingredient and is derived through homogeneous-model identities.Source: §5 · p. 9

Consequences for Theorem 4.1

  • The first two claims of Theorem 4.1 follow directly from Lemma 5.1, while margin monotonicity then implies a lower gradient bound, L → 0, and ρ → +∞.Because ˜γ approximates the normalized margin within O(ρ^-L), these results also establish the third claim.Source: §5 · p. 9

Convergence to KKT points

  • For Theorem 4.4, reparameterizing time by log ρ and integrating the margin-growth inequality shows that many times have small directional velocity ∥d ˆθ/d log ρ∥2.The boundedness of ˜γ is used to obtain these times.Source: §5 · p. 9
  • These low-directional-velocity points are approximate KKT points; convergent subsequences can be modified into approximate-KKT sequences with the same limits, which are KKT points by Dutta et al. (2013).The detailed argument is deferred to Appendix C.Source: §5 · p. 9

Proof of Lemma 5.1

  • The proof establishes radial growth by decomposing dθ/dt into radial and tangential components and applying the chain rule together with Euler’s theorem for homogeneous functions.The argument uses the identity ⟨∂◦qn, θ⟩ = Lqn and the bound e^-qmin ≤ L; when L(t0) < 1 and L is non-increasing, radial growth is positive for t > t0.Source: §5 · p. 9

6 DISCUSSION AND FUTURE DIRECTIONS … A.2 SMOOTHED NORMALIZED MARGIN

The paper proves that gradient flow/descent increases normalized margin and converges to a KKT point under minimal assumptions, while extending the analysis to broad binary losses through a smoothed normalized margin. It also identifies open problems involving nonsmooth optimization, stronger optimality guarantees, and bias terms.

6 DISCUSSION AND FUTURE DIRECTIONS

  • Gradient flow/descent makes the normalized margin increase and converge to a KKT point of a natural max-margin problem for homogeneous neural networks.The result is established under a minimal set of assumptions.Source: §6 · p. 10
  • Future work includes extending smooth-network results to nonsmooth networks, proving stronger optimality under structural assumptions, and handling non-homogeneous networks with bias terms.The bias extension is motivated by experiments in which a CNN with bias also showed increasing normalized margin, but a proof remains technically challenging.Source: §6 · p. 10

A RESULTS FOR GENERAL LOSS

  • The general-loss analysis includes logistic loss and other exponential-tail losses, including ℓ(q) = e−q3 and ℓ(q) = log(1 + e−q3).The results cover a broad class of binary classification losses.Source: A RESULTS FOR GENERAL LOSS · p. 16

A.1 ASSUMPTIONS

  • The loss assumptions require local Lipschitz regularity, L-homogeneity, structured exponential-tail behavior, and eventual separability below the threshold ℓ(bf).The exponential-tail conditions constrain f, f′, and its inverse g, while separability requires L(t0) < e−f(bf).Source: §4.1 · p. 5, §A.1 · p. 16
  • For exponential and logistic losses, the assumptions are satisfied; for logistic loss, bf = 0 and the separability threshold is ℓ(0) = log 2.The technical condition (B3.4) enables asymptotic comparison across data points and is satisfied by the stated examples.Source: §A.1 · p. 16

A.2 SMOOTHED NORMALIZED MARGIN

  • The smoothed normalized margin is defined using the inverse loss and parameter norm, with logistic and exponential losses yielding explicit forms.For exponential loss, the smoothed margin matches the previously defined expression.Source: §A.2 · p. 17
  • As training loss tends to zero, the smoothed normalized margin converges to the normalized margin, and Lemma A.5 formalizes this approximation.The proof uses a LogSumExp approximation and the large-margin properties imposed by (B3.3).Source: §A.2 · p. 17
  • For exponential loss, the approximation error is O(ρ−L), while logistic loss achieves the same O(ρ−L) rate when L is sufficiently small.The general approximation result does not require (B3.4), even though the broader framework assumes it.Source: §A.2 · pp. 17–18

A.3 THEOREMS · B MARGIN MONOTONICITY FOR GENERAL LOSS

Under assumptions (A1), (A2), (B3), and (B4), the paper establishes gradient-flow monotonicity and convergence results for normalized margins and KKT points, including finite-time guarantees and tight convergence rates.

A.3 THEOREMS

  • Theorem A.7 establishes a gradient-flow monotonicity result for the normalized margin under assumptions (A1), (A2), (B3), and (B4).Its statement specifies that, for almost every t > t0, a derivative condition holds for the smoothed normalized margin.Source: §A.3 · p. 18
  • Every limit point of gradient flow is shown to converge directionally to a KKT point of the constrained optimization problem (P).The theorem assumes (A1), (A2), (B3), and (B4).Source: §A.3 · p. 18
  • After finite time, θ/q_min(θ)^(1/L) reaches an (ϵ, δ)-KKT point when log ||θ(t*)||2 lies in an interval of width Δ = Θ(ϵ^-2).The interval begins at r = Θ(log δ^-1), and the guarantee holds for any ϵ, δ > 0.Source: §A.3 · p. 18
  • A refined analysis provides tight rates for loss convergence and weight growth under assumptions (A1), (A2), (B3), and (B4).The supplied passage states the existence of these rates but does not include their explicit formulas.Source: §A.3 · p. 18
  • For exponential and logistic losses, where g(x) = Θ(x), Theorem A.10 yields a corresponding corollary on convergence and weight-growth behavior.The supplied passage identifies the losses and condition but does not include the corollary’s explicit rate formulas.Source: §A.3 · p. 18

B MARGIN MONOTONICITY FOR GENERAL LOSS

  • The margin-monotonicity analysis uses gradient flow under assumptions (A1), (A2), (B3), and (B4), with ρ = ||θ||2 and θ̂ = θ/||θ||2.The analysis treats these parameter-dependent quantities as functions of time.Source: B MARGIN MONOTONICITY FOR GENERAL LOSS · p. 19

B.1 PROOF FOR PROPOSITION 1 AND 2 … C.5 NON-ASYMPTOTIC ANALYSIS

The appendix develops proofs of monotonicity, loss decay, and convergence toward KKT points for homogeneous neural-network training, including asymptotic and non-asymptotic analyses. The non-asymptotic analysis identifies an intermediate time at which the smoothed iterate satisfies the conditions for an (ε, δ)-KKT point.

B.1 PROOF FOR PROPOSITION 1 AND 2

  • For t > t0, log ρ increases and the smoothed normalized margin satisfies d/dt log ˜γ ≥ L, using homogeneous-function properties generalized to locally Lipschitz functions.The proof also derives an exact weight-growth formula via Clarke subdifferentials and chain rules.Source: §B.1 · pp. 19–20

B.2 PROOF FOR PROPOSITION 3

  • The loss L tends to zero, which directly implies ρ tends to infinity and, by Lemma A.5, |¯γ − ˜γ| tends to zero.The argument integrates a differential inequality and uses monotonicity of ˜γ.Source: §B.2 · p. 21

C CONVERGENCE TO THE MAX-MARGIN SOLUTION

  • The convergence analysis studies the norm ρ and normalized direction ˆθ under assumptions (A1), (A2), (B3), and (B4).The direction is analyzed through KKT conditions for the associated max-margin optimization problem.Source: C CONVERGENCE TO THE MAX-MARGIN SOLUTION · p. 21

C.1 PRELIMINARIES FOR KKT CONDITIONS

  • For nonsmooth constrained problems, approximate (ϵ, δ)-KKT points converge to KKT points when their errors vanish, the points converge, and MFCQ holds at the limit.The appendix uses a nonsmooth KKT framework based on Clarke subdifferentials.Source: §C.1 · p. 22

C.2 KKT CONDITIONS FOR (P)

  • For the neural-network problem (P), homogeneity ensures MFCQ at every feasible point, making KKT conditions necessary for global optimality.The objective is 1/2∥θ∥^2 and the constraints are 1 − qn(θ) ≤ 0.Source: §C.2 · pp. 22–23

C.3 KEY LEMMAS

  • The key lemma constructs an approximate KKT point from the normalized iterate; monotonicity of ˜γ ensures the construction, with β → 1 and L → 0 driving both approximation errors to zero.Corollary C.10 bounds β over time intervals, supporting the later directional-convergence analyses.Source: §C.3 · pp. 23–25

C.4 ASYMPTOTIC ANALYSIS

  • Every limit point of the normalized direction, rescaled by qmin, is shown to be a KKT point by constructing convergent approximate KKT points and applying MFCQ.The construction uses times where β approaches one and the normalized iterates approach the directional limit.Source: §C.4 · pp. 25–26

C.5 NON-ASYMPTOTIC ANALYSIS

  • The non-asymptotic proof begins under explicit small-error conditions, assuming ϵ < 6^2/C1 and δ < C2/f(bf).These conditions are stated for the proof of Theorem A.9.Source: §C.5 · p. 26
  • An intermediate time t* is selected so that β(t*)^-2 − 1 ≤ 2ϵ^2C^-2, providing the quantitative control needed for approximate stationarity.The existence of t* follows from Corollary C.10 within the interval (t1, t2).Source: §C.5 · p. 26
  • By Lemma C.8, proving that ˜θ(t*) is an (ϵ, δ)-KKT point reduces to establishing 1 − β(t*) ≤ ϵ and C2/f(˜γ(t*)ρ(t*)^L) ≤ δ.These are the two conditions explicitly checked in the proof.Source: §C.5 · p. 26
  • The first KKT inequality is obtained from the assumed bound on ϵ, which implies β(t*)^-2 − 1 < 3 and consequently |β(t*)| < 1/2.This bound is then used to control 1 − β(t*).Source: §C.5 · p. 26

C.6 PROOF FOR COROLLARY 4.5 … E.2 SMOOTHED NORMALIZED MARGIN

The appendices connect KKT limits to kernel-SVM max-margin directions, derive tight asymptotic loss and weight-growth bounds, and extend smoothed-margin analysis to gradient descent under smoothness and learning-rate conditions. The construction yields a smoother margin that controls discretization error while retaining the relevant limiting behavior.

C.6 PROOF FOR COROLLARY 4.5

  • Every limit point is aligned with a KKT point of (P) and therefore with a max-margin solution of the kernel-SVM problem (Q), using gradients for smooth models and Clarke subgradients for non-smooth models.For non-smooth models, the kernel is K_θ̄(x, x′) = ⟨h(x), h(x′)⟩ for a subgradient selection h satisfying h(x_n) = h_n.Source: §C.6 · pp. 26–27

D TIGHT BOUNDS FOR LOSS CONVERGENCE AND WEIGHT GROWTH

  • Under Assumptions (A1), (A2), (B3), and (B4), Theorem A.10 establishes tight bounds for loss convergence and weight growth.The proof first bounds the loss, then relates the weight norm to the loss and finally derives time-dependent bounds.Source: D TIGHT BOUNDS FOR LOSS CONVERGENCE… · p. 27, §D.2 · p. 28

D.1 CONSEQUENCES OF (B3.4)

  • The consequences of (B3.4) imply logarithmic derivatives of f and g scale as Θ(1/x), so both functions grow at most polynomially.Specifically, log f(x) = Θ(log x) and log g(x) = Θ(log x).Source: §D.1 · p. 27

D.2 PROOF FOR THEOREM A.10

  • Theorem A.10’s proof obtains tight asymptotics by bounding G and G^−1, controlling the loss, and relating the parameter norm ρ to the loss and time.The resulting relation is ρ^L = Θ(g(log t)).Source: §D.2 · pp. 27–29

E GRADIENT DESCENT: SMOOTH HOMOGENEOUS MODELS WITH EXPONENTIAL LOSS

  • For smooth homogeneous models with exponential loss, the gradient-descent proof discretizes the gradient-flow analysis and introduces a smoother normalized margin to control second-order discretization errors.The original margin becomes less smooth as ρ → +∞, while the new margin increases slightly more slowly to cancel the discretization error.Source: E GRADIENT DESCENT: SMOOTH HOMOGENEOUS… · p. 29

E.1 ASSUMPTIONS

  • The gradient-descent extension assumes C2 smoothness away from zero, homogeneity, exponential loss, separability, and a learning rate controlled by local loss-dependent smoothness.A constant learning rate satisfies the condition when η0 is sufficiently small, while the analysis uses a non-decreasing factor µ(x) = o(1).Source: §E.1 · p. 30

E.2 SMOOTHED NORMALIZED MARGIN

  • The smoothed normalized margin ˆγ is constructed through φ so it is well-defined below the initial loss threshold and has controlled relations to the original normalized margins.The construction proves existence of the defining integral and establishes the required limiting properties as L(θ_m) → 0.Source: §E.2 · pp. 30–31

E.3 THEOREMS … E.6 PROOF FOR THEOREM E.5

The theorems establish normalized-margin monotonicity, convergence toward KKT points, and quantitative KKT-time guarantees under the stated assumptions. Their proofs show loss vanishing and weight divergence, while refined analysis yields tight training-loss rates.

E.3 THEOREMS

  • Theorem E.2 shows that after t0, the smoothed normalized margin increases unless the normalized parameters remain unchanged.This theorem is proved under assumptions (S1), (A2)–(A4), and (S5).Source: §E.3 · p. 32
  • For every ϵ, δ > 0, gradient descent reaches an (ϵ, δ)-KKT point within a window with r = Θ(log δ−1) and ∆ = Θ(ϵ−2) in log ρ.The point is θ/q_min(θ)^(1/L) at some time t* satisfying log ρ(t*) ∈ (r, r + ∆).Source: §E.3 · p. 32
  • Theorem E.5 provides tight convergence rates for both training loss and weight norm under assumptions (S1), (A2)–(A4), and (S5).The proof bounds one-step loss changes and combines upper and lower estimates on E(L(t)) to obtain the tight loss rate.Source: §E.3 · p. 32, §E.6 · p. 38

E.4 PROOF FOR THEOREM E.2

  • Theorem E.2 is proved by interpolating each gradient-descent step and inductively maintaining bounds on margin, weight growth, loss decrease, and margin monotonicity.Corollary E.6 supplies the relation ⟨θ(t), −∇L(t)⟩ = Lν(t), which supports the induction and positivity of ν(t) while L(t) < 1.Source: §E.4 · pp. 32–33
  • Gradient descent drives training loss to 0 and the weight norm ρ to +∞, while the normalized margin and smoothed margin asymptotically coincide.The proof derives loss decay from gradient and decrement bounds, then uses Lemma E.1 to obtain |γ̄ − γ̂| → 0.Source: §E.4 · pp. 35–36

E.5 PROOF FOR THEOREM E.3 AND E.4

  • The argument for convergence to KKT points requires L →0 and β →1, with L →0 following from Theorem E.2; Theorem E.4 permits o(1) additive errors in log ρ.Source: §E.5 · p. 36

E.6 PROOF FOR THEOREM E.5

  • The refined analysis proves the weight-loss relation ρ^L = Θ(log 1/L) and reduces the loss-rate result to showing E(L(t)) = Θ(T).Here T = Σ_{τ=t0}^{t−1} η(τ), and the resulting rate is L(t) = Θ(1/T (log T)^(2−2/L)).Source: §E.3 · p. 32, §E.6 · p. 38

F GRADIENT DESCENT: GENERAL LOSS FUNCTIONS

The analysis extends beyond the original loss class by imposing stronger second-order conditions on losses represented as ℓ(q)=e^−f(q). Under these assumptions, the paper preserves key gradient bounds and derives tight training-loss and weight-norm rates.

Assumptions

  • General losses are handled by replacing (B3) with (S3), requiring ℓ(q)=e^−f(q), C2 smoothness, positive f′, controlled growth, and an inverse-function condition.Exponential and logistic losses satisfy (S3).Source: F GRADIENT DESCENT: GENERAL LOSS… · p. 38
  • Lemma F.1 shows that (S3.4) implies (B3.4), with bg=max{2f(bf),f(2bf)} and K=2p.The resulting bounds control the scaling of g′ and f′ across comparable arguments.Source: F GRADIENT DESCENT: GENERAL LOSS… · p. 38

Generalized quantities

  • The framework redefines κ(x), λ(x), φ(x), Cη, and H(x) so the previous analysis applies to general losses while retaining analogous gradient and Hessian bounds.The new definitions ensure κ(x) is well-defined and support the construction of ˆγ(θ).Source: F GRADIENT DESCENT: GENERAL LOSS… · pp. 38–39

Convergence rates

  • Under (S1), (A2), (S3), (A4), and (S5), Theorem F.4 establishes tight rates for training loss and weight norm.The proof transfers the earlier gradient-flow and descent arguments using the generalized bounds.Source: F GRADIENT DESCENT: GENERAL LOSS… · p. 40

G EXTENSION: MULTI-CLASS CLASSIFICATION

This section extends the margin-regularization analysis to multi-class classification with cross-entropy loss. Under homogeneous-network and separability assumptions, the main gradient-flow results and smoothed-margin lemma continue to hold, with gradient descent requiring adjusted smoothness and learning-rate conditions.

Multi-class formulation

  • The extension models each input with C outputs and defines margins using the correct-class output minus the largest incorrect-class output.The dataset labels lie in [C], and the pointwise margin is q_n(θ) := Φ_y_n(θ; x_n) − max_j≠y_n Φ_j(θ; x_n).Source: G EXTENSION: MULTI-CLASS CLASSIFICATION · p. 40

Gradient flow

  • The multi-class gradient-flow assumptions require locally Lipschitz, chain-rule-compatible outputs, positive homogeneity, cross-entropy loss, and eventual low-loss separability.These conditions are stated as (M1)–(M4), with homogeneity degree L and the threshold L(t0) < log 2.Source: G EXTENSION: MULTI-CLASS CLASSIFICATION · pp. 40–41

Assumptions

  • Cross-entropy training becomes separable once the loss falls below log 2, because every correct-class logit gap s_nj is then positive.The condition L(t0) < log 2 is assumed explicitly and implies s_nj > 0 for every example and incorrect class.Source: G EXTENSION: MULTI-CLASS CLASSIFICATION · p. 41

Gradient flow

  • The multi-class extension preserves Theorem 4.1, Theorem 4.4, and the corresponding smoothed normalized-margin result for cross-entropy loss.The optimization problem is redefined for the cross-entropy setting, while the proof of the generalized smoothed-margin lemma follows the earlier argument.Source: G EXTENSION: MULTI-CLASS CLASSIFICATION · p. 41

Gradient descent

  • For gradient descent, the extension replaces local regularity with C2 smoothness and adds a learning-rate condition, while adapting the technical bounds to the multi-class setting.The proof redefines the constants used in the earlier analysis and uses log-sum-exp properties to bound the smoothed margins and their first and second derivatives.Source: G EXTENSION: MULTI-CLASS CLASSIFICATION · pp. 41–42

H EXTENSION: MULTI-HOMOGENEOUS MODELS · I CHAIN RULES FOR NON-DIFFERENTIABLE FUNCTIONS

The paper extends its margin-growth analysis to multi-homogeneous models by separating the norms of homogeneous parameter blocks, and explains the chain-rule conditions needed for gradient-flow arguments with non-differentiable losses. It shows that the relevant monotonicity results persist under these extensions and identifies broad function classes where the required chain rule holds.

H EXTENSION: MULTI-HOMOGENEOUS MODELS

  • The multi-homogeneous extension separates the norm of each homogeneous parameter block and proves the results for gradient flow, with gradient descent following by the same argument.Only a small part of the homogeneous-model proof changes.Source: H EXTENSION: MULTI-HOMOGENEOUS MODELS · p. 42
  • For multi-homogeneous models, the smoothed normalized margin is reformulated using each block’s norm ρ_i and normalized parameter ˆw_i.The model is assumed to be (k_1, . . . , k_m)-homogeneous.Source: H EXTENSION: MULTI-HOMOGENEOUS MODELS · p. 42
  • After a threshold time t_0, every parameter-block norm grows logarithmically and the smoothed normalized margin is nondecreasing along the multi-homogeneous gradient flow.The generalized lemma establishes d/dt log ρ_i > 0 for all blocks and d/dt log ˜γ ≥ 0 for t > t_0.Source: H EXTENSION: MULTI-HOMOGENEOUS MODELS · p. 42
  • For cross-entropy loss, the same multi-homogeneous monotonicity lemma holds after replacing the smoothed normalized margin with the cross-entropy-specific definition.The proof changes only in the bound corresponding to Lemma B.5; the remaining steps are unchanged.Source: H EXTENSION: MULTI-HOMOGENEOUS MODELS · p. 43

I CHAIN RULES FOR NON-DIFFERENTIABLE FUNCTIONS

  • Clarke’s subdifferential gives a chain-rule inclusion for locally Lipschitz non-differentiable functions, so the usual exact loss-decrease identity along gradient flow need not hold.For differentiable losses, the ordinary chain rule directly shows that the loss decreases along gradient flow.Source: I CHAIN RULES FOR NON-DIFFERENTIABLE… · pp. 43–44
  • The analysis therefore restricts attention to locally Lipschitz functions that admit a chain rule along every arc, for which a generalized gradient-flow loss-decrease identity holds almost everywhere.This framework follows Davis et al. (2020) and Drusvyatskiy et al. (2015).Source: I CHAIN RULES FOR NON-DIFFERENTIABLE… · p. 44
  • Chain-rule-admitting functions include C1-smooth, subdifferentiably regular, Whitney C1-stratifiable, semi-algebraic, semianalytic, and o-minimally definable functions, and the class is closed under composition.The composition theorem establishes that composing locally Lipschitz chain-rule functions preserves the property.Source: I CHAIN RULES FOR NON-DIFFERENTIABLE… · p. 44

J MEXICAN HAT · K EXPERIMENTS · K.1 EVALUATION FOR NORMALIZED MARGIN

The paper constructs a homogeneous Mexican Hat example where gradient flow fails to converge directionally, then experimentally finds increasing normalized margins on MNIST and CIFAR-10, while test accuracy changes little despite prolonged training.

J MEXICAN HAT

  • The example demonstrates that gradient flow need not converge in direction even for C∞-smooth homogeneous models.The original Mexican Hat function is not homogeneous, so the paper modifies it before establishing the directional nonconvergence result.Source: J MEXICAN HAT · p. 45
  • Under 0 < r < 1 and ϕ = 1/(1−r^2) initially, normalized parameters do not converge; their limit points form the circle {(x, y, z) ∈ S^2 : x^2 + y^2 = 1, z = 0}.The construction adds an extra variable and normalizes parameters to make the Mexican Hat example homogeneous.Source: J MEXICAN HAT · p. 45

K EXPERIMENTS

  • The experiments train a standard biased 4-layer MNIST CNN and a version retaining only first-layer biases, using bias removal to obtain homogeneity in parameters.Both models use SGD with batch size 100, no momentum, He-normal weight initialization, and images normalized to [0, 1].Source: K EXPERIMENTS · pp. 46–47

K.1 EVALUATION FOR NORMALIZED MARGIN

  • The normalized margin is defined for the bias-free CNN as margin divided by the product of layer-weight L2 norms, while the smoothed version is used for the biased CNN.For the original normalized-margin plots, non-first-layer biases are ignored when computing layer norms.Source: §K.1 · p. 47
  • Loss-based learning-rate scheduling makes training loss decrease exponentially faster than constant-rate SGD and produces rapid normalized-margin growth, whereas constant-rate margin growth is slow.The scheduled runs can reach training loss as small as 10^-800, requiring re-parameterization and numerical tricks.Source: §K.1 · p. 48
  • On MNIST and CIFAR-10, normalized margins increase after fitting for CNNs and VGGNets with and without bias, under constant or loss-based learning-rate schedules.The MNIST results are shown in Figures 3–4, while the CIFAR-10 experiments use a modified VGGNet-16 and are shown in Figures 5–6.Source: Figure 3 · p. 47, Figure 4 · p. 47, §K.1 · p. 48
  • After 10,000 epochs of loss-based scheduling, test accuracy changes only slightly on MNIST and CIFAR-10 even though normalized margin increases substantially.The paper identifies this as a gap between margin-based generalization bounds and observed generalization error.Source: §K.1 · p. 49, Figure 7 · p. 49

K.2 EVALUATION FOR ROBUSTNESS … L.2 ADDRESSING NUMERICAL ISSUES

Longer training with loss-based learning rates improves L2 robustness on both training and test sets, while the paper details adaptive scheduling and numerically stable optimization for extremely small losses. The robustness gains are theoretically linked to normalized margin growth, though changing Lipschitz constants limit their matching rates.

K.2 EVALUATION FOR ROBUSTNESS

  • Normalized margin lower-bounds L2 robustness when it is β-Lipschitz, explaining why longer training can improve training-set robustness in homogeneous models.For correctly classified points, Rθ(z) ≥ q ˆθ(z)/β; normalized margin and margin share the same sign.Source: §K.2 · p. 49
  • Training longer consistently improves L2 robust accuracy on both training and test sets, with model-5 significantly outperforming model-1 despite marginal gains over later models at large perturbations.Figure 8 reports increasing robust-accuracy order from model-1 through model-4, while model-5’s improvement over model-1 remains significant.Source: Figure 8 · p. 50, §K.2 · pp. 50–51
  • The normalized-margin and robustness curves remain stable across evaluation hyperparameters, but their growth rates differ because the local Lipschitz constant may change during training.The paper suggests combining longer training with Lipschitz-constraining techniques as future work.Source: §K.2 · p. 51

L ADDITIONAL EXPERIMENTAL DETAILS

  • The additional experimental details document the procedures and numerical safeguards used to support the robustness experiments and training schedule.Robustness is evaluated with the standard Carlini–Wagner method using default hyperparameters.Source: §K.2 · p. 50, L ADDITIONAL EXPERIMENTAL DETAILS · p. 51

L.1 LOSS-BASED LEARNING RATE SCHEDULING

  • The schedule is motivated by the observation that, at perfect training accuracy, cross-entropy Hessian smoothness scales as O(¯L·poly(ρ)), suggesting learning rates near the inverse smoothness.The relative learning rate α is tuned while the loss supplies the scale for η(t).Source: §L.1 · p. 51
  • The loss-based learning-rate schedule adapts each epoch by increasing α when training loss decreases and reducing it otherwise, implementing a line-search variant.The schedule uses η(t) = α(t)/L(t −1), with α(0) = 0.1, ru ≈ 1.149, and rd ≈ 1.072.Source: §L.1 · p. 51

L.2 ADDRESSING NUMERICAL ISSUES

  • For losses as small as 10^-800, the implementation evaluates a relative loss using stable log-sum-exp and Taylor approximations, avoiding underflow and overflow.When q_n > Q, the approximation introduces relative error O(Ce^-Q); otherwise, the loss is computed directly with stable log1p.Source: §L.2 · pp. 51–52
  • Gradient descent on the relative loss remains equivalent after rescaling the learning rate, and the chosen scale keeps α(t) between 10^-9 and 100 for stable backward passes.The implementation sets eF(t) to the previous epoch’s log loss and maintains current log loss by adding log R(t).Source: §L.2 · p. 52

Related papers

Loading 1906.05890v4…