Skip to main content
2 of 7
added 368 characters in body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Convergent (sub)gradient-type scheme to optimize smoothed 0/1 loss

Let $x_1,\ldots,x_n \in \mathbb R^d$ and $y_1,\ldots,y_n \in \{\pm 1\}$, and $\epsilon, h \gt 0$. Define $\theta(t) := Q((t-\epsilon)/h)$, where $Q(z) := \int_{z}^\infty \phi_h(z)\mathrm{d}z$ is the survival function of the Gaussian distribution $N(0,h^2)$ with density function $\phi_h$. Define $L:\mathbb R^d \to \mathbb R$ by

$$ L(w) := \frac{1}{n}\sum_{i=1}^n \theta(m_i(w)), $$

where $m_i(w) := y_i x_i^\top w$ defines the margin at the labeled data point $(x_i,y_i)$.

Question. Is there a convergent (sub)gradient-type scheme which can be used to optimize $L$ over the unit-sphere in $\mathbb R^d$ ?


Notice that since each $m_i$ is differentiable on $\mathbb R^d$ with gradient $\nabla m_i(w) = -y_ix_i$, the function $L$ is differentiable on $\mathbb R^d$ with gradient given by $$ \nabla L(w) = -\dfrac{1}{nh}\sum_{i=1}^n \phi_h( m_i(w)-\epsilon )y_ix_i $$

dohmatob
  • 6.9k
  • 1
  • 18
  • 76