Directional derivative of steep/legendre convex functions

71 Views Asked by At

This question is Proposition 26.7 in Bandit Algorithms by Lattimore & Szepesvári [PDF].

Let $f$ be a proper, extended real valued convex function $f:\mathbb{R}^n \to \mathbb{R}\cup\{\infty\}$. The domain $dom(f) = \mathcal{D}$ be defined as $\mathcal{D} = \{x \in \mathbb{R}^n | f(x) \neq \infty \}$ is assumed to be nonempty. Let $B_{\epsilon}(x) = \{ y\text{ } |\text{ } \lVert x-y \rVert_2 < \epsilon \} $ be the epsilon ball around $x$.

A point $x$ is in the interior of a set $\mathcal{A}$ if $\exists$ $\epsilon$ such that $B_{\epsilon}(x) \in \mathcal{A}$. We define $\mbox{int}(\mathcal{A}) = \{ x\in \mathcal{A} | \text{ } \exists \text{ }\epsilon>0 \text{ such that } B_{\epsilon}(x) \subset \mathcal{A} \}$.

A point $z$ is on the boundary of $\mathcal{A}$ if $\forall$ $\epsilon>0$ $B_{\epsilon}(z)$ contains points in $\mathcal{A}$ and $\mathcal{A}^C$. We define the boundary of $\mathcal{A}$ as $\delta\mathcal{A}= \{x | \text{ }\forall\text{ } \epsilon \text{ } \exists\text{ } z_{1}, z_{2}\in B_\epsilon(x) \text{ with } z_1 \in \mathcal{A} \text{ and } z_2\notin \mathcal{A} \}$.

Let $\mathcal{C} = int(\mathcal{D})$. Further assume $f$ is Legendre, which is defined as:

  1. $\mathcal{C}$ is not empty.

  2. $f$ is differentiable and strictly convex on $\mathcal{C}$. Note this implies that $\forall x,y \in \mathcal{C}$, $f(y) > f(x) + \nabla f(x)^T(y-x)$ .

  3. $\underset{n\rightarrow \infty}{\lim} \lVert \nabla f(x_n) \rVert_2 = \infty$ for any sequence of points $x_n\in \mathcal{C}$ such that $\underset{n\rightarrow \infty}{\lim}x_n = x$ with $x\in \delta\mathcal{C}$.

I'm trying to prove that if $x\in \mathcal{C}$ and $y\in \delta\mathcal{C}$, then $$\underset{\alpha \rightarrow 1}{\lim} \nabla f((1-\alpha)x+\alpha y)^T(y-x) = \infty.$$

This is obvious in one dimension, and since this is pretty much a one dimensional calculation I would have thought the intuition would hold. That said, since it's only given that the norm of the gradient blows up at the boundary, I'm having trouble showing that it blows up in the specific given direction $y-x$. I'm pretty sure that this has something to do with the (strict) convexity, but I've been thinking about this for a while and I'm stumped.