Optimization Online


On almost sure rates of convergence for sample average approximations

Dirk Banholzer (dirk.banholzer***at***soton.ac.uk)
Jörg Fliege (J.Fliege***at***soton.ac.uk)
Ralf Werner (ralf.werner***at***math.uni-augsburg.de)

Abstract: In this paper, we study the rates at which strongly consistent estimators in the sample average approximation approach (SAA) converge to their deterministic counterparts. To be able to quantify these rates at which convergence occurs in the almost sure sense, we consider the law of the iterated logarithm in a Banach space setting and first establish under relatively mild assumptions convergence rates for the approximating objective functions. These rates can then be transferred to the estimators for optimal values and solutions of the approximated problem. Based on these results, we further investigate the asymptotic bias of the SAA approach. Especially, we show that under the same assumptions as before the SAA estimator for the optimal value converges in mean to its deterministic counterpart, at a rate which essentially coincides with the one in the almost sure sense. Further, optimal solutions also convergence in mean; for convex problems with the same rates, but with an as of now unknown rate for general problems. Finally, we address the notion of convergence in probability and conclude that in this case (weak) rates for the estimators can also be derived, and that without imposing strong conditions on exponential moments, as it is typically done for obtaining exponential rates. Results on convergence in probability then allow to build universal confidence sets for the optimal value and optimal solutions under mild assumptions.

Keywords: Stochastic programming, sample average approximation, almost sure rates of convergence, law of the iterated logarithm, convergence in mean

Category 1: Stochastic Programming

Citation: University of Southampton, Department of Mathematical Sciences, Southampton, SO17 1BJ, UK. January 2017.

Download: [PDF]

Entry Submitted: 01/25/2017
Entry Accepted: 01/25/2017
Entry Last Modified: 03/31/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society