Geometry of First Order Methods and Adaptive Acceleration.
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 geometric property of first order methods when applying to solve non smooth optimization problems. With the tool of "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 a straight line or a 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 local acceleration guarantees of the proposed acceleration scheme. Moreover, our result provides a geometric interpretation of these vector extrapolation techniques. Numerical experiments on various first order methods are provided to demonstrate the advantage of the proposed adaptive acceleration scheme.