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

The paper asks why gradient-based training favors particular solutions in homogeneous neural networks. It analyzes gradient descent and gradient flow through normalized margins and a max-margin formulation, showing monotone smoothed margins and convergence toward KKT points, with potential robustness benefits from longer training.

  • Problem

    The paper addresses the open question of why gradient descent or its variants are biased toward solutions with good test-set generalization, extending the question beyond linear classifiers.

  • Method

    The paper analyzes gradient descent and gradient flow for homogeneous neural networks under exponential-tail losses, using normalized margins, a smoothed margin, and a constrained max-margin problem.

  • Results

    The smoothed normalized margin is asymptotically equivalent to the normalized margin and non-decreasing after a small-loss threshold, while parameter-direction limit points satisfy KKT conditions for the max-margin problem.

  • Takeaways & Limitations

    The results indicate that gradient descent and gradient flow implicitly perform margin maximization in deep homogeneous networks, and longer training may improve robustness.

  • Takeaways & Limitations

    The convergence guarantee is to KKT points rather than globally optimal margins because the deep-network max-margin problem can be highly non-convex.

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 favors particular solutions and extends implicit-bias analysis from linear models to homogeneous neural networks. It shows that normalized margins increase asymptotically, converge toward KKT points of a max-margin problem, and may improve robustness with longer training.

  • Gradient descent on separable linear logistic regression converges in direction to the L2-margin-maximizing solution while the weight norm diverges.
  • Homogeneous networks satisfy Φ(cθ; x) = c^LΦ(θ; x), including bias-free deep fully-connected and convolutional networks with ReLU or LeakyReLU activations.For these networks, the order L equals the number of layers.
  • The theory assumes an exponential-tail loss and that training reaches a sufficiently small threshold guaranteeing 100% training accuracy.The covered losses include exponential, logistic, and cross-entropy loss; for logistic and cross-entropy loss, the threshold can be set to ln 2.
  • A smoothed normalized margin becomes non-decreasing after the loss crosses the threshold and converges to the normalized margin asymptotically.Specifically, |˜γ − γ̄| → 0 as t →∞ while ˜γ is non-decreasing for t > t0.
  • Every limit point of the normalized parameter direction lies along a KKT point of a natural max-margin problem, indicating implicit margin maximization.The result applies to gradient descent or gradient flow under the paper’s homogeneous-model setting.
  • O(1/(t(log t)^(2−2/L))) loss decay and O((log t)^(1/L)) weight growth extend linear-network asymptotics to homogeneous neural networks.
  • Training longer can enlarge normalized margins, while experiments report noticeable L2-robustness improvements on both training and test sets.The normalized margin provides a lower bound for L2-robustness on fully connected ReLU networks after division by a Lipschitz constant.

2 RELATED WORK

Prior work established implicit max-margin bias for linear and some deep linear models, while this paper broadens the analysis to homogeneous nonlinear and potentially non-smooth networks under weaker assumptions.

  • Prior results show full-batch and stochastic gradient methods converge toward max-margin directions for separable linear logistic regression.
  • Deep linear-network results characterize convergence of the product of weights toward the max L2-margin direction, with related analyses covering linear convolutional networks.
  • Earlier studies also examined margin maximization for boosting and the Normalized Perceptron, alongside implicit bias in single-layer or single-unit ReLU models.
  • Compared with Nacson et al., this paper requires only a small loss threshold rather than loss convergence to zero and proves KKT conditions for all parameter-direction limit points.It also avoids assumptions on loss-direction convergence and LICQ, while establishing normalized-margin monotonicity and tight loss rates.
  • The analysis covers gradient descent for smooth homogeneous models and gradient flow for homogeneous models that may be non-smooth, including ReLU networks.

3 PRELIMINARIES

