Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates\n for Minibatches

Accelerated coordinate descent is a widely popular optimization algorithm due\nto its efficiency on large-dimensional problems. It achieves state-of-the-art\ncomplexity on an important class of empirical risk minimization problems. In\nthis paper we design and analyze an accelerated coordinate descent (ACD) method\nwhich in each iteration updates a random subset of coordinates according to an\narbitrary but fixed probability law, which is a parameter of the method. If all\ncoordinates are updated in each iteration, our method reduces to the classical\naccelerated gradient descent method AGD of Nesterov. If a single coordinate is\nupdated in each iteration, and we pick probabilities proportional to the square\nroots of the coordinate-wise Lipschitz constants, our method reduces to the\ncurrently fastest coordinate descent method NUACDM of Allen-Zhu, Qu,\nRicht\\'{a}rik and Yuan.\n While mini-batch variants of ACD are more popular and relevant in practice,\nthere is no importance sampling for ACD that outperforms the standard uniform\nmini-batch sampling. Through insights enabled by our general analysis, we\ndesign new importance sampling for mini-batch ACD which significantly\noutperforms previous state-of-the-art minibatch ACD in practice. We prove a\nrate that is at most ${\\cal O}(\\sqrt{\\tau})$ times worse than the rate of\nminibatch ACD with uniform sampling, but can be ${\\cal O}(n/\\tau)$ times\nbetter, where $\\tau$ is the minibatch size. Since in modern supervised learning\ntraining systems it is standard practice to choose $\\tau \\ll n$, and often\n$\\tau={\\cal O}(1)$, our method can lead to dramatic speedups. Lastly, we obtain\nsimilar results for minibatch nonaccelerated CD as well, achieving improvements\non previous best rates.\n

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.