An intuition for three different types of subgradients (proximal, regular, limiting)

Question

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking.

These subgradients are (assume $x \in$ dom$f$):

• Proximal subgradient: $\partial_p(f(x)) = \{v\ |\ \exists \delta>0,\rho > 0\ s.t.\ f(y) \geq f(x) + \langle v, y-x\rangle - \frac{1}{2}\rho ||y - x||^2\ \forall\ y \in B_\delta(x) \}$
• regular subgradient: $\{v\ |\ \exists\ \delta > 0\ s.t. f(y) \geq f(x) + \langle v, y-x\rangle + o(||y-x||)\ \forall\ y\in B_\delta(x) \}$
• limiting subgradient, defined by $\partial^\infty(f(x)) = \{v\ |\ (v, 0) \in N_{epi f}(x, f(x))\}$, where $N_C(x)$ is the limiting normal cone $\limsup_{x'\rightarrow _C x}\hat{N}_C(x)$ and $\hat{N}_C(x)$ is the normal cone to $C$ at $x$, with $v \in \hat{N}_C(x)$ iff $\langle v, y - x\rangle \leq o(||y-x||)\ \forall\ y\in C$

However, I'm having trouble conceptualising these; for instance, playing with the relatively straightforward function

$f(x) = -|x|$

it seems like all three of these subgradients coincide ($x = 0$ has no subgradient, everything else has $\partial f(x) = \nabla f(x)$ since the limiting normal cone coincides with the normal cone and there exists no $\delta$ for which $B_\delta(0)$ does not intersect $f(x)$), but playing with the less straightfoward

$f(x) = \begin{cases}x^2 \sin(1/x) &\text{if }x \not= 0\\0 &\text{if } x = 0\end{cases}$

just leaves me completely utterly lost; I can't see how the difference between a limiting normal cone and a normal cone makes a difference, I'm struggling to derive the proximal subgradient, etc.

If anyone could provide some intuition for these three concepts, preferably while working through the two functions I've been playing with, that would be fantastic!

Answer 1

This might not be a satisfying answer, but this is how I personally deal with this issue (at least in the topic of optimization).

I think these concepts are not made for actually computing them but rather for proofs and theoretical statements.

Let's say you want to study a nonsmooth, nonconvex optimization problem. Usually, you cannot hope to find the global minimum, but only apply some kind of iterative method. But what is this iterative method going to compute? A local minimum? Even in the smooth, nonconvex case this might fail and you can only hope for stationary points (which might turn out to be saddle points).

So what kind of object is your iterative method even supposed to compute? Evidently we need to generalize the concept of first order stationarity. What is the "right" generalization, you might ask. Well this is where the different subdifferentials come into play. Depending on the properties of your objective function (e.g. locally lipschitz or not) and the type of iterative scheme you are using the "right" notion might vary.

• Do you need good calculus?
• Do you need the subdifferential to be convex?
• Do you need to graph of the subdifferential map to be closed? (e.g. Murdukhovich, aka limiting differential)

To be at least a bit more concrete: Consider an iterative scheme to solve a given nonsmooth, nonconvex optimization problem $$ \min_x f(x) $$ that produces a sequence ${(x_n)}$ with $x_n \to \bar{x}$. Let's assume that you can prove that at each iteration there is an object $w_n \in \partial f(x_n)$ that fulfills $ w_n \to 0$. You clearly would like to deduce that $0 \in \partial f(\bar{x})$. For this you would need the closedness of the graph of the map $ x \mapsto \partial f(x)$. Last but not least it would be nice to have a theorem saying that if $x$ is a local minimizer, then it stationary wrt your given subdifferential.

If you can prove all these statements, you know that the iterates of your optimization method converge to "good" points. (And as you can see - we used the concept without actually ever computing it.)

Here a very concrete example showing how you can work with different subdifferential without ever computing them: Assume the problem at hand is $$ \min_x h(x) + g(x) $$ such that $h$ is smooth, but nonconvex and $g$ is nonsmooth, but convex. A possible algorithm, utilizing the proximal operator, would be $$ x_{k+1} = \text{prox}_g (x_k - \nabla h (x_k) ) $$ which is equivalent to $$ x_{k+1} = \text{argmin}_y \left\{ g(y) + \langle \nabla h (x_k), y - x_k \rangle + \frac12 || y - x_k ||^2 \right\}. $$ The function to be minimized in the last expression is a convex function so we can use first order optimality and some calculus of the convex subdifferential, to deduce $$ 0 \in \partial g(x_{k+1}) + \nabla h (x_k) + x_{k+1} - x_k. $$ Thus $$ \nabla h (x_{k+1}) - \nabla h (x_k) + x_k - x_{k+1} \in \partial g(x_{k+1}) + \nabla h (x_{k+1}) . $$ Here is where the magic happens! If you have good calculus for your subdifferential, e.g. the Frechet subdifferential $\partial^F$, then $$ \partial g(x_{k+1}) + \nabla h (x_{k+1}) = \partial^F (g + h) (x_{k+1}). $$ Now you have an expression, namely $\nabla h (x_{k+1}) - \nabla h (x_k) + x_k - x_{k+1}$, for which you can usually deduce convergence to zero, inside your subdifferential. The only things you ever had to compute where regular gradients and and proximal operators. Note however, that proximal operators can usually only be analytically computed for "simple" functions (similar to the subdifferential). In nonsmooth optimization it is therefore assumed that the nonsmoothness comes from a "simple" term (like the absolute value) and one tries to put all the "complicated" parts into the smooth function.