The Implicit Bias of Gradient Descent on Separable Data

Motivation

• The paper positions implicit bias as important because overparameterized training has many zero-error solutions, while optimization can favor solutions that generalize well.It notes that this bias remains poorly understood across optimization algorithms and settings.Source: §1 · p. 1

Problem setting

• For logistic and cross-entropy losses on separable problems, minimizing the loss requires the predictor norm to diverge, so prediction depends on its limiting direction rather than norm minimization.This contrasts with finite-minimizer losses such as squared loss, where gradient descent can select a minimum-Euclidean-norm solution.Source: §1 · p. 2

Main contribution

• Gradient descent on every linearly separable dataset makes the normalized predictor converge to the L2 maximum-margin separator, although neither norm nor margin is explicitly optimized.The result applies to homogeneous linear predictors and hard-margin SVM solutions.Source: §1 · p. 2

Generalization

• The same directional bias holds for generalized linear problems using smooth, strictly decreasing, lower-bounded losses with exponential tails.The loss class extends beyond logistic regression while retaining the max-margin directional limit.Source: §1 · p. 2

Convergence rate

• Convergence to the max-margin direction is slow: typically O(1/log(t)), and O(log log(t)/log(t)) on some degenerate datasets, explaining continued predictor improvement at tiny training loss.This slow convergence helps explain why optimization can remain beneficial after zero training error and extremely small loss.Source: §1 · p. 2

Algorithm dependence

• The max-margin bias is specific to gradient descent: changing the optimizer, including using ADAM (Kingma and Ba, 2015), changes the implicit bias.Thus the selected predictor direction depends on the optimization algorithm, not only the training objective.Source: §1 · p. 2

Global convergence

• Gradient descent reaches zero loss while the weight norm and every training margin diverge, even without convexity, under the stated smoothness and stepsize conditions.The stepsize must satisfy η < 2β^-1σ_max(X)^-2.Source: §2 · p. 3

Max-margin implicit bias

• With a tight exponential loss tail, gradient descent converges in direction to the L2 max-margin vector solving the hard-margin SVM problem.The result applies to any linearly separable dataset, any starting point, and losses such as logistic and exponential loss.Source: §2 · p. 4

Residual behavior

• The deviation from the logarithmically growing max-margin trajectory is at most O(log log(t)), and it is bounded for almost all datasets.The bounded-residual statement extends beyond the generic non-degenerate case through a characterization of degenerate iterates.Source: §2 · pp. 4–5

Proof intuition

• The max-margin direction emerges because exponentially weighted gradients asymptotically select the smallest-margin support vectors, whose KKT relations identify the SVM solution.The analysis cancels the dominant t^-1 increment using the max-margin term and controls the remaining residual increments by a convergent series.Source: §2 · p. 4

Refined residual analysis

• For almost all datasets whose support vectors span the data, the residual converges to a fixed vector characterized by an additional theorem.This refinement assumes rank(X_S) = rank(X).Source: §2 · p. 5

Related implicit-bias results

• The implicit bias depends on the optimization algorithm: coordinate descent yields the maximum L1-margin solution, whereas gradient descent yields the maximum L2-margin predictor without explicit regularization.This contrasts algorithmic bias with regularization-path results, which obtain max-margin predictors by adding infinitesimal explicit Lp regularization.Source: §2 · p. 6

Theorem 5

• The normalized weight vector converges to the normalized max-margin vector for any linearly separable dataset, with generally logarithmic convergence rates.The L2 rate improves to O(1/log(t)) for almost every dataset, while the angle rate improves to O(1/log^2(t)); the stated rates are tight up to possible log log(t) factors.Source: §3 · pp. 6–7

Implications

• The loss can become exponentially small before the predictor is close to max-margin, so continued optimization after zero training error may still improve the margin and generalization.The contrast between logarithmic convergence of the predictor and 1/t loss decay explains why optimization can remain useful in this regime.Source: §3 · p. 7

Population loss

• Population loss can increase logarithmically even as the margin and population misclassification error improve, because the growing norm increases loss on points still misclassified by the max-margin predictor.The max-margin predictor has zero training error but need not have zero population or test misclassification error.Source: §3 · p. 7

Validation loss

• Validation loss likewise increases logarithmically when at least one validation sample is misclassified by the max-margin vector, despite possible improvement in the model’s margin or error rate.This increase can misleadingly suggest overfitting or motivate premature stopping, although the model may still be improving.Source: §3 · pp. 7–8

