Beyond First Order: V U $$\mathcal {V}\mathcal {U}$$ -Decomposition Methods

When minimizing a nonsmooth convex function bundle methods are well known by their robustness and reliability. While such features are related to global convergence properties of the algorithm, speed of convergence is a different matter, as fast rates cannot be expected if the objective function lacks smoothness. In the typical bundle dichotomy that splits iterates between null and serious steps, the latter subsequence converges with R-linear speed. Moving from the first-order method realm to the world of superlinear speed is possible when realizing that nonsmoothness often appears in a structured manner. This is the basis of the V U $${\mathcal {V}\mathcal {U}}$$ -decomposition approach presented in this chapter. Thanks to this decomposition, it is possible to make a Newton-like move in certain U $${\mathcal {U}}$$ -subspace, where all the function “smoothness” concentrates at least locally. On its orthogonal complement, the “sharp” V $${\mathcal {V}}$$ -subspace, an intermediate iterate is defined such that the overall convergence is driven by the U $${\mathcal {U}}$$ -step. As a result, the serious-step subsequence converges with superlinear speed. By focusing on the proximal variants of bundle methods, this chapter introduces gradually the V U $${\mathcal {V}\mathcal {U}}$$ -theory and the ingredients needed to build superlinearly convergent algorithms in nonsmooth optimization. For functions whose proximal points are easy to compute, as in machine learning, an implementable quasi-Newton V U $${\mathcal {V}\mathcal {U}}$$ -algorithm is given. The bundle machinery is incorporated for functions whose proximal points are not readily available. In this case, superlinear speed can be achieved by solving two quadratic programming problems per iteration.