Bridging conformal prediction and scenario optimization
Niall O’Sullivan, Licio Romao, Kostas Margellos · 2025
Read Bridging conformal prediction and scenario optimization by Niall O’Sullivan, Licio Romao, Kostas Margellos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23561.txt.
Introduction
Niall OSullivan, Licio Romao, and Kostas Margellos connect two frameworks that both promise safe decisions from limited data. Conformal prediction builds sets that contain the true outcome with a stated confidence. Scenario optimization solves a decision problem using sampled cases and bounds the chance that a hidden rule is broken. The two literatures grew apart, and their similar-looking guarantees were never cleanly tied together. Writing in twenty twenty-five, the authors start from the basic form of conformal prediction and choose its scoring and set-building pieces in a pointed way.
With those choices, the classic scenario bounds on rule-breaking probability come back exactly. The bookkeeping of ranked scores is itself shown to be a small scenario problem with some constraints thrown away, which returns the conformal guarantee from the other side. The bridge also lets the authors analyze a conditional form of conformal prediction with scenario tools.
Catalog record
| CREATOR | Niall O’Sullivan, Licio Romao, Kostas Margellos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23561
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bridging conformal prediction and scenario optimization Niall O’Sullivan, Licio Romao, Kostas Margellos Abstract Conformal prediction and scenario optimization constitute two important classes of statistical learning frameworks to certify decisions made using data. They have found numerous applications in control theory, machine learning and robotics. Despite intense research in both areas, and apparently similar results, a clear connection between these two frameworks has not been established. By focusing on the so-called vanilla conformal prediction, we show rigorously how to choose appropriate score functions and set predictor map to recover well-known bounds on the probability of constraint violation associated with scenario programs. We also show how to treat ranking of nonconformity scores as a one-dimensional scenario program with discarded constraints, and use such connection to recover vanilla conformal prediction guarantees on the validity of the set predictor. We also capitalize on the main developments of the scenario approach, and show how we could analyze calibration conditional conformal prediction under this lens. Our results establish a theoretical bridge between conformal prediction and scenario optimization. I Introduction Modern operations in critical infrastructures, such as transportation, power systems, and robotics, rely on past data to make informed decisions on long-term planning and real-time operation strategies. In the context of power systems, flexibility aggregators make decisions using available data to manage their energy resources, while providing services to the electricity grid, e.g., see [ 1 , 2 ] . Similar high-stake decisions are made in the context of autonomous systems, where robots must make decisions based on available data to navigate in unknown environments while safely achieving their goals; see [ 3 ] and references therein. Conformal prediction and the scenario approach theory constitute widely employed techniques that enable a user to rigorously certify the underlying decision-making process. The former, originally proposed in seminal papers [ 4 , 5 , 6 ] , has gained prominence within the control community due to its simplicity and strong guarantees. It has been recently applied to a wide range of applications, including drug discovery, robotic motion planning, and several machine learning frameworks [ 7 , 8 , 3 ] . Main ingredients of conformal prediction include the set predictor, which is an output set that contains a new sample with a probability that can be quantified in a distribution-free manner; and the nonconformity scores, which are used to assess the quality of the decision and inform the construction of the set predictor. In the conformal prediction setting, the resulting predictor set is accompanied by distribution-free guarantees on its validity [ 9 , 6 , 10 , 7 ] , where validity relates to the property of the set predictor contains a pre-specified mass of all possible samples. The so-called scenario approach has been developed in a series of seminal papers [ 11 , 12 , 13 , 14 , 15 ] and has received wide attention within the control community due to its ability to attach violation certificates to the solution of an optimization problem. Similarly to conformal prediction, the scenario approach theory has been applied to a wide range of applications, including machine learning [ 16 ] , feedback control design [ 12 , 17 , 18 , 19 , 20 ] , and uncertainty quantification [ 21 ] . The scenario approach involves solving an optimization problem with constraints corresponding to different samples/realizations of some uncertain parameter. A fundamental result has been the (exact) characterization of the cumulative distribution and the expected value of the so called probability of constraint violation, i.e., the probability that the optimal solution violates the constraint corresponding to a new unseen sample. Such developments serve as generalization guarantees to solutions computed on the basis of a finite number of samples. Recent advancements involve tighter guarantees on scenario optimization with sample discarding [ 22 , 23 ] , connections to statistical learning based on the notion of compression [ 24 , 25 ] , and a posteriori assessements [ 26 ] . Conformal Prediction (Vanilla) Scenario Optimization Conformal Prediction (Calibration Conditional) Theorem 4 Theorem 5 Theorem 6 Fig. 1: Connections between conformal prediction and scenario optimization. From conformal prediction to scenario approach: By appropriate choice of nonconformity scores and a set predictor in vanilla conformal prediction, we recover well-known results on the expected value of the probability of constraint violation in scenario programs (Theorem 4 ). From scenario approach to conformal prediction: By interpreting the ranking of nonconformity scores as an one-dimensional scenario program with discarded constraints, we derive vanilla conformal prediction results (Theorem 5 ). We also view the calibration conditional conformal prediction under the scenario approach lens, using the results on the cumulative distribution of the probability of constraint violation in scenario programs (Theorem 6 ). In this paper we aim at establishing formal relationships between the two approaches, that we believe will open the road for transferring results from one domain to the other. Our main contributions are: 1. From conformal prediction to scenario approach: We show how to choose an appropriate score function and set predictor, at the core of conformal prediction, to bound the expected probability of constraint violation in scenario optimization (Theorem 4). 2. From scenario approach to vanilla conformal prediction: We show that using a specific scenario optimization program together with a discarding mechanism we can view the so called vanilla conformal prediction under a scenario approach lens and establish the corresponding vanilla conformal prediction bounds (Theorem 5). To achieve this, we build on results related to the expected value of the probability of constraint violation in scenario optimization. 3. From scenario approach to calibration conditional conformal prediction: We capitalize on the characterization of the cumulative distribution (rather than the expected value) of the probability of constraint violation in scenario optimization and show how this can be employed to infer calibration conditional conformal prediction bounds (Theorem 6). Besides attempts to contrast conformal prediction and the scenario applications in specific applications [ 27 ] , [ 19 ] , to the best of our knowledge this is the first formal connection between these domains. Our main contributions are also pictorially illustrated in Figure 1 . The remainder of the paper is organized as follows. Section II introduces the main concepts from conformal prediction and the scenario approach that are relevant to our developments, and provides some preliminary results. Section III shows how tools from conformal prediction can be leveraged to obtain certain results of the scenario approach theory. In Section IV we view conformal prediction under a scenario approach lens. We first show how results on the characterization of the probability of constraint violation in scenario optimization can be leveraged to reinterpret the vanilla conformal prediction bounds (Section IV-A ), and then recover the so called calibration conditional conformal prediction results (Section IV-B ). Section V concludes the paper and provides directions for future research. Notation We denote by \mathbb{N} the set of natural numbers. We let \Omega be an abstract probability space and call (\Omega,\mathcal{F},\mathbb{P}) a probability space, where \mathcal{F} is a \sigma -algebra of subsets of \Omega and \mathbb{P} is a probability measure defined on \mathcal{F} . II Background and preliminary results II-A Conformal prediction Conformal prediction has gained significant attention due to its ability