PaperlayerView exact revision on arXiv

Source-linked AI summary

Characterizing the implicit bias via a primal-dual analysis

Ziwei Ji, Matus Telgarsky

arXiv:1906.04540v3cs.LGmath.OCstat.ML

TL;DR

For linearly separable data, the paper studies which low-training-error solution gradient descent prefers and addresses gaps in prior results for general losses and step-size schedules. It characterizes the limiting direction through a dual optimization problem based on a smoothed margin, and establishes convergence rates for broad loss classes and for exponential or logistic loss under specified schedules.

  • Problem

    For linearly separable data, the question is which of the low-training-error solutions gradient descent prefers; most prior results rely on exponentially-tailed losses and do not prove tight rates across step-size schedules.

    Source: §1 · p. 1

  • Method

    The analysis associates each primal gradient-descent iterate with a dual variable and characterizes the limiting direction through a dual optimization problem corresponding to a smoothed margin.

    Source: §1 · p. 1, §2 · p. 3

  • Results

    For losses asymptoting to 0, normalized iterates converge to the direction given by the smoothed-margin dual problem at O(1/√t); for exponential or logistic loss, the chosen schedule gives O(ln(n)/t) rates for ℓ2 margin maximization and, for exponential loss, implicit bias.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The dual optimization problem gives a closed-form characterization of the implicit bias for a broad class of losses, beyond the exponentially-tailed losses on which most prior results rely.

    Source: §1 · p. 1

    Whether the analysis extends to stochastic gradient descent or accelerated gradient descent remains an open problem.

    Source: §6 · p. 11

Abstract

from arXiv · show

This paper shows that the implicit bias of gradient descent on linearly separable data is exactly characterized by the optimal solution of a dual optimization problem given by a smoothed margin, even for general losses. This is in contrast to prior results, which are often tailored to exponentially-tailed losses. For the exponential loss specifically, with $n$ training examples and $t$ gradient descent steps, our dual analysis further allows us to prove an $O(\ln(n)/\ln(t))$ convergence rate to the $\ell_2$ maximum margin direction, when a constant step size is used. This rate is tight in both $n$ and $t$, which has not been presented by prior work. On the other hand, with a properly chosen but aggressive step size schedule, we prove $O(1/t)$ rates for both $\ell_2$ margin maximization and implicit bias, whereas prior work (including all first-order methods for the general hard-margin linear SVM problem) proved $\widetilde{O}(1/\sqrt{t})$ margin rates, or $O(1/t)$ margin rates to a suboptimal margin, with an implied (slower) bias rate. Our key observations include that gradient descent on the primal variable naturally induces a mirror descent update on the dual variable, and that the dual objective in this setting is smooth enough to give a faster rate.

1 Introduction

The paper studies which low-training-error solution gradient descent selects, addressing prior work that mostly relies on exponentially-tailed losses and lacks tight rates across step-size schedules. For linear classifiers on linearly separable data, it characterizes implicit bias through a dual smoothed-margin problem and establishes convergence guarantees for broad losses and selected schedules.

1 Introduction

  • Gradient descent's implicit bias is motivated by the question of which low-training-error solution it prefers, given the link between low complexity and generalization.The paper also situates margin maximization and implicit bias in relation to dual analyses of boosting and iterative Bregman projection.Source: §1 · p. 1, §1.1 · p. 2
  • Prior studies of implicit bias often rely on exponentially-tailed losses, while this work focuses on linear classifiers and linearly separable data.The introduction frames tight rates across step-size schedules as another gap in prior results.Source: §1 · p. 1
  • For losses that asymptote to zero, normalized gradient descent iterates converge at O(1/√t) to a direction characterized by a dual optimization problem for a smoothed margin.The result covers exponentially-tailed and polynomially-tailed losses; Ji et al. (2020) give an asymptotic result without a closed-form characterization.Source: §1 · p. 1
  • With an aggressive step-size schedule, exponential and logistic losses yield an O(ln(n)/t) rate for ℓ2 margin maximization, and the exponential loss yields the same rate for implicit bias.Prior work either gives O(1/t) convergence to a suboptimal margin or an eO(1/t) rate to maximum margin.Source: §1 · pp. 1–2
  • Gradient descent on the primal variable induces a mirror-descent update on the dual variable, and dual smoothness supports faster convergence guarantees.The paper uses this analysis to establish O(1/t) margin-maximization and implicit-bias rates.Source: §1 · p. 2

1.2 Preliminaries and assumptions

  • The setup uses the ℓ2 norm and assumes linearly separable examples; its smoothed-margin function normalizes the dual variable.The stated loss assumptions include global smoothness, which the authors retain to simplify analysis and highlight the main ideas.Source: §1.2 · pp. 2–3

2 A primal-dual convergence analysis

The section derives a dual convergence analysis from gradient descent on the primal risk: the induced dual update is mirror descent. Smoothness of the dual objective yields an O(1/t) dual rate under a constant transformed step size, and the analysis also supports faster primal guarantees.

