ReLU Regression with Massart Noise
Authors: Ilias Diakonikolas
Jongho Park
Christos Tzamos
Venue: NeurIPS 2021 Poster (2021)
Keywords: Robust learning

Abstract: We study the fundamental problem of ReLU regression, where the goal is to fit Rectified Linear Units (ReLUs) to data. This supervised learning task is efficiently solvable in the realizable setting, but is known to be computationally hard with adversarial label noise. In this work, we focus on ReLU regression in the Massart noise model,  a natural and well-studied semi-random noise model. In this model, the label of every point is generated according to a function in the class, but an adversary is allowed to change this value arbitrarily with some probability, which is {\em at most} $\eta < 1/2$. We develop an efficient algorithm that achieves exact parameter recovery in this model under mild anti-concentration assumptions on the underlying distribution. Such assumptions are necessary for exact recovery to be information-theoretically possible. We demonstrate that our algorithm significantly outperforms naive applications of $\ell_1$ and $\ell_2$ regression on both synthetic and real data.

ReLU Regression with Massart Noise
Ilaas Diakonikolas University of
Jongho Park
University Wisconsin-Madison
ilias$cs. wisc.edi
jongho. wongho.park@wwsc.... wwrkkwisc.eeeeeee edu
Christos Tzamos
University of Meaconsin-Madiseee tzamos@wisc edu
Abstract
We study the fundamental problem of ReLU regression, where the goal is to fit Rectified Linear Units (ReLUs) to data. This supervised learning task is efficiently solvable in the realizable setting, but is known to be computationally hard with adversarial label noise. In this work, we focus on ReLU regression in the Massart noise model, a natural and well-studied semi-random noise model. In this model, the label of every point is generated according to a function in the class, but an adversary is allowed to change this value arbitrarily with some probability, which is at most v) < 1/2. We develop an efficient algorithm that achieves exact parameter recovery in this model under mild unti-concentration assumptions the underlying distribution. Such assumptions are necessary for exact recovery to be information- theoretically possible. We demonstrate that our algorithm significantly outperforms naive applications & and &g regression on both synthetic and real data.
Introduction
Learning in the presence of outliers is a key challenge machine learning, with several data analysis
applications, including in ML security (4) 7
14) and in exploratory data analysis of real datasets 41 36). The goal to design computationally efficient
46
with natural outliers, e.g., in biology (43
learners that can tolerate constant fraction of outliers, independent of the dimensionality of the
data. Early work in robust statistics 288, 30) gave sample-efficien robust estimators for various basic tasks, alas with exponential runtime. recent line of work in computer science, starting with (L3 15), developed the first computationally efficient robust learning algorithms for various digh-dimensional tasks. Since these early works, there has been significant progress in algorithmic robust high-dimensional statistics by several communities, see 16) for a recent survey.
In this work, we study the problem of learning Rectified Linear Units (ReLUs) in the presence of label noise. The ReLU function ReLU Rd - R. parameterized by a vector w E Rd is defined as ReLUw (x) = ReLU(w x) max {0, w x}. ReLU regression the task of fitting ReLUs to a set labeled examples is fundamental task and an important primitive in the theory of deep learning. In recent years, ReLU regression has been extensively studied in theoretical machine learning both from the perspective of designing efficient algorithms and from the perspective of computational hardness, see, e.g., (26 45
37
48
27
15
25 18] The computational
difficulty of this problem crucially depends on the assumptions about the input data. In the realizable case, i.e., when the labels are consistent with the target function, the problem efficiently solvable, see, e.g., (45). On the other hand, in the presence of even a small constant fraction of adversarially labeled data, computational hardness results are known
for approximate recovery (2) 37) and See Section
under well-behaved distributions 27 15 25 work.
I for a detailed summary of related
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

A challenging corruption model is the adversarial label noise model, in which an adversary is allowed corrupt an arbitrary 1) < 1/2 fraction of the labels. The aforementioned hardness results rule out the existence of efficient algorithms for learning ReI.Us with optimal error guarantees in this model, even when the underlying distribution on examples Gaussian. Moreover, when no assumptions are made on the underlying data distribution, no fully polynomial time algorithm with non-trivial guarantee is possible. In fact, for the distribution- iepuutionniideeedeenn setting, even for the simpler case of learning linear functions, there are strong computational hardness results for any constant 1) 33 (9) These negative results motivate the following natural question:
Are there realistic label noise models in which efficient learning is possible without strong distributional assumptions?
Here we focus on ReLU regression in the presence of Massart (or bounded) noise (38), and provide an efficient learning algorithm with minimal distributional assumptions. In the process, we also provide an efficient noise-tolerant algorithm for the simpler case of linear regression.
The Massart model (38) is classical semi-random noise model originally defined in the context of binary classification. In this model, an adversary has control over a random yj < 1/2 fraction of the labels. Recent work (12) gave the first efficient learning algorithm for linear separators with non-trivial error gurrantees in the Massart model without distributional assumptions. In this work, ask what extent such algorithmic results possible for learning real-valued functions. To state our contributions, we formally define the following natural generalization of the model for real-valued functions.
Definition 1.1 (Learning Real-valued Functions with Massart Noise). Let F. be a concept class of real-valued functions over Ied and f I2d + R be an unknown function F. For a given parameter < 1/2, the algorithm specifies m E E and obtains m samples (x,, Vt) such that:
(a) every x; is drawn i..dd. from a fixed distribution Dx, and
(b) each y: is equal to fxx;) with probability 1 -n and takes arbitrary value with probability t/. chosen by an adversary after observing the samples drawn and the values that can be corrupted.
In the context of binary classification, the above model has been extensively studied in the theoretical ML community for the class of linear separators 2 3 51 50 20 12 (.. Even though the noise model might appear innocuous first sight, the ability of the Massart adversary to choose whether to perturb given label and, if so, with what probability (which is unknown to the learner), makes the design of efficient algorithms in this model challenging. Specifically. for distribution distribution-indeeeeeen of linear separators, even approximate learning in this model is computationally hard (17)
independent PAC learning
Extending this model to real-valued functions, we study regression under Massart noise for the realizable setting; that is, when the uncorrupted data exhibit clean functional dependencies, i.e., Vi ReLU(w* xz). The realizable setting is both of theoretical and practical interest. Prior work 45 2
GI 49) developed algorithms for learning ReLUs in this setting (without Massart noise), providing theoretical insights on the success deep learning architectures. On the practical side, there are many applications in which we observe clean functional dependencies on the uncorrupted data. For instance, clean measurements are prevalent in many signal processing applications, including medical imaging, and are at the heart of the widely popular field of compressive sensing (8)
1.1
Main Results
To build up to the more challenging case of ReLUs, we start with the simpler case of linear functions, which is in and of itself one of the most well-studied statistical tasks, with numerous applications in machine learning (44). as well as in other disciplines, including economics (1l) and biology (39).
In our Massart setting, the goal (inliers) satisfy. We show that, under the minimal (necessary) assumption that the distribution is not fully concentrated on any subspace, the problem efficiently identifiable.
identify a linear relation y w"" x that the clean samples (x, y)
Theorem 1.2 (Fxact Recovery of Linear Functions). Let Dx be distribution IRd that has zero measure on any linear subspace and let 1 < 1/2 be the upper bound on the Massart noise rate. Denote w" the vector representing the true linear function. There is an algorithm that draws
2

---

(T-2)))))
samples, runs in poly(d,b, (d (1 - 2n)) time, where b is upper bound on the bit complexity of the samples and parameters, and outputs w" with probability at least 9/ 10.
We provide a more general algorithmic result that relaxes the density assumption on Dx in Theo- rem C.3 of Appendix C so that the only assumption needed is that the support of DD spans Rd, It is important to note that if the distribution was concentrated entirely on a linear subspace, it would be information-theooveiaall impossible to determine the orthogonal component of w on that subspace. That is, our anti-concentration assumption on the distribution is necessary for identifiability to be provide
possible. Even when this assumption is violated and the problem is non-identifiable, (weaker) PAC learning guarantee for the linear case in Theorem D.I of Appendix D
Our main algorithmic result is for the problem of ReLU regression, where the inliers satisfy y = ReLU(w" x) and an 1) < 1/2 fraction of the labels are corrupted by Massart noise. Even in this more challenging case, we show it is possible to efficiently identify the true parameters w", long as every homogeneous halfspace contains a non-negligible fraction of the sample points.
Theorem 1.3 (Exact Recovery of ReLUs), Let Dx be a distribution on R that has zero measure
on any linear subspace and such that PIx~D_lW. x 2 0] 2 X for any w E Rd. Let nj < <1/2 be the upper bound on the Massart noise rate. Denote w the parameter vector of the target ReLU
There is an algorithm that draws Ö( x2x01120 22)]2 samples, runs in time poly(d,b, b,,,, (1- 27) ")
de
and outputs w with probability at least 9/10.
We similarly provide a more general result relaxing the density assumption on Dx in Theorem C.4 of Appendix We note that the assumption on the mass of halfspaces in Theorem 1.3 is necessary for identifiability. Indeed, if there was a halfspace, parameterized by w E R such that Prx-D,, / [w-x 0) O, it would be impossible to distinguish between the functions ReLU(( x) and ReI.U(2w x) (even without noise), as all points would have 0 labels. remains an interesting open problem whether similar PAC learning guarantees be obtained for the case of ReLU regression. We suspect that this problem is computationally hard in full generality.
C
1.2 Technical Overview
As explained in the introduction, the focus of our work is on the problem of robust regression in the presence of outliers. When 1) < 2/2 fraction of the data is arbitrarily corrupted in the realizable setting, the goal is to compute the function that fits as many as points (inliers) as possible. Given a sufficient number of samples from a hull-dimessional distribution, this function is unique for the class of ReLUs and matches the true function with high probability. However, even in the simpler case of linear functions, the corresponding computational problem of by fo-minimization is computationally hard without distributional assumptions, as it is an instance of robust subspace recovery (2)).
Our positive results are driven by relaxing the assumption that arbitrary fraction of the points is corrupted. Instead, as defined in Definition [.] we consider a more restricted adversary that is presented with uniformly random yj fraction of the points, which can be corrupted arbitrarily will.
to to l minimization Given this milder corruption model, we propose novel algorithms for efficient exact recovery of the underlying function. We obtain our algorithms by replacing the ly- f6-minimization with é (-minimmization, which can be shown to converge to the true function in the limit and is efficient to optimize the linear regression case. For intuition, consider a single-point distribution that always outputs labeled examples of the form (x, v). where the example x is always the same but the labels may differ. The Massart assumption indicates that the value of y is correct more than half of the time, so the estimate that maximizes the number of correct samples (Eo -iniiiiiizer) recovers the underlying function. However, if one considers the f miiinimizer, i.c., the value e that minimizes Elly - vI]. this corresponds to the median value of y which is also correct if more than half samples are correct.
We generalize this intuition and propose a natural and tight condition under which empirical &1- minimization results in the true fo-minimizer (see Lemma 2.2h. While this condition holds under Massart noise for arbitrary distributions in the population level, it can fail to hold with high probability when considering only finite set of samples from the distribution. For example, consider the one- dimensional case of w where most x, 's are near-zero and uncorrupted, while a few corrupted samples lie extremely far from zero. The empirical ε miiiimiierr here will be dominated by the few
3

---

corrupted samples and would not be the fo-minimizer. In particular, the sample complexity of naive & (-minimization would crucially depend on the concentration properties of the distribution on x.
Transforming the points via radial-isotropy The main technical idea behind obtaining sample- efficient algorithms that run in polynomial time to transform the original point set into an equivalent one that satisfies the required properties with high probability, as it becomes sufficiently concentrated. In particular, performing linear transformation mapping every point x Ax, while keeping the corresponding label y, is without loss of generality, we are interested in identifying the true (generalized) linear function that depends only on the inner product of every point with a parameter vector w. Finding such vector w' in the transformed space Ax results in the equivalent vector w = w' in the original space. Moreover, an additional operation we can perform is to take a single sample (x, y) and multiply it by a positive scalar À 0 to replace it with the sample (Ax, Xy). For both the linear and ReLU cases, any sample that is an inlier for the true function remains an inlier after this transformation.
We can use these two operations to bring our point set in radial-isotropic position, i.e., so that all the x's in the dataset are unit-norm and the variance in any direction is nearly identical:
Definition 1.4 (Radial Isotropy). Let S be the unit sphere in R. Given {x1...., .,)) C Sd-1
A Rd + Rd is a oudial-isotropp transformation if Ei= (Ax:)Axx)*
I. For 0 < y < 1,
||Ax.
we say the points are in appproxiimate radial- vadial--sotropic position, for all v E Sa-1, it holds that (d/n) Ex=((x; v) 21-7
In such a normalized position, we can argue that with high probability the weight of all inliers in every direction is more than the weight of the outliers, which guarantees that the empirical E f--minimizer will converge to the true function.
Learning ReLUs Unfortunately, while f1-minimization for linear functions is convex and ef- ficiently solvable via linear programming. é --minimizztiion for ReLUs is challenging due to its non-convexity; that is, we cannot easily reduce ReLU regression to a simple optimization method. We instead establish structural condition under which we can compute an efficient separation oracle between the optimal parameter vector w and query w. More specifically, we show that any suboptimal guess for the parameter vector w can be improved by moving along the opposite direction of the gradient of the fllloss for the subset of points in which the condition in Lemma B.1 is satisfied. Identifying such a direction of improvement yields a separating hyperplane, so we exploit this to efficiently identify w' by running the ellipsoid method with our separation oracle.
However, for this result hold with a small number of samples, we need to again bring to radial- isotropic position the points that fall in the linear (positive) part of the ReLU for the current guess vector w. In contrast to the linear case, though, where this transformation was applied once, this case it needs to be applied again with every new guess. This results in a function that changes at every step, which is not suitable for direct optimization.
Using these ideas, our algorithms can efficiently recover the underlying function exactly using few samples. Our algorithms make mild genericity assumptions about the position of the points, requiring that the points are not concentrated on a lower-dimensional subspace or, for the case of ReLUs, do not lie entirely in an origin-centered halfspace. As already mentioned, such assumptions are necessary for the purposes of identifiability.
1.3 Related Work
Given the extensive literature on robust regression, here we discuss the most relevant prior work.
ReLU Regression In the realizable setting. 45) and, more recently. 3i showed that gradient descent efficiently performs exact recovery for ReLU regression under the Gaussian distribution on examples. (49) generalized this result to a broader family of well-behaved distributions. In the agnostic or adversarial label noise model, a line of work has shown that learning with near-optimal error guarantees requires super-polynomial time, even under the Gaussian distribution 27 15 25 18).
On the positive side, (TI gave an efficient learner with approximation guarantees under log-concave distributions. Without distributional assumptions, even approximate learning is hard 20 37).

---

The recent work (2) studies ReLU regression in the realizable setting under noise model similar to but more restrictive than the Massart model of Definition I.I Specifically, in the setting of (32). the adversary can corrupt a label with probability at most 1). but only via additive noise bounded above by a constant. (32) gives an SGD-type algorithm for ReI.U regression in this model, We note that their algorithm does not achieve exact recovery and its guarantees crucially depend on the concentration properties the marginal distribution and the bound on the additive noise.
Comparison of Noise models It is worth comparing the Massart noise model (Definition L.1 with other noise models studied in the literature. The strongest corruption model we are aware of the strong contamination model (33, in which an omniscient adversary can corrupt an arbitrary 1/2 fraction of the labeled examples. In the adversarial label noise model, the adversary can corrupt an arbitrary 7) 1/2 fraction of the labels (but not the examples). Efficient robust learning algorithms in these models typically only give approximate error guarantees and require strong distributional assumptions. Specifically, for the case of linear regression, (34 14 give robust approximate learners in the strong contamination model under the Gaussian distribution and, more broadly, distributions with bounded moments. In the adversarial label noise model, (6) gave efficient robust learners under strong concentration bounds on the underlying distribution that can tolerate ? 1/50 fraction of outliers.
The recent work (1O) considers a Massart-like noise model in the context of linear regression with random observation noise. (TO) provides an SDP-based approximate recovery algorithm when the noise rate satisfies < 1/3. It should be noted their algorithm does not efficiently achieve exact recovery. Due to space limitations, we provide a more detailed description of that work in Appendix
related noise model is that of oblivious label noise, where the adversary can corrupt an fraction of the labels with additive noise that is independent of the covariate More precisely, the oblivious adversary corrupts the vector of labels y E IR' by adding a rjm--parse corruption vector b. Since b is independent of the covariates, oblivious noise be viewed corrupting sample with probability with a random non-zero entry of b. Consequently, oblivious noise can be seen as a special case of Massart noise. We formally compare these two noise models in more detail in Appendix A line of work ( 47 22 42) studied robust linear regression under oblivious noise and developed efficient exact recovery algorithms under strong distributional assumptions.
Warmup: Linear Regression with Massart Noise
In this section, we establish structural conditions under which we can perform efficient lo- minimization for linear functions under Massart noise, is imperative that we find the tu fo-minimizer with respect to w since, with a sufficient number of samples, the Ly- fo-minimizer is the true function we wish to recover. We then show that appropriately transforming the data via rasiao-isotropic transformation and then solving for the empirical E lloss arg wen m -i efficiently recover the true parameter w*. We describe the algorithm for recovering linear functions below.
Σm [ w x, can
Algorithm 1 Linear function recovery via radial isotropy
Draw m Ö (1))))) samples (xi, Ui y with MaMMsst noise Compute A that puts (x,, M) in 1/2-approximate radial-isotropic position 1
W + arg min Em [Ax.]I2 w
Axi by solving the LP
Ax.
return Aw
In fact, there is no need to compute exact radial-isotropic transformation (7 0) as approximate one suffices. An approximate radial-isotropic transformation can be computed efficiently as in Lemma 2. which we prove in Appendix A
Lemma 2.1. Given S IRd in general position, there is a poly (n, d, 11) time algorithm that
computes positive definite symmetric matrix A such that { [TAXT x S in "-approximate cadial-isotrape position where is an upper bound on the bit complexity of the parameters and samples in S. Morever, the condition number of A is at most ppoly(n.d.b)
5

---

Given that computing such approximate transformation A and solving a linear program (LP) can be done efficiently, Algorithm gives us the polynomial runtime for Theorem
The proof of Theorem 1.2 relies on two key ideas. First, we can minimize the empirical 4osss with respect to instead of the fo-loss because the two are equivalent under the structural condition of Lemma 2 Once the following sufficient condition is satisfied, we can efficiently solve for l e--minimization as this is efficient in the case of linear functions by solving an LP.
Lemma 2.2 (Structural Condition for Recovery). Given f R. - IR. and m samples (x4, Ui) in Rd, let the fo-minimizer w' arg min 1 EE 1i f(w xs)llo be unique. If
Σ
If((w" +r) f(w" xx,) Σ [f(( + +))) f(w" xt)l (*)
y1 f(w x.)
B f(w""w"> x.)
for all non-zero r E IRd, then w is also the f1-minimizer arg wind m E 18t h(xx)l
The structural condition points be greater than the sum of |x for the "bad" points in every direction r. However, this implies that if one sample is much greater in norm than the others in some direction, this point can have undue influence and may easily dominate the fı-loss. Therefore, without any preprocessing or transformation to the data, one has to rely on naively increasing the sample complexity until there are enough points in this direction to satisfy condition of such outlier points and reduce the sample complexity through transforming the dataset with radial isotropy. We defer the proof of Lemma 2.2 and Theorem 1.2 to Appendix A
for linear functions reduces to having the sum of | x,| for the "good"
Instead, we minimize the dominating effects
3 ReLU Regression with Massart Noise
In this subsection, we study the problem of exact recovery for ReLUs in the presence of Massart noise. For the case of ReLUs, we can still use the structural condition of Lemma 2.2 to do f1- minimization arg minw 1 Σ 18: ReLU(w-- x.)]- However, minimizing this objective is no longer straightforward, because the objective function is non-convex. Despite this fact, it is possible to exactly recover ReLU under mild anti-concentration assumptions on the underlying distribution.
The key idea behind Theorem 1.3 is establishing the condition under which we can compute an efficient separation oracle between the query w and the true parameter w". Once we obtain a separation oracle, we can use the ellipsoid method to recover w exactly. In turn, similarly to Lemma we identify a sufficient structural condition on the dataset, which allows us to efficiently compute a separating hyperplane between w and w w A w", and then use radial-isotropic transformations such that this condition is satisfied. We state this separation condition in the following lemma.
2.2
Lemma 3.1 (Separation Condition). Let H be an hypothesis class such that H = {ho hw f(w - x). w E Rd) where f IR- + R is monotonically nonddecraasing. Given a set of m samples (Xa, yo let w arg min m E 11y, f(w xx)llo be unique. Let A > 0 and B B(w, A)
be the open ball of radius A centered at w. Denote the empirical & fo-loss L(w) = (1/m) Em 19: f(w x.)l. Given a query wo & B(w*, A). if
Σ
l(wo-
xxl x.) V (()
Σ
(wo - w") x1 (wo x,) 2 Am
then V Vi(w))= (Wo- w) = 0 is a separating hyperplane for wo and B(w", A/2) such that vi(wo) (wo- w) > for w
In particular, the gradient of the empirical fı-loss gives us the separating hyperplane above. Other than the fact that only the points in the non-negative side of the halfspace of w are considered in the separation condition f the condition resembles much of the structural condition used for linear functions. Analogously, we apply a radial-isotropic transformation to the points of w Xx > 0. Thus, we have the following sub- sub-procede proccduree of the ellipsoid method where A is the radius of a ball which depends the distance between the points (and hence the bit complexity b).
The main difference between the algorithm for ReLUs and linear functions that here we must apply a different radial-isotropic transformation to every new subset of points in every iteration, depending on the query Wo. turn, the algorithm transforms the space according a new transformation A and computes a separating hyperplanc and transforms the hyperplane back into the original space. Due to

---

Algorithm 2 Separation oracle sub-procedure
Input: (Xi, 34 3t) with Massart noise, query Wo. A
Output: Unless Wo E [3ww., ,A), a separating hyperplane between wo and "(ww,A/2) if ReLUUww x) fits at least points then
return Wo as true parameter w*
S {(x;, Wt) Wo x; 2 0 for i [m]}
Compute A that puts Sx into 1/2-approximate radial-isotropic position
Ax: r + [S] [x..v.)s |x: sggn Wo X; - y/))
(wo
return separating hyperplane A A-rr. (wo- w)
these repeated transformations, the proof of Theorem 1.3 requires more intricate argument to make the ellipsoid method work correctly. We now prove Theorem
Proof of Theorem 1.3 Let Wo be the original query to the oracle and assume the separation condition
① holds for a set of points (Ax,/ / Ax. 1 3t/ Axx/| [|2) and A 'wo- Then, by Lemma 3.1
r-(A- -w w) 0 where r = (1/m) i= (Ax,/ |xx 11) .sgn() Wo X; y/) separates A Wo
and A- w" Thus the separation for wo and w is A -ir- (Wo w) 0.
Now it remains to check the sample complexity necessary for the separation condition i EEach unique set of {(x,, yi) : Wo x, 2 0 for i E [m]] determines a radial isotropic transformation but there can only be at most m m=+1 unique sets by the VC dimension of halfspaces. So there only most md+1 radial-isotropic transformations we have consider. Let A be the linear transformation of the radial-isotropic transformation applied to points of wo X; 2 0. Denote (R;, 0s) = (Ax:/ Ax:112, / w = A -' -ww", Wo = A -wa, and let Dx be Dxl(wox20)) transformed by A then normalized so that Dx lies on S6-1, Then, for all md*1 transformations, have the following VC inequality using Odde²² samples with high probability:
sup Pr [l(w - ww) x x ス
0, y ReLU(W" x)) t|
wERd
&nDx
- (1/m))
Σ 1 [ w") x t, x 0, y ReLU(w" xx,)| sc.
Let S = (Xx, Rt) Wo x; 2 0}. Similarly to the proof of Theorem 1.2
we have that mxx(x.)) Ir-
x| S T-y-ed E Ex
(ل=ا)
Da || x|] where 7 = 1/2. Then, we can write
(1/1S)) Σ I(wo- w*) x (y: = ReT.U(w" .x))
ES
(000 poc
= (m/|S])
((1/m) Σ 1 (wo - w²) x > 1 Wo 8; 2,20 0, y1 = RReLU(w* xx))
=1
2 RE, ll w²) x|1| {u- = ReI.U(w* x)} (em/lS))
max (x.0)SS
I(wo - w") x
2 (1 - 17) EB, [l - w x|| (emd/ ([ - 2ed)) ) (wo w') x|]
By setting = Ō(1(1 2n)) /d), we can bound m/|S] be at most constant times A for all md+1 possible subsets S using Hoeffding's ' inequality and the union bound. Then we have
(1/1S))
Σ (wu- w 1 ReLU(W* xx) ((1/2) (1-2))))111)4441)) 22) [l w').x(] (K.D)
We can do the same to the corrupted points in S getting < (1/22 (1 - 24) II(w w*) x|]. Thus, for points (x, D) E S, we have the condition
(1/1S))
Σ
(wo- w*) -x]
Σ
(wo w') x1) 2 (1/2 - I| w') xl]
G=ReLU(W's.
( *))
M (1/2 - n) wo w'lle/d.
7

---

By Lemma 3.1 the inequality above implies that we can find a hyperplane of r that separates Wo and B(w", 2/2) where Á transformed hyperplane of A ''r seperates wo and B(w", A/2) where A = 2d
1 2n Ww w In the original space of (x,, Vi Bi)
we have that the
2d
1-2n
Wo Amiin
Amax (A)
w*ll2 since applying A -1 1 to keeps the distance from w to Wo at least 2ddhmax (A]
1-2n
Wo w "11 and
applying A to w" bounds the distance from w" to Wo to be at least A. Therefore, we can set of 1-2n Amtn w -w
Algorithm 2 to be equal to millwww
22"
If * w", by bounded bit complexity b, we have that the volume of the ellipsoid decreases at every step but the ball of radius (mmn (A) will always be contained in it. Thus the algorithm terminates
4d)mmx (A)
in poly(d, (d, b, (1 - 22n)=1 iterations since log
Amaze (A) Aania (A)
poly (d, b, (1 2n)-
4 Experiments
In this section, we apply our algorithms that are based on radial-isotropic transformations to both synthetic and real datasets and compare robustness in regression with other baseline methods of & and fzrregrssioon. Our experiments demonstrate the efficacy of radial-isotropic transformations in robust regression and how our algorithms outperform baseline regression methods.
All experiments were done on a laptop computer with a 2.3 GHz Dual-Core Intel Core i5 CPU and 8 GB of RAM. We ran CVXPY's linear program solver for & rregressio for linear functions.
Recovering Linear Functions We first show how our algorithm based on radial-isotropic position (Algorithm D compares to naive { regression in exact recovery using an LP solver. As another baseline, we also ran erregression with a normalization preprocessing step, where we normalize all y ). We did not run regression with an isotropic- isotropic-transfommiae transformation preprocessing points (x. y) to ( |||]] ||=]|
step because this yields identical results naive regression with preprocessing.
We evaluated different transformations the data on the following synthetic distribution. Define a mixture of Gaussians Dx = [ + I2) + 2d
1 Ei ((de;, /े la), where e, denotes the i-th
standard basis vector and d = 30. Let w 9c2
Σ ii=1 C₁. For various noise levels n), consider the following -Massart adversary: the labels for all x for which any coordinate is greater than & are flipped to -w" x with probability 17, and the labels for all other points are not flipped. Essentially, only the points not from N(e1, la) are affected by Massart noise.
We measured exact parameter recovery rate, which captures how often the algorithm solves for w exactly. We varied the noise rate 7) while running the methods with 120 samples from Dx. We also varied the sample size while keeping the noise 7) = 0.25. We ran 200 trials for each measurement of exact recovery rate and the error bars represent two standard deviations from the mean.
Recovering ReLUs For ReLUs, used the same distribution the experiments for linear functions to generate samples. We ran and compared constant-step-sized gradient descent on the empirical -lsss n gradient descent since our separation oracle for the Ellipsoid method bears similarities with gradient descent. As seen in Lemma 3.1 this is due the fact that our separating hyperplane based on the gradient of the empirical & loss of a subset of points.
1 >x= 1y; -ReLU(w* xx)) with different transformations the data. We ran
The experiment is set up with 17 = 0.4, w 9e2 + Ei e,, Wo = 0, 240 samples from Dx, and gradient descent step size of one. For 'Original', we use step size of 1/465 to keep the magnitude of the points X; comparable to that of the transformed points X,
In Figure 2 a), 'Original' corresponds to naive gradient descent, while 'Normalized" has normal- ization preprocessing step. The transformations of 'Isotropic' and 'Radial-isotropic" follow our algorithm for ReLUS from Section where the transformation is only applied to the positive-side points of w.x; 2 0 for the current hypothesis w. The gradient is then calculated with the transformed points X; and appropriately transformed back to the original space in order update The gradient descent updates under transformation A and step size a is the following:
w'< f A W then
(AV L')
8

---

Radial-ssctrppc
0.8
Original
0.8
Exatt Recovers Rate
Sract Deccovery Rata
0.6
0.6
Radeo--setropcc
Normal lod
0.4
0.0
0.0
0.0
0.1
0.2
0.3
0.4
100
200
300
400
500
600
Noise
Sample Size
(a) Recovering Linear (vs. noise rate)
(h) Recovering Linear (vs. sample size)
Figure 1: Experiments for exact parameter recovery of linear functions on synthetic data. Exact recovery rate (y-axis) measures how often the algorithm outputs the true parameter out of 200 trials. We compare Algorithm D with naive éi-miimmization and fi-minimization with normalized data. Error bars cover standard deviations from the mean.
Fraction covered sutspacce with margin
12
Ridge
0.8
10
Rescaled
0.6
Distance to
0.4
-sstrocc Normelized
0.2
Original
0.0
200
800
Steos
loga(]
2
Gradient Descent ReLU
(b) Drug Discovery Dataset
Figure 2: On the left, we compare the performance of different transformations with gradient descent on synthetic data where we measure the é di-iittaece to the optimal solution. On the right, we compare different regression methods applied real data where the labels are artificially corrupted with 7-Massart noise. Rescaled LI represents Algorithm [ We report the fraction of points that lie in the subspace generated by its output with margin.
points. This update method is where L/ denotes the empirical -loss for the transformed subset of directly adapted from our Ellipsoid method.
Drug Discovery Dataset The drug discovery dataset originally curated by (40) and used the same dataset as the one used (14). The dataset has a training and test set of 3084 and 1000 points of 410 dimensions. The Massart noise adversary corrupts the training data (x,, ys) so that all points are corrupted to flip labels to - 100y, with probability
We compared 4 regrrsssion with radial-isotropic transformation ('Rescaled LI') to other baseline methods, such as least squares and naive fr-regression. For ridge regression, we optimized the regularization coefficient based the uncorrupted data. We measure performance by computing the fraction the test set that lies within the subspace generated by the output vector with a margin of
Results In Figure I our algorithm with radial-isotropp transformation outperforms other baseline methods in robustness with respect to the noise level and in efficiency with respect to the sample size. This is in line with the results of Theorem 1.2 In fact, our experiments on ReLUs also empirically demonstrate that radial isotropy significantly improves ReLU regression gradient descent by making the dataset more robust noise each iteration. For the drug discovery dataset, although

---

& (--regressoon with radial isotropy performs slightly worse than naive & é1-regression when there is minimal noise, significantly outperforms the baseline methods at regimes of high noise levels.
5 Conclusion
In this work, we propose a generalization of the Massart (or bounded) noise model, previously studied in binary classification, to the real-valued setting. The Massart model a realistic semi-rane cemi-random noise model that is stronger than uniform random noise or oblivious noise, but weaker than adversarial label noise. Our main result is an efficient algorithm for ReL.U regression (and, in the process, also linear regression) in this model under minimal distributional assumptions. At the technical level, we provide structural conditions for fo-minimization to be efficiently computable. A key conceptual idea enabling our efficient algorithms is that of transforming the dataset using radial-isotropic transformations. We empirically validated the effectiveness of radial-isotropic transformations for robustness via experiments both synthetic and real data. In contrast to previous works on robust regression that require strong distributional assumptions, our framework and results may be seen as an intricate balance between slightly weakening the noise model yet affording generality in the underlying distribution.
Acknowledgments and Disclosure of Funding
Ilias Diakonikolas is supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CAREER), a Sloan Research Fellowship, and a DARPA Learning with Less Labels (LwLL) grant.
References
[1] ARTSTEIN-AVIDAN, S., KAPLAN, H., AND SHARIR, M. On radial isotropic position: Theory and algorithms. arXiv preprini 2xXi:20005.04188 (2020).
[2] AWASTHI, P., BALCAN, M. F., HAGHTALAB, N., AND URNER, R. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015 (2015), pp. 167-190.
[3] AWASTHI, P., BALCAN, M. F., HAGHTALAB, N., AND ZHANG, H. Learning and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Conference Learning Theory, COLT 2016 (2016), pp. 152-192.
[4] BARRENO, M., NELSON, B., JOSEPH, A. D., AND TYGAR, J. D. The security of machine learning. Machine Learning 81, 2 (2010), 121-148.
[5] BHATIA, K., JAIN, P., KAMALARUBAN, P., AND KAR, P. Consistent robust regression. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 (2017), pp. 2107-2116.
[6] BHATIA, K., JAIN, P., AND KAR, P. Robust regression via hard thresholding. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015 (2015), pp. 721-729.
[7] BIGGIO, B., NELSON, B., AND LASKOV, P. Poisoning attacks against support vector machines. In Proceedings of the 29th International Conference Machine Learning, ICML 2012 (2012).
[8] CANDÈS, E. J., AND WAKIN, M. B. An introduction to compressive sampling. IEEE signal processing magazine 25, 2 (2008), 21-30.
[9] CHEN, S., KOEHI.RR, F., MOITRA, A., AND YAU, M. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020 (2020).
[10] CHEN, S., KOFHLER, F., MOITRA, A., AND YAU, M. Online and distribution-fred robustness: Regression and contextual bandits with huber contamination. arXiv preprint 15X:v:2010.04157 (2020).
10

---

[11] DIAKONIKOLAS, I., GOEL. S., KARMALKAR. S., KLIVANS, A. R., AND SOLTANOLKOTABI, M. Approximation schemes for relu regression. In Conference on Learning Theory, COLT 2020 (2020), vol. 125 of Proceedings of Machine Learning Research, PMLR, pp. 1452-1485.
[12] DIAKONIKOLAS, I., GOULEAKIS, T., AND TZAMOS, C. Distribution-indeeeneen pac learning of halfspaces with massart noise. In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, Eds. Curran Associates, Inc., 2019, pp. 4751-4762
[13] DIAKONIKOLAS, I., KAMATH, G., KANE, D. M., LI, J., MOITRA, A., AND STEWART, A. Robust estimators in high dimensions without the computational intractability. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS) (2016), pp. 655 6654.4
[14] DIAKONIKOLAS, I., KAMATH, G., KANE, D. M., J., STEINHARDT, AND STEWART,
A. SEVER: A robust meta-algorithm for stochastic optimization. In Proc. 36th International Conference on Machine Learning (ICML) (2019), pp. 1596-1606.
[15] DIAKONIKOLAS, I., KANE, D., AND N.ZARIFIS. Near-optimal SQ lower bounds for agnosti- cally learning hallipacces and relus under gaussian marginals. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020 (2020).
[16] DIAKONIKOLAS, I., AND KANE, D. M. Recent advances in algorithmic high-dimensional robust statistics. CoRR abs/19/ I. /.059// (2019).
[17] DIAKONTKOLAS, I., AND KANE, D. M. Hardness of learning halfspaces with massart noise. CoRR abs/2012.09720 (2020).
[18] DIAKONIKOLAS, I., KANE, D. M., PITTAS, T., AND ZARIFIS, N. The optimality of polyno- mial regression for agnostic learning under gaussian marginals. CoRR abs/2102.04400. (2021). To appear in COLT 2021.
[19] DIAKONIKOLAS, I., KONG, W., AND STEWART, A. Efficient algorithms and lower bounds for robust linear regression. In Proc. 30th Annual Symposium on Discrete Algorithms (SODA) (2019), pp. 2745-2754.
[20] DIAKONIKOLAS, I., KONTONIS, V., TZAMOS, C., AND ZARIFIS, N. Learning halfspaces with massart noise under structured distributions. Conference on Learning Theory, COLT 2020 (2020), J. D. Abernethy and S. Agarwal, Eds., vol. 125 of Proceedings of Machine Learning Research, PMLR, pp. 1486-1513.
[21] DIELMAN,
Applied Regression Analysis for Business and Economics. Duxbury/Thomson Learning Pacific Grove, CA, 2001.
[22] D' D'ORSI, T., NOVTKOV, G., AND STEURER, D. Regress consistently when oblivious outliers overwhelm. arXiv preprint arXiv:2009. TETV:2009.117744 (2020).
[23] DU, S. S., LEE, D., AND TIAN, Y. When is a convolutional filter easy to learn? In 6th International Conference Learning Representations, ICLR 2018 (2018).
[24] DUNAGAN, J., AND VEMPALA, S. Optimal outlier removal in high-dimensional spaces. J. Computer & System Sciences 68, (2004), 335-373.
[25] GOEL, S., GOLLAKOTA, A., AND KLIVANS, A. R. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020 (2020).
[26] GOEL, S., KANADE, V., KLIVANS, A., AND THALER, J. Reliably learning the relu in polynomial time. In Conference on Learning Theory (2017), pp. 1004-1042.
[27] GOEL, S., KARMALKAR, S., AND KLIVANS, A. R. Time/aceuracy tradeoff' for learning a relu with respect to gaussian marginals. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019 (2019),
pp. 8582-8591.

---

[28] HAMPEL, F. R., RONCHETTI, E. M., ROUSSEEUW, P. J., AND STAHEL, W. A. Robust statistics. The approach based on inffuence functions. Wiley New York. 1986.
[29] HARDT, M., AND MOITRA, A. Algorithms and hardness for robust subspace recovery. In Proc. 26th Annual Conference on Learning Theory (COLT) (2013), pp. 354 375.
[30] HUBER, J., AND RONCHETTI, E. M. Robust statistics. Wiley New York, 2009.
[31] KALAN, S. M. M., SOLTANOLKOTABI, M., AND AVESTIMEHR, S. Fitting relus via sgd and quantized sgd. In 2019 IEEE International Symposium Information Theory (ISIT) (2019),
IEEE, pp. 2469-2473.
[32] KARMAKAR, S., MUKHERJEE, A., AND MUTHUKUMAR, R. A study of neural training with iterative non-gradient methods. arXiv e-prints (2020), arXiv-2005.
[33] KHACHIYAN, L. On the complexity of approximating extremal determinants matrices. Journal of Complexity 11, (1995), 133-153.
[34] KLIVANS, A., KOTHARI, P., AND MEKA, R. Efficient algorithms for outlier-robust regression. In Proc. 31st Annual Conference on Learning Theory (COLT) (2018), pp. 1420-1430.
[35] LAI, K. A., RAO, A. B., AND VEMPALA, S. Agnostic estimation of mean and covariance. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS) (2016), pp. 663-674.
[36] LI, J., ABSHER, D., TANG, H., SOUTHWICK, A., CASTO, A., RAMACHANDRAN, S., CANN, H., BARSH,, G., FELDMAN, M., CAVALLI-SFORZA, L., AND MYERS, R. Worldwide human relationships inferred from genome-wide patterns of variation. Science 319 (2008), 100-1104.
[37] MANURANGSI, P., AND REICHMAN, D. The computational complexity of training relu (s). arXiv preprint arXiv: 1810.04207 (2018).
[38] MASSART, P., AND NEDELEC, E. Risk bounds for statistical learning. Ann. Statist. 34, 5 (10 2006), 2326-2366.
[39] MCDONALD, J. H. Handbook of Biological Statistics, volume 2. Sparky House Publishing, Baltimore, MD, 2009.
[40] OLIER, I., SADAWI, N., BICKERTON, G. R., VANSCHOREN, J., GROSAN, C., SOLDATOVA, L., AND KING, R. D. Meta-qsar: a large-scale application of meta-learning to drug design and discovery. Machine Learning 107, (2018), 285-311.
[41] PASCHOU, P., LEWIS, J., JAVED, A., AND DRINEAS, P. Ancestry informative markers for fine-scale individual assignment to worldwide populations. Journal of Medical Genetics 47 (2010), 335-847.
[42] PESME, S., AND FLAMMARION, N. Online robust regression via SGD on the 11 loss. In Ad- vances in Neural Information Processing Systems 33; Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020 (2020).
[43] ROSENBERG, N., PRITCHARD, J., WEBER, J., CANN, H., KIDD, K., ZIIYOTOVSKY, L., AND FELDMAN, M. Genetic structure of human populations. Science 298 (2002), 2381-2385.
[44] ROUSSEEUW, P. J., AND LEROY, A. M. Robust Regression and Outlier Detection. John Wiley & Sons, Inc., New York, NY, USA, 1987.
[45] SOLTANOLKOTABI, M. Learning relus via gradient descent. In Advances neural information processing systems (2017), pp. 2007-2017.
[46] STEINHARDT, J., KOH, P. W., AND LIANG, P. S. Certified defenses for data poisoning attacks. In Advances in Neural Information Processing Systems 30 (2017), pp. 3520-3532.
[47] SUGGALA, A. S., BHATIA, K., RAVIKUMAR, P., AND JAIN, P. Adaptive hard thresholding for near-optimal consistent robust regression. In Conference on Learning Theory, COLT 2019 (2019), pp. 2892-2897.
12

