KKT conditions and MFCQ for margin constraints

Let $q_1,\dots ,q_N:{\mathbb{R}}^d\to \mathbb{R}$ be locally Lipschitz functions, with $N,d\ge 1$. Write ${\mathrm{\partial }}^{\circ }{q}_i(\theta )$ for the closed convex hull of limits of ordinary gradients at differentiability points approaching $\theta$. The margin-constrained problem is to minimize $\frac{1}{2}\mathrm{\parallel }\theta {\mathrm{\parallel }}_2^2$ subject to $q_i(\theta )\ge 1$ for every $i$. A point $\theta$ is feasible when all these inequalities hold; an index $i$ is active at a feasible point when $q_i(\theta )=1$.

A feasible point $\theta$ is a Clarke KKT point if there are multipliers ${\lambda }_i\ge 0$ and vectors $h_i\in {\mathrm{\partial }}^{\circ }{q}_i(\theta )$ such that

$\theta ={\sum }_{i=1}^N{\lambda }_i{h}_i,{\lambda }_i(q_i(\theta )-1)=0(1\le i\le N)\mathrm{.}$

A feasible point satisfies the Mangasarian–Fromovitz constraint qualification (MFCQ) in margin form if there is a direction $v\in {\mathbb{R}}^d$ such that $⟨h_i,v⟩>0$ for every active $i$ and every $h_i\in {\mathrm{\partial }}^{\circ }{q}_i(\theta )$. If the same constraints are written $g_i(\theta ):=1-q_i(\theta )\le 0$, this condition is equivalently $⟨k_i,v⟩<0$ for every active $i$ and $k_i\in {\mathrm{\partial }}^{\circ }{g}_i(\theta )$, since ${\mathrm{\partial }}^{\circ }{g}_i(\theta )=-{\mathrm{\partial }}^{\circ }{q}_i(\theta )$.

A feasible point is an $(\epsilon ,\delta )$-approximate Clarke KKT point if there are ${\lambda }_i\ge 0$ and $h_i\in {\mathrm{\partial }}^{\circ }{q}_i(\theta )$ such that

${\parallel \theta -{\sum }_{i=1}^N{\lambda }_i{h}_i\parallel }_2\le \epsilon ,{\sum }_{i=1}^N{\lambda }_i(q_i(\theta )-1)\le \delta ,$

where $\epsilon ,\delta >0$. The second inequality measures total complementary-slackness error; every summand is nonnegative at a feasible point.

Clarke generalized gradient and Euclidean pairing

Training margins and homogeneity convention

Kaifeng Lyu and Jian Li, Gradient Descent Maximizes the Margin of Homogeneous Neural Networks, Appendix C.1–C.2

The margin form fixes the sign convention for lower constraints $q_i\ge 1$: a strict MFCQ direction increases every active margin. For upper constraints $g_i\le 0$, the corresponding active directional derivatives are negative. This sign convention is used in all local KKT arguments on this page.

The cited Lyu–Li Appendix C defines $g_i=1-q_i\le 0$ but states MFCQ using positive directional derivatives of $g_i$. This conflicts with its Lemma C.7: since ${\mathrm{\partial }}^{\circ }{g}_i=-{\mathrm{\partial }}^{\circ }{q}_i$, homogeneity gives $⟨h,\theta ⟩=-L{q}_i(\theta )$ for $h\in {\mathrm{\partial }}^{\circ }{g}_i(\theta )$, not $+L{q}_i(\theta )$. The margin-form convention above is sign-consistent, and the assigned homogeneous MFCQ lemma proves its positive-direction claim directly.