Implicit bias of gradient-based learning

If $X=0$, then $F(w)=\frac{1}{2}\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$ for every $w$, and the displayed update leaves $w_0=0$ fixed. Since $\mathrm{\parallel }w{\mathrm{\parallel }}_2\ge 0$ with equality only at $w=0$, this is the unique least-squares minimizer of minimum norm.

Suppose $X\mathrm{\ne }0$ and set $A=X^{\mathsf{T}}X$. The matrix $A$ is symmetric, and $⟨u,Au⟩=\mathrm{\parallel }Xu{\mathrm{\parallel }}_2^2\ge 0$, so its eigenvalues are nonnegative. By [F1], choose an orthonormal eigenbasis $u_1,\dots ,u_d$ with $A{u}_j={\lambda }_j{u}_j$ and $0\le {\lambda }_j\le {\lambda }_{\max }$. If ${\lambda }_j=0$, then $X{u}_j=0$ and $⟨X^{\mathsf{T}}y,u_j⟩=⟨y,X{u}_j⟩=0$; conversely, $Xz=0$ implies $Az=0$, so the zero-eigenvalue space is exactly $\ker X$.

For any increment $h$, expansion of the square gives $F(w+h)=F(w)+⟨X^{\mathsf{T}}(Xw-y),h⟩+\frac{1}{2}\mathrm{\parallel }Xh{\mathrm{\parallel }}_2^2$; since the last term is $O(\mathrm{\parallel }h{\mathrm{\parallel }}_2^2)$, $\mathrm{\nabla }F(w)=Aw-X^{\mathsf{T}}y$. Thus the iteration is $w_{k+1}=(I-\eta A)w_k+\eta X^{\mathsf{T}}y$, the fixed-step update in [F4]. Writing $c_{j,k}=⟨w_k,u_j⟩$ and $b_j=⟨X^{\mathsf{T}}y,u_j⟩$, for ${\lambda }_j>0$ induction on $k$ gives $c_{j,k}=\frac{1-(1-\eta {\lambda }_j{)}^k}{{\lambda }_j}{b}_j$; for ${\lambda }_j=0$, $c_{j,k}=0$ for all $k$.

The step bound gives $0\le 1-\eta {\lambda }_j<1$ for every positive eigenvalue, including the endpoint $\eta =1\mathrm{/}{\lambda }_{\max }$ where the largest-eigenvalue factor is zero. Hence $c_{j,k}\to b_j\mathrm{/}{\lambda }_j$ when ${\lambda }_j>0$, and the zero-eigenvalue coordinates remain zero. There are finitely many coordinates, so $w_k$ converges to a vector $w_{\mathrm{\infty }}$ satisfying $A{w}_{\mathrm{\infty }}=X^{\mathsf{T}}y$ and $w_{\mathrm{\infty }}\perp \ker X$.

By [F2], the normal equation $A{w}_{\mathrm{\infty }}=X^{\mathsf{T}}y$ makes $w_{\mathrm{\infty }}$ a least-squares minimizer, and every least-squares minimizer is $w_{\mathrm{\infty }}+z$ for some $z\in \ker X$. The orthogonality in step 3.1 yields $\mathrm{\parallel }{w}_{\mathrm{\infty }}+z{\mathrm{\parallel }}_2^2=\mathrm{\parallel }{w}_{\mathrm{\infty }}{\mathrm{\parallel }}_2^2+\mathrm{\parallel }z{\mathrm{\parallel }}_2^2$, with equality to $\mathrm{\parallel }{w}_{\mathrm{\infty }}{\mathrm{\parallel }}_2^2$ only for $z=0$. Thus $w_{\mathrm{\infty }}$ is the unique minimum-norm least-squares minimizer, in agreement with [F3].

Strict separability gives $u$ with $m_i(u)>0$ for every $i$. Since the sample is finite, $a:={\min }_i{m}_i(u)>0$. The scaled vector $u\mathrm{/}a$ satisfies $m_i(u\mathrm{/}a)=m_i(u)\mathrm{/}a\ge 1$, so the feasible set in [F1] is nonempty.

