1
$\begingroup$

I want to solve the optimization problem $$ \text{minimize }g(x) \quad \text{subject to} \quad \Vert x\Vert_{\infty}/\Vert x\Vert_{2} \le s $$ for $x\in\mathbb{R}^d$ and $s\in(0,\infty)$. The function $g:\mathbb{R}^d\to\mathbb{R}$ is (strongly) convex and Lipschitz smooth.

I know, that I could probably try to find saddle points of the corresponding Lagrangian but I would like to know, if there is a faster or more elegant way.

Do you know of a similar problem, that has been considered before?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ That problem was convex before, but not after adding that non-convex constraint. $\endgroup$
    – Mark L. Stone
    Commented Jul 20, 2021 at 22:47

1 Answer 1

Reset to default
5
$\begingroup$

As @Mark L. Stone commented, that constraint isn't convex (and therefore not a convex optimization problem). You could instead consider the different constraint: $$\|x\|_{\infty} \leq sM$$ $$\|x\|_{2} \leq M$$ which is convex. Note that the elements $x$ satisfying $\|x\|_{\infty} \leq s \|x\|_2$ and $\|x\|_2 \leq M$ satisfy this constraint. So the solution $\tilde{x}^*$ of this new optimization problem will do at least as well (in terms of the criteria $g$) as the solution $x^*$ of your nonconvex optimization problem as long as $\|x^*\|_{2} \leq M$ (of course, you might be overfitting).

From a practical perspective, I can't imagine there is any loss in using this constraint. Also, this type of constraint has been used in practice (e.g. Lasso/Ridge/ElasticNet regression with a lower/upper bound on the coefficients, bounded Lipschitz regression).

As a note, the nonconvex constraint is only interesting/well-defined if $s \in [1/\sqrt{d},1)$. This is because we always have $\|x\|_{\infty} \leq \|x\|_2$ and $\|x\|_2 \leq \sqrt{d}\|x\|_{\infty} \leq \sqrt{d}s\|x\|_2$. Also, it is not clear to me apriori that the original nonconvex constraint offers any kind of meaningful regularization.

Edit: Actually if you set $s=1/\sqrt{d}$ then the nonconvex constraint is equivalent to $\|x\|_2 = \|x\|_{\infty}$ which implies $x$ has only one nonzero element. So in that sense, it might give sparse solutions for small $s$. This is interesting as $\|\cdot\|_2$ regularization alone only shrinks and does not give sparse solutions.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hi Lars, thank you for your answer! I am particularly interested in the case where $s$ is small. When $s=1/\sqrt{d}$, then $x$ has to be a vector in which all entries are equal. So this constraint can be interpreted as an anti-sparsity constraint. Your proposal sounds interesting. If I underestimate $M$, then the constraint $\Vert x\Vert_2\le M$ will probably be active, right? Then $\Vert x\Vert_\infty \le sM = s\Vert x\Vert_2$, which means that the original constraint is satisfied. But this is not the case if I overestimate $M$. Do you know a good way to ensure $M$ is not overestimated? $\endgroup$
    – Philipp Trunschke
    Commented Jul 21, 2021 at 16:56
  • $\begingroup$ I don't think its anti-sparsity. $s = 1/\sqrt{d}$ implies $\|x\|_2 = \|x\|_{\infty}$. So assuming you defined $\|x\|_2 = \sqrt{\sum_i x_i^2}$, you must have exactly one entry equal to $\|x\|_{\infty}$. and the rest equal to zero (since one term contributes $\|x\|_{\infty}^2$ to the inside of the $\sqrt{}$). So this suggests it may have sparse solutions. $\endgroup$
    – Lars
    Commented Jul 21, 2021 at 17:02
  • 1
    $\begingroup$ If $M$ is small enough, It should be active. However, I am not sure if the proposed convex constraint gives sparse solutions ($\|x\|_2$ only shrinks coefficients). The $\|\cdot\|_{\infty}$ constraint may only force large coefficients to take the value $\pm sM$. Though there might be some ratio of $M/s$ that leads to sparse solutions, which would be interesting and novel. I actually think your proposed nonconvex constraint is interesting, assuming it does indeed give sparse solutions. Unfortunately, it will be a challenge to implement. To estimate $M$, I would use cross-validation. $\endgroup$
    – Lars
    Commented Jul 21, 2021 at 17:06
  • $\begingroup$ If $g$ is an empirical risk, then cross-validation seems to be a logical choice. For general $g$, however, it can not be used. A simple strategy would obviously be to solve the problem for different values of $M$. Increasing $M$ when the constraint is active and decreasing $M$ when the constraint is not active. Do you think there is a better way than a bisection method? $\endgroup$
    – Philipp Trunschke
    Commented Jul 21, 2021 at 17:32
  • $\begingroup$ Ah, good point. I had statistical applications on my mind. I don't see a better method than bisection. You could employ warm starts to maybe get faster convergence. $\endgroup$
    – Lars
    Commented Jul 21, 2021 at 17:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .