Recursive hard-margin comparison trajectories have summable descent defects

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.

Define, for all sufficiently large integer $t$, $G_t={\sum }_{m=1}^M{h}_m{L}_m(t)+c+D(t),D(t)={\sum }_{k<m}{d}_{k,m}{ϵ}_{k,m}(t)\mathrm{.}$ The correction $D(t)\to 0$, and step 4.1 proves ${\sum }_t\parallel G_{t+1}-G_t-{\sum }_{m=1}^M{h}_m{a}_m(t)\parallel <\mathrm{\infty }\mathrm{.}$ We next prove, separately and in full, the analogous gradient estimate ${\sum }_t\parallel -\eta \mathrm{\nabla }L(G_t)-{\sum }_{m=1}^M{h}_m{a}_m(t)\parallel <\mathrm{\infty }\mathrm{.}$ First consider the exponential loss, for which $-\eta \mathrm{\nabla }L(G_t)={\sum }_i\eta e^{-v_i^T{G}_t}{v}_i$ exactly. Discarded nonsupport indices. If $i\in D_k$, write $p_i=v_i^T{h}_k>1$. The identities in step 1.1 give $e^{-v_i^T{G}_t}=e^{-v_i^{T}c-v_i^{T}D(t)}({\prod }_{j<k}{L}_{j-1}(t{)}^{-1})L_{k-1}(t{)}^{-p_i}{\prod }_{j>k}{L}_{j-1}(t{)}^{-v_i^T{h}_j}\mathrm{.}$ The first factor is bounded above because $D(t)\to 0$. In the remaining product the first exponent differing from $1$ is $p_i>1$. step 4.1 therefore shows ${\sum }_t{e}^{-v_i^T{G}_t}<\mathrm{\infty }$. This handles all nonsupport gradients, including arbitrary negative later margins. Retained indices. For $i\in S_k$, step 1.1 gives the exact factorization $\eta e^{-v_i^T{G}_t}=b_i{a}_k(t)e^{-v_i^{T}D(t)}\mathrm{.}$ Because $v_i\in V_k$, only the $d_{j,m}$ with $j\le k$ can contribute to $v_i^{T}D(t)$. Split $v_i^{T}D(t)=U_{i,k}(t)+W_{i,k}(t),$ $U_{i,k}(t)={\sum }_{m>k}{v}_i^T{d}_{k,m}{ϵ}_{k,m}(t),W_{i,k}(t)={\sum }_{j<k}{\sum }_{m>j}{v}_i^T{d}_{j,m}{ϵ}_{j,m}(t)\mathrm{.}$ All sums are finite. Since every extra iterated log in a product is eventually at least $1$, $\mathrm{\mid }{U}_{i,k}(t)\mathrm{\mid }\le \frac{C}{L_k(t)},\mathrm{\mid }{W}_{i,k}(t)\mathrm{\mid }\le C{\sum }_{j<k}\frac{1}{L_j(t)},\mathrm{\mid }{v}_i^{T}D(t)\mathrm{\mid }\le \frac{C^{\mathrm{\prime }}}{L_k(t)}\mathrm{.}$ The last bound follows because $L_j(t)\ge L_k(t)$ for $j<k$. It remains valid when $k=M$, where $U_{i,M}=0$. Taylor's theorem on a fixed neighborhood of zero gives $e^{-v_i^{T}D(t)}=1-U_{i,k}(t)+E_{i,k}(t),\mathrm{\mid }{E}_{i,k}(t)\mathrm{\mid }\le C({\sum }_{j<k}\frac{1}{L_j(t)}+\frac{1}{L_k(t{)}^2})\mathrm{.}$ Thus ${\sum }_t{a}_k(t)\mathrm{\mid }{E}_{i,k}(t)\mathrm{\mid }<\mathrm{\infty }$, by step 4.1. This bound includes every crossed correction with $j<k$, every product of two different corrections, and every higher Taylor remainder; none is silently omitted. Consequently, after summing over the finite sets of indices, $-\eta \mathrm{\nabla }{L}_{\exp }(G_t)={\sum }_{k=1}^M{a}_k(t)B_k-{\sum }_{k<m}{a}_k(t){ϵ}_{k,m}(t)A_k{d}_{k,m}+e_t,$ where ${\sum }_t\mathrm{\parallel }{e}_t\mathrm{\parallel }<\mathrm{\infty }$. Since $a_k{ϵ}_{k,m}=a_m$, the exact triangular identity in step 3.1 makes the right side ${\sum }_{m=1}^M{a}_m(t)(B_m-{\sum }_{k<m}{A}_k{d}_{k,m})+e_t={\sum }_{m=1}^M{h}_m{a}_m(t)+e_t\mathrm{.}$ This proves the gradient estimate for exponential loss. Logistic tail correction. Since $f_{\log }(s)=e^{-s}\mathrm{/}(1+e^{-s})$, $0\le e^{-s}-f_{\log }(s)=\frac{e^{-2s}}{1+e^{-s}}\le e^{-2s}\mathrm{.}$ For every index, $v_i^T{h}_1\ge 1$, and all later $L_m(t)$ are $o(\log t)$; therefore $v_i^T{G}_t\ge (1-o(1))\log t$. In particular, simultaneously for the finitely many indices and all sufficiently large $t$, $v_i^T{G}_t\ge \frac{3}{4}\log t$. Hence $e^{-2v_i^T{G}_t}\le t^{-3\mathrm{/}2}$ is summable. The difference between the logistic and exponential gradient vectors at $G_t$ is thus summable, proving the same gradient estimate for logistic loss. Combining the increment and gradient estimates proves the promised absolutely summable defect: ${\delta }_t:=G_{t+1}-F(G_t)=G_{t+1}-G_t+\eta \mathrm{\nabla }L(G_t),{\sum }_t\mathrm{\parallel }{\delta }_t\mathrm{\parallel }<\mathrm{\infty }\mathrm{.}$ Also $L(G_t)\to 0$, because every comparison margin tends to $+\mathrm{\infty }$.