Put $R=\mathrm{\parallel }u\mathrm{/}a{\mathrm{\parallel }}_2$ and $K=\mathcal{F}\cap \{w:\mathrm{\parallel }w{\mathrm{\parallel }}_2\le R\}$. The set $K$ is nonempty by step 1.1 and is closed and bounded by [F1], so [F2] makes it compact and gives a minimizer $w_{\ast }$ of $\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}_2^2$ on $K$. Every feasible vector outside the radius-$R$ ball has norm greater than $R$, while $u\mathrm{/}a\in K$ has norm $R$; therefore no such vector improves on $w_{\ast }$. Hence $w_{\ast }$ is a global minimizer on $\mathcal{F}$.

If two distinct feasible minimizers $w,z$ existed, their midpoint would remain feasible because each $m_i$ is linear. But ${\parallel \frac{w+z}{2}\parallel }_2^2=\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}_2^2+\frac{1}{2}\mathrm{\parallel }z{\mathrm{\parallel }}_2^2-\frac{1}{4}\mathrm{\parallel }w-z{\mathrm{\parallel }}_2^2$ is strictly smaller than their common minimum value, a contradiction. Therefore the minimizer is unique.

The exponential loss has $-{\mathrm{\ell }}_{\exp }^{}(u)=e^{-u}$. For $u>1$, $0<1-e^{-u}<1$, so $(1-e^{-u})e^{-u}\le e^{-u}\le (1+e^{-u})e^{-u}$, which is exactly the pair of bounds in [F1].

The logistic loss has $-{\mathrm{\ell }}_{\log }^{}(u)=e^{-u}\mathrm{/}(1+e^{-u})$. For $r=e^{-u}\in (0,1)$, $1-r\le 1\mathrm{/}(1+r)\le 1$ because $1-(1-r)(1+r)=r^2\ge 0$ and $1\le 1+r$. Multiplying by $r>0$ gives $(1-e^{-u})e^{-u}\le -{\mathrm{\ell }}_{\log }^{}(u)\le e^{-u}\le (1+e^{-u})e^{-u}$ for $u>1$, as required by [F1].

If $q$ is differentiable at $x$, then $q$ is differentiable at $cx$ and the homogeneity identity gives $Dq(cx)[v]=c^{L-1}Dq(x)[v]$ for every direction $v$, by writing $q(cx+tv)=c^{L}q(x+(t\mathrm{/}c)v)$ and taking the difference-quotient limit as $t\to 0$.

At every differentiability point $x\mathrm{\ne }0$, differentiating $q(cx)=c^{L}q(x)$ with respect to $c$ at $c=1$ gives $⟨x,\mathrm{\nabla }q(x)⟩=Lq(x)$.

Conversely, differentiability at $cx$ implies differentiability at $x$ by applying the same argument with scale $1\mathrm{/}c$. Thus scaling by $c$ bijects the differentiability points and sends each gradient to $c^{L-1}$ times that gradient. Taking all gradient limits as $x\to \theta$, and then their closed convex hull as in [F1], proves ${\mathrm{\partial }}^{\circ }q(c\theta )=c^{L-1}{\mathrm{\partial }}^{\circ }q(\theta )$.

For any gradient limit $h={\lim }_k\mathrm{\nabla }q(x_k)$ with differentiability points $x_k\to \theta$, continuity of $q$ gives $⟨\theta ,h⟩=Lq(\theta )$. This identity is preserved by convex combinations and limits, so [F1] yields it for every $h\in {\mathrm{\partial }}^{\circ }q(\theta )$.

Put $f_i(\theta )=e^{-q_i(\theta )}$. At every differentiability point of $q_i$, ordinary differentiation gives $\mathrm{\nabla }{f}_i=-e^{-q_i}\mathrm{\nabla }{q}_i$. The exponential has nonzero derivative, so $f_i$ is differentiable exactly where $q_i$ is; passing to limits of gradients and then closed convex hulls as in [F1] gives ${\mathrm{\partial }}^{\circ }{f}_i(\theta )=-e^{-q_i(\theta )}{\mathrm{\partial }}^{\circ }{q}_i(\theta )$. Along an absolutely continuous arc, the assumed chain rule for $q_i$ and the one-variable chain rule give $(f_i\circ \theta {)}^{\mathrm{\prime }}=-e^{-q_i}⟨h_i,\dot{\theta }⟩$ for every $h_i\in {\mathrm{\partial }}^{\circ }{q}_i(\theta )$.