Numerical illustration

• Figure 1 illustrates logarithmic norm growth and convergence of the angle and margin gap, alongside rapidly decreasing training loss for gradient descent and momentum.The figure reports training loss decreasing as t^-1 while the angle and margin gap decrease logarithmically toward zero.Source: §3 · p. 8, Figure 1 · p. 8

4.1 Multi-Class Classification with Cross-Entropy Loss

• For linearly separable multiclass data, gradient descent drives cross-entropy loss to zero while predictors diverge toward the K-class SVM directions, assuming the required equation has a solution.The authors conjecture this solvability condition holds for almost all multiclass datasets but leave the proof open.Source: §4.1 · p. 9

4.2 Deep networks

• 8.3% final validation error accompanies logarithmically growing final-layer norm and slowly improving validation error after zero training error, despite increasing validation loss.These observations come from convolutional-network training on CIFAR10 with stochastic gradient descent, momentum, softmax output, and cross-entropy loss.Source: §4.2 · pp. 9–10, Figure 2 · p. 10

4.3 Other optimization methods

• Momentum and stochasticity preserve gradient descent’s asymptotic bias, whereas ADAM reaches zero training error without converging to the L2 max-margin predictor.Figure 3 compares ADAM and gradient descent on a simple dataset; later work characterizes adaptive-method limits as potentially dependent on initialization and step size.Source: §4.3 · pp. 12–13, Figure 3 · p. 12

4.4 Other loss functions

• For losses with ℓ′(u)=exp(−u^ν), ν>0.25, follow-up work identifies the exponential tail as rate-optimal, while polynomial or heavier tails fail to reach max margin.A normalized gradient scheme for exponential loss improves convergence to O(log(t)/…).Source: §4.4 · p. 13

4.5 Matrix Factorization

• For under-determined matrix factorization with exponential loss, gradient-descent directions asymptotically relate to unit-nuclear-norm maximum-margin solutions under additional assumptions, largely independent of initialization.This contrasts with squared loss, where the minimum-nuclear-norm conjecture requires infinitesimal initialization and step sizes.Source: §4.5 · p. 13

5. Summary

• Gradient descent without early stopping induces implicit L2 regularization and converges to the maximum L2-margin solution for separable binary and multi-class classification.This holds for logistic, exp, and other exponential-tailed monotone decreasing losses, and for multi-class cross-entropy loss.Source: §5 · pp. 13–14
• The implicit bias is independent of the exponential-tailed loss’s non-tail behavior, sufficiently small step-size, and initialization, unlike the dependence noted for least-squares problems.Logistic and exp loss behave differently on non-separable data but identically on separable data in the stated bias result.Source: §5 · p. 14
• Directional convergence to the maximum L2-margin solution is much slower than training-loss convergence, supporting continued optimization after zero error and extremely small loss.The summary identifies this rate mismatch as the reason further optimization can remain useful.Source: §5 · p. 14
• Validation loss or a plateauing training loss should not determine stopping, because validation and test 0–1 errors may improve even while validation loss increases.The summary recommends monitoring validation 0–1 error instead of logistic, exp, or cross-entropy validation loss.Source: §5 · p. 14

Appendix A. Proof of Theorems 3 and 4 for almost every dataset

• Appendix A proves the relevant theorems for almost every linearly separable dataset under a β-smooth decreasing exponential-tailed loss and a sufficiently small step-size, with arbitrary initialization.The theorem identifies the target as the L2 max-margin vector and allows the stated gradient-descent iterates to be analyzed under these conditions.Source: Appendix A · p. 15
• For almost every dataset, the appendix handles support-vector geometry through uniquely defined coefficients, at most d support vectors, and projections onto their span and complementary left-nullspace.If support vectors do not span the data, any solution satisfying the auxiliary condition may be used in the proof.Source: Appendix A · p. 15

A.1 Simple proof of Theorem 9

• The simple proof specializes to exp loss in continuous time and establishes the result by showing the residual r(t), and hence the offset ρ(t), remains bounded.It bounds separate support-vector and non-support-vector contributions, then integrates the resulting inequality using the margin gap θ > 1.Source: §A.1 · p. 16

A.2 Complete proof of Theorem 9

• A.2 proves the general case for non-infinitesimal step sizes and exponentially tailed functions, extending the preceding special-case analysis with additional term bounds.The proof targets boundedness of the residual r(t), which implies boundedness of ρ(t)=r(t)+˜w.Source: §A.2 · p. 17
• The residual increment satisfies a polynomial decay bound with exponent min(θ,1+1.5µ+,1+0.5µ−), together with an improved bound under an additional condition.These bounds control the cross term in the recursive norm expansion for r(t).Source: §A.2 · p. 17
• Using the norm recursion and convergent power-series bounds, the proof shows that |∥r(t+1)∥−∥r(t)∥|<ǫ0 eventually and concludes that ∥r(t)∥ is bounded.The conclusion uses θ>1 and µ−,µ+>0.Source: §A.2 · pp. 17–18

A.3 Proof of Theorem 4

• Under rank(XS)=rank(X), the proof decomposes r(t) into orthogonal components; its complementary component is not updated during gradient descent and remains constant.This constant component can be absorbed into ˜w without affecting eq. 7, so one may assume r(t)=P1r(t).Source: §A.3 · p. 18
• The contradiction argument uses arbitrarily late indices in the complementary set and the decreasing function h(t) to force the residual norm below any prescribed threshold.This establishes convergence to zero from the recurrence bounds and the eventual norm-change control.Source: §A.3 · p. 19
• The same rank-based invariance condition uniquely determines ˜w given w(0), because ¯P1(˜w−w(0))=0 together with eq. 7 fixes the remaining component.The proof notes that ¯P1r(t) is not updated during gradient descent.Source: §A.3 · p. 19

A.4 Proof of Lemma 10

• A.4 proves Lemma 10 for a β-smooth non-negative objective under η<2β−1, using the standard smoothness inequality to bound the gradient-descent sequence.The objective values are controlled by the initial finite value and the non-negativity condition.Source: §A.4 · pp. 19–20

A.5 Proof of Lemma 11

• The proof defines r(t)=w(t)−ŵ log t−w̃, where ŵ is the L2 max-margin vector and w̃ satisfies the theorem conditions.This residual is the quantity whose convergence behavior is controlled throughout the proof.Source: §A.5 · p. 20
• Therefore, for sufficiently large t, (r(t+1)−r(t))^⊤r(t)≤C_1t^-min(θ,1+1.5μ+,1+0.5μ−), with an improved bound under an additional ε_1-dependent condition.The proof separately establishes the result when ||P_1r(t)||≥ε_1 and then combines both regimes.Source: §A.5 · pp. 20, 25
• Using the exponential loss tail and diverging margins, the proof decomposes and bounds three terms according to the signs and magnitudes of x_n^⊤r(t).The case analysis uses assumptions on the loss derivative, projection properties, and inequalities for exponential terms.Source: §A.5 · pp. 21–22
• When ||P_1r(t)||<ε_1, the proof obtains C_3t^-1−1.5μ+ + C_4t^-1−0.5μ− + C_5t^-2 + C_6t^-θ as an upper bound.This is the explicit intermediate estimate used to derive the lemma’s uniform rate.Source: §A.5 · p. 25

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

• For almost all datasets, the KKT conditions in eq. 6 admit a unique solution α.The support set S uniquely determines the solution, and the corresponding system gives α uniquely.Source: Appendix B · pp. 25–26
• α_n ≠ 0 exactly when x_n is a support vector, while α_n = 0 for n ∉ S.For a fixed support set, the KKT conditions force non-support components to vanish; generically, zero components cannot occur among support vectors.Source: Appendix B · pp. 25–26
• There are at most d support vectors for almost every dataset.All support vectors lie on the same hyperplane, and generically no more than d points lie on any one hyperplane.Source: Appendix B · p. 25

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

• The appendix addresses the measure-zero cases excluded by Theorem 4, where support vectors can have zero dual coefficients, thereby completing Theorem 3 for all datasets.For almost all datasets the recursion stops at M = 1; degenerate datasets may require M > 1.Source: Appendix C · pp. 26–27
• The recursive construction starts from the full dataset, repeatedly projects zero-coefficient support vectors orthogonally to nonzero-coefficient support vectors, and defines lower-dimensional max-margin predictors until the recursion stops.The stopping stage M is the minimal index with no remaining zero-coefficient support vectors, and the characterization uses ˆw1 through ˆwM.Source: Appendix C · pp. 26–27
• Theorem 13 characterizes gradient descent for every linearly separable dataset under smooth exponential-tail losses and a sufficiently small step size, with iterated-log max-margin terms and bounded residual.The theorem applies for any starting point and uses the sequence of recursively defined max-margin vectors.Source: Appendix C · p. 27

