Budget-constrained stochastic approximation

Uday V. Shanbhag, Jose H. Blanchet

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations


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.

Original languageEnglish (US)
Title of host publication2015 Winter Simulation Conference, WSC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9781467397438
StatePublished - Feb 16 2016
EventWinter Simulation Conference, WSC 2015 - Huntington Beach, United States
Duration: Dec 6 2015Dec 9 2015

Publication series

NameProceedings - Winter Simulation Conference
ISSN (Print)0891-7736


OtherWinter Simulation Conference, WSC 2015
Country/TerritoryUnited States
CityHuntington Beach

All Science Journal Classification (ASJC) codes

  • Software
  • Modeling and Simulation
  • Computer Science Applications


Dive into the research topics of 'Budget-constrained stochastic approximation'. Together they form a unique fingerprint.

Cite this