# Strong convexity inequality w.r.t. infinity norm $\lVert\cdot\rVert_{\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$$: $$$$\label{prop} \tag{P}\qquad \alpha \lVert x-x^*\rVert_{\infty} \leq \lVert\nabla f(x)\rVert_{\infty},$$$$ 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$$.

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