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 [EQUATION]  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-squared error.
['Uday V. Shanbhag', 'Jose H. Blanchet']
Budget-constrained stochastic approximation