Skip to main content
1 of 4

Strong convexity inequality w.r.t infinity norm $||\cdot||_{\infty}$

Consider a twice differentiable 1-strongly convex function $f:\mathbb{R}^n \to \mathbb{R}$.

Is it true that there exists $\alpha>0$ independent of $n$ such that, for all $x \in \mathbb{R}^n$: \begin{equation} \label{prop} (P): \qquad \alpha ||x-x^*||_{\infty} \leq ||\nabla f(x)||_{\infty}, \end{equation} where $x^*$ is the unique global minimizer of $f$.

If the answer if no, what would be a sufficient condition to verify property (P)?

The reason why I am asking the question is that, using the equivalence of norms, it is simple to show that (P) holds with $\alpha = \frac{1}{\sqrt{n}}$. But I think it is possible to do better, but cannot prove it. For example, it holds with $\alpha = 1$ for $n=1$, and for $f=x\mapsto \frac{1}{2}||x||_{2}^2$ for every $n$.

Thanks in advance,

EDIT:

Reminder:

  • As $f$ is twice differentiable, it is 1-strongly convex iff $\nabla^2 f \succcurlyeq I_{n \times n}$.
  • $||x||_{\infty} \triangleq \max_{1 \leq i \leq n}|x_i|$.