# Performance Bounds for the Scenario Approach and an Extension to a Class of Non-convex Programs

arXiv: https://arxiv.org/abs/1307.0345 · HTML: https://mlsanity.com/paper/1307.0345/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2013.

## Built on by (most cited first, 9 of 9)

- [Compression, Generalization and Learning](https://mlsanity.com/paper/2301.12767/) (2023)
- [A Robust Optimisation Perspective on Counterexample-Guided Repair of Neural Networks](https://mlsanity.com/paper/2301.11342/) (2023)
- [Margin theory for the scenario-based approach to robust optimization in high dimension](https://mlsanity.com/paper/2303.03891/) (2023)
- [Uniform Risk Bounds for Learning with Dependent Data Sequences](https://mlsanity.com/paper/2303.11650/) (2023)
- [Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces](https://mlsanity.com/paper/2405.15509/) (2024)
- [Improved Compression Bounds for Scenario Decision Making](https://mlsanity.com/paper/2501.08884/) (2025)
- [PAC Learnability of Scenario Decision-Making Algorithms: Necessary Conditions and Sufficient Conditions](https://mlsanity.com/paper/2501.08887/) (2025)
- [Online Complexity Estimation for Repetitive Scenario Design](https://mlsanity.com/paper/2509.02103/) (2025)
- [Scenario Approach with Post-Design Certification of User-Specified Properties](https://mlsanity.com/paper/2602.15568/) (2026)

## Abstract (arXiv)

We consider the Scenario Convex Program (SCP) for two classes of optimization problems that are not tractable in general: Robust Convex Programs (RCPs) and Chance-Constrained Programs (CCPs). We establish a probabilistic bridge from the optimal value of SCP to the optimal values of RCP and CCP in which the uncertainty takes values in a general, possibly infinite dimensional, metric space. We then extend our results to a certain class of non-convex problems that includes, for example, binary decision variables. In the process, we also settle a measurability issue for a general class of scenario programs, which to date has been addressed by an assumption. Finally, we demonstrate the applicability of our results on a benchmark problem and a problem in fault detection and isolation.