# How to show dual norm of subgradient of a $L$-Lipschitz convex function is bounded by $L$?

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.

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$$.
• 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? – Saeed May 20 '19 at 18:12
• @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 ? – Gabriel Romon May 20 '19 at 18:23
• 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? – Saeed May 21 '19 at 19:25