On almost sure rates of convergence for sample average approximations
Dirk Banholzer (dirk.banholzersoton.ac.uk)
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.
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|