Sample complexity of sample average approximation for conditional stochastic optimization

DOI10.1137/19M1284865MaRDI QIDQ5116551zbMATH OpenFDO

Authors

Publication date 18 August 2020

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.11957

zbMATH Keywords

stochastic optimizationsample average approximationlarge deviations theory

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Nonlinear programming (90C30) Stochastic programming (90C15)

Abstract: In this paper, we study a class of stochastic optimization problems, referred to as the emph{Conditional Stochastic Optimization} (CSO), in the form of $mi{n}_{xinmathcalX}E{E}_{xi}{f}_{x}iBig(E{E}_{eta|xi}[g_{e}ta(x,xi)]Big)$, which finds a wide spectrum of applications including portfolio selection, reinforcement learning, robust learning, causal inference and so on. Assuming availability of samples from the distribution $PP(xi)$ and samples from the conditional distribution $PP(eta|xi)$, we establish the sample complexity of the sample average approximation (SAA) for CSO, under a variety of structural assumptions, such as Lipschitz continuity, smoothness, and error bound conditions. We show that the total sample complexity improves from $cO(d/ep{s}^4)$ to $cO(d/ep{s}^3)$ when assuming smoothness of the outer function, and further to $cO(1/ep{s}^2)$ when the empirical function satisfies the quadratic growth condition. We also establish the sample complexity of a modified SAA, when $xi$ and $eta$ are independent. Several numerical experiments further support our theoretical findings. Keywords: stochastic optimization, sample average approximation, large deviations theory

Recommendations

• A note on sample complexity of multistage stochastic programs
• Sample average approximation method for compound stochastic optimization problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Robust sample average approximation
• Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
• Accelerating Stochastic Composition Optimization
• Approximation of Carathéodory functions and multifunctions
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• CVXPY: a Python-embedded modeling language for convex optimization
• Convergence of the empirical mean method in statistics and stochastic programming
• Decomposition methods in stochastic programming
• Error bounds, quadratic growth, and linear convergence of proximal methods
• From error bounds to the complexity of first-order descent methods for convex functions
• Kernel smoothing for nested estimation with application to portfolio risk measurement
• Learnability, stability and uniform convergence
• Lectures on Stochastic Programming
• Multi-stage stochastic optimization applied to energy planning
• On complexity of multistage stochastic programs
• On complexity of stochastic programming problems
• Optimization methods for large-scale machine learning
• Risk bounds for statistical learning
• Robust sample average approximation
• Sample average approximation method for chance constrained programming: Theory and applications
• Sample average approximation method for compound stochastic optimization problems
• Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• Statistical estimation of composite risk functionals and risk optimization problems
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• The sample average approximation method for stochastic discrete optimization
• Understanding machine learning. From theory to algorithms

Cited in

(13)

• Solving Nonsmooth and Nonconvex Compound Stochastic Programs with Applications to Risk Measure Minimization
• A nested benders decomposition-based algorithm to solve the three-stage stochastic optimisation problem modeling population-based breast cancer screening
• Distributed stochastic compositional optimization problems over directed networks
• A functional model method for nonconvex nonsmooth conditional stochastic optimization
• Sample average approximation for stochastic programming with equality constraints
• Stochastic approximation versus sample average approximation for Wasserstein barycenters
• Improved complexities for stochastic conditional gradient methods under interpolation-like conditions
• Optimal sample complexity of subgradient descent for amplitude flow via non-Lipschitz matrix concentration
• The sample average approximation method for stochastic discrete optimization
• An Improved Unconstrained Approach for Bilevel Optimization
• An inexact semismooth Newton SAA-based algorithm for stochastic nonsmooth SOC complementarity problems with application to a stochastic power flow programming problem
• Streaming constrained binary logistic regression with online standardized data
• Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization

Describes a project that uses

Uses Software

• SBEED
• CVXPY

This page was built for publication: Sample complexity of sample average approximation for conditional stochastic optimization

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