Source-linked AI summary
Characterizing Implicit Bias in Terms of Optimization Geometry
Suriya Gunasekar, Jason Lee, Daniel Soudry, Nathan Srebro
TL;DR
The paper investigates how optimization algorithms select among multiple solutions in underdetermined linear regression and separable classification, and whether that selection is determined by optimization geometry independently of hyperparameters. It characterizes implicit bias across mirror descent, natural gradient descent, steepest descent, AdaGrad, and matrix factorization, finding that robustness depends strongly on the loss family and algorithm.
Problem
The paper asks which global minimum an optimization algorithm reaches among many feasible solutions, and how that choice depends on geometry, loss, initialization, step-size, momentum, stochasticity, and adaptivity.
Method
The paper analyzes limit points or limit directions for generic optimization methods on linear models, then studies adaptive optimization and factorized matrix parameterizations.
Results
For unique-finite-root losses, mirror descent has a potential-based characterization under suitable conditions, while natural gradient and steepest descent are less robust; strictly monotone losses yield stronger steepest-descent and matrix-factorization characterizations.
Takeaways & Limitations
Implicit bias can often be linked to optimization geometry, but the characterization depends on the loss type and may change with initialization or finite-step hyperparameters.
Takeaways & Limitations
The paper leaves extensions to nonlinear neural networks, explicitly constrained linear models, multiple feasible zero-loss solutions, and multi-output losses for future work.
Abstract
from arXiv · showhide
We study the implicit bias of generic optimization methods, such as mirror descent, natural gradient descent, and steepest descent with respect to different potentials and norms, when optimizing underdetermined linear regression or separable linear classification problems. We explore the question of whether the specific global minimum (among the many possible global minima) reached by an algorithm can be characterized in terms of the potential or norm of the optimization geometry, and independently of hyperparameter choices such as step-size and momentum.
1. Introduction
The paper asks how optimization geometry and algorithmic choices determine which solutions are selected among many global minima. It develops characterizations for linear regression and classification across several optimization methods and loss families.
- Implicit bias selects special global minima in overparameterized models, influencing learned-model properties including generalization.
- The paper asks whether mirror descent, natural gradient descent, and steepest descent can be related to potentials, Riemannian metrics, or norms.
- For unique-finite-root losses, the analysis studies the limit point, while for strictly monotone losses with unattainable infima, it studies the limit direction.
- Mirror descent admits a robust limit-point characterization independent of step-size and momentum in the dual space, whereas finite-step natural gradient and primal-momentum variants break it.
- Steepest descent lacks the expected characterization for unique-finite-root losses, but obtains a precise limit-direction characterization for strictly monotone losses.
- The paper also studies AdaGrad and matrix factorization, extending its investigation beyond basic linear models and standard gradient descent.
2. Losses with a Unique Finite Root
For realizable underdetermined linear models with losses having unique finite roots, the paper characterizes how optimization geometry, initialization, and update choices determine the selected global minimum. Mirror descent has a divergence-minimization characterization under suitable convergence conditions, while momentum, natural-gradient step size, and steepest-descent geometry can break it.
- When N < d and the data are realizable, the loss has multiple global minima G satisfying the linear prediction constraints.
- Gradient descent converges to the global minimum closest to initialization in ℓ2 distance, because its iterates remain in the affine manifold generated by the data.
- For unique-finite-root losses, gradient descent’s implicit bias depends on initialization rather than step size, momentum, or mini-batch size.
- Mirror descent converges to the global minimum minimizing Bregman divergence Dψ(w, w(0)) from initialization, provided its iterates converge to a global minimizer.
- Starting mirror descent at argminw ψ(w) yields the global minimum minimizing ψ(w), and this characterization extends to dual momentum and constrained affine equality settings.
- The geometry-based characterization fails for primal momentum, finite-step natural gradient descent with non-quadratic potentials, and general-norm steepest descent.Primal momentum and finite-step natural gradient can depend on hyperparameters; steepest descent can fail even as step size approaches zero.
3. Strictly Monotone Losses
Strictly monotone losses are unattainable on separable data, so implicit bias is characterized through the limiting direction rather than a finite minimizer. For exponential loss, steepest descent selects a norm-dependent maximum-margin direction independently of initialization and sufficiently small step-size, whereas AdaGrad retains initialization and step-size dependence.
- 3. Strictly Monotone Losses: On separable data, strictly monotone losses have infimum zero but no finite minimizer, so iterates diverge and analysis uses their limit direction.The limit direction determines the classifier’s decision rule.
- 3.2 Steepest Descent: Steepest descent with exponential loss converges in direction to a maximum-margin solution under any norm.The theorem applies to separable datasets and bounded sufficiently small step-sizes.
- 3.2 Steepest Descent: This steepest-descent characterization is independent of initialization and sufficiently small step-size, unlike the squared-loss limit point.The result covers all initializations and bounded step-sizes satisfying the theorem’s condition.
- 3.2 Steepest Descent: The ℓ1-norm special case corresponds to coordinate descent and connects to AdaBoost’s implicit ℓ1 regularization.The paper presents coordinate descent on exponential loss as an alternative presentation of AdaBoost.
- 3.2 Steepest Descent: The optimization and ℓp regularization paths differ, but both converge in direction to the same maximum-margin separator in their respective limits.The limits are t →∞ for steepest descent and c →∞ for regularization.
- 3.3 AdaGrad: For AdaGrad with exponential loss, bounded adaptive matrices preserve non-vanishing effects from initialization and step-size in the limit direction.The paper concludes that AdaGrad’s implicit bias depends on w(0), G(0), and η.
4. Gradient descent on the factorized parameterization
The paper studies gradient descent after factorizing matrix predictors, where the factorized parameterization can induce a different implicit bias from direct optimization. For strictly monotone losses, under stated convergence conditions, the normalized factors approach stationary points associated with a nuclear-norm maximum-margin problem, though stronger predictor convergence remains open.
- 4. Gradient descent on the factorized parameterization: Matrix factorization rewrites the predictor as W = UV^⊤, yielding an equivalent objective with the same global minima over W.The paper also relates unconstrained factorization to symmetric positive-semidefinite factorization.
- Losses with a Unique Finite Root: For squared loss, factorized gradient descent’s implicit bias depends on initialization and step-size, so exact minimum-nuclear-norm selection requires infinitesimal initialization and step-sizes.Finite initialization and finite step-size do not yield the conjectured characterization exactly.
- Strict Monotone Losses: For strictly monotone exponential loss, Theorem 7 characterizes the normalized factor limit as a first-order stationary point of a non-convex maximum-margin problem.The result assumes full-rank initialization, finite step-sizes, vanishing loss, and directional convergence of updates and gradients.
- Strict Monotone Losses: Every global minimum of the maximum-margin factorized problem corresponds to a predictor minimizing the nuclear norm among positive-semidefinite linear classifiers with margin constraints.Without rank constraints, all second-order stationary points are global minima.
- Strict Monotone Losses: The paper expects the predictor direction W̄∞ = Ū∞Ū∞^⊤ to minimize the associated problem, but proving direct convergence of W(t) to W* remains future work.The stronger claim is stated as an expectation rather than an established theorem.
- Strict Monotone Losses: Theorem 7 additionally requires gradient directional convergence, beyond the necessary directional convergence of the factor iterates.Relaxing this extra condition is identified as future work.
5. Summary
The paper finds fundamentally different implicit biases for losses with finite roots versus strictly monotone losses, with characterizations depending on the optimization method and geometry.
- Finite-root losses: For finite-root losses, mirror descent has a limit-point characterization, but steepest descent lacks a succinct general-norm characterization.The mirror-descent result depends on the potential, while steepest descent remains uncharacterized even in the infinitesimal-step-size limit.
- Strictly monotone losses: For strictly monotone losses, steepest descent converges in direction to a maximum-margin separator within the unit ball of the chosen norm.This characterization is independent of initialization and sufficiently small step-size.
- Strictly monotone losses: Matrix factorization yields a maximum-margin limit direction with unit nuclear norm, independently of initialization and step-size.This contrasts with the squared-loss setting described in the paper.
- Strictly monotone losses: AdaGrad can produce a limit direction that depends on initial conditions, unlike the initialization-independent matrix-factorization result.The paper therefore does not find hyperparameter independence uniformly across optimization algorithms.
- Overall conclusions: The study characterizes linear-model implicit bias as minimum-norm or minimum-potential solutions and maximum-margin solutions among interpolating or separating solutions.The paper connects these special solutions to standard generalization analyses.
- Future work: Understanding implicit bias in nonlinear models, especially neural networks, remains an open direction requiring further work.The paper also identifies constrained optimization, multi-output losses, and optimization-to-regularization paths as future directions.
A.1 Proof of Theorem 1-1b
The appendix establishes mirror-descent convergence by showing that its iterates satisfy the relevant stationarity and feasibility conditions, including constrained and momentum variants.
- Theorem 1: Theorem 1 applies to realizable linear datasets, unique finite-root losses, strongly convex potentials, and step sizes whose iterates converge to a global minimizer.Under these conditions, the limit point is characterized by the potential and initialization.
- Constrained mirror descent: With realizable affine equality constraints, the limit minimizes Bregman divergence over the intersection of the global-minimum set and the constraint set.The constrained theorem requires a feasible zero-loss solution.
- Dual momentum: When initialized at a minimizer of the potential, dual-momentum mirror descent converges to the potential-minimizing global solution for arbitrary step-size and momentum sequences, provided it converges to a global minimum.Dual momentum is treated as a special case of a broader dual update family.
- Stochastic gradients: The same theorem extends to instancewise stochastic gradients because the proof uses the gradient’s membership in the data span.The stochastic-gradient extension follows the same argument as the deterministic result.
- Theorem 1: The unconstrained mirror-descent limit minimizes Bregman divergence to initialization over the set of global minima.The proof combines a stationarity condition inherited by every iterate with primal feasibility at convergence.
A.2.1 PRIMAL MOMENTUM AND NATURAL GRADIENT DESCENT
The appendix demonstrates that finite-step primal momentum can alter mirror-descent limits, whereas infinitesimal-step natural gradient descent follows the corresponding mirror-descent path after initialization-dependent updates.
- Primal momentum: After finitely many momentum updates, later iterates follow standard mirror descent from the altered dual state.This preserves a mirror-descent-style affine constraint in dual coordinates, but with the post-momentum initialization.
- Primal momentum: For any positive first-step primal momentum, the dual iterate can leave the data manifold, so the expected potential-minimization characterization fails.The example derives a non-data-span component proportional to log(1 + β1).
- Natural gradient descent: Natural gradient descent with infinitesimal step size follows the corresponding infinitesimal mirror-descent path on a convex problem.In the example, the path begins from the point produced by an initial finite natural-gradient step.
- Natural gradient descent: The initial natural-gradient update depends explicitly on the first step size through w(1) = w(0) − η1∇²ψ(w(0))^-1∇L(w(0)).Subsequent infinitesimal updates therefore inherit the altered starting point.
Appendix B. Steepest descent for strictly monotone losses
For exponential loss, steepest descent under any norm is analyzed through a generalized duality inequality that yields a maximum-margin limit direction in the corresponding norm geometry.
- Theorem 5: Theorem 5 considers separable data, exponential loss, arbitrary norms, all initializations, and bounded step sizes satisfying the stated upper bound.The result concerns the asymptotic direction of steepest-descent iterates.
- Theorem 5: The limit direction is the maximum-margin separator within the unit ball of the chosen norm.The theorem uses the dual norm to relate gradient magnitude and loss decay.
- Proof strategy: The proof proceeds through a generalized duality lemma, steepest-descent properties, and a final combination of those lemmas.The duality lemma establishes ∥∇L(w)∥⋆ ≥ γL(w) for every w.
- Generalized duality lemma: The generalized duality lemma extends the earlier ℓ1-norm result to arbitrary norms using the dual norm.Its proof invokes weak Fenchel duality and the definition of maximum norm-margin.
B.2 Properties of ∇L(w(t)) and L(w(t)) for steepest descent
For exponential-loss steepest descent, suitable finite step-sizes make the loss decrease monotonically, while the dual-norm gradient vanishes and iterates approach zero loss.
- B.2 Properties of ∇L(w(t)) and L(w(t)) for steepest descent: Steepest descent with finite step-sizes satisfying the stated upper bound produces a strictly decreasing loss sequence.The bound is η_t ≤ min{η_+, 1/(B^2L(w(t)))} under the lemma’s assumptions.
- B.2 Properties of ∇L(w(t)) and L(w(t)) for steepest descent: The dual-norm gradient converges to zero for any finite positive step-size sequence and in the continuous-time limit.The proof establishes summability of squared dual-norm gradients.
- B.2 Properties of ∇L(w(t)) and L(w(t)) for steepest descent: The iterates converge to a global minimum, with L(w(t)) tending to zero under the lemma’s steepest-descent conditions.This applies to exponential loss on the considered separable setting.
- B.2 Properties of ∇L(w(t)) and L(w(t)) for steepest descent: The monotonicity proof uses convexity, Taylor expansion, and a step-size bound controlling the update’s second-order term.The argument assumes the contrary and derives L(w(t+1)) ≤ L(w(t)), yielding a contradiction.
B.3 Remaining steps in the proof of Theorem 5
The proof continues by bounding steepest-descent margins and normalized iterates, then extends the convergence argument to adaptive steepest descent and AdaGrad.
- B.3 Remaining steps in the proof of Theorem 5: The steepest-descent updates admit an equivalent recursive form used to lower-bound the unnormalized margin.The proof then combines margin bounds to control the normalized margin.
- B.3 Remaining steps in the proof of Theorem 5: Duality relates the minimum margin to the dual-norm gradient, while bounded cumulative terms imply the normalized iterates stabilize.The proof separately controls the duality term and the initial-loss contribution.
- B.3 Remaining steps in the proof of Theorem 5: The adaptive steepest-descent analysis allows a time-dependent norm whose dual norm bounds every feature vector.This provides the setup for the adaptive update sequence.
- B.3 Remaining steps in the proof of Theorem 5: Under the adaptive conditions, if the loss tends to zero, the analysis obtains the corresponding asymptotic conclusion for the iterates.The result assumes bounded step-size and the stated initialization condition.
- B.3 Remaining steps in the proof of Theorem 5: AdaGrad is treated as a special case of adaptive steepest descent because its diagonal geometry evolves monotonically.The proof uses this monotonicity to invoke the adaptive convergence lemma.
D.1 Convergence of −∇L(w(t))
For almost all separable datasets, sequences minimizing exponential loss and converging directionally have gradients asymptotically dominated by their support vectors.
- D.1 Convergence of −∇L(w(t)): Almost-all dataset results assume signed features are independently drawn from a distribution absolutely continuous with respect to d-dimensional Lebesgue measure.The proof absorbs labels into the features without loss of generality.
- D.1 Convergence of −∇L(w(t)): For strictly monotone loss on separable data, minimizing sequences have loss tending to zero, positive margins, and diverging norm.When direction converges, the iterates decompose into a diverging directional component plus a smaller residual.
- D.1 Convergence of −∇L(w(t)): The support-vector set consists of samples attaining the smallest asymptotic margin, while the next-smallest margin is strictly larger.These margins determine the dominant and non-dominant terms in the gradient analysis.
- D.1 Convergence of −∇L(w(t)): For almost all datasets, the support-vector count is below d and the corresponding data submatrix has positive smallest singular value.This follows from the support-vector equations and a generic-rank argument.
- D.1 Convergence of −∇L(w(t)): The gradient proof splits support-vector and non-support-vector contributions, showing the latter are asymptotically negligible because their margins are larger.Consequently, every gradient limit point lies in the positive span of support vectors.
- D.1 Convergence of −∇L(w(t)): Every limit point of the normalized negative gradient belongs to the positive span of the support vectors.The conclusion follows after combining the two contribution bounds and reversing the label-absorption change of variables.
D.2 Proof of Theorem 7
Theorem 7’s proof analyzes gradient descent on a positive-semidefinite factorization through directional limits, dual certificates, and KKT stationarity conditions.
- D.2 Proof of Theorem 7: Theorem 7 considers gradient descent on a positive-semidefinite factorization with exponential loss, full-rank initialization, finite step-sizes, and vanishing predictor loss.The assumptions also require directional convergence of the factor and predictor sequences.
- D.2 Proof of Theorem 7: A normalized factor limit is identified as a scaled first-order stationary point of the associated non-convex optimization problem.The proof studies the directional limit of U(t) and the corresponding gradient sequence.
- D.2 Proof of Theorem 7: The factorization proof uses Frobenius, nuclear, and operator norms to characterize the limiting matrix geometry.These norms are explicitly distinguished in the proof’s notation.
- D.2 Proof of Theorem 7: The proof constructs nonnegative coefficients supported on the active data indices as a dual certificate satisfying dual feasibility and complementary slackness.The support restriction sets coefficients outside the active set to zero.
- D.2 Proof of Theorem 7: Stationarity requires the limiting factor to satisfy a scaled relation with the limiting gradient matrix.Equivalently, the columns of the limiting predictor lie in an eigenspace associated with one eigenvalue of the limiting gradient.
- D.2 Proof of Theorem 7: The proof establishes the scaled stationarity relation by analyzing factor updates, diminishing error terms, and the cumulative update sequence.The final scaling is D = 1/∥Z̄∞Ū∞∥.