Strong convexity inequality w.r.t $\|\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 is 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$.
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|$.

 A: Too long for a comment. I don't think that it works. Let $A \in \mathbb R^{n \times n}$ be symmetric with all eigenvalues in $(0,1]$.
Then, $f(x) := \frac12 x^\top A^{-1} x$ satisfies your requirements and $x^* = 0$. You are asking about
$$
\alpha \|x\|_\infty \le \|\nabla f(x)\|_\infty = \|A^{-1} x\|_\infty$$
for all $x$. Using $y = A x$, this is equivalent to
$$
\| A y \|_\infty \le \alpha \| y\|_\infty \qquad\forall y.$$
This, in turn, is equivalent to
$$
\| A \|_{\infty,\infty} \le \alpha^{-1}
$$
for the induced matrix norm and I don't think that it is possible.
Note that https://en.wikipedia.org/wiki/Matrix_norm#Examples_of_norm_equivalence gives the estimate
$$
\|A\|_{\infty,\infty} \le \sqrt{n} \|A\|_2$$
and this gives $\alpha = 1/\sqrt{n}$ (what you already have).
However, I suspect that this estimate for the matrix norm is sharp (also for symmetric matrices).
Thus, $\alpha = 1/\sqrt{n}$ is the best you can hope for.
A: Here is an idea for a counter-example.
First, let $v$ be a unit vector, $\|v\|_2=1$. Then
$\|vv^T\|_\infty = \|v\|_\infty\|v\|_1$.
Given $n$ it is possible (see below) to choose a unit vector $v_n \in \mathbb R^n$ such that $\|v_n\|_\infty\|v_n\|_1 =O( \sqrt n)$.
Now set $Q:=I_n + vv^T$, $f(x) = \frac12x^TQx$. Then $Q^{-1} = I_n - \frac12 vv^T$. Then using reverse triangle inequality
$$
\|Q^{-1}\|_\infty + \|-I_n\|_\infty \ge \frac12\|vv^T\|_\infty = O(\sqrt n).
$$
Using the vector $v_n$ from above to construct $Q$, we find $\|Q^{-1}\|_\infty = O(\sqrt n)$. Then there is a vector $d$ such that $\|d\|_\infty\le 1$ and $\|Q^{-1}d\|_\infty = O(\sqrt n)$.
Set $x:=Q^{-1}d$, $x^*=0$. Then
$
\|x-x^*\|_\infty = O(\sqrt n)$
but $\|\nabla f(x)\|_\infty = \|d\|_\infty =1$.

Here is the construction of $v_n$: set $v_n =\pmatrix{1 & \alpha & \dots & \alpha}^T$. For the choice $\alpha = \frac {n\sqrt n}{(n-1)^2}$ one has
$$
\frac{ \|v\|_1\|v\|_\infty}{\|v\|_2^2} = O(\sqrt n).
$$