---

[48] YEHUDAI, G., AND SHAMIR, O. On the power and limitations of random features for understanding neural networks. CoRR abs/I904.0060 (2019).
[49] YEHIDDI, G., AND SHAMIR, O. Learning single neuron with gradient methods. In Conference Learning Theory (2020), PMLR, pp. 3756-3786.
[50] ZHANG, C., SHEN, J., AND AWASTHI, P. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020 (2020).
[51] ZHANG, Y., LIANG, P., AND CHARIKAR, M. A hitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017 (2017), pp. 1980-2022.
13


Reviews:
[{"review_id": "VohWkYfl8yd", "reviewer": "Reviewer_Dpt6", "summary": "The paper considers the problem of linear and ReLu regression in the Massart noise model, where an adversary is allowed to change the label to an arbitrarily value with some probability at most $\\eta <1/2$. The work develops an efficient algorithm that achieves exact parameter recovery in this model under mild assumptions on the underlying distribution. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Quality and Clarity**: \n\n-  One of the strong points if the paper is that it is very well-written and well organized. The ideas are presented clearly with intuitive explanations, and the proofs are rigorous. \n\n- The authors are careful in evaluating the strengths/weaknesses of their work. The work seems to be built upon an established literature and the review of related works are informative. \n\n- Minor comments: \n  - Definition 1.1: \"and after inspecting which samples can be corrupted, it may change the label to an arbitrary value\" --> I interpreted this as \"change each label to an arbitrary value\" or \"change the labels to arbitrary values\". Please clarify.\n  - bit complexity of the parameters and samples: this is mentioned a few time but are not defined\n  - the sentence starting at Line 140 is very difficult to read\n\n**Originality**: \n\n-  The paper consider a slightly weakened model (in comparison to the the contamination model), but leads to more generality in the underlying data distribution.\n\n- The result of the work is significantly different (stronger) from the closest comparisons ([32] and [10]), and the methods are designed specifically to address the limitation of those works.\n\n- The generalization of the approach from linear to ReLU regressions are non-trivial in both technical analysis and algorithmic designs. \n\n\n**Significance**:\n\n- As stated in the Originality section, the result of the work is significantly different (stronger) from the closest comparisons ([32] and [10]) and seems to extend existing works in a demonstrable way.\n\n- On the other hand, I'm unfamiliar with some pieces of related work and don't have a strong conviction in how it will impact the field, and would leave the judgement up to other reviewers. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6KEmTiPc2J", "reviewer": "Reviewer_vpXo", "summary": "The aim of this work is to propose a computationally efficient algorithm for linear and ReLU regression in the presence of a bounded adversarial Massart noise model. It has been tried to make the assumptions on the underlying data distribution as mild as possible, not to mention that (as claimed by the author(s)) some assumptions are necessary from an information-theoretic point of view.\n\nThe core idea is to consider the unknown corrupted samples as outliers which do not follow the simple linear or ReLU rules between their features and corresponding labels. This should be added to the fact that (based on the paper's assumption) the fraction of corrupted samples is less than 1/2, so the clean data points have the majority. This way, author(s) have proposed a linear transformation on the samples in order the make them \"Radially Isotropic\", so (with high probability) the ratio of outliers to clean samples remain as low as possible in *every direction* of the space. Then, some existing robust estimators such as sum of $\\ell_0$ or $\\ell_1$ models have been shown to remove the effect of outliers and acquire the true parameters. I haven't completely checked the proofs, however, the overall idea makes sense to me and is, in fact, quite interesting. In any case, I am not completely familiar with this line of research so I wait to see other reviews in order to assess the novelty of techniques that have been utilized in this work.\n\nWith respect to weaknesses, paper lacks proper discussion at some points which I have explained in the \"Main review\" section. Also, author(s) have assumed a completely clean and noise-free model except for the adversarial part which still includes more than half of the samples. This assumption is a little worrisome in practice, where some minimum levels of, for example, additive noise are *always* present. How robust or sensitive is the proposed method and its theoretical guarantees when the presumed ideal noise-free environment is minimally perturbed?\n\nOverall a well-motivated and fairly well-written paper with some interesting theoretical achievements (as far as I am aware). My vote at this stage is weak-accept.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\nMy main concerns are as follows:\n\nAuthor(s) seem to have a good grasp of existing literature in this area, but it hasn't been completely reflected in the Introduction section. Some discussions and comparisons are still vague and need clarification. I believe the classification of prior advancements in terms of: achieved guarantees, distributional assumptions and etc. can be improved by some reorganization, which also helps the reader to position the current work w.r.t. others, more effectively.\n\nThe adversary described in Definition 1.1 does not match with the one that has been explained in Lines (117:119). In Def 1.1, adversary is allowed to alter (at will) each point $\\left(x_i,f\\left(x_i\\right)\\right)$, with probability $\\eta\\left(x_i\\right)\\leq\\eta$. No information regarding $\\eta\\left(\\cdot\\right)$ has been given except that it is bounded by the constant $\\eta$. That means the function $\\eta\\left(\\cdot\\right)$ can also be chosen by an adversary. That is different from the explanation given in Lines (117:119): \"we consider a more restricted adversary that is presented with a uniformly random $\\eta$ fraction of the points, which can be corrupted arbitrarily at will\". So a natural question would be which of them is finally considered in this work?\n\nAlso, more discussion w.r.t. the adversarial perturbation model considered in this work would be helpful. It is not as strong as the \"contamination model\", but obviously hurt more than a purely random noise. What is the intuition behind this particular noise model?\n\nIn Section 1.2, the transition from ReLU and linear regression in the presence of Massart noise to $\\ell_0$ or $\\ell_1$-regression is not smooth. More explanations are needed here, otherwise the core idea behind the results become somehow ambiguous and hard to understand.\n\n\n------------------------------------------------\nMinor comments:\n\n-(Line 107): What author(s) mean by \"It remains an interesting open problem whether similar PAC learning guarantees can be obtained for the case of ReLU regression.\"? Aren't the results from Theorem 1.3 associated with the most general case? Or author(s) are referring to a more general adversarial noise model rather than Massart noise here? \n\n-(Line 144): I guess it should be $w=A^Tw'$, right? It might not be important since $A$ is later assumed to be symmetric. However, it may confuse the readers.\n\n-(Definition 1.4): What is $\\mathcal{S}^{d-1}$? Is it the surface of $d$-dimensional unit sphere?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No problem here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "1UewisEe8v7", "reviewer": "Reviewer_8NsY", "summary": "This paper studies regression problems in presence of Massart (bounded) noise, where for each sample x_i, the adversary is allowed to change its label/response f(x_i) to an arbitrary value with probability less or equal to eta. Specifically, the authors focus on two problems: linear regression and ReLU regression. For both cases, they make a ``mild yet necessary assumption on the data, that the distribution is not concentrated entirely on any linear subspace; and provide algorithms which exactly recover the true function in polynomial time with constant probability. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I feel the paper is well-written but I have a few concerns on the theoretical guarantee.\n\n- In Theorem 1.2, it turns out that the sample complexity for robust linear regression is suboptimal. In particular, even when the noise rate eta = 0, it is given by O(d^3) which is worse than that of noiseless regression. It also seems unpleasant to have bit complexity dependence in running time.\n\n- In Theorem 1.3, I cannot follow the assumption that $P( w \\cdot x \\geq 0 ) \\geq \\lambda$ for all w.\n\n- What is the computational cost to obtain a radial-isotropic transformation matrix A? This turns out to be a crucial algorithmic component but I did not find a concrete discussion. Note that since you require unit data norm and identity covariance simultaneously, finding such transformation is nontrivial.\n\n- The distributional assumption is informally stated throughout. Can you provide a fews examples that satisify the condition, say Gaussian distributions or uniform distributions?\n\n- I may miss some important messages, but if the data distribution were uniform, then would it be necessary to perform radial-isotropic transformation? My understanding is not being necessary, in which case the technical novelty appears vacuous. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0odb8IOz-v", "reviewer": "Reviewer_463t", "summary": "The authors study exact parameter recovery in ReLU regression under a generalization of the semi-random Massart noise model. Assuming certain distributional anti-concentration, the authors propose and analyze an algorithm that runs in polynomial time and recovers the exact parameters with high probability, given a sample of size polynomial in the input dimension and the (inverse of) the Massart parameter. Along the way, they also provide similar guarantees for the simpler case of linear regression.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is a joy to read. The study is important and relevant to the NeurIPS community. To the best of my knowledge, the results are novel and significant. I checked the proofs only at a high level, but the claims seem sound to me.\n\nA couple of comments/questions:\n1. The algorithm design as well as the proofs -- both in linear/ReLU regression -- leverage insights and techniques from the work of Hopkins et al. 2020. While this paper is cited in the appendix, there is no reference to it in the main text. I urge the authors to discuss this reference in the main text.\n2. Given suitable anti-concentration assumptions, what are the main challenges in extending the results from linear regression to ReLU regression? The guarantees in Theorems 1.2 and 1.3 are very similar, and under the anti-concentration assumption for ReLU regression, proof of 1.3 seems like a straightforward extension of 1.2.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of ReLU regression under the Massart noise model that has recently been studied extensively for classification problems. The main result of the paper is an algorithm that does exact parameter learning under certain distributional assumptions. 

All the reviewers appreciated the results of the paper. While it builds on prior techniques in the area, the technical novelty in the work is high enough. Certain technical questions raised by the reviewers were subsequently resolved by the authors' response. Overall this is a solid theory paper and I recommend acceptance.
Decision: Accept (Poster)