Safe Adaptive Importance Sampling

By Sebastian U. Stich, Anant Raj, Martin Jaggi. 2017

60 citations recorded by the source corpus.

Importance sampling has become an indispensable strategy to speed up optimization algorithms for large-scale applications. Improved adaptive variants - using importance values defined by the complete gradient information which changes during optimization - enjoy favorable theoretical properties, but are typically computationally infeasible. In this paper we propose an efficient approximation of gradient-based sampling, which is based on safe bounds on the gradient. The proposed sampling distribution is (i) provably the best sampling with respect to the given bounds, (ii) always better than uniform sampling and fixed importance sampling and (iii) can efficiently be computed - in many applications at negligible extra cost. The proposed sampling scheme is generic and can easily be integrated into existing algorithms. In particular, we show that coordinate-descent (CD) and stochastic gradient descent (SGD) can enjoy significant a speed-up under the novel scheme. The proven efficiency of the proposed sampling is verified by extensive numerical testing.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

FairBatch: Batch Selection for Model Fairness (2020, background): “More recently, importance sampling techniques have been proposed for faster convergence (Loshchilov and Hutter, 2016; Alain et al., 2016; Stich et al., 2017; Csiba and Richt ´ arik, 2018; Katharopoulos and Fleuret, 2018; Johnson and Guestrin, 2018).”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “Importance sampling [1, 12, 30], uses only a subset of the dataset in each epoch to save on computation.”
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”
Training Deep Models Faster with Robust, Approximate Importance Sampling (2018, background): “For more general convex problems, some adaptive sampling strategies include [22] and [23].”