PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence of Gradient Descent on Separable Data

Mor Shpigel Nacson, Jason D. Lee, Suriya Gunasekar, Pedro H. P. Savarese, Nathan Srebro, Daniel Soudry

arXiv:1803.01905v3stat.MLcs.LG

TL;DR

The paper asks when gradient descent on separable data converges to the L2 maximum-margin separator and how loss tails and step sizes affect margin convergence. It analyzes general monotone-tail losses across linear networks, showing broad convergence results, optimal fixed-step behavior for exponential tails, and faster convergence with normalized updates.

  • Problem

    The role of loss-tail shape in maximum-margin convergence and margin-convergence rates remains unclear beyond tight exponential-tailed losses.

  • Method

    The paper analyzes gradient descent on separable linear models and fully connected linear networks under different loss tails and fixed or variable step sizes.

  • Results

    Super-polynomial-tailed losses converge toward the L2 maximum-margin solution across linear-network depths, exponential tails have the optimal fixed-step margin rate, and normalized updates achieve O(log(t)/√t) instead of 1/log(t).

  • Takeaways & Limitations

    Exponential-tailed losses combine maximum-margin convergence with the best fixed-step rate analyzed, while aggressive normalized updates can substantially accelerate exponential-loss convergence.

  • Takeaways & Limitations

    The results exclude polynomially tailed losses in general, and normalized GD remains below state-of-the-art Wide ResNet performance because weight decay and momentum are outside the paper's scope.

Abstract

from arXiv · show

We provide a detailed study on the implicit bias of gradient descent when optimizing loss functions with strictly monotone tails, such as the logistic loss, over separable datasets. We look at two basic questions: (a) what are the conditions on the tail of the loss function under which gradient descent converges in the direction of the $L_2$ maximum-margin separator? (b) how does the rate of margin convergence depend on the tail of the loss function and the choice of the step size? We show that for a large family of super-polynomial tailed losses, gradient descent iterates on linear networks of any depth converge in the direction of $L_2$ maximum-margin solution, while this does not hold for losses with heavier tails. Within this family, for simple linear models we show that the optimal rates with fixed step size is indeed obtained for the commonly used exponentially tailed losses such as logistic loss. However, with a fixed step size the optimal convergence rate is extremely slow as $1/\log(t)$, as also proved in Soudry et al. (2018). For linear models with exponential loss, we further prove that the convergence rate could be improved to $\log (t) /\sqrt{t}$ by using aggressive step sizes that compensates for the rapidly vanishing gradients. Numerical results suggest this method might be useful for deep networks.

1 INTRODUCTION

The paper studies how gradient descent's implicit bias depends on loss tails and step sizes for separable data, extending maximum-margin convergence beyond tight exponential losses. It also examines convergence rates, deep linear networks, and normalized updates.

  • Motivation: Gradient descent can select different models among multiple global optima, making optimization-induced implicit bias relevant to generalization in high-capacity models.This issue is especially prominent in deep learning, where explicit regularization and capacity restrictions may not sufficiently determine inductive bias.
  • Open questions: Prior analyses established maximum-margin convergence for tight exponential-tailed losses but left the role of tail shape and convergence acceleration unresolved.The paper explicitly asks whether other monotone losses converge to the same separator and how their tails affect the rate.
  • Main contributions: The paper shows convergence to the L2 maximum-margin solution for super-polynomial tails, but not generally for (sub)polynomial tails.This identifies a broader sufficient family than tight exponential tails while distinguishing heavier-tailed losses.
  • Main contributions: Exponential-tailed losses, including logistic loss, achieve the optimal fixed-step-size margin convergence rate among the analyzed losses.The paper also extends the analysis and asymptotic rates to fully connected linear networks of arbitrary depth.
  • Main contributions: Normalized gradient updates improve exponential-loss convergence from 1/log(t) to O(log(t)/√t), with experiments suggesting benefits may extend to nonlinear neural networks.The numerical evidence motivates studying aggressive step sizes beyond standard gradient descent.

2 SETUP AND REVIEW OF PREVIOUS RESULTS

The setup considers gradient descent on unregularized strictly monotone losses over linearly separable data, where iterates diverge but their directions define the classifier. Previous results connect tight exponential tails to maximum-margin convergence, while direction and margin convergence can remain logarithmically slow.

  • Setup: The paper studies unregularized empirical loss minimization for homogeneous linear predictors on strictly linearly separable binary data.Labels can be absorbed into the inputs, and the predictor is represented by a weight vector w with the L2 norm used throughout.
  • Setup: Strict monotone losses are differentiable, strictly decreasing, positive, bounded below, and approach zero together with their derivative as the margin grows.The definition also requires the derivative's lim sup not to vanish as the margin tends to negative infinity.
  • Setup: For separable data, logistic, exponential, and probit losses have no finite global minimizer, so gradient descent iterates diverge while the normalized direction specifies the classification boundary.This makes directional convergence the relevant notion of implicit bias.
  • Previous results: Under a tight exponential tail and sufficiently small fixed step size, gradient descent converges in direction to the unit-L2 maximum-margin separator for almost all separable datasets and any initialization.The exponential-loss case extends through bounded local smoothness when η < 1/L(w(0)).
  • Previous results: 1/log(t) is the convergence rate for direction and margin under exponentially tailed losses, although the loss itself can decay as O(1/t).Thus loss convergence is substantially faster than convergence to the maximum-margin direction.
  • Previous results: Fully connected deep linear networks were previously shown to converge toward the L2 maximum-margin separator under exponential loss, but the result required additional parameter and loss-convergence conditions and did not give a margin rate.The current paper uses this setting to study broader tails and rates.

3 MAIN RESULTS

The paper characterizes when gradient descent on strictly monotone losses reaches the L2 maximum-margin direction and how tail behavior and step-size choices affect margin convergence. It extends the result to deep linear networks and shows that aggressive step sizes can substantially accelerate convergence for exponential loss.

  • Linear networks with general tails: Super-polynomial tails under Assumption 1 yield convergence to the maximum-margin solution for linear networks of any depth.The assumptions include strict monotonicity, asymptotic convexity, and a non-oscillatory tail; the family includes logistic, exponential, poly-exponential, and selected sub-exponential losses.
  • Linear networks with general tails: (Sub)polynomial tails need not converge to the maximum-margin separator, while hinge loss generally requires regularization for such convergence.The hinge-loss behavior is attributed to convergence toward a finite initialization-dependent minimizer.
  • Linear networks with general tails: Logistic loss is covered by the broader super-polynomial-tail characterization, extending prior exponential-loss results for fully connected linear networks.The paper explicitly includes logistic loss even though the earlier network characterization analyzed exponential loss.
  • Rates of convergence: 1/log(t) is the optimal fixed-step-size margin-convergence rate, attained by exponentially tailed losses including logistic and exponential loss.For poly-exponential losses with 0.25 < ν ≤ 1, the rate is also O(1/log(t)), but ν < 1 has strictly worse constants than ν = 1.
  • Faster rates using variable step sizes: For exponential loss, aggressive variable step sizes improve margin convergence to log(t)/√t instead of the fixed-step-size rate 1/log(t).The normalized update is stated without requiring the unknown optimal margin, and the paper reports this improvement for linear models.
  • Faster rates using variable step sizes: The faster-step-size strategy is proposed to improve understanding of gradient descent and may be applicable to deep neural networks, rather than serving primarily as a faster SVM optimizer.The paper's numerical results motivate this possible extension, but the stated goal is not to develop a faster SVM solver.

4 EXPERIMENTS WITH NORMALIZED GRADIENT DESCENT

