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 show that under the same assumptions the SAA estimators converge in mean to their deterministic equivalents, at a rate which essentially coincides with the one in the almost sure sense. Eventually, we address the notion of convergence in probability and conclude that in this case (weak) rates for the estimators can also be derived, but without imposing strong conditions on exponential moments, as it is typically done for obtaining exponential rates.

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: 01/25/2017

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