# Optimality condition for strongly convex function under sparsity constraint

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$$.

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.$$