Experiments compare normalized gradient descent with standard gradient descent on synthetic linear models, MNIST, and CIFAR-10. Normalization generally accelerates convergence and improves test performance, though CIFAR-10 results remain below standard optimization using momentum and weight decay.

  • Synthetic experiments: Normalized GD converges significantly faster than GD on synthetic logistic regression and layered linear-network experiments.The comparisons examine convergence through training loss, margin gaps, and related measures.
  • CIFAR-10: On CIFAR-10, best-yet test-error progress stops after t = 2350 despite learning-rate decays.The experiment suggests that regularization and/or momentum may be required for further improvement.
  • MNIST: 1.4% test error versus 1.91% shows normalized GD outperforming GD on MNIST.GD training loss stagnates as gradients become small, whereas normalized GD continues decreasing the loss.
  • CIFAR-10: 6.93% test error versus 9.90% shows normalized GD outperforming GD on CIFAR-10 after 7,800 iterations at η = 2.0.The learning rate was selected from {1.0, 1.5, 2.0, 2.5, 3.0} using validation performance.
  • CIFAR-10: Normalized GD remains below standard Wide ResNet optimization, whose momentum and weight decay achieve 4.45% test error compared with 7.75% without them.The comparison motivates reconciling weight decay, momentum, and gradient normalization.

5 DISCUSSION

The discussion connects tail behavior, optimization dynamics, and implicit bias: super-polynomial tails support maximum-margin convergence, exponential tails give the optimal linear-model rate, and larger step sizes can accelerate exponential-loss gradient descent. It also identifies extensions, assumptions, and open gaps involving regularization, momentum, stochasticity, and non-separable data.

  • Tail conditions: Super-polynomial tails yield L2 maximum-margin convergence in multilayer linear networks, whereas polynomial tails do not.The stated intuition is that support vectors dominate gradients only for super-polynomial tails.
  • Convergence rates: Exponential tails have the optimal convergence rate for linear classifiers within the studied loss family.The authors note that this may explain the empirical preference for exponentially tailed losses, although they lack an intuitive explanation for the result.
  • Deep linear networks: Multilayer linear networks retain similar convergence rates, with only a negligible depth-related decrease, even for infinitely many layers.This result assumes convergence of the loss to zero and shows little dependence on depth despite possible exploding or vanishing gradients.
  • Adaptive learning rates: Increasing the learning rate can significantly accelerate gradient descent for exponential loss.The accelerated method can also approximate the regularization path, reaching an ε-close same-norm predictor after t ≥ log(n/ε)/γ^2 steps under the stated setup.
  • Experiments and future work: Normalized gradient descent improves convergence speed on synthetic linear, multilayer linear, and nonlinear ReLU networks, and improves MNIST and CIFAR-10 results by 0.5% and 3%.The experiments still show a gap from state-of-the-art results, attributed to weight decay and momentum outside the paper’s scope.
  • Scope and limitations: The analysis remains bounded by assumptions on iterate and gradient convergence, while extensions to non-strictly-separable data and stochastic gradient descent remain open.The discussion also contrasts this work’s optimization-dynamics analysis with prior explicit regularization-path analyses.

B.3 Proof of Theorem 5

Normalized steepest descent with ηt = 1/√(t+1) yields a decreasing objective and a margin convergence rate of t^-1/2 log t for exponential loss.

  • Setup: ηt = 1/√(t+1) defines the variable step size for normalized steepest descent with exponential loss.The updates apply to any separable dataset and any initial point.
  • Rate: t^-1/2 log t is the convergence rate of the iterates’ margin to the maximum margin γ.The displayed bound gives the corresponding asymptotic rate.
  • Descent property: The step size satisfies the conditions ensuring that the objective function decreases.This follows because ηt/L(wt) < 1/L(wt).

C Tail Analysis – Proof sketch

