3
$\begingroup$

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.