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 '20 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 '20 at 20:09
0
$\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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.