# Metric / strong slope restriction of function on unit ball in $\mathbb R^m$

Diclaimer. I'm not sure this is the right venue for this question, but I'll give it a try

Definition [Strong / metric slope]. Given a complete metric space $$(M,d)$$ and a function $$f:M \to (-\infty,+\infty]$$, define its strong slope at a point $$x \in M$$, denote $$\partial |f|(x)$$, by $$|\partial|f(x) := \begin{cases}0,&\mbox{ if }f\text{ attains a local minimum at }x,\\ \limsup_{y \to x}\frac{f(x)-f(y)}{d(x,y)},&\mbox{else.}\end{cases}$$

This concept crops up in gradient-flow literature for metric spaces, probability spaces, etc. For more details on this concept, see this monograph and the references therein.

Now, consider the unit ball $$\mathbb B_m := \{x \mid \|x\| \le 1\}$$ in $$\mathbb R^m$$, seen as a metric space equipped with euclidean distance.

## Question

Fix $$n\ge 1$$ points $$a_1,\ldots,a_n \in \mathbb R^m$$ and consider the convex function $$f:\mathbb B_m \to \mathbb R$$ defined by $$f(x) := \max \{a_i^\top x \mid i = 1,\ldots,n\}$$.

How to go about computing $$|\partial|f(x)$$ ?

Note. Ultimately, I'm only interested in uniform lower-bound on $$\partial |f|(x)$$ for $$\|x\| < 1$$, i.e finding $$\alpha > 0$$ such that $$\inf_{x \in \mathbb B_m^\circ}\partial |f|(x) \ge \alpha$$.

Any useful hints will be very much appreciated.

## Observations

• I know how to solve the problem in case the domain of $$f$$ is replaced with the entire flat space $$\mathbb R^m$$. Indeed, in this case, I can prove that $$|\partial|f(x) \ge \gamma := \min_{q \in \Delta_{n-1}}\|A^\top q\|$$, where $$A$$ is the $$n \times m$$ matrix with $$i$$th row equal to $$a_i$$.
• In the spherical case (the setup of my problem), even the completely linear scenario where $$n=1$$, i.e $$f(x) \equiv a_1^\top x$$, is already not clear to me.
• In the case of Banach spaces (of which $$\mathbb B_m$$ is not!), there are known uniform lower-bounds in terms of Hadamard derivatives.
• Extend this function to all of $\mathbb{R}^m$. I suspect that $\partial |f|$ and $\nabla \tilde f$ are somehow related where $\tilde f$ is the extension. – Laithy Nov 3 '20 at 19:26
• @Laithy Thx! I had this in mind but it lead to nasty calculations and ultimately, a dead-end. Rethinking my problem, I'm fine with replacing the unit-sphere by its convex hall, namely, the closed unit-ball $\mathbb B_m$. For $\tilde{f}$ be the extension which agrees with $f$ on $\mathbb B_m$ and equals $\infty$ outside that ball. Now, for any $x \in \mathbb B_m^\circ$, $\tilde{f}$ and $f$ agree on a neighborhood of $x$, and so have $|\partial|f(x) = \min\{\|v\| \mid v \in \partial \tilde{f} w)\}$, which can be computed explicitly. The case $\|x\|= 1$ leads to a 1d convex optimization problem. – dohmatob Nov 3 '20 at 20:09

## 1 Answer

Disclaimer. I'm going to answer post an answer, since I'm probably the only one interested in this problem...

So, after rethinking my problem, I'm fine with replacing the unit-sphere by its convex hall, namely, the closed unit-ball $$\mathbb B_m$$. For $$\tilde{f}$$ be the extension which agrees with $$f$$ on $$\mathbb B_m$$ and equals $$\infty$$ outside that ball (thanks to a comment by user @Laithy).

## Basic theory for convex functions

Let $$X = (X,\|\cdot\|)$$ be a Banach space with topological dual $$X^\star =(X^\star,\|\cdot\|_\star)$$. The following result about stronge slope of convex functions is well-known

Fact 1. If $$f:X \to (-\infty,+\infty]$$ is an extended-value convex function, then $$|\partial|f(x) = \|\partial f(x)\|_\star := \inf \{\|v\|_\star \mid v \in \partial f(x)\},$$ where $$\partial f(x) := \{v \in X^\star\mid f(y) \ge f(x) + \langle v,y-x\rangle \;\forall z \in X\}$$.

Combining this with the subdifferential rule for sums of convex functions, we have

Fact 2. Let $$\tilde f:X \to \mathbb R$$ be a convex function, $$C$$ be a nonempty convex subset of $$X$$, and define an extended-value convex function $$f:X \to (-\infty,+\infty]$$ by $$f(x) = \tilde{f}(x)$$ if $$x \in C$$, and $$f(x) = \infty$$ else. Then $$|\partial|f(x) = \inf \{\|u + v\|_\star \mid u \in \partial f(x),\; v \in N_C(x)\},$$ where $$N_C(x) \subseteq X^\star$$ is the normal cone of $$C$$ at $$x$$.

## Application to my problem

For my specific problem, we have

• $$X = \mathbb R^m$$, a Banach space with the euclidean norm.
• $$C = \mathbb B_m$$ the unit ball in $$\mathbb R^m$$.
• $$N_C(x) = \begin{cases}\mathbb R_+ x,&\mbox{ if }\|x\| = 1,\\\{0\},&\mbox{ if }\|x\| < 1,\\\emptyset,&\mbox{ if }\|x\| > 1.\end{cases}$$
• $$f:\mathbb R^m \to \mathbb R$$, $$f(x) := \max_{i \in [n]}a_i^\top x$$. Thus, $$\partial \tilde f(x) = \mbox{conv}(\{a_i \mid i \in I(x)\}$$, where $$I(x):= \{i \in [n] \mid a_i^Tx = \tilde{f}(x)\}$$
• $$f = \tilde{f} + i_C$$.

Thus, invoking Fact 2 gives

• Case 1: $$\|x\| < 1$$. Let $$A$$ be the $$n \times m$$ matrix whose $$i$$th row is $$a_i$$. Noting that $$N_C(x) = \{0\}$$, one computes

$$\begin{split} |\partial |f(x) &= \inf\{\|u\| \mid u \in \mbox{conv}(\{a_i \mid i \in I(x)\}\}\\ &\ge \inf\{\|u\| \mid u \in \mbox{conv}(\{a_i \mid i \in [n]\}\},\text{ since inf. on larger set is smaller}\\ &= \inf_{q \in \Delta_{n-1}}\|A^\top q\|. \end{split}$$

• Case 2: $$\|x\|=1$$. Here, $$N_C(x) = \mathbb R_+ x := \{tx \mid t \ge 0\} \subseteq \mathbb R^m$$, and we get $$\begin{split} |\partial |f(x) &= \inf\{\|u+tx\| \mid u \in \mbox{conv}(\{a_i \mid i \in I(x)\},\; t \ge 0\}\\ &\ge \inf_{q \in \Delta_{n-1},\;t \ge 0}\|A^\top q + tx\|\\ \end{split}$$

• Case 3: $$\|x\| > 1$$. Here $$N_C(x) = \emptyset$$, and so $$|\partial|f(x) = \inf\{\|u + v\| \mid u \in \partial \tilde{f}(x),\; v \in \emptyset\} = \inf \emptyset = \infty.$$

In particular, I obtain the following result

Theorem. It holds that $$\inf_{x \in \mathbb B_m^\circ}|\partial|f(x) \ge \min_{q \in \Delta_{n-1}}\|A^\top q\|.$$