Trimmed Maximum Likelihood Estimation for Robust Generalized Linear Model
Authors: Pranjal Awasthi
Abhimanyu Das
Weihao Kong
Rajat Sen
Venue: NeurIPS 2022 Accept (2022)

Abstract: We study the problem of learning generalized linear models under adversarial corruptions.
We analyze a classical heuristic called the \textit{iterative trimmed maximum likelihood estimator} which is known to be effective against \textit{label corruptions} in practice. Under label corruptions, we prove that this simple estimator achieves minimax near-optimal risk on a wide range of generalized linear models, including Gaussian regression, Poisson regression and Binomial regression. Finally, we extend the estimator to the much more challenging setting of \textit{label and covariate corruptions} and demonstrate its robustness and optimality in that setting as well.

Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models
Pranjal Awasthi
Abhimanyu Das Google Research
Google Research
pranjallavastii@oogggee.co
abhidas@google.co com
Weihao Kong Google Research
Rajat Sen
Google Research senrajat@google.co com
weihaookogggoogle..coo com
Abstract
We study the problem of learning generalized linear models under adversarial corruptions. We analyze classical heuristic called the iterative trimmed maximum likelihood estimator which is known to be effective against label corruptions practice. Under label corruptions, we prove that this simple estimator achieves minimax opar-optimal risk on wide range of generalized linear models, includ- ing Gaussian regression, Poisson regression and Binomial regression. Finally, we extend the estimator to the more challenging setting of label and covariate corruptions and demonstrate its robustness and optimality in that setting well.
Introduction
Generalized lincar models (GLMs) are an elegant framework for statistical modeling of data and are widely used in many applications [NW72 DB18 MN19.. generalized linear model captures the relationship of labels (or observations) y to covariates via the conditional density f x) x exp(y- 3 x- b(3 x)). Here 3 is the parameter of the model. Parameter estimation in GLMs is done via the standard maximum likelihood estimation (MLE) paradigm and has been extensively studied [NW72). While GLMs offer a mathematically tractable formulation for statistical modeling, real data rarely satisfies the generative process GLM and as a result there has been considerable interest in developing robust learning algorithms for GLMs [LWI]] NRWYID PSBRI8] The predominant way to model misspecification or adversarial corruptions in the data is Huber's e-contamination model These models assume that small fraction of the data corrupted by an adversary. Furthermore, the adversary can be restricted to either only corrupting the labels y, or be allowed to corrupt both the covariates and the labels y for an fraction of the data.
[Hubll] and its recent extensions that allow for stronger adversaries
Various algorithms have been proposed for robust estimation in generalized linear models. One line of work proposed computationally intractable algorithms that are based on non-convex M estimators [Hubll] LWI1 or by running tournaments over exponentially large search space Yat85] Another line of work proposes polynomial time algorithms that either achieve sub-optimal error rates [PSBRI8] or only apply to restricted settings such the noise being heavy tailed [ZZ21] In practical settings a simple heuristic namely the iterative trimmed estimator has been shown to work well under settings where only the labels are corrupted [SS19b]. However, from a theoretical perspective the iterative trimmed MLE estimator has only been analyzed under restrictive settings such when the underlying GLM is Gaussian regression model.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Our key theoretical contribution in this work is a general analysis of the trimmed MLE estimator. In particular, we show that for broad family of GLMs, and under adversarial corruptions of only the labels, not only does the iterative trimmed MLE estimator enjoy theoretical guarantees, it in fact nearly achieves the minimax error rate! Next, we also consider the more challenging setting of corruptions to both covariates and labels. In the setting where the covariance of the covariate is known, we leverage the same approach in [PJL20] by running the filtering algorithm [DHL19 as a prepossessing step to trim away the abnormal covariates before applying the iterative trimmed MLE estimator. This can simultancously handle both covariate and label corruptions and nearly achieve minimax eтrоr rates. Below state main results.
Un)} be independent and identically distributed samples generated by a generalized linear model with sub- Gaussian Ty. Let an e fraction of the labels be adversarially corrupted. Then, with high probability, the iterative trimmed MLE estimator when given as input S. provides the following guarantees:
Theorem 1.1 (Informal Theorem). Let S. = {(x1,
O 1/e)) parameter estimation error for the Gaussian regression model where a² is the variance of Gaussian noise on y.
( ( elee(pp(llg(/// (og((/))) parameter estimation error for Poisson regression model.
"<tmeVlogge log(1/E)) parameter estimation error for the Binomial regression model with m trials.
(ollog(1/c) parameter estimation error for a general class of smooth and continuous GLMs (includes the Gaussian regression model).
Previous work [SSI9b] analyze the iterative trimmed maximum likelihood estimator under the Gaussian regression settings (least square) where only the labels are corrupted, and proved O(r) fz-error bound for parameter estimation. Other iterative trimming approach such as [BJK15] also achieves only achieve (ar) error in this setting. Our error bound of ( log(1/e)) significantly improved the dependency on the corruption level e and nearly matched the minimax lower bound of ae [Gao20]. In all the generalized linear models studied in this work, we show that the iterative trimmed maximum likelihood estimator achieves (s2-6) error for any 8 > 0, which matches the minimax lower bound (2()) up to a sub-polynomial factor.
Next, we present our second main result that can simultaneously handle both covariate and label corruptions and nearly achieve minimax eтrоr rate.
Theorem 1.2 (Informal Theorem). Let S. {(x1, 32)..... "......,(xs (Xn. be independent and iden- tically distributed samples generated by a generalized linear model with sub- Gaussian x, whose covariance is known. Let an e fraction of the labels and covariates be adversarially corrupted. After a preprocessing step. the iterative trimmed MLE with high probability achieves the same parameter estimation recovery bounds as in Theorem ablove.
Our algorithm requires the covariance matrix of the covariate distribution being identity or known. Thus the error rate we get is incomparable to the results in the general covariance settings.
Outline of the paper. In Section 2 we discuss related work. We define preliminaries in Section followed by the iterative trimmed MIE algorithm, formal results, and proof sketches for the label corruption case in Section 4 In Section 5 the sample corruption case. We defer proofs to the Appendix.
we introduce our algorithm, results and proof sketches for
2 Related Work
There is vast amount of literature in statistics, machine learning and theoretical computer science on algorithms that are robust to adversarial corruptions and outliers. Classical works in the Huber's s contamination model present algorithms for general robust estimation that obtain near optimal eтror rates [Hubll] Yat85). Minimax optimal but computationally inefficient robust estimators have been established in the works of [Tuk75] Yat85 CGRI5 Gao20) for a variety of problems such as mean and covariance estimation. In recent years there has also been a line of work in designing computationally efficient algorithms for handling adversarial corruptions LRVI6 DKK + CSVI7
BJK15] CKMY22
CAT 20 DKSS21].

---

Several special cases of generalized linear model has been studied extensively from the robustness perspective. There is a long line of work on designing robust algorithms for the linear least squares problem. This corresponds to the special case of the GL.M being Gaussian regression model
[SBRI19] BIK15 BIKK KKM18 CCML3 BP21 PJL.20 DKS19]. When the covariate follows from a aub-Gaussian distribution, previous best result 20 achieves Eg error σe /logo](1/e using Huber regression while we show iterative thresholding achieves relog((// (ss) error. Another special case of GLMs that has been studied from a robustness perspective is the logistic regression model [EXMY14] [PSBR18 CKMY20) Our analysis of the iterative trimmed MLE estimator on binomial regression matches the best known eтror guarantees for this setting.
The work of [PSBRT8] proposes a general procedure for robust gradient descent and shows that one use this design robust estimation algorithms for a abroad class of GL. Building upon these works, the authors in [JLST2I] present nearly linear time algorithm for GLMs. Compared to our work, [PSBRI8] assumes æ has bounded 8th moment, [JLST2I] assumes x 2-4 hypercontractive. and both papers achieve an OVVE) error guarantee with e-fraction of corruptions while our algorithm achieves better (s) guarantee under the stronger sub-Gaussian assumptions. In addition, for GLMs, both papers assume a uniform upper bound (and lower bound) on the second order derivative of function b(-), which is not satisfied by the widely used Poisson and Binomial regression studied in this paper. In a similar setting, [ZZ21] proposed a reweighted MLE estimator for dealing with settings where the covariates are heavy tailed but not corrupted by an adversary.
Iterative thresholding is a longstanding heuristic for robust linear regression that dates back to Legendre LS59.. It's theoretical property in the non-asymptotic regime is first studied in (BJK13), which shows a (or) error bound for sufficiently small label corruption level when the label noise is (0, o²). The iterative thresholding algorithm is later extended and analyzed in the oblivious label corruption setting [BJKK17 SBRJ19), and is shown to provide consistent estimate even when the corruption level goes to PJL20] extended the iterative thresholding algorithm to the heavy-tailed covariate setting and can simultaneously handle both labels and covariate corruptions.
In addition, [PL20 adapted the implicit result in [BJKKI7] to show that iterative thresholding
algorithm achieves O(a error rate for sub-Gaussian covariate. [SS19b] empirically demonstrated
the effectiveness of the trimmed loss estimator under labels corruptions, and also proved theoretical guarantees in a special class of GLMs, which, however, also has ((r) error when specialized to the Gaussian noise setting. (SS19a) studied the trimmed loss estimator the mixed linear regression setting. Finally, [CKMY22] proposed an alternating minimization algorithm for the fixed design linear regression setting with Huber contamination on the labels, which different from our strong contamination model (with adaptive replacement) for generalized linear model. Their algorithm incorporates semidefinite programming in the set selection step, and achieves a near-optimal Ö(ae) error. On a very high level, our proof follows from a similar framework as in [CKMY22).
PJL20 first proposed a generic approach to modify an estimator which is robust against label corruption into one that is robust against simultaneous label and covariate corruptions by running a covariate filter algorithm [DKP20] [DK19 as a preprocessing step. In the Gaussian regression setting, our Algorithm@ij identical to Algorithm 3 of [P]L20] and the difference is in the improved error rate. In particular, Lemma 4.1 in [PJ220 implies a (E) error bound while we proved Oore log error bound.
3 Preliminaries
In this section, we formally introduce the robust generalized linear model studied in this paper. First we define the classical generalized linear model as follows.
Definition 3.1 (Generalized linear model). We say that (x, y) follows from generalized linear model if there exist function b(-), and function c(-) such that the probability density function of equals
f(yl3 x) =ly) exp(y- 3T xx
The derivative 6-(-) is called mean function E'yl3" x] (((3Tx). x). The second order derivative (")+) is called variance function as Var[yl x = b"( x)
Here we provide three commonly used examples of generalized linear models studied in this paper.
Definition 3.2. Commonly used examples of generalized linear model
3

---

Gaussian regression: b(0) 3 cly) expí 1xp(-1///2 12/2) /2z
Poisson regression: 6(0) = (), c(y) = y!
Binomial regression: Let m be the number of trials of the binomial distribution. b(0) m log(1 exp(0)), c(y)
(%)
We consider the sub-Gaussian random design setting in this work, i.e. each covariate x; is drawn i..d. from a sub-Gaussian distribution with zero mean and covariance E.
Definition 3.3 (Sub-Gaussian design), We assume that each covariate x; is drawn independently from zero mean, covariance Σ sub-Gaussian distribution with sub- nub-Guassian [[x,] = 0, E x L fnr all v E IR",
namely,
Pr(v 211) exp(-1P).
Having introduced the generation model of the good data, now we describe the corruption model where the adversary is allowed to corrupt a small fraction the data points.
Definition 3.4 (Corruption model). We consider different data generation model with fraction of adversarial corruptions:
Label corruption model:
Given n ii.dd sample {(x;, y:) generated by generalized linear model. The udversary is allowed to inspect the sample, and replace total of e labels ys with arbitrary values.
Sample corruption model: linear model. The udversary is allowed to inspect the sample, and replace total of data points (xi, yi) with arbitrary values.
Given n i.idd sample ((x,))) M= generated by a generalized
We call the corrupted dataset S = = TU E where T contains the remaining uncorrupted data points, and E contains the set of data points that is controlled by the adversary.
The goal of our algorithm is recovering the underlying regression coefficient f from set of examples with fraction corrupted under & eтror metric, i.e., ||3 fr We assume || R for a constant R. and <= e for sufficiently small constant For simplicity of the presentation, throughout this paper, we assume = Ia- We remark that our algorithm for label corruption model applies to the general covariance setting and is able to achieve small estimation error in terms |// - l since always (implicitly) whiten the data to apply analysis (see Section C for more details). On the other hand, the algorithm for sample corruption model only works with the knowledge of Σ.
4
Label Corruption
In this section, we formally describe our algorithm and proof-sketch for the label corruption setting.
4.1
Algorithm
We start with defining the trimmed maximum likelihood estimator, which is simple and natural heuristic for robustly learning generalized linear model.
Definition 4.1 (Trimmed maximum likelihood estimator). Given set of data points ((x, vi) define the trimmed maximum likelihood estimator as
((S) min min
Σ
log (url
(cS))))(1-e)nn (X..
In the setting of generalized linear model, the objective of trimmed maximum likelihood estimator is biconvex problem in Š and 3 but not jointly convex. The following alternating minimization algorithm is a simple heuristic approximate the trimmed maximum likelihood estimator whose similar form has been studied in [B] BJKKI7 [SS19] (KMY22).

---

Algorithm 1: Alternatin minimization of trimmed maximum likelihood estimator
Input: Set of examples ((x1,,1))..... (Xnn)))....,
(x), e, 7), R
Output: B g( arg [ Eierlyde lvsl:
300) + 0:
for f oo do do
Choose ((() arg www. 2c)n Eier log f (1i1k xx));
Compute B(++ arg m |118|| [ snt E Lies(1) - log (3))
if 1 Liesin log (( xx)) 1 Lieso log (1: x,)) then
Return git)
The algorithm starts by naively pruning out - data points whose labels have the largest magnitude. Then each round of the alternating minimization algorithm has two steps. In optimizing over set S, find the set ((()) of size (1 - e)n with the best likelihood. In optimizing over 88 we find regression coefficient g(t) which maximizes the likelihood on the current set of data S(t), The algorithm terminates and outputs B when the likelihood no longer improves by more than It is clear that algorithm terminates (1/1n) rounds when the log-likelihood is bounded. Since the original trimmed maximum likelihood estimator is a biconvex optimization problem in S, 3 which is not jointly convex, our algorithm does not guarantee return global optimal solution. Nonetheless, as we showed, it does return first order stationary point which will be close to the true coefficient 3 It worth noting that some recent papers on robust statistics [CDK TDK+21 CDGS20 ZJS22] show similar nice statistical properties of an approximate first order stationary point for non-convex optimization problems.
We present the guarantee of our algorithm for Gaussian, Poisson, Binomial regression, and broad class of generalized linear models.
Theorem 4.2 (Gaussian regression with label corruption). Let fx,, Us Vi be set of data points generated by Gaussian regression model with ys = 3") + Tp. NO,, sub- Gaussian design, with s--fraction of label corruption and = 2 d With probability 1- 8, Algorithm with parameters & Ec: 1)
iterations, e2, = oo terminate within O min(i,07)z))
and output an estimate 3 such that
|| 3
Theorem 4.3 (Poisson regression with label corruption). Let S Vo be a set of data points generated by Poisson regression model with sub-Gaussian design, with frartiio of label corruption and Q( (g)). With probability 0.99, Algorithm |
with parameters 22c,
e. (dn),, contant R 2 ||""| terminate within dn/e? iterations, and output estimate such that
|| - 8- - (s. exp(y (opp(/oogg(/))))
Theorem 4.4 (Binomial regression with label corruption). Let S = (x;, Us Di); be generated by a Binomial regression model with sub- Gabb-aassinnn Design, with ec-fraction of label corruption and n Q d+log(1/8)) With probability 1 8. Algorithm with parameters = Ec, = e2/m, m, constant R 2 ||3"|| terminate within m² E iterations, and output estimate such that
- --1--11-000 ( log(m/Ec) log(1/
m
Theorem 4.5 (A class of generalized linear model with label corruption). Let = fx Us h be generated by generalized linear model with lub-Gaussian Design, with ec-fraction of label corruption and n = ( d+log(1//)) Assuming that Co < 8"(-) S C for non-zero constants Co, C, b(0) = 0, 00) O, and log(c(y)) O(log(1/Ee)) Vy - e llooog///))) then with probability
5

---

1-6, Algorithm | Tith parameters = Ec, = R = oc terminates within log(1/E.) iterations,
and output estimate 3 such that
|| - 3*1 O Log(L/=))
4.2 Proof Sketch
We provide an intuitive proof sketch for the above theorems (the full proofs are deferred to Section A in the Appendix). The high level proof framework is similar to [CKMY22], although the details drastically different since the focus of our paper is on random design with strong contamination for a wide range of generalized linear model while [CKMY22 focuses linear (least square) regression with Huber corruption on the labels.
The guarantee of our alternating minimization algorithm relies two claims:
First, the algorithm returns approximate stationary point B. Second, any approximate stationary point will be close to the true coefficient 3".. In this section, we will present high level intuition of the proof of the two claims.
Alternating minimization algorithm returns an approximate stationary point. First we define the first order approximate stationary point as follows. Let & E Id be a regression coefficient vector and $ contains the set of datapoints of size (1 E)m with the largest log-likelihood under B. We call a aappproximate stationary point if
(3* - Σ V log (v.l(3 x1) VES
5 113 B1
72
i.e, the gradient of the log-likelihood projected along the 3 3 direction is small. Our goal is to show when the algorithm terminates, that is when 3 can not be improved by more than 17, the gradient along the 8 3 must be small. This is clear where the empirical log- likelihood function is smooth, simply because the gradient large, one can improve the log-likelihood by more than which will result in contradiction. The smoothness (norm of the Hessian matrix) of the empirical log-likelihood in generalized linear model is directly related to the range of (0)).. In particular, 1 (0) bounded for Gaussian regression and Binomial regression.
However, problem arises for Poisson regression where (0 = exp(0) becomes extremely large for large 0, which results in non-smooth curvature for empirical log- lilkiiihhood... We overcome this difficulty by leveraging the special property of function b(0) = cxp(0) the Poisson regression setting. Observing that the derivative 8 (()) is equal to second order derivative 8" b²(0) for Poisson regression, the gradient along the 3 3 direction can be small when the second order derivative along the 3 B direction gets large, which will result in more than r) improvement of the log- likelihood by moving toward 3 and therefore contradiction. Hence, the second order derivative along the 3 3 direction must be small, and we blue have the same argument as in the smooth objective function setting.
Any approximate stationary point will be close to the true coefficient. Let us first write down the apppproximate stationary condition for generalized linear model as
Volog ((u
-3)=
1 Σ (v. 6'B x3)) - -B) S 711,8* - -11
iES
iES
Recall that T contains the set of uncorrupted data points, and contains the set of data points that controlled by the adversary. Split Š into Š T and Š n E, and rearrange the terms we get
1
Σ - ((8
(3* Tx
Σ - x))) =) ~1 -11 iEŚNE
KEšNT
To obtain an upper bound on ||3 - B1|. we will prove a lower bound in terms ||3 B|| on the left hand side, and an upper bound in terms of || - Oll on the right hand side. Finally we will combine the upper and lower bound into an upper bound on || -1]

---

Lower bound on the LHS. Note that SnT contains uncorrupted data points. The high level intuition
that since mean y/ is b' (5 x,) and B'(.) is monotone,
(v: - 6' x.) (8" - -B) -))xx, x; should
be roughly O ( 2 and ( ((8-
- .) X2) should be proportional to |1:3" 3 given
enough samples. More formally, we will decompose the LHS as
Σ (ys ((3 x3))(0-- - -)xx
iEšNT
(B xx)x
xi) (8* -8-- -3 n
Σ iEśnT
xx)) (3* -B)=
-3xxx
Ui
iEŠNT
The first term contains (1 - E) fraction of uncorrupted random examples sampled from a zero mean distribution with certain tail bound, e.g. sub-exponential for Gaussian and Binomial regression, k-th moment bound for Poisson regression.
Therefore,
apply resilience property bound the first term. Overall, heavily utilize the resilience property of the sample set that is drawn from "nice" distributions. Take sample mean as an example, resilience (SCV17 [JSI9] (also known as stability (DKI9) dictates that given large enough sample set S = { the sample mean of any large enough subset of S will be close to each other. We define mean resilience formally here:
Definition 4.6 (Resilience). Given sample set S = {x suppose for any T C S, 2 (1-E)n, it holds thut ग Eier X; [ Eiesx;ll S then we call the set S satisifes (e, (r,s)-resilience.
Specifically, under sub- Gab-Gaussiin distribution, a set S of i.i.d samples with size n = ((d/=²) satisfies (E, ( [og((//)) resilience with high probability. Resilience property applies to sub-ex eob-epennnnial and k-th moment bounded distribution as well, and this gives us way control the behavior of any subset of good data.
For the second term, we prove that -iESST x;) is strongly convex function again using the resilience property, which implies 1 n Eiesnr (B(8* xx) 83 xi) (0* T))xx; 2211
311²).
x;)) Upper bound on the RHS. To upper bound - Eie - x3) - -3) xi. we
will prove an upper bound on / E b'(3 x2))2 and / EiESnE(((0 3) Tx,;,
separately, then apply Cauchy-Schwarz inequality. The key difficulty is bounding EiEiSnn - (fTT))))) as it contains corrupted data points controlled by an adversary,
which does not follow any good property possessed by the good stochastic data. However, since $ contains (1 8)n datapoints with the largest log- likelihoodd under B3, can argue that
Σ
log (vv x;))s
Σ VET'S
log [(vl x:))
-
SEŠEE
or even
max - log f'vv x;))5 min - iETi
log (3 x.))
SE
since otherwise one can replace the data points in S n E by the ones in T \ S to form new set with better likelihood than S. This gives an upper bound the negative log-likelihood of y in
S S E. Therefore we adopt a two step approach to upper bound the / E.eSne
TTxx,)² x,
First we prove an upper bound on the negative log-likelihood on 7 \ S, which becomes a negative log-like ligeliood bound on Š n E immediately. Second we turn the negative log- log-likeldhood bound into square error bound.
The two steps vary drastically for different regression models. For the first step of upper bounding the negative likellod,,,,d, in Gaussian regression use the resilience property of the quadratic
7

---

form of sub- Glussaassin random variable. In Poisson regression, we leverage the resilience property of y;x; which heavy tailed. In Binomial regression, since the distribution only has support size m, we directly analyze the resilience of the negative log-likelihood. In general GL,Ms, due to the generality of the likelihood function, we have to again analyze the resilience of the negative log-likeling oggliikelhood directly. For the second step of turning the log- oggliikeihhod bound to quadratic bound, we get the bound trivially in Gaussian regression since Gaussian likelihood indeed quadratic. For Poisson and Binomial setting, we have to build proxy function which lower bound the negative log-likelihood function log (,, xx)) ) to connect it to quadratic function. For the general class of GLMs, leverage the bounds on the (.))) and log(c(y)) to obtain a quadratic bound.
4.3 Proof for Poisson Regression
As an illustrative example, we show how the above proof sketch can be used for Poisson regression to formally prove Theorem 4.3 (Proofs for the other GLMs are deferred to Section A in the Appendix)
Lemma 4.7 (Approximate stationary point close to S for Poisson regression). Given a set of datapoints 5 = {x,, yi Vilim generated by a Poisson regression model with E-fraction of label corruption, and the largest en labels removed. Let B be a max(s, eax/(=, sta)-stationary point and || & R. Given that S2 / with probability 0.99, it holds that
|| 3*11 = O(E exp(( (1og/(//))))))
Since 6²( exp(f) is unbounded for Poisson regression, the following lemma (proved in the appendix) shows that alternating minimization algorithm still return an approximate stationary point Lemma 4.8 (Algorithm 1 finds an approximate stationary point for Poisson regression). Given set of datapoints S
Xx ys Vi=1 generated by a Poisson model with Ec-fraction of corruption. then with probability 1 ô, the output of Algorithm 1 with imput
Assuming that 02( d+log(1/6)
parameters e = 2Ec, R 2 |8 II. = (dn), is a max(E, a B1
2=a
>approxximate stationary point.
Proof of Theorem
4.3 Lemma 4.8 implies the output of Algorithm
max(E, 2
approxi-
113- 31
mate stationary point. Lemma 4.7 then implies that - = ( exp( /log(1/E))) To bound the
number of iterations, we need an upper bound on the negative log- likellhoo on O, and a uniform
lower bound on the negative log-likelihood. The initial negative log-likelihood is upper bounded by
1 Ete log(ye!) + -1 I (E + 1) = O(1) where ((1) contains the smallest (1 - E)n labels. Trivially, there is 0 lower bound on the negative log- likeliihood for Poisson distribution. Therefore. the algorithm will terminate in dn/s² iterations.
5 Result for Sample Corruption Model
The learning problem becomes much harder in the presence of label and covariate corruption, since it is hard to tell whether data point is corrupted by simply looking at the likelihood of yı. From a technical level, the resilience condition we leveraged on covariate x; in set F. breaks down when there is covariate corruption. Luckily, we are able to restore the resilience property by first running the filtering algorithm for robust mean estimation [DHL19] Specifically, if the covariate distribution has identity (or known) covariance and sub- sub-Gaussian tail, one can apply the filtering algorithm to the e corrupted data set, and the resulting data set {w.x,) ) will have close to identity covariance and the same resilient condition as uncorrupted data set. This prepossessing step only takes nearly linear time. This approach is firstly proposed in 2PL20 as a general method to make an algorithm robust against covariate-corruption.
5.1 Algorithm
The guarantee of Algorithm@iss formalized in the following theorems. Theorem 5.1 (Gaussian regression with sample corruption). Given a set of datapoints S (x,, V generated by a Gaussian regression model with y; = (x,, 3*) + Tks qi ~ NO0
sub-Gaussian design, fraccton of sample corruption and = 2 ( With probability
8

---

Algorithm 2: Alternating minimization of trimmed maximum likelihood estimator in sample
corruption model
Input: Set of examples $ = ((x1 (1)))))) (Xa, Un)), E, E.
Output: B
1 S. + {(E-1/xx x
91) "i..... ( (E-1//2, vn)) // Whiten the covariates.
S Filtering( S,
// Algorithm in [DL119]
3 < Algorithm ,,,,
Return 3;
1-8, Algorithm with parameters E E,, 2/ R oC terminate within O min(L,o")e? iterations, and output an estimate B such that
|| - = O(or,
Theorem 5.2 (Poisson regression with sample corruption). Given set of datapoints S (xx, Vi Ji generated by Poisson regression model with E--fraction of label corruption and (2 With probability 0.99, Algorithm 2 with parameters 28c, 17 =² (dn), R 2 ||3*|| terminate within dn/Ež iterations, and output an estimate such that
|| - 3- Os,, exply (xxpp//ol(1/ee)))) log(1/E.))
Theorem 5.3 (Binomial regression with sample corruption). Given a set of datapoints S (x,, Ue 1a 2=1 generated by a Binomial regression model with sc-fraction of sample corruption and 22 ) With probability 1 - 5, Algorithm with parameters = Ec, 17 =. R 2 ||8*1 terminate within m/E. iterations, and output an estimate B such that
||3 3-1 log(m/Ec) log(1/Eo)
Theorem 5.4 (A class of generalized linear model with sample corruption). Let S be generated by a generalized linear model with Gauusaassin Design, with Ex-fraction of sample corruption and n 52( 22 (og(1))) Assuming that Co S 5"(() s C for non-zero constants Co. C, b(O) (0) O. and log(ely)) Oloog(((o))) Vy & @(yTog(1/e.) With probability 1 6, Algorithm 2 with parameters E.. 17 2 R do terminate within log( log(1/=<)/Et iterations, and output an estimate 3 such that
{xi, Ui ) i
| 3r log(L/E)))
The proof same compared to the label corruption setting except that since x,, E is now controlled by the adversary, we can no longer bound / Eiesne((3 B) Txxx)> x2 by the resilience property of (uncorrupted) sub-Gause Goo-Gaussiin samples. Instead, we will leverage the fact that corrupted sample with small covariance also resilient.
Conclusion
In this paper, provided a general theoretical analysis showing that simple and practical heuristic namely the iterative trimmed MLE estimator achieves minimax optimal error rates upto a logarithmic factor under adversarial corruptions for wide class of generalized linear models (GLMs). It would also be interesting to study whether our techniques can be extended to design robust algorithms for more general exponential families beyond GLMs.
References
[Ah122]
Thomas Ahle. Sharp and simple bounds for the raw moments of the binomial and poisson distributions. Statistics & Probability Letters, 182: 189300, 2022.

---

[BJK15] Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding. Advances in neural information processing systems, 28, 2015.
[BJKK17] Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar. Con- sistent robust regression. Advances in Neural Information Processing Systems, 30, 2017.
[BP21]
Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 102-115, 2021.
[CAT*20] 20] Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni, Michael I Jordan, Nicolas Flammarion, and Peter I. Bartlett. Optimal robust linear regression in nearly linear time. arXiv preprint arXiv:2007.000
2020.
[CCM13] Yudong Chen, Constantine Caramanis, and Shie Mannor. Robust sparse regression under adversarial corruption. In International Conference Machine Learning, pages 774-782. PMLR, 2013.
[CDGS20] Yu Cheng, Ilaas Diakonikolas, Rong Ge, and Mahdi Soltanolkotabi. High-dimensional robust mean estimation via gradient descent. In International Conference Machine Learning, pages 1768-1778. PMLR, 2020.
[CDK+21] Yu Cheng. Ilas Diakonikolas, Daniel M Kane, Rong Ge, Shivam Gupta, and Mahdi Soltanolkotabi. Outlier-robust sparse estimation via non-convex optimization. arXiv preprint arXiv:2109. 2021.
[CGRI5] Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance matrix estimation via matrix depth. arXiv preprint arXiv: 1e0..50666,1,1 2015.
[CKMY20] Sitan Chen, Frederic Kochler, Ankur Moitra, and Morris Yau. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. Advances in Neural Information Processing Systems, 33:8391-84033 2020.
[CKMY22] Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. Online and distribution- free robustness: Regression and contextual bandits with huber contamination. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 684-695. IEEE, 2022.
[CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47-60, 2017.
[DB18] Annette Dobson and Adrian G Barnett. An introduction to generalized linear models. Chapman and Hall/CRC, 2018
[DHL19]
Yihe Dong, Samuel Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. Advances in Neural Information Processing Systems, 32, 2019.
[DK19]
Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXhv:1911.05911. 2019.
[DKK*19 19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high- nigh-dimensions without the computational intractability. SIAM Journal Computing. 48(2):742-886 2019.
[DKP20] Ilias Diakonikolas, Daniel M Kane, and Ankit Pensia. Outlier robust mean estimation with subgaussian rates via stability. Advances in Neural Information Processing Systems, 33:1830-1840, 2020.
[DKS19] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart, Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2745-2754. SIAM, 2019.
[DKSS21] Ilias Diakonikolas, Daniel M Kane, Alistair Stewart, and Yuxin Sun. Outlier-robust learning of ising models under dobrushin's condition. In Conference Learning Theory, pages 1645-1682, PMLR, 2021.
[FXMY14] Jiashi Feng. Huan Xu, Shie Mannor, and Shuicheng Yan. Robust logistic regression and classification. Advances in neural information processing systems, 27, 2014.
10

---

[Gao20] Chao Gao. Robust regression via mutivariate regression depth. Bernoulli, 26(2):1139-
1170, 2020.
[Hubl1] Peter J Huber. Robust statistics. In International encyclopedia of statistical science, pages 1248-1251. Springer, 2011.
[JLST2I] Arun Jambulapati, Jerry Li, Tselil Schramm, and Kevin Tian. Robust regression revisited: Acceleration and improved estimation rates. Advances in Neural Information Processing Systems, 34, 2021.
[JLT20]
Arun Jambulapati, Jerry Li, and Kevin Tian. Robust sub-gaussian principal component analysis and indth-independent schatten packing. Advances in Neural Information Processing Systems, 33: 15689915701, 2020.
[KKM18] Adam Klivans, Pravesh K Kothari, and Raghu Meka. Efficient algorithms for outlier- robust regression. In Conference On Learning Theory, pages 1420-1430. PMLR, 2018.
[LRV16]
Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 20/6 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 665-674. IEEE, 2016.
[LS59]
Adrien-Maric Legendre and DE Smith. On the method of least squares. Source Book in Mathemathics, Ed. DE Smith (originally published in 1805), pages 576-579, 1959.
[LW11]
Po-Ling Loh and Martin J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. Advances in Neural Information Processing Systems, 24, 2011.
[MN19]
Peter McCullagh and John A Nelder. Generalized linear models. Routledge, 2019.
[NRWY12] Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu. A unified framework for high-dimensional analysis of m-estimators with decomposable regulariz- ers. Statistical science, 27(4):538-55 2012.
[NW72]
John Ashworth Nelder and Robert WM Wedderburn. Generalized linear models. Journal of the Royal Statistical Society: Series A (General), 135(3):370-33)) 1972.
[PJL20]
Ankit Pensia, Varun Jog, and Po-Ling Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv preprini arXiv:2009. 12976, 2020.
[PSBR18] Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint 2018.
[SBRJ19] Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, and Prateek Jain. Adaptive hard thresholding for near- optimal consistent robust regression. In Conference on Learning Theory, pages 1892228997 PMLR, 2019.
[SCV17] Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A criterion for learning the presence of arbitrary outliers. arXiv preprint arXiv:1703 04940, 2017.
[SS19a] Yanyao Shen and Sujay Sanghavi. Iterative least trimmed squares for mixed linear regression. Advances in Neural Information Processing Systems, 32, 2019.
[SS19b] Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In International Conference on Machine Learning, pages 5739-5748. PMLR, 2019.
[Tuk75]
John W Tukey. Mathematics and the picturing of data. In Proceedings of the Inter- national Congress of Mathematicians, Vancouver, 1975, volume 2, pages 523-531, 1975.
[Yat85]
Yannis G Yatracos. Rates of convergence of minimum distance estimators and kol- mogorov's entropy. The Annals of Statistics, 13(2):768-774, 1985.
[2JS19]
Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. Generalized resilience and robust statistics. arXiv preprint arXiv: /90908875, 2019.
[ZIS22]
Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. Robust estimation via generalized quasi-gradients. Information and Inference: A Journal of the IMA, 11(2):581-636, 2022.
[7721]
Ziwei Zhu and Wenjing Zhou. Taming heavy-tailed features by shrinkage. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 3268-3276. PMIR,
2021.
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] (See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "gbWCpD7lcZa", "reviewer": "Reviewer_nLxp", "summary": "The paper studies generalized linear models when a fraction of data is corrupted by an adversary. The main focus is on analyzing Trimmed Maximum Likelihood Estimator(TML), a popular estimator for this setting. TML is defined as a solution to a non-convex optimization problem and the standard off-the-shelf guarantees for convex optimization do not apply. The main contribution of the paper is to develop strong finite-time guarantees for the statistical properties of this estimator for various link functions. In particular, the results are significantly tighter than that of Bhatia et al. 2015 and 2017. The paper begins by analyzing the setting where the covariates are clean and only the labels are corrupted. Then the results are extended to the setting where the covariates may also have been corrupted.", "questions": "+ See above.\n+ The proofs in Appendix are not very clear. More critically, there are questions regarding soundness. For example, in Line 395, why is the expression upper bounded by O(1)? Should it not depend on R, which can be \\infty in this setting?", "limitations": "The paper should add potential limitations of their results.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n## Strengths\nThe main contribution is to show any approximate stationary point of TML, which can be obtained by an alternating minimization algorithm, has desirable statistical properties. This result is technically interesting and practically relevant. Thus, it would be of interest to the NeurIPS community.\n\n## Preliminary Recommendation\nI like the paper, and my preliminary recommendation is \"Accept\".  I look forward to reading the authors' response addressing the points below.\n\n## Weaknesses\nHowever, the paper needs significant improvements on several fronts mentioned below, and I look forward to reading the authors' response addressing these points.\n\n1. Related work: I feel the literature review of the current paper should include the following:\n\n\t+ (Covariate Filtering approach of [PJL20]) The paper's approach in Section 5 to handle corruptions in covariates is very similar to [PJL20]. Please include a detailed comparison. In particular, the lines 36 and 241 need to be modified.\n\n\t+ Other works in robust statistics (and ML in general) show that approximate stationary points of a non-convex problem have good statistical properties, for example, [CDGS20, CDKGGS21, ZJS20].\n\n\n2. Technically imprecise statements: I feel the writing is sloppy at times. For example, \n\t+ Line 35: trimmed MLE estimator does not achieve the minimax error rate (Error is off by a logarithmic factor).\n\t+ In the current form, the writing in Line 27 gives the impression that [33] is minmax optimal when the noises are heavy-tailed. I am not sure if that is the case.\n\t+ Line 130: It is not readily obvious to me that the results adapt to the unknown covariance setting in the label corruption model; I recommend adding explicit details and precise proofs.\n\t+ Line 96: I believe the results in [PJL20] are tighter for the Gaussian regression.\n      \n\t+ I recommend adding explicit dependence on the norm of R in the error guarantees instead of hiding it in the big-O.\n\n \n\n3. Writing:\n\t+ I liked that the paper gives a brief proof sketch of the proof of stationary points being statistically efficient. However, the proof sketch is unclear in several places. For example, \"resilience\" is not defined in the main body (the paper can use the additional space available on the 9th page). I strongly suggest improving the prose in this proof sketch in the next version because it is the main technical contribution.\n\n     + (Appendix) The Appendix in particular needs to be heavily revised. Some specific comments are below:\n         -    The proofs in Appendix are written in a very unorganized manner. It is not obvious from the beginning what statistical conditions are required from the inliers (see also the remark in the Questions section below). It is thus difficult to verify the soundness of the proofs (since there is an adaptive adversary involved, one is prone to to incorrectly claim that certain random variables are independent). I recommend reorganizing and rewriting the proofs in a coherent manner. \n         -  The proofs in Appendix are not described clearly. Majority of the text in the proofs do not give a high-level intuition of the proof strategy. For example, they are along the lines of \"Observe that\", \"it holds that\", and so on. See also the formatting on Page 15.\n\n          \n   - Furthermore, there are numerous typos in the paper.\n     + Line 78: \"proposed\"\n\t  + Line 144: \"terminates\"\n\t + Line 191: \"mmoment\"\n\t + Line 201: missing period\n\t + Line 206: \"intro\", Lemma 4.5 \n\t + Lemma 4.5, Lemma 4.6: Given \"as\".\n\t + Line 247: \"extends\"\n\t + Definition 3.1:  \"exists\" -> exist. Where is scalar $\\phi$?\n\t + Display after Line 162: There should be a parenthesis enclosing the expression before \\top.\n\n### Update\nI had forgotten to include the detailed bibliography for the references: \n\n[PJL20] A. Pensia, V. Jog, P. Loh. 2020. Robust regression with covariate filtering: Heavy tails and adversarial contamination\n\n[CDGS20] Y. Cheng, I. Diakonikolas, R. Ge, M. Soltanolkotabi. 2020. High-Dimensional Robust Mean Estimation via Gradient Descent\n\n[CDKGGS21] Y. Cheng, I. Diakonikolas, R. Ge, S. Gupta, D. Kane, M. Soltanolkotabi. 2021. Outlier-Robust Sparse Estimation via Non-Convex Optimization\n\n[ZJS20] B. Zhu, J. Jiao, J. Steinhardt. 2020. Robust estimation via generalized quasi-gradients\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "boM8c-hojP", "reviewer": "Reviewer_8oay", "summary": "This is a theoretical work studying a widely used heuristic in classification with label corruption. The algorithm of interest is trimmed maximum likelihood estimation, i.e., finding the parameters with maximum likelihood over all subsets of training data that have the same size as the clean set. The algorithm is widely used but existing theoretical guarantees only apply to Gaussian regression model. The paper proved improved and minimax near-optimal results for a broader class of generalized linear models.", "questions": "* Should there be an asumption that eps < 1?\n* In algorithm 1, |T| = (1 - 2eps) n is assigned to the new S_hat. Should it be (1-eps)n according to the description elsewhere and in [26]? This is related to my next question\n* If |S_hat| = (1 - eps)n, then how could you ensure that T\\S_hat has the same number of data points as S_hat \\intersect E? \n", "limitations": "This is pure theoretical work. The author pointed out the limitations in applying their SDP-based algorithm to covariate corruptions problems. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* The result is a clear step beyond existing work towards the theoretical understanding of a heuristic but widely used algorithm. \n* Particularly, the results improved existing constant error bounds to ~O(eps) (the minimax optimal), with a dependence on the corruption level. \n* The writing is clear. Proof sketch is appreciated. \n\n## Weaknesses\n\n* The proof relies on sub-gaussian data and its “resilience” property, which can be a strong assumption that the original data is from “nice” distribution. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IsIu4VtcQti", "reviewer": "Reviewer_B8AC", "summary": "This paper studies the theoretical properties of alternating minimization of trimmed log-likelihood loss for generalized linear models with corruption in the label space and joint space.", "questions": "The authors have remarked several limitations including sub-Gaussian covariates and a very limited assumption on the covariance for sample corruption model. On top of that, I have a couple of concerns.\n\n1. My major concern is whether the theoretical results are suspicious to be simple corollaries of existing results. First, the authors have appreciated the works [1][2] based on which a majority of their results are developed. The only difference seems to be the adopted loss, which is the negative log-likelihood, and the more general distribution, the generalized linear models. The formulation is reduced to [1] when Gaussian regression is assumed. A similar algorithm is used in [3] but not cited/discussed. I notice that Theorem 1.8 in [4] probably presents a stronger result with milder assumptions than that developed in this paper. Furthermore, Example 4 in [5] and Theorem 1.4 in [6] seem relevant but absent in references. It would be nice if a clear connection can be drawn between this work and [3][4][5][6]. \n\n2. The theoretical results may not be fundamental enough to exclude empirical results. The work could've taken advantage of the remaining 0.8 pages to demonstrate some experimental results even with a toy simulation dataset.\n\n3. Line 1 in Algorithm 1 filters out data points with large labels in terms of $\\ell_1$ norm. Does it still apply to nominal distributions? Some explanations or references will be appreciated.\n\n4. Although the paper is well-written, there are many issues in terms of grammar, tense and punctuation if one takes a closer look at it. I list a few of them found as follows.\n- Line 12, should use bold letters $\\boldsymbol{\\beta}$ for vectors for consistency.\n- Line 35, 'achieve' -> 'achieves'.\n- Line 52, 'a' -> 'an'.\n- Line 53-55, duplicate 'achieve(s)'; tenses do not match for 'improved' and 'matches'.\n- Line 70, 'Section B' -> 'Section 5'.\n- Definition 3.1, scalar $\\phi$ defined but unused.\n- Definition 3.3, comma after the statement.\n- A lot of equations and paragraphs end without punctuation.\n- Line 129, 'though' -> 'through'.\n- Line 144, 'maximize' -> 'maximizes'; 'terminate' -> 'terminates'; 'output' -> 'outputs'.\n- Line 183, 'upper bound terms of' -> 'upper bound in terms of'.\n- Line 201, period at the end.\n- Line 241, duplicate 'be/been applied'.\n- Line 247, 'extends' -> 'extended'.\n\n\nReferences:\n\n[1] Shen, Yanyao, and Sujay Sanghavi. \"Learning with bad training data via iterative trimmed loss minimization.\" In International Conference on Machine Learning, pp. 5739-5748. PMLR, 2019.\n\n[2] Chen, Sitan, Frederic Koehler, Ankur Moitra, and Morris Yau. \"Online and distribution-free robustness: Regression and contextual bandits with huber contamination.\" In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 684-695. IEEE, 2022.\n\n[3] Shen, Yanyao, and Sujay Sanghavi. \"Iterative least trimmed squares for mixed linear regression.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[4] Diakonikolas, Ilias, Daniel M. Kane, Alistair Stewart, and Yuxin Sun. \"Outlier-robust learning of ising models under dobrushin’s condition.\" In Conference on Learning Theory, pp. 1645-1682. PMLR, 2021.\n\n[5] Foster, Dylan J., and Akshay Krishnamurthy. \"Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination.\" Advances in Neural Information Processing Systems 34 (2021): 18907-18919.\n\n[6] Chen, Sitan, Frederic Koehler, Ankur Moitra, and Morris Yau. \"Classification under misspecification: Halfspaces, generalized linear models, and evolvability.\" Advances in Neural Information Processing Systems 33 (2020): 8391-8403.", "limitations": "The authors have partially addressed the limitations. Potential negative societal impact is not mentioned but unnecessary due to the theoretical nature of the work. The studied problem is interesting and results have rigorous technical proofs. If the authors can put this work  in a more clear position in the literature, I believe the paper can improve significantly.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe studied setting, as a combination of the adopted estimator, the distributional assumption and the contamination models, is novel with respect to the cited literature in the manuscript. The asserted results and technical proofs seem solid. The paper is well-written and very easy to follow.\n\nWeaknesses:\n\nAlthough the setting is novel, the claims in this paper may be trivial extensions of existing results. No empirical results are given. There are a noteworthy number of typos and grammatical issues that render it not publication-ready.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept