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 Answer 1

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

$\endgroup$
3
  • $\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$
    – user494522
    May 20, 2019 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$ May 20, 2019 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$
    – user494522
    May 21, 2019 at 19:25

You must log in to answer this question.