# On the exact feasibility of convex scenario programs with discarded constraints

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2020.

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

- [Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions](https://mlsanity.com/paper/2301.01526/) (2023)
- [Probabilities Are Not Enough: Formal Controller Synthesis for Stochastic Dynamical Models with Epistemic Uncertainty](https://mlsanity.com/paper/2210.05989/) (2022)
- [Safe exploration in reproducing kernel Hilbert spaces](https://mlsanity.com/paper/2503.10352/) (2025)
- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [Bridging conformal prediction and scenario optimization](https://mlsanity.com/paper/2503.23561/) (2025)
- [Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics](https://mlsanity.com/paper/2212.00679/) (2022)
- [Finite sample learning of moving targets](https://mlsanity.com/paper/2408.04406/) (2024)
- [Bridging Conformal Prediction and Scenario Optimization: Discarded Constraints and Modular Risk Allocation](https://mlsanity.com/paper/2603.19396/) (2026)
- [Correct-by-Construction Control for Stochastic and Uncertain Dynamical Models via Formal Abstractions](https://mlsanity.com/paper/2311.09786/) (2023)
- [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)
- [Multi-Variable Conformal Prediction: Optimizing Prediction Sets without Data Splitting](https://mlsanity.com/paper/2605.12341/) (2026)
- [Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification](https://mlsanity.com/paper/2609.01355/) (2026)

## Abstract (arXiv)

We revisit the so-called sampling and discarding approach used to quantify the probability of constraint violation of a solution to convex scenario programs when some of the original samples are allowed to be discarded. Motivated by two scenario programs that possess analytic solutions and the fact that the existing bound for scenario programs with discarded constraints is not tight, we analyze a removal scheme that consists of a cascade of optimization problems, where at each step we remove a superset of the active constraints. By relying on results from compression learning theory, we show that such a removal scheme leads to less conservative bounds for the probability of constraint violation than the existing ones. We also show that the proposed bound is tight by characterizing a class of optimization problems that achieves the given upper bound. The performance improvement of the proposed methodology is illustrated by an example that involves a resource sharing linear program.