For any direction $v$, the limsup of the finite sum of difference quotients is at most the sum of their limsups, so ${\mathcal{L}}^{\circ }(\theta ;v)\le {\sum }_i{f}_i^{\circ }(\theta ;v)$. The right side is the support function of the nonempty compact convex set $C:={\sum }_i{\mathrm{\partial }}^{\circ }{f}_i(\theta )$ by [F1]. If some $g\in {\mathrm{\partial }}^{\circ }\mathcal{L}(\theta )$ lay outside $C$, [F3] would give a direction $v$ with $⟨g,v⟩>{\sup }_{c\in C}⟨c,v⟩={\sum }_i{f}_i^{\circ }(\theta ;v)$, contradicting $⟨g,v⟩\le {\mathcal{L}}^{\circ }(\theta ;v)$. Thus ${\mathrm{\partial }}^{\circ }\mathcal{L}(\theta )\subseteq C$. Using step 1.1 expands this inclusion to the displayed weighted-margin form.

Summing the ordinary arc derivatives from step 1.1 gives the displayed derivative formula. For a negative Clarke gradient-flow arc, step 2.1 supplies $h_i$ with $\dot{\theta }={\sum }_i{e}^{-q_i}{h}_i$; substitution makes the derivative $-⟨\dot{\theta },\dot{\theta }⟩=-\mathrm{\parallel }\dot{\theta }{\mathrm{\parallel }}_2^2$.

Set $H_0={\mathbb{R}}^d$, $R_0=I$, and $T_0=\{1,\dots ,n\}$. Suppose $T_{m-1}$ is nonempty and the projected vectors $a_i=R_{m-1}{v}_i$, $i\in T_{m-1}$, are strictly separable inside $H_{m-1}$. Here $R_{m-1}$ is the orthogonal projector onto $H_{m-1}$. Let $h_m\in H_{m-1}$ be the unique minimum-norm vector with $h_m^T{a}_i\ge 1$. Existence and uniqueness follow by restricting to a nonempty compact norm sublevel of the closed feasible set and strict convexity, exactly as for the original hard-margin problem. Let $J_m=\{i\in T_{m-1}:h_m^T{a}_i=1\}$ and $D_m=T_{m-1}\setminus J_m$. There exist coefficients ${\alpha }_i\ge 0$, $i\in J_m$, with $h_m={\sum }_{i\in J_m}{\alpha }_i{a}_i\mathrm{.}$ To prove this dual representation from a proved finite-dimensional supplier, apply [F4] to the matrix with columns $a_i$, $i\in J_m$, and right-hand side $h_m$. If no nonnegative representation existed, the alternative would give a vector $y$ with $a_i^{\mathsf{T}}y\ge 0$ for active indices and $h_m^{\mathsf{T}}y<0$. Replace $y$ by its orthogonal projection into $H_{m-1}$, preserving these pairings. Then $h_m+ϵy$ preserves all active inequalities, preserves the finitely many inactive strict inequalities for sufficiently small positive $ϵ$, and decreases squared norm because its derivative at zero is $2h_m^{\mathsf{T}}y<0$. This contradicts minimality, proving the representation. Define $S_m$ as the union of the positive-coordinate supports of all such nonnegative representations, and $T_m=J_m\setminus S_m$. Because there are finitely many indices, averaging one witness representation for each index in $S_m$ gives a single representation $h_m={\sum }_{i\in S_m}{\alpha }_i{a}_i,{\alpha }_i>0(i\in S_m)\mathrm{.}$ In particular $S_m\mathrm{\ne }\mathrm{\varnothing }$. Set $E_m=\mathrm{span}\{a_i:i\in S_m\},H_m=H_{m-1}\cap E_m^{\perp }\mathrm{.}$ Let $Q_m$ be the orthogonal projector onto $E_m$, and let $R_m=R_{m-1}-Q_m$ be the orthogonal projector onto $H_m$. These are nested orthogonal projections by construction. Define $V_m=E_1\oplus \cdots \oplus E_m$ and its projector $P_m=I-R_m$. Thus $h_m\in E_m$, each $E_m\mathrm{\ne }\{0\}$, and distinct $E_m$ are orthogonal. If $T_m\mathrm{\ne }\mathrm{\varnothing }$, its next projected data $b_i=R_m{v}_i$ are strictly separable in $H_m$. To prove this crucial assertion, suppose not. The origin then belongs to the convex hull of the $b_i$: otherwise the nearest point $b\mathrm{\ne }0$ of that compact convex hull satisfies $b^T{b}_i\ge \mathrm{\parallel }b{\mathrm{\parallel }}^2>0$ for every $i$, a strict separator. Thus there are $c_i\ge 0$, not all zero, with ${\sum }_{i\in T_m}{c}_i{b}_i=0$. Consequently ${\sum }_{i\in T_m}{c}_i{a}_i$ lies in $E_m$ and can be written ${\sum }_{j\in S_m}{d}_j{a}_j$. For sufficiently small $ϵ>0$, each ${\alpha }_j-ϵd_j$ remains positive, and $h_m={\sum }_{j\in S_m}({\alpha }_j-ϵd_j)a_j+{\sum }_{i\in T_m}ϵc_i{a}_i\mathrm{.}$ This is an admissible nonnegative dual representation with a positive coefficient at an index of $T_m$, contradicting the definition of $S_m$. This proves strict separability, including that no next projected vector vanishes. Continue until $T_M=\mathrm{\varnothing }$. At each nonterminal stage a nonzero orthogonal subspace is removed, so $1\le M\le d$ and the procedure terminates. The sets $S_1,D_1,\dots ,S_M,D_M$ partition the indices. The following elementary identities will be used repeatedly: If $i\in S_k$, then $v_i\in V_k$, $v_i^T{h}_j=1$ for $1\le j\le k$, and $v_i^T{h}_j=0$ for $j>k$. If $i\in D_k$, then $v_i^T{h}_j=1$ for $j<k$, $v_i^T{h}_k>1$, and the later $v_i^T{h}_j$ are arbitrary finite constants. Indeed membership in the successive remaining sets gives the equalities before removal; $R_{k-1}{v}_i\in E_k$ gives $v_i\in V_k$ for $i\in S_k$; and orthogonality gives all later zero inner products. Also $h_1=w^{\ast }$. This construction deliberately uses spans of the projected support vectors. It never assumes that a product of unrelated raw-data projectors is an orthogonal projector.