The preliminaries define the norms, smoothness and local regularity used in the analysis, then specify binary classification, discrete gradient descent, and generalized gradient flow for possibly non-smooth losses.

  • The paper uses the L2 norm ∥v∥2, natural-number indexing [N], base-e logarithms, and standard gradient, smoothness, and local-Lipschitz notation.
  • For locally Lipschitz functions, the Clarke subdifferential is a convex generalized derivative, and the analysis uses its chain-rule behavior along absolutely continuous arcs.
  • Binary classification uses a scalar network output Φ(θ; x), predicts by sign, and defines training data as labeled pairs (x_n, y_n) with y_n ∈ {±1}.
  • Discrete gradient descent updates parameters as θ(t+1) = θ(t) − η(t)∇L(θ(t)) under a C2-smooth training loss.
  • The paper’s non-smooth framework permits gradient-flow analysis without assuming differentiability, while gradient descent retains a smoothness requirement.
  • Gradient flow treats training as infinitesimal-step descent and uses a continuous parameter trajectory satisfying a differential inclusion with Clarke’s subdifferential.For C1-smooth losses, the inclusion reduces to the usual differential equation.

4 GRADIENT DESCENT / GRADIENT FLOW ON HOMOGENEOUS MODEL

Under regularity, homogeneity, exponential-type loss, separability, and—for gradient descent—smoothness and a sufficiently small constant learning rate, the paper analyzes normalized-margin dynamics after the training loss becomes small. It proves monotonicity of smoothed margins, convergence toward KKT points of a margin-related problem, and extensions across losses, classification settings, and multi-homogeneous models.

  • Assumptions: The analysis assumes network regularity, positive homogeneity, an exponential-type loss, and separability; gradient descent additionally requires smoothness and a sufficiently small constant learning rate.The separability condition requires training loss below a threshold, ensuring every training example is classified correctly.
  • Normalized margin: The normalized margin compares directions by dividing the dataset margin by the parameter norm raised to the homogeneity order.The unnormalized margin scales with parameter magnitude, so normalization isolates directional effects.
  • Gradient flow: For gradient flow, a smoothed normalized margin is non-decreasing after the loss falls below the threshold, up to stationary-direction cases.The smoothed quantity is an O(∥θ∥^-L/2)-additive approximation of the normalized margin.
  • Gradient descent: For gradient descent, a multiplicative approximation of the normalized margin either increases each step or the normalized parameter direction remains unchanged.The paper also derives convergence behavior in which training loss tends to zero and parameter norm tends to infinity.
  • Convergence and optimality: Normalized margins and their smoothed approximations converge to the same value, while normalized parameter limit points satisfy KKT conditions for the margin-related constrained problem.The constrained problem is equivalent to maximizing normalized margin over directions, but deep-network constraints can be highly non-convex.
  • Extensions: The results extend to logistic and other exponential-tail losses, multi-class cross-entropy, and multi-homogeneous models; limit directions can correspond to max-margin solutions for an NTK hard-margin SVM.For gradient flow, the broader loss results continue to hold, with analogous gradient-descent extensions.

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

The proof sketch decomposes parameter dynamics into radial and tangential components, showing that the smoothed normalized margin increases once the loss is sufficiently small. This monotonicity supports convergence of the loss, parameter norm, and normalized margin.

  • Key proof lemma: Lemma 5.1 relates smoothed-margin growth to the radial and tangential velocity components of the parameters.The proof uses chain rules and Euler’s theorem for homogeneous functions.
  • Key proof lemma: For almost every t > t0, the parameter norm grows and the smoothed normalized margin has nonnegative logarithmic growth.Specifically, d/dt log ρ > 0 and d/dt log ˜γ ≥ L.
  • Consequences: The first theorem claims follow directly from Lemma 5.1, while loss convergence and parameter divergence follow from margin monotonicity and gradient lower bounds.As L → 0, the parameter norm satisfies ρ → +∞, and ˜γ approximates the normalized margin up to O(ρ^-L).
  • KKT convergence: Reparameterizing time by log ρ reveals times when directional velocity is small, enabling identification of approximate KKT points.Convergent subsequences of normalized parameters can then be related to KKT points through an approximation theorem.
  • Proof mechanics: The proof derives closed-form relations for relevant quantities by repeatedly applying the chain rule and Euler’s theorem.The displayed derivation separates radial motion from directional motion.

6 DISCUSSION AND FUTURE DIRECTIONS

