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.

В данной работе предлагаются способы получения ускоренных и не- ускоренных вариантов рандомизированных покомпонентных мето- дов и неускоренных вариантов методов рандомизации суммы, исхо- дя из оптимальных методов для общих задач (стохастической) вы- пуклой оптимизации. В работе подчеркивается нетривиальность оценок, полученных для соответствующих ускоренных вариантов этих методов, которые выводятся в статье с помощью недавно пред- ложенной техники каплинга. В отличие от многих других ситуаций, в данном случае не удается “вытащить”, не погружаясь в детали до- казательства (должным образом корректируя его), оптимальные ме- тоды (оценки) для рандомизированных покомпонентных методов и методов с рандомизацией суммы исходя из оптимальных методов (оценок), применимых к общим задачам стохастической оптимиза- ции.