Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling

By Zheng Qu, Peter Richtárik, Tong Zhang. 2015

93 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Federated Learning: Strategies for Improving Communication Efficiency (2016, methodology): “This strategy can be seen as the combination of the master training method and a randomized block coordinate minimization approach [15, 14].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “ethods, which involve extending classical stochastic methods to process multiple data points at a time, have emerged as a popular paradigm for distributed machine learning in data center environments [28, 88, 96, 102, 103]. In practice, however, they have been shown to have limited ﬂexibility to ada”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) (e.g., Takáč et al., 2013; Shalev-Shwartz and Zhang, 2013b; Qu et al., 2015; Richtárik and Takáč, 2016) suﬀer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is…”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “P In particular, let w tk denote the point obtained by minimizing g tk,µ only approximately (for example, using Quartz [14] or S VRG [6, 8]).”
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].”
Distributed optimization with arbitrary local solvers (2015, background): “In general, one would intuitively expect that the optimal choice would be to have Θ such that T A (Θ) = O (1) × c . values In practice, however, the best strategy for any given local solver is to try several for the number of local iterations to estimate the optimal choice.”
SGD: General Analysis and Improved Rates (2019, methodology): “This arbitrary sampling paradigm was later adopted in many other settings, including accelerated coordinate descent for strongly convex functions (Hanzely & Richtárik, 2018), coordinate and accelerated descent for convex functions (Qu & Richtárik, 2016), primal-dual methods (Qu et al., 2015; Chambol”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, background): “ smooth convex optimization [47], composite convex optimization [62], and parallel/subspace descent variants [63]. These results were later further extended to handle arbitrary sampling distributions [58, 59,61,6] . Accelerated variants of RCD were studied in [34,16,1]. For other non-randomized coor”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “…and Variance Reduction Variance reduced methods (Roux et al., 2012; Johnson & Zhang, 2013; Shalev-Shwartz & Zhang, 2013; Defazio et al., 2014; Qu et al., 2015; Shalev-Shwartz, 2016; Qu et al., 2016; Csiba & Richtárik, 2015; Csiba et al., 2015; Nguyen et al., 2017; Gower et al., 2018; Zhou,…”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) [151, 149, 164, 111, 188, 176, 150, 140, 141, 143, 38, 40] suffer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increased.”
99% of Parallel Optimization is Inevitably a Waste of Time (2019, background): “…mention that there are already a few variance reduced methods that scale, up to some level, linearly in a parallel setup: Quartz for sparse data (Qu et al., 2015), Katyusha (Allen-Zhu, 2017), or SAGA/SVRG/SARAH non-with importance sampling for non-convex problems (Horváth & Richtárik,…”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, background): “That is, the support of a sampling 4 For some prior results on importance sampling for minibatches, in the context of QUARTZ, see [5].”
Batched Stochastic Gradient Descent with Weighted Sampling (2016, background): “Importance sampling has also been considered in the related setting of stochastic coordinate descent/ascent methods [15, 16, 17, 18].”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, methodology): “For dual methods based on coordinate descent, importance sampling is relatively well understood (Nesterov, 2012; Richtárik and Takáč, 2014; Qu and Richtárik, 2016; Qu et al., 2015; Allen-Zhu et al., 2016).”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, background): “Like in most optimization problems (see [54, 75, 70, 17]), dual methods have been also developed in the literature of randomized algorithms for solving linear systems [86, 26, 48].”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, unknown): “Alternative variance-reduced method include MISO (Mairal, 2015), FINITO (Defazio et al., 2014b), SDCA (Shalev-Shwartz, 2016), dfSDCA (Csiba & Richt´arik, 2015), AdaSDCA (Csiba et al., 2015), QUARTZ (Qu et al., 2015), SBFGS (Gower et al., 2016), SDNA (Qu et al., 2016), SARAH (Nguyen et al., 2017) and”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, background): “[30] Zheng Qu, Peter Richtárik, and Tong Zhang.”
Importance Sampling for Minibatches (2016, methodology): “These methods include SCD [31], RCDM [20, 26], SDCA [34], Hydra [25, 6], mSDCA [36], APCG [15], AsySPDC [16], RCD [18], APPROX [5], SPDC [39], ProxSDCA [32], ASDCA [33], IProx-SDCA [40], and QUARTZ [23].”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, methodology): “[29] Zheng Qu, Peter Richtárik, and Tong Zhang.”
Coordinate Descent Face-Off: Primal or Dual? (2016, methodology): “In particular, Algorithm 2 has been analyzed in [15].”