General feasibility bounds for sample average approximation via Vapnik-Chervonenkis dimension
From MaRDI portal
Publication:5087110
DOI10.1137/21M140211XzbMATH Open1495.90119arXiv2103.01324OpenAlexW3133808553WikidataQ114074086 ScholiaQ114074086MaRDI QIDQ5087110FDOQ5087110
Authors: Henry Lam, Fengpei Li 
Publication date: 8 July 2022
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: We investigate the feasibility of sample average approximation (SAA) for general stochastic optimization problems, including two-stage stochastic programming without the relatively complete recourse assumption. Instead of analyzing problems with specific structures, we utilize results from the Vapnik-Chervonenkis (VC) dimension and Probably Approximately Correct learning to provide a general framework that offers explicit feasibility bounds for SAA solutions under minimal structural or distributional assumption. We show that, as long as the hypothesis class formed by the feasbible region has a finite VC dimension, the infeasibility of SAA solutions decreases exponentially with computable rates and explicitly identifiable accompanying constants. We demonstrate how our bounds apply more generally and competitively compared to existing results.
Full work available at URL: https://arxiv.org/abs/2103.01324
Recommendations
- On feasibility of sample average approximation solutions
- Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
- On sample average approximation for two-stage stochastic programs without relatively complete recourse
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Sample average approximation methods for a class of stochastic variational inequality problems
two-stage stochastic programmingVapnik-Chervonenkis dimensionfeasibilitysample average approximationsample complexity
Cites Work
- Weak convergence and empirical processes. With applications to statistics
- Best subset selection via a modern optimization lens
- Title not available (Why is that?)
- Learnability and the Vapnik-Chervonenkis dimension
- A two-stage stochastic programming framework for transportation planning in disaster response
- Risk-averse two-stage stochastic programming with an application to disaster management
- Uncertain convex programs: randomized solutions and confidence levels
- Ambiguous chance constrained problems and robust optimization
- The empirical behavior of sampling methods for stochastic programming
- A Sample Approximation Approach for Optimization with Probabilistic Constraints
- Upper and lower bounds for stochastic processes. Modern methods and classical problems
- Sample average approximation of expected value constrained stochastic programs
- A two-stage stochastic programming model for transportation network protection
- Central limit theorems for empirical measures
- Lectures on stochastic programming. Modeling and theory.
- Sample average approximation method for chance constrained programming: Theory and applications
- Stochastic decomposition. A statistical method for large scale stochastic linear programming
- Decomposition algorithms for two-stage chance-constrained programs
- The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
- A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support
- A sampling-and-discarding approach to chance-constrained optimization: feasibility and Optimality
- On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
- On complexity of stochastic programming problems
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- A note on bounds for VC dimensions
- FAST—Fast Algorithm for the Scenario Technique
- Random LSC Functions: An Ergodic Theorem
- Sample average approximation method for compound stochastic optimization problems
- The optimal sample complexity of PAC learning
- Convergence analysis of sample average approximation of two-stage stochastic generalized equations
- High-Dimensional Classification by Sparse Logistic Regression
- Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables
- Asymptotic results of stochastic decomposition for two-stage stochastic quadratic programming
- On feasibility of sample average approximation solutions
- Complexity estimates for Fourier-Motzkin elimination
- Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
- Logarithmic sample bounds for sample average approximation with capacity- or budget-constraints
- Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
Cited In (4)
- Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
- Statistical learning theory: a pack-based strategy for uncertain feasibility and optimization problems
- An inexact semismooth Newton SAA-based algorithm for stochastic nonsmooth SOC complementarity problems with application to a stochastic power flow programming problem
- On feasibility of sample average approximation solutions
Uses Software
This page was built for publication: General feasibility bounds for sample average approximation via Vapnik-Chervonenkis dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5087110)
