Nonasymptotic upper estimates for errors of the sample average approximation method to solve risk averse stochastic programs

DOI10.1137/22M1535425MaRDI QIDQ6423322zbMATH OpenOpenAlexFDO

Authors Volker Krätschmer

Publication date 13 January 2023

Full work available at URL https://doi.org/10.1137/22m1535425

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Stochastic programming (90C15) Limit theorems for vector-valued random variables (infinite-dimensional case) (60B12)

Abstract: We study statistical properties of the optimal value of the Sample Average Approximation. The focus is on the tail function of the absolute error induced by the Sample Average Approximation, deriving upper estimates of its outcomes dependent on the sample size. The estimates allow to conclude immediately convergence rates for the optimal value of the Sample Average Approximation. As a crucial point the investigations are based on a new type of conditions from the theory of empirical processes which do not rely on pathwise analytical properties of the goal functions. In particular, continuity in the parameter is not imposed in advance as often in the literature on the Sample Average Approximation method. It is also shown that the new condition is satisfied if the paths of the goal functions are H"older continuous so that the main results carry over in this case. Moreover, the main results are applied to goal functions whose paths are piecewise H"older continuous as e.g. in two stage mixed-integer programs. The main results are shown for classical risk neutral stochastic programs, but we also demonstrate how to apply them to the sample average approximation of risk averse stochastic programs. In this respect we consider stochastic programs expressed in terms of mean upper semideviations and divergence risk measures.

Recommendations

• First order asymptotics of the sample average approximation method to solve risk averse stochastic programs
• Asymptotics of minimax stochastic programs
• Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
• Sample average approximation of expected value constrained stochastic programs
• Stochastic optimization problems with CVaR risk measure and their sample average approximation

Cited in

(3)

• Sample average approximation for risk-averse problems: a virtual power plant scheduling application
• Sample Size Estimates for Risk-Neutral Semilinear PDE-Constrained Optimization
• First order asymptotics of the sample average approximation method to solve risk averse stochastic programs

This page was built for publication: Nonasymptotic upper estimates for errors of the sample average approximation method to solve risk averse stochastic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6423322)