Testing and non-linear preconditioning of the proximal point method

Abstract

Employing the ideas of non-linear preconditioning and testing of the classical proximal point method, we formalise common arguments in convergence rate and convergence proofs of optimisation methods to the verification of a simple iteration-wise inequality. When applied to fixed point operators, the latter can be seen as a generalisation of firm non-expansivity or the $\alpha$-averaged property. The main purpose of this work is to provide the abstract background theory for our companion paper "Block-proximal methods with spatially adapted acceleration". In the present account we demonstrate the effectiveness of the general approach on several classical algorithms, as well as their stochastic variants. Besides, of course, the proximal point method, these method include the gradient descent, forward--backward splitting, Douglas--Rachford splitting, Newton's method, as well as several methods for saddle-point problems, such as the Alternating Directions Method of Multipliers, and the Chambolle--Pock method.

References in corpus (4)

• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Block-proximal methods with spatially adapted acceleration
• A Generalization of the Chambolle-Pock Algorithm to Banach Spaces with Applications to Inverse Problems

Cited by in corpus (11)

• Block-proximal methods with spatially adapted acceleration
• Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization
• First-order primal-dual methods for nonsmooth nonconvex optimisation
• Linearly convergent bilevel optimization with single-step inner methods
• Primal-dual block-proximal splitting for a class of non-convex problems
• Regularisation, optimisation, subregularity
• Predictive online optimisation with applications to optical flow
• A nonsmooth primal-dual method with interwoven PDE constraint solver
• Proximal methods for point source localisation
• Prediction techniques for dynamic imaging with online primal-dual methods
• Online optimisation for dynamic electrical impedance tomography