General feasibility bounds for sample average approximation via Vapnik-Chervonenkis dimension
From MaRDI portal
Publication:5087110
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.
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
Cites work
- scientific article; zbMATH DE number 823069 (Why is no real title available?)
- A Sample Approximation Approach for Optimization with Probabilistic Constraints
- A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support
- A note on bounds for VC dimensions
- A sampling-and-discarding approach to chance-constrained optimization: feasibility and Optimality
- A two-stage stochastic programming framework for transportation planning in disaster response
- A two-stage stochastic programming model for transportation network protection
- Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables
- Ambiguous chance constrained problems and robust optimization
- Asymptotic results of stochastic decomposition for two-stage stochastic quadratic programming
- Best subset selection via a modern optimization lens
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- Central limit theorems for empirical measures
- Complexity estimates for Fourier-Motzkin elimination
- Convergence analysis of sample average approximation of two-stage stochastic generalized equations
- Decomposition algorithms for two-stage chance-constrained programs
- FAST—Fast Algorithm for the Scenario Technique
- High-Dimensional Classification by Sparse Logistic Regression
- Learnability and the Vapnik-Chervonenkis dimension
- Lectures on stochastic programming. Modeling and theory.
- Logarithmic sample bounds for sample average approximation with capacity- or budget-constraints
- On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
- On complexity of stochastic programming problems
- On feasibility of sample average approximation solutions
- Random LSC Functions: An Ergodic Theorem
- Risk-averse two-stage stochastic programming with an application to disaster management
- Sample average approximation method for chance constrained programming: Theory and applications
- Sample average approximation method for compound stochastic optimization problems
- Sample average approximation of expected value constrained stochastic programs
- Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
- Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
- Stochastic decomposition. A statistical method for large scale stochastic linear programming
- The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
- The empirical behavior of sampling methods for stochastic programming
- The optimal sample complexity of PAC learning
- Uncertain convex programs: randomized solutions and confidence levels
- Upper and lower bounds for stochastic processes. Modern methods and classical problems
- Weak convergence and empirical processes. With applications to statistics
Cited in
(4)- Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
- On feasibility of sample average approximation solutions
- 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
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)
