U. V. Shanbhag and J. H. Blanchet, “Budget-constrained stochastic approximation,” 2015 Winter Simulation Conference (WSC), Huntington Beach, CA, USA, 2015, pp. 368-379, doi: 10.1109/WSC.2015.7408179.
Abstract
Traditional stochastic approximation (SA) schemes employ a single gradient or a fixed batch of noisy gradients in computing a new iterate. We consider SA schemes in which N k samples are utilized at step k and the total simulation budget is M, where Σ k=1 K N k ≤M and K denotes the terminal step. This paper makes the following contributions in the strongly convex regime: (I) We conduct an error analysis for constant batches (N k = N) under constant and diminishing steplengths and prove linear convergence in terms of expected error in solution iterates based on prescribing N k in terms of simulation and computational budgets; (II) we extend the linear convergence rates to the setting where N k is increased at a prescribed rate dependent on simulation and computational budgets; (III) finally, when steplengths are constant, we obtain the optimal number of projection steps that minimizes the bound on the mean …
Authors
Uday V Shanbhag, Jose H Blanchet
Publication date
2015/12/6
Conference
2015 Winter Simulation Conference (WSC)
Pages
368-379
Publisher
IEEE