The proof sketch explains why sufficiently fast loss tails isolate support vectors, leading gradient dynamics toward the SVM KKT conditions and motivating the tail conditions used for rate analysis.

  • Tail parameterization: The tail is represented as -ℓ′(u) = exp(-f(u)) with f strictly increasing for strictly monotone losses.This parameterization makes the tail’s growth rate explicit in the gradient analysis.
  • Support-vector dominance: Asymptotic gradient contributions become dominated by samples with minimal margin when f increases sufficiently fast.The resulting gradient direction is determined primarily by support vectors.
  • SVM characterization: The limiting direction satisfies the SVM KKT conditions because it is a nonnegative combination of support vectors.This identifies the limit direction with a scaled maximum-margin separator.
  • Asymptotic analysis: The analysis uses continuous-time gradient descent to derive the asymptotic scale g(t) and residual term ρ(t).The differential equation for g(t) is generally intractable.
  • Validity conditions: The proof requires f′(t) = ω(t^-1), equivalently f(t) = ω(log(t)), and uses log(f′(t)) = o(f(t)) for approximation.The latter condition holds for many functions but is an additional validity condition for the rate calculation.

D.2 Theorem 2 Proof

For deep linear networks, the proof connects layerwise gradient descent dynamics to a limiting linear predictor whose direction satisfies the maximum-margin characterization under the stated assumptions.

  • Theorem assumptions: Theorem 2 covers any depth L, almost all linearly separable datasets and initializations, and bounded step-size sequences.The result concerns the sequence of layer parameters W(t).
  • Loss assumptions: The proof assumes a strictly monotone loss with ℓ′(u) = -exp(-f(u)) < 0 and asymptotically f′(u) = ω(...).These tail conditions extend the argument beyond exponential loss.
  • Limit characterization: Under loss minimization, directional convergence of parameters and predictor gradients, the limit direction is specified by the stated KKT-based characterization.The proof uses the equivalent linear predictor w(t) = P(W(t)).
  • Gradient dynamics: Layerwise updates show that W1(t + 1) − W1(t) is driven by the predictor gradient z(t) multiplied by the downstream layers.This connects predictor-level dynamics to the parameter-level direction.
  • Asymptotic alignment: The first-layer increments and parameters converge in the same direction, supporting the limiting directional result.The residual terms vanish asymptotically in the cited derivation.

E Proof of Theorems 3 and 4

The rate analysis derives asymptotic dynamics for general tails and shows that exponential tails give the optimal fixed-step margin rate for linear models, while faster tails can change the scaling.

  • Rate derivation: The proof obtains general-tail rates by first deriving an ordinary differential equation, then specializing it to deep and shallow linear networks.Additional shallow-network analysis characterizes the component outside the support-vector span.
  • Deep linear networks: Theorem 9 represents the equivalent predictor of a depth-L linear network as ẇg(t) + ρ(t), with ρ(t) = o(g(t)) and ρ(t) orthogonal to the max-margin separator.This representation is the basis for calculating convergence rates.
  • Shallow-network conditions: The rate analysis requires additional assumptions such as β-smoothness and a sufficiently small step size in the L = 1 theorem.Theorem 10 assumes η < 2β^-1 together with a lower-growth condition on f′.
  • Linear-model optimum: Exponential loss yields the optimal margin convergence rate for L = 1.The section explicitly targets this comparison in the shallow linear case.
  • Exponential tails: O(1/log(t)) is the tight margin convergence rate for losses with tight exponential tails f(t) = Θ(t).This bound was previously proved for exponential-tailed losses.
  • Faster tails: For faster-than-exponential tails f(t) = ω(t), margin convergence rates are proportional to 1/g(t), with g(t) asymptotically tied to f^-1(log(t)).The asymptotic solution is ğ(u) = f^-1(log(u)).

F.2 Proof of Theorem 9

