Budget-constrained stochastic approximation

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 Nk samples are utilized at step k and the total simulation budget is M, where equation 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 (Nk = N) under constant and diminishing steplengths and prove linear convergence in terms of expected error in solution iterates based on prescribing Nk in terms of simulation and computational budgets; (II) we extend the linear convergence rates to the setting where Nk 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-squared error.