Homogeneous Clarke flow produces approximate margin-KKT points

The classifier restriction in [F7] is unnecessary for the following calculation, which we verify for the given margins. For $f_i=e^{-q_i}$, the smooth inverse $q_i=-\log f_i$ and ordinary differentiation give ${\mathrm{\partial }}^{\circ }{f}_i(x)=-e^{-q_i(x)}{\mathrm{\partial }}^{\circ }{q}_i(x)$ by the gradient-limit characterization [F1]. The finite-sum limsup inequality bounds ${\mathcal{L}}^{\circ }(x;w)$ by the support function of $C_x:={\sum }_i{\mathrm{\partial }}^{\circ }{f}_i(x)$, a nonempty compact convex set. If $g\in {\mathrm{\partial }}^{\circ }\mathcal{L}(x)\setminus C_x$, choose its nearest point $c\in C_x$ using [F6]. Convexity gives $⟨g-c,b-c⟩\le 0$ for $b\in C_x$, so the direction $g-c$ strictly separates $g$ from $C_x$, contradicting that support bound. Hence ${\mathrm{\partial }}^{\circ }\mathcal{L}(x)\subseteq C_x$. The flow inclusion therefore yields $\dot{\theta }={\sum }_i{e}^{-q_i}{h}_i$ for some $h_i\in {\mathrm{\partial }}^{\circ }{q}_i(\theta )$ almost everywhere. Along the locally absolutely continuous flow, the assumed margin chain rules and ordinary scalar chain rule give ${\mathcal{L}}^{\mathrm{\prime }}=-⟨{\sum }_i{e}^{-q_i}{h}_i,\dot{\theta }⟩=-\mathrm{\parallel }\dot{\theta }{\mathrm{\parallel }}_2^2$ almost everywhere.

For $t\ge t_0$, put $r=\mathrm{\parallel }\theta {\mathrm{\parallel }}_2$, $u=\theta \mathrm{/}r$, $\varphi =\mathcal{L}(\theta )$, $z=-\log \varphi$, $a_i=e^{-q_i(\theta )}$, $p_i=a_i\mathrm{/}\varphi$, and $\mu ={\sum }_i{p}_i{q}_i(\theta )$. By [F5], $r>0$, $\varphi \to 0$, and $\tilde{\gamma }(t)\ge {\gamma }_0:=\tilde{\gamma }(t_0)>0$. Since $\varphi <1$, every $q_i>0$ and $\mu \ge z>0$; indeed $q_i=z-\log p_i$. Homogeneity gives $q_{\min }(u)=q_{\min }(\theta )\mathrm{/}{r}^L=\bar{\gamma }(t)\ge {\gamma }_0$.

Local boundedness in [F1] and compactness of the unit sphere [F6] give a common bound $B$ for $\mathrm{\parallel }h{\mathrm{\parallel }}_2$ over all $u$ on that sphere, all $i$, and $h\in {\mathrm{\partial }}^{\circ }{q}_i(u)$. By the scaling identity in [F4], every $h_i\in {\mathrm{\partial }}^{\circ }{q}_i(\theta )$ therefore satisfies $\mathrm{\parallel }{h}_i{\mathrm{\parallel }}_2\le B{r}^{L-1}$.

At almost every $t\ge t_0$, choose the flow representation from [step 1.1], put $v=\dot{\theta }$, and define $\beta =⟨\theta ,v⟩\mathrm{/}(r\mathrm{\parallel }v{\mathrm{\parallel }}_2)$. Euler's identity [F4] gives $⟨\theta ,v⟩=L\varphi \mu >0$, so $v\mathrm{\ne }0$ and $0<\beta \le 1$. Differentiating $\tilde{\gamma }=z\mathrm{/}{r}^L$ yields ${\tilde{\gamma }}^{\mathrm{\prime }}=L(\mu \mathrm{/}({\beta }^2{r}^L)-z\mathrm{/}{r}^L)(\log r{)}^{\mathrm{\prime }}\ge L{\gamma }_0({\beta }^{-2}-1)(\log r{)}^{\mathrm{\prime }}$, since $\mu \ge z$ and $\mu \mathrm{/}{r}^L\ge \bar{\gamma }\ge {\gamma }_0$. Also $\mathrm{\parallel }{u}^{\mathrm{\prime }}{\mathrm{\parallel }}_2\le \mathrm{\parallel }v{\mathrm{\parallel }}_2\mathrm{/}r\le B\varphi r^{L-2}\le [B\mathrm{/}(L{\gamma }_0)](\log r{)}^{\mathrm{\prime }}$, because $(\log r{)}^{\mathrm{\prime }}=L\varphi \mu \mathrm{/}{r}^2$. Thus for $s<t$, $L{\gamma }_0{\int }_s^t({\beta }^{-2}-1)(\log r{)}^{\mathrm{\prime }}d\tau \le \tilde{\gamma }(t)-\tilde{\gamma }(s)$.

