3
$\begingroup$

I am studying the monograph Online Learning and Online Convex Optimization. At page 133, the author has the following Lemma:

$\textbf{Lemma 2.6.}$ Let $f: S \rightarrow \mathbb{R}$ be a convex function. Then, $f$ is $L$-Lipschitz over $S$ with respect to a norm $\|\cdot\|$ if and only if for all $w \in S$ and $z \in \partial f(w)$ we have that $\|z\|_{\star} \leq L$, where $\|\cdot\|_{\star}$ is the dual norm.

Dual norm is defined as $\|z\|_{\star}= \sup_{\|x\|\leq 1} \langle x,z\rangle$ and supposedly, $S$ is a subset of $\mathbb{R}^n$. I want to explore the "only if" case: $f$ is $L$-Lipschitz $\rightarrow \|z\|_{\star} \leq L$.

$\text{The suggested proof in the monograph:}$

Choose $w \in S, z \in \partial f(w)$. Let $u$ be such that $u-w=\arg\max_{v:\|v\|=1} \langle v,z \rangle$. Therefore, $\langle u-w,z \rangle=\|z\|_{\star}$. Then, using the definition of sub-gradient

$$ f(u) -f(w) \geq \langle z,u-w \rangle = \|z\|_{\star} $$ Since $f$ is $L$-Lipschitz

$$ \langle z,u-w \rangle = \|z\|_{\star} \leq f(u) -f(z) \leq L \|u-v\| $$

And since $ \|v\|=\|u-w\|=1$, hence the claim.

My question: what if $S$ be a ball in $\mathbb{R}^n$ where its radius is less than $1/2$, i.e., $S=B_{\epsilon}(0)$, then we are not able to build such a $v$. I mean we cannot have two distinct $u,w$ where the norm of their difference of is one. Therefore, the proof is flawed. Am I mistaken or something is going on which I have overlooked? Could you elaborate this for me and give a proof that does not need the that special $v$ if I am right.

$\endgroup$
1
$\begingroup$

Consider $w\in S$ and $z\in \partial f(w)$. By convexity of $f$, for any $y\in S$ one has $$\langle z,y-w\rangle\leq f(y)-f(w)\leq L\|y-w\| $$ thus when $y\neq w$, $$\langle z,\frac{y-w}{\|y-w\|}\rangle \leq L$$

It is reasonable to assume that $w\in \operatorname{int} S$, so that there exists some $\epsilon >0$ such that $\overline{B}(w,\epsilon)\subset S$. Consider an arbitrary $x$ such that $\|x\|=1$ and let $y=w+\epsilon x$. Then $y\in \overline{B}(w,\epsilon)$ and $$\langle z,x \rangle = \langle z,\frac{y-w}{\|y-w\|}\rangle \leq L$$ Hence $\|z\|_* \leq L$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you elaborate what would happen when $w$ in on the boundary of $S$. Also, can $S$ be a closed set to have this result? $\endgroup$ – Saeed May 20 '19 at 18:12
  • $\begingroup$ @Saeed If $w$ is on the boundary this proof does not work. But if $w$ is not in the interior of $S$, the subdifferential of $f$ at $w$ may be empty, so why bother ? $\endgroup$ – Gabriel Romon May 20 '19 at 18:23
  • $\begingroup$ I am asking because most of the time we declare that we have $S$ as a closed convex set for optimization problem and use the proven result. Therefore, $w$ can be on the boundary of $S$. I just want to know whether the result is true for just open sets or it works for any closed sets? $\endgroup$ – Saeed May 21 '19 at 19:25

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.