Adaptive Catalyst for Smooth Convex Optimization

Ch. 268319. P. 20–37.

Ivanova A., Pasechnyuk D., Grishchenko D., Shulgin E., Gasnikov A., Matyukhin V.

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 major approach of our envelope is the same as in Catalyst [37]: an accelerated proximal outer gradient method, which is used as an envelope for a non-accelerated inner method for the ℓ2 regularized auxiliary problem. Our algorithm has two key differences: 1) easily verifiable stopping condition for inner algorithm; 2) the regularization parameter can be tuned 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 [37, 38].

Keywords: Alternating minimization, Adaptive Methods, Accelerated methods, Catalyst, Coordinate descent, Distributed methods

In book

Optimization and Applications: 12th International Conference, OPTIMA 2021, Petrovac, Montenegro, September 27 – October 1, 2021, Proceedings

Switzerland: Springer, 2021.