Timezone: »
We propose and analyze a novel adaptive step size variant of the Davis-Yin three operator splitting, a method that can solve optimization problems composed of a sum of a smooth term for which we have access to its gradient and an arbitrary number of potentially non-smooth terms for which we have access to their proximal operator. The proposed method leverages local information of the objective function, allowing for larger step sizes while preserving the convergence properties of the original method. It only requires two extra function evaluations per iteration and does not depend on any step size hyperparameter besides an initial estimate. We provide a convergence rate analysis of this method, showing sublinear convergence rate for general convex functions and linear convergence under stronger assumptions, matching the best known rates of its non adaptive variant. Finally, an empirical comparison with related methods on 6 different problems illustrates the computational advantage of the adaptive step size strategy.
Author Information
Fabian Pedregosa (UC Berkeley)
Gauthier Gidel (MILA)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Oral: Adaptive Three Operator Splitting »
Fri Jul 13th 09:50 -- 10:00 AM Room A9
More from the Same Authors
-
2020 Poster: Linear Lower Bounds and Conditioning of Differentiable Games »
Adam Ibrahim · Waïss Azizian · Gauthier Gidel · Ioannis Mitliagkas -
2018 Poster: Frank-Wolfe with Subsampling Oracle »
Thomas Kerdreux · Fabian Pedregosa · Alexandre d'Aspremont -
2018 Oral: Frank-Wolfe with Subsampling Oracle »
Thomas Kerdreux · Fabian Pedregosa · Alexandre d'Aspremont