# Characterizing the implicit bias via a primal-dual analysis

arXiv: https://arxiv.org/abs/1906.04540 · HTML: https://mlsanity.com/paper/1906.04540/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2019.

## Built on by (most cited first, 5 of 5)

- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Understanding Deflation Process in Over-parametrized Tensor Decomposition](https://mlsanity.com/paper/2106.06573/) (2021)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)
- [Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification](https://mlsanity.com/paper/2505.22359/) (2025)

## Abstract (arXiv)

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 ℓ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 ℓ2 margin maximization and implicit bias, whereas prior work (including all first-order methods for the general hard-margin linear SVM problem) proved widetildeO(1/√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.