Nonsmooth Optimization — Subgradients and Proximal Methods
Stub. The calculus of nonsmooth convex functions: subgradients and subdifferentials, their relationship to directional derivatives, a calculus for combining them, optimality conditions for composite nonsmooth objectives, and proximal operators/the Moreau envelope (a smoothed surrogate for a nonsmooth function); then the resulting algorithms — subgradient descent, proximal-gradient methods for regularized optimization (with a convex-case convergence rate), proximal coordinate descent, and the proximal point method.
Corresponds to Chapters 8–9. Many objectives that matter in practice aren’t differentiable everywhere (e.g. an regularizer, or a hinge loss), so the gradient has to be replaced by the subdifferential — the set of all slopes of lines that stay below the function everywhere, reducing to the ordinary gradient where is smooth — with its own calculus for differentiating sums, compositions, and constrained problems, and the proximal operator/Moreau envelope giving a smooth surrogate whose gradient recovers useful subgradient information. Algorithmically, the plain subgradient method works but converges slowly (no subgradient is as informative as a true gradient); proximal-gradient algorithms recover fast convergence rates for the common case of a smooth loss plus a nonsmooth regularizer by handling each part separately (gradient step on the smooth part, proximal step on the nonsmooth part), with proximal coordinate descent and the proximal point method as further refinements.
Outline (TODO — flesh out each)
- Subgradients and subdifferentials
- The subdifferential and directional derivatives
- Calculus of subdifferentials
- Convex sets and convex constrained optimization
- Optimality conditions for composite nonsmooth functions
- Proximal operators and the Moreau envelope
- Subgradient descent; the subgradient method and steplengths
- Proximal-gradient algorithms for regularized optimization
- Convergence rate for convex
- Proximal coordinate descent for structured nonsmooth functions
- The proximal point method