How is the subgradient method different from gradient descent in practice?

Question

I'm trying to learn about the subgradient descent optimization method. I'm having trouble understanding how it differs from basic gradient descent in a practical sense. According to this lecture, the next step in gradient descent is: $$x^{(k+1)}=x^{(k)}-t_k\nabla f(x^{(k)})$$ and the subgradient method step is: $$x^{(k+1)}=x^{(k)}-t_kg(x^{(k)})$$ Gradient descent applies to continuously differentiable functions, where $\nabla f(x^{(k)})$ is the gradient evaluated at the current step. For the subgradient method, $g(x^{(k)})$ is a subgradient of the objective function $f$ at $x^{(k)}$. If the objective function is differentiable at $x^{(k)}$, there is only one subgradient: $g(x^{(k)}) = \nabla f(x^{(k)})$. If $f$ has a "corner" at $x^{(k)}$ where the gradient is not defined, there may be more than one subgradient.

My confusion is that, for all practical purposes, it seems like the objective function will most likely be differentiable at each iteration, and wouldn't this make it the same as gradient descent? For example, take the objective function $f: \mathbb{R} \to \mathbb{R}$: $$\begin{equation} f(x)= \begin{cases} 2x-3, & |x| > 2 \\ \frac{1}{4}x^2, & |x| \leq 2 \end{cases} \end{equation}$$ The gradient is: $$\begin{equation} \nabla f(x)= \begin{cases} 2, & |x| > 2 \\ \frac{1}{2}x, & |x| < 2 \\ \rm{undefined}, & |x| = 2 \end{cases} \end{equation}$$ Since $f$ is not continuouly differentiable, we supposedly can't use gradient descent. But assuming we know these gradients, and if $|x^{(k)}| \neq 2$ over all iterations (likely), why don't we just use basic gradient descent to solve this?

My other question is this. Imagine, for the same problem, $x^{(k)} = 2$ (i.e. the corner) at some iteration $k$. The subgradient at $x=2$ can be any value $1 \leq g \leq 2$ [edited 13 June 2020, replacing $\neq$ with $\leq$]. If we're using the subgradient method, how do we choose a value for $g$ in this range for this iteration?

Answer 1

This is a good observation. As long as your function $f$ is convex and lower-semicontinuous, the set of points where your function has a "corner" (i.e. does nothave a unique subgradient) has measure-zero. In practice, this means that subgradient methods will work analogously (if not, identically) to gradient methods almost everywhere. There are similar results for convergence guarantees, too. The literature on "subgradient projectors" will further illuminate concrete results.

As for a subgradient selection rule, I view this as an engineer's question, since (as far as I know) the subgradient selection rule does not matter too much in the theory. However, I like to take the subgradient of smallest norm. This motivation comes from minimizing the absolute value $|\cdot|$. If, at some iteration $k$, you're at the problem's solution of $x_k=0$, the subgradient at that point is $[-1,1]$. If you select any nonzero subgradient, the method will not necessarily terminate (assuming your algorithm terminates when $\|x_k-x_{k+1}\|$ is small). Point being: If you're not careful about how you select subgradients, your numerical method might not detect that you are at the solution.