The implicit bias of gradient descent

The loss goes to zero and every margin diverges. Smoothness of $\mathcal L$, with $\beta_{\mathcal L}=\beta\sigma_{\max}^2(X)$, gives $\mathcal L(w(t+1))\le\mathcal L(w(t))-\eta(1-\tfrac{\beta_{\mathcal L}\eta}{2})\|\nabla\mathcal L(w(t))\|^2$, so $\sum_t\|\nabla\mathcal L(w(t))\|^2$ is finite. But for a separator $w_*$, $w_*^\top\nabla\mathcal L(w)=\sum_n\ell'(w^\top x_n)\,w_*^\top x_n$ is a sum of strictly negative terms, so each $\ell'(w(t)^\top x_n)\to0$, and since $\limsup_{-\infty}\ell'<0$, this forces $w(t)^\top x_n\to+\infty$. This justifies replacing $-\ell'$ by its exponential tail in all later steps.

Why the limit must be the SVM, and why the scale is $\log t$ (heuristic). Take $\ell(u)=e^{-u}$ in continuous time and suppose $w(t)=g(t)w_\infty+\rho(t)$ with $g\to\infty$, $\rho/g\to0$. The negative gradient $\sum_ne^{-g\,w_\infty^\top x_n}e^{-\rho^\top x_n}x_n$ is dominated by the points minimizing $w_\infty^\top x_n$, and since $w(0)$ becomes negligible, $w_\infty$ lies in their cone. Normalized to $\hat w$, this says $\hat w=\sum\alpha_nx_n$ with $\alpha_n\ge0$ and $\alpha_n=0$ unless $\hat w^\top x_n=1$: the KKT conditions of the SVM, sufficient because that problem is convex. The remaining gradient is $e^{-g}\sum_Se^{-\rho^\top x_n}x_n$, so matching $\dot g\,\hat w$ needs $\dot g\propto e^{-g}$, i.e. $g=\log t+\text{const}$. The proof plugs in $g=\log t$, $w_\infty=\hat w$ and bounds the residual.

An offset $\tilde w$ cancels the $1/t$ term, and generic data admit one. The increment of $\hat w\log t$ is about $\hat w/t$, and at $w=\hat w\log t+\tilde w$ the support vectors contribute $t^{-1}\eta\sum_Se^{-x_n^\top\tilde w}x_n$; choosing $\eta e^{-x_n^\top\tilde w}=\alpha_n$ makes the two match, which needs $\alpha_n>0$ and a solvable linear system for the $x_n^\top\tilde w$ (the columns of $X_S$ are generically independent). Genericity is a zero-set-of-polynomials argument: for almost every $X$ at most $d$ points lie on an affine hyperplane, so $|S|\le d$, and $\alpha_S=(X_S^\top X_S)^{-1}\mathbf 1$ is a rational function of $X_S$ that is not identically zero, so its zero set, over the finitely many candidate sets $S$, is null.

In continuous time the residual is bounded, because the support-vector terms can only decrease $\|r\|$. Let $r=w-\hat w\log t-\tilde w$, with $\sum_Se^{-x_n^\top\tilde w}x_n=\hat w$ (no $\eta$ in continuous time). Substituting the decomposition into the flow, $$\tfrac12\tfrac{d}{dt}\|r\|^2=\frac1t\sum_{n\in S}e^{-x_n^\top\tilde w}\big(e^{-x_n^\top r}-1\big)x_n^\top r+\sum_{n\notin S}t^{-\hat w^\top x_n}e^{-x_n^\top\tilde w}e^{-x_n^\top r}x_n^\top r.$$ The first sum is $\le0$ because $z(e^{-z}-1)\le0$, and the second is at most $Ct^{-\theta}$ by $ze^{-z}\le1$, integrable since $\theta>1$. So $r$ is bounded; the strict gap between support and non-support margins makes the error integrable.

