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][1]. However, tracking the support sets is becoming hard.

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


  [1]: https://arxiv.org/pdf/1410.5137.pdf