acceptodds
Under review as a conference paper at ICLR 2027

Robust Confidence Intervals Using Side Information

Abstract

We study how to construct implementable confidence intervals for the mean of a distribution with unknown, finite variance when an adversary may corrupt a constant fraction of the samples. Although robust mean estimation has been extensively studied, implementable confidence intervals remain elusive. We first observe that no asymptotically valid confidence interval of nontrivial width is possible without additional restrictions or side information. Our main result is that side information, in the form of machine learning predictions with bounded mean squared error (MSE), can enable confidence interval computation. At the core of our method is a reduction of variance estimation to an optimization problem. We prove that although the exact version of this problem is NP-hard, there is a polynomial-time additive approximation algorithm. Based on this result we develop an almost-linear time algorithm that provides an upper bound on the sample variance. We use this upper bound in our novel midpoint estimator and these together yield asymptotically valid confidence intervals uniformly over admissible adversaries. We complement our theoretical study with a series of experiments on the dataset introduced in Cen et al. (2025). We evaluate our method on real-world, bounded data, examining coverage and interval length across multiple corruption levels. Under two corruption strategies that directly try to distort the clean mean or variance of the observed samples, our method maintains coverage and non-trivial length under any considered corruption level less than 50%.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Robust mean estimation, confidence intervals, statistical inference, strong contamination model

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_jfVEOpenReview ↗
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 η\eta 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 β2\beta^2 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 ⁠ Vˉ\bar{V}(MSE) ⁠ which is conservative, in the sense that ⁠ V*(MSE) <Vˉ<\bar{V}(MSE) << V*(MSE) +ϵ(σ^f+β)2+ \epsilon (\hat\sigma_f + \beta)^2⁠, where ⁠ σ^f\hat\sigma_f ⁠ is empirical standard deviation for the predicted labels. They further argue that it is computationally expensive and come up with another algorithm which is O(nlog⁡n)O(n \log n), 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 O(nlog⁡n)O(n\log n) 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 β2\beta^2 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 β\beta, 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
AuthorsOpenReview ↗

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−δa1-\delta_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−α1-\delta_a-\alpha, where α\alpha is the confidence parameter in the original theorem statement. Thus, to obtain overall asymptotic coverage of at least 9595\\%, we allocate the error budget so that α+δa≤0.05\alpha+\delta_a\leq 0.05.

Our theoretical framework assumes that a valid upper bound β\beta on the predictor's population root mean squared error is given. Alternatively, β\beta can be viewed as a prediction-error budget: we need not know the exact accuracy of ff, but our guarantees hold whenever its population RMSE is below β\beta. Bootstrap calibration is not part of our theoretical guarantees; rather, it is a practical design choice we used to obtain an informative value of β\beta 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 β\beta 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 β\beta. 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 β\beta in practice, or which applications are conducive to obtaining a meaningful β\beta 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 β\beta is underestimated. We will clarify these distinctions in the revised manuscript through a discussion section.

AuthorsOpenReview ↗

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 n=1000n=1000 and β=1.1\beta=1.1. The population MSE assumption is satisfied because 1<β2=1.211<\beta^2=1.21.

We set an allowed corruption budget of η=0.1\eta=0.1 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 2β=2.22\beta=2.2 and 10β=1110\beta=11, respectively.

The table reports average corruption radii over 10,000 simulated samples. The clipped-residual column uses the bound R=β2η≈0.492R=\beta\sqrt{2\eta}\approx0.492 and the midpoint column uses the instance-optimal bias bound.

ScenarioMidpoint biasClipped-residual biasRadius reduction
No corruption0.4060.49217.4%
Moderate corruption (2β=2.22\beta=2.2)0.3460.49229.7%
Large corruption (10β=1110\beta=11)0.1760.49264.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 β\beta and η\eta 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 β2η\beta\sqrt{2\eta}. I would like the following reflected in the revised PDF, not only in the anonymous repository:

Fig. 1d is the only thing inflating β\beta. Report coverage when β\beta is below the realized RMSE (e.g., 0.80.8–1.0×1.0\times), 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 δa\delta_a 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 Pr⁡(Gn)\Pr(G_n) to be high, explicit. List η\eta 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 Valign≈VMSE∗V_{\text{align}}\approx V^*_{\text{MSE}}, 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 η=0\eta=0 but about 100% for η≥0.025\eta\ge 0.025 with the same βcal\beta_{\text{cal}}. This proves the conservative nature is mainly from the worst case radius against non adaptive attacks, not only from βcal\beta_{\text{cal}} (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 O(nlog⁡n)O(n\log n), 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 β\beta (and η\eta). 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 β\beta-misspecification experiment.

I remain in favor of acceptance but I wish to recalibrate from 4 to 3, following the weaknesses I have raised.

Reviewer_ECP5OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper constructs robust confidence intervals for a population mean for the scenario that an adversary can corrupt a portion of the labels. The framework assumes trusted predictions, a known population prediction-error bound, and the corruption budget. It characterizes compatible clean samples, develop computational bounds on their maximum variance, and efficiently compute the extreme compatible sample means. Their midpoint estimator has an exact, instance-dependent error radius. Combining this radius with variance-based inflation gives pointwise asymptotic coverage, uniformly over admissible label adversaries.

Critical strengths
  • The clean-sample MSE and sampling events ensure coverage simultaneously for every permitted corruption. This supports the stated adversarial uniformity without requiring independence between the adversary and the sample.
  • The prefix/suffix structure produces an exact O(nlog⁡n)O(n\log n) algorithm. The midpoint’s optimality is especially useful because its observable radius can be substantially smaller than the universal bound.
Critical weaknesses
  • The practical availability of a trustworthy prediction-error bound is unclear. Assumption 1 requires a population MSE bound for the final predictor. Bootstrapping cross-fitted development losses does not establish that certificate for the final refitted model or account for calibration failure in the overall coverage level.
  • The prediction-only baseline is unnecessarily wide. Because predictions remain uncorrupted, the same assumptions justify
fˉ±(β+z1−α/2σ^fn).\bar f\pm\left(\beta+ z_{1-\alpha/2}\frac{\widehat\sigma_f}{\sqrt n}\right).

The paper instead uses σ^f+β\widehat\sigma_f+\beta in the sampling term.

Questions for authors
  • What procedure certifies the population risk of the final predictor, and how does its failure probability enter the desired coverage level?
  • Can you include the tighter prediction-only interval and clipped-residual estimator, reporting both coverage and length?
4 comments
AuthorsOpenReview ↗

Rebuttal: Part 1

Thank you for appreciating our work and for highlighting the usefulness of our midpoint estimator. We hope that our answers below address your concerns and questions. We’d be very happy to engage in further discussion, if the reviewer has more issues they’d like to see addressed. We include supplemental experiments that can be found: https://anonymous.4open.science/r/Robust-Confidence-Intervals-Using-Side-Information-5D68/

We split the rebuttal into two comments; we address [Q2] in the next comment.

[W1] We believe that we have addressed this as a response to [Q1] (please see below). If there’s any further question about the practical availability of such predictors, please let us know.

[W2] Thank you for pointing this out! That improvement is indeed correct, and we will be updating all the experimental results of the paper with this tighter baseline. We emphasize, however, that even with this improvement, our midpoint estimator is still substantially better than the prediction-only estimator.

We have rerun our main experiments with this updated baseline and summarize some results below and include a link to the full results. We refer to this baseline as the mean of predictions + σf\sigma_f in the supplementary experimental material.

We implemented the updated baseline and rerun the original election dataset experiments (see EXP_real.pdf). Indeed, although the baseline correction yields some improvement upon the previous sampling radius, this improvement is relatively minor as the experiments show. Moreover, the midpoint estimator continues to dominate the prediction-only baseline.

[Q1] Assumption 1 can be extended to allow a population MSE bound that holds with probability at least 1−δa1-\delta_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−α1-\delta_a-\alpha, where α\alpha is the confidence parameter in the original theorem statement. Thus, to obtain overall asymptotic coverage of at least 9595\\%, we allocate the error budget so that α+δa≤0.05\alpha+\delta_a\leq 0.05.

Our theoretical framework assumes that a valid upper bound β\beta on the predictor's population root mean squared error is given. Alternatively, β\beta can be viewed as a prediction-error budget: we need not know the exact accuracy of ff, but our guarantees hold whenever its population RMSE is below β\beta. Bootstrap calibration is not part of our theoretical guarantees; rather, it is a practical design choice we used to obtain an informative value of β\beta 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 β\beta 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 β\beta. 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 β\beta in practice, or which applications are conducive to obtaining a meaningful β\beta 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 β\beta is underestimated. We will clarify these distinctions in the revised manuscript through a discussion section.

AuthorsOpenReview ↗

Rebuttal: Part 2

[Q2] Yes, we have updated the experimental results to include the tighter prediction-only interval and clipped-residual estimator. The supplemental experiments can be found at: https://anonymous.4open.science/r/Robust-Confidence-Intervals-Using-Side-Information-5D68/

The midpoint estimator dominates both of these estimators (see EXP_real.pdf)

We also wanted to comment further on the clipped-residual estimator compared to our midpoint estimator. While the clipped-residual estimator achieves the same worst-case bias bound as the midpoint estimator, it generally does not achieve the instance-optimal worst-case bound the midpoint estimator uses. In particular, it ignores the geometry of the sample data (its bound depends only on η\eta and β\beta), which can substantially influence the worst-case bias. As we show, this instance-optimal worst-case bound can be substantially better than the worst-case bound in many cases.

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 n=1000n=1000 and β=1.1\beta=1.1. The population MSE assumption is satisfied because 1<β2=1.211<\beta^2=1.21.

We set an allowed corruption budget of η=0.1\eta=0.1 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 2β=2.22\beta=2.2 and 10β=1110\beta=11, respectively.

The table reports average corruption radii over 10,000 simulated samples. The clipped-residual column uses the bound R=β2η≈0.492R=\beta\sqrt{2\eta}\approx0.492 and the midpoint column uses the instance-optimal bias bound.

ScenarioMidpoint biasClipped-residual biasRadius reduction
No corruption0.4060.49217.4%
Moderate corruption (2β=2.22\beta=2.2)0.3460.49229.7%
Large corruption (10β=1110\beta=11)0.1760.49264.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 β\beta and η\eta 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 rebuttal. The new comparisons against the tighter prediction-only interval and the clipped-residual estimator address my main concern. Given the stronger comparisons, I increased my score from 2 to 3. My remaining concern is how to obtain a reliable prediction-error bound in practice. You explain how to account for the chance that a valid bound fails, but the bootstrap used in the experiments has not been shown to provide such a bound.

Thank you for reading our response and updating your score. We would like to address your remaining concern. We have now updated our manuscript (changes in blue text) with a new main body section titled “Discussion of Assumption 1” (section 6, page 10). In this section, we provide two methods for obtaining β\beta: 1) existing papers may provide such an accuracy parameter; 2) under reasonable assumptions, clean historical data can be used to learn β\beta. We hope this helps resolve this concern, and we are happy to answer additional questions!

Reviewer_179bOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper addresses the challenge of constructing asymptotically valid, finite-width confidence intervals for a population mean under adversarial contamination (η\eta-corruption) when a clean variance bound is unknown. Noting a need for "side-information", the authors propose an assumption that the learner has access to a predictor with known RMSE bound β\beta. They then combine two ingredients: (1) an upper bound on the clean sample variance and (2) an estimator with bounded distance to the clean sample mean. These ingredients are combined to generate asymptotically valid confidence intervals.

Regarding (1), they provide multiple approximation methods. Regarding (2), they propose a "midpoint estimator".

Critical strengths

1.) Well-motivated problem setup. Departing from works like Diakonikolas and others, wherein a bound on the variance is provided, this paper approaches with a bound on a predictor's RMSE.

2.) The authors are pretty thorough with their examination of the problem of computing the largest possible sample variance, given corrupted labels -- showing its NP-Hardness and providing multiple approximations.

Critical weaknesses

1.) In the experiment of Section 5, YY is a bounded, discrete label (an integer sentiment score ranging from -2 to 2). Hence, a trimmed-mean confidence interval would be practical here for a comparison. The "naive" interval that was shown to behave poorly at larger nn is a weak baseline.

2.) Although the motivating Proposition 2.1 showed that the case of unbounded labels forces us to have to incorporate something like "side information," the experiments of this paper examine bounded labels.

