About accelerated randomized methods

Abstract

We show how one can obtain nonaccelerated randomized coordinate descent method (Yu. Nesterov, 2010) and nonaccelerated method of randomization of sum-type functional (Le Roux-Schmidt-Bach, 2012) from the optimal method for the stochastic optimization problem (SIGMA, Devolder-Glineur-Nesterov-Dvurechensky-Gasnikov, 2014). The main trick is a special restart technique. We considered this trick to be usefull in others contexts. We consider only strongly convex case. We show that accelerated variants of this methods seems to be nontrivial in this context. That is, it is hard (perhaps impossible) to obtain accelerated variants using the same trick. We also propose new approach for accelerated coordinate descent methods. This approach is based on the coupling technique (Allen-Zhu-Orrechia, 2015) and allows us: to generalize accelerated coordinate descent methods for conditional optimization problems, to obtain the dual solution due to the primal-dual nature, to extend Universal method (Yu. Nesterov, 2013) to accelerated coordinate descent methods etc.

41 pages, in Russian in TRUDY MIPT. 2016. V. 8. no. 2. P. 67-100

References in corpus (3)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Randomized Dual Coordinate Ascent with Arbitrary Sampling

Cited by in corpus (4)

• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• Solving smooth min-min and min-max problems by mixed oracle algorithms
• Accelerated Directional Search with non-Euclidean prox-structure
• Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations