Geometry of First-Order Methods and Adaptive Acceleration

Clarice Poon, Jingwei Liang

Published 2020-03-09Version 1

First-order operator splitting methods are ubiquitous among many fields through science and engineering, such as inverse problems, signal/image processing, statistics, data science and machine learning, to name a few. In this paper, we study a geometry property of first-order methods when applying to solve non-smooth optimization problems. With the tool "partial smoothness", we design a framework to analyze the trajectory of the fixed-point sequence generated by first-order methods and show that locally the fixed-point sequence settles onto a regular trajectory such as straight line or spiral. Based on this finding, we discuss the limitation of current widely used "inertial acceleration" technique, and propose a trajectory following adaptive acceleration algorithm. Global convergence is established for the proposed acceleration scheme based on the perturbation of fixed-point iteration. Locally, we first build connections between the acceleration scheme and the well studied "vector extrapolation technique" in the field of numerical analysis, and then discuss acceleration guarantees of the proposed acceleration scheme. Moreover, our result provides a geometric interpretation of vector extrapolation. Numeric experiments on various first-order methods are provided to demonstrate the advantage of the proposed adaptive acceleration scheme.