Inductively choose $c_m\in E_m$ to solve $h_m=\eta {\sum }_{i\in S_m}\exp (-v_i^T{\sum }_{j=1}^m{c}_j)Q_m{v}_i\mathrm{.}$ For existence and uniqueness put $a_i=Q_m{v}_i=R_{m-1}{v}_i$ for $i\in S_m$, and ${\beta }_i=\eta \exp (-v_i^T{\sum }_{j<m}{c}_j)>0$. We need ${\sum }_{i\in S_m}{\beta }_i{e}^{-a_i^T{c}_m}{a}_i=h_m\mathrm{.}$ On $E_m$ consider ${\mathrm{\Phi }}_m(c)={\sum }_{i\in S_m}{\beta }_i{e}^{-a_i^{T}c}+h_m^{T}c={\sum }_{i\in S_m}({\beta }_i{e}^{-a_i^{T}c}+{\alpha }_i{a}_i^{T}c),$ using the strictly positive ${\alpha }_i$ from step 1.1. Every scalar function $s\mapsto {\beta }_i{e}^{-s}+{\alpha }_{i}s$ is bounded below and tends to $+\mathrm{\infty }$ as $s\to \pm \mathrm{\infty }$. The $a_i$ span $E_m$, so ${\max }_i\mathrm{\mid }{a}_i^{T}c\mathrm{\mid }\ge {\delta }_m\mathrm{\parallel }c\mathrm{\parallel }$ for some ${\delta }_m>0$, by compactness of the unit sphere. Therefore ${\mathrm{\Phi }}_m(c)\to \mathrm{\infty }$ when $\mathrm{\parallel }c\mathrm{\parallel }\to \mathrm{\infty }$: one scalar summand tends uniformly to infinity and all the others have finite lower bounds. Thus ${\mathrm{\Phi }}_m$ attains its minimum. Its Hessian satisfies $z^T{\mathrm{\nabla }}^2{\mathrm{\Phi }}_m(c)z={\sum }_{i\in S_m}{\beta }_i{e}^{-a_i^{T}c}(a_i^{T}z{)}^2>0(0\mathrm{\ne }z\in E_m),$ so the minimizer is unique. Its zero gradient is exactly the required equation. Put $c={\sum }_{m=1}^M{c}_m$ and $b_i=\eta e^{-v_i^{T}c}>0$. For $i\in S_m$, later $c_j$ are orthogonal to $v_i$, so the equation becomes $Q_m{\sum }_{i\in S_m}{b}_i{v}_i=h_m\mathrm{.}$ All factors of $\eta$ are thus included in $b_i$, and $c$ depends on the fixed step as expected.