C.1 Auxiliary notation

• The auxiliary notation decomposes the iterates into max-margin, correction, and residual components, with uniqueness guaranteed when the stated constraints hold.The auxiliary construction also establishes existence and uniqueness for the correction terms used in the decomposition.Source: §C.1 · pp. 27–28

C.2 Proof of Theorem 13

• The proof of Theorem 13 defines a residual r(t) relative to the asymptotic expansion and bounds its squared-norm increment using gradient-descent updates and summable error terms.The argument expands ∥r(t + 1)∥² into increment, cross, and residual terms, then bounds the first two through the asymptotic relations.Source: §C.2 · p. 28
• A recursive inequality for the residual norm follows from bounds on its cross term, and a discrete summability lemma then implies that the residual remains bounded.The proof applies Lemma 15 with φ(t) = ∥r(t)∥ and uses κ_i(t) ∈ L1 for i = 0, 1, 2.Source: §C.2 · p. 29
• The proof concludes because the required error sequences are absolutely summable, completing the bounded-residual argument for Theorem 13.This establishes the final step after combining the increment inequality with Lemma 15.Source: §C.2 · p. 29

C.3 Proof of Lemma 14

• Lemma 16 proves f(t) ∈ L1 when the first exponent νm0 exceeding 1 follows only unit exponents in the iterated-log product.The proof treats m0 > 1 and m0 = 1 separately using changes of variables.Source: §C.3 · pp. 29–30
• Under exponential-tailed losses, the proof bounds gradient and remainder terms using eventual margin growth, Cauchy–Schwarz, and integrability from Lemma 16.For sufficiently large t, loss derivatives are controlled by exponential margin terms, while the relevant remainder contributions become integrable.Source: §C.3 · pp. 31–32
• Collecting all cases yields either nonpositive, integrable, or f(t)∥r(t)∥ terms with f(t) ∈ L1, proving Lemma 14.The case analysis separates signs of x_n^⊤r(t) and applies asymptotic bounds to each resulting term.Source: §C.3 · pp. 35–38

C.4 Proof of the existence and uniqueness of the solution to eqs. 63-64

• The equations are reduced to coordinates in the span of X_S1, with orthogonal coordinates vanishing and the first basis direction aligned with ˆw1.An orthonormal basis separates the rank-K data span from its orthogonal complement, reducing the problem to coordinates s1,…,sK.Source: §C.4 · p. 39
• For fixed remaining coordinates, the first coordinate has a unique solution, while critical points of E(s2,…,sK) solve the reduced equations and are global minima by convexity.The function E is a positive linear combination of convex exponentials because β_n > 0.Source: §C.4 · pp. 39–40
• E(s2,…,sK) is coercive because every nonzero direction makes at least one exponent diverge, so continuity guarantees a finite global minimum.The rank condition ensures that no nonzero direction is orthogonal to all data vectors, forcing divergence along every direction at infinity.Source: §C.4 · p. 40
• The Hessian is strictly positive definite because every nonzero coordinate direction affects at least one data projection, making E strictly convex and yielding a unique solution ˜w1.Strict convexity establishes uniqueness after existence has been shown.Source: §C.4 · p. 40

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

• The constructed ˇw_k,m satisfies the constraints in equation 113 because its projected components obey the required annihilation relations.The relations P̄_mP_m = 0 and P̄_{m+k}x_n = 0 imply P_{k−1}Q_kv = 0 and P̄_kQ_kv = 0.Source: §C.5 · p. 41
• Orthogonal projection decomposition separates the equations into independently solvable products on orthogonal subspaces.The projections satisfy the stated orthogonality relations, allowing each product to be solved separately.Source: §C.5 · p. 41
• The solution ˇw_k,m to equations 65–66 exists uniquely for every k = 1, …, m.The proof reduces the system to orthogonal projection subspaces and shows the resulting d_k × d_k matrix is full rank.Source: §C.5 · pp. 41–42

C.6 Proof of Lemma 15

• Lemma 15 follows by repeatedly expanding the recurrence φ^2(t + 1) ≤ z(t) + h(t)φ(t) + φ^2(t).The iteration replaces earlier φ^2 terms with ψ(t) = z(t) + h(t) until the claimed bound is obtained.Source: §C.6 · pp. 42–43
• The lemma holds with C2 = (φ(1) + C) exp(C) and C3 = exp(C).These constants result from the iterated recurrence bound.Source: §C.6 · p. 43

