Technical Summary: Calibrating Decision Robustness via Inverse Conformal Risk Control

1. Problem Statement

Decision-making under uncertainty is a fundamental challenge in operations research and machine learning. Robust Optimization (RO) addresses this by optimizing decisions against worst-case scenarios within a prespecified uncertainty set. However, the effectiveness of RO hinges on the robustness level (e.g., the radius of the uncertainty set or the confidence level in Conformal Prediction).

Current practices typically select this level ad hoc (e.g., fixing a 95% confidence level) or via heuristics. This approach presents a critical gap:

• Insufficient Protection: A level chosen without rigorous guidance may fail to protect against adverse outcomes.
• Over-conservatism: A level chosen too conservatively leads to costly, suboptimal solutions.
• Lack of Trade-off Visibility: Existing methods, including recent Conformal Prediction (CP) approaches that define data-driven uncertainty sets, fix the coverage target a priori. They offer little guidance on the specific trade-off between miscoverage (the probability the outcome falls outside the set) and regret (the cost relative to an oracle decision) across different robustness levels.

The paper asks: How can decision-makers evaluate and select robustness levels with explicit, reliable trade-offs between protection (low miscoverage) and efficiency (low regret)?

2. Methodology: Inverse Conformal Risk Control (CREME)

The authors propose a new framework called Conformal REgret Miscoverage Estimate (CREME). Unlike standard Conformal Risk Control (CRC), which starts with a target risk level and finds a set to satisfy it, CREME inverts this logic. It takes a family of uncertainty sets (indexed by a robustness parameter $\lambda$) as given and certifies the actual risk levels they incur.

Core Components

1. Risk Estimators:
   The method constructs valid estimators for two metrics across all $\lambda \in \Lambda$:

   • Miscoverage ($I_\lambda$): The indicator that the realized outcome $Y$ is outside the uncertainty set $U_\lambda(X)$.
   • Regret ($R_\lambda$): The difference between the cost of the robust decision $z^*_\lambda$ and the optimal cost for the realized outcome.

   The estimators $\hat{\alpha}_I(\lambda)$ and $\hat{\alpha}_R(\lambda)$ are designed to be upper bounds on the true expected miscoverage and regret, respectively.

2. The Estimator Formulation:
   Using a calibration dataset $D = \{(X_i, Y_i)\}_{i=1}^n$, the method computes the empirical average loss $\bar{\ell}_n(\lambda)$. The risk estimator is defined as:
   $$\hat{\alpha}_\ell(\lambda) = \inf \left\{ \alpha \in (0, B) : B - \bar{\ell}_n(\lambda) \geq \frac{\lceil (n+1)(B-\alpha) \rceil}{n} \right\}$$
   where $B$ is an upper bound on the loss function. A computationally efficient upper bound is derived as:
   $$\tilde{\alpha}_\ell(\lambda) = \frac{n}{n+1}\bar{\ell}_n(\lambda) + \frac{B}{n+1}$$
   This formulation provides distribution-free, finite-sample guarantees that the estimated risk upper bounds the true risk.

3. The Certified Pareto Frontier:
   By varying $\lambda$, the method traces a curve of $(\hat{\alpha}_I(\lambda), \hat{\alpha}_R(\lambda))$. Under the assumption of majorant consistency (shrinking the uncertainty set does not increase the conditional expected cost), this curve is weakly decreasing and characterizes the Pareto frontier of the robust policy family. This allows decision-makers to visualize the exact trade-off: how much regret is saved by accepting a specific increase in miscoverage.

4. Handling Post-Hoc Selection (Data Splitting):
   A critical statistical challenge arises if a decision-maker selects $\lambda$ after observing the estimated frontier (post-hoc selection), as this breaks the exchangeability assumption required for validity. To address this, CREME employs a data-splitting strategy:

   • Split 1 ($D_1$): Used to construct the Pareto frontier and allow the decision-maker to select a preferred $\hat{\lambda}$.
   • Split 2 ($D_2$): Used to compute a re-calibrated risk estimate for the selected $\hat{\lambda}$.
     This ensures that the final reported miscoverage and regret guarantees remain valid with finite-sample coverage, even after the selection step.

3. Key Contributions

1. Inverse Conformal Risk Control Framework: The paper proposes a principled framework for "inverse" CRC, enabling risk quantification with respect to arbitrary loss functions (specifically miscoverage and regret) for any given robustness level.
2. Certified Pareto Frontier: The authors develop a distribution-free estimator that constructs a certified Pareto frontier for robust optimization. This is the first method to provide explicit finite-sample guarantees on the trade-off between miscoverage and regret.
3. Post-Hoc Validity via Splitting: The paper addresses the statistical pitfalls of data-dependent parameter selection by integrating a data-splitting technique that restores exact finite-sample validity for the selected robustness level.
4. Broad Applicability: The framework is demonstrated to be applicable across classical optimization formulations, including linear programming, the newsvendor problem, portfolio optimization, and shortest path problems.

4. Experimental Results

The authors evaluate CREME on four representative optimization paradigms:

• Linear Programming
• Newsvendor Problem
• Portfolio Optimization
• Shortest Path Problem

Key Findings:

• Validity vs. Accuracy: CREME achieves a superior balance between validity (ensuring the true risk is bounded) and accuracy (tightness of the bound) compared to naive Monte Carlo estimators. While Monte Carlo estimators are accurate but lack validity guarantees, CREME maintains high validity even in small-sample regimes, prioritizing conservatism when data is scarce.
• Decision Quality: When decision-makers use the CREME frontier to select a robustness parameter based on their risk preferences, the selected parameters are near-optimal, closely approximating the true Pareto-optimal trade-off.
• Comparison with Baselines: Standard baselines (Parametric Quantile, Empirical Quantile, and standard Conformal Prediction) tend to be overly conservative. They successfully control miscoverage but often result in significantly higher regret (suboptimal costs) because they do not explicitly optimize the trade-off. CREME guides users toward a balanced solution.
• Computational Efficiency: The method is computationally efficient, with runtime scaling linearly with the number of calibration samples and the size of the robustness parameter grid.

5. Significance and Limitations

Significance:
The paper offers a principled, data-driven methodology for guiding robustness selection. It empowers practitioners to move away from arbitrary or overly conservative heuristics. By visualizing the certified trade-off between safety (miscoverage) and cost (regret), decision-makers can calibrate robustness levels that align with their specific risk tolerances, leading to more cost-effective and reliable decisions in high-stakes environments.

Limitations (as stated by the authors):

1. Bounded Loss Assumption: The theoretical analysis relies on knowing an upper bound $B$ for the loss function. While the authors note that data-driven estimates of $B$ work well in practice, the formal guarantees depend on this bound.
2. Sample Efficiency: The use of data splitting to handle post-hoc selection reduces sample efficiency (using only half the data for the final estimate). The authors suggest future work could integrate stability-based or e-value-based methods to improve this.
3. Exchangeability: The current framework assumes exchangeable data. Extensions to non-exchangeable settings (e.g., time series) are noted as a potential future direction.
4. Solver Errors: The validity assumes exact optimization solutions. While the paper discusses how to incorporate solver sub-optimality gaps, this is left for future development.