3.) The midpoint estimator has bias bn=Θ(βη),b_n = \Theta( \beta \sqrt{\eta} ), which does not shrink with nn, while the sampling error does shrink with nn. Hence, at sufficiently large nn, the width of the authors' confidence interval is pretty much governed by the bias, which might raise questions as to the value of estimating the sample variance so much (Table 8 and Figure 1c)

Questions for authors

I'm on the fence. I would be happy to raise my score if some comparisons with robust baselines could be presented. Below are three suggestions that I think would materially affect my assessment.

Question 1.) Since the experimental labels lie in known bounded sets {-2,0,1,2}, the clean variance is automatically bounded a priori (e.g., σY2≤4\sigma_Y^2 \leq 4 by Popoviciu's inequality).

Hence, there exist some robust baselines are now quite reasonable from a practical and computational standpoint; for example, trimmed/Winsorized mean intervals.

Could the authors' midpoint interval be compared against a bounded-support robust baseline like trimmed mean?

Question 2.) For the experiments with bounded labels in [-2,2], another baseline is to consider estimations in which we no longer enforce the constraint: 1n∑i=1nui2≤β2\frac{1}{n}\sum_{i=1}^n u_i^2 \leq \beta^2. That is, we could drop the use of side information and instead replace with the constraint that zi∈[−2,2]z_i \in [-2,2].

Question 3.) Might there be an experiment that could showcase success of the midpoint estimator confidence interval in a context with unbounded labels?

5 comments
AuthorsOpenReview ↗

Rebuttal Part 1: Weaknesses

Thank you for appreciating our work and for being willing to raise your score, provided that we have answered your questions. We have included supplemental experiments (referenced throughout) that can be found here: https://anonymous.4open.science/r/Robust-Confidence-Intervals-Using-Side-Information-5D68/

We will first address "weaknesses" in this comment and follow up with addressing "questions" in the next comment.

[W1] We appreciate the reviewer’s comment on the bounded scores and would like to provide additional context on our experimental methodology. First, we would like to explain why we did not include the trimmed mean estimator [1] as a baseline in the bounded distribution setting of our experiments. Indeed, as you note, for data in [−2,2][-2, 2], we can get a trivial variance bound of 4 from Popoviciu's inequality. However, even with this variance bound, it is not straightforward to construct meaningful intervals with the trimmed mean estimator in this bounded support setting because the interval’s guarantee includes large, unoptimized constants.

As an example, the explicit variance-based guarantee in Theorem 1 of [1] yields a confidence interval with radius r=208η+24log⁡(4/δ)n,r = 20\sqrt{8\eta+\frac{24\log(4/\delta)}{n}}, after substituting σ2≤4\sigma^2 \leq 4, where nn denotes the total sample size, η\eta the contamination fraction, and 1−δ1-\delta the confidence level. At our largest experimental sample size, n=350n=350, and confidence level 9595\\%, this radius is approximately 10.9610.96 even in the contamination-free case. The resulting interval has width approximately 21.9221.92, so the derived interval trivially covers the entire $ [-2,2] $ range.

Moreover, in many of our experimental settings, we cannot even apply the trimmed mean. For example, with 55\\% corruption, n=350n=350, and confidence level 9595\\%, the trimming quantile specified by [1] is

