LEARNING DISTRIBUTIONS GENERATED  BY SINGLE-LAYER RELU  NETWORKS  IN  THE PRESENCE  OF ARBITRARY OUTLIERS
Authors: Saikiran Bulusu
Geethu Joseph
M. Cenk Gursoy
Pramod Varshney
Venue: ICLR 2022 Submitted (2022)
Keywords: Learning distribution
ReLU
Truncated Gaussian
Unsupervised learning

Abstract: We consider a set of data samples such that a constant fraction of the samples are arbitrary outliers and the rest are the output samples of a single-layer neural network (NN) with rectified linear unit (ReLU) activation. The goal of this paper is to estimate the parameters (weight matrix and bias vector) of the NN assuming the bias vector to be non-negative. Our proposed method is a two-step algorithm. We first estimate the norms of the rows of the weight matrix and the bias vector using the gradient descent algorithm. Here, we also incorporate either the median or the trimmed mean based filters to mitigate the effect of the arbitrary outliers. Next, we estimate the angles between any two row vectors of the weight matrix. Combining the estimates of the norms and the angles, we obtain the final estimate of the weight matrix. Further, we prove that ${O}(\frac{1}{\epsilon p^4}\log\frac{d}{\delta})$ samples are sufficient for our algorithm to estimate the NN parameters within an error of $\epsilon$ with probability $1-\delta$ when the probability of a sample being uncorrupted is $p$ and the problem dimension is $d$. Our theoretical and simulation results provide insights on how the estimation of the NN parameters depends on the probability of a sample being uncorrupted, the number of samples, and the problem dimension. 

Under review as a conference paper at ICLR 2022
LEARNING DISTRIBUTIONS GENERATED BY SINGLE- LAYER RELU NETWORKS IN THE PRESENCE OF AR- BITRARY OUTLIERS
Anonymous authors Paper under double-biee blind review
ABSTRACT
We consider a set of data samples such that constant fraction of the samples are arbitrary outliers and the rest are the output samples of a single-layer neural network (NN) with rectified linear unit (ReLU) activation. The goal of this paper is to estimate the parameters (weight matrix and bias vector) of the NN assuming the bias vector to be non-negative. Our proposed method is a two-step algorithm. We first estimate the norms of the rows of the weight matrix and the bias vector using the gradient descent algorithm. Here, also incorporate either the median or the trimmed mean based filters to mitigate the effect of the arbitrary outliers. Next, we estimate the angles between any two row vectors of the weight matrix. Combining the estimates of the norms and the angles, we obtain the final estimate of the weight matrix. Our main contribution is the sample complexity for robust estimation rather than the algorithm itself. Here, we prove that Ω ep log {) sam- ples are sufficient for our algorithm to estimate the NN parameters within an error of with probability 1-å when the probability of a sample being uncorrupted is p and the problem dimension is d. Our theoretical and simulation results provide insights on how the estimation of the NN parameters depends on the probability of sample being uncorrupted, the number of samples, and the problem dimension.
INTRODUCTION
A fundamental challenge in machine learning and statistics is to estimate high dimensional dis- tribution given a set of observed data samples from the distribution. One solution technique the deep generative method that models the unknown distribution as the output distribution of neural network (NN) when the input of the NN is drawn from known distribution like standard Gaussian which is motivated from the case of image generation by generative adversarial networks (GANs)
(Goodfellow et al. (2014); Arjovsky et al. (2017); Radford al. (2015); Kingma & Welling (013));
Van Oord et al. (2016). Then, the unknown distribution is estimated by learning the NN parameters from the data samples. Several approaches like GANs (Goodfellow et al. (20 20144): (Arjovsky et al.
2017) ; Radford et al. (2015). ). variational autoencoders (Kingma & Welling (2013), and autore- gressive models (aan Oord et al. (2016)) have been proposed to train the NN. However, they do not provide theoretical guarantees for the parameter learning. So, we address the open problem of com- puting the sample complexity for the parameter estimation of single-layer NN with rectified linear unit (ReLU) activation using a corrupted dataset in the unsupervised learning framework. Here, the corrupted dataset refers to the model wherein the output samples consists of a fraction of arbitrary outliers introduced by an adversary (Byzantine). Motivated by the deep generative models, we con- sider the unsupervised learning framework, i.e., we assume the knowledge of the output samples but, the corresponding inputs are unknown and drawn from the standard Gaussian distribution.
We start with brief review of the related literature. The NN parameter estimation has been con- sidered under both supervised and unsupervised learning frameworks. The estimation rely on the stochastic gradient descent -baD) algorithms (Goel et al. (2018); Allen-Zhu et al. (2019); Chen et al. (2020): Oymak (2019); Mazumdar & Rawat (aawat((2115) Wu et al. (0199; Lei et al. (2020); or the gradient descent (GD)- based approach (Cao & Gu p) Du al. (2019)). A major short- coming of these works is that they assume that the available samples are not corrupted by noise
Lei
outliers. Several works in the literature have addressed the problem of corrupted samples in the

---

Under review as a conference paper at ICLR 2022
context of supervised learning. The existing works have considered the learning of the parameters of a NN with ReLU activation using both SGD-based (Bakshi et al. (2019); Goel et al. (2019);
Mukherjee & Muthukumar (2020h) and GD-based algorithms/Zhang
(2019 Frei et al. 2020);
Vempala & (21me))(2019). However, to the best of our knowledge, the estimation of a NN in the
presence of noise outliers in the unsupervised learning framework has not been studied in the
literature.
Our setting of unsupervised parameter estimation also related to the area of robust statistics as described below. We recall that the goal of our paper is to estimate the parameters of a NN us- ing corrupted output samples assuming that the input distribution Gaussian. Mathematically, this problem is equivalent to estimating the parameters of a truncated Gaussian distribution (see Sec- tion 2 for details). The area of robust statistics also deals with the estimation of high dimensional distributions like Gaussian, Gaussian product, and Gaussian mixture distributions where a constant fraction of the samples were corrupted by noise (Huber (2004): Hampel et al. (201T); Lai et al. (2016); Diakonikolas et al. (2019); Diakonikolas & Kane (2019); Kane (2021)). However, in this paper, we consider parameter estimation from truncated Gaussian samples in the adversarial setting which has not been studied in the literature.
We present our major contributions as the following.
Parameter Estimation (Sections 2 and 3): We estimate the parameters (weight matrix and bias vector) of single-layer NN with ReLU in the unsupervised learning framework where each output sample can potentially be an arbitrary outlier with a fixed probability. We propose an estimation algorithm that has two steps: (i) we estimate the row norms of the weight matrix and the bias vector using GD along with either the median or trimmed mean-based filters to mitigate the effect of arbitrary outliers, and (ii) we estimate the angles between any two row vectors of the weight matrix using a simple geometric result (Williamson & Shmoys 2011 Lemma 6.7).
Theoretical guarantees (Section 4) We show that the proposed algorithm requires 2( log () samples to estimate the network parameters within an error of e with probability 1 6 when the probability of sample being uncorrupted is p. Here, e represents the estimation error.
Empirical validation (Section 5 We evaluate the performance of our algorithm empirically in terms of its relation to the probability of a sample being uncorrupted, number of samples, and dimension (see Figs. [ []. We that our proposed filtering schemes ensure robustness to the arbitrary outliers. Also, the performance of our algorithm improves with the increase in the probability of a sample being uncorrupted and the number of samples, as expected. Further, we note that the estimation eтror increases slowly as the dimension grows for a fixed number of samples the presence of arbitrary outliers. These observations from the empirical results are consistent with our theoretical results.
To summarize, in this paper, we estimate the parameters of single-layer NN with ReLU activation in the presence of arbitrary outliers. The results obtained in this paper provide insights to generalize to multi-layer NN with various activation functions and obtain generalization bounds.
2 LEARNING NEURAL NETWORK MODEL USING CORRUPTED OUTPUT SAMPLES
We consider a single-layer ReLU NN. Let the weight matrix of the NN be denoted by W E Rdxk and the bias vector by b E Rdd The input to the NN is denoted by the latent variable E R* We assume that the variable z is drawn from the standard Gaussian distribution. The Gaussianity assumption is for mathematical tractability, and it is motivated by popular generative approach to estimate a high-dimensional distribution from observed samples in the case of image generation by GANs Goodfellow et al. (2014); Radford et al. (2015): Arjovsky al. (2017). Thus, the output of the network is the random vector x E I given by
ReLUU + b), where NO I,).
where \/0, I&) denotes the Gaussian distribution with mean 0 and covariance matrix I which is the identity matrix of size x k. Let the distribution of the random vector x be denoted by D(W, b). Then, our goal is estimate the unknown parameters W and b of the distribution D(W, b) using
2

---

Under review as a conference paper at ICLR 2022
the knowledge of output samples X1,X2..... X,, Here, we assume that fraction of the samples are arbitrary outliers. The distribution of the observed samples are modeled using the Huber's 's p- contamination model modfied as the following.
Definition 2.1 (Huber's j-Contamination Model Huber (1644). The observed samples are said to be following Huber's 's contamination model if any given sample is drawn from the true distribution D and an arbitrary distribution G with probability p. and 1 - p. respectively. In other words, the observed samples are drawn from the mixture distribution, P,(W, b) given by
(W, = PD(W, b) + (1-
(2)
Note that if b has large negative values, then most of the output samples are zeros due to the ReLU operation. Further, if W is a zero matrix, then any negative coordinate of cannot be identified as it is reset to zero after the ReLU operation. Further, in Wu et al. (2019), the authors have shown that if b E Rd then exponentially large number of samples are required to estimate the bias. This holds true in our case in the presence of arbitrary outliers if b has large negative values, then we would require larger number of samples to estimate the bias vector b compared to that in Wu et al. (2019). Hence, we also assume b to be non-negative.
Our estimation problem is challenging due to two reasons: 1) ReLU operation is not invertible, and therefore, estimation of W and b utilizing maximum likelihood of the probability density function of the random vector x is intractable; 2) the distribution of the corrupted samples is unknown. We tackle these issues using a new formulation combining the GD algorithm and filtering technique. Note that the GD algorithm is similar to that in Wu et al. (2019) wherein the authors use the SGI) algorithm. The proposed algorithm presented in the next section.
ESTIMATION OF PARAMETERS OF SINGLE-LAYER NN
To design our estimation algorithm, we first note that the weight matrix W may not be identifiable from the distribution D(W, b). This is because of the fact that for any matrices W1 and W, if W, WT W2 WT then there exists a unitary matrix Q such that W₂ W.Q. As N Is), we have QZ ~ (N, It). Hence, for any vector b, we have D(W1,b) = D(W b) (Wu et al. (2019). Since our goal is to learn the distribution, learning either W, or W2 is sufficient. In short, we focus on the learnability of the underlying distribution and not the learnability of the NN parameters. Therefore, our proposed algorithm estimates WWT E g and b E Rd from the observed samples from Pp(W. b).
Next, we note that (i,j)-th entry (WWT) (i,j) of the symmetric matrix WWT is [[ ] 222 cos(O.y), where Oz = =,, is the angle between vectors Wi, and W(.:) which are the i-th and j-th rows of matrix W, respectively. Also, note that the ly norm of vector is given by ||x||, = ( (1)))))/P Thus, we can construct the matrix WWT using the row norms (i,, 2 and angles (0,))
Our estimation algorithm consists of two steps: 1) estimation of row norms of W and bias vector b; and 2) estimation of angles between the row vectors of W.
To estimate [i,::) E I. and b(i) E R. for i E [d] (1,2,..., dd. suppose ~ D(W, b). Its i-th coordinate can be written as
xii = (1.:)) b()()))
(3)
where W(i,:) + b(i) ~ AV((ii), (B) Thus, to compute b()) and [( it is
enough to consider the i-th entries of the observed samples. Also, in (3). the ReLU operator sets x(i) to zero if Wii.)) T) z + b(i) is negative. Consequently, we estimate b(i) and (i..)))l using the positive entries of the observed samples. Hence, estimation of b(i) and W :)2 is equivalent to estimating the parameters of one-dimensional normal distribution using positive samples, i.e., the samples that belong to the set Ry0 == (x(i) E IR x(i) > 0). We use μ² b(i) and x²
| to denote the parameters of this oinedimnnll normal distribution. The estimation of 4² and a using corrupted samples is discussed next.
[[ [1
'Or algorithm and its analysis follow even if the outliers not sampled from the same arbitrary distribu- tions G. However, we need assume that all the true samples come from the same distribution D.
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Learning one-layer ReLU
Algorithm 2: ProjGD
NN with outliers
Input: Samples Xzo, Parameters T, n, and n6
Input: Samples X,, E R
Compute (x, 1 from Xz0 using 7
for i E [d] do
X's t- (Xm, m E [n] :x, (1))
2 Ex t filter {x (1)
ProjGD(A<0)
3 Vo + 10 0]
E + 1/v(1)
for .......; T do
b(i) + max(o, v(2)/v(1))
1 f- v1-1(2)/
o² t 1/vi-1(1)
for i fori<je [d] do
Compute Oig using 11
8e - - + +122//2 ji] using 5 and (6
E(i,)) / Sii i) (ost))
gt + 8x + 8a
Vi V 7--181
E) < ().,5) Output: ΣE Rddd b E Ed
10
Vi t P(v.) using 10
Output: VT E R2
We determine the parameters of the univariate normal distribution using maximum likelihood timation (Daskalakis et al. (2018)) given by argmin, ?(v) where ?(v) is the expected negative log-likelihodd with respect to x(i) and v = :1/02: 11/0²] E RR2. This optimization problem can be solved using a learning algorithm like GD or SGD. SGD utilizes only one sample for the gradi- ent computation which introduces large variance due to the stochasticity and low reliability in the presence of arbitrary outliers. Thus, we use GD that utilizes all the samples for the gradient.
To derive our algorithm based on GD, we compute the gradient (Daskalakis al. 2018). Vi(v)- Ex.x [()] where
B(i) (x + (a (x2(1/2 - -x(1) +[ (1)/2 z(1)
(4)
Here, x(i) N(n,, . R20) and (i) N(u, o²: Rso)) Also, 11¹ and 0² the parameters of the true distribution, and μ and 0² are functions of v. In (4. Ez (a(Ba(() admits a closed form
expression Johnson al. 1995)) Be Eg (1) = 1-622 p2)/2 R Here, we define
(-n//o)
A = E[ < (1) < x0| +
(5)
1 1 1 ((-1/))
1 2l -1- (-H//)
- -1 (
8² Var(z(i)) < 2(1) < 00) = o²
(6)
o1 01 (1-0((-u/0)
11-
where (b)) and (-) denote the probability density function and the cumulative distribution function of the standard normal distribution, respectively. We also need Ex (i)] to compute Ex, (())) Since the value of [xx[xx() (i)] is not known, we use the sample mean to estimate (xx[x(()) For this, all the positive samples are partitioned into n, batches. Let Sj be the j-th batch. We then compute
the vector x, (1) E RR2 as follows:
|S Ex(oEs, x(1)2/2 - Ex(OEs, x(i)]
We then combine the ni, vectors (0) estimate Ex, [g()). Recall that the observed samples are from the mixture distribution p, (W, b). Therefore. to compute the expectation with respect to the true distribution D(W, b). a filter is applied on this set of ns vectors to mitigate the effect of the arbitrary outliers which a common tool in the robust statistics literature and obtain Ex [g (i). We consider two filters: median and trimmed mean.
Median: The median based filter possesses the following robustness property. Typically, median is the value separating the higher half from the lower half of given set of points. If more than half of a given set of points are in -MM, M) for some M > O, then their median must be in [-M, M). Thus, the median of (i) no 1= is the vector computed either from all the true samples or outliers
whose magnitudes are comparable to the true samples.
Trimmed Mean: The trimmed mean removes the vectors among the set of n, vectors with relatively large and small values and computes the estimate of Fx [gx(() as the mean of the remaining vectors.
4

---

Under review as a conference paper at ICLR 2022
Here, use the parameter B to indicate the number of vectors to be discarded. This technique prunes the vectors (i)), j [mu) that computed from the batches with outliers having relatively high or low magnitudes. Therefore, we obtain the gradient estimate as
g(1) Ex (i) + (x( filter (f (xx)0)))
+10)2 R
(8)
where filter is either median or trimmed mean, and and 8² are given in and (6). respectively,
Having computed the gradient estimate, we next present the proposed GD algorithm. In the I-th iteration, the algorithm performs the following three steps: The first step is Gradient Computation Step where the gradient ge E R² is computed from the observed positive samples using (8). The second step Update Step where the gradient computed in the previous step is used to perform the GD update:
V Vt-1 1/--1
where Yt-1 > 0 is the diminishing step size. The last step is Projection Step where the objective function ((v) is strongly convex function of if v belongs to a bounded region. To control the the objective function, we project the update vector v into the domain D, {v E R 1/r v(1) I r, [v(2) I r]. Thus, the projection is
durong-convxxity
(10) The GD algorithm is run for iterations where T is the algorithm parameter. The overall algorithm is summarized in Algorithm - This completes the first step of our algorithm that uses the GD algorithm to obtain the estimate of the bias vector and the row norms of the weight matrix.
P(v)= [min ( (1)
min(max(vv2), -)),))
Finally, using the estimates b and E obtained using the GD algorithm, we estimate O:ş similar to Wu al. (2019) using (Williamson & Shmoys, 2011 Lemma 6.7). Specifically, we have
B, = 2T
Σ 1(xm(0) (i) > ((i)) > b(1)) m=1
(11)
where 1-) denotes the indicator function and b is the estimate of the bias vector computed in the previous step using the projected GD algorithm.
The overall algorithm is given in Algorithm where D is the estimate of WW Here, Steps 1-5 estimate the row norms of W and b, and Steps 6-9 estimate the angles between any two rows of W.
Our algorithm is similar to that in Wu et al. (2019) except for the filter which is also standard technique in robust statistics. However, our algorithm is different from the algorithm in Wu et al.) (2019) in the following aspects. We do not rescale the unknown parameters (see Step I of Algorithm in Wu et al. 2)199). We employ median or trimmed mean based filter to compute the full gradient and utilize the GD algorithm instead of SGD used in Wu et al. (2019). We note that our main contribution is the analysis rather than the algorithm which is presented the next section.
THEORETICAL GUARANTEES FOR PARAMETER ESTIMATION
In this section, we provide our main result which characterizes the sample complexity for robust estimation of NN parameters. We address the general problem of learning the distribution generated by a NN the presence of arbitrary outliers (p < 1). Hence, the proof techniques which have been devised for only the special case of p- 1 in Wu et al. (2019), are not applicable our setup due to the presence of corrupted samples. Therefore, we develop novel proof techniques for performing the parameter estimation in the presence of arbitrary outliers. To arrive the main result, first present the error bounds for the two steps of Algorithm I which are described in Sec. 3
The following proposition provides the estimation error bounds for the first step, i.e., the estimation of the bias vector b and the norms of the row vectors of WWT. The proof relies on the fact that the objective function is y-strongly-connex and L-smooth, and we show that the parameters 1), L functions of r. Using the properties of the objective function, we the bound on the error between the true gradient vi(v) and the estimated gradient g, computed from the output samples with arbitrary outliers, obtained in terms of parameter This bound leads the following result that shows that
5

---

Under review as a conference paper at ICLR 2022
estimate b(i) within an additive error of =| ((,:)) and E(, within an additive error of B|l Wi. where a function of the above parameters.
Proposition 4.1. Suppose we initialize the projected gradient step (Algorithm 2 such that llvo and the number of iterations as T. Then, there exists y > such that for any 6,c E (0,1), the output (E(i, ((()) of the projected GD step of our algorithm with median-based filter for any i E [d] satisfies
v*Il = V and choose the step size "It
(i, = (i,:) and (B(1) -((1 =I
(12)
with probability at least 1 - if the number of data samples n Z 11a7. log Here, the error bound is = = V the parameter r. Also, is the probability of sample being uncorrupted and V. E [1/2p, 1] is such that ((e²) < _ S (vV)) with > 0 (p--1/5 where the order constants depend only on r.
Φ+ + 2e(I.An) with n, T. O being constants that depend only on
Ln
The two terms in the error bound E in Proposition 4.1 can be interpreted as the following. The first term V (1- -イz captures the convergence error due the GD algorithm. For any upper bound on the convergence error f > Algorithm runs in time (log S log V) log 7+T This
relation shows that smaller convergence errors require more iterations. The second term 2e(L+m) captures the error due to the gradient computed using the observed samples. Two factors contribute to this error: 1) difference between the (true) sample mean and the true mean, and 2) the arbitrary outliers. Also, the difference between the sample mean and true mean decreases with the number of samples. We notice that the sample complexity depends on Ve which is the probability of a sample being uncorrupted deviating from its mean and variance by and as V. < O(Ve). Consequently, for smaller error e, we need a large number of samples n. Ω [ log ). We also note that the lower bound on e decreases with p.
The following proposition bounds the estimation error the second step, i.e., the estimation of the angle between any two row vectors W(i,:) :) and W(,;)) (where i + j [d). The result shows that we can estimate fig within an additive error of E.
Proposition 4.2. Assume that (2) holds. Then, for a fixed pair of + j E [d] and 6, E (0, 1), the estimate Big of Algorithm 1 that uses a median- filter satisfies
|oos cos 0yyl V2Tp(p'e. - 1122) + 3T p) 27 p)
(13)
with probability least if the number of data samples n. 2 11/27 log Here, the error bound is == (1-1+t+) + + +1 2e(L+m) with 17 L O being constants that depend only on the parameler r. Also, is the probability of sample being uncorrupted and V. E [1/2p) 1] is such that ((e3) < V, S ((ve) with e > 0 (p-1/3) where the order constants depend only on r.
Combining Propositions 4.1 and 4.2 we next present the sample complexity needed to achieve a small parameter estimation error. Specifically, the diagonal entries, E(i, i), for i E [d] are obtained from Proposition 4.1 Further, the off-diagonal entries of are obtained by combining the Proposi- tions 4.1 and 4.2 to obtain the final result follows:
Theorem 4.3. Suppose we initialize the projected gradient step (Algorithm 2 with median-based and choose the step size "tt = Y and the number of iterations as T. Then, there exists > 0 such that for 5,e E (0, 1), the outpul of Algorithm /
filter) such that [| - - =
(Σ, b) satisfies
| WWT || S (V2Tp(oV.- - 1/2) + m -23 + 23)) |
(14)
[b bl| SE|WIE.
(15)
with probability at least 1 - 8 if the number of data samples n. = 22 + log z) Here, p is the probability of a sample being uncorrupted and V. E [1/2p, 1] is such that O v. s O(ve) with > O 103) where the order constants depend only on

---

Under review as a conference paper at ICLR 2022
Table 1: Runtime of various schemes when 0.95, 20000, and d = 5. The table indicates that SGD schemes are faster than their GD counterparts.
Scheme
Oracle
Without Filter
With Median
With Trimmed Mean
GD
16,95
17.73
34.44
60.78
SGD
1.24
1.60
2.11s
3.62 s
We note that in Propositions and on the parameter r O. Recall that the parameter is required for the convexity region D, and we can choose to be a large constant. Thus, r is relatively insensitive parameter which does not require any hand-tuning.
and 4.2, and Theorem 4.3 1). L and the other order constants depend
As the probability of sample being uncorrupted reduces, we observe that the error bound in (14 becomes larger as expected. Also, as the probability of a sample being uncorrupted decreases, the number of samples n required for the error bound increases. Moreover, the obtained error bounds increase with the problem dimension for a fixed number of samples.
Our results also comparable with the existing error bounds for ReLU parameter estimation without outliers from (Wu et al., 2019, Theorem 1). Specifically, if there are no outliers, for any S, (0, 1), the number of samples al. 2019) to achieve the following error bounds with probability least 1 26,
O log } are sufficient for the SGD algorithm in Wu
Σ BG-WWTLE
|F s (/| and ||b bll s ||
(16)
where Ç indicates the parameter estimation error. Comparing the above bounds with (4] and [15) we observe that our bounds are larger due to the presence of arbitrary outliers. In particular,
consists of error terms. The first term V (1 (1- T < 1 in our error bounds results from the convergence of the GD algorithm and is similar to Ç < 1 in (16). However, the second error term 2<(L+m) quantifies the error due to the gradient estimated from the output samples with arbitrary
Ln outliers and not present in (6).. Additionally, (1)). the extra term 3z - p) further increases
the bound compared to the error bound in (16). Therefore, the error Ç in (16) can not be directly compared to the error in (14p and (T5). Further, our sample complexity depends on the probability of sample being uncorrupted p and the second error term whereas the complexity in (Wu et al., 2019 Theorem 1) depends on the square of the convergence error term ( in their sample complexity. Also, when there is no outlier (p- 1), the two sample complexities do not match.
5 SIMULATION RESULTS
In this section, we provide numerical results to verify the performance of our algorithm. In our setup, the columns of W are chosen as the left singular vectors of random matrices from the standard Gaussian distribution. For b, we use random vector from the standard normal distribution whose negative values are replaced with zeros. The mixture of samples are generated such that sample comes from D(W, b) with probability p and from g N5, 1) with probability 1 - p. The hyper- parameters in our proposed algorithm are set as r = and % = 0.Ic We use the batch-splitting approach compute the gradient. This approach induces randomization. As the output samples consist of a fraction of arbitrary outliers, the standard gradient descent algorithm without any filter would perform poorly as shown in our results. Also, we choose the total number of GD and SGD iterations T' to be | 1/10/000 where |x is the number of positive output samples. From our experiments, we observe that the errors first decrease with the number of iterations and then after certain number of iterations, the errors flatten. Based on this observation, we chose the number of iterations (see Appendix A.4). Note that we discard the zero entries and only consider only the set of positive samples X for the number of iterations they do not convey any information about the row norms of W and bias vector
We compute two eтror metrics from the estimated parameters and the ground truth, || Also, we compare algorithm with two other schemes: oracle scheme (estimation using the true samples only), and scheme without filter.
WWT / W| and b/bbb////|
The results shown in Figs. and 2 and Table 1 and the observations from them follows.

---

Under review as a conference paper at ICLR 2022
bnbi wetor
Enter In blas weterr
066
0.25
Ener in bios
0.5
0.15
8.3
0.05
Probebiliit true samples (P)
No samples (n) X10
Dimension (6)
10"
Eiror in weight mabrix
Eneri in Weight Marrix
in woights
1.6
4.5
0.5
0.5
10a
Probabilitt true samples (p)
No.of samples 110
(a) d= 5 and n 20000.
(b) 0.95 and d = 5.
(c) p 0.95 and 20000.
GD wio Filter + GD with Median -X GD with Trimmed Mean 4 Oracle GD
Figure 1: Comparison of the different GD schemes as function of (first column), (second column), and d (third column). The figures indicate that utilizing the filters improves the performance of GD algorithm for mixture of samples.
0.4
vector
2.5
vedtor
0.3
Brror in bioo vector
0.6
1.8
0.2
0.7
0.
Probabiiily true samples (p)
samplea x10*
Dimension (6)
Error in weight mantix
Eror in weight matric
0.8
in weights
2.5
0.6
1.5
0.0
1.5 samples
10
19
20
Probebiliiy true samples (p)
Dimansion (00
(a) d== 5 and n 20000.
(b) p= 0.95 and d = 5.
(c) 0.95 and n = 20000.
SGD with Median + GD with Median -E Oracle SGD
Oracle GD
Figure 2: Comparison of GD and SGD schemes as function of p (first column), n (second column), and d
(third column). We infer that SGD is more sensitive to corrupted samples compared GD.
From Fig. we observe that the GD schemes perform better than the corresponding SGD schemes. Further, the performance improved when we use median based filter along with GD or SGD (for instance, seen by comparing the performances of GD without Filter and GD with Median in Fig. 1). Thus, the filter ensures that the effect of the outliers is reduced, and the curves are closer to the Oracle GD scheme. Finally, from Fig. [ we also infer that the median-basse based approach performs slightly better than the trimmed mean-based approach.
Effect of filters:
Dependence probability of a sample being uncorrupted p: The variation in the error estimation as a function is shown in Figs. [a and 2a The performance of the proposed schemes improve with p. as expected. This trend is because as p increases, the fraction of outliers in the observed samples
8

---

Under review as a conference paper at ICLR 2022
decreases, which leads to better performance. Note that the oracle schemes assume the knowledge of true samples. Thus, their performance does not change with p. On the contrary. the performance of the schemes without filters and SGD schemes with filter do not have monotonic behavior with p. This observation shows that these schemes are not able to handle the outliers effectively. Further, all the schemes converge the corresponding oracle schemes when p 1.
Dependence on number of samples n. Figs. 1b and 2b show how the estimation error of different schemes varies with We observe that the parameter estimation errors computed using Oracle SGD and Oracle GD schemes decrease as the number of samples increases. This trend is because the oracle schemes consider only the true samples. Also, the Oracle GD scheme performs better than the Oracle SGD scheme. Further, the estimation errors computed using our proposed schemes with median and trimmed mean based filters perform better than GD without filter. Hence, the filters mitigate the effect of arbitrary outliers and having more samples reduces the estimation errors.
Dependence on dimension In Figs. Igg..Temr and 2c we plot the error different schemes as a function of the dimension d. We note that due to the presence of arbitrary outliers, the errors increase as the dimension increases for GD without filter. Further, we observe a performance improvement using our proposed schemes with median and trimmed mean-based filters compared to the other benchmarking schemes, supporting our previous conclusions that the filters mitigate the effeet of outliers. However, we observe slow increase in the parameter estimation errors using our proposed schemes with median and trimmed mean based filters as we increase the dimension for fixed number of samples. We observe that the errors when using the oracle schemes also increase slowly as the dimension is increased (Wu et al. (2019).
Comparison of runtimes: From Table I we observe that the SGD schemes run faster than their GD counterparts. This is because the SGD utilizes only one sample for the gradient whereas GD utilizes all the samples for the gradient. Further, the usage of median and trimmed mean based filters along with SGD or GD increases their computation times. However, we reiterate that using the GD scheme with filters offers the best performance terms of error (see Fig. 2). Further, the runtimes of the trimmed mean-based schemes are significantly higher than those of the median-based schemes.
To summarize, from our results, we conclude that GD schemes offer better performance than the SGD schemes. Also, we deduce that compared to the trimmed mean-based scheme, the median- based filter computationally more efficient while offering similar or lower estimation error. More- over, the median-based scheme is parameter free (the trimmed mean depends on the parameter (9) and enjoys strong theoretical guarantces (see Theorem 4.3). Overall, the median- GD algo- rithm is the most effective approach to estimate the NN parameters in the presence of the outliers and performs slightly better than trimmed mean-based GD algorithm. Further, we observe that GD) schemes with filters perform better than Oracle SGD scheme.
6 CONCLUSION
In this paper, we proposed an algorithm for estimation of the parameters of a single-layer ReLU neural network from the truncated Gaussian samples where each sample was assumed be an arbitrary outlier with a fixed probability. Our only assumption was that the bias vector was non- negative. We derived a GD-based algorithm for parameter estimation and incorporated filters to handle the outliers. We analyzed the sample complexity of the proposed algorithm in terms of the parameter estimation error. The efficacy of our approach was also demonstrated using numerical experiments. Removing the non- negaatiiyy assumption on the bias vector is a promising direction for future work. Also, extending our results multi-layer neural networks is also an interesting problem to consider in the future.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 252-252. PMLR, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223. PMLR, 2017.

---

Under review as a conference paper at ICLR 2022
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. Conference on Learning Theory, pp. 195-268. PMLR, 2019.
Yuan Cao and Quanquan Gu. Tight sample complexity of learning one-hidden-layer convolutional neural networks. arXiv preprint arXiv:1911 1.00059, 2019.
Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep ReLU networks is perd-per tractable, arXiv preprint arXiv:2009. 13512 2020.
Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Efficient statistics, in high dimensions, from truncated samples. In 2018 IEEE 59th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 639-649. IEEE, 2018.
Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint
2019.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jemyy Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimenssios without the computational intractability, SIAM Journal on Computing, 48(2):742-864, 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685. PMLR, 2019.
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of single neuron with gradient descent. arXiv preprint arXiv:2005. 14426, 2020.
Surbhi Goel, Adam Klivans, and Raghu Meka. Learning convolutional layer with overlapping patches. International Conference on Machine Learning, pp. 1783-1791. PMLR, 2018.
Surbhi Goel, Sushrut Karmalkar, and Adam Klivans. Time/accuracy tradeoff's for learning a ReLU with respect to gaussian marginals. arXiv preprint arXiv:1911.01444 2019.
Ian J Goodfellow, Jean Pouget-Abadie Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint 10X.:21406.2661, 2014.
Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw, and Werner A Stahel. Robust statisties: The approach based on influence functions, volume 196. John Wiley & Sons, 2011.
Peter J. Huber. Robust Estimation of Location Parameter. The Annals of Mathematical Statistics, 35(1):73 - 101, 1964.
Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
Norman Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan. Continuous univariate distri- butions, volume 1, volume 289. John wiley & sons, 1995.
Daniel Kane. Robust learning of mixtures Gaussians. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1246-1258. SIAM, 2021.
Diederik Kingma and Max Welling. arXiv11312.61 14, 2013.
Auto-encoding variational Bayes. arXiv preprint
Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 665-674, 2016. doi: 1.0/FOCS.2006...7
Qi Lei, Jason Lee, Alex Dimakis, and Constantinos Daskalakis. SGD learns one-layer networks in WGANs. In International Conference on Machine Learning, pp. 5799-5808. PMLR, 2020.
Arya Mazumdar and Ankit Singh Rawat. Representation learning and recovery in the ReLU model. arXiv preprint arXiv: 1803 00330444 2018.
10

---

Under review as a conference paper at ICLR 2022
Anirbit Mukherjee and Ramchandran Muthukumar. Guarantees on learning depth-2 neural networks under data- poisoninonnnn attack. arXiv preprint arXiv:2005.01699, 2020.
Samet Oymak. Stochastic gradient descent learns state equations with nonlinear activations. In
Conference on Learning Theory, pp. 2551-2579. PMLR, 2019.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv: D.0xi::5//..044..4 1.06434, 2015.
Aaron Van Oord. Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks. In International Conference on Machine Learning, pp. 1747-1756. PMLR, 2016.
Santosh Vempala and John Wilmes. Gradient descent for one-hidden-layer neural networks: Poly- nomial convergence and SQ lower bounds. In Conference on Learning Theory, pp. 3115-3117. PMLR, 2019.
David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
Shanshan Wu, Alexandros Dimakis, and Sujay Sanghavi. Learning distributions generated by one-layer ReLU networks. Advances in Neural Information Processing Systems, 2019.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer ReLU networks via gradient descent. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1524-1534. PMLR, 2019.


Reviews:
[{"review_id": "nJD4THsKNTa", "reviewer": "Reviewer_D2X8", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This is a well-defined problem and the authors make an improvement on previous works on learning the parameters in generative models, which all (to my knowledge) avoided the existence of outliers.  At a technical level, the argument has nearly-exact parallels with the procedure of Wu et al., with a small modification for accoutning for outliers that involves swapping the gradient estimate the median and trimmed mean.  It appears to me that the current result does not recover the Wu et al. result as the probability p of uncorruption tends to 1, which is weird (see below; please correct me if I'm wrong).  The presentation also had some issues making it difficult to determine how accurate the parameter estimation really is.  These are the main reasons I'm leaning towards rejection.\n\nA few concrete comments I'm hoping the authors can address:\n\n(1) Is it the case that the current result does not recover the parameters as p --> 1?  In Theorem 4.3, for p=1, the second term doesn't appear to go to zero, since one will be left with a 3 pi ||W||_F^2 term.  Compare this with Theorem 1 of Wu et al.  \n\n(2) The statements of Theorem 4.3 and Propositions 4.1/4.2 seem incomplete.  Where is the quantifier for epsilon?  The appearance of the \\Psi terms is also confusing and not really remarked upon in any detail, although they seem key, and the lack of placement of epsilon in the statement of the results makes it harder to tell what is going on.   This may be related to the fact that the discussion following the statement of Theorem 4.3 talks about the \"first term\" and the \"second term\", but the quantities mentioned do not actually appear as direct quantities in the theorem statement.  \n\n(3) The appendix is structured oddly.  There are no formal statements of lemmas/theorems; there are only \"Steps\" presented on page 12, and then claimed proofs for the \"steps\" in the subsequent sections.  This made it hard to verify the veracity of many of the claims.  There should be precise, formal statements of results so that the reader can verify the proofs.  \n\nFor instance: in Appendix A.1.3. it seems that the authors are only proving the result for the median filter (assuming this is what med{.} denotes), although the results are claimed for both the trimmed mean and the median filter.  Is there a proof for the trimmed mean somewhere?  Can the authors give some more details on how precisely (47)-(50) are derived? \n\n(4) The authors should be more explicit about how the estimation procedure nearly identically mimics that of Wu et al., with the difference being the outlier-robust mean estimation.  If I had not previously read the Wu et al. paper, it would not have been clear from the text how indebted the present work is to Wu et al.\n\n\nSome other minor comments/typos encountered while reading:\n\n* p.1, \"...datasets impacted by a Byzantine\" -- not sure what this refers to?\n\n* p.2, \"adversial\"\n\n* p.3, \"RVe x\"\n\n* Regarding the assumption that the bias is negative: Claim 2 of Wu et al. shows that having negative bias would require exponential sample complexity.\n\n* Where is \\tilde g_x defined in algorithm 2?\n\n*p. 9 and experiments: why is it that the p=0.95 case is so bad for standard gradient descent?  This seems unusual.  Presumably this is using the batch-splitting approach, so there is randomization induced by which samples appear first in the algorithm.  Did the authors average over different realizations of the batches?  \n\n* In the appendix, g_t appears everywhere but seems to refer to \\tilde g_t.  Are these the same?\n\n\n", "summary_of_the_paper": "The authors study the problem of learning the parameters of a generative model defined by a single-layer relu network in the presence of outliers from the Huber contamination model.  They derive a gradient-based algorithm for estimating the norms and angles between rows of the generating matrix, which suffices for estimating the matrix WW^T (which is the only estimable parameters in this setting).  Their analysis is largely the same as that of Wu et al. '19, with additional care needed to take care of outliers.  This is done via trimmed mean or median estimates.  \n", "summary_of_the_review": "This is a well-defined problem and the authors make an improvement on previous works on learning the parameters in generative models, which all (to my knowledge) avoided the existence of outliers.  At a technical level, the argument has nearly-exact parallels with the procedure of Wu et al., with a small modification for accoutning for outliers that involves swapping the gradient estimate the median and trimmed mean.  It appears to me that the current result does not recover the Wu et al. result as the probability p of uncorruption tends to 1, which is weird (see below; please correct me if I'm wrong).  The presentation also had some issues making it difficult to determine how accurate the parameter estimation really is.  These are the main reasons I'm leaning towards rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jaRvbwr2htu", "reviewer": "Reviewer_fTQC", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "- The problem of learning ReLU Gaussian distribution over outliers that this work is looking at is not very well motivated and I am not convinced by the significance of the problem.\n- The techniques used in this paper look incremental in addition to [1] where they worked with the same problem but without outliers. This paper essentially follows the same two step procedure as in [1] and use a robust gradient estimation procedure over it which is also a common tool used in the robust statistics literature.\n- The main theorem - Theorem 4.3 statement is really hard to understand. Particularly, I see that the error does not go down to 0 even with infinite number of samples and time. There is a pi(2-p)3 term which does not go down to 0. Also, [1] proved a lower bound of 1/epsilon^2 but this paper gives an upper bound of 1/epsilon? Can the authors please clarify this part? In general, I think the writing of the paper could be improved. ", "summary_of_the_paper": "The paper studies the problem of parameter estimation of one layer ReLU neural networks where the data is generated by the same network and with probability p, some of the examples are corrupted to arbitrary outliers.They give an algorithm with theoretical guarantees on the sample complexity and also, provide simulations on how the estimation error scales with the important parameters.", "summary_of_the_review": "I would make a recommendation for rejecting this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ciFVSGa-UQL", "reviewer": "Reviewer_CkRT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\n* In the bound in equation (16), the multiplier is at least $3\\pi$. The error does not tend to 0 even as the sample size $n\\rightarrow 0$. This is true even there are no outliers $(p=1)$.\n* In Figure 1(b), the errors for GD with filters do not decrease with increasing sample size. Why is that?\n* For how many iterations was SGD run? The number of GD iterations is set to $|\\mathcal{X}_{>0}|/100$. Is this a sufficient number of iterations? Can you please show/tell how the error goes down with iterations, say for $n=20000, d=5, p=0.9$? Can you please explain why you discard examples with zero entries to set the number of iterations?\n \n \nMinor:\n* The terms $\\eta, L$ used in Proposition 4.2 should be described further in the main text. Otherwise, it is not possible to understand the results. Why is there a matrix transpose in the definition of $\\Xi$? \n* The similarity between the bounds in equation (18) and results in Theorem 4.3 is superficial. This is because, the bounds in (18) can be tightened arbitrarily close to 0 by increasing the sample size, but the bounds in Theorem 4.3 cannot be. \n \n \n\n\n", "summary_of_the_paper": "Given observations $x_1, \\cdots, x_n$ assume that a fraction $p$ of the observations are drawn from \n$$ x = ReLU(Wz + b), \\text{ where } z \\sim N(0, I_k) $$\nand the rest are drawn from an arbitrary distribution $\\mathcal{G}.$ \nThe authors study the problem of estimating $W, b$ in this model.  They assume that $b$ has non-negative entries. \nThe authors separate the problem in two parts: \n* estimate $\\| W(i,:) \\|, b_i$ from the $i$th coordinates of the observations\n* estimate the angles between the rows of $W$ \nThey use a gradient descent algorithm for the first part and use a clever random projections based idea for the second part.\n They derive error bounds of their method and demonstrate the performance of their method through simulations.\n \n \n \n ", "summary_of_the_review": "The error bounds do not seem tight and there are some concerning issues with their simulations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "1UPBGwsy89", "reviewer": "Reviewer_ApGT", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths\n+ The paper is well written.\n+ The techniques in this paper are fairly natural and intuitive (for the specific assumptions made in this paper -- see below.)\n+ The results make sense and are consistent with existing results for learning single-layer NNs without outliers.\n\nWeaknesses\n- The algorithm (rather strongly) depends on the i.i.d. Gaussianity assumption of the input data, which -- of course -- is unrealistic in practice. I admit that it is not uncommon to see such assumptions in theory-focused papers, but that's a larger criticism beyond this paper. For this particular case however, it's hard to envision how the techniques would generalize to more realistic situations -- the Williamson-Shmoys angle estimates according to (11) only hold true for i.i.d. Gaussian inputs.\n- I'm a bit confused about the claim about learnability. The main results are for learning WW' where W is the weight matrix, but in the intro the authors talk about sample complexity of learning the network parameters. How could that translate to learning W up to epsilon relative error (and how would sample complexity be affected in this case?)\n- I'm a bit confused about the utility of Algorithm 2 (and Proposition 4.1). Isn't it just univariate Gaussian estimation with outliers, and if yes, why propose a new method and not just use existing robust estimators? \n- It may be helpful to clarify the 'r' hyperparameter in Algorithm 2, and how it affects the constants in Prop 4.1 and the sample complexity.\n\n---\nThanks for the response. Keeping score unchanged.", "summary_of_the_paper": "The paper presents and analyzes an approach to learn single-layer ReLU networks (assuming Gaussian-distributed input data) in the Huber contamination model where a constant fraction of the training samples may be corrupted. \n\nThe approach involves two steps: \n* estimating row-wise weight norms using gradient descent with median/trimmed mean gradients.\n* estimating angles between rows using standard properties of inner products with Gaussian vectors.\n\n", "summary_of_the_review": "This is a well-written theoretical paper on understanding the sample complexity of learning shallow ReLU neural nets from corrupted samples; however, both the approach and the obtained results are somewhat narrowly applicable to the case of Gaussian inputs and do not seem like they can generalize to more challenging settings.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of learning single-layer neural networks under Gaussian marginals in the presence of outliers. The authors give a recovery algorithm in this setting. The consensus among the reviewers was that the paper lacks technical depth. Specifically, the algorithm is a minor tweak of the one in Wu et al. 2019 for the case without outliers. Another concern was that the algorithm does not recover the prior result when the fraction of uncorrupted points goes to 0. Overall, the paper is below the acceptance threshold.
Decision: Reject