arXiv (Cornell University) · 2017 · 11 citations · 7 references
ComputingComputer ScienceAlgorithmsMachine LearningOptimizationBias-variance TradeoffResampling TechniquesSampling TheoryStochastic OptimizationStochastic ProgrammingBandit AlgorithmsConvergenceConvergence Rate AnalysisConvergence TimeMulti-armed Bandit OptimizationMulti-armed Bandit Variance ReductionOptimization Algorithms
Many stochastic optimization algorithms work by estimating the gradient of the cost function on the fly by sampling datapoints uniformly at random from a training set. However, the estimator might have a large variance, which inadvertently slows down the convergence rate of the algorithms. One way to reduce this variance is to sample the datapoints from a carefully selected non-uniform distribution. In this work, we propose a novel non-uniform sampling approach that uses the multi-armed bandit framework. Theoretically, we show that our algorithm asymptotically approximates the optimal variance within a factor of 3. Empirically, we show that using this datapoint-selection technique results in a significant reduction in the convergence time and variance of several stochastic optimization algorithms such as SGD, SVRG and SAGA. This approach for sampling datapoints is general, and can be used in conjunction with any algorithm that uses an unbiased gradient estimation -- we expect it to have broad applicability beyond the specific examples explored in this work.
7
The Nonstochastic Multiarmed Bandit Problem
Peter Auer, Nicolò Cesa‐Bianchi, Yoav Freund et al. · SIAM Journal on Computing · 2002 · 2.3K citations
Stochastic Optimization with Importance Sampling
Peilin Zhao, Tong Zhang · arXiv (Cornell University) · 2014 · 66 citations · Full text
Importance Sampling for Minibatches
Dominik Csiba, Peter Richtárik · arXiv (Cornell University) · 2016 · 25 citations · Full text