Appendix D. Calculation of convergence rates

• Appendix D calculates the various convergence rates referenced in Section 3.The supplied passage identifies the appendix’s scope but does not provide the individual rate formulas or values.Source: Appendix D · p. 44

D.1 Proof of Theorem 5

• Gradient descent admits w(t) = ˆw log t + ρ(t), with bounded residuals almost everywhere and O(log log(t)) corrections in measure-zero cases.The measure-zero correction is orthogonal to some support vectors and asymptotically has a positive angle with the others.Source: §D.1 · p. 44
• For all datasets, the training loss decays as L(w(t)) = O(t^-1), including measure-zero cases with an O(log log(t)) correction.The correction eventually has a non-negative angle with all support vectors.Source: §D.1 · p. 46
• For the exponential-loss example with x = (1, 0), the continuous-time dynamics give w1(t) = log(t + exp(w1(0))) and w2(t) = w2(0), demonstrating strictness of the non-degenerate upper bounds.The example uses initialization w2(0) > 0.Source: §D.1 · p. 46

D.2 Validation error lower bound

• The validation-loss calculation considers a validation sample k with ˆw⊤xk < 0, meaning the L2 max-margin vector misclassifies at least one validation example.V denotes the set of validation-sample indices.Source: §D.2 · p. 46

Appendix E. Softmax output with cross-entropy loss

• Under strict multiclass linear separability and a sufficiently small learning rate, softmax cross-entropy gradient descent drives the loss to zero, the weight norm to infinity, and every incorrect-class margin to infinity.These are the three conclusions stated in Lemma 19.Source: Appendix E · p. 47
• The multiclass theorem characterizes iterates as a logarithmically growing K-class SVM solution plus a bounded residual, assuming the associated equation has a solution.The theorem applies to any starting point and sufficiently small stepsize.Source: Appendix E · p. 47

E.1 Notations and Definitions

• The multiclass proof defines transformed examples, class-specific support-vector sets, vectorized weight matrices, and projections onto each class’s support-vector subspace.These definitions rewrite the K-class SVM constraints and organize the residual decomposition.Source: §E.1 · p. 48

E.2 Auxiliary Lemma

• The auxiliary lemma bounds the residual increment through (r(t + 1) − r(t))⊤r(t) ≤ C1t^-θ + C2t^-2 and provides a sharper bound under an additional condition.The stated constants and thresholds exist for sufficiently large t.Source: §E.2 · p. 49

E.3 Proof of Theorem 7

• The proof targets boundedness of r(t), which immediately implies boundedness of ρ(t) = r(t) + ˜w.This is the central objective of E.3.Source: §E.3 · p. 49
• The squared-norm recurrence expands into increment, cross, and prior-norm terms, allowing each contribution to be bounded separately.The expansion is given in equation (131).Source: §E.3 · p. 49
• Because the relevant t^-ν power series converges for ν > 1, the residual norm changes by less than ϵ0 for all sufficiently large t.This establishes eventual small increments in ∥r(t)∥.Source: §E.3 · pp. 49–50
• Combining the recurrence bounds yields a bounded series when θ > 1, and therefore establishes that ∥r(t)∥ is bounded.The conclusion completes the proof strategy for Theorem 7.Source: §E.3 · p. 50

E.4 Proof of Lemma 20

• Lemma 20 bounds the cross term (r(t + 1) − r(t))⊤r(t) by C1t^-θ + C2t^-2 for sufficiently large t.The estimate holds for some C1, t1 and all t > t1.Source: §E.4 · p. 50
• The lemma derives this estimate from w(t) = ˆw log(t) + ˜w + r(t), using the SVM-direction condition, gradient decay, and exponential inequalities.The proof expands the cross term over examples and classes before applying these bounds.Source: §E.4 · pp. 50, 51, 53
• The proof splits according to whether examples belong to the support set and whether projected residual components exceed fixed thresholds, controlling each case separately.For large projected components, terms become nonpositive; for small components, uniform constants provide the bound.Source: §E.4 · pp. 54–55
• These case bounds imply the existence of t1 > 0 and C1 such that the cross-term estimate in equation (128) holds.This is the concluding result of Lemma 20.Source: §E.4 · p. 55

• The experiment matches Fig. 1, except it uses stochastic gradient descent with a mini-batch size of 4.Source: Figure 4 · p. 55