- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The authors propose Budget-First Conformal Robustness Control for decision-making under pointwise deployment budgets. The method learns budget-feasible decision rule and certifies failure risk control under independent data. Experiments include continuous robust decision-making, image classification, and finite-candidate answer shortlisting.
Critical strengths
The paper considers a practically relevant budget-first setting, where every output should satisfy a prescribed budget.
Critical weaknesses
However, I'm not sure whether the upper-bound objective in (8) is a suitable surrogate for actual failure risk, particularly when model probabilities are estimated inaccurately. Moreover, the advantage of this formulation over directly minimizing failure risk is insufficiently explained. These two concerns lead me to recommend weak rejection. I would consider raising my score if the authors clearly address both points.
Questions for authors
-
In the continuous setting, the expected model-assigned probability outside the prediction set, , may differ substantially from the actual failure risk. Even if two models, and , yield the same value of this quantity, their actual failure risks may differ substantially. In (8), is it reasonable to require this quantity to be an upper bound on the actual failure risk and then minimize it? Are there experimental results showing that this quantity is close to the actual failure risk for the trained model ?
-
In the continuous experiment, the budget requires (r(x)\leq T). Why not set (r(x)\equiv T) and directly minimize the sample version of (\mathbb P{\phi(Y,z(X))>T})? What statistical or computational advantage does the proposed formulation offer over this direct objective? A comparison would help clarify its benefit.
5 comments
Response to Reviewer xtWF (Part 2/3)
Q1 (continued).
Empirical verification. Table R1 compares the level with the failure risk of the exact deployed rule on independent test data. Besides BCRC, it reports a Direct-risk variant that uses the same set family and deployment rule but minimizes the smoothed failure risk directly, without the level term and the constraint.
Table R1. Continuous experiment. Gap is minus failure risk.
| Budget | BCRC level | BCRC failure risk | Gap (pp) | Direct-risk level | Direct-risk failure risk | Gap (pp) |
|---|---|---|---|---|---|---|
| 5 | 0.486 | 0.489 | −0.30 | 0.472 | 0.489 | −1.72 |
| 8 | 0.374 | 0.375 | −0.05 | 0.370 | 0.375 | −0.53 |
| 10 | 0.318 | 0.308 | +0.99 | 0.283 | 0.307 | −2.40 |
| 12 | 0.238 | 0.249 | −1.11 | 0.214 | 0.249 | −3.53 |
BCRC and Direct-risk have similar observed failure risks across all four budgets, with all paired 95% confidence intervals for their differences containing zero. Their levels differ. BCRC’s level is within 1.1 pp of its failure risk, while Direct-risk’s is lower at all four budgets, by up to 3.5 pp.
Robustness to inaccurate probabilities. We replaced only the true noise with heavy-tailed multivariate noise or skewed lognormal noise (, standardized to mean zero and unit variance). Table R2 also includes the best budget-adapted conformal baseline and the direct method of Q2 (Direct Decision Network). At every budget BCRC has the exceedance risk closest to the oracle, and its level stays within 1.2 pp of its failure risk.
Table R2. Misspecified noise with the Gaussian model unchanged. Gap is minus failure risk.
| Noise | Oracle | BCRC | Best adapted baseline | Direct Decision Network | Gap (pp) | |
|---|---|---|---|---|---|---|
| 5 | 0.4852 | 0.4858 | 0.4888 | 0.4875 | −0.34 | |
| 8 | 0.3702 | 0.3712 | 0.3734 | 0.3732 | −1.17 | |
| 10 | 0.3078 | 0.3087 | 0.3114 | 0.3186 | −0.76 | |
| 12 | 0.2475 | 0.2480 | 0.2504 | 0.2590 | −0.67 | |
| Lognormal | 5 | 0.4840 | 0.4863 | 0.4876 | 0.4873 | −0.65 |
| 8 | 0.3694 | 0.3715 | 0.3723 | 0.3737 | −0.69 | |
| 10 | 0.3067 | 0.3085 | 0.3096 | 0.3189 | −0.35 | |
| 12 | 0.2461 | 0.2476 | 0.2483 | 0.2614 | −0.63 |
Response to Reviewer xtWF (Part 3/3)
Q2. Why not set and directly minimize failure risk? What statistical or computational advantage does BCRC offer?
In the continuous experiment, the budget is , so setting and directly minimizing is a valid alternative, with the same oracle minimum as Eq. (4). Compared with directly learning a decision policy, BCRC achieves better sample efficiency in our experiments and provides input-dependent certificates that are tighter than on many inputs. It also applies to budgets other than .
Budgets other than . Setting is optimal only when the certificate is the only quantity under the budget. For the portfolio cost of Section 3.1, setting violates the budget. BCRC needs no change, since the robust problem (5) includes this cost and the budget selects the set size.
Statistical advantage. Fixing simplifies the optimization problem, but learning a low-risk decision policy from finite data remains challenging. The direct method parameterizes and optimizes a smoothed threshold-exceedance loss, whose gradient becomes small when the loss is far from . BCRC instead learns a conditional outcome model and derives decisions through budget-feasible uncertainty sets. This structured approach provides additional learning signals from the full outcomes, which we find improves sample efficiency. On inputs where the budget constraint is binding, the resulting decision minimizes the probability of exceeding under the fitted Gaussian model. To test this, we implemented the reviewer's proposal as a Direct Decision Network and compared the two methods across training-set sizes.
Table R3. BCRC minus Direct Decision Network in realized test exceedance rate (pp).
| 200 | −0.59 | −1.03 | −2.43 | −3.47 |
| 500 | −0.48 | −0.59 | −1.17 | −2.09 |
| 1,000 | −0.20 | −0.33 | −1.27 | −1.87 |
| 1,500 | −0.21 | −0.21 | −1.11 | −1.76 |
All 16 paired bootstrap 95% CIs exclude zero, and the gap is largest for small training sets. At , BCRC is within 0.02–0.15 pp of the exact oracle , and the Direct Decision Network within 0.2–1.9 pp.
Input-dependent certificates. With , every decision is reported with the same bound . BCRC reports the worst-case loss over the deployed set, which equals only where the budget is binding. On 4% / 26% / 25% / 37% of test inputs at , the largest set in the family already fits within the budget. The certificate on these inputs averages 2.6 / 4.5 / 6.0 / 7.8. Across all test inputs, measuring failure against BCRC's own certificates rather than increases empirical failure risk by at most 0.013 percentage points. Thus, the tighter certificates incur virtually no additional observed failure risk.
Thank you again for the careful and constructive review. We hope these responses address both of your concerns, and we are happy to provide any further clarifications to help your evaluation.
Response to Reviewer xtWF (Part 1/3)
We sincerely thank the reviewer for the thoughtful questions. In response, we (a) added a new Proposition R1 with empirical verification and (b) compared BCRC with the reviewer’s proposed direct method under matched settings. We respond to each question in detail below.
Q1. Is the objective in Eq. (8) a suitable surrogate for the failure risk, particularly when model probabilities are inaccurate?
Setup. The goal is the budget-first problem (4), which minimizes the failure probability P{ϕ(Y,z(X))>r(X)} subject to the pointwise budget C(z(x),r(x),x)≤T. BCRC restricts the rule to a nested family of sets Uθ(x;s). For each input it deploys the largest set that meets the budget and takes the robust decision zθ(x) and its worst-case loss rθ(x) over that set. The target thus becomes minimizing the failure risk P(Eθ(X,Y)=1) over θ, where Eθ indicates ϕ(Y,zθ(X))>rθ(X). BCRC solves it through Eq. (8), which minimizes E[αˉθ(X)] subject to P(Eθ(X,Y)=1)≤E[αˉθ(X)], where αˉθ(x)=Pθ(Y∈/Uθ(x)∣x) is the probability that the fitted model assigns outside the deployed set.
Direct failure-risk minimization determines the deployed rule but leaves the model-assigned risk level unconstrained, since different parameterizations can induce the same rule while assigning different probabilities outside the set. Because the true miscoverage of the deployed set upper-bounds the failure risk, the model-assigned miscoverage is the natural counterpart of the level α in (2), and BCRC uses its average as the learning objective. This upper-bound relation may fail for estimated probabilities, so Eq. (8) requires the level to upper-bound the failure risk. Under the conditions of Proposition D.4, its solutions keep the minimum failure risk, and their level equals that risk.
Theoretical guarantees. Let θA solve Eq. (8), and let θR minimize the failure risk among the parameters that satisfy its constraint. Proposition D.2 gives
0≤P(EθA=1)−P(EθR=1)≤E[αˉθR(X)]−P(EθR=1).
We strengthen this result with a new Proposition R1 (Proposition D.4 in the revision): if a risk-minimizing rule in the family can be reparameterized so that its deployed decision and certificate stay the same while E[αˉθ(X)] equals its failure risk, then every minimizer of (8) satisfies
E[αˉθA(X)]=P(EθA(X,Y)=1)=minθ∈ΘP(Eθ(X,Y)=1).
In the continuous Gaussian family, rescaling the covariance provides such a reparameterization where the budget is binding (Appendix D.1). This also addresses the reviewer’s example. If θ1 and θ2 satisfy the constraint with the same E[αˉθ(X)] and θ1 has the lower failure risk, then θ1 can be rescaled to a strictly smaller objective with the same decisions, so θ2 is not a solution.