Coordinate Descent Face-Off: Primal or Dual?

By Dominik Csiba, Peter Richtárik. 2016

12 citations recorded by the source corpus.

Randomized coordinate descent (RCD) methods are state-of-the-art algorithms for training linear predictors via minimizing regularized empirical risk. When the number of examples ($n$) is much larger than the number of features ($d$), a common strategy is to apply RCD to the dual problem. On the other hand, when the number of features is much larger than the number of examples, it makes sense to apply RCD directly to the primal problem. In this paper we provide the first joint study of these two approaches when applied to L2-regularized ERM. First, we show through a rigorous analysis that for dense data, the above intuition is precisely correct. However, we find that for sparse and structured data, primal RCD can significantly outperform dual RCD even if $d \ll n$, and vice versa, dual RCD can be much faster than primal RCD even if $n \ll d$. Moreover, we show that, surprisingly, a single sampling strategy minimizes both the (bound on the) number of iterations and the overall expected complexity of RCD. Note that the latter complexity measure also takes into account the average cost of the iterations, which depends on the structure and sparsity of the data, and on the sampling strategy employed. We confirm our theoretical predictions using extensive experiments with both synthetic and real data sets.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “A directly primal-dual randomized coordinate descent method called Quartz, was developed in [75].”
Semi-Stochastic Gradient Descent Methods (2013, background): “Several recent papers, e.g., Richtárik & Takáč [9], Le Roux, Schmidt & Bach [12, 13], ShalevShwartz & Zhang [14] and Johnson & Zhang [3] proposed methods which achieve such a variancereduction effect, directly or indirectly.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “For a theoretical and computational comparison of applying RCD to the primal versus the dual problems, see [39].”
Rows vs. Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression (2015, background): “The formulations (5) and (6) can be viewed as primal and dual variants, respectively, of the ridge regression problem, and our analysis is related to the analysis in [3] (independent work around the same time as this current work).”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “While there are deep links between standard SGD and RCD methods, these are often indirect and rely on duality (Shalev-Shwartz and Zhang, 2013; Csiba and Richtárik, 2018; Gower and Richtárik, 2015).”