6
$\begingroup$

Assume I have a differentiable function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ that is $L$-Lipschitz with respect to a norm $\|\cdot\|$ on $\mathbb{R}^n$: $$ \forall x, y \in \mathbb{R}^n, |f(x) - f(y)| \le L\|x-y\|. $$ I know that if $f$ is further assumed to be convex, and $\|\cdot\|$ is the euclidian norm, then convexity implies $$ L\|\nabla f(x)\|_2 \ge f(x + \nabla f(x)) - f(x) \ge \langle \nabla f(x), \nabla f(x)\rangle = \| \nabla f(x)\|_2^2, $$ thus $\|\nabla f(x)\|_2 \le L$.

But does $\|\nabla f(x)\| \le L$ still hold if $\|\cdot\|$ is any norm on $\mathbb{R}^n$? And if $f$ is only assumed differentiable?

$\endgroup$
1
  • $\begingroup$ That is what I was thinking... I am quite sure I have seen this argument used to upper bound the L1-norm in some optimization papers, but that does not seem to be true to me, so I was wondering whether there were some differentiability arguments I am not aware of. $\endgroup$
    – pauloss
    Jan 26, 2021 at 10:48

1 Answer 1

4
$\begingroup$

Recall that for a differentiable function $f : \mathbb{R}^n \to \mathbb{R}$, its gradient is defined thanks to the euclidean structure of $\mathbb{R}^n$: it is the only vector field such that for all $x$ and $u$ $$ \mathrm{d}_xf\cdot u = \langle \nabla f(x),u\rangle. $$

In what follows, all gradients $\nabla f$ are the classic euclidean gradients defined thanks to the usual euclidean structure.

An important result is that if $f$ is Lipschitz for some norm, then it is almost everywhere differentiable, and is Lipschitz for any norm. Moreover, the euclidean gradient is then defined almost everywhere.

Notice that for the euclidean norm, one has $\|\nabla f(x)\|_2 = \|\mathrm{d}_xf\|_2$, where this second norm is the operator norm subordinate to the euclidean one: it is because by Cauchy-Schwarz inequality: $$ |\mathrm{d}_xf\cdot u| = |\langle \nabla f (x),u\rangle| \leqslant \|\nabla f (x) \|_2 \|u\|_2, $$ hence $\|\mathrm{d}_xf\| \leqslant \|\nabla f(x)\|_2$, and equality is reached for $u = \nabla f(x)$. So saying $f$ is $L$-Lipschitz show that $\|\nabla f\|_2 \leqslant L$ almost everywhere.

But if you consider another norm on $\mathbb{R}^n$, there is no reason for (the above vector field) $\nabla f$ to stay bounded with the same constant: indeed, the equivalence of norms in a finite dimensional vector space assures that for any norm $\|\cdot\|$, there exists a constant $C>0$ such that $$ \|\nabla f(x)\| \leqslant C\cdot \|\nabla f (x) \|_2. $$ A counter example to having the same constant $L$ is just the following: suppose $f(x) = \langle u,x \rangle$ for a given $u \in \mathbb{R}$ and for $\langle\cdot,\cdot\rangle$ the usual inner product. Then $\nabla f \equiv u$ on $\mathbb{R}^n$, hence $\|\nabla f \|_2 = \|u\|_2$. But if one measures $\nabla f$ thanks to $\|\cdot\|_{\lambda}=\lambda \|\cdot \|_2$ with $\lambda >0$, one has $$ \|\nabla f \|_{\lambda} = \lambda \|u\|_2 $$ which is strictly greater than $L = \|u\|_2$ if $\lambda >1$.

To conclude, note that that I never used any convexity assumption, but I used only the Lipschitz one.

$\endgroup$
4
  • $\begingroup$ I see, convexity seemed to be overkill there. Actually, I am trying to upperbound gradients' $L1$-norm. Norms equivalence works but it depends on the dimension. Assuming that $f$ is restricted to a set where $\|x\|_1 \le M$ for some $M > 0$, would it hold that $\|\nabla f\|_1 = O(L)$ or something similar? I am very confused about this since they seem to use such a result there (page 5), but I am surely missing something: papers.nips.cc/paper/2015/file/…. $\endgroup$
    – pauloss
    Jan 26, 2021 at 11:47
  • $\begingroup$ Well, I have absolutely no skill in optimisation, but if you are refering to the sentence "We can bound the error in terms of the L1-Lipschitz constant, which can be much smaller than th L2-Lipschitz constant", I find it weird: I did some (possibly false) computations and it seems to me that the $L_2$ Lipschitz constant is smaller than the $L_1$ Lipschitz constant. In fact I have something like $C_2 \leqslant C_1 \leqslant \sqrt{n}C_2$. $\endgroup$
    – Didier
    Jan 26, 2021 at 12:51
  • $\begingroup$ Thank you for your insights. :) I think inequalities between L1 and L2 norms give $|f(x) - f(y)| \le C_2 \|x-y\|_2 \le C_2 \|x-y\|_1$ thus $C_2 \ge C_1$, and $|f(x) - f(y)| \le C_1 \|x-y\|_1 \le \sqrt{n}L_1 \|x-y\|_2$ which yields $\sqrt{n} C_1 \ge C_2$, since these constants should be defined as the smallest upper bound. $\endgroup$
    – pauloss
    Jan 26, 2021 at 13:15
  • $\begingroup$ For the record, an upper bound such as $\|\nabla f(x)\|_1 \le L_1$ does not generally hold. However, convexity with $y = x + \nabla_i f(x) e_i$ (where $i$ is chosen such that $\| \nabla f(x)\|_\infty = | \nabla_i f(x) |$) gives $\| \nabla f(x) \|_\infty \le L_1$, which gives the upper bound $\langle s, \nabla f(x) \rangle \le \| s \|_1 L_1$ in the above paper using Hölder's inequality. $\endgroup$
    – pauloss
    Jan 27, 2021 at 11:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .