Stochastic Dual Coordinate Ascent with Adaptive Probabilities

By Dominik Csiba, Zheng Qu, Peter Richtárik. 2015

98 citations recorded by the source corpus.

This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method to adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

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 Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “Csiba et al. (2015) proposes an adaptive sampling scheme for SDCA for binary classification which unfortunately cannot be generalized to the CRF setting due to an intractable computation. Closely related to our work is Perekrestenko et al. (2017) who analyzed several adaptive sampling strategies for”
Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “To the best of our knowledge, the only other approach that uses an adaptive sampling scheme to guide the optimization with convergence guarantees is the one from Csiba et al. (2015), in the context of the stochastic dual coordinate ascent (SDCA) algorithm.”
Distributed optimization with arbitrary local solvers (2015, methodology): “For instance, this setting has been used previously in [13, 48, 57].”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “…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 & Richt ´ arik, 2015; Csiba et al., 2015; Nguyen et al., 2017; Gower et al., 2018; Zhou, 2018) admit linear convergence on empirical risk…”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “For instance, this setting has been used previously in [164, 143, 37].”
Faster Coordinate Descent via Adaptive Importance Sampling (2017, methodology): “The work of [Csiba et al., 2015] has taken the non-uniform sampling a step further towards adaptive sampling.”
Approximate Steepest Coordinate Descent (2017, background): “, 2007; 2010; Shalev-Shwartz & Tewari, 2011) uniform sampling (UCD) is used, whereas other papers propose adaptive sampling strategies that change over time (Papa et al., 2015; Csiba et al., 2015; Osokin et al., 2016; Perekrestenko et al., 2017).”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “An alternative to choosing adaptive stepsizes is the use of adaptive probabilities [28].”
Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses (2015, methodology): “Further examples include the ability to design distributed variants of the method [20], or the use of importance/adaptive sampling to lower the number of iterations [21, 12, 9, 14].”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, methodology): “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”
Safe Adaptive Importance Sampling (2017, background): “In contrast, adaptive importance sampling strategies constantly re-evaluate the relative importance of each data point during training and thereby often surpass the performance of static algorithms [22, 5, 26, 10, 21, 23].”
Efficient Use of Limited-Memory Accelerators for Linear Learning on Heterogeneous Systems (2017, background): “Related to this notion, [3, 9, 11] have explored the use of similar information as an adaptive measure of importance, in order to adapt the sampling probabilities of coordinate descent.”
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].”