Adaptive Catalyst for Smooth Convex Optimization

2019/11/25 by Anastasiya Ivanova, Ivanova, Anastasiya, Dmitry Pasechnyuk +9 · 1 citation
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC

paper · pdf · doi:10.48550/arxiv.1911.11271

arxiv created 2021/03/07 · arxiv updated 2021/03/09

Abstract

In this paper, we present a generic framework that allows accelerating almost arbitrary non-accelerated deterministic and randomized algorithms for smooth convex optimization problems. The main approach of our envelope is the same as in Catalyst (Lin et al., 2015): an accelerated proximal outer gradient method, which is used as an envelope for a non-accelerated inner method for the ℓ₂ regularized auxiliary problem. Our algorithm has two key differences: 1) easily verifiable stopping criteria for inner algorithm; 2) the regularization parameter can be tunned along the way. As a result, the main contribution of our work is a new framework that applies to adaptive inner algorithms: Steepest Descent, Adaptive Coordinate Descent, Alternating Minimization. Moreover, in the non-adaptive case, our approach allows obtaining Catalyst without a logarithmic factor, which appears in the standard Catalyst (Lin et al., 2015, 2018).

Cited by

• Smooth Quasar-Convex Optimization with Constraints

Related

• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Accelerated Alternating Minimization and Adaptability to Strong Convexity
• Adaptive Accelerated Gradient Method for Smooth Convex Optimization
• A Novel Catalyst Scheme for Stochastic Minimax Optimization
• RECAPP: Crafting a More Efficient Catalyst for Convex Optimization