Faster Coordinate Descent via Adaptive Importance Sampling

By Dmytro Perekrestenko, Volkan Cevher, Martin Jaggi. 2017

42 citations recorded by the source corpus.

Coordinate descent methods employ random partial updates of decision variables in order to solve huge-scale convex optimization problems. In this work, we introduce new adaptive rules for the random selection of their updates. By adaptive, we mean that our selection rules are based on the dual residual or the primal-dual gap estimates and can change at each iteration. We theoretically characterize the performance of our selection rules and demonstrate improvements over the state-of-the-art, and extend our theory and algorithms to general convex objectives. Numerical evidence with hinge-loss support vector machines and Lasso confirm that the practice follows the theory.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, background): “Closely related to our work is Perekrestenko et al. (2017) who analyzed several adaptive sampling strategies for a generalization of the primal-dual SDCA setup, including our proposed gap sampling scheme.”
Balanced Mini-batch Sampling for SGD Using Determinantal Point Processes (2017, background): “A second class of methods relies on non-uniform sampling of mini-batches [8, 11, 33, 39, 48, 49].”
Safe Adaptive Importance Sampling (2017, background): “For instance both extreme cases c k = (cid:96) k and c k = u k (the latter choice is quite common, cf. [36, 23]) might be poor.”
Distributed Learning with Sparse Communications by Identification (2018, methodology): “ng [71, 52], that can sometimes be used in practice. The idea of adaptive coordinate descent methods based on the coordinate-wise Lipschitz constants and current values of the gradient is proposed in [49,42,60]. The idea of adaptively using the iterates structure enforced by a non-smooth regularizer”
Stochastic Learning on Imbalanced Data: Determinantal Point Processes for Mini-batch Diversification (2017, background): “A second class of methods relies on non-uniform sampling of minibatches [8, 11, 32, 38, 47, 48].”
Approximate Steepest Coordinate Descent (2017, background): “…in (Shalev-Shwartz & Zhang, 2013; Friedman et al., 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).”
Efficient Use of Limited-Memory Accelerators for Linear Learning on Heterogeneous Systems (2017, background): “In contrast to existing importance sampling schemes [17, 12, 5] which assign static probabilities to individual coordinates, our selection scheme (11) is dynamic and adapts to the current state α of the algorithm, similar to that used in [9, 11] in the standard non-heterogeneous setting.”
Advances in Variational Inference (2017, background): “Several authors suggested variants of importance sampling in the context of mini-batch selection [32], [55], [148], [226].”