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

ca.classical-analysis-and-odesconvex optimizationfa.functional-analysismultivariable-calculusnorms

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

Best Answer

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

Related Question