Convex optimization with full subdifferential information

Question

Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a non-smooth convex optimization problem for the special case where the full subdifferential is available? All of the results that I can find are designed for the case where one has an oracle that can generate a single subgradient.

Answer 1

The difficulty with non-differentiable convex functions in optimization stems from the fact that an arbitrary subgradient need not be a descent direction, and hence classical first-order methods cannot be guaranteed to work. (But see Lewis' and Overton's works on nonsmooth quasi-Newton methods, e.g., http://people.orie.cornell.edu/aslewis/publications/13-nonsmooth.pdf, where an appropriate line-search strategy is used to mitigate that difficulty.)

If you have access to the full subdifferential, you could try to compute (analytically or algorithmically) a minimum-norm subgradient $$ p^k = \arg\min_{\xi\in\partial f(x^k)}\|\xi\|,$$ which is a descent direction (and can be used to measure stationarity) and can be used in place of the standard gradient in any algorithm built on descent directions (e.g., gradient descent with Armijo line search). A proof (and a counterexample for arbitrary subgradients) can be found in Andrzej Ruszczyński's book Nonlinear Optimization.

A related approach is to compute (again, analytically or algorithmically) instead proximal points $$ \mathrm{prox_f(v)} = \arg\min_{w} \frac12 \|v-w\|^2 + f(w) = (\mathrm{Id} + \partial f)^{-1}(v)$$ which can be used directly in place of gradient steps when applied to a suitable $v^k$ (think implicit vs. explicit Euler method for ODEs). Most current first-order methods for convex optimization are based on this approach, such as Nesterov's optimal first-order method which uses a specially chosen sequence of step sizes. A good introduction to these methods can be found in Lieven Vandenberghe's lecture notes.

Answer 2

Regarding difficulty results (i.e., lower bounds) for iterative methods, worst-case complexity results in the oracle model hold regardless of whether you provide the full subgradient to the algorithm. What happens is that lower bounds for nonsmooth convex optimization are obtained by piecewise linear functions, and the adversary can always (consistently) adapt the instance so that at all query points the function is locally linear, thus the subdifferential is a singleton. You can see the proof at page 120 in the following notes http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf

If you care about average-case analysis (where the adversary is not allowed to adapt) then the question is much more delicate, and I think there is no answer in the literature up to date.