Put $B_m={\sum }_{i\in S_m}{b}_i{v}_i$ and $A_k={\sum }_{i\in S_k}{b}_i{v}_i{v}_i^T$. Since $v_i\in V_k$ for $i\in S_k$, $A_k$ maps into $V_k$. Its diagonal block $Q_k{A}_k{\mathrm{\mid }}_{E_k}:E_k\to E_k$ is positive definite: for $z\in E_k\setminus \{0\}$, $z^T{A}_{k}z={\sum }_{i\in S_k}{b}_i((Q_k{v}_i{)}^{T}z{)}^2>0.$ For each $m>1$ define the vectors $d_{k,m}\in E_k$, $1\le k<m$, by ${\sum }_{k<m}{A}_k{d}_{k,m}=P_{m-1}{B}_m\mathrm{.}$ This system has exactly one solution. To see this without neglecting its cross blocks, start with $y=P_{m-1}{B}_m\in V_{m-1}$. For $k=m-1,m-2,\dots ,1$ solve the invertible diagonal-block equation $Q_k{A}_k{d}_{k,m}=Q_{k}y$, and replace $y$ by $y-A_k{d}_{k,m}$. Before that step $y\in V_k$ and afterwards $y\in V_{k-1}$, because $A_k{d}_{k,m}\in V_k$ and its $E_k$ component has been removed. The final residual is zero. The same backward argument applied to a homogeneous system proves uniqueness. This is a genuinely triangular solution; an $A_k{d}_{k,m}$ can have nonzero components in earlier $E_j$. Because $B_m\in V_m$ and $Q_m{B}_m=h_m$, these solutions give the exact cancellation identity $B_m-{\sum }_{k<m}{A}_k{d}_{k,m}=h_m(1\le m\le M),$ with the empty sum understood as zero. All $c_m$ and $d_{k,m}$ are fixed finite vectors.

For sufficiently large real $s$ let $L_0(s)=s$, $L_m(s)=\log L_{m-1}(s)$, and $a_m(s)=L_m^{\mathrm{\prime }}(s)=\frac{1}{s{\prod }_{j=1}^{m-1}{L}_j(s)},{ϵ}_{k,m}(s)=\frac{a_m(s)}{a_k(s)}=\frac{1}{{\prod }_{j=k}^{m-1}{L}_j(s)}(k<m)\mathrm{.}$ All iterated logs used here, including $L_M$, are positive and eventually increasing. Each $a_m$ and each ${ϵ}_{k,m}$ is positive, decreasing and tends to zero. The summability test used below is elementary. A product $s^{-{\nu }_0}{\prod }_{j=1}^q{L}_j(s{)}^{-{\nu }_j}$ is integrable and integer-summable on a sufficiently large tail if its first exponent differing from $1$ is greater than $1$. Indeed, if that first exponent occurs at $L_r$ (where $r=0$ denotes $s$), the substitution $y=L_r(s)$ removes all earlier factors and reduces the integral to $y^{-1-\delta }$ times finitely many real powers of iterated logs of $y$. Those later powers are $O(y^{\delta \mathrm{/}2})$, since $\log \log y=o(\log y)$, so the integral converges. The original function is eventually decreasing: its logarithmic derivative is dominated by the negative derivative of its earliest positive-power denominator. The integral test gives integer summability. This proves the needed form of source Lemma 16, including arbitrary signs of later exponents. In particular: ${\sum }_t\frac{a_k(t)}{L_j(t)}<\mathrm{\infty }(j<k),{\sum }_t\frac{a_k(t)}{L_k(t{)}^2}<\mathrm{\infty }\mathrm{.}$ For the first series the exponent at $L_j$ is $2$, while all earlier exponents are $1$; for the second the exponent at $L_k$ is $2$. Also ${\sum }_t\mathrm{\mid }{ϵ}_{k,m}(t+1)-{ϵ}_{k,m}(t)\mathrm{\mid }<\mathrm{\infty },$ by positive monotonicity and telescoping. Finally ${\sum }_t\mid L_m(t+1)-L_m(t)-a_m(t)\mid <\mathrm{\infty }\mathrm{.}$ Indeed the summand equals $a_m(t)-{\int }_t^{t+1}{a}_m(s)ds$, is nonnegative, and is at most $a_m(t)-a_m(t+1)$, which telescopes. These observations account explicitly for every discretization term.