1
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Laithy
    Nov 3, 2020 at 19:26
  • $\begingroup$ @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. $\endgroup$
    – dohmatob
    Nov 3, 2020 at 20:09

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.