2015/08/10 by Alexander Gasnikov, Gasnikov, Alexander, Pavel Dvurechensky +3
Computer Science · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1508.02182
openalex publication_date 2015/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.