Strong convexity inequality w.r.t. infinity norm $\lVert\cdot\rVert_{\infty}$

Question

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} \tag{P}\qquad \alpha \lVert x-x^*\rVert_{\infty} \leq \lVert\nabla f(x)\rVert_{\infty}, \end{equation} where $x^*$ is the unique global minimizer of $f$.

If the answer is no, what would be a sufficient condition to verify property \eqref{prop}?

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}\lVert x\rVert_{2}^2$ for every $n$.

Edit. Reminder:

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

Answer 1

I think it is not possible to do much better than $\frac{1}{\sqrt n}$. More precisely, I believe the best $\alpha$ is $\frac{1}{\sqrt n}$ whenever $n$ is a power of $2$, and therefore (since $\alpha$ is non-decreasing in $n$) at most $\frac{\sqrt{2}}{\sqrt n}$ in general.

Indeed, consider $f(x)=\frac 1 2 \|A^{-1} x\|_2^2$ for a linear invertible map $A$ on $\mathbf{R}^n$. If I understand correctly the definition of $1$-strongly convex function, $f$ is $1$-strongly convex iff the $2\to 2$ norm of $A$ is $\leq 1$. For this specific class of examples, your question reduces to "is there a constant independent of $n$ such that $\alpha \|A\|_{\infty \to \infty} \leq \|A\|_{2\to 2}$ for every linear map $A$ on $\mathbf{R}^n$". This is clearly false, for example for a Hadamard matrix: its $2 \to 2$ norm is $\sqrt{n}$ and $\infty\to \infty$ norm is $n$. The claim in the first paragraph of the answer therefore follows from the existence of Hadamard matrices of size $n$ whenever $n$ is a power of $2$.