The discussion extends the framework to broader losses and states the main theoretical contribution: normalized margins increase and converge to KKT points under minimal assumptions. It also identifies unresolved extensions to nonsmooth models, stronger optimality guarantees, and biased networks.

  • Main contribution: The paper proves that gradient flow and gradient descent increase normalized margins and converge directionally to KKT points of a natural max-margin problem.The result is established under a minimal set of assumptions for homogeneous neural networks.
  • Future directions: Open directions include nonsmooth gradient descent, stronger structural assumptions yielding local or global optimality, and rigorous treatment of bias terms.The nonsmooth case lacks a known loss-decrement inequality of the smooth-case form.
  • Losses and assumptions: The loss framework includes exponential, logistic, and other losses with exponential tails.Examples include ℓ(q) = e^-q3 and ℓ(q) = log(1 + e^-q3).
  • Losses and assumptions: The analysis assumes local Lipschitz regularity with a chain rule, positive homogeneity, exponential-type loss behavior, and eventual training-data separability.For logistic loss, the separability threshold can be set to log 2.
  • Losses and assumptions: The technical loss assumption B3.4 enables asymptotic comparison of loss and gradient scales at different data points and is satisfied by several example losses.The paper notes that weaker assumptions may be possible but uses B3.4 for simplicity.
  • Smoothed margin: The smoothed normalized margin approximates the ordinary normalized margin, with an O(ρ^-L) additive error for exponential loss and sufficiently small logistic-loss values.For sequences with loss tending to zero, the two margins converge to the same value.

A.3 THEOREMS

The theorems establish monotonicity of the smoothed margin, directional convergence to KKT points, finite-time approximate KKT behavior, and quantitative convergence rates under the stated assumptions.

  • Monotonicity: Under the regularity, homogeneity, loss, and separability assumptions, the smoothed normalized margin is nondecreasing after the threshold time.The theorem states an almost-everywhere monotonicity alternative for the margin dynamics.
  • Directional convergence: Every limit point of the normalized parameter direction is aligned with a KKT point of the natural max-margin problem.This is the infinite-time directional convergence result for gradient flow.
  • Finite-time approximation: For any ϵ, δ > 0, gradient flow reaches an (ϵ, δ)-KKT point within a log-parameter-norm window of width Θ(ϵ^-2).The window begins at r = Θ(log δ^-1).
  • Convergence rates: A refined analysis provides tight rates for loss convergence and parameter-norm growth.The paper gives a corresponding corollary for exponential and logistic losses.

B.1 PROOF FOR PROPOSITION 1 AND 2

The proof uses homogeneous-function identities and nonsmooth chain rules to control parameter growth and margin dynamics, then converts small directional motion into approximate KKT conditions. Loss convergence establishes the limiting approximation between smoothed and ordinary margins.

  • Margin dynamics: The key differential inequalities give d/dt log ρ > 0 and d/dt log ˜γ ≥ L after t0.These inequalities drive monotonicity and subsequent convergence arguments.
  • Homogeneous identities: Euler’s theorem extends to locally Lipschitz homogeneous functions through Clarke’s subdifferential and provides the key radial identity.This permits the proof to handle nonsmooth homogeneous networks.
  • Parameter growth: The proof derives an exact parameter-growth formula using the homogeneous-network identity and chain rules.The resulting relation is used to establish positive radial growth after the threshold time.
  • Margin dynamics: Because the loss is non-increasing and below the threshold, the smoothed margin remains well-defined and positive throughout the analyzed trajectory.The threshold ensures the inverse loss transformation stays in its domain.
  • Asymptotic behavior: Integrating the growth inequalities forces the loss toward zero and the parameter norm toward infinity.Loss convergence then implies that smoothed and ordinary normalized margins have vanishing difference.
  • KKT construction: Normalizing parameters by qmin(θ)^(1/L) produces approximate KKT points, with the approximation improving as the loss decreases and the margin is monotone.The construction uses subgradients of the individual margins and associated multipliers.

C.6 PROOF FOR COROLLARY 4.5

The proof connects KKT points of the margin problem to kernel-SVM max-margin directions, then derives asymptotic bounds for loss and weight growth under gradient-flow and gradient-descent analyses.

  • KKT and kernel-SVM characterization: KKT points of (P) determine max-margin directions for the kernel-SVM problem (Q).Every limit point is along a KKT point of (P), and therefore along a max-margin direction of (Q).
  • KKT and kernel-SVM characterization: For smooth models, the kernel uses gradients, while for non-smooth models it uses selected Clarke subgradients.The resulting kernel is an inner product of the corresponding feature derivatives or subgradients.
  • Auxiliary growth bounds: The auxiliary functions f and g grow at most polynomially because their logarithmic derivatives are Θ(1/x).This yields log f(x) = Θ(log x) and log g(x) = Θ(log x).
  • Gradient-descent analysis: Under the stated assumptions, the loss and weight-growth analysis reduces to bounding the loss through G and G^-1, then translating those bounds into bounds on ρ.The proof first bounds L, derives ρ in terms of L, and finally obtains time-dependent bounds.
  • Gradient-descent analysis: Gradient-descent discretization requires a smoother normalized margin because the original smoothed margin becomes less smooth as the weight norm diverges.The alternative margin is designed to grow slightly more slowly, offsetting discretization error.

E.3 THEOREMS

The theorems establish monotonicity of a smoother normalized margin during gradient descent and characterize convergence toward KKT points, while also proving loss and weight-growth behavior.

  • KKT convergence: Every gradient-flow limit point lies along a KKT direction of the constrained margin problem.The corresponding theorem is stated for gradient flow under (S1), (A2)–(A4), and (S5).
  • KKT convergence: For any ϵ, δ > 0, gradient descent reaches an (ϵ, δ)-KKT point within a window of width ∆ = Θ(ϵ^-2) in log weight norm.The window begins at r = Θ(log δ^-1).
  • Rates: The paper also derives tight convergence rates for training loss and weight norm under the same assumptions.These rates are stated in Theorem E.5.
  • Monotonicity: The original normalized margin approaches the smoother margin as training loss tends to zero and the weight norm diverges.The proof derives L(t) → 0 and ρ(t) → +∞, then applies the asymptotic relationship between the margins.

F GRADIENT DESCENT: GENERAL LOSS FUNCTIONS

The analysis extends gradient-descent guarantees beyond exponential loss by imposing stronger smoothness and growth conditions on a general loss representation.

  • Assumptions: General losses are handled by replacing the earlier loss assumption with a stronger condition involving second-order derivatives.The paper states that this condition is needed to extend the results to other loss functions.
  • Assumptions: The generalized loss is written as ℓ(q) = e^-f(q), with f satisfying smoothness, positivity, growth, and inverse-function conditions.These assumptions include f being C2-smooth and f′(q)q → +∞ as q → +∞.
  • Assumption reduction: The new assumptions imply the earlier derivative-growth condition with bg = max{2f(bf), f(2bf)} and K = 2p.This implication enables reuse of the previous proof framework.
  • Proof extension: The paper redefines κ, λ, φ, Cη, and H to obtain analogous bounds for ν(t), ∥∇L∥2, and ∥∇2L∥2.With these bounds, the gradient-descent monotonicity and convergence theorems follow by the same argument.
  • Results: The generalized analysis yields tight rates for training loss and weight norm under the modified assumptions.These rates are stated in Theorem F.4.

G EXTENSION: MULTI-CLASS CLASSIFICATION

The paper extends its margin analysis to multi-class classification with cross-entropy loss by redefining margins and adapting the gradient bounds and smoothness conditions.

  • Setup: The multi-class extension uses cross-entropy loss and assumes that the loss falls below log 2 to ensure separability.Under this condition, every pairwise margin against an incorrect class is positive.
  • Setup: For each example, the margin is represented through the correct-class output relative to competing class outputs.The multi-class network produces a vector of C outputs, and pairwise score differences define the relevant margins.
  • Margin analysis: The smoothed normalized margin is redefined for cross-entropy, and the associated constrained optimization problem is redefined accordingly.The paper states that Theorems 4.1 and 4.4 continue to hold under these definitions.
  • Proof adaptation: The key gradient lower bound used in the binary analysis continues to hold for the multi-class smoothed margin.The proof compares pairwise multi-class margins with the minimum margin and applies the corresponding loss bound.
  • Gradient descent: For gradient descent, the extension requires C2 smoothness of each output and the same learning-rate condition adapted to the multi-class setting.The analysis also redefines constants used to bound the multi-class margin and its derivatives.

H EXTENSION: MULTI-HOMOGENEOUS MODELS

