- Rating
- 3(−1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper finds a confidence interval for the population mean when there is an adversary that can replace an fraction of the labels. The authors study that in such cases, it is not possible to create a non-trivial asymptotically valid confidence interval without any side information or additional restrictions. The setting of the problem is as follows; suppose that we have a predictor (some ML model) that is trained on uncorrupted values, and during prediction, only the labels of the feature-label dataset are corrupted by the adversary. In such a case, find a confidence interval for the mean of the labels, which is asymptotically valid. The setting is motivated in this paper by taking a sample-survey-based hypothetical scenario where an LLM bypasses the human-authenticator and systematically poisons the survey.
The method involves finding the maximum variance which can be attainable given the setting which still validates the predictor MSE based on the corruption budget, and finding the endpoints to which the means can deviate given the configuration. Finding the maximum attainable variance is non-trivial, and the paper shows that it is an NP-hard problem by reducing it to a subset sum problem. So, they try to come up with a poly-time algorithm that bounds the true maximum value of allowed variance under the MSE constraint V*(MSE) and by a sample evaluated quantity (MSE) which is conservative, in the sense that V*(MSE) (MSE) V*(MSE) , where is empirical standard deviation for the predicted labels. They further argue that it is computationally expensive and come up with another algorithm which is , and claim that it is a good enough estimate. And finally plugging all of them together gives the desired confidence interval.
Critical strengths
I found the feasible set approach quite intuitive. Rather than trying to identify which labels were corrupted, the method considers all clean label vectors consistent with the available information and bounds the uncertainty across them.
The midpoint estimator is the most interesting part of the paper. It achieves the smallest worst case error relative to the clean sample mean for each observed feasible set, and then they proceed to show how to compute it in time.
The computational results complement each other well. After establishing the fact that exact variance maximization is NP-hard, they provide both; an additive approximation algorithm, and a faster upper bound which is guaranteed to be at least as tight as the expensive bound.
Critical weaknesses
The method assumes a known upper bound on the predictor’s MSE for the clean target population. In a heavy tailed setting, estimating prediction error empirically does not automatically provide guarantees. The experiments use bootstrap to calibrate, but the paper does not establish that this procedure supplies a valid bound under its assumptions, and the coverage guarantee depends on , which leaves an important gap to be closed.
The comparisons do not establish the benefit over the simpler alternatives. The prediction-only baseline uses a larger sampling correction than necessary, and a simple clipped-residual estimator can attain the same universal contamination bound as the proposed estimator.
The paper allows corruption of labels while keeping the predictions intact. In an open survey, LLM agents might fabricate demographics and identities as well as answers, changing the inputs used to generate those predictions. A clearer explanation is needed as to how this side information can be protected in application.
Questions for authors
Does the proposed bootstrap calibration provide a valid population MSE bound under the paper’s assumptions? If additional assumptions are needed, can you state them and explain how uncertainty in the estimated bound should enter the final coverage guarantee?
Could you compare it against a prediction only interval using the predictions’ own standard error, and a clipped-residual estimator with the same universal contamination radius guarantee? It would be helpful to understand when the proposed estimator's instance specific radius produces a substantial improvement.
5 comments
Rebuttal: Part 2
[Q2] Thank you for this question. While the clipped-residual estimator achieves the same worst-case bias bound as the midpoint estimator, it does not generally achieve the instance-optimal worst-case bound that the midpoint estimator uses. As we show, this instance-optimal worst-case bound can be substantially better than the worst-case bound in many cases. In particular, we have included updated experimental results on both the election dataset and a synthetic unbounded distribution with the clipped-residual estimator (see EXP_real.pdf and EXP_synthetic_rpdf). Across both datasets, we outperform the prediction-only baseline and the clipped-residual baseline.
We complement these experimental results with a Gaussian example illustrating how the midpoint estimator's instance-dependent corruption radius improves over the universal clipped-residual bound. Consider i.i.d. standard normal clean residuals, with and . The population MSE assumption is satisfied because .
We set an allowed corruption budget of for both methods and compare three scenarios: no actual corruption, moderate corruption, and large corruption. In the latter two scenarios, we select 100 residuals uniformly at random and replace each selected residual by and , respectively.
The table reports average corruption radii over 10,000 simulated samples. The clipped-residual column uses the bound and the midpoint column uses the instance-optimal bias bound.
| Scenario | Midpoint bias | Clipped-residual bias | Radius reduction |
|---|---|---|---|
| No corruption | 0.406 | 0.492 | 17.4% |
| Moderate corruption () | 0.346 | 0.492 | 29.7% |
| Large corruption () | 0.176 | 0.492 | 64.3% |
Interestingly, our method performs even better than the clipped-residual estimator as corruption becomes more extreme. This is because retaining a large observed residual consumes more of the squared-error budget, restricting the set of compatible clean residual vectors and narrowing the range of their means. The midpoint radius adapts to this information, whereas the universal clipped-residual bound depends only on and and therefore remains unchanged across the three scenarios. We will update the manuscript with these examples to further support our midpoint estimator.
Thank you for the additional experiments. The corrected prediction-only baseline confirms the midpoint’s advantage, and the Gaussian example clarifies when the instance dependent radius beats . I would like the following reflected in the revised PDF, not only in the anonymous repository:
Fig. 1d is the only thing inflating . Report coverage when is below the realized RMSE (e.g., –), under an adversary that uses the predictions, such as, your erasure attack. Note that an empty feasible set flags an underestimation. State the extended Assumption 1 with failure probability and the union bound formally, and clarify that the bootstrap certifies the cross fitted models rather than the refitted predictor, and it relies on dev/eval exchangeability. A split with a finite sample upper confidence bound on the bounded loss would close this gap, which would also make the finite-sample slack needed for to be high, explicit. List as a second assumed budget. Include only the corrected prediction, clipped-residual, support-only and robust-mean baselines in the main text. Mention that the oracle baselines as non-implementable and tuned to the tested attacks, and use consistent wording (“competitive” vs. “outperforms”). Tables 1, 8 and 10 indicate that, the gain comes mainly from the midpoint center and that , so DP is not needed in practice, mention this explicitly and mention NP-hardness and the DP as theoretical complements. Coverage is about 97% at but about 100% for with the same . This proves the conservative nature is mainly from the worst case radius against non adaptive attacks, not only from (l.410–413).
I continue to see the problem, the impossibility result and the midpoint estimator as valuable contributions. To my knowledge this is the first observable CI for a mean under constant fraction of adaptive contamination without a known variance. Robust estimators give bounds that depend on unknown variances, and bootstrap results for trimmed means only work when the contamination decreases with n. The midpoint is optimal for an instance and computable in , and validity holds uniformly over adaptive adversaries. The concerns raised are about assumptions and experiments, not about errors in the theory. 179b’s robust baselines are provided, in the repository. The support only argument is correct and favors the method. ECP5’s prediction only correction has been amended, and the midpoint still dominates.
Some of the weaknesses that I concede would be, validity rests on an assumed (and ). The calibration is based on heuristic, and their underestimation is not tested. Most of the practical gain comes from the midpoint rather than the variance theorized in the paper. In Q1/Q2 a clean set exists. The new results are not yet in the PDF. These can be fixed, provided the revision includes the baselines and a -misspecification experiment.
I remain in favor of acceptance but I wish to recalibrate from 4 to 3, following the weaknesses I have raised.
Rebuttal: Part 1
Thank you for your thoughtful review and appreciation of our work and approach. We would like to address some of your comments below. We include supplemental experiments (referenced throughout) here: https://anonymous.4open.science/r/Robust-Confidence-Intervals-Using-Side-Information-5D68/
We split the rebuttal into two comments; [Q2] is addressed in the next comment.
[W1] Thank you for this comment; we address it in [Q1]. If you have follow-up questions from our response, we’d be more than happy to address them!
[W2] We have run updated experiments using both the updated prediction-only baseline and the clipped mean estimator across the original election dataset and a synthetic unbounded dataset (see EXP_real.pdf and EXP_synthetic.pdf). Across both the election data and the synthetic dataset, our midpoint estimator outperforms the prediction-only baseline, the clipped-residual baseline, and two common robust mean estimators.
[W3] This is a good suggestion, and we will add further discussion of adversarial contamination of covariates. For the sentiment analysis experiments in our paper, the pollster holds the raw text corpus, and the adversary is an annotator who can only assign labels to the texts. Since the annotator cannot modify the texts used to generate the predictions, the predictions remain protected from manipulation.
[Q1] Assumption 1 can be extended to allow a population MSE bound that holds with probability at least 1−δa. It is then straightforward to show that our asymptotic coverage theorem can account for the assumption's failure probability using a union bound. More precisely, we can guarantee an asymptotic coverage of at least 1−δa−α, where α is the confidence parameter in the original theorem statement. Thus, to obtain overall asymptotic coverage of at least 95, we allocate the error budget so that α+δa≤0.05.
Our theoretical framework assumes that a valid upper bound β on the predictor's population root mean squared error is given. Alternatively, β can be viewed as a prediction-error budget: we need not know the exact accuracy of f, but our guarantees hold whenever its population RMSE is below β. Bootstrap calibration is not part of our theoretical guarantees; rather, it is a practical design choice we used to obtain an informative value of β for our real-data experiments, where the population prediction error is unknown, and the available data must support both predictor development and evaluation.
We calibrated β on separate development data before test-set evaluation. As reported in the paper, we subsequently audited the clean held-out test sample and verified that its empirical prediction MSE was bounded by the chosen β. This provides evidence that the calibration was adequate for the evaluated sample, although it does not establish a theoretical certificate for the population MSE.
We believe this is also an interesting avenue for future research: how best to estimate β in practice, or which applications are conducive to obtaining a meaningful β from past data. In a future iteration, we also believe it would be valuable to do sensitivity tests to coverage guarantees for the midpoint estimator when β is underestimated. We will clarify these distinctions in the revised manuscript through a discussion section.