= 8(0.05)+\frac{12\log 80}{175} \approx 0.7005 > \frac{1}{2}.$$ Since the trimming quantile exceeds $1/2$, the trimmed mean estimator is inadmissible. Other robust mean estimators that we know of share similar issues. For example, consider the Lee-Valiant estimator [2,3]. In Theorem 2.2 and Theorem 2.3 of [2], the irreducible bias term is $\sigma \cdot 222 \sqrt{\eta}$ and $\sigma \cdot 135 \sqrt{\eta}$, respectively. Hence, the resulting interval would again cover the entire support. These examples further highlight the practical applicability of our estimator, which has *small computable constants*. While we believe that many of the constants in these papers can be optimized further, we felt it was outside the scope of our paper to do so. If the reviewer knows of other estimators that they would like to compare our algorithm against, we welcome the suggestions! See also our response to **[Q1]**, where we implemented some versions of the trimmed estimators vs ours. TL;DR: our estimators perform better across a range of configurations. **[W2]** Second, we agree that an unbounded label experiment would be a good addition to the paper, since our impossibility result requires it–and thank you for suggesting it!. We have included such additional experimental results with unbounded synthetic data, which further confirm that our midpoint estimator performs universally better compared to existing robust mean alternatives we test against (see EXP_synthetic.pdf). **[W3]** We agree that for sufficiently large $n$, the bias will dominate the interval width because the sampling term decays with $1/\sqrt{n}$. However, in the strong contamination model, this dependence is *unavoidable*. Our experimental results (Table 9, page 50) support that, for reasonable sample sizes and corruption levels, the sampling radius plays a *meaningful* role in interval width. For example, for the Q1 dataset, with $n=350$ samples and a corruption fraction of $\eta=0.05$, the sampling radius accounts for almost half of the total interval width. Specifically, the bias radius is $0.078$, and the sampling radius is $0.075$. Our experiments also show that optimizing our variance estimation can produce appreciably smaller intervals compared to using the naive variance bound. In Table 8 (page 49), for the same experimental setup as above, our interval length with the optimized variance bound is $0.306$ compared to $0.348$ with the trivial variance bound, which represents a $12\\%$ reduction. References: [1] Lugosi and Mendelson (2021), Robust multivariate mean estimation: the optimality of trimmed mean [2] Lee et al. (2025), All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance [3] Lee and Valiant (2022), Optimal Sub-Gaussian Mean Estimation in R
AuthorsOpenReview ↗

Rebuttal Part 2: Questions

Thank you for your questions; we will address [Q1] and [Q2] in this post and [Q3] in the next. The supplemental experiments can be found at: https://anonymous.4open.science/r/Robust-Confidence-Intervals-Using-Side-Information-5D68/

[Q1] We complement our analysis with experiments comparing against an adaptation of the Lugosi-Olivera trimmed mean [1] and the Lee-Valiant estimators [2]. Per our earlier response (see [W1]), although these estimators achieve optimal error rates up to constant factors, the constants in their theoretical guarantees may lead to conservative confidence intervals.

Concretely, these guarantees are of the form Pr⁡[∣μ^−μ∣≤C(δ,η,n)σ]≥1−δ\Pr[|\widehat{\mu}-\mu| \leq C(\delta,\eta,n)\sigma]\geq 1-\delta, where $ C$ is a constant that depends on $n, \eta, $ and $ \delta$. To derive meaningful baselines for our experiments, we construct for each estimator an “oracle”-based sharp bound that preserves coverage above 95% for any combination of η,n,δ\eta, n, \delta the estimator can operate on. We call them “oracle” because we provide them with the clean population standard deviation and heuristically search for the smallest multiplier C that preserves at least 95% empirical coverage for each tested combination of η\eta and nn (see EXP_baselines_construction.pdf for more). Since we provide them a priori with the clean population standard deviation, these “oracle” baselines are actually unrealistic to compute in practice.

