4

I am studying about SVM now. Then I came across the problem.

The dual optimization problem is as follows:

\begin{align*} &\max_\alpha~~~~~ W(\alpha) = \sum_{i=1}^{n} \alpha_i -\frac{1}{2}\sum_{i,j=1}^{n} y_i y_j \alpha_i \alpha_j \langle x_i, x_j \rangle \\ &s.t.~~~~~\alpha_i \geq 0 ~~~~\textrm{for } i=1,\cdots,n \\ & ~~~~~\sum_{i=1}^{n} \alpha_i y_i = 0 \end{align*}

This problem has some constraints. So I cannot apply the gradient descent.

There are other methods of optimization like Newton or SMO. However, I could not understand it at all. So I want to use Gradient Descent.

Then, I came up with some idea. It is to use lower bound. It means this: \begin{align*} &\max_\alpha~~~~~ W(\alpha) = \sum_{i=1}^{n} \alpha_i -\frac{1}{2}\sum_{i,j=1}^{n} y_i y_j \alpha_i \alpha_j \langle x_i, x_j \rangle - \lambda\left\|\sum_{i=1}^{n} \alpha_i y_i \right\|_1 \\ &s.t.~~~~~\alpha_i \geq 0 ~~~~\textrm{for } i=1,\cdots,n \end{align*}

Can I apply GD to this problem? I could not make a progress any more than this.

Could anyone help me?

Ferdi
  • 4,882
  • 7
  • 42
  • 62
yoyo
  • 979
  • 1
  • 6
  • 9

1 Answers1

1

This is a constrained optimization problem. Practically speaking when looking at solving general form convex optimization problems, one first converts them to an unconstrained optimization problem (e.g., using the penalty method, interior point method, or some other approach) and then solving that problem - for example, using gradient descent, LBFGS, or other technique. If the constraints have a "nice" form, you can also use projection (see e.g. proximal gradient method). There are also very efficient stochastic approaches, which tend to optimize worse, but generalize better (i.e., have better performance at classifying new data).

As well, your formulation doesn't appear to be correct. Generally one has $\alpha_i \leq C$ for hinge-loss SVM. If one uses e.g. square loss, then that constraint wouldn't be present, but your objective would be different.

MotiNK
  • 1,224
  • 6
  • 14
  • Thank you for your comment. But it has some points I could not understand. First, how can I decide whether the constraints have a “nice” form or not? Second, so if I want to use GD, I should convert the problem to an unconstrained. Is that right? – yoyo Aug 22 '18 at 14:27
  • "Nice" would depend on the method you want to use to solve the problem. For proximal gradient methods, this would mean that you have a cheap proximal operator for the convex set defined by your constraints. And yes, if you want to solve using GD, you would need to convert to an unconstrained version. Note though that you have vastly more efficient stochastic algorithms today; a not-so-recent but simple one is http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf - more recent ones take advantage of variance reduction in the stochastic procedure and converge faster – MotiNK Aug 22 '18 at 18:10
  • Let me summarize briefly, "PegasosMPB.pdf" is the simple optimization method and I can use proximal gradient methods instead for GD. Is this right? – yoyo Aug 22 '18 at 23:09
  • Pegasos is a fairly simple stochastic algorithm for solving SVM efficiently (in the primal form, not the dual). Proximal GD can be used instead of GD when you have an efficient proximal operator. At the bottom of the wiki page you for proximal gradient you can see links to Stanford courses on convex optimization. The topic is too broad to cover in the context of a question on this site. – MotiNK Aug 23 '18 at 06:54