Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by $$ \ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h). $$
Note that
- $\phi_{\gamma,h}$ is nonconvex.
- $\phi_{\gamma,h}$ is nondecreasing
- $\phi_{\gamma,h}$ is $O(1/h)$-Lipschitz continuous and its derivative is $O(1/h^2)$-Lipschitz.
Let $(x_1,y_1),\ldots,(x_n,y_n)$ be $n$ points in $\mathbb R^{d} \times \{\pm 1\}$, and for any $(w,b) \in \mathbb R^{d+1}$, define
$$ F(w,b) := \frac{1}{n}\sum_{i=1}^n\phi_{\gamma,h}(y_i(x_i^\top w - b)). $$
Fix $p \in [1,\infty]$ and let $B_p$ be the unit-ball in $\mathbb R^d$ w.r.t the $\ell_p$-norm. I'm particularly interested in the case $p \in \{1,2\}$.
Question. Is there a convergent gradient-based algorithm which minimizes $F$ over $B_p \times \mathbb R$, or even $B_p \times \{0\}$ ?
Ideally, an explicit rate of convergence would be provided too.
