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



Strong convexity inequality w.r.t. infinity norm $\lVert\cdot\rVert_{\infty}$
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](https://en.wikipedia.org/wiki/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$.


