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} \text{(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$, and for $f=x\mapsto \frac{1}{2}\|x\|_{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}$.
• $\|x\|_{\infty} \triangleq \max_{1 \leq i \leq n}|x_i|$.

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

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} \text{(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 if 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$, and for $f=x\mapsto \frac{1}{2}\|x\|_{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}$.
• $\|x\|_{\infty} \triangleq \max_{1 \leq i \leq n}|x_i|$.

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} \text{(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$, and for $f=x\mapsto \frac{1}{2}\|x\|_{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}$.
• $\|x\|_{\infty} \triangleq \max_{1 \leq i \leq n}|x_i|$.

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 if 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$, and for $f=x\mapsto \frac{1}{2}||x||_{2}^2$ for every $n$.

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

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} \text{(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 if 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$, and for $f=x\mapsto \frac{1}{2}\|x\|_{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}$.
• $\|x\|_{\infty} \triangleq \max_{1 \leq i \leq n}|x_i|$.