Nonconvex Variance Reduced Optimization with Arbitrary Sampling

By Samuel Horváth, Peter Richtárik. 2018

48 citations recorded by the source corpus.

We provide the first importance sampling variants of variance reduced algorithms for empirical risk minimization with non-convex loss functions. In particular, we analyze non-convex versions of SVRG, SAGA and SARAH. Our methods have the capacity to speed up the training process by an order of magnitude compared to the state of the art on real datasets. Moreover, we also improve upon current mini-batch analysis of these methods by proposing importance sampling for minibatches in this setting. Surprisingly, our approach can in some regimes lead to superlinear speedup with respect to the minibatch size, which is not usually present in stochastic optimization. All the above results follow from a general analysis of the methods which works with arbitrary sampling, i.e., fully general randomized strategy for the selection of subsets of examples to be sampled in each iteration. Finally, we also perform a novel importance sampling analysis of SARAH in the convex setting.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

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 Computer Vision and Pattern Recognition

Citations in the corpus

Natural Compression for Distributed Deep Learning (2019, background): “, variants utilizing minibatching [14], importance sampling [20, 25], momentum [34], or variance reduction [24, 7]), is the cost of communication of the typically dense gradient vector gi(x), and in a parameter-sever implementation with a master node, also the cost of broadcasting the aggregated gra”
SGD: General Analysis and Improved Rates (2019, background): “…(Hanzely & Richt´arik, 2018), coordinate and accelerated descent for convex functions (Qu & Richt´arik, 2016), primal-dual methods (Qu et al., 2015; Chambolle et al., 2018), variance-reduced methods with convex (Csiba & Richt´arik, 2015) and nonconvex (Horv´ath & Richt´arik, 2018) objectives.”
99% of Parallel Optimization is Inevitably a Waste of Time (2019, unknown): “…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, 2018). ar X iv :1 90 1.”
L-SVRG and L-Katyusha with Arbitrary Sampling (2019, methodology): “It was studied in the arbitrary sampling paradigm (Hanzely and Richtárik, 2019; Horváth and Richtárik, 2019).”