0
$\begingroup$

Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ such that $$ \alpha \le v^\top \nabla^2 f(\theta) v \le L, $$ for all unit vectors $v \in \mathbb{R}^p$ with $\Vert v \Vert_0 \le 2s$. Consider the set of sparse vectors $D_s := \{v : \Vert v \Vert_0 \le s\}$ and define $$ \theta_0 := \arg\min_{\theta \in D_s} f(\theta). $$ Then I want to show that $\nabla f(\theta_0)^\top (\theta - \theta_0) \ge 0$ for any choice of $\theta \in D_s$. (I am not sure whether this statement is true or not.)

First approach: Let $P_s$ be the hard thresholding operator on the vector, i.e., $P_s(x):= \arg\min_{y \in D_s} \Vert y - x \Vert_2$. Thus, $P_s(x)$ only retains the top-$s$ elements of the vector $x$ in absolute value and sets everything else to 0. For example, $P_2((-2, 3, 1)^\top ) = (-2, 3, 0)^\top$. Let $S = \text{support}(\theta_0)$. Now We look at the limiting quotient $$ \lim_{t \to 0^+}\frac{f(P_s(\theta_0 + t(\theta - \theta_0))) - f(\theta_0)}{t}. $$

Note that for small enough choice of $t$, we will have $\text{support}(\theta_0 + t(\theta - \theta_0)) = \text{support}(\theta_0) = S$. Then, it follows that $\nabla f(\theta_{0,S})^\top (\theta_S - \theta_{0,S})\ge 0$. Here, the vector $\theta_S$ is defined as follows : $(\theta_S)_j = \theta_j \mathbb{1}(j \in S)$ for all $j \in [p]$. Therefore, we have $\nabla f(\theta_{0})^\top (\theta_S - \theta_{0})\ge 0$. But this is not enough as $\theta_S$ may not be $\theta$ due to a potential mismatch in support.

Second approach I. am trying to prove this by contradiction. Assume that $\nabla f(\theta_{0})^\top (\theta - \theta_{0})< -c$, where $c>0$. Let $v = -(\theta - \theta_0)/\Vert \theta - \theta_0\Vert_2$. Let $\theta_1 = P_s(\theta_0 - (\eta/L) v)$. Then by simple Taylor's expansion, we have $$ f(\theta_1)\le f(\theta_0) + \nabla f(\theta_0)^\top (\theta_1 - \theta_0) + \frac{L}{2} \Vert \theta_1 - \theta_0\Vert_2^2. $$ My goal is to find an $\eta>0$ such that $ \nabla f(\theta_0)^\top (\theta_1 - \theta_0) + \frac{L}{2} \Vert \theta_1 - \theta_0\Vert_2^2<0$. This would directly contradict that $\theta_0$ is the minimizer. I am trying to replicate a similar kind of analysis shown in the proof of Theorem 1 in this paper. However, tracking the support sets is becoming hard.

I would appreciate any kind of help or reference pointers. Thank you.

Update: The statement may not hold in general. Consider the function $f(\theta) = (\theta_1-1)^2 + (\theta_2-1)^2/2$, and consider the optimization problem $$ \min_{\Vert \theta\Vert_0 \le 1} f(\theta). $$ In this case, the minimizer is $\theta_0 = (1,0)$ and $\nabla f(\theta_0) = (0, -1)^\top$. Let $\theta = (0,1)^\top$. Then, $\nabla f(\theta_0)^\top (\theta - \theta_0) = -1<0$.

$\endgroup$

1 Answer 1

0
$\begingroup$

I don't think that this is true. Let us take $p = 2$, $s = 1$ and $f(x) = \frac12 \|x - (1,1)\|^2$. Then, $\theta_0 = (1,0)$ is a minimizer, but with $\theta = (0,1)$ we get $$ \nabla f(\theta_0)^\top (\theta - \theta_0) = (0,-1)\cdot(-1,1) = -1 < 0. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.