@article{373446eb057e4665b780350c4f48f525,
title = "On optimal probabilities in stochastic coordinate descent methods",
abstract = "We propose and analyze a new parallel coordinate descent method—NSync—in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen using an arbitrary probability law. This is the first method of this type. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities to the sets to optimize the bound. The complexity and practical performance of the method can outperform its uniform variant by an order of magnitude. Surprisingly, the strategy of updating a single randomly selected coordinate per iteration—with optimal probabilities—may require less iterations, both in theory and practice, than the strategy of updating all coordinates at every iteration.",
keywords = "Arbitrary sampling, Complexity, Coordinate descent, First order method",
author = "Peter Richt{\'a}rik and Martin Tak{\'a}{\v c}",
note = "Funding Information: This work appeared on arXiv in October 2013 ( arXiv:1310.3438 ). P. Richt{\'a}rik and M. Tak{\'a}{\v c} were partially supported by the Centre for Numerical Algorithms and Intelligent Software (funded by EPSRC grant EP/G036136/1 and the Scottish Funding Council). The second author also acknowledge support from the EPSRC Grant EP/K02325X/1, Accelerated Coordinate Descent Methods for Big Data Optimization. Funding Information: This work appeared on arXiv in October 2013 (arXiv:1310.3438 ). P. Richt{\'a}rik and M. Tak{\'a}? were partially supported by the Centre for Numerical Algorithms and Intelligent Software (funded by EPSRC grant EP/G036136/1 and the Scottish Funding Council). The second author also acknowledge support from the EPSRC Grant EP/K02325X/1, Accelerated Coordinate Descent Methods for Big Data Optimization. Publisher Copyright: {\textcopyright} 2015, The Author(s).",
year = "2016",
month = aug,
day = "1",
doi = "10.1007/s11590-015-0916-1",
language = "English (US)",
volume = "10",
pages = "1233--1243",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer Verlag",
number = "6",
}