2 A primal-dual convergence analysis

  • The primal gradient-descent iterates induce a mirror-descent update on the dual variable, which the paper analyzes using the dual objective.The update is expressed through p_t = Zw_t and q_t = ∇ψ(p_t).Source: §2 · p. 3
  • Under Assumptions 1.1 and 1.2, for any t ≥ 0 and q ∈ dom ψ*, Theorem 2.2 states that if ˆη_t ≤ 1/β, its rate for ψ differs from the natural lower bound by an additive constant.Source: §2 · p. 4
  • Setting the transformed step size to 1/β gives an O(1/t) dual convergence rate, while smoothness of both primal and dual objectives underpins the faster guarantees.The paper contrasts this with Freund et al. (2013), who use a step size proportional to 1/√t and obtain an eO(1/√t) dual rate.Source: §2 · p. 4
  • The dual analysis connects its objective's minimum to the maximum margin and helps characterize implicit bias for general losses.For the exponential loss, the section points to an O(1/t) margin-maximization rate with constant step size.Source: §2 · p. 4

2.1 Proof of Theorem 2.2

  • The proof establishes that the dual objective is nonincreasing and uses a mirror-descent result to support the convergence argument.The analysis relies on smoothness of the dual objective with respect to the ℓ1 norm.Source: §2.1 · pp. 4–5

3 The dual optimal solution characterizes the implicit bias

The section characterizes gradient descent’s implicit-bias direction through a constrained dual optimum associated with a smoothed margin. It also establishes that the dual solution’s mapped direction is unique and that the proof’s objective values converge to the optimum.

3 The dual optimal solution characterizes the implicit bias

  • Unlike Ji et al. (2020), who give no closed-form characterization or convergence rate, this section characterizes implicit bias using the dual optimum.Ji et al. (2020) show that gradient-descent iterates and regularized solutions converge to the same direction.Source: §3 · p. 6
  • The implicit-bias direction is determined by Z^T qbar, where qbar minimizes f(q) subject to ψ*(q) ≤ 0.The theorem states this for the iterates under Assumptions 1.1 and 1.2, once ψ(Zw_t) ≤ 0, which holds for all sufficiently large t.Source: §3 · p. 6
  • The constraint ψ*(q) ≤ 0 arises naturally when qbar is derived as the convex dual solution of the smoothed margin.The paper notes that this condition may look technical in the definition of qbar.Source: §3 · p. 6

3.1 Proof of Theorem 3.1

  • The proof establishes a minimizer qbar, uniqueness of Z^T qbar across minimizers, and convergence of f(q_t) to f(qbar).The proof first establishes the lower bound f(q_t) ≥ f(qbar) and combines it with an upper bound to obtain convergence.Source: §3.1 · p. 7

4 1/t and 1/ ln(t) exponential loss rates with fast and slow steps

The section establishes faster margin and implicit-bias convergence guarantees for exponential-loss gradient descent under specified step-size regimes. The strongest rates use aggressive steps, while constant steps yield a slower but tight implicit-bias rate.

4 1/t and 1/ ln(t) exponential loss rates with fast and slow steps

  • The exponential loss is the main focus; the section also proves a margin-maximization rate for the logistic loss.The initialization is fixed at zero to simplify the bounds, with the analysis stated to extend to nonzero initialization.Source: §4 · p. 8
  • Constant normalized steps yield the strongest rates here, but their induced exponential-loss step sizes can grow exponentially and may not transfer to deep learning.The paper also analyzes constant ordinary step sizes, which are more common in prior work, and proves a tight O(ln(n)/ln(t)) bias rate in that regime.Source: §4 · p. 8

4.1 O(1/t) margin maximization rates

  • O(1/t) margin maximization is obtained for the exponential loss with a nonincreasing normalized step size and zero initialization.The proof uses a bounded error guarantee from the dual analysis.Source: §4.1 · pp. 8–9

4.2 Tight ln(n)/t and ln(n)/ ln(t) bias rates

  • O(ln(n)/t) implicit-bias convergence with constant normalized steps and O(ln(n)/ln(t)) with constant steps are both reported as tight.These tight bias rates are analyzed for the exponential loss.Source: §4.2 · p. 9
  • The tight bias-rate claim is illustrated by a constructed dataset in R2 with one example at (0.1, 0) and the others at (0.2, 0.2).The construction starts from w0 = (0, 0).Source: §4.2 · p. 10

5 Examples of losses satisfying Assumption 1.2

The section identifies losses satisfying Assumption 1.2 and gives conditions for convexity and smoothness of the associated function. These bounds support constant gradient-descent step sizes for the logistic and polynomial losses.

  • Exponential, logistic, and polynomial losses ℓ_poly,k for k > 0 satisfy Assumption 1.2.Source: §5 · p. 11
  • If ℓ′²/(ℓℓ′′) is increasing, then ψ is convex.Source: §5 · p. 11
  • For the exponential loss, β = 1; if ℓ′′ ≤ cℓ′, then β ≤ cn.Source: §5 · p. 11
  • For logistic and polynomial losses, bounded ℓ′ makes a constant step size sufficient for the stated condition in Theorems 3.1 and 2.2.Source: §5 · p. 11

6 Open problems

The section identifies extending the analysis beyond linear models and beyond gradient descent as open problems.

  • Extending the results to nonlinear models, including deep linear or homogeneous networks, remains open.Source: §6 · p. 11
  • Whether the analysis extends to stochastic gradient descent or accelerated gradient descent remains open.Source: §6 · p. 11

A Dual objective to the smoothed margin

The appendix constructs a primal-dual formulation for the smoothed margin by replacing a nonconvex normalized objective with a convex perspective. Its dual form connects to maximum-margin optimization for exponentially tailed losses.

B Omitted proofs from Section 2

The omitted proofs use smoothness and convexity properties to establish the dual update’s descent behavior.

C Omitted proofs from Section 3

The omitted proofs establish conditions for the dual optimization argument and show that its minimization over the specified sublevel set has a solution. They also address uniqueness of the direction induced by that minimizer.

C Omitted proofs from Section 3

  • The separability assumption supplies a vector u with ⟨u, −z_i⟩ ≥ γ for every training example.A separate assumption provides a positive constant c for the proof’s bounds.Source: C Omitted proofs from Section 3 · p. 16
  • The proof bounds the range of ∇ψ and hence the domain of ψ*, making the sublevel set S0 compact.It first shows the relevant coordinates of ∇ψ lie between 0 and 1.Source: C Omitted proofs from Section 3 · p. 16
  • Compactness of S0 and closedness of ψ* ensure that f attains a minimum over S0.The proof states that S0 is closed and contained in dom ψ* before concluding compactness.Source: C Omitted proofs from Section 3 · p. 16
  • The proof argues that two minimizers cannot induce different directions through Z^T q.It considers the midpoint of two minimizers in the convex set S0 and uses the stated property of σ.Source: C Omitted proofs from Section 3 · pp. 16–17

D Omitted proofs from Section 4

These omitted proofs supply technical bounds and existence arguments used in the Section 4 results. For logistic loss, the warm-start analysis bounds the time and iterate norm needed to reach its stated threshold.

D Omitted proofs from Section 4

  • For logistic loss, the lower-bound argument also applies because the proof states that ∥q_j∥_1 ≥ 1.The passage contrasts this with the exponential-loss case, where q_j belongs to the probability simplex.Source: D Omitted proofs from Section 4 · pp. 17–18
  • For logistic loss, Lemma E.8 bounds the first iteration t0 at which Lemma 5.4’s conditions hold by O((ln n)^2/γ^2), with ∥wt0∥ = O((ln n)/γ).Source: D Omitted proofs from Section 4 · p. 18
  • The proof establishes almost-sure existence of the vector v̄, then uses strong convexity over span(S⊥) to obtain a unique minimizer.The strong-convexity argument follows from the stated support-vector properties.Source: D Omitted proofs from Section 4 · pp. 18–19
  • The proofs bound the iterate norm using different controls: ∥w_t∥ ≤ t for η̂_j = 1, while η_j = 1 gives ∥w_t∥ = Θ(ln t).The latter bound is attributed to Soudry et al. (2017, Theorem 3).Source: D Omitted proofs from Section 4 · p. 23

E Omitted proofs from Section 5

The omitted proofs verify properties of ψ used by the main results, including convexity and smoothness. They also check a monotonicity condition for the logistic loss.

E Omitted proofs from Section 5

  • The proof establishes that ψ is β-smooth with respect to the ℓ∞ norm and sets β = cn.The smoothness check bounds the Hessian quadratic form for arbitrary ξ and v.Source: E Omitted proofs from Section 5 · p. 24
  • The proof checks that ϕ(z) = zℓ′(z)/ℓ(z) is increasing on (−∞, 0) for the logistic loss.The passage identifies this as the condition requiring verification for Theorem 5.1.Source: E Omitted proofs from Section 5 · p. 24
  • The proof verifies convexity of ψ for the exponential, logistic, and polynomial losses by checking the corresponding loss-dependent expressions.For the polynomial loss, it treats the ranges (−∞, 0] and (0, ∞) separately.Source: E Omitted proofs from Section 5 · p. 25

E.1 Warm start tools for the logistic loss

The warm-start proofs address the logistic loss’s initially poor smoothness by establishing improved smoothness on a sublevel set and bounding the iterations needed to enter it. The resulting warm start supplies conditions for the subsequent analysis.

E.1 Warm start tools for the logistic loss

  • Directly applying Theorem 3.1 to logistic loss incurs initial smoothness n and yields an n/t rate, while smoothness later improves.The preceding analysis requires L(Zw_t) ≤ ℓ(0)/(2e^2), which the warm-start argument handles.Source: §E.1 · pp. 25, 27
  • On the relevant sublevel set, ψ is 2-smooth with respect to the ℓ∞ norm.The proof uses this smoothness after establishing ψ(Zw_t) < 0.Source: §E.1 · pp. 26–27
  • Lemma E.8 states that, for logistic loss ln(1 + ez) with step size ηj = 1/(2R(wj)), the first iteration t with L(Zwt) ≤ ℓ(0)/(2e2) satisfies ψ(Zwt) ≤ 0.Source: §E.1 · p. 27

Related papers

Loading 1906.04540v3…