1
$\begingroup$

Can somebody suggest me how to solve the following optimization problem? \begin{equation*} F(\mathbf{w},\xi)= \begin{aligned} & \underset{\mathbf{w,\xi}}{\text{minimize}} & & \frac{1}{2}\|\mathbf{w}-\mathbf{w}_{t-1}\|^2_2 + \beta \|\mathbf{w}\|_1 +\alpha C\xi\\ & \text{subject to} & & 1-y\mathbf{w}^T\mathbf{x} \leq \xi, \xi \geq 0 \end{aligned} \end{equation*}

An equivalent formulation is this: \begin{equation*} F(\mathbf{w},\xi)= \begin{aligned} & \underset{\mathbf{w,\xi}}{\text{minimize}} & & \frac{1}{2}\|\mathbf{w}-\mathbf{w}_{t-1}\|^2_2 +\alpha C\xi\\ & \text{subject to} & & 1-y\mathbf{w}^T\mathbf{x} \leq \xi, \xi \geq 0\\ & & &\|\mathbf{w}\|_1 \leq t \end{aligned} \end{equation*} Edit: I need solution techniques that works in online setting and suitable for large $\mathbf{w,x}$, say in millions.

$\endgroup$
  • $\begingroup$ You are missing a $beta$ and t in the objective in the equivalent formulation. When you say solve, do you mean a dedicated structure exploiting fast solver, in contrast to the obvious approach of just writing it as a standard convex quadratic program and use standard methods for that. $\endgroup$ – Johan Löfberg Sep 24 '15 at 10:42
  • $\begingroup$ unless you mean there exist a beta such that equivalence holds etc $\endgroup$ – Johan Löfberg Sep 24 '15 at 10:46
  • $\begingroup$ as per Mark Schmidt here notes on LASSO, $t$ and $\beta$ are inversely related. By solve, I mean approach to solve it in cases when $\mathbf{w,x}$ are in huge dimension, say, 1M. $\endgroup$ – chandresh Sep 24 '15 at 10:55
  • $\begingroup$ my concern is non-differentiability of $L1$ . Proxmial algorithms can be used but hinge loss constraint prohibits to use it, since, originally, they were proposed for unconstrained problems. I don't know if anybody is aware of using proximal algorithms under constraints. $\endgroup$ – chandresh Sep 24 '15 at 11:01
  • 1
    $\begingroup$ Actually, what does $w_{t-1}$ represent? It already looks very close to a proximal minimization form. $\endgroup$ – Michael Grant Sep 24 '15 at 15:26
3
$\begingroup$

You can (and should) replace $\alpha C$ with $\alpha$ and $yw^Tx$ with $w^Tx$. There are many irrelevant details in your problem which can be "normalized" away.

Now, a bit of algebra reveals that it is optimal to set (indeed the problem in $\xi$ is the minimization of a line with slope $\alpha > 0$) \begin{eqnarray} \xi = (1 - w^Tx)_+ := \max(1-w^Tx, 0), \end{eqnarray} and then minimize $E(w) := \frac{1}{2}\|w-w_{t-1}\|^2 + \beta\|w\|_1 + \alpha(1 - w^Tx)_+$ for $w$.

Now, $E(w)$ can be rewritten as \begin{eqnarray} E(w) = g(w) + f(Kw), \end{eqnarray} where $K := x^T \in \mathbb{R}^{1 \times n}$, $g(w) := \frac{1}{2}\|w-w_{t-1}\|^2 + \beta\|w\|_1$, and $f(z) := \alpha(1 - z)_+$.

Thus minimizing $E(w)$ is equivalent to solving the following minimax game \begin{eqnarray} \underset{z \in \mathbb{R}}{\text{maximize }}\underset{w \in \mathbb{R}^n}{\text{minimize }}\langle z, Kw\rangle + g(w) - f^*(z), \end{eqnarray} where $f^*(z) := \underset{s \in \mathbb{R}}{\text{max }}zs - f(s)$, the convex conjugate of $f$ (compute it as exercise). It's straightforward to compute the proximal operators of $g$ (this will be a shrinkage) and $f^*$ (this will be a projection onto a compact interval followed by a translation), and so you have all the ingredients (except minor details ...) needed to invoke the proximal primal-dual algorithms of Chambolle-Pock, for example.

Finally, because $g$ is strongly convex, you will converge in $\mathcal{O}(\|x\|/\sqrt{\epsilon})$ iterations for a tolerance $\epsilon > 0$ on the duality gap.

Below are some details (useful for actually implementing the algorithms).

Computing $f^*$ and $\textrm{prox}_{\lambda f^*}$. Using basic properties of convex conjugates, we have \begin{eqnarray} (z)_+^* = i_{[0, 1]}(z) \implies (-z)_+^* = i_{[0,1]}(-z) = i_{[-1,0]}(z) \implies (1 - z)_+^* = z + i_{[-1,0]}(z), \end{eqnarray} and so $f^*(z) = \alpha(\frac{z}{\alpha}) + \alpha i_{[-1, 0]}(\frac{z}{\alpha}) = \begin{cases}z, &\mbox{ if} -\alpha \le z \le 0,\\+\infty, &\mbox{ otherwise.}\end{cases}$

A direct computation then yields that any prox step $\lambda > 0$, we have \begin{eqnarray}\textrm{prox}_{\lambda f^*}(z) = \textrm{proj}_{[\lambda - \alpha, \lambda]}(z) - \lambda, \end{eqnarray} i.e a projection onto a compact interval followed by a translation.

$\endgroup$
  • $\begingroup$ Looks cool. Let me see how fast and good it is to apply proximal primal-dual algo. $\endgroup$ – chandresh Sep 25 '15 at 8:48
  • $\begingroup$ I hope this helps. Lemme know if you need more practical details. $\endgroup$ – dohmatob Sep 25 '15 at 13:18
  • $\begingroup$ why did you change the sign in $(1-z)^*_+=-z + i_{[-1,0]}(z)$? Earlier was correct as shown in 28 [slide ] (mit.edu/~9.520/spring07/Classes/svmwithfenchel.pdf) $\endgroup$ – chandresh Oct 1 '15 at 4:12
  • $\begingroup$ The earlier stuff was a misprint. Indeed, you have the identity (easy to prove): $h^*(z + a) \equiv h^*(z) - a^Tz$. $\endgroup$ – dohmatob Oct 1 '15 at 7:05
  • $\begingroup$ what about the proof given in slide 28 linked in my previous comment? $\endgroup$ – chandresh Oct 1 '15 at 7:12

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.