Accelerated Gradient Methods Through Variable and Operator Splitting
Preprint
Abstract
This paper introduces a unified framework for accelerated gradient methods through the variable and operator splitting (VOS). The operator splitting decouples the optimization process into simpler subproblems, and more importantly, the variable splitting leads to acceleration. The key contributions include the development of strong Lyapunov functions to analyze stability and convergence rates, as well as advanced discretization techniques like Accelerated Over-Relaxation (AOR) and extrapolation by the predictor-corrector methods (EPC). For convex case, we introduce a dynamic updating parameter and a perturbed VOS flow. The framework effectively handles a wide range of optimization problems, including convex optimization, composite convex optimization, and saddle point systems with bilinear coupling.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Provable non-accelerations of the heavy-ball methodMathematical Programming, 2025
- High order spatial discretization for variational time implicit schemes: Wasserstein gradient flows and reaction-diffusion systemsJournal of Computational Physics, 2023
- An adaptive polyak heavy-ball methodMachine Learning, 2022
- On lower iteration complexity bounds for the convex concave saddle point problemsMathematical Programming, 2021
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemsMathematical Programming, 2019
- A Survey of Sparse Representation: Algorithms and ApplicationsIEEE Access, 2015
- Templates for convex cone problems with applications to sparse signal recoveryMathematical Programming Computation, 2011
- On successive‐overrelaxation acceleration of the Hermitian and skew‐Hermitian splitting iterationsNumerical Linear Algebra with Applications, 2007
- Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problemsIMA Journal of Numerical Analysis, 2007
- Regression Shrinkage and Selection Via the LassoJournal of the Royal Statistical Society Series B: Statistical Methodology, 1996