Yet, our results show that our midpoint estimator remains competitive with these sharp baselines at their operating regimes. To demonstrate that these are indeed very strong baselines, we do another experiment on synthetic data: we optimize the midpoint’s derived interval radius using exactly the same oracle procedure; it overall outperforms both baselines (except for the small region where it performs similarly to the oracle Lee-Valiant. That said, we want to stress out that this comparison is not exactly direct: both the trimmed mean and the Lee-Valiant are point estimates that attain the optimal rates up to constants, but, as demonstrated, they were not designed to be turned into practical confidence intervals of the unknown distribution, in the sense that evaluating their theoretical confidence radius requires population quantities that should be unknown. Our work tries to complement exactly that gap by introducing predictions that let us deliver short, observable confidence intervals.

We also comment that both of these standard robust-mean estimators have explicit limits on the fraction of corruption samples that they can tolerate in our setting. At n=350n=350 and δ=0.05\delta=0.05, the Lugosi-Mendelson trimmed mean requires η<0.025\eta < 0.025, which is lower than the settings we test on our main submission. Lee-Valiant requires η<0.33\eta < 0.33 in our setup, but the guarantee analysis requires at least 9⌊ηn⌋+log⁡(1/δ)9\lfloor\eta n\rfloor + \log(1/\delta) median-of-means groups for its sub-Gaussian guarantee; forcing each group to contain at least one observation then gives η<0.11\eta <0.11. For η\eta values beyond this, the estimator reduces to the sample median (see EXP_baselines_construction.pdf for the derivation of the cutoffs). Consequently, our midpoint + ValignV_align interval can withstand a much higher corruption fraction.

[Q2] Thank you for this suggestion! We agree that this bounded-support estimator provides a natural baseline for our bounded-label experiments. However, we also want to highlight that our midpoint estimator and related theorems apply to unbounded distributions, in addition to bounded distributions.

With regard to your suggestion, although the bounded-support estimator has the nice property of not requiring β\beta, this lack of knowledge comes at a cost in terms of interval width. For example, consider the Q1 experiment with n=350n=350, η=0.1\eta=0.1, and k=35k=35. Using only the support constraint [−2,2][-2,2] and the corruption budget, the smallest compatible clean sample mean is obtained by replacing the kk largest observations with −2-2, while the largest is obtained by replacing the kk smallest observations with 22. It’s straightforward to show that the resulting minimum bias is at least 2k/n=0.22k/n = 0.2. By comparison, Table 9 reports an average corruption radius of 0.1150.115 for our midpoint estimator in the Q1 experiment, a substantial improvement. The improvement arises because even an observation within the allowed label range can be inconsistent with an accurate predictor, which in turn restricts the set of compatible clean mean vectors. A smaller bias term is especially important because this term does not shrink with nn.

AuthorsOpenReview ↗

Rebuttal Part 3: Questions

[Q3] Yes, and thank you for this suggestion. We generated a heavy-tailed distribution and provided a similar analysis of the length of our interval against different baselines (see EXP_synthetic_data.pdf). As shown there, our method remains competitive even against oracle-based baselines that use some information about the true distribution. We explicitly tested against an adversary that pushes the magnitudes of the corrupted labels as far as possible in a chosen direction (extreme shift attack) and an adversary that replaces the points with the largest residuals with their prediction (erasure attack).

Bounded labels provide useful information, including a variance bound from the known range and the ability to identify out-of-support observations as corrupted. However, under our prediction-MSE assumption, an unbounded label distribution need not lead to wider intervals. The empirical MSE constraint limits the total squared norm of compatible clean residuals. Treating an extreme observed residual as uncorrupted can therefore consume much of the available budget or violate the constraint altogether, narrowing the range of compatible clean means. The harder instances are those in which the observed data remain compatible with clean label vectors having substantially different means. This is consistent with the shorter intervals observed under extreme shift attacks than under erasure attacks in our experiments.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.