2
$\begingroup$

Given the smooth hinge loss $L_\epsilon$ as follows

$L_\epsilon(y_i (w^T x_i + b)) = \begin{cases} 0 & y_i (w^T x_i + b) \\ \frac{(1-y_i (w^T x_i + b))^2}{2 \delta} & 1 - \delta < y_i (w^T x_i + b) \le 1 \\ 1 - y_i (w^T x_i + b) & y_i (w^T x_i + b) \le 1 - \delta \end{cases}$

and the objective function for a SVM, where I want to minimize with respect to $w, b$ and $x_i$ is the $i$th training example with $y_i \in {-1, 1}$, as

$f = \frac{C}{N} \sum_{i = 1}^N L_\epsilon(y_i (w^T x_i + b)) + \frac{1}{2} ||w||^2$

I want to compute the Lipschitz constant and the strongly convexity parameter of the above function so I can use the minimization algorithm by Nesterov to compute the optimal solution. These values are given by the largest and smallest eigenvalues of the Hessian, respectively.

I have computed the Hessian as follos

$\nabla^2 L_\epsilon = \begin{pmatrix} \frac{\partial^2L_\epsilon}{\partial w^2} & \frac{\partial^2L_\epsilon}{\partial w \partial b} \\ \frac{\partial^2L_\epsilon}{\partial w \partial b} & \frac{\partial^2L_\epsilon}{\partial b^2}\end{pmatrix}$

with

$\frac{\partial^2L_\epsilon}{\partial w^2} = \begin{cases} 0 & y_i (w^T x_i + b) \\ \frac{y_i^2 x_i x_i^T}{\delta} & 1 - \delta < y_i (w^T x_i + b) \le 1 \\ 0 & y_i (w^T x_i + b) \le 1 - \delta \end{cases}$

$\frac{\partial^2L_\epsilon}{\partial b^2} = \begin{cases} 0 & y_i (w^T x_i + b) \\ \frac{y_i^2}{\delta} & 1 - \delta < y_i (w^T x_i + b) \le 1 \\ 0 & y_i (w^T x_i + b) \le 1 - \delta \end{cases}$

$\frac{\partial^2L_\epsilon}{\partial w \partial b} = \begin{cases} 0 & y_i (w^T x_i + b) \\ \frac{y_i^2 x_i}{\delta} & 1 - \delta < y_i (w^T x_i + b) \le 1 \\ 0 & y_i (w^T x_i + b) \le 1 - \delta \end{cases}$

So the Hessian of $f$ becomes

$\nabla^2 f = \frac{C}{N} \nabla^2 L_\epsilon + 1$

But now I'm stuck. Can I, for given training examples $\{x_i\}_{i = 1}^N$ compute the Hessian taking the second case, or do I have something wrong in the Hessian?

$\endgroup$
1
$\begingroup$

The function $L_\epsilon$ is not strongly convex, because for $|b|$ or $\|w\|$ sufficiently large, it is locally linear, ie. $\nabla^2 L_\epsilon =0$. Therefore, the objective $f$ is not strongly convex with respect to $b$. It is strongly convex with respect to $w$ (with strong convexity constant 1), solely due to the $\frac{1}{2}\|w\|^2$ term.

Computing the Lipschitz constant exactly may be more difficult than the original problem. However, there are different ways to bound it. The Hessian of the objective can be written as: $$ \nabla^2 f = \begin{pmatrix} I & 0 \\ 0 &0 \end{pmatrix}+ \frac{C}{N \delta} \sum_{i} [1−\delta <y_i(w^T x_i+b)\le 1] \begin{pmatrix} x_i \\ 1 \end{pmatrix} \begin{pmatrix} x_i \\ 1 \end{pmatrix}^T $$ We can bound the spectral norm of the Hessian by noting that in the extreme case all the terms in the sum could be active: $$ \|\nabla^2 f\| \le 1+ \frac{C}{N \delta} \left \|\sum_{i} \begin{pmatrix} x_i \\ 1 \end{pmatrix} \begin{pmatrix} x_i \\ 1 \end{pmatrix}^T \right\| $$ This in turn can be bounded by quantities that are easier to compute. For example, applying the triangle inequality gives a crude bound: $$ \|\nabla^2 f\| \le 1+ \frac{C}{N \delta} \sum_{i=1}^N (\|x_i\|^2+1) $$ Or you can try bounding the spectral norm by the Frobenius norm: $$ \|\nabla^2 f\| \le 1+ \frac{C}{N \delta} \sqrt{\sum_{i=1}^N \sum_{j=1}^N (x_i^T x_j+1)^2} $$ However, I expect using these bounds in the basic Nesterov algorithm will result in overly conservative step sizes. The difficulty in (efficiently) estimating the Lipschitz constant is why it's useful to design methods which don't require knowing it up front.

$\endgroup$
  • $\begingroup$ So for the Nesterov algorithm I could choose the strongly convexity parameter $\mu = 0$, because the function is not strongly conex. However, at the end of the day another optimization scheme should be utilized. $\endgroup$ – Masala Nov 21 '13 at 9:23
  • 1
    $\begingroup$ The "basic" Nesterov algorithm shouldn't be applied to functions which are not strongly convex, but there are ways to modify it to make it work. In your case, you could add a term $\mu b^2/2$ to the objective and use continuation to find the optimum as $\mu \rightarrow 0$. $\endgroup$ – p.s. Nov 21 '13 at 9:57
  • $\begingroup$ May I ask, what do you exactly refer to by "Nesterov algorithm"? $\endgroup$ – Daniel Nov 26 '13 at 10:31
  • $\begingroup$ I meant the method from the 1983 paper "A method for solving a convex programming problem with convergence rate O(1/k^2)". Now that I reread it, I realize it doesn't require strong convexity just Lipschitz continuity of the derivative. $\endgroup$ – p.s. Nov 26 '13 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.