The normalized margin is $\bar{\gamma }(t)=q_{\min }(u(t))$ and converges to ${\gamma }_{\mathrm{\infty }}>0$ by [F5]. Continuity of $q_{\min }$ and the limit-point definition in the Statement imply $q_{\min }(u_{\ast })={\gamma }_{\mathrm{\infty }}$. Fix $\epsilon >0$. Choose an integer $k$ large enough that $B\mathrm{/}(L{\gamma }_{0}k)<\epsilon {\gamma }_0^{1\mathrm{/}L}\mathrm{/}4$ and $\sqrt{2}\mathrm{/}(k{\gamma }_0^{1\mathrm{/}L})<\epsilon$. Then choose $T$ so that for every $t\ge T$, ${\gamma }_{\mathrm{\infty }}-\tilde{\gamma }(t)\le L{\gamma }_0\mathrm{/}{k}^3$, $\mu (t)\ge z(t)>N\mathrm{/}(eL{\gamma }_0^{2\mathrm{/}L}\epsilon )$, and $\mathrm{\mid }\bar{\gamma }(t{)}^{-1\mathrm{/}L}-{\gamma }_{\mathrm{\infty }}^{-1\mathrm{/}L}\mathrm{\mid }<\epsilon \mathrm{/}2$. By the limit-point property, choose $s\ge T$ with $\mathrm{\parallel }u(s)-u_{\ast }{\mathrm{\parallel }}_2<\epsilon {\gamma }_0^{1\mathrm{/}L}\mathrm{/}4$. Since [F4] and [step 1.1] give $(\log r{)}^{\mathrm{\prime }}=L\varphi \mu \mathrm{/}{r}^2>0$ almost everywhere by step 3.1, absolute continuity makes $r$ strictly increasing; [F5] gives $r\to \mathrm{\infty }$. Thus there is a unique $s^{\mathrm{\prime }}>s$ with $\log r(s^{\mathrm{\prime }})-\log r(s)=1\mathrm{/}k$. Step 3.1 gives $L{\gamma }_0{\int }_s^{s^{\mathrm{\prime }}}({\beta }^{-2}-1)(\log r{)}^{\mathrm{\prime }}d\tau \le L{\gamma }_0\mathrm{/}{k}^3$. Hence some nonexceptional $t\in (s,s^{\mathrm{\prime }})$ has $\beta (t{)}^{-2}-1\le 1\mathrm{/}{k}^2$; otherwise the integral would be larger. Integrating the direction bound in step 3.1 gives $\mathrm{\parallel }u(t)-u_{\ast }{\mathrm{\parallel }}_2<\epsilon {\gamma }_0^{1\mathrm{/}L}\mathrm{/}2$. Therefore $\widehat{\theta }:=u(t)\mathrm{/}\bar{\gamma }(t{)}^{1\mathrm{/}L}$ is feasible and $\mathrm{\parallel }\widehat{\theta }-{\theta }_{\ast }{\mathrm{\parallel }}_2<\epsilon$.

At this time $t$, choose $h_i$ from [step 1.1], let $q_{\ast }=q_{\min }(\theta (t))$, and put ${\widehat{h}}_i=h_i\mathrm{/}{q}_{\ast }^{(L-1)\mathrm{/}L}\in {\mathrm{\partial }}^{\circ }{q}_i(\widehat{\theta })$ using [F4]. Set ${\lambda }_i=q_{\ast }^{(L-2)\mathrm{/}L}r{a}_i\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2\ge 0$. Then ${\sum }_i{\lambda }_i{\widehat{h}}_i=q_{\ast }^{-1\mathrm{/}L}r(v\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2)$ and $\mathrm{\parallel }\widehat{\theta }-{\sum }_i{\lambda }_i{\widehat{h}}_i{\mathrm{\parallel }}_2=\sqrt{2(1-\beta )}\mathrm{/}\bar{\gamma }(t{)}^{1\mathrm{/}L}\le \sqrt{2}\mathrm{/}(k{\gamma }_0^{1\mathrm{/}L})<\epsilon$. For complementarity, set $d_i=q_i(\theta (t))-q_{\ast }\ge 0$ and $A={\sum }_i{e}^{-d_i}\ge 1$; then $p_i=e^{-d_i}\mathrm{/}A$ and $\mu -q_{\ast }={\sum }_i{p}_i{d}_i\le N\mathrm{/}e$, since $x{e}^{-x}\le 1\mathrm{/}e$ for $x\ge 0$. Direct substitution gives ${\sum }_i{\lambda }_i(q_i(\widehat{\theta })-1)=\frac{\beta }{L\bar{\gamma }(t{)}^{2\mathrm{/}L}}\frac{\mu -q_{\ast }}{\mu }\le \frac{N}{eL{\gamma }_0^{2\mathrm{/}L}\mu }<\epsilon$. This is the $(\epsilon ,\epsilon )$-approximate KKT witness in [F3].