On almost sure rates of convergence for sample average approximations
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.
Entry Submitted: 01/25/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|