The paper extends its analysis to multi-homogeneous models by separating the norms of distinct homogeneous parameter parts. Its non-smooth analysis relies on chain-rule conditions that preserve the gradient-flow loss-decrease argument.

  • Multi-homogeneous extension: For multi-homogeneous models, the proof separates the norm of each homogeneous parameter part instead of treating all parameters as one whole.The same argument is then applied primarily to gradient flow, with extension to gradient descent described as straightforward.
  • Smoothed normalized margin: The smoothed normalized margin is defined for multi-homogeneous models and can be rewritten using each part’s norm and normalized direction.The construction is presented for general losses satisfying the stated conditions and separately for cross-entropy.
  • Monotonicity: For all t > t0, the analysis establishes positive growth of each parameter-part norm and nonnegative growth of the smoothed normalized margin.These properties are expressed through derivatives of log ρ_i and log ˜γ.
  • Non-smooth analysis: The non-smooth extension uses functions admitting chain rules, because ordinary loss-decrease identities need not hold for arbitrary locally Lipschitz non-differentiable functions.The admissible class includes C1-smooth, subdifferentiably regular, Whitney C1-stratifiable, semi-algebraic, semianalytic, and definable functions.
  • Non-smooth analysis: The chain-rule class is closed under composition, allowing the paper to derive a chain rule for compositions from the component functions’ chain rules.The result applies to locally Lipschitz component functions and holds along arcs almost everywhere.

J MEXICAN HAT

The Mexican Hat construction provides a smooth homogeneous example whose normalized parameter direction fails to converge, while experiments examine normalized-margin growth on MNIST and CIFAR-10. The experiments report continued margin growth after fitting, with faster growth under loss-based scheduling and little later change in test accuracy.

  • J MEXICAN HAT: A C∞-smooth homogeneous construction based on the Mexican Hat function shows that gradient flow need not converge in parameter direction.The construction normalizes the input variables before evaluating the Mexican Hat function and multiplies by a homogeneous radial factor.
  • J MEXICAN HAT: Under the specified initial condition, the normalized parameter trajectory has limit points forming a circle on the unit sphere.The limit set is {(x, y, z) ∈ S2 : x2 + y2 = 1, z = 0}.
  • J MEXICAN HAT: The example reaches radius r → 1 while its angular coordinate continues circling, demonstrating nonconvergence despite smoothness and homogeneity.The proof tracks radial and angular dynamics, with the polar angle tending to infinity.
  • K.1 EVALUATION FOR NORMALIZED MARGIN: With loss-based learning-rate scheduling, MNIST training accuracy reaches 100% after about 20 epochs and the original normalized margin increases rapidly after fitting.The accompanying plot also tracks the relative learning rate α(t).
  • K.1 EVALUATION FOR NORMALIZED MARGIN: On MNIST, both CNNs fit the training set after about 100 epochs with constant-rate SGD, after which their normalized margins continue increasing slowly.The comparison includes models with and without bias, trained with learning rate 0.01.
  • K.1 EVALUATION FOR NORMALIZED MARGIN: On CIFAR-10, experiments with modified VGGNet models report that the normalized margin increases over time, while extended scheduled training changes test accuracy only slightly.The test-accuracy observation is reported for 10,000 training epochs across MNIST and CIFAR-10 experiments.

K.2 EVALUATION FOR ROBUSTNESS

The experiments evaluate whether longer training improves L2-robustness through larger normalized margins on CNNs without bias. Robust accuracy generally improves across training checkpoints, although gains can become marginal at larger perturbation radii and normalized margin and robustness do not grow at the same rate.

  • Margin–robustness connection: Normalized margin provides a theoretical lower bound on L2-robustness, but the two quantities increase at different rates in these experiments.The authors suggest that a changing local Lipschitz constant may explain the differing growth rates and identify Lipschitz constraints as future work.
  • Robustness results: Longer training improved L2-robust accuracy on both the training and test sets, especially relative to the earliest checkpoint.For model-1 through model-4, robust accuracy increases noticeably; model-5 remains significantly better than model-1.
  • Training-set evaluation: For small perturbation radii, training-set robust accuracy follows model-1 through model-5, while larger radii reduce the additional benefit of model-5 over models 2–4.The improvement of model-5 over model-1 remains significant across the reported radii.
  • Test-set evaluation: On the test set, model-1 through model-5 are nearly indistinguishable for ϵ < 0.2, but longer training improves their ordering for larger ϵ.Misclassified test samples are assigned robustness 0 in this evaluation.
  • Evaluation stability: The robustness curves retain stable shapes and relative positions across different evaluation hyperparameter settings.The tested variations included learning rates and binary-search steps.
Loading 1906.05890v4…