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$
2
  • 1
    $\begingroup$ A more detailed description of $g$ could help $\endgroup$ Commented May 3, 2019 at 7:34
  • $\begingroup$ Why not use subgradient instead of gradient if $g$ is non-smooth? $\endgroup$ Commented May 6, 2019 at 10:15

1 Answer 1

Reset to default
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$
4
  • $\begingroup$ Could you give an example with Frank Wolf for a function with non trivial projection? $\endgroup$ Commented May 3, 2019 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$ Commented May 3, 2019 at 11:02
  • $\begingroup$ Is there a paper + code to show what you write above? $\endgroup$ Commented May 3, 2019 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$ Commented May 3, 2019 at 11:06

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.