In discrete time the same energy argument goes through up to summable errors. Expand $\|r(t+1)\|^2=\|r(t)\|^2+2(r(t+1)-r(t))^\top r(t)+\|r(t+1)-r(t)\|^2$; the squared increment is summable by the descent lemma. The cross term splits into a discretization term $O(t^{-2})$, the non-support term $O(t^{-\theta})$ of Step 4, and the sign-definite support-vector sum of Step 4 perturbed by the tail factors $1\pm O(t^{-\mu_\pm})$. A case split on $|z|=|x_n^\top r|$ shows the perturbation adds $O(t^{-1-1.5\mu_+})$ or $O(t^{-1-0.5\mu_-})$ when $z$ is tiny and nothing once $-z^2$ dominates, leaving the term $\le-C't^{-1}$ when $|z|\ge\epsilon_2$. So the cross term is at most $C_1t^{-\nu}$, $\nu=\min(\theta,1+1.5\mu_+,1+0.5\mu_-)>1$, and $\|r\|^2$ stays bounded.

When the support vectors span the data, $r(t)\to0$. Spanning puts every gradient in $\operatorname{span}X_S$, so $\bar P_1r$ is frozen and can be absorbed into $\tilde w$, leaving $r=P_1r$. If $\|P_1r\|\ge\epsilon_1$, then $\sigma_{\min}(X_S)>0$ gives some support vector $|x_n^\top r|\ge\epsilon_2$, and the last case of Step 5 makes the cross term $\le-C_2t^{-1}$, whose sum diverges, so $r$ re-enters the $\epsilon_1$-ball infinitely often. During an excursion the cross terms are negative, so $\|r\|^2$ can rise only by the tail of the summable squared increments, and letting $\epsilon_1\to0$ gives $r\to0$.

A zero-coefficient support vector forces a $\log\log t$ term. Such a point has an uncancelled gradient of order $t^{-1}e^{-x_n^\top\rho}$, which the residual can damp only by growing slowly in a new direction: $\rho$ grows until $e^{-x_n^\top\rho}\sim1/\log t$, leaving a contribution $\sim1/(t\log t)=\tfrac{d}{dt}\log\log t$. That is the $\hat w_2\log\log t$ term, and the recursion repeats at each level. The proof subtracts all levels with offsets and corrections, shows the cross term is at most $\kappa_1(t)\|r\|+\kappa_2(t)$ with $\kappa_i$ summable, and closes with a discrete Gronwall bound.

The rates follow by expanding the direction. The residual is $O(1)$, or $O(\log\log t)$, against a norm of order $\log t$, so $$\frac{w(t)}{\|w(t)\|}=\frac{\hat w}{\|\hat w\|}+\Big(I-\frac{\hat w\hat w^\top}{\|\hat w\|^2}\Big)\frac{\rho(t)}{\|\hat w\|\log t}+O\Big(\frac{1}{\log^2t}\Big).$$ The direction error is $O(1/\log t)$, and because its leading part is orthogonal to $\hat w$, $1-\cos$ is quadratic in it. The margin gap picks up $\min_{n\in S}x_n^\top\rho$ at order $1/\log t$, and the loss is $t^{-1}\sum_Se^{-\rho^\top x_n}$ plus a faster remainder. For degenerate data the $\log\log t$ part of $\rho$ slows the direction, but it eventually makes a nonnegative angle with the active support vectors, so the margin and loss keep their rates. One point $x=(1,0)$ with $w_2(0)\ne0$ attains the direction, angle and loss rates but not the margin rate (its gap is $\approx w_2^2/(2\log^2t)$); two support vectors with different $x_n^\top\rho$, e.g. $x_1=(1,2)$, $x_2=(1,-1)$, attain the $1/\log t$ margin rate. For Corollary 6, $\log(1+e^{-u})\ge-u$ gives validation loss $\ge-(\log t)\hat w^\top x_k-\rho^\top x_k=\Omega(\log t)$.