0
$\begingroup$

I am currently in the situation where I have to find the $\arg\min$ of a convex objective function with a non-smooth convex constraint. More formally, this takes the following form

$$\beta^* := \arg \min_{g(\beta) \leq R} \frac{1}{2} \|\beta-z\|_2^2$$

where $g(\beta)$ is convex but non-smooth.

I looked around for a while but could not find an algorithm able to solve this kind of question. All algorithms I found assumed that $g(\beta)$ is smooth. Does anyone of you know an algorithm able to solve such problems?

$\endgroup$
  • 1
    $\begingroup$ A more detailed description of $g$ could help $\endgroup$ – Johan Löfberg May 3 at 7:34
  • $\begingroup$ Why not use subgradient instead of gradient if $g$ is non-smooth? $\endgroup$ – foxell May 6 at 10:15
1
$\begingroup$

The constraint $g(\beta)\leq R$ is equivalent to saying that $\beta$ is in the sublevel set of $g$. Since $g$ is convex, this is a convex set. If it easy to project onto this sublevel set then you can use projected gradient descent to solve this problem. If the sublevel set is not easy to project onto but is also compact then you can use Frank-Wolfe to solve this problem.

There is also a relationship/equivalence between a constraint of the form $g(\beta)\leq R$ and an unconstrained problem with a regularizer $\lambda\tilde{g}(\beta)$. If you write the problem in this way then you can use a number of splitting algorithms, for example forward-backward.

$\endgroup$
  • $\begingroup$ Could you give an example with Frank Wolf for a function with non trivial projection? $\endgroup$ – Royi May 3 at 10:58
  • $\begingroup$ Sure, consider a matrix completion problem with a nuclear norm constraint (i.e. a convexification of a low rank constraint). You want to minimize a quadratic norm (the difference between the observed matrix values and your prediction) but you want to do it while staying inside some nuclear norm ball of radius $\beta$. To project onto the nuclear norm ball requires one to compute a singular value decomposition and threshhold the singular values. To do a Frank Wolfe step one only needs to compute the leading left and right singular vectors, which can be computed much more efficiently (lanczos). $\endgroup$ – Tony S.F. May 3 at 11:02
  • $\begingroup$ Is there a paper + code to show what you write above? $\endgroup$ – Royi May 3 at 11:04
  • $\begingroup$ Section 7.2 of this paper: arxiv.org/abs/1901.01287 although it's a slightly more sophisticated problem (because the algorithm being demonstrated is more than Frank-Wolfe/Conditional gradient) although the code is not currently available. Basically, the svd takes $O(n^3)$ operations but computing the leading right and left singular vectors takes something like $O(n^2)$ operations iirc. There is even a scipy function just for leading singular vectors, docs.scipy.org/doc/scipy/reference/generated/… $\endgroup$ – Tony S.F. May 3 at 11:06

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.