The proof decomposes the predictor into a maximum-margin component and an orthogonal residual, then controls the residual through support-vector quantities. It establishes asymptotic behavior whose key scaling is independent of the loss function and yields directional convergence to the maximum-margin separator.

  • Asymptotic decomposition: The equivalent predictor is decomposed as w(t) = g̃(t)ŵ + ρ(t), with ρ(t) orthogonal to the L2 maximum-margin separator.The maximum-margin separator is denoted ŵ, and the residual satisfies ρ(t)⊤ŵ = 0.
  • Directional convergence: The normalized predictor converges in direction to the normalized L2 maximum-margin separator as the predictor norm diverges.The conclusion combines directional convergence of the decomposition with ∥w(t)∥ → ∞.
  • Support-vector control: Support-vector quantities ψ_n(t) are shown to remain asymptotically bounded above and below.The argument uses contradiction, positivity of the support-vector coefficients, linear independence, and the maximum-margin representation.
  • Residual control: The residual components in the support-vector span are bounded after scaling by f′(g̃(t)).This follows from bounded ψ_n(t) and the definition of the remainder term R_n(t).
  • Loss-independent scaling: ζ(t) has asymptotic behavior independent of the loss function, while the remaining scaling terms depend only on the dataset and network depth.The proof summarizes the asymptotic system using ζ(t) = Θ(1) and τ(t) = Θ(1).

G Proof that non-support vectors direction converge for L = 1

This section analyzes when non-support-vector directions converge under general loss tails. It shows that faster-than-polynomial tails support maximum-margin convergence, whereas polynomial or sufficiently heavy tails can prevent it.

  • Theorem 10: Theorem 10 imposes a β-smooth loss condition, a bounded step-size restriction, and a lower-growth condition on f′ for directional convergence.The theorem applies to the depth-one case and assumes η < 2β^-1.
  • General-tail framework: Theorem 2 covers arbitrary depth, almost all separable datasets and initializations, and bounded step-size sequences under the stated strictly monotone-tail assumptions.Its conclusion is conditional on loss minimization, positive-margin directional convergence, and directional convergence of predictor gradients.
  • Tail threshold: If f(t) = O(log(t)), convergence to the maximum-margin separator is not guaranteed.The section explicitly contrasts this regime with the required condition f(t) = ω(log(t)).
  • Polynomial tails: Polynomial-tailed losses fail to converge to the maximum-margin separator in the worked two-dimensional example.For this case, g(t) grows as t^1/3 while h(t) grows at the same scale, violating the asymptotic separation used in the analysis.
  • Super-polynomial tails: For poly-exponential tails with exponent ϵ > 1, f(t) = Θ(log^ϵ(t)) = ω(log(t)), consistent with maximum-margin convergence.The integrated dynamics are given by exp(log^ϵ(w_1(t))) = t + C and exp(log^ϵ(2w_2(t))) = 4t + C.
  • Boundary regime: For ϵ ≤ 1, the example does not converge to the maximum-margin separator, matching the condition f(t) = O(log(t)).The reported limits are w_1(t)/w_2(t) → 0 for ϵ < 1 and → 0.5 for ϵ = 1.

H.3 Example: Demonstrating that the upper bound in Theorem 3.1 is not always obtained

The worked example demonstrates that the upper bound from Theorem 3.1 is not always attained. With an extra coordinate that remains constant, the asymptotic margin gap can retain the theorem’s slower rate.

  • Tightness: The example shows that the stated upper bound is tight because the unchanged second coordinate controls the asymptotic deviation from the target direction.This is the paper’s direct conclusion from the integrated dynamics.
  • Example setup: The example uses a single data point x_1 = (1, 0), whose maximum-margin separator is ŵ = (1, 0).The analysis takes the continuous-time limit of gradient descent.
  • Experimental context: The experimental setup also uses random Gaussian initialization and compares GD at η = 1/β with normalized GD using the same initial step size.These choices are reported for the corresponding training experiments.
  • Observed behavior: Normalized GD reaches zero numerical training loss faster, but its margin-gap curve is less stable under the aggressive learning rate.The instability is attributed to rapid switching of the datapoint attaining the smallest margin.

I.2 Neural Networks on a Toy Dataset

Toy-data experiments compare GD and Normalized GD on logistic regression and two- and three-layer networks with linear or ReLU activations. Across these settings, Normalized GD reaches the maximum-margin solution faster, while linear and ReLU networks show similar convergence plots.

  • Dataset and setup: The synthetic dataset contains 600 two-dimensional points generated from separate positive and negative Gaussian distributions.The same generated points are reused across the experiments.
  • Logistic regression: Logistic-regression plots show that Normalized GD converges significantly faster to the maximum-margin solution than GD.Both methods are compared over 5×10^4 epochs.
  • Evaluation convention: For the nonlinear network, angle and margin are computed from the product W_1W_2...W_d as though the model were linear.This convention is also used in the analysis of the 3-layer experiments.
  • Two-layer networks: In 2-layer networks with architecture 2 × 10 × 1, linear and ReLU activation plots look similar, and Normalized GD remains faster.The normalized method reaches zero numerical loss in roughly 10^4 epochs in the reported comparison.
  • Three-layer networks: The 3-layer networks use architecture 2 × 10 × 10 × 1, and their linear and ReLU convergence plots are also similar.The comparison is conducted for both GD and Normalized GD over 5×10^4 epochs.

J Losses with poly-exponential tails

For poly-exponential tails, gradient descent converges in direction to the normalized L2 maximum-margin separator under stated smoothness, monotonicity, tail, and step-size conditions. The convergence rate is optimized at tail exponent ν = 1 and becomes slower as ν moves away from 1.

  • Convergence theorem: ν > 0.25 and η < 2β−1 suffice for gradient descent on β-smooth strictly monotone losses with tight poly-exponential tails to satisfy the stated asymptotic behavior.The result holds for any initialization and almost all linearly separable datasets.
  • Convergence theorem: w(t)/∥w(t)∥ converges to the normalized L2 maximum-margin separator for poly-exponential tails with ν > 0.25.The theorem generalizes the exponential-tail convergence result.
  • Convergence rates: ν = 1 achieves the optimal convergence rate for poly-exponential tails, while rates become slower as |ν − 1| increases within ν > 0.25.The rate comparison is summarized in Table 1 and accompanying analysis.
  • Proof strategy: The proof decomposes the iterates into a leading maximum-margin term, a tail-dependent correction, and a remainder whose growth is controlled asymptotically.The analysis uses w(t) = ˆw g(t) + ρ(t), with further bounds on the residual terms.
  • Proof strategy: For separable data and sufficiently small step size, the loss tends to zero, the parameter norm diverges, and every training margin tends to infinity.These properties provide the asymptotic regime used in the tail analysis.

K.2.3 Proof Of Lemma 8

The proof of Lemma 8 controls the residual sequence by bounding its squared-norm recursion and separating cases according to support-vector projections and residual signs. These bounds establish the required asymptotic control of the remainder.

  • Residual decomposition: The residual is defined by subtracting the leading maximum-margin and tail-correction terms from w(t).This representation isolates the part whose boundedness must be proved.
  • Residual recursion: The cross term satisfies an upper bound of order t−1 times a logarithmic factor, yielding improved residual bounds after combination with the increment estimates.The proof invokes this bound repeatedly to control the recursion.
  • Conclusion of the proof: The resulting bounds establish the asymptotic estimates needed for the theorem’s iterate decomposition.The proof tracks the correction vectors and residual terms through the final substitutions.
  • Case analysis: The analysis splits cases according to the sign and magnitude of x_k⊤r(t), using the poly-exponential derivative bound and Taylor-type inequalities.Separate thresholds handle small and large residual projections.
  • Residual recursion: The proof expands ∥r(t + 1)∥2 into increment, cross, and previous-norm terms, then bounds each contribution.The same squared-norm recursion is the central device for controlling the residual.
Loading 1803.01905v3…