Robust Estimation Under Heterogeneous Corruption Rates
Authors: Syomantak Chaudhuri
Jerry Li
Thomas Courtade
Venue: NeurIPS 2025 poster ()
Keywords: robust statistics
robust estimation
robust regression
minimax estimation
Primary area: theory
TL;DR: Minimax rate of robust estimation when different samples have different but known rates of corruption.

Abstract: We study the problem of robust estimation under heterogeneous corruption rates, where each sample may be independently corrupted with a known but non-identical probability. 
  This setting arises naturally in distributed and federated learning, crowdsourcing, and sensor networks, yet existing robust estimators typically assume uniform or worst-case corruption, ignoring structural heterogeneity.
  For mean estimation for multivariate bounded distributions and univariate gaussian distributions, we give tight minimax rates for all heterogeneous corruption patterns.
  For multivariate gaussian mean estimation and linear regression, we establish the minimax rate for squared error up to a factor of $\sqrt{d}$, where $d$ is the dimension.
    Roughly, our findings suggest that samples beyond a certain corruption threshold may be discarded by the optimal estimators -- this threshold is determined by the empirical distribution of the corruption rates given.

Robust Estimation Under Heterogeneous Corruption Rates
Syomantak Chaudhuri University of California, Berkeley
Jerry Li University of Washington
Thomas A. Courtade University of California, Berkeley
Abstract
We study the problem of robust estimation under heterogeneous corruption rates, where each sample may be independently corrupted with a known non-identical probability. This setting arises naturally in distributed and federated learning, crowdsourcing, and sensor networks, yet existing robust estimators typically as- sume uniform or worst-case corruption, ignoring structural heterogeneity. For mean estimation for multivariate bounded distributions and univariate gaussian distributions, we give tight minimax rates for all heterogeneous corruption patterns. For multivariate gaussian mean estimation and linear regression, we establish the minimax rate for squared error up to a factor of Vd, where d is the dimension. Roughly, findings suggest that samples beyond certain corruption threshold may be discarded by the optimal estimators this threshold is determined by the empirical distribution of the corruption rates given.
Introduction
In traditional statistics, we typically rely on the assumption that our data is generated in a "nice", ii.d. manner from some population distribution. Robust statistics can be assumptions, aiming to ensure meaningful performance even when the data that has been corrupted by small fraction of arbitrary, but potentially adversarially chosen, outliers. First proposed in seminal work by statisticians such as Huber, Tukey, and Anscombe more than fifty years ago 4 this problem remains highly relevant to this day, and has received considerable recent attention from the statistics, machine learning, and theoretical computer science community, see e.g. [5]20]] A full survey of this line of work is beyond the scope of this paper, see e.g. [21] for more comprehensive overview.
relaxation of these
There are number of related ways in the literature to model such outliers. For instance, one classical setting is known as the Huber contamination model [22]. Here, there is a "nice" distribution D, typically assumed to be from some well-behaved class of distributions, and we receive n samples = (1 c) + eN for some arbitrary noise distribution N, and 0. In other words, generate sample point Z,, generate clean sample from with probability (1 <). and we sample an outlier from a noise distribution with probability c. There are also number of other, more powerful, adversaries considered in the literature, for instance, which allow the adversary to choose the corrupted points adaptively based on the clean samples; see e.g. (23 for more detailed discussion. However, by now, least for many basic estimation tasks such as mean estimation, tight (or nearly tight) rates are known for many parametric families of distributions under all of these corruption models.
Zi...., Zn from a distribution some parameter
But, all of these models share an unfortunate drawback: namely, they all essentially assume a homogeneous prior the error rates across the dataset. In the Huber contamination model, for
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

example, every sample is corrupted with the same probability c. In practice, this is usually not the case: we often obtain data from various heterogeneous sources, and consequently we should have different priors on the cleanliness of different data points in our dataset. As an example, many large-scale biomedical datasets are agglomerated in a distributed fashion over different institutions and at different points in time, and it is unreasonable to assume that the rate of outliers ought to be similar over the various sub-parts of the data. But because all existing robust statistics techniques assume uniform noise prior, it is unclear whether can obtain the optimal statistical rates for such datasets, or what these rates even are in the first place.
Motivated by these considerations, we propose natural generalization of the Huber contamination model with heterogeneous corruption rates, where every data point is corrupted with a potentially different eπror rate. Formally:
Definition 1 (X-contamination). Let be the number of samples, and let À (A1,.... An) E [0, 1]".
Let P be some distribution. We say dataset Z = (Zi.... Zn) is X-contaminated set of samples from P if Z; = (1 B,)X; + B;X,, where:
X1,.... Xn üdd
a set of clean samples from P.
Bg ~ Bern(A;) Xz) are independent Bernoulli random variables for i = =1, 1,.... n, and
The outliers
Xx,) are sampled from some joint distribution conditioned on the realizations of X1 X,...., Xn and B B,,
When set of samples is generated this way, denote this by Z ~~ P.
In other words, we assume that the probability that the i-th sample is corrupted is X; for different values of X; We pause to make a couple of remarks on this definition. First, when all the X; are the same, this is essentially the standard Huber contamination model, except allow that the outliers may be chosen adaptively. Second, we will assume that we know À exactly. However, our upper bounds also naturally generalize the setting where we only have approximate knowledge of the A, ie., we just need constant factor approximation Å₃ of the corruption rate for our results to hold (i.e.. A S cA.). Such upper bounds on the corruption rates can often be estimated from past performance in practice. Finally, just as in standard robust statistics, there are many similar but not equivalent definitions we can consider here, for instance, corresponding to oblivious contamination or strong corruption (21 25. Our proposed error upper and lower bounds hold for both adaptive and non-adaptive adversaries. We leave the exploration between the differences between these definitions as interesting future direction.
From a more conceptual point of view, the main challenge in this heterogeneous setting how to effectively "mix" the information from data points with different noise levels. As an illuminating example, one important special case of the >-contamination model is semi-verified learning 77, (9] where there is (very) small amount of trusted data, and large amount of potentially very noisy data, which corresponds to the setting where X; = 0 for a small number of i, and X; = y for some y close to for the rest of the data. In general, robust estimation is impossible if X; 1/2 for all i, however, turns out that in the semi-verified setting, one can obtain consistent estimators by combining the information from the two sets of samples (7]. This example illustrates the main technical challenge of the general heterogeneous setting. To obtain the tight rates, one must correctly identify how to incorporate information from the noisier samples into the information from cleaner ones, and to do so smoothly as a function of X4-
1.1 Our results
We establish lower and upper bounds for the statistical rates for a number of fundamental estimation tasks in the X-contaminated setting. We first consider robust mean estimation in the heterogeneous setting, one of the most important and well-studied problems in robust statistics. For any distribution P. let μP Ex-P [XX] be the expectation of P. We will measure the effectiveness of our estimators using the following minimax metrics:
Definition 2 (Minimax, Minimax PAC rates for heterogeneous robust mean estimation 26 27). Let
D be a set of distributions over IRd, and let À E [o, 1]". The minimax rate for X-corrupted mean estimation for the class D is defined to be
L(X, D) = inf sup Ez-ap P [II - prl6
M PED
2

---

where the infimum is taken over all estimators M. The minimax PAC rate for x-corrupted mean estimation for the class D defined to
(A, D,
Pr [[] pr S inf sup inf ( Z~XP M PED
(2)
Readers can refer to Ma et al. [26] for more details on the minimax PAC rate. Stated simply, the minimax PAC rate simply the smallest rate so that the probability that the estimator exceeds [ D, 6) is small. Since by standard techniques, we can boost the error probability 6, we will typically focus on the setting where 8 small constant, and we will let [ D) :- LPac (, D, 1/5). We use this notion because it is necessary in the robust setting. In settings where the unknown mean could unbounded, no estimator can achieve finite expected error, even in the standard Huber contamination model. This is because all samples may be corrupted with exponentially small probability, in which case the error could be arbitrarily large.
Mean Estimation for Bounded Distributions: We first consider the class of bounded, multivariate distributions. For this setting, we show:
Theorem 1. Let Dr be the set of all distributions on Rdd supported the l2 ball of radius r. Then,
( k
L(A,D)) 1().1), where f(X, k)
min
Hi: S 5 + (22)
(3)
=E(0.1)
Moreover, the optimal estimator can be implemented in nearly-linear time.
The function f(A, k) can be thought of as a measure of the "effective" error rate of the dataset, and will play a crucial role in many of our results going forward. Indeed, Theorem I implies that the optimal robust mechanism chooses corruption level t and only utilizes the data having corruption rate below 1, i.e, there is no improvement by considering the other samples up to constant factors.
Mean Estimation for Gaussians: Our next result concerns heterogeneous mean estimation for Gaussians. Our main result can be summarized as follows:
Theorem 2 (informal, see Theorem 4p. Let DÍ the set of all multivariate Gaussian distributions on Rdd with identity covariance. Suppose that f(2, d) = O(), then d-1/2 f(x, d) $ L,xc( DN S f(),)) d).
In other words, we show that, in the regime where there are sufficiently many relatively clean samples, f(), d) dictates the minimax rate, up to v factor. Note that this is arguably the most interesting regime from statistical perspective, as it is the only regime where the recovered Gaussian has non-trivial statistical overlap with the true Gaussian. We note that our lower bound technique also yields non-trivial bounds in more general settings, however, they somewhat more difficult to interpret- see the supplementary material for more discussion.
We pause make couple of remarks on this result. First, in constant dimensions, our bound tight up constant factors, so our bound tight in this regime. Second, we note that naïve multi multi-dimensional techniques such as coordinate-wise methods would lose (d) factor in the squared &g errerr, so our bound represents a polynomial improvement over baseline methods.
Finally, we turn our attention to Gaussian design linear regression with heterogeneous corruptions. We assume the uncorrupted covariates are Gaussian with covariance matrix Σ E ddd and noise rate o². Then, for any choice of regression coefficients 3 E Rd,, we assume that the clean data is of the form (W, Y) E Rd+1 where W ~ (0, E), and conditioned on W. Y ~ N(WT B, r²). We let DEE, o²) the family of distributions over (W. Y' of this form. For any P E D(E, )²), we let 3p denote its associated regression coefficients. In analogy to Equation (2) we define the minimax PAC rate of squared excess risk under heterogeneous corruptions to be
Linear Regression:
inf { t (0, 00) Pr ZmIP
Tree (A, D(E, = inf
sup M PED(E,0))
[II - 33 > 1 S
(4)
and as before, we let Treg(A (A, D(E, o"); :- (A, D(E, o²), 1/5). Here || = Ex, which known to be the natural
measure of error for linear regression [28 Note that this
3

---

is the standard joint contamination model [9), where both the covariate and the target can be jointly corrupted by the adversary, i.c., Z; = (W;(1 B,) + B,W, Y;(1 B,) + B, This is
opposed to the simpler target contamination model also considered the literature where only the target Y can be corrupted [30].
Our main result in this setting is as follows:
Theorem 3 (informal, see Theorem 5). Suppose that f(,, d) = =O1), then d= d) x
Lreg (x, of), & f(A.d) d).
In other words, as before, we establish the tight rate up to a factor of O(va).
Upper bound techniques For all four problems, the upper bounds in the theorem statements can be achieved by a thresholding estimator set an appropriate threshold t and take the optimal robust mean estimator with homogeneous corruption rate t. Thus, least for bounded distributions and Gaussians in a constant number of dimensions, our results show that there no significant benefit in collecting data with higher corruption rate beyond certain threshold.
Per-sample reweighting In addition to this simple thresholding method, we also give a family of more refined estimators that find an optimal per-sample weighting scheme, that match the theoretical guarantees of the simple thresholding estimator, but which has a number of additional advantages over it. First, as we discuss below, these methods seem to sometimes perform better practice in preliminary synthetic evaluations. Second, in the high-dimensional settings, the thresholding based methods have error rates which seem to plateau, resulting the vd gap in the upper and lower bounds. We believe resolving this gap a very interesting open question. As first step, we derive natural heterogeneous variants of Tukey depth 4 and regression depth [31] using these per-sample reweighting methods. We believe that these methods may allow us to bridge this gap, by leveraging the higher corruption points that the thresholding based methods ignore to boost the accuracy. To reiterate, we propose the reweighted estimators as a possible avenue to improve the upper bounds but the estimators used to obtain the minimax upper bounds are based on the thresholding estimators.
Lower bound techniques A key technical challenge that separates our analysis from that of standard homogeneous robust statistics analysis is that of capturing the heterogeneity in the lower bound. The standard approach for the lower bound in homogeneous robust statistics is to add a term due to the corruption rate to the non-robust lower bound (32 For example, in robust d-dimensional Gaussian mean estimation under identity covariance with corruption, the minimax rate is of the order @ + )²,, where n is the number of samples. The term _ is obtained from classical statistics literature while the e² term captures the fact that two distributions with mean within lp distance of e can not be distinguished due to the e contamination proved via Le Cam's method (28 Such two- staged approach is unsuitable for our setting since the number of samples n can be made arbitrarily large by artificially appending samples with À Le Cam's method captures the difficulty of the problem in terms of corruption rate but fails to capture the dimensionality of the problem, while Assouad's 's method can capture the difficulty of the problem in higher dimension, but seems to have difficulty capturing the power of an adversary. Thus, the challenge lies in constructing tight lower bounds that incorporate both the terms jointly. Readers may refer to our lower bound construction in Appendix for more details.
Experimental evaluations While we emphasize that the main contribution of this work is the- oretical, in the supplementary material, we also perform some preliminary synthetic evaluations to validate the effectiveness of our methods. In the bounded and univariate Gaussian settings, we demonstrate that both the thresholding- methods well the per-sample reweighting methods outperform baselines from the standard homogeneous robust statistics literature. Our results also demonstrate that some settings, the per-sample reweighting methods also yield improvements over the threshold-based methods in practice.
1.2 Related Works
As discussed previously, the robust statisties literature has typically focused on a homogeneous corruption rate. In terms of heterogeneity, Charikar et al. [7] introduced the notion of verifierfieed

---

learning where small amount of data is sampled from the true distribution in conjunction with dataset having only a fraction of the data uncorrupted (a < 1). The semi-verified learning problem is closely related to the problem of list-decodable estimation introduced by Balcan et al. [3]; list- decodable learning aims to recover a list of possible values the quantity being estimated with the guarantee that one of entries in the list is close to the true value. Typical results in semi-verified learning lead of an error that depends on a but does not typically scale with the number of clean samples. There has been line of work extending their results 99
13
[4
19 34].
Robustness and privacy are known to deeply related 38 the privacy literature there has been a line of work on optimal mechanisms under heterogeneous privacy demands [1) However, these works only focus on bounded univariate setting, and do not seem to imply anything directly for the heterogeneous corruption setting we consider.
Organization: We define the problem of mean estimation for bounded distributions in Section and provide a general proof sketch to obtain the minimax rate. In Section [] we present our results on Gaussian mean estimation for both univariate and multivariate setting, followed by results on excess risk minimization for Gaussian linear regression in Section [4] We present our thoughts on future
works in Section Some illustrative experiments be found in Appendix A
2
Mean Estimation for Bounded Distributions
In this section, we prove Theorem !
2.1 Upper Bound
To obtain upper bound L(X, LD), we shall restrict our attention to the class of estimators of the form 1 W;Zi for w E An. Via standard bias-variance decomposition.
E
Σ
W MP
E
Z
μP
E
Σ (Z. - B[|z))
(S)
2
Denoting E[X,|B; = 1] = MQQ. the bias term can be upper bounded
wi [E[2,] pP)
Σ wrda(uQ. - -PP)
S 4r 4rr 2)2
(6)
using Jensen's 's inequality and the fact that I@q. - prl12 s 2r. The variance term needs to bounded
with more care since X are not independent can dependent on X, B. It can be upper bounded as
W: (Z₁ E s 7 + 16 (see Appendix B.1.. Thus, we get the upper bound
E
Σ
2,
PP
7r ([wl 2 + 3(w x33) Vi E A..
Taking minimum over E A..
L(X, D²) < 7 min | + +3w x)2
(8)
WEAn
Since Slater's condition holds, by KKT we obtain the solution of the above be of form wi
(B 17-30 3(w" A)Ax)+, where (z)+ max(x, 0}. for suitable 3 that ensures w An. Exploiting this structure. we obtain near-linear time algorithm presented in Algorithm 1 For vector X, the notation X denotes the sub-vector (Aa:-.., As) for a < The proof of correctness is presented in Appendix B.2
find the exact minimizer of [|ll| + c(w X)2
Simpler Upper Bound: While Algorithm | recovers the exact minimizer for ( we also discuss significantly simpler upper bound take the mean of the samples with corruption probability less
5

---

Algorithm Robust Mean Estimation for Bounded Distributions
Input: Z and corresponding A, with assumed to be in ascending order n < (ENGTH(A)
< 1
while I n do
if Ak+1 1+ then alfl
k + 1+1
else
break end if end while
1
8 k(1 k(1-cl (1 1
a a+
1+clAff
#/ + adt, wh+1 t- 0
return > wiZi
than for hyperparameter t. Let N(t)) 1f2: X tt]l Therefore, for any t E [0, 1], get the upper bound from
N(t) + (+)
L(),r) P
We can similarly take a minimum over to get an upper bound on L(A, D.). This simpler upper bound suffices for proving minimax optimality.
2.2 Lower Bound
We use Le Cam's 's two-point method to obtain the lower bound. Fix some 0 S 6 S 1. Let
Po = rei (2Ber() _ - 6) - 1) and Pi = (21 + +6) 1), where is a unit vector; we have ||r, /r, 112 = 22
Under distribution Po. consider the strategy such that adversary tries ensure that the i-th sample is as close to rei (2Ber()) - 1) as possible in mean. Let Qi rei (2Ber(xx) - 1)) with
A 2 I+28
28
7
(10)
else,
then the adversary simply samples Y independently from Q. Thus, the adversary can simulate 25
the distribution rej (2Ber() {)) 1) when A; 2 I+26 If X 1+28 then the adversary does not
perturb the distribution all, equivalently, samples X, from Po independently. Thus, the proposed
adversarial strategy results in Z, drawn independently from rej (2Ber( - (4) - 11). where
28
: 51
A
(11)
1
28
Similar arguments hold when the underlying distribution is Pt.
Let nt)) l[i A < t). Using Le Cam's method, we show in Appendix B.3
2 (1 652n(26) A8 E
[ 1 4
(12)
2.3 Proving Minimax Optimality
We outline how to pick 'good' 8. For x E [0, 11, let h(x) N(xr) 12.² Note that h is monotone,
piece-wise continuous, and 3a > 0 such that h(a) < 0. We use the notation h(x to denote the left limit of æ; note that h((=)) = n(22) 2
1
By simulate, the mixture distribution matches the claimed distribution.

---

0223
0100
01.
-1
-1
[C]
Figure 1: Plot of weighted Tukey depth (see (1 visualized for three different weighing schemes. (A)
computed with the standard uniform weights w; +. (B) is computed with w; Ro:A, S0JT using the value of from (2T). and (C) is computed with weights given by Algorithm |
[A,
For the dataset, the true underlying distribution is (O, 0), I). and is sampled i.idd Points are contaminated by replacing them with samples from ( 2), / /5). The samples are marked in red 'x' if they were A; The estimated mean,
contaminated; the size of the markers for each point proportional
the point with maximum depth, is marked with yellow star.
Consider the case that ((2) 0, i..,, I[:: 3 3.- This conditions correspond to extremely high levels of corruption and unsurprisingly, show the minimax rate be ( Plug-in 5 1 in to get L(A,r) Z 2 We can get matching upper bound in by setting =
Alternately, (()) ) > 0 then since h(-) a cadlag function and h(a) < O, there exists 6, E (0.
such that ((6.) 2 and h(6_) ) - 0, i.e., (26.) 2 1267 and n²(6.) < 1267 Plug-in 8, in 12 to
get
L(A,)) 2 22 (653n(25.)
(13)
2 2
1
V 2
= r282.
(14)
In the upper bound of set = 25, to get
L(A,r) S 2
((2.)) + +
(15)
< 2 1 1202.
(16)
proving minimax optimality of the proposed schemes in
g and up to constant factors.
3 Mean Estimation for Gaussian Distributions
In this section, we describe our results for the problem of mean estimation for multivariate Gaussian distributions at a high level. For conciseness, we defer the complete proof's to the appendix.
Upper Bound: We propose weighted version the Tukey median of point E Ied for a dataset Z (Zi...., 7.,) and ur E A, as
Define the weighted depth
Dw 2) min eES
will V (Z, 11) 2 0},
(17)
where Sy far E Rd ||0||2 = 1}. The weighted Tukey median is defined as
ÚUM (Z, w) = arg max Dea (17, Z). nERd
(18)
The standard Tukey depth (i.e., w = 1/n) a point vj the mininum number of samples in a closed half-space with 77 at the boundary. Thus, depth of n7 is high if it is surrounded by samples in all
7

---

directions. Our weighted version allows us to decrease the sensitivity to samples which are more likely to be corrupted. In F we illustrate the Tukey depth map for three different weighing schemes which demonstrates how using the weights can be used to leverage the heterogeneity. eetaalishes an upper bound on the performance of the weighted Tukey median. Proposition |
Proposition (Upper Bound for Gaussian Distributions). For all E An satisfying (w" X)2 d S for some universal constants
sup PIZ [llÄTM(Z, w) ppll 2 d' ((w">)² d](w(12) S 1/5
(19)
PEDY
for some universal constant d'
The proof of Proposition[[ssee Appendix C.I) involves proving that the depth of any point sufficiently far from the true mean is going to be lower than the depth of the true mean in a uniform convergence sense. Due the weighted nature of the depth definition, we modify results from empirical process theory to adapt to the weights and get tight upper bound.
Let (t) li X I t and denote the weights w(t) such that w(t); 5() N(t) i.e., we consider the Tukey median estimator obtained by only considering samples with corruption less than I. Define
ús t) jiM Z, (()).
(20)
By Proposition the following holds for some universal constant d'
PrzzaP |l [lás(Z, (, 1pl13 2 d' (p= (P=N()))
) $1/5,
sup PEDA
(21)
V such that 12 + N(J S e for universal constants e.
3.1 Lower Bound and Minimax Rate
Univariate Case We begin our exposition by considering our result for d 1, i.e., univariate Gaussian distributions. We use Le Cam's method to obtain the lower bound [28]: Le Cam's method lower bounds the estimation problem by hypothesis testing problem where the optimal test is entirely determined by the distribution of data from the different hypotheses. The two hypotheses we consider are No, 1) and 6 5, 1) for 5 to be chosen later. The adversary tries to ensure that the resulting corrupted distribution under either hypotheses the same, rendering those sample useless for hypothesis testing.
If the corruption rate is greater than for sample, then the adversary can trivially 'simulate' the distribution 1/ (A(6, 1) + WV(6, 1)). Alternately, when ö is small, adversary can simulate 1)) instead, where Z(8) is appropriate normalizing constant. The adversary can simulate this distribution when the corruption rate is greater than 1 e Thus, only the samples in the set {i: >₂ < (i - are relevant for hypothesis testing, and it remains to choose a value of 5 judiciously.
the distribution max(
Based generic multivariate bounds of Theorem 4 later, we have the following Corollary 1 the univariate case.
Corollary (Minimax Rate for Univariate Gaussian
Distributions).
Suppose
mineejo.1] (12 NtO)) for some universal constants e, then
1 + +x²) (Ntee
LPAc(A, ~ min (E(o,]]
(22)
N(t))
Moreover, the estimator (is(Z,u(t")
w(t))), with 8" arg minrejo.1)
(12 NtT) achieves this error.
Thus the proposed weighted Tukey median scheme is optimal in the univariate case demonstrating that beyond a certain corruption threshold determined by N-).), there no way leverage the more contaminated samples up to universal constants.

---

Multivariate Case In the multivariate setting, our upper and lower bounds (see Appendix are off by multiplicative factor of vd. This gap possibly be attributed by our rather relaxed handling of the heterogeneity since the proof technique we consider can recover the minimax rate of Vi (see Appendix
+ + in the homogeneous setting where
Theorem 4. Suppose minee[o.1]
(t2 N(C)) S for some universal constants then d (t)
min Vd rEjo.1]
+
S LPAc(A, DY)
S
min re(o.1]
d +12
+1²)
(23)
[((t)
Moreover, the estimator (Z, w(t)),, with t = arg min bound.
(22 d N(A)
achieves the upper
The proof of Theorem 4 can be found in Appendix C.3
As Theorem suggests, might be possible to leverage the heterogeneity beyond just discarding samples with higher threshold and this might reduce the squared-error by factor of vd. However, as stated before, this gap might be an artifact of the analysis rather than a true phenomenon. We leave this as an open question.
4 Linear Regression
We now consider the problem of linear regression under Gaussian covariates. The proofs for this section can be found in Appendix D
Background: Under corruptions, the minimax rate is known to be g²d i..., independent of Σ as long as E is non-singular the lack information in directions with low eigenvalues of Σ if offset by the || || distance. In the homogeneous robust regression setting with corruption, the minimax rate is the order aLd + o²e² 31
For the upper bound, we consider weighted version of Tukey median adapted to regression 31 Define the weighted regression depth of point E Bd for dataset Z with Z, (W,, Y,) and E An as
(m, Z) min a
wi wi WW 2 0).
(24)
The regression depth of a point 1) Ied is high if for all half-spaces, the sign of the residual errors using are distributed equally in every direction. The weighted Tukey regression coefficient is defined as
²TC 2, w) == arg max Duo (1). 2). NER
(25)
Proposition 2 (Upper Bound for Regression). For all w E An satisfying (w 2)2 \)² dl|woll cor some universal constants
sup PrzzaP [lâTT(Z, w) Bpll 2 d' (ww"')) + dl w|]) < 1/5 PED(E,0")
(26)
for some universal constant d'
Like 20)). we can similarly consider a thresholding method - define As (2,1) = 3TM( (Z, w(t)). The lower bound construction is similar in spirit to Theorem Based upper and lower bounds, present Theorem
Theorem (Minimax Rate for Linear Regression). Suppose min (p+ win) cor some
universal constants e, then
o² min [E(.1]
d (MI))
((()) +22 S Treg (A,
min [5001]
d
+12) )(p).
(27)
Vd
N(t)
Moreover, the estimator is Z, w(t"),, with t" arg argmenngjo.1) bound.
d (+² N(
achieves the upper
Note that when X; = e Vi, we can recover the homogeneous minimax rate of o2d more refined lower bound in Appendix
222 using the

---

Discussion and Future Work
There exists several avenues of future work. Perhaps most pressing issue would to address the vd gap in our upper and lower bounds for multivariate Gaussian mean estimation and linear regression. In this regard, seems that neither our upper nor or lower bound in Theorem 4 can be tight for all choices of X. Indeed, the lower bound in Equation 23 is not tight for homogeneous corruption (although this can be avoided with our more sophisticated lower bound technique, see Appendix [T). and the other hand, the upper bound fails to be tight in the aforementioned regime of semi- seriiveriiie learning, where the upper bound would suggest that the error in the estimator should diverge as d + 0o, whereas existing upper bounds due to 7 already demonstrate that dimension independent rates are possible. This suggests that fundamentally new measures of robustness are needed to fully characterize the complexity of learning under heterogeneous errors in the high-dimensional setting. The heterogeneous robust estimation problem can also be studied under different corruption models such total-variation distance Kullback-Leible divergence corruption.
Acknowledgments and Disclosure of Funding
S.C. acknowledges the support of Al Policy Hub, UC Berkeley.
References
[1] Peter Huber. The 1972 wald lecture robust statistics: A review. The Annals of Mathematical Statistics, pages 1041-1067, 1972.
[2] Peter J Huber. Robust regression: asymptoties, conjectures and monte carlo. The annals of statistics, pages 199-821, 1973.
[3] Frank J Anscombe. Rejection of outliers. Technometrics, 2(2):123-146, 1960.
[4] W. Tukey, Mathematics and the picturing of data. Proceedings of the International Congress of Mathematicians, Vancouver, 1975, 2:523-531, 1975.
[5] Iaas Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 655-664, 2016. doi: 10. 10.100/FOCS..01...
[6] Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages doi: 10.1109/FOCS.20166
665-674, 2016.
[7] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, STOC 2017, page 47-60, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 978 14504452652 doi: 10. 144444/355539933555554 URL https:////// http:///ooo.oog//.... org/10..1111... 1145/ 3055399 3055491
[8] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pages 999-1008 PMLR, 2017.
[9] Michela Meister and Gregory Valiant. data prism: Semi-verified learning the small-alpha regime. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1530-1544 1546. PMLR, 06-09 Jul 2018. URL https: attps://proceeddngg: mlr 0eoss//775/meister1....
[10] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stew- art. Sever: robust meta-algorithm for stochastic optimization. International Conference on Machine Learning, pages 1596-1606. PMLR, 2019.
10

---

[11] Yihe Dong, Samuel Hopkins, and Jenry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. Advances in Neural Information Processing Systems, 32, 2019.
[12] Sam Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. Advances in Neural Information Processing Systems, 33: 13:11902-11912 2020.
[13] Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard. List-decodable mean estimation via iterative multi-filtering In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9312-9323. Curran Associates, Inc., 2020. URL http:ttt///proceeiinnng neurips www..ep....ppppper....eee haapppppplleeae hppp://00AAanillllcccee666666002
pdf
[14] Prasad Raghavendra and Morris Yau. List Decodable Learning via Sum of Squares, pages 161-180 2020. doi: 10. 13711197811111111111 1177199999999..1 URL hhttps://eppliii siam. org/doi/ abs abs/10. 1137/ 9911//11997711117999999 10
[15] Jules Depersin and Guillaume Lecué. Robust sub-gaussian estimation of a mean vector in nearly linear time. The Annals of Statistics, 50(1):511- 115-536,,,3,, 2022.
[16] Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari, and Santosh S Vempala. Robustly learning mixtures of k arbitrary gaussians. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 1234-1247, 2022.
[17] Jules Depersin and Guillaume Lecué. Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms. Probability Theory and Related Fields, 183(3): 997-1025, 2022.
[18] Allen Liu and Ankur Moitra. Robustly learning general mixtures of gaussians. Journal of the ACM, 70(3):1-53, 2023.
[19] Shiwei Zeng and Jie Shen. Semi-verified pac learning from the crowd. Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statisties, volume 206 of Proceedings of Machine Learning Research, pages 505-522 PMLR, 25-27 Apr 2023. URL http::://pooceedaaiiii
mlr www.prres/v22/2egg222.. html
[20] Roberto I Oliveira and Zoraida F Rico. Improved covariance estimation: optimal robustness and sab-gaussian guarantees under heavy tails. The Annals of Statistics, 52(5):1953-1977, 2024.
[21] Ilias Diakonikolas and Daniel M Kane. Algorithmic high-dimensional robust statistics. Cam- bridge university press, 2023.
[22] Peter J Huber. Robust estimation of a location parameter. In Breakthroughs in statisties: Methodology and distribution, pages 492-518. Springer, 1992.
[23] Guy Blanc, Jane Lange, Ali Malik, and Li- Li-Yang Tan. On the power of adaptivity in statistical adversaries. In Conference on Learning Theory, pages 5030-5061. PMLR, 2022.
[24] Clément Canonne, Samuel B Hopkins, Jerry Li, Allen Liu, and Shyam Narayanan. The full landscape of robust mean testing: Sharp separations between oblivious and adaptive contamination. In 2023 IEEE 64th Annual Symposium Foundations of Computer Science (FOCS), pages 2159-21111 2168 IEEE, 2023.
[25] Guy Blanc and Gregory Valiant. Adaptive and oblivious statistical adversaries are equivalent. arXiv preprint arXiv:2410. 2024.
[26] Tianyi Ma, Kabir A Verchand, and Richard J Samworth, High-probability minimax lower bounds. arXiv preprint arXiv:2406. /3447, 2024.
[27] Syomantak Chaudhuri and Thomas A. Courtade. Private estimation when data and privacy demands are correlated, 2025. URL htth:t:s::. :/tp:::///xxvvi org/
11

---

[28] Martin J. Wainwright. high--Dimessioal Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[29] Adam Klivans, Pravesh K Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, pages 1420-1430. PMLR, 2018.
[30] Takayuki Kawashima and Hironori Fujisawa. Robust regression against heavy heterogeneous contamination. Metrika, 86(4):421-442, 2023.
[31] Chao Gao, Robust regression via mutivariate regression depth. Bernoulli, 26(2):1 139 - 1170, 2020. doi: 1.3155019-BBJ1144
[32] Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance and scatter matrix estimation under Huber's 's contamination model. The Annals of Statistics, 46(5);1932 1960, 2018, doi: 10.1214/17-A0S1607 URL https: //doi. org/ 10. 1211/121 A0S1607
[33] Maria-Floring Balcan, Avrim Blum, and Santosh Vempala. A discriminative framework for clustering via similarity functions. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, page 67 180, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 978 978160558 1145/1374376. 1374474
doi: 10.1145//174436, 1374474. URL
https://doi.oog
[34] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2018. page 1047-1060, New York, NY. USA, 2018. Association for Computing Machinery. ISBN 9781 150055555, doi: 10.1 114/311 887888877 187558.
URL. htt.tttts///i..... org/ 10. 1tt///11.11115/33 1145/3188745 3188758
[35] Kristian Georgiev and Samuel Hopkins. Privacy induces robustness: Information-con ccopputinnncommuttiiinn gaps and sparse mean estimation. Advances in neural information processing systems, 35: 6829-6842, 2022.
[36] Samuel Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies privacy in statistical estimation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 497-506, 2023.
[37] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 1121-1146. PMLR, 23-29 Jul 2023. URL RRLLittts///proceediigg
mlr pwwss/ wvtps//v22/////2/ 2233// html
[38] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the Forty-Fine First Anmual ACM Symposium on Theory of Computing, STOC '09, page 371-380, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585068 doi: 10.1145/1536414 1536466.. URL http::ttt////t //oii org/10. 1111411515514.1111 1536466
[39] Rachel Cummings, Hadi Elzayn, Emmanouil Pountourakis, Vasilis Gkatzelis, and Juba Ziani. Optimal data acquisition with privacy-aware agents. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning, SaTML 2023, Raleigh, NC. USA, February 8-10, 2023, pages 210 210-224. IEEE, 2023. doi: 10.1 10.100/AAMM555555 001.5755.2222000000 000223. URL httpssts:://do org/ 10 1109/SaTML545777 2023.00023
[40] Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms. In Proceedings of the 23rd
ACM Conference on Economics and Computation, EC '22, page 1141, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450391504 doi: 10. 10.1145/3490486. 3538329. URL https:://oi. org/ 1145 3538329
[41] Syomantak Chaudhuri, Konstantin Miagkov, and Thomas A. Courtade. Mean estimation under heterogeneous privacy demands. IEFE Transactions on Information Theory, 132--133
2025. doi: 10. 1..1100 1T.11//TT.2224.551144999
12

---

[42] Peter J. Rousseeuw and Mia Hubert. Regression depth. Journal of the American Statistical Association, 94(446):388 402, Jun 1999. doi: 1111800016221499.99990077777
[43] Luc Devroye and Gábor Lugosi. Combinatorial methods density estimation. In Springer Series in Statisticy, 2001. URL http:htttt/pa..snaaaeeet http:pps...aaaaatcooo.oooooooraa
118160190
[44] Renjie Liao. Notes on rademacher complexity. https://ww, cs toronto edu/"rjliao
Accessed 10-05-2025.
[45]
Patrick Rebeschini. Covering numbers bounds
for bounds
boundddsforrrddmmmmmccrrooooooo chaiiiininiiiiiiciiiii.n.. https: /
www www.stare statt.ttts.....m.. ox www.acc.uuu/ueee www.:ttww..o.r...roooooocccceaea htt.a//ooooo//eccce////////////a
Ac-
cessed 13-05-2025,
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Claims are theoretical and their proofs are provided in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We make the assumptions clear. For example, our methods are not useful without knowing the À vector. We also make it clear that out estimators are not tractable in high dimension.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
Formal proof' are presented in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide all the high level details to understand the experiments. Exact syper-parameters used are not specified for ease of exposition but can be found in the linked codebase. The experiments are fairly straightforward to implement (less than 200 lines of code).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Attached Jupyter notebooks allows reviewers to verify the plots without writing any extra code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nips. wttpcccpccccccccccccceooooc /wweddeeeeooeebbbiiccceee wwwiebbmsssiin seriiisssoopiiiii
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All the necessary details to understand and interpret the result are contained in the paper. Auxiliary details like the specific choice of hyper-parametts parameters included in the codebase.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Ys]
Justification: Some notion of error/variance is captured in the graphs in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Experiments performed at not computationally expensive and can be performed most laptops on CPU (without GPU).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps:/neurrpps. cc httpp//ps...ppppitttcccccccccaie
Answer:
[Yes]
Justification:
No violation of the Code of Ethics were committed.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is more theoretical in nature and no immediate significant impact on the society is foreseen by the authors.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No real-world datasets are used in this work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We did not use any external assets. Prior research is properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We introduce no new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not relevant for this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer:[NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLM -usage was restricted editing the paper and help in speeding up the development of the codebase.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
hatoss//baarijs.cc/ooofreeeeese
20

---

10
100
16.
Trecshodd Methed
Trecshedd Mothed
Saniple
(a) Bounded Mean Estimation
(b) Univariate Gaussian Mean Estimation
Figure 2: Mean estimation algorithms for (a) bounded distributions and (b) univariate Gaussian distributions. The x-axis is proxy for degree contamination of the model.
A Experiments
We investigate the practical performance of our algorithms and compare with baseline in Figure 2 For bounded mean estimation, estimator the homogeneous setting. For univariate Gaussian mean estimation, we use the sample median, equivalent to Tukey median in dimension, as the baseline for the same reason.
the sample mean the baseline since it is the minimax robust
We set 10a and for a fixed value q, we sample the corruption rates À i.i.d. from the distribution expect higher corruption rate.
with edf given by F(t) Fixing this sampled A, we sample the dataset 104 times. For bounded distribution, we plot the mean squared-error and the corresponding standard deviations over the trials each value of q considered. For the Gaussian distribution, we plot the empirical --th quantile of the squared-error along with 15 th and 17 quantiles over the trials. For the bounded distribution, we choose = and choose 20 20 the true underlying distribution be the point mass O, and the corrupted values to be 1. For univariate Gaussian distribution, we fix the true distribution to be A 1) and the corrupted values sampled i.i.d from ((000 1).
(1 t)9. As increases
Optimal linear method the plots refer to the reweighing scheme proposed while threshold method refers to the special case of reweighing that discards samples above certain corruption threshold and performs standard homogeneous robust estimation on the sub- sampled dataset.
While unclear for the Gaussian distribution, the reweighing does seem provide marginal improve- ment over thresholding method. Further investigation is required to establish whether reweighing may pose significant advantages in high dimensions.
B Bounded Mean Estimation: Proofs
B.1 Variance Upper Bound
Using X + 11
get
27
m
Σ wi (Z, - 1(2z))
=E Σ
wr((1 ((1 B.)X; - -1-x)ppp + Σ
w. (B,BB.. - \mHe)
1=1
(28)
< 2E
Σ
w:((1 B.)X; (1 A1)
+ 2E
Σ wi B.x. \mpr)
2
(29)
21

---

Since {(1- - B,)X; (1 p)pp) are independent random variables and [| B,) S can use the crude variance bound E B,)X; -(1 2, I r² to obtain
we
a
E
Σ
w (X) -p) X )pp
S 2 1
(30)
Inspecting the other term, use the law of total variance by conditioning B. In particular,
E
Σ wi (B. )MO,
E
wil (B,(; -mQ.) uQx (B; Ac))
(31)
I 2E
Σ
(X,,, mQ,)
+
Wi/MQ (B: Xx))
(32)
For the first term in 32 use Jensen's inequality
E
(X, mQQ)
E
E
Σ wy B (X; (QQ)
B
(33)
S R
Σ Bi
(34)
-r²
Σ
i X1 X₂) + (w=
(35)
S |/ 11 + 4r (w x) S
(36)
For the second term in (32 using the fact that || S r, using Jensen's 's inequality we get
27
E
Σ w.pe (B: - Ac))
S 2
Σ wi willB -aa1)
S 4 w
(37)
Combining the above, obtain
E
Σ ws (2; E(2i))
< 7r fr + 16r X}²
(38)
B.2
Upper Bound Solution
To solve
min W
|| + c(w x)2
(39)
consider the Lagrangian C(w, B, r) condition on the Lagrangian leads
|ml + c(w7 ))² + 28(1 - E, w;) - E, 27, KKT
wi = B - c(w x)1; + 74 Vi,
(40)
where yww; 0, 0. Vi. Thus, can equivalently write
wi = (33 c(w" x)
(41)
Notice that are decreasing in X, thus, order the indices such that X < >.... < An Note that since this is strictly convex objective with convex compact constraint set we are guaranteed unique solution w.
22

---

Let m such that wi > 0 vi < m and = 0 vi > m; if no such m exists then it is understood
m n2. Since Σ w 1. use
obtain the condition
m3 - c(w" 1)I| =
(42)
Noting that w x= m
1= W
41
to obtain
A
cw T X|
(43)
Solving for w X and substituting in
22
obtain | k(1+c) X - 1
+
and
1+ c 1
| + C
ATT wy m + c B
1 1
Vi [m].
(44)
Thus, the problem of solving for the weights has been reduced to identifying the index le after which the weights are zero. This is precisely what Algorithm [ does. In particular, m - 1 = min
Wy = 0} by definition and Wm+1 0 e Am+1 2 ]+<||A[1 112 by (44). Therefore, if the loop in <|
Algorithm | runs without termination till index A = m,, then it will correctly terminate at & = m
I since Am+1 1|
Thus, we need to show that the algorithm does not terminate before k m to prove correctness. ++ Assume the contrary that terminates kt = m, i.c., Ap-1 e|
Observe that
Ap+1 2 1+ c|IA
1+ 1+cpAtt*11 12
(45)
c|1i
c|127 ||:
1 cllAp c|AAp1111
Ap42
(46)
where 46
follows since A(s) are indexed in non-decreasing order. Extending this argument, we get
+ [AT
Am
Note since Wm > O, we have
c AT
Am
(47)
by
44
contradiction. This proves that the proposed algorithm solves for correctly.
B.3 Lower Bound
By Le Cam's method,
L(A,)) 228
r202
1 1-TV TV
/ Ber
{/2 -e)) - Ber
1
1 (
( +e:
(48)
28
KL
Ber
2 - 6
Ber
+
(49)
282
6
2
(50)
1=1
where we used 2e log
1+2e
< 12e² E [0. H.. Let n(t) = =lfi: X < t)}, then we obtain
1-2c
I(A,)) 2 282
(1-1 682n
i 168m
28
(51)
25
1 1
2 282 [1
v 6652((6)
Y8 E
(52)
23

---

C
Mean Estimation for Gaussian Distributions: Proofs
C.1
Upper Bound
Recall
Dm, 2) = =mi
w [ (1; (Z: -1) 2 0},
(53)
vE
ÚTM (Z, == arg max (17, Z). nER"
(54)
Let G= B; = and B = [n] \. G. Note that Z; = X, for i E G. The depth of the true mean is lower bounded
(m, Z) 2
min #EEd LEG
Σ
w;;1((X, - (1) 03.
(55)
Define the class of indicator functions F₂ (fo()) 1[ u)²uv 0310 v Saj. Note that F[[(X)] Vʃ E Fy- With some abuse of notation, let w(G) {wili G). By Proposition 4 we have with probability at least
min Σ ws (F(X)) - 2) 2 -6262 [ -|wn()) fEFu iEG
log 4/6
(56)
2
log 4/8
2 -|wl|| 62v +
(57)
2
where we used VC(F,,) = d: readers may refer to 43 Corollary 4.2.2] for VC dimension of homogeneous half-space classifiers. Further, with probability least 8/4, by McDiarmid's inequality 28
Σ IEG
Wi
Wt B, = =0}
(58)
i=1
log 4/8 2
2
wi(1 A1) - 11111112
(59)
1=1
log 4/6
=1 wxx X ||l||2
(60)
2
Thus, with probability at least - 5/2,
D (u, Z) 2 w X
log 4/6
||0||
62v +
(61)
2 2
8
Next, we show that depth of any point far away from the true mean is low. For any E Id such that We shall set the value of a > 0 later.
|| /1/2 2 r = t 1-1( 1 + ax), let Ur =
9-2 1-
sup (w 2) - Σ wi + 1: 21
sup
r., 2 0}. wil[(Xx - 77= En
(62)
ie
n
1=1
Define the class of indicator functions Gp = (f((z) [f(z Te, 2 0)|l7 Ml12 2 r). Since EX r) u, 2 0}] d(-11n (l12)) we have Elf(X)) - Vf E Gy,.
Now, note that 9,. C (f((z) 11(x F) > 0}/11 E Rd). By reparameterzing x, we have vC(Lf,(z) 1[(x n)² un 03/1 e Rd)) = vC(lf(() = 11(2 - rn 03/7 E Rd)..
24

---

Observe that (C((f,(z) = 1((x n 2 0Hn E RT) & vC((fn.(a)) = If(x -n)² 2 U E IR)) = d + 1. Thus, vC( s + 1 - 2d.
Thus, by Proposition 4 with probability at least 8/4.
sup --1o~vlla22r
Dw 2) -
Wi + sup DEGp
wig(Xi)
(63)
KEB
log 4/6
+
a 1|l12 62v2d +
(64)
2
IEB
Again, by McDiarmid's inequality, with probability at least 1 8/4,
1 log 4/8
Σ
wi S w
w
(65)
iEB
Thus, with probability at least 1- -5/2, we have
sup
(n 2) 2
1
w² x ||l|2 88v + VVV
log 4/0
(66)
well Pill-allb2
2
Combining 66 and (66). picking
ensures that point 77 such that || 2/1 2 Φ ( a)) can be returned by the Tukey median estimator. Thus,
w X + ||||| (500v d + 3.5
log
with probability at least - 8, we have
A| - ulle S --
2 +
(67)
S 3a,
(68)
using the identity 4- ( 2) s
3r Vx
[0, E.
The above upper bound is valid as long as
a = 2 " + || 150v + V
log 2 1
Setting& 8 = 1 1/5, ensuring / w X + ||l|| (150vd d 4.3)
w + 155||w|lavd S suffices.
Thus, summarizing, let g(w, A) = ww" X + 155 w 12 For w and A such that g(w, A) S J. we have the guarantee that with probability at least +.
|| ul12 3g(w,
(69)
To reduce the above condition to the simpler form stated in the main paper, note that
3 w
g(w, A)2
<
T X + 155/|/||avd
(70)
2
< 155w T + 155/|w||2v// 2
(71)
2 x 1552 (w=>>²² x)² + dll v11))=
(72)
Ensuring the above is less than 1 suffices. Thus, Ve E An such that (w T X)² + d [|| 2 <
432450 we
have
sup PrzzaP [l] Z, w) 1rl1 2 432450 (ww2 x)² + d w [2)] < 1/5
(73)
PEDN
Correspondingly, the threshold based estimator satisfies the following - Vt E [0, 1] such that t +
N(t) I 432450 we have
N(.) ) s 1/5
d
sup PrzZa (is(Z,w(1)) - uell 2 432450 ( PEDA
(74)
25

---

C.2 Lower Bound
We provide lower bound for Gaussian mean estimation in R in this section. For vector E IR RV let e(v) denote a vector R- with the first v elements and the last d va elements equal to
0. Define the parameterized distribution Ps(T)= = (, 7) for å > 0 to be specified later, and let
Pg (P&(T)]T {-1,1] ").
Note: The supremum in our minimax definition over both the true distribution and the adversarial strategy. We shall specify the adversarial strategy later for our lower bound argument.
Note that LPAc(A, (x, D 2 LpAc(A, Ps) vo and thus, we shall lower bound LPAC (2, Ps).
We begin by lower bounding
(((A inf sup Ez~,p (Z) -1r122] PEPs
(75)
For vector T, let 7 denote the vector such that 5; vi * and Ty r,²² Using Assouad's lower bound technique (28).
inf sup Ez~ap [I - pr
inf M 2va
Σ
E
( -
(76)
M PEPs
7E(-1,1)vá
inf
Σ
Σ
E [I((2)) - -
(77)
M 2
inf
Σ
E (Z) -(et))))))(r)(1"
(78)
2v
TE(-1.1jvG
V
inf
Σ
E BII(ZZ); 57y
(79)
2V2
rE(-1,1]va
Now, note that
E Bl),(Z), - 87, 12 + M - 677412
Σ
E [[M(2); - -5r,
bj
2
TE(-1.1)VR
rE(-1.1)va
(80)
Thus, we get
Vd
E [[) 5T513] +E [Z), - -7331p
Ts(A,P)) 2 inf
Σ
(81)
M
2Vd
2
j=1
rE(-1,1)va
V
E [IM(2), 5T +E [Z) --
Σ
inf
(82)
2vd
2
(E(-1,1)va
va
Σ
8L P2 Pa-a
(83)
2
J=1
where the last line follows by Le Cam's method and the notation Pz~ refers to the distribution of Z when the true distribution is Ps( We shall now specify particular adversarial strategy to lower bound the above.
Adversarial strategy motivation: Consider particular sample with corruption rate À and let the underlying true distribution be Pp(r). Denote the perturbed sample as 7(r) and the outlier to be X (T). Note that Z(r) ~ (1 (1- (1-A) + (+) For any particular clean sample X(r) ~ Ps(T), the adversary's 's goal is to ensure the sample Z(T) contains information about One possible way
26

---

is that the adversary try ensure Z(r) wax./ P(r') where the maximum is taken pointwise over the pdf and a normalizing constant. Observe the identity
T
P(r) + maax P(r') - -P(+)) = max P(T')
(84)
r'
where (+)+ == m) is pointwise over the pdf. First, note that
f
max (a(7')())= - Ps(T)(o)) da -
JZERd
r'#r
where (x) is understood to be the pdf of PO(T) at x. Thus, (max.' P(T')-P(7)), T-1 a valid
pdf, and for X = _ we have (1 P(T + (max,'yr ((r')-((r) max. P(r') Thus, for
7-1
any A 2 1-11- #. there exists way for the adversary to make the distribution of Z(r) max., P(r') rendering the sample useless for identifying т.
Now, we find an upper bound on T in terms of 8.
/
Ix- 6ofv
T
max JARRA IE(- /2T)
dr
(85)
1 dr
JIERN (22Ttd 1E(-1,1)v
max
(86)
- JISERVA (2T)VV TEt (2 1L/-1/
lol 13
max
dx
(87)
Va
[ JETER V (2T)
1-"1
max
6
dx
(88)
-E(-1,1)
/
1 10-6113
Vd
dy
(89)
VER:y20
V2n
[24(())
(90)
where (--) is the cumulative distribution function of standard normal distribution. Using 24(xz) < e", we obtain
1 + and
S Bva
(91)
Thus, A > 1 then the adversary can ensure that Z(7) information about 7.
P(r') T
and contains no
Adversarial strategy:
If for sample i, A; 2 e ovd -vvd then independently sample X max, Po(r') Po(r) + (1 3) max./ Ps(r'), where 3 (T (1-1)
The constraint A; >
1 e ovd ensures [0, and the above is valid distribution.
Thus, Z(7) ~ max,, Ps(r') If X; <1 <1-c- then adversary does no corruption, or equivalently, independently sample (() Ps(T) so that Z(T) Ps(T).
T
27

---

Thus, using Pinsker's inequality in 83
obtain
Va
LE(A,
2
2vd
Σ
82
1
V
KL KL(P2~>Ps(1h) PZ)aPo(res)
(92)
==1
TE( (E(-1,1)va
vd
Σ
8
1 -
KL (8 (21))
(93)
2Vd
2
==1
TEl TE/-1,1
vd
Σ
Σ
8²
1-
1
Σ
(L((P(T).P3(TT))
(94)
2v
2
j=l
TE1-1,13V4
= Vd82 (1- (1- (1---
(95)
Let 6, be such that
n21 - Eb S 6482*
1
and N(1 ---bvā
1
(96)
646
Substituting 6. in (95)
7
do2 < inf sup Æ P [lM - 1p112]
(97)
8 M PEPs.
For a random variable K, let infft Pr|K 2r[K2 (1-aa)) (e..)...ee..(.(..... is the q-quantile of the random variable. Note that for a random variable K, EK S Q(K, + (1 x essss-sup Wr E [0,1], 1], where ess denotes essential supremum. Further, note that in the minimax term M suppePs, we can restrict ourselves to estimators M which output ō.jvā almost surely - otherwise the error can be reduced by projected to this region. Thus ess-supl| M uP [|3 I 44/66 for any estimator M and any distribution P. Thus, combining the above observations, we have
=
(o)--v
-e (1M(2)) uP 12:
4 5
4v
inf sup Ez~ (l<x)||M(2)) mrll inf sup M PEPs
+
(98)
pEPs. 5
5
Using
97
we get
7
Vdo2 < inf sup o (1 5
4
4Vd82
uPl12, -MP113
+
(99)
8
5 M PEPs.
4
(PAcc(APs.).. AV
(100)
5
3
V < (P, Po.) < (A, )N).
(101)
40
C.3 Minimax Optimality
For proving Theorem we shall use the weighing w; = 10,,51-56.v
N(1-e5.va) in our upper bound. From
74h. Vt E [0, 1] such that 1 + Nio S for some universal constant c, we have
d
[l w(t)) 1112 S 1 N(t))
(102)
28

---

Thus, min (++ N(t) S c and let the minimum value be attained at t*, then we have
| Z, w(t)))
1112 2
1=2 + N(t)))
(103)
5.va
d
(104)
N 1 - --vv
- d + 64d6
(105)
do,
(106)
where we used 96 in 105 Combining with 101 when minkejo.11 (1²
d
S c, we have
N(B)
d
vdo% z LPAC L D
min [E
e +
S do
(107)
(t)
Thus, when mineelo.1] (1 xitss Sc.
(p+ d
(e c d
min vd rE|0,1]
x(1) Lpnc(A, DD)
min tE(0,1]
N(0)
(108)
D Linear Regression: Proofs
D.I Upper Bound
Recall
n
Dw, 2) min Σ
w: wi((( 17 w 2 2),
(109)
vESd
BTC (Z, w) = arg max Du (1), Z).
(110)
BERU
Let the true underlying regression coefficient be 8, i.e. W M.,. and conditioned on W.
Y ~ NN3T o Let G = {i: B, = 0}, B = [n] \ G, and Let w(G) = {wuli E G}. Note that Z: = (W,, Y.) for G. The depth of the true coefficient is lower bounded as
D (B, 2 min W T - 3d WW.((" 0).
(111)
IEG
Define the class of indicator functions F3 (f((w,) I[( NTT B)( (()o= that [[](Z)] vʃ E Fg. By Proposition
0}|u Sa). Note
4
we have with probability at least
wi (((x)) - 1) 2 62] [
log 4/5
min JeF&
(112)
iEG
log 4/8
2 -|wl||| 62vd+
(113)
where we used VC(F3) d. To see this, notice I((y - w ()= w) 2 0} = (woffwwyy-iili w" 3)) 2 0} = T(uTwi 2 0). where w(y - w 3) E TRd. Thus, it is equal to the VC dimension of homogeneous half-space classifiers, which is [43 Corollary 4.2.2]. Further, with probability at
29

---

least 1 1 5/4, by McDiarmid's inequality 128
Σ IEG
w
w =0}
(114)
log 4/8
wi(1 A1)
1|01122
(115)
log 4/6
w² X ||1||21
(116)
2
Thus, with probability at least 1-8
8/22
w²> X
log 4/6
(w Z) 2 2
| 62v + 1
(117)
2
2
Next, we show that depth of any point far away from the coefficient is low. For any 1) Rd such that ||7 ulls 2 r, let Un pl2="
n-8" We shall set the value of later.
sup 1: v p--ulee 2r
Dw Z) 2
wi
sup
wx - W/)o 2 0}.
(118)
iEB
Again, by McDiarmid's inequality, with probability at least 1 - 8/4,
Σ mc S " |00122 log 4/8
(119)
Define the class of indicator functions G3 (.n((u y)
I[( - 1f) (v) 2 0Hlln A|I 2 r).
Thus, by Proposition 4 with probability at least 8/4,
log 4/6
sup fEg,
w.(f((z) s =2] VC(Gs) + ||we|2|/
(120)
2
Now, note that
Bif(Z)] = Pr [(Y - 77" w"" (n- 2 0]
(121)
Using W N( and YIW ~ ~N(3 o²), we get that
- //W (1 3) M(S - M) where M M- (T 100,117-313 and 5~~ ~ No0, 0() are independent. Letting Tı, T2 Wiid N/ 1).
(122)
Pr [r WWWW (1- (1-
2 0] = Pr |M(MM( - M) 2 0]
(123)
= -rr(5 2 M 2 0]
(124)
Pr PrrooT 2 || Ti
(125)
| B B11
1
Pr
T2
<
Tii [T 0
(126)
o
1
||
B||
1
arctan
(127)
2
1
aretan ||
(128)
2
Thus,
1
Elf(Z)] <
arctan Vf Gg.
(129)
π
30

---

Thus, with probability at least - 6/2, and using VC dimension bound presented in Proposition
3
log 4/6
sup w:lve-Alle22
(10 2
I 2 arctan + + X + || 2/ 2
+ 879vd
(130)
Combining with setting
log 4/6
/he snlva)
}
tan
2
w
x
+ |1ol2
3.5g
(131)
ensures that the estimator BTC satisfies
11 - 5||x r
(132)
3 " + |10122 3.5 1oga/6 2
with probability at least 8 as long as
Substitute 5 = 1/ and let g(w, A) = w
A + 946//w/l 20 Vd. Then, for w such that g(w, A) S 2 we
have with probability at least 5.
1| B|1I S tan Tg(w, A) - 80g(w, A),
(133)
where we used the identity tan лι & & Vo E [0,2/5]
To reduce the above condition to the simpler form stated in the main paper, note that
( w x 916/|1/l11 vd
2
- (946w 946||/0|22vd 2
(134)
2
$ 2 x 9462 (ww">) + dl(w]13)
(135)
Ensuring the above is less than 25 suffices.
Thus, Vw A, such that X)2 d| 11186150 we have
sup Prz~aP [| w) pell 2 114549248o² ((wF x)2 + dll2011) $ 1/5
(136)
PEDN
Correspondingly, the threshold based estimator satisfies the following - Vt E [0, 1] such that {²
N(J S II186450 we have
sup PRZZAP (lūs((Z m((t) - pr 2 11454924802 (p+ ) 1/5
(137)
PEDN
Proposition 3. VC(Gg) 200d.
Proof. Recall G3 [f = - w) 2 0)l1 - عll 2 r), where v,
タ-
-y- 311a*
Let 9 (f, y) Ifly - w) w) 0}|n E Rd . + p1. Note that for the purposes of VC dimension calculation, by re-parameterizing y and 1/. we can write
f (g,(w,)) v) 1[ - (n) 0}ln R RR,nn 0}.
(138)
We now switch to region notation instead a functional notation. Let G = ((w, v) 9 (w, v) = 1} and define the following
H + {ww, y) y - 17 w 2 0}.
H {ww vll nj w < 0).
H3+ (ww,))nn" 2 0},
31

---

H = (ww v)u"" s 0}.
Note that G = ( n H u ( n H Define g = {G RR," + 0), H+ (H) n H |n E Rd , # 0} and - [ n H n Rd , 0).
We use the following property related to VC dimension 43
BA A,B B)) < 10 (VCA)
(139)
The above holds for union well.
Noting that 9 S {G H1 HH E Ht H2 E - Define T = max (ax(VC(( VC(H()) then )C(g)) VC(g) < 10T. Similarly, by writing H (H, H o'' In,ny R 7. * 0), we
have VC(*(*) & 10 max{VC( () (C( }}} = 10(d+1 1), where we used VC( ({H,))+) = d + 1 and (C( )) d. Similarly, VC(H-) < 10(d + 1).
Thus, VC(gg) < 100 (d + 1) < 200d.
D.2 Lower Bound
The lower bound argument we present similar to Appendix C.2
We
begin
by
noting that
when true regression coefficient is 8 then (W,
~
Σ3
N
BT DB
+ o²
For a vector IR V let ev)) denote vector in 12d with as the first v elements and the last d- d-
elements equal to 0. Let B(T) = - for 0 to be specified later. For {-1, 1)
define the YIW ~ N(WT B(T), In other words, for t E 1 (W,Y) ~ Po(r) where
Pa(t) N
Σ E3(r) ((T)TS ( (())"),(()++ + +02 1)
and let P3 = (Ps(T)]= E (-1,1]
We have (A, D(E, 02)) 2 T (2, Ps) Vg and thus, shall lower bound Treg (A, Po).
We begin by lower bounding
LE(A, Ps) inf sup E [IM(2) 3pp12]]
(140)
M PEPs
For vector 7, let 7/ denote the vector such that 7, = = ,(iVi $ and Tj = - For an estimation M [)), define N(2) - M note that this is bijective map. Using Assouad's lower bound
32

---

technique (28).
inf sup Eg (I 3r113] M PEPs
2
inf 1
Σ
E ( - [
(141)
M 2va
TEl r
inf 1
Σ
E (Z] - 6c
(142)
M 2va
rE1-1.1jva
=inf
1
Σ
E [ - 6c(T))1
(143)
N 2v
rE(-1,1)va
1
inf
Σ
Σ
E [[N) - 6c(T)a(²)
(144)
2vd
TE( 76(-1,1]V3
Σ
E [[N( - 5c(T)s(1]
(145)
N 2
j=1
rE1-1,13va
vd
2 inf
Σ
[[N - 57,1
(146)
2va
==1
rE(-1,13v2
Now, note that
B ( OTH OT + [Z)) 87
Σ
bj
1EI-1
rE1-1.1va
(147)
Thus, we get
Vd
E E[N(Z), -7,1 + [2(2), 8T3iPP]
Lg(A,P3)
2 inf
Σ
(148)
N
2
j=1
7E(-1,1lva
Vd
[ 67, +E N(Z); - 87/1
1
inf
(149)
2va
j=1
7E(-1,13va
Σ
8' TV(P2 PZ ((tr))())))))
(150)
j=1
7E(-1,1)va
where the last line follows by Le Cam's 's method and the notation Pz~,P.(T) refers to the distribution of when the true distribution is PT(T). We shall now specify particular adversarial strategy to lower bound the above.
Adversarial strategy motivation: Readers can refer the motivation in Appendix C.2 for more details on the main idea behind the strategy described. We need to find an upper bound on the normalizing constant T for the pdf max, P((T) Let
Σ S(7) = B(T)TE B(7)
EB(TT
0²
Thus,
Ke.w0)12 S(r)
T=
max WEERd re(-1,1)
dwdy
(151)
By Schur's formula, [S(r) 1 and by block inversion formula,
S(7)-1 Σ
((T)8(7))
3(
8
o²
B(T)
33

---

Σ
0 1
Performing change of variable (w,y) G(v, y) where G
we obtain
(n o s(r) -(r)
Σ
T
max
drdy
(152)
"ZER yER rE( TE(-1,1)Vi (2 0
Noting that
GT) 1+ ((())((())
e()
we get
1xll (dols) " xs
T
max WEER TE{ (-1,,1 va
dxdy
(153)
/2T ddl 0
ZERA
{ JAERS ((2T)
1|=11//2
max
(beir) T
20
dydr
(154)
YER 2
rE(-1,1)va
EZERVA ((2m)va
Ia 12/2
VER V 2
rE(-1,1va
max
(6+ 2-
20
dyda
(155)
Let X ~ 10 be random variable in Rv We can write
2 x u12
T Ex
max MER 2 rE(-11)va
20
dy
(156)
Note that max (e(t..vaaar 6||x|| 1/1 Thus,
(0-611X
y 2 8|| 1/
(6+ ( x-
max rE(-111va
y S -01 1 I11
S1
else.
Using the above upper bound, we obtain
26|| 1|1
T Ex
1
(157)
V2na²
25E X []]
= 1 +
(158)
2TTO²
25
1 +
(159)
πо
2av/i
<
(160)
26v2 then the adversary can ensure that Z(7) max_, P(r)) and contains no
Thus, if 2 1 - e
information about 7.
Adversarial strategy:
If for sample i, A 2 1 - e
20 to
then independently sample {()) ~
3 max Pa(r") Pa(r)
+ (1 - 3) max., Pa(r') where 3 (1-1) The constraint X; >
T-1
1
26v3
ensures 3 [0, 1] and the above is valid distribution.
Thus, Z(T) ~ max,, Ps(r') If X < - e-
20 *5
then adversary does no corruption, or equivalently, independently sample (()) Ps(T) so that Z(T) Ps(T).
T
34

---

Thus, using Pinsker's inequality in 150). obtain
vd
(c(APP))
2
Σ
8²
(1-13 2
(1-
(161)
2v2
5=1
TE1-1,13v2
Va
Σ
Σ
8²
1
1
V22
I
KL (8 022))
(162)
2
1=1
TE(-1,1)va
V2
Σ
8²
1-
Σ
KL (L(P(()), Pb(T))
(163)
2vd
2
1=1
TEI-
2
hdiSI=E"
82
vd82
1-
V
26v3
(164)
where (164) follows since
KL (Po(T),Po(7")) = EWWANTO,EK KL (N(W" 3(T),
(165)
82(T - - --W-E=1F (T)
Ew
(166)
20²
821[T - =/1
(167)
20²
28 o²
(168)
Replacing 8 + 8/0 in (644, we get
LE(A, 2 V28882 (1 (1-V 1-V02mi 82n(1 6- 25y2
19,
(169)
Let 5, be such that
26, ve n11 - c a
and N(1 - e-- 20 2 6452
S 6482
(170)
Substituting 6, in 169
Vido 28 < inf sup EZ-aP [Z) - 3p1 M5 PEP.s.
(171)
Note that in the minimax term inf suppEPs. we can restrict ourselves to estimators M which almost surely - otherwise the error can be reduced by projected to this region. Thus ess-supl M(Z) Brll < 4 2d for any estimator M and any distribution P. Thus, combining the above observations, we have
output in V = -y E [-6_0,0,ajva x {O]d-vā)
4 o (IM(I)) uell 5
4Vd6302
inf M PEPs. Ez P Pl) - upll S inf M PEPs,
+
(172)
5
Using 171b. get
< inf sup o (IIN(Z) - )
4
4Vd8302
v Vd
+
(173)
5 M PEPos.
5
4
4V76600
Tree (A, Pas.) +
(174)
5
5
3 40
v Vd82 02 < Ling Pah.) S Ling (2, o(E,
(175)
35

---

D.3 Minimax Optimality
HA, <1- 28.
For proving Theorem
we shall use the weighing w,
in our upper bound.
v6.
N(1-c
From 137 Vt [0, 1] such that t2 + d N(O)
I c for some universal constant have
[|8s(Z, m()) m 0² 0² ( ( MOO
(176)
Thus, min ( N(8) S e and let the minimum value be attained at t", then we have
d
(Z w(t))
غ S o²
tx2
(177)
((*)
I 0²
e
26o
2
+ 0²
d
(178)
26./d
N
4d82
S 0
640 do
(179)
π
odd82
(180)
where we used 170 in (79). Combining with 175 when min (f+ x(0) S have
Vdo28, S Lreg(A
min [E
(
d N(I)
S do
(181)
Thus, when min.e(o.1] (++
d N(())
S c,
min vd :E
c+ N(t)
S Lreg (A, D(E,0²))
S 0² min
c+ N(t)
(182)
E Weighted Generalization Bound
We refer the readers to 43 for introduction to VC dimension, covering numbers, and packing numbers.
Define the weighted empirical Rademacher complexity to be RE X) Jsu E, (x,, x We first generalize Massart's lemma to weighted Rademacher complexity.
Lemma (Weighted Massart's Lemma). Assume [F] is finite and let
B max /EF
Σ wf[(xx).
(183)
i=1
then
R₂ (F X)= - B., /2 F
(184)
36

---

Proof.
d sup E. fite ((x; x]
eaRw(FoX). =
(185)
B
Eadddss E. i /( ((x))
X
(conditional Jensen's 's inequality)
(186)
x
(187)
fer
n
Σ
E
X
(188)
fEFi=l
ΣII
3 (x))())//2
(by Hoeffding's lemma)
(189)
/EFi=1
$ |Fle BL112
(190)
Thus,
In
F
sB m
R. RF o
Vs > 0.
(191)
8
Setting 8 /2ln B,.
we get the claimed upper bound.
Lemma 2 (Weighted Rademacher Complexity Bound). R. (Fo S 31//w/12 Sallulll/VCCCT /VC(F) VX, where VC(F) the Vapnik-Chervonenii dimension of F.
Proof. Much of this proof follows the analysis of Liao 44 version of our problem.
Rebeschini
45
adapted to the weighted
In the context of this proof, for the realized X and for f E F, define
w T(X.²²
II
(192)
|llla
Let maxyeF I1 I c. For family of functions that we consider, c = 1.
Let Let F, F be the minimal Ej 27 cover of F with respect to || Ilws i.e., Fj is the set of least cardinality such that for any f E F. E F, such that || - f'llu I cy. Let [J, = C(F, Ey ll llw).
For any f F, let fz(5) F, be such that || f5())l S ej- Denoting B(: X Eo[(:), we have for any m 2 1,
(F [oF)) x = Eg
sup fEF
w -
- fm())()) + ( - - (f(())
(193)
Eg sup
(f(x(f(X,)) - fm(()(()))
+ Eo
sup fEF
Σ
WiO Σ f(((())) - ((-1(())))
fEr
1=1
(194)
Notice that
E
sup fEF
w,o,(f(X.)) - fm (f)(i)
< sup Σ wxlf(X,) fm,))(X))
(195)
feF
S sup feF
/ -ma
(196)
< V
(197)
37

---

Now, for the second term, by Lemma]
|
we have
T7
Σ
W.OS Σ
Sup who: 11-10x))---1(1110
sup Σ
sup fer
(198)
Thus, using Lemma]] !
E
sup /EF
Σ
(199)
m
Note that K(s()) - 11:00) -0-0) E
Σ Twlp l2 sup (15(()) -
(200)
seF
2ln F/ Further, by triangle inequality,
-)-(F)-)-((f))) - (lf((f))
- fll If f--1(f)l
(201)
5 te-1
(202)
3ej
(203)
= 6(( (-1)-
(204)
Thus,
E sup FEF
WHO
Σ (5-
$ [2/| Σ (g - (t)) [Fyl-
(205)
J=1
Combining the above bounds,
(Fo X) S 1|w12
2 2//ccm11 + 12 > (cg
s InC es /n
llw)
(206)
1=1
e/2
< ||l||2
n 2m+1 2V"2m+I + +22
c
VlnC(F, x,, 11-1ll)dd 2111-lluddd
(207)
cf2mm11
For any e E (0, q]. 3m E 2>1 such that 2 SeS
c
Thus,
2m
p0/2
(F o x) $ ||w||2 2//nc + 12
VIC((F 2,. 1..., (lw)do }
(208)
e/2
Taking <-> obtain
2//2
(F x) S 12|lw
W(nC(F x, 1w.dx..
(209)
Setting e = 1 and using Lemma
3 obtain
e/2
10 2e
Ry ()) 12/vC(F) ||l|2
dx x2
(210)
x2
0//2
20
$ 12
V
In dr using In S 22/eVz 2
(211)
< 331/vC(F)]lu112
(212)
Lemma 3. C(F, xI
< 1 In VC(F)
The readers can refer to the proof of Lemma presented in distance
45
which generalizes to our modified
|| |/..
38

---

Proposition 4. Let be a family of valued functiins and let Ni...., Xn P. For fixed vector w E R. with probability at least - 6.
} 62]lw/llv + 1w0
log
supp
Σ wx(f(x,)) - SEF
(213)
Proof. By McDiarmid's inequality, with probability at least 1 - 8,
}
Σ (x(x)) - ELCCC))) }/
log
sup JEF
Σ (x())( -E(((OI))
S IE
sup SEF
+ -1lwll2
2
(214)
Let X 1..... X
then
}
}}]
E
sup ʃEF
Σ
-
sup LEF
E
Σ (x:(((X) X
(215)
(x((f())) -F(3))) }
E
sup fer
(216)
by Jensen's 's inequality. Let 01. on be i..dd Rademacher random variables then
}
Σ w.oo(f(Xx)) - F(X3)) H
Σ (f(x,) - f(x3)
E
sup
= E
sup JEF
(217)
FEF
< E
sup FEF
waFzf(Xi,) + sup
Σ wil w;(-o;)
JEF
(218)
= 2E
sup
w(oif((i)
(219)
fEF
2E
RRw (FoX)
(220)
The result of Lemma
Seemma@comea completes the proof.
F LeCam-Assouad Interpolation Lower Bound
In this section, provide improved lower bound over those in Appendix C.2 and Appendix D.2 while using similar ideas.
Fix value of E [d] and m = - such that they are whole numbers. Roughly speaking, shall parametrize the mean of the d-dimensional Gaussian distributions in the hypotheses by vectors in {-d, 8 with repeating each element m times. Choosing leads Le Cam's method while t == d leads to Assouad's 's method.
For vector R², let (v( Rd witt
e<(v), u7a/a] Vi [d],
(221)
where [.] denotes the ceiling function. For convenience, we drop the subscript and denote (x by e(v). Define the parameterized distribution Ps(T) = (Ve((T), T) for 5 > 0 to be specified later, and let Pa {Po(T)]T E {
The supremum in minimax definition is over both the true distribution and the adversarial strategy. shall specify the adversarial strategy later for our lower bound argument.
Note:
Note that LPAC (X, D 2 LPAC (A, Ps) 45 and thus, we shall lower bound LPAC (A, Ps).
We begin by lower bounding
(A Ps) inf sup E P [I -pp112] PEP:
(222)
39

---

For vector T, let 7 denote the vector such that = 7/' Vi + j and Ty = rj.. Using Assouad's
lower bound technique 28
inf sup E (2 - pr M PEPs
inf
1
Σ
B - 5c(T))1
(223)
M
2
TE(-1.11
= inf
1
Σ
E [M()) 5e(T),1
(224)
M rE(-1,1)
2
inf
Σ
E
[IM (C- - -0T
2
TE(-1,1)
(225)
Σ rE(-1,1)
E
(2) - 8T:1
M
k=1
(226)
Now, note that Vi, k
E (Z)
8T.
+
[IM (1 1-1++ 8T,12
Σ
(-
2
TEf-1,13
1,1-1,13
(227)
Thus, we get
221
E ( (;- - 5T + E [IM
(E- 1)++ 8T;113
Lz(A, Po)
inf
2
2
rE(-1.1)
(228)
(Z) - 5T.
+
E
[M
()
(1-1)++k
8T.
inf
2
2
1.1=1.13+
(229)
2
3ΣΣ Σ 8 (U-TTVP2=,PAth) Par)))(r9)),, k= rE(-1.13
(230)
where the last line follows by Le Cam's method and the notation Pz~, Po(T) refers to the distribution of Z when the true distribution is PT(
Adversarial strategy motivation: Consider particular sample with corruption rate and let the underlying true distribution be Po(T). Denote the perturbed sample as Z(r) and the outlier to be (r). Note that Z(T) ~ (1 - Xx()) + XP For any particular clean sample X (() Ps(7). the adversary's goal to ensure the sample Z(T) contains no information about т. One possible way P(r') where the maximum is taken pointwise over the pdf and T a normalizing constant. Observe the identity
is that the adversary try ensure Z(r) ~ max./ T
P(T)
+
mmx (mxx P(7') -P(r)) = max P(T'),
(231)
-'
where (+)+ = maxt- 0} is pointwise over the pdf. First, note that
max (x(7')()) Pd(()(()) da d==T-1,
T'
(max,exs P(r')- T-1
where (a())(x) is understood to be the pdf of P3(T) at r. Thus,
a valid
pdf, and for À I=t, we have (1 X)P(TT + (max,' ((r')P(())
max P(r))
Thus, for
T-1
40

---

any 121-1 7. there exists way for the adversary to make the distribution of Z(r) max, P(r') rendering the sample useless for identifying т.
Now, we find an upper bound on T in terms of 6. Let 1 denote a vector of size m with all elements equal 1.
T
max ZERR rE(-1,1)
dr
(232)
(2
max Jt UEER' (2T) rE(-1,1)*
1s-6e(-)
de
(233)
VoSERm ((2T) m rE1-1.1)
max
del
(234)
Now note that
1e'-Ar113
max =E(-1,1)
dr' 1+ TV
(235)
Z'RR (22)
by total variation definition. Using Pinskser's inequality and KL divergence between multivariate Gaussians, we obtain
(VW((61..).N(1111)))
(236)
2
= mm
(237)
Combining (234).
235 and 237 and using m =
T T (1+8m < ovid
(238)
(239)
Thus, if A 1 - 1- -vid then the adversary can ensure that (())
max. P(r)
and contains no
T
information about т.
Adversarial strategy: If for sample i, A; 2 1 - c -vid then independently sample X()) ~
max, Po(r") P((r)) + (1 - 3) max./ Pa(t') where 3 (T-1)(1-A) T
The constraint A; 2
T-1
X
1 5vid ensures / E [0, 1] and the above is a valid distribution.
Thus, Z(r) max, Ps(r') If X < 1 - -- AvErd then adversary does corruption, equivalently, T independently sample (7) ~ Ps(T) so that ((7) ~ Ps(T).
Thus, using Pinsker's inequality in (30)) obtain
Lg(A, P&) >
Σ
82
KL (L(PZ~APo(r), Pa-sPattn)
(240)
2
2
k= i=1
T.(-1.13
Σ -11-1,11
8²
KL (87=1 03n
(241)
2
2
Σ
82
Σ
(L(P)(T),
(242)
2
2
TE(-1,13
<iv
d82
d
(1-
i n(1 - e -vval)
A8
(243)
Let 6, be such that
n11 e -6. -ilV
< 64d62
and N(1 - e -b.V
2
(244)
64d82
41

---

Substituting 6, in (243)
do? S inf sup
Ez-,p P [lI -uple -
(245)
M PEPs.
For a random variable K, let Q(K, inf Pr 1) S (1-a)), i.e. Q(, a is the a-quantile of the random variable. Note that for random variable K, EK S Q(K, x)2 + (1 x s)sss-uupK Vr E [0, 1], where ess-sup denotes essential supremum. Further, note that in the minimax term ar suppEP.. : we can restrict ourselves to estimators M which output in [-5,, 5.1 almost surely otherwise the error can be reduced by projected to this region. Thus ess-sup/ (l MPll I 4d62 for any estimator M and any distribution P. Thus, combining the above observations, we have
inf sup Σ (Z) uPll z inf sup M PEPs. FQ (IM(2)- uPll2 5
4
4d6
(246)
Ad PEPs.
5
Using 245). we get
7
< inf sup o ((IMZ)) up upl12
4
4
4d6
8
do
5 M PEPs.
112,
5)
+
5
(247)
4
4d6²
= Po.)+
(248)
5
3 d6? S LA Po.) S LPpc D
(249)
40
We remark that the lower bound presented here appears to be different from that of Appendix C.2 However, the exact difference is hard to comment since the term 8 is implicitly defined in the two bounds. We do however remark that can reconstruct the same vd gap in upper and lower bound using this method as demonstrated below.
F.1 On Minimax Optimality
In the upper bound, use the weighing w; [A. E1A.51-ff.var 2
From 74p Ve E [0,1] such that
N(1-otevit)
Nio S e for some universal constant c, we have
d )
jiss (iss(Z, w()))
(250)
Thus, min (u2 + No.) ) S and let the minimum value be attained at v", then we have
d
Aūs(Z, w(v")) -1112 x
0x +
(251)
N(v*)
<
e
So
(252)
N 1 c 85ve
64d262
< dto2 +
(253)
t
~ 5.52 (setting 1 = Vd)
(254)
Combining with 249 when min (0² Mo0 s c, we have
where we used 244 in (553)
d
do² S (PAc(A, (AA))
min vE
0² + N(v)
<dl.88
(255)
d Scc. Thus, when min (12 N(C)
1 d
( 2
min
N(1) S LPAC(A,
DN)
min [c(0.]]
(256)
Vd
42

---

F.2 Benefits of this Lower Bound
The lower bound presented Appendix does match the standard lower bound when all the corruptions rates are equal, i... the homogeneous robust estimation problem. When À = λ1, from
(95) in Appendix C.2 we obtain
{ vdo < log
(
Le(A1,Pb) 2 vd8² 1 no
(257)
Setting 8. max
1 log 2/n
[-
obtain the lower bound
Vd
vd +
x²
La(A1,Po.)
(258)
Vd
and thus,
Vd
X²
IPA
+
(259)
Vd
Using the lower bound presented of (243)
fix this issue.
Take 1 and set 6.
1 log
{ to get the lower bound
max
2dn''
Va
18.A1,P8.) + x
(260)
Now take d and set 8, max {
{ log ( }
get the lower bound
V2n
Ln(A1, Ps) 2 d
(261)
Combining the two cases, obtain the bound
d + X² Lg(A1,
(262)
and thus, get the right lower bound of
LPAC (A1,
2 X?
(263)
Similar steps can be used for Gaussian linear regression.
43


Reviews:
[{"review_id": "eMu0SizJwM", "reviewer": "Reviewer_hemm", "summary": "The paper presents a generalization of the Huber contamination model to heterogenous known per-sample corruption rates and presents estimators and proofs of optimality (up to a constant factor) for mean estimation in two settings (bounded distributions and Gaussians) as well as linear regression with Gaussian covariates.", "questions": "How frequently is knowing $\\lambda$ (or an accurate approximation) realistic in settings such as federated learning?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\nRobust mean estimation is an important problem; the author's heterogenous contamination model is applicable to practical settings such as federated learning. The optimal estimators presented are valuable contributions; the proofs of optimality presented are clear and helpful.\n\n### Weaknesses\n\nAs noted by the authors, the estimators presented are only tractable on low-dimensional data, and require that corruption rates for each sample are known, which may not always be realistic in practice.\n\nThe paper has a large number of minor typos and grammatical errors:\n- \"are not independent can dependent\" on line 197\n- $||\\mu_{P_1} - \\mu_{P_2}||^2_2$ should be $||\\mu_{P_0} - \\mu_{P_1}||^2_2$ on line 215\n- \"This conditions\" should be \"This condition\" on line 228\n- \"get\" -> \"get a\" on line 230\n- $\\hat{\\mu}_S(\\boldsymbol{Z}, w(t))$ is generally used instead of the $\\hat{\\mu}_S(\\boldsymbol{Z}, t)$ from Equation 20 that appears to be intended", "was_revised": true, "final_justification": "I maintain my score of accept given the paper's significant theoretical contributions.", "rebuttal": "We appreciate the reviewer for pointing out this practical question. It can indeed be challenging to know the corruption rates in practice. It may be noted that we just need a constant factor approximation $\\hat \\lambda_i$ of the corruption rate for our bounds to hold (i.e., $\\lambda_i \\leq c \\hat \\lambda_i$). For this reason, it is common in the robust estimation literature to assume that we roughly know the corruption rate. In practice, corruption rates can often be estimated from past performance. For example, the reviewer mentions the setting of federated learning. In many standard federated learning setups, such as those which arise in learning over an IoT sensor network, one can monitor the response of nodes to estimate individual corruption rates. In addition, our assumption of $\\lambda$ being known is still a useful modeling choice. The theory we develop allows us to understand how the estimation error degrades as a function of the corruption rates; this can help answer practical questions such as whether it is better to replace some bad sensors, or to focus on expanding the network with possibly lower quality sensors."}, {"review_id": "55PG9wYS3D", "reviewer": "Reviewer_VCX4", "summary": "The paper proposes and studies the model of heterogeneous corruption where the $i$-th sample in the dataset has a different (assumed to be known) corruption level $\\lambda_i$ and the $i$-th point is generated by (i) determining with probability $\\lambda_i$ whether the sample is inlier and (ii) in case of inlier the sample is drawn from the inlier distribution, otherwise it is drawn from a different distribution (given the previous samples).\n\nThe paper establishes the minimax rates for several estimation problems under this model: Mean estimation for multivariate bounded distributions, mean estimation for multivariate Gaussians with identity covariance and multivariate linear regression. For the last two there is a gap of $\\sqrt{d}$ between the upper and lower bounds.\n\nThe upper bounds all involve the function $f(\\lambda,k)=\\min_{t \\in [0,1]}(k/\\{\\lambda_i \\leq t\\}+t^2)$ which is related to the best effective corruption rate. The upper bounds can be achieved by a simple algorithm that chooses a corruption level $t$ and runs an estimator on the subset of the data data corresponding to $\\lambda_i \\leq t$ (where $t$ is chosen to minimize the error). The authors also show alternative methods based on reweighting the points (for the bounded distributions case they show a method that optimizes the weights of the points based on explicit calculations, and for the other problems they show variants of the Tukey median and Tukey regression depth). The lower bounds are built on Le Cam's two point method.", "questions": "The third bullet in the definition of the contamination model is a bit stronger than Huber's model with heterogeneous corruption levels, since outliers are drawn adaptively. Is this adaptivity necessary to assume for the lower bounds?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- Estimation with heterogeneous data is well motivated. The paper gives the first non-trivial results for basic estimation problems that remained unstudied.\n- The paper provides experiments showing the advantage of the proposed algorithms.\n\nWeaknesses:\n\n- The bounds on the minimax squared $\\ell_2$ error are tight only for the bounded support distributions and univariate Gaussians and has a $\\sqrt{d}$ gap otherwise. This is still better than naive coordinate-wise methods but means that the precise bound is still unknown.\n- Some of the narrative about the upper bound method was somewhat unclear to me even after the explanation of page 2. If the simple algorithm of running the homogeneous contamination estimator for the best level achieves the claimed error upper bound is there a theoretical advantage of the other methods presented or they are shown as alternative methods?", "was_revised": true, "final_justification": "The authors have provided clear explanations to my points. After reviewing the other rebuttals and discussions my view of the paper remains positive, I thus keep my original score.", "rebuttal": "We thank the reviewer for their review and apologise for the confusion regarding the discussion of weighted estimator in the text. We clarify that indeed the thresholding method, a strict subset of the weighted estimator, is used to obtain the bounds provided in this work. However, we include the weighted estimator as we believe that it might be important in establishing a tighter bound in the high-dimensional Gaussian setting in some regimes. We shall change the current exposition to reflect this point more clearly. \n\nThe reviewer also asks about the adaptivity in the contamination model. We emphasize that our lower bounds do not require adaptivity, whereas our upper bounds hold even against adaptive adversaries. We consider the adaptive adversary in large part only because such adversaries are standard in the robust statistics literature [21]. However, it is an interesting question to fully characterize the power of adaptivity in such heterogeneous settings, as has been done in the standard homogeneous setting.\n\nRegarding the $O(\\sqrt{d})$ gap, please see the response we posted to Reviewer 9oan."}, {"review_id": "Y9AibkUT7q", "reviewer": "Reviewer_1wmi", "summary": "This paper introduces a novel framework for robust estimation under heterogeneous corruption, where each data point can be corrupted with a known, but potentially distinct, probability $\\lambda_i$. This model is a generalization of the standard Huber contamination model, which assumes a uniform corruption rate.  The authors provide a theoretical analysis for several fundamental estimation problems within this framework. For bounded mean estimation, they establish tight minimax optimal rates. For multivariate Gaussian mean estimation and linear regression, they establish minimax rates up to a factor of $\\sqrt{d}$, where $d$ is the dimension. The paper proposes two main types of estimators: a simple and intuitive thresholding-based method, and a more refined per-sample reweighting scheme. The results suggest that the optimal estimators may effectively discard samples whose corruption rates exceed a certain threshold, which is determined by the empirical distribution of the corruption rates themselves.", "questions": "1. The paper's main theoretical limitation is the $\\sqrt{d}$ gap in the high-dimensional settings (Theorem 4 and 5). The authors suggest this might be an \"artifact of the analysis\".  Could you provide more intuition on why the current analysis techniques (specifically, the uniform convergence bounds for the weighted Tukey median in Appendix C.1) might be losing this factor? Do you have a conjecture on whether the upper or lower bound is closer to the true rate, and what new analytical tools might be needed to close this gap?\n\n2. The framework assumes that the corruption rates $\\lambda_i$ are known precisely. How would the proposed rates change if one only had access to estimates $\\hat{\\lambda}_i$ such that, for instance, $|\\hat{\\lambda}_i - \\lambda_i| \\leq \\varepsilon$ for all $i$? Would the error from estimating $\\lambda_i$ dominate the statistical error rates derived in the paper, or would it add a lower-order term? A brief formal discussion on this point would strengthen the paper's practical relevance.\n\n3. The paper proposes both a simple thresholding estimator and a more complex reweighting estimator (Algorithm 1). For bounded mean estimation, the thresholding estimator is sufficient to achieve the minimax rate. The experiments in Figure 2a show only \"marginal improvement\" from the reweighting scheme.  Could the authors provide more insight into the scenarios where the additional complexity of the optimal reweighting scheme is justified? Is there a specific structure in the distribution of $\\lambda_i$ values where reweighting provides a significant practical advantage over simply choosing an optimal threshold?\n\n4. In the proof of the upper bound for the weighted Tukey median (Proposition 1, Appendix C.1), the result relies on Proposition 4, which provides a weighted generalization bound. The bound on the Rademacher complexity in Lemma 2 has a dependency on $\\|w\\|_2$.  This $\\|w\\|_2$ term eventually leads to the $\\frac{d}{N(t)}$ term for the thresholding estimator. Is this dependence on $\\|w\\|_2$ fundamental, or is it possible that a different analysis technique could yield a bound that depends on the weights w in a more nuanced way, potentially helping to close the  $\\sqrt{d}$ gap?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths\n\n\n1. **Originality and Significance:** The formulation of the robust estimation problem with heterogeneous corruption rates is novel and significant. It addresses a practical limitation of existing models that assume homogeneous corruption, making the framework relevant for applications in distributed settings like federated learning, crowdsourcing, and sensor networks. \n\n\n\n2. **Theoretical Depth and Rigor:** The paper provides a comprehensive theoretical analysis, deriving minimax rates for several key problems. The proofs for the upper and lower bounds are rigorous. For the bounded mean estimation problem, the derived rate is shown to be tight, which is a strong result. The use of both Le Cam's and Assouad's methods for the lower bounds demonstrates a sophisticated handling of the technical challenges. \n\n\n3. **Proposed Estimators:** The paper proposes both a simple, computationally efficient thresholding estimator and a more complex reweighting scheme (Algorithm 1). The thresholding approach is intuitive and shown to be minimax optimal (up to constants), providing a clear and actionable strategy. The introduction of weighted versions of Tukey depth and regression depth is a natural and elegant extension of classical robust methods to the heterogeneous setting. \n\n\n\n\n\n### Weaknesses\n\n\n1. **Gap in Bounds for High Dimensions:** The most significant limitation is the  $\\sqrt{d}$ gap between the upper and lower bounds for multivariate Gaussian mean estimation and linear regression.  While the authors are transparent about this gap, it means the characterization of the minimax rate in high dimensions is incomplete. It remains unclear whether this is an artifact of the analysis or a true phenomenon. \n\n\n2. **Assumption of Known Corruption Rates:** The entire framework relies on the assumption that the corruption rates $\\lambda_i$ are known exactly.  The authors mention that their bounds generalize to approximate knowledge of $\\lambda_i$, but this is not formally detailed. In many practical scenarios, these rates may need to be estimated, which would introduce an additional layer of error not accounted for in the current analysis.\n\n\n3. **Limited Practical Demonstration:** The experimental evaluation is presented as \"preliminary\". While the results in Figure 2 do support the theoretical claims by showing improvement over baselines, they are limited to low-dimensional synthetic data. Furthermore, the practical advantage of the more complex reweighting scheme over the simple thresholding method is described as \"marginal\" for the bounded case, which might underwhelm practitioners.", "was_revised": true, "final_justification": "I am maintaining my score.\n\nThe paper introduces a novel and interesting framework for robust estimation with heterogeneous corruption. While the primary weakness is the $\\sqrt{d}$ gap in high-dimensional settings, the authors convincingly argued that their result is a non-trivial improvement over prior work. Their plan to refine the lower bound is reasonable. The rebuttal successfully clarified all my concerns.", "rebuttal": "We thank the reviewer for their review. \n\n1) Please see the response we posted to reviewer 9oan.\n\n2) See response to Reviewer hemm. In general, our methods are able to easily tolerate multiplicative errors in knowing the $\\lambda_i$. We did not consider the exact form of additive error that the reviewer proposes, but in some sense it seems less natural to have additive error when $\\lambda_i$ is small. However, we believe exploring this could be an interesting direction.\n\n3) This is indeed an interesting question. In theory, the reweighting scheme subsumes the thresholding estimator. While we use the thresholding estimator for proving the minimax bounds, we present the more complex estimator to demonstrate the possible constant-factor advantages in the bounded setting. In fact, we conjecture that in the Gaussian high-dimensional setting, the weighted Tukey estimator should outperform the thresholding estimator, at least in some regimes. \n\n4) While the weighted Tukey median likely does sometimes outperform thresholding-based estimators in the high dimensional setting, there is a fundamental difficulty with obtaining tight bounds in all regimes with any weighted Tukey median-based technique. In particular, in the semi-verified regime (as defined on lines 65-74), one can show that no weighted Tukey median will be able to obtain optimal rates in all parameter regimes. Rather, it seems that a “two-step” process will be necessary to obtain tight statistical rates. This is one of the concrete barriers we encountered that we alluded to in the response to Reviewer 9oan, and in the next version of the paper, we will make this connection more explicit."}, {"review_id": "TLVaEUjke6", "reviewer": "Reviewer_9oan", "summary": "The authors consider the problem of robust estimation under the Heterogeneous corruption model, where the corruption across samples is independently but not identically distributed. They derive upper and lower bounds on the minimax rates (and minimax PAC rates) for several canonical estimation problem such as mean estimation for Gaussian distributions and linear regression in this heterogeneously robust corruption model.", "questions": "I would like to see more discussion on the O(\\sqrtt{d}) gap in the regime where the dimension in not constant. Which of the bounds is conjectured to be tight by the authors and why?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: I find this particular model of heterogeneous robust corruption to be interesting and well supported by practical scenarios. The results are clearly presented and intuitions are given for the algorithms attaining the upper bounds and the lower bounds techniques. The difficulty of this scenario w.r.t. classical robust estimation is captured in the introduction, and the approaches of the authors are adjusted to retrieve non-trivial bounds.\nWeaknesses: While I do think the results are intersting, they seem to be quite loose. I particularly refer to the results of Gaussian mean estimation and Linear Regression, which suffer from a O(\\sqrt{d}) deficit between the upper and lower bounds, which is only tight in the non interesting constant dimension regime.", "was_revised": true, "final_justification": "I am maintaining my score. While I think the results are intersting, non-trivial, and should be published, the gap in high-dimensional settings prevents me from giving a higher score than my current one.", "rebuttal": "We acknowledge that closing this gap in high dimensions is a very interesting open problem. However, we want to emphasize (as some reviewers also point out), that obtaining a $O(\\sqrt{d})$ gap is already quite nontrivial, as all previously known techniques would achieve a $O(d)$ gap. \n\nFrom a technical perspective, there are new, interesting behaviors unique to these high dimensional settings that present as concrete barriers to reducing this gap, and it seems like neither bound is tight for all regimes. In the full version of the paper, we will expand upon the types of barriers we found, and why we believe that fundamentally new ideas are needed to obtain fully instance-optimal bounds. As a first step in this direction, in the full version of the paper, we will include a refined version of the lower bound technique which properly interpolates between Le Cam and Assoaud’s lemma, i.e., interpolates between $2$ to $2^d$ hypotheses. We believe that analyzing this technique properly gives us a promising avenue to obtaining tighter lower bounds for all regimes."}]

Author rebuttal:

Meta-review: This paper is a contribution in robust statistics, studying a generalization of the Huber contamination model where the corruption rate depends on the (index of) the sample and is known a-priori. The paper studies mean estimation (bounded, Gaussian) and linear regression (Gaussian), and show either up-to-constant tight minimax rate results, or new results that have a $\sqrt{d}$ factor gap.

Reviewers agree that the model and problem setting are both of interest to the NeurIPS community. While there is still a $\sqrt{d}$ gap for some problems, this is already an improvement as prior techniques would yield a $O(d)$ gap.

I recommend acceptance of this paper as there are no soundness concerns and the results are of interest to the community.
Decision: Accept (poster)