arXiv (Cornell University) · 2019 · 11 citations · 12 references
Open access
ComputingComputer ScienceAlgorithmsComputational MechanicsOptimizationConvex OptimizationGlobal OptimizationGradient-based OptimizationIterative SolversNonlinear ProgrammingNumerical AlgorithmsAccelerated OptimizationAnderson AccelerationConvergenceFixed-point ComputationGlobal Convergence AnalysisLocal Convergence AnalysisProximal AlgorithmsSmooth Optimization
Anderson acceleration is a well-established and simple technique for speeding up fixed-point computations with countless applications. Previous studies of Anderson acceleration in optimization have only been able to provide convergence guarantees for unconstrained and smooth problems. This work introduces novel methods for adapting Anderson acceleration to (non-smooth and constrained) proximal gradient algorithms. Under some technical conditions, we extend the existing local convergence results of Anderson acceleration for smooth fixed-point mappings to the proposed scheme. We also prove analytically that it is not, in general, possible to guarantee global convergence of native Anderson acceleration. We therefore propose a simple scheme for stabilization that combines the global worst-case guarantees of proximal gradient methods with the local adaptation and practical speed-up of Anderson acceleration.
12
Gradient methods for minimizing composite functions
Yu. Nesterov · Mathematical Programming · 2012 · 1.4K citations
Iterative Procedures for Nonlinear Integral Equations
Donald G. Anderson · Journal of the ACM · 1965 · 975 citations · Full text
Extrapolation Methods for Vector Sequences
David A. Smith, William F. Ford, Avram Sidi · SIAM Review · 1987 · 215 citations