Separable logistic and exponential gradient descent select the hard-margin direction

Write $v_i=y_i{x}_i$, $L(w)={\sum }_i\mathrm{\ell }(v_i^{T}w)$, $f=-{\mathrm{\ell }}^{\mathrm{\prime }}>0$ and $F(w)=w-\eta \mathrm{\nabla }L(w)$. The sample is nonempty and strictly separable. Choose a unit vector $u$ and $\gamma >0$ with $u^T{v}_i\ge \gamma$ for every $i$. For logistic loss, $0<{\mathrm{\ell }}^{\mathrm{\prime }\mathrm{\prime }}(s)\le 1\mathrm{/}4$, so $0⪯{\mathrm{\nabla }}^{2}L(w)⪯\frac{1}{4}X{X}^T$. Thus $\beta ={\lambda }_{\max }(X{X}^T)\mathrm{/}4$ is a global smoothness constant. The stated bound is exactly $\eta <2\mathrm{/}\beta$. For exponential loss use the stated ${\beta }_{\mathrm{l}\mathrm{o}\mathrm{c}}$ on the convex region containing the actual update segments, and put $\beta ={\beta }_{\mathrm{l}\mathrm{o}\mathrm{c}}$. Integration of the Hessian along the update segment (or the ordinary Lipschitz-gradient descent inequality) gives $L(w_{t+1})\le L(w_t)-\eta (1-\eta \beta \mathrm{/}2)\mathrm{\parallel }\mathrm{\nabla }L(w_t){\mathrm{\parallel }}^2\mathrm{.}$ Since $L\ge 0$, the gradient squares are summable and $\mathrm{\parallel }\mathrm{\nabla }L(w_t)\mathrm{\parallel }\to 0$. Meanwhile, $\mathrm{\parallel }\mathrm{\nabla }L(w_t)\mathrm{\parallel }\ge -u^T\mathrm{\nabla }L(w_t)={\sum }_{i}f(v_i^T{w}_t)u^T{v}_i\ge \gamma {\sum }_{i}f(v_i^T{w}_t)\mathrm{.}$ Hence every $f(v_i^T{w}_t)\to 0$. For both listed losses this forces $v_i^T{w}_t\to +\mathrm{\infty }$, and therefore $L(w_t)\to 0$. In particular $\mathrm{\parallel }{w}_t\mathrm{\parallel }\to \mathrm{\infty }$. No asymptotic directional information has been used in this step.

Here is the elementary comparison fact replacing the full source Lemma 14 case split. For a $C^2$ convex loss $L$, let $x,y$ be such that the Hessian has eigenvalues in $[0,B]$ at every point of the segment $[x,y]$, and suppose $\eta B\le 2$. The symmetric matrix $H_{x,y}={\int }_0^1{\mathrm{\nabla }}^{2}L(y+s(x-y))ds$ has eigenvalues in $[0,B]$, and $\mathrm{\nabla }L(x)-\mathrm{\nabla }L(y)=H_{x,y}(x-y)$. Therefore $\mathrm{\parallel }F(x)-F(y)\mathrm{\parallel }=\mathrm{\parallel }(I-\eta H_{x,y})(x-y)\mathrm{\parallel }\le \mathrm{\parallel }x-y\mathrm{\parallel }\mathrm{.}$ For logistic loss this applies globally with $B={\lambda }_{\max }(X{X}^T)\mathrm{/}4$ by step 1.1 and the stated step restriction. For exponential loss, no membership of $G_t$ in the assumed local-smoothness region is needed. Let $K={\max }_i\mathrm{\parallel }{v}_i{\mathrm{\parallel }}^2$. At every $z$, $\mathrm{\parallel }{\mathrm{\nabla }}^2{L}_{\exp }(z){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le {\sum }_i{e}^{-v_i^{T}z}\mathrm{\parallel }{v}_i{\mathrm{\parallel }}^2\le K{L}_{\exp }(z)\mathrm{.}$ Convexity gives $L_{\exp }(z)\le \max \{L_{\exp }(w_t),L_{\exp }(G_t)\}$ on the connecting segment $[w_t,G_t]$. Both endpoint losses tend to zero, by step 1.1 and [F4]. Thus on this segment the Hessian bound $B_t=K\max \{L_{\exp }(w_t),L_{\exp }(G_t)\}$ tends to zero. Since $\eta$ is fixed, $\eta B_t\le 2$ for every sufficiently large $t$. This proves eventual nonexpansiveness between the actual and comparison iterates, under exactly the stated exponential-loss hypothesis. Choose $T$ large enough for this property and define $r_t=w_t-G_t$. Then $\mathrm{\parallel }{r}_{t+1}\mathrm{\parallel }=\mathrm{\parallel }F(w_t)-F(G_t)-{\delta }_t\mathrm{\parallel }\le \mathrm{\parallel }{r}_t\mathrm{\parallel }+\mathrm{\parallel }{\delta }_t\mathrm{\parallel }\mathrm{.}$ Iteration yields ${\sup }_{t\ge T}\mathrm{\parallel }{r}_t\mathrm{\parallel }\le \mathrm{\parallel }{r}_T\mathrm{\parallel }+{\sum }_{t\ge T}\mathrm{\parallel }{\delta }_t\mathrm{\parallel }<\mathrm{\infty }\mathrm{.}$ This closes the residual estimate without first assuming any residual growth or sign bound. It is a complete substitute for source Lemmas 14 and 15 in this two-loss theorem. For completeness, the source's scalar recurrence follows directly: for nonnegative $\varphi ,h,z$ with ${\varphi }_{t+1}^2\le {\varphi }_t^2+h_t{\varphi }_t+z_t$ and $\sum h_t<\mathrm{\infty }$, use $h_t{\varphi }_t\le h_t(1+{\varphi }_t^2)\mathrm{/}2$ and iterate; ${\prod }_t(1+h_t\mathrm{/}2)\le \exp (\sum h_t\mathrm{/}2)$ bounds the product and gives ${\varphi }_{t+1}^2\le C_2+C_3{\sum }_{s\le t}{z}_s$, which is precisely the needed Lemma 15 estimate. By [F4], $G_t-{\sum }_{m=1}^M{h}_m{\log }^{\circ m}t$ is bounded. Thus the bounded residual above proves $w_t={\sum }_{m=1}^M{h}_m{\log }^{\circ m}t+O(1)\mathrm{.}$ In particular $w_t=w^{\ast }\log t+O(\log \log t),\frac{w_t}{\mathrm{\parallel }{w}_t\mathrm{\parallel }}⟶\frac{w^{\ast }}{\mathrm{\parallel }{w}^{\ast }\mathrm{\parallel }}\mathrm{.}$ The first convergence uses $h_1=w^{\ast }\mathrm{\ne }0$ and $\log \log t=o(\log t)$. Any component of the initialization orthogonal to the data span simply remains in the bounded remainder; arbitrary initialization is covered.

Let $I:=\{i:(w^{\ast }{)}^T{v}_i=1\}$ be the first-stage active set. It is nonempty: otherwise the finite minimum $\rho :={\min }_i(w^{\ast }{)}^T{v}_i$ would exceed $1$, and $w^{\ast }\mathrm{/}\rho$ would be feasible with smaller norm. Let $A$ have columns $v_i$ for $i\in I$. If no $\alpha \ge 0$ satisfied $A\alpha =w^{\ast }$, [F7] would give $y$ with $v_i^{T}y\ge 0$ for every $i\in I$ and $(w^{\ast }{)}^{T}y<0$. For each inactive $i$, $(w^{\ast }{)}^T{v}_i-1>0$; because there are finitely many constraints, choose $ϵ>0$ small enough that $w^{\ast }+ϵy$ still satisfies every inactive constraint and that $2ϵ(w^{\ast }{)}^{T}y+{ϵ}^2\mathrm{\parallel }y{\mathrm{\parallel }}_2^2<0$. The active constraints remain satisfied because $v_i^{T}y\ge 0$. This gives a feasible vector of smaller norm, contradicting minimality. Therefore there is a nonnegative representation $w^{\ast }=A\alpha$.

Fix the labels. Multiplication $x_i\mapsto v_i=y_i{x}_i$ preserves Lebesgue-null sets. Outside a finite union of proper polynomial zero sets, every set of at most $d$ of the $v_i$ is linearly independent and no $d+1$ of them lie in one affine hyperplane. The latter excludes the determinant-zero conditions for the augmented rows $(v_i^T,1)$; the former excludes the appropriate Gram determinant-zero conditions. Each relevant polynomial is nonzero, as witnessed by coordinate vectors for the linear conditions and affinely independent points for the affine conditions. By [F6] under [A1], each of these proper polynomial zero sets is Lebesgue null, and so is their finite union. This is the only inherited Countable Choice use. All first-stage active points lie in the hyperplane $(w^{\ast }{)}^{T}v=1$, so their number is at most $d$. Their column matrix $A$ has full column rank, and the dual representation is uniquely $\alpha =(A^{T}A{)}^{-1}\mathbf{1},$ because $A^T{w}^{\ast }=\mathbf{1}$ and $w^{\ast }=A\alpha$. Each coordinate of this rational function has a polynomial numerator not identically zero: for orthonormal columns, every coordinate is $1$. After excluding these finitely many additional numerator-zero sets for every possible active subset, every active multiplier is nonzero. Since the KKT multipliers are nonnegative, they are all positive. Thus every first-stage active index has a simultaneously positive dual representation; [F4] gives $M=1$, and the expansion of step 2.1 gives $w_t=w^{\ast }\log t+O(1)$. Restricting this null-set conclusion to the open set of strictly separable arrays proves exactly the almost-everywhere clause in the Statement. This is a consequence, not an extra general-position assumption on the all-data result.

The qualification that further logarithms may occur is realized by a concrete separable example. In ${\mathbb{R}}^q$ take $n=q$ and $v_i=e_1+\cdots +e_i(1\le i\le q)\mathrm{.}$ The first hard-margin vector is $e_1$: the first constraint forces $w_1\ge 1$ and $e_1$ satisfies all constraints. Its unique dual representation has only the first coefficient positive, because comparison of coordinates from $q$ down to $2$ forces all later coefficients to vanish. After projecting off $e_1$ the same argument applies to the remaining staircase vectors. Consequently $S_m=\{m\}$ and $h_m=e_m$ through $M=q$. Under either stated GD regime the proved expansion is $w_t=e_1\log t+e_2\log \log t+\cdots +e_q{\log }^{\circ q}t+O(1)\mathrm{.}$ For $q=2$ this gives a nonzero $\log \log t$ residual, and larger $q$ give further nonzero iterated-log coefficients. This also confirms that replacing the all-data proof by only its almost-everywhere branch would lose an actual part of the stated theorem.