The Implicit Bias of Gradient Descent on Separable Data

Daniel Soudry; Elad Hoffer; Mor Shpigel Nacson; Suriya Gunasekar; Nathan Srebro

Source-linked AI summary

The Implicit Bias of Gradient Descent on Separable Data

Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, Nathan Srebro

arXiv:1710.10345v7Oct 27, 2017stat.MLcs.LG

TL;DR

The paper asks how implicit regularization operates when gradient descent minimizes logistic loss on separable data without a finite minimizer. It analyzes the resulting dynamics and shows that the normalized predictor converges to the hard-margin SVM direction, slowly enough to explain continued benefits from optimization after training loss is already tiny.

Problem
The paper studies how implicit regularization affects the predictor direction when unregularized logistic loss is minimized on separable data and the predictor norm diverges.
Method
The paper analyzes gradient-descent dynamics, characterizing residual errors and convergence rates for separable logistic regression and related settings.
Results
The normalized predictor converges to the L2 maximum-margin hard-margin SVM solution, with direction convergence typically O(1/log(t)) and slower O(log log(t)/log(t)) in some degenerate datasets.
Takeaways & Limitations
Continued optimization can improve predictions after zero training error and extremely small loss, so validation 0–1 error is preferable to validation loss for deciding when to stop.
Takeaways & Limitations
The paper focuses on exponential-tail losses and leaves open whether other loss tails yield the same max-margin direction or faster convergence.

Abstract

from arXiv · show

We examine gradient descent on unregularized logistic regression problems, with homogeneous linear predictors on linearly separable datasets. We show the predictor converges to the direction of the max-margin (hard margin SVM) solution. The result also generalizes to other monotone decreasing loss functions with an infimum at infinity, to multi-class problems, and to training a weight layer in a deep network in a certain restricted setting. Furthermore, we show this convergence is very slow, and only logarithmic in the convergence of the loss itself. This can help explain the benefit of continuing to optimize the logistic or cross-entropy loss even after the training error is zero and the training loss is extremely small, and, as we show, even if the validation loss increases. Our methodology can also aid in understanding implicit regularization n more complex models and with other optimization methods.

1. Introduction

The paper frames implicit optimization bias as a possible explanation for good generalization in overparameterized models, then asks how gradient descent behaves on separable logistic-loss problems where the predictor norm diverges.

Overparameterized training objectives can have many global minima, yet optimization algorithms may bias learning toward particular solutions that generalize well.
Existing understanding covers implicit regularization from early stopping and minimum-norm solutions for underdetermined least squares.
Logistic and cross-entropy losses have no finite minimizer on separable data, so driving the loss toward zero requires the predictor norm to diverge.
The central question is how the normalized predictor w(t)/∥w(t)∥ behaves as t →∞ when gradient descent achieves zero classification error.
The paper shows that gradient descent converges in direction to the L2 maximum-margin separator without explicit regularization.

2. Main Results

On linearly separable data, gradient descent drives logistic-type loss to zero while the predictor norm diverges, yet its normalized direction converges to the L2 maximum-margin separator. Under exponential-tail conditions, the residual is at most O(log log(t)) and is bounded for almost all datasets.

Optimization behavior: Gradient descent reaches zero loss while the predictor norm diverges and every training margin tends to infinity.These conclusions hold under the stated smooth decreasing-loss assumptions and an appropriate stepsize.
Directional limit: The main question is whether the diverging predictor has a limiting direction and which separator determines it.Prediction depends on the normalized predictor rather than its diverging norm.
Main theorem: For separable datasets and exponential-tail losses, normalized gradient descent converges to the L2 maximum-margin vector, the hard-margin SVM solution.The result applies to any starting point and stepsize below the stated smoothness bound.
Convergence rate and residual: The residual grows at most as O(log log(t)) and is bounded for almost all datasets.A complete characterization extends the bounded-residual result beyond non-degenerate datasets to all datasets, including degenerate cases.
Main theorem: The max-margin direction arises without explicitly optimizing either the predictor norm or a margin constraint.The proof sketch attributes the asymptotic direction to gradients from the smallest-margin support vectors, whose KKT conditions match the SVM solution.
Related optimization biases: The implicit bias depends on the optimization algorithm: coordinate descent yields the max-L1-margin predictor, whereas gradient descent yields the max-L2-norm predictor.This contrasts algorithm-induced bias with explicit infinitesimal regularization.

3. Implications: Rates of convergence

Gradient descent converges in direction to the normalized L2 max-margin separator, but this convergence is logarithmically slow. Consequently, margin and sometimes classification error can improve even after training loss is tiny, while population or validation loss may increase.

The normalized weight vector converges to the normalized L2 max-margin vector for linearly separable data.
O(1/log(t)) convergence in angle and O(1/log^2(t)) convergence in margin hold for almost every dataset.
Non-vanishing explicit regularization generally does not produce a max-margin solution.
The convergence rates are tight apart from possible log log t factors, including improvements established for degenerate cases.
The norm grows logarithmically while training loss decreases rapidly, so approaching the max-margin direction may require an exponentially small loss.
Population and validation loss can increase logarithmically even as the margin and population misclassification error improve.

4. Extensions

The paper extends its implicit-bias analysis to multiclass cross-entropy and restricted deep-network settings, while contrasting gradient descent with adaptive methods. These extensions retain important scope conditions and leave the effect of other loss tails open.

4.1 Multi-Class Classification with Cross-Entropy Loss: For linearly separable multiclass data, gradient descent on softmax cross-entropy yields predictors that diverge while their directions approach a K-class SVM solution under an additional solvability assumption.
4.2 Deep networks: The deep-network extension applies exactly when a single weight layer is optimized and ReLU activation patterns eventually stop switching.
4.2 Deep networks: The restricted deep-network proof reduces the fixed-activation network to a linear problem on transformed inputs, where the linear separability condition permits applying the main theorem.
4.2 Deep networks: The deep-network case is non-convex unless only the last layer is optimized, although the proof can extend to piecewise-linear constant activations.
4.3 Other optimization methods: Adaptive methods can induce a different bias: ADAM reaches zero training error but does not converge to the L2 max-margin predictor, unlike gradient descent.
4.4 Other loss functions: The analysis focuses on exponential-tail losses, leaving convergence direction and rate for other loss tails as open questions.

5. Summary

The paper characterizes gradient descent’s implicit bias for homogeneous linear predictors and exponential-tailed monotone losses. It shows convergence toward the maximum L2-margin solution, but this directional convergence is much slower than loss convergence and does not justify stopping based on loss plateaus.

Implicit bias: Gradient descent induces implicit L2 regularization and converges to the maximum L2-margin solution for binary and multi-class separable classification.This holds for logistic, exponential, and other exponential-tailed monotone decreasing losses, including multi-class cross-entropy.
Implicit bias: The induced bias is independent of the loss’s non-tail behavior, sufficiently small step-size, and initialization.Logistic and exponential losses behave differently on non-separable data but exhibit the same bias on separable data.
Convergence: Directional convergence to the maximum L2-margin solution is very slow compared with training-loss convergence.The result explains why continued optimization can remain useful after zero training error and an extremely small loss.
Stopping criterion: Validation 0–1 error, rather than training or validation loss plateaus, should guide stopping decisions.Validation and test errors may improve while training-loss decreases are tiny and validation loss increases.
Proof strategy: The proof analyzes a residual around a logarithmically growing maximum-margin component and uses support-vector projections and margin separation.For almost every dataset, the residual is shown bounded under the stated theorem conditions.

A.2 Complete proof of Theorem 9

The proof of Theorem 9 establishes boundedness of the residual after subtracting the logarithmically growing maximum-margin component. It proceeds by controlling residual increments and exploiting exponential-tail decay and a positive margin gap.

Proof setup: The general proof extends the special continuous-time exponential-loss argument to finite step sizes and exponentially tailed losses.The authors note that additional terms make the general analysis more involved.
Residual control: A descent lemma for β-smooth non-negative objectives supplies finite cumulative control when η < 2β^-1.This control applies for any starting point and the associated gradient-descent sequence.
Residual control: The proof bounds the residual’s inner-product increments by a decaying power of t and obtains eventually small changes in its norm.The resulting exponent depends on the margin-separation and tail parameters.
Residual control: The proof defines r(t) as the residual after removing the maximum-margin term and an offset, then aims to show ∥r(t)∥ is bounded.Bounded residual implies boundedness of the corresponding offset-adjusted quantity.
Margin decomposition: Exponential-tail bounds separate support-vector and non-support-vector contributions, with the latter controlled by a margin strictly greater than one.Integrating these bounds yields bounded residual norm.

A.5 Proof of Lemma 11

The proof of Lemma 11 controls the residual dynamics by decomposing gradient contributions according to support-vector geometry and residual signs. It derives summable decay bounds that support boundedness and eventual convergence arguments.

Residual dynamics: The residual is defined by subtracting the logarithmically growing maximum-margin vector and an offset from w(t).The proof studies the resulting update expression term by term.
Conclusion: Combining the bounds yields the desired increment inequality and completes the lemma’s residual-control argument.The proof explicitly treats the complementary small-residual case with the displayed summable bound.
Term bounds: Gradient contributions are controlled using exponential-tail bounds after separating support-vector and non-support-vector terms.The analysis invokes the positive margins of non-support vectors and asymptotic growth of w(t)^T x_n.
Case analysis: The proof handles separate cases according to the signs of x_n^T r(t), applying exponential inequalities and threshold choices to obtain negative or decaying bounds.The case analysis covers both large and small projected residual regimes.

Appendix B. Generic solutions of the KKT conditions in eq. 6

For almost all datasets, the KKT solution associated with the maximum-margin problem is unique and has nonzero dual variables on support vectors. Consequently, there are at most d support vectors.

Generic KKT structure: For almost all datasets, the KKT conditions admit a unique solution α.The proof establishes uniqueness after fixing the uniquely determined support-vector set.
Generic KKT structure: For almost all datasets, α_n is nonzero whenever x_n is a support vector satisfying the unit-margin condition.Zero dual components occur only outside the support-vector set.
Support vectors: There are at most d support vectors for almost every dataset.All support vectors lie on one hyperplane, and generically no more than d points lie on the same hyperplane.
KKT proof: Given the support-vector set, the KKT equations determine the restricted dual variables through the corresponding support-vector matrix.The generic nonzero result follows by excluding polynomial root sets of measure zero.

Appendix C. Completing the proof of Theorem 3 for zero measure cases

This appendix extends the asymptotic characterization to degenerate, measure-zero datasets by recursively resolving zero-coefficient support vectors. It establishes a logarithmic max-margin expansion with bounded residual.

Scope: The analysis covers all linearly separable datasets, including degenerate cases excluded by the earlier almost-everywhere result.Degeneracy occurs when support vectors have zero dual coefficients.
Stopping condition: For almost all datasets, the recursion stops at M = 1 because support vectors have nonzero coefficients.Only a measure-zero set requires later stages.
Recursive construction: The recursive construction repeatedly projects zero-coefficient support vectors onto components orthogonal to nonzero-coefficient support vectors.At each stage, a max-margin predictor is defined on the projected, lower-dimensional dataset.
Asymptotic expansion: The iterates admit a decomposition into iterated-logarithmic max-margin terms plus correction vectors and a bounded residual.The expansion uses terms of the form ˆw_m log◦m(t).
Residual control: The proof bounds residual growth by a convergent-series argument applied to a squared-norm recurrence.The residual increment is controlled by summable error terms, yielding boundedness.

C.3 Proof of Lemma 14

The proof of Lemma 14 shows that residual updates satisfy a summable recurrence. Exponential-tail bounds and iterated-log integrability make the error terms summable, which controls the residual norm.

Summability: Lemma 16 establishes integrability for products of powers of t and iterated logarithms when the first exponent exceeding one appears.This criterion supplies the convergence test used throughout the proof.
Lemma 14: The resulting inner-product increment satisfies (r(t + 1) − r(t))^T r(t) ≤ κ1(t)∥r(t)∥ + κ2(t), with κ1 and κ2 absolutely summable.This is the formal statement of Lemma 14.
Termwise bounds: The proof decomposes residual-update terms according to support-vector components and bounds each component using exponential-tail estimates.The bounds distinguish whether the residual projection onto a data point is positive or nonpositive.
Conclusion: All remaining terms are either negative, integrable, or proportional to the residual norm with an integrable coefficient.This is the concluding bound needed for Lemma 14.

C.5 Proof of the existence and uniqueness of the solution to eqs. 65-66

This section proves existence and uniqueness of the auxiliary vectors used in the recursive asymptotic decomposition. Orthogonal projections separate the equations into independently solvable components.

Orthogonal decomposition: The construction decomposes the solution across mutually orthogonal projection subspaces.Each projected product can therefore be solved separately.
Constraint satisfaction: The auxiliary vectors satisfy the recursive projection constraints by construction.The projection identities ensure compatibility with the support-vector subspaces.
Uniqueness: The projected linear systems have full-rank coefficient matrices, giving unique solutions for each auxiliary vector ˇw_k,m.The proof uses a diagonal nonzero matrix and the rank argument in the corresponding equations.
Residual implication: The norm-recurrence lemma converts summable update bounds into bounded residual behavior.The argument applies a recurrence for φ(t)^2 with summable h(t) and z(t).

D.1 Proof of Theorem 5

This section derives convergence rates and extends the asymptotic analysis to multiclass softmax cross-entropy. The rates remain slow, while separable multiclass iterates exhibit vanishing loss and diverging norm.

Binary rates: For almost all datasets, w(t) = ˆw log t + ρ(t) with bounded ρ(t); degenerate datasets add orthogonal O(log log(t)) corrections.The leading direction remains the L2 max-margin vector.
Binary rates: For all datasets, the training loss satisfies L(w(t)) = O(t^-1), including the zero-measure degenerate case.The degenerate correction does not change the loss rate because it has a nonnegative angle with support vectors asymptotically.
Multiclass extension: In the multiclass setting, separable softmax cross-entropy has loss converging to zero, norm diverging to infinity, and all incorrect-class margins diverging.These properties hold under strict linear separability and an appropriately small learning rate.
Multiclass extension: The multiclass theorem characterizes the iterates through class-specific max-margin quantities plus bounded residuals.The result assumes the defining auxiliary equation has a solution.

E.3 Proof of Theorem 7

The proof establishes boundedness of the residual term r(t) by bounding its squared-norm increment and showing the relevant error terms decay through convergent power series. Consequently, the residual remains bounded under the stated nondegeneracy and separability conditions.

Increment bounds: A t^-ν power series with ν > 1 converges, yielding a bound on the residual increment and eventually |∥r(t + 1)∥ − ∥r(t)∥| < ϵ0.The proof uses this convergence after substituting the relevant bounds into the recurrence.
Cross-term bound: The cross term (r(t + 1) − r(t))⊤r(t) is bounded by C1t^-θ + C2t^-2 for sufficiently large t, with θ > 1.The argument treats separately whether the projection of r(t) onto the relevant subspace is large or small.
Residual decomposition: The proof decomposes the iterate as w(t) = ˆw log(t) + ˜w + r(t) and aims to show that r(t) remains bounded.The squared-norm recurrence for r(t) separates increment, cross, and residual-norm terms.
Conclusion: Combining the increment and cross-term bounds shows that ∥r(t)∥ is bounded.The conclusion follows after establishing the required bound in both projection cases.

Appendix F. An experiment with stochastic gradient descent

Figure 4 repeats Figure 1 using stochastic gradient descent with mini-batches of size 4.

Experimental setup: Figure 4 uses the same experimental setup as Figure 1, changing the optimizer to stochastic gradient descent with mini-batches of size 4.The caption specifies the controlled comparison with Figure 1.