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: NeurIPS 2022 Accept (2022)
Keywords: Learning distribution
ReLU
Truncated Gaussian
Unsupervised learning

Abstract: We consider a set of data samples such that a fraction of the samples are arbitrary outliers, and the rest are the output samples of a single-layer neural network with rectified linear unit (ReLU) activation. Our goal is to estimate the parameters (weight matrix and bias vector) of the neural network, assuming the bias vector to be non-negative. We estimate the network parameters using the gradient descent algorithm combined with either the median- or trimmed mean-based filters to mitigate the effect of the arbitrary outliers. We then prove that $\tilde{O}\left( \frac{1}{p^2}+\frac{1}{\epsilon^2p}\right)$ samples and $\tilde{O}\left(  \frac{d^2}{p^2}+ \frac{d^2}{\epsilon^2p}\right)$ time are sufficient for our algorithm to estimate the neural network parameters within an error of $\epsilon$ when the outlier probability is $1-p$, where $2/3<p \leq 1$, and the problem dimension is $d$ (with log factors being ignored here). Our theoretical and simulation results provide insights into the training complexity of ReLU neural networks in terms of the probability of outliers and problem dimension. 

Learning Distributions Generated by Single-Layer ReLU Networks in the Presence of Arbitrary Outliers
Saikiran Bulusu" Department of EECS Syracuse University Syracuse, NY 13244 sabulusu@syr.. edu
Geethu Joseph"
Faculty of EEMCS
Delft University of Technology 2628 XE Delft, The Netherlands g joseph@tudelft.....
M. Cenk Gursoy Department of EECS Syracuse University Syracuse, NY 13244 mcgursoydsyr.c. edu
Pramod K. Varshney
Department of EECS Syracuse University Syracuse, NY 13244 varshney@syr.co edu
Abstract
We consider set of data samples such that a fraction of the samples are arbitrary outliers, and the rest are the output samples of single-layer neural network with rectified linear unit (ReLU) activation. Our goal is to estimate the parameters (weight matrix and bias vector) of the neural network, assuming the bias vector be non-negative. We estimate the network parameters using the gradient descent algorithm combined with either the median- or trimmed mean- mean-based filters mitigate the effect of the arbitrary outliers. We then prove that Ô ( + +
samples and ò ( neural network parameters within an error of e when the outlier probability is where 2/3 p S and the problem dimension is (with log factors being ignored here). Our theoretical and simulation results provide insights into the training complexity of ReLU neural networks in terms of the probability of outliers and problem dimension.
( 22p time sufficient for algorithm to estimate the
FF"
Introduction
Probability densities based on generative models used in various applications such as image inpainting, deblurring, and generating new images. In particular, generative models representing the distribution over natural images are used for image inpainting and generate new images Van Oord et al. (201)). A critical obstacle in generative modeling is building complex and expressive models that are tractable and scalable. Hence, fundamental challenge in machine learning, in statistics, is to estimate a high dimensional distribution using a set of observed data samples generated by the distribution. One solution technique the deep generative method that models the unknown distribution as the output distribution of neural network when the input of the neural network is drawn from a known distribution (for example, standard Gaussian image generation by generative adversarial networks (GANs)) [Goodfellow al. 2014: Arjovsky et al. 2017 Radford jet al., 2015 Kingma, Welling 2013 Van Oord et al. 2016). Here, the unknown distribution is estimated by learning the neural network parameters from the data samples. Several deep generative
well as
First two authors have equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022), New Orleans, USA.

---

models like GANs (Goodfellow et al., 2014 Arjovsky et al., 2017 Radford et al., 2013), variational autoencoders (Kingma. Welling 2013). and autoregressive models (Van Oord et al., 2016) have been proposed. However, the guarantees associated with such models are generally unknown. So, we address the problem of computing the sample complexity for the parameter estimation of a single-layer neural network with rectified linear unit (ReLU) activation using a corrupted dataset. Here, the corrupted dataset refers to the model wherein the output samples consists a fraction of arbitrary outliers introduced by an adversary (Byzantine). Motivated by the deep generative models, we consider 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 a brief review of the related literature. The algorithms for neural network parameter es- timation have been widely studied under both supervised and unsupervised learning frameworks. The estimation algorithms generally rely on the stochastic gradient descent (SGD)-basee algorithm (Goel
jet al,, 2018 Allen-Zhu et al. 2019) Chen et al. 2022 Oymak 2019 Lei et al. 2020]; or the gradient descent (GD)-based approach (Cao. Gu 2019 | Du et al. 2019). Further, some works have considered the sample complexity of a single-layer NN with ReLU activation in the unsupervised learning framework (Mazumdar, Rawai, 2018 Wu et al., 2019). It is known that when the bias vector is assumed to be a random vector, the column space of the weight matrix can be recovered within an error of (dd) when the output dimension is d' (Mazumdar, Rawat 2018). Further, when the sufficient to
bias vector is assumed to be nonnegative, ((1/2)) samples and O /c)) iterations estimate the parameters of the ReLU network within an error of c. However, none of the above works have considered the problem of corrupted samples. To the best of our knowledge, the estimation of a neural network in the presence of noise or outliers has been addressed only in the context of supervised learning (Bakshi et al.) 2019. Goel al. 2019: Mukherjee, Muthukumar, 2020 Zhang
et al.) 2019 Frei et al. [020 Vempala, Wilmes| 2019). Our paper focuses on a special case of unsupervised learning with corrupted samples wherein we consider a single layer ReLU network.
Our neural network parameter estimation is also related to the area of robust statistics. Mathematically, the problem of learning the distribution using neural network is equivalent to estimating the parameters of a truncated Gaussian distribution (see Section 2 for details). Robust statistics also deals with the estimation of high dimensional distributions like Gaussian, Gaussian product, and
Gaussian mixture distributions where a fraction of the samples are arbitrary outliers (Huber 2004
Hampel et al. 2011] Lai al. 2016 Diakonikolas al., 2019 Diakonikolas, Kane 2019 Kane 2021). However, parameter estimation from truncated Gaussian samples in the noisy setting has not been studied in the robust statistics literature, and we address this literature gap.
We present our major contributions as the following.
Learming Algorithm: We devise a learning algorithm (Algorithm D to estimate the parameters (weight matrix and bias vector) of single-layer ReLU neural network in the unsupervised learning framework where each output sample can potentially be an arbitrary outlier with a fixed probability. Our estimation algorithm uses GD along with either the median- or trimmed mean-based filters to mitigate the effect of outliers.
+ log samples to estimate the network parameters within an error of e with probability 1 - when the probability of a sample being uncorrupted is p E (2/3, 1] and the output dimension is d (Theorem 1). We also characterize the total variation distance between the estimated and true distributions. (Corollary D.
Sample Complexity: Our algorithm requires δ [
Lower bound: We derive a lower bound on the sample complexity which says that at least 0(1/pe²) samples are required to estimate the parameters up an error of e. (Theorem
Empirical validation (Section 5): show that it is robust to the arbitrary outliers. Also, we see that the performance of our algorithm improves with the the probability of sample being uncorrupted and the number of samples, and it increases slowly as the network output dimension grows. These observations from the empirical results are consistent with our theoretical results.
We empirically evaluate the performance of our algorithm and
Overall, the results obtained in this paper show that parameter estimation of single layer ReI.U neural network is possible using robust gradient descent even in the presence of outliers.

---

2 ReLU Neural Network Learning Problem
Let the weight matrix of the ReLU neural network be denoted by W E R and the bias vector by b E R.. The input to the neural network is denoted by the latent variable = E R We assume that the variable x is drawn from the standard Gaussian distribution. Thus, the output of the network is the random vector a: E Rd given by ReLU(( + b) D(W, b), where D(W,b) denotes the distribution of æ: Our goal is to estimate the unknown parameters W and b of the distribution
D(W, b) using the knowledge of a corrupted set of data samples X {-((*) <R4) N Here, we assume that a data sample in X' follows the Huber's p-contamination model (Huber 1964). i... a sample is drawn from D(W (WW b) with probability p. and it an arbitrary outlier drawn from an unknown distribution Dout with probability 1 p. Hence, given sample E X follows the distribution D,- = pD(W, b) + (1 opttut-
We make two observations about the learning problem. Firstly, it is known that when all the samples are from the true distribution, exponentially large number of samples are required estimate the bias b, if it can take any value from the set Rd (Wu et al. 2019). Naturally, the requirement on the number of samples would be worse in the presence of arbitrary outliers and so, assume b to be non-negative. Thus, we assume the following.
Assumption 1. The entries of b E R are all nonnegative.
Secondly, the weight matrix W may not be identifiable from the distribution D(W, b). In particular, for any unitary matrix Q E Rm we have D(W, b) = D(WQ, b). Since our goal is to learn the distribution, learning either W or WQ is sufficient. Thus, focus the learnability of the underlying distribution and not the learnability of the neural network parameters. Specifically, our proposed algorithm estimates WWT E 4xd and b E R.d.
We tackle these issues using new formulation which we discuss next.
3 Robust Estimation Algorithm
Our algorithm is similar to that in eWu al. 2019) which considers the special case of p = 1 and uses SGD. For the general case of p I 1, we combine the estimation framework with a robust filter to estimate the parameters.
To derive the robust estimation algorithm, we first consider a true sample x D(W, b) whose i-th element is nonzero. We have x; ReLU(W. b.) ~ ~N 13l)?)) where A (b;, [W the truncated normal distribution obtained by restricting the normal distribution (b, W to the set of positive real numbers. Hence, estimation of b, and W || is equivalent to estimating the parameters of one-dimensional truncated normal distribution // ( ||??? using positive samples. Therefore, we estimate the parameters in two steps. In the first step, we estimate the i-th element b, of the bias vector and the norm || W of the i-th row of the weight matrix, for é [d]. The second step is the estimation of the angle 9, between the i-th row W, E R and the j-th row W, E T of the matrix W, for i.j E [d]. Then, the ji, entry of the symmetric matrix WWT given by (Wal) all [Will c0,)))
The first step of the algorithm estimates the parameters of the univariate distribution given by - (b., w)ll?) using the i-th element of the samples x = {z; n, > 0, E X} via maxi- mum likelihood estimation (Daskalakis al., 2018). Then, the parameter estimates are given by arg min,. E(p,,3) where ((H,a²) is the expected negative log likelihood that æ; ~ N' NN o²) and the expectation is with respect to the true distribution x; - (b;. J W.ll"). Further, from Daskalakis al. 2018). (1,, o²) is convex function of v ===-- [1/02 m/o² E Rg. Thus, we
solve the convex optimization problem of maximizing E(u, d?) over v.
0² arg min ((v).
(1)
VER2
3

---

The optimization problem in (1) can be solved using GD or SGD which is based on the gradient of ((v) given by the relation (Daskalakis al. 2018): V((v) = g h(v) where
g B Bun (b..IIW.1PP)
[2 -x]
(2)
y "
h(v) - B ym
U2
n²
+u p 2(1 (-P/o)
-
od(-u/0
where μt 22 U2/ U1, o² = 1/01, and (()) and (()) denote the probability density function and the cumulative distribution function of the standard normal distribution, respectively. The relation (3) follows directly from the closed form expressions of the first and second moments of the truncated
Gaussian distribution ~
22
which are functions of e only Johnson et 1995).
We observe that g does not depend on v and only depends on the true distribution parameters (b;, [W&ll"). whereas h(v) does not depend on the true distribution. Therefore, the estimation of which depends on the true distribution, can use the available data samples, and h(v) can be computed in closed form using the current iterate of v. In other words, we compute the component of gradient g only once the GD or SGD algorithm because it does not change across the iterations. This observation motivates us to use the GD algorithm to estimate the parameters instead of SGD. SGD introduces large variance due to the stochasticity and lower accuracy due to the outliers in every iteration whereas GD introduces a small error that does not depend on the algorithm iterate. This key observation and use of (3) to compute the gradient is the main difference between our algorithm and the algorithm in (Wu al. 2019), apart from the robust estimation aspect.
To estimate g, we partition Xx into batches of size NB and compute the batchwise estimate g()
(b)
Σ
123/2 -x
NB
ZEZ
where X C xx+ is the b-th batch of samples. We then combine the batchwise estimates using a well-known filter in the robust statistics literature such as the median or trimmed mean to handle the outliers. The median filter mitigates the effect of outliers by ensuring that if more than half of the batchwise estimates lie in an interval around the true value g. then their median also lies in the same interval. Similarly, the trimmed mean prunes the outliers by removing the vectors with relatively large and small values (controlled by its parameter) and computes the estimate of as the mean of the remaining vectors. Therefore, we obtain the gradient estimate ğ h(v) as
h(v) = filter (g()) gg))).))) (((xxt((())))))
-2(v):
(5)
where the function filter(-) (-) is either median or trimmed mean, and h(v) is given in (3) Using the gradient estimate, the robust GD algorithm updates the k-th iterate u(k) as
(k) = P (o(kk 1) 7(k- 1) و h(v(k 1))]), where >(+) > 0 is the diminishing step size and P(-) projects the iterate into bounded region D, as D. = {v E 2² 1/r S 11 S r, 0 02 rr P(v) = [min (max 11 1/r},r)
(6)
(7)
man 0},
(8)
The projection ensures that ((v) is strongly convex function of v. and the parameter controls the strong-convcxit (Daskalakis ct al. 2018) (see Section 4 for more details). The robust GD algorithm
is summarized in Algorithm? 2 The role of r is further discussed in Section 4 This completes the
first step of our algorithm based on robust GD which is summarized in Algorithm 2
Finally, using the estimates obtained via the robust GD algorithm, we estimate O, similar et al. 2019) using (Williamson, Shmoys, 2011 Lemma 6.7). Specifically, we have
Wu
N Σ
0, = π 2T
b.) (17())) (n) > b,)
N
n=1
where 1(-) is the indicator function and b is the output of the robust GD algorithm. The overall distribution learning algorithm is given in Algorithm | where Σ denotes the estimate of W T

---

Algorithm 1: ReLU network estimation
Algorithm 2: Robust GD
Input: Samples X' = {xx(0) E
[B]] N
Input: Positive samples X C IR+
n=1
1 for i E [d] do
Parameters: Iterations K, step size (k)), projection parameter r, batch size NB
2
X' and at; Compute using Algorithm with input
x + (an
0}
1 B +- |x+ /NB
as X
Compute (g (b) B from X'' using
===1
Σ + 1/8, b, t ma 02/01}
3 9 <- filter (1) 9
(B)
v(0) +0
for i <jj [d] do
5 for A: ........ K do
Compute Big using
Jr - 12(k-1) 1i
0²
8
Dig t // Dip Eio (o,))
Compute h(v(k 1)) using (3)
9
Ej. f- Ei.j
8 Update uk) using 6
Output: Σ Rdddd and b Rd
Output: v(K) R²
Error Bounds for Parameter Estimation
This section provides our main result which characterizes the sample complexity for robust estimation of neural network parameters. The analysis of distributed learning in the presence of arbitrary outliers is studied in Chen et al. (017); Yin et al. (2018). They assume that the available samples are split into a fixed number of batches and a constant fraction (<1/2) of batches are outliers. However, our setting assumes probabilistic model where each data sample can be outlier with probability - p and there is no deterministic upper bound on the number of outliers. Consequently, each batch can have mixture of true samples and outliers, and is critical to choose the right batch size NB (see Proposition
2 and its discussion for details).
We rely two propositions to arrive at the main results. The propositions establish the properties of the objective function of the optimization problem in I and the error bounds for the robust GD algorithm presented in Algorithm 2
Proposition 1. There exist positive constants and n that depend only on the projection parameter 2 of Algorithm 2 such that the objective function E(v) in ① is n-strongly convex and L-smooth function of v when v E D,, defined in (7. Here, L is an increasing function of r whereas r) is a decreasing function r.
Proposition I proves that the projection parameter r controls the strong-convexity and smoothness parameters of the objective function. If r takes large value, it leads to small strong-convexing convexity parameter and a large smoothness parameter L. We use this property to interpret the role of parameter in the algorithm performance using the next result presenting the error bounds of the robust GD algorithm. To this end, we make the following assumptions to derive the error bounds:
Assumption 2. The projection parameter 2 1 is such that the minimizer of T o² E D, where D, is defined in (7).
Assumption The step size of the robust GD algorithm in Algorithm 2 is fixed across the iterations, i.e, 7(k) = 7, for k- = 1,2,.... K.
large value of ensures that the first assumption is satisfied. However, if any prior knowledge about the true parameters is known, the parameter r can accordingly take smaller values. The second assumption is guideline on how to choose the step size of the robust GD algorithm for the analysis. Under the above assumptions, the error bound for the robust GD algorithm is as follows.
Proposition 2. Consider the robust GD algorithm in Algorithm based on the median filter, which solves ① with input as X Let p+ E (1/2, 1] be the probability that a given sample in X+ follows the true distribution + (wi/v 1/vî). Assume that there exist e (0,1), 8 (0, 1/2), and Ç E (0. 225) such that the batch size Ng satisfies
NB = ( log
1 2
2(1 8) log and NB S 1og(1/pt)
)
(10)
1+(
5

---

Then, under Assumptions 7 1 the output v(K) of our algorithm satisfies ([o(K) -0'll S e, with probability at least 1 - 0 i = Ω2
No log and K = =Q(log 4 Here, all the order constants,
the step size 1/L in Assumption 3 and the linear convergence rate L I+ < 1 depend only on the projection parameter Also, 77, L > are defined in Proposition 7
The above result indicates the role and suitable choices of the parameters: K, 2(k), r. and NB as discussed next. The result states the number of iterations K scales logarithmically with the inverse of the error e. Also, Assumption shows that the result holds when the step size is the same across all the iterations. Finally, r should be large enough to satisfy Assumption 2 However, large r leads to slower convergence because the rate of convergence is an increasing function of r. Finally, the algorithm gives an upper and lower bound on the batch size Ng. We note that for GD, the estimation error depends on the error in the first term of the gradient in (5), which is estimated using the batchwise gradient estimate (4). The error in the batchwise gradient estimate is contributed by the outliers and the finite sample error (the difference between the sample moments computed using a finite number of samples from distribution and the true moment of the distribution). With large batch size, the number of batches without any outliers is also small. Since the outliers are drawn from an arbitrary distribution Dout. even if a batch contains one outlier, the error in the batchwise gradient estimate can be large. This observation explains the upper bound on the batch size which depends on p+. It is important to note that when there are no outliers (i.e., p' = 1). there is no upper bound on the batch size. Similarly, if the batch size is small, the batchwise gradient computed using batches without outliers incurs a large finite sample error. This observation intuitively explains the lower bound on the batch size which is independent of p². In short, the upper and lower bounds on NB balances the tradeoff between the error due to the outliers and the finite sample error. Further, we note that the upper and lower bounds can be simultaneously achieved by choosing to be large enough.
We also note the restriction on p+ which is not surprising. This is because the median-based methods work only if the number of outliers are smaller than that of the uncorrupted data samples, which naturally restricts the probability of outliers.
We next present our main theorem that discusses the overall complexity of our algorithm.
Theorem 1. Consider the learning algorithm in Algorithm 2 that uses the meadian basann robust GD. Let p E (2/3, 1] be the probability that a given sample follows the true distribution 'D (WWT, b). Assume that there exist e 1), 1/2), and Ç E (0, 1 -28) such that the batch size NB of Algorithm 2 satisfies
NB = ( log b) and No S
1 log(2/p) 1 1+5
2(1 - 5)
log
(11)
Then, under Assumptions 1o the outputs E and b of Algorithm 1 satisfy
SSWWTT s [( + (1 (1-1) p)] W 2 and ||6- bl S sc||W]l
(12)
with probability at least 1 - 8 if the number of samples N =ō
52 log 9). The algo-
rithm runs in time ò (e. [ マlzz log and space Ô (#) マोッ log g + de) All the order
constants and the step size y in Assumption 3 depend only on the algorithm parameter
With no outliers (p- = 1), our result is comparable with the existing error bounds from (Wu et al.
2019 Theorem 1). Specifically, for SGD in (Wu al. 2019) with outliers, the number of samples
N Ô (3 log )) is sufficient to achieve
- ww || S 1 and 1 b1l S < W|
(13)
with probability at least 1 for any c, E (0, 1). In our case, when p = 1, there no upper bound
on NU and we choose N₁ = N Ω (+ log 3 :)) to achieve (33) with probability 1 - ò. Thus, the time and space complexities of our algorithm are identical to those of SGD in (Wu et al. 2019). We next bound the total variation distance between the estimated distribution and the true distribution under the restriction that W is full-rank square matrix.

---

1.5
0.35
9.
0.3
Ererin bies vector
vector
0.05
0.2
0.2
Eneriin
0.5
0.18
0.05
0.5
1.5
100
200
300
400
500
Probabiiitt samples (P)
No. samples
10
Dimension
Enror in weggh matro
16t
Error in weight metrix
Error in weights
1.5
1.5
0.5
0.5
0.5
1.5
500
Probobiliit true samples (P)
(a) d = and N 20000.
(b) p= 0.95 and d 5.
(c) p= 0.95 and N = 20000.
wio + Median
Trimmed
4 GD
Figure 1: Comparison of the different GD schemes as a function of p (first column), N (second column), and d (third column). The figures indicate that utilizing the filters improves the performance of GD algorithm for mixture of samples.
Corollary 1. Consider the learning algorithm Algorithm T that uses the seradiin-basee robust GD. Suppose that W Rdxdd is full-rank with and let &. be the condition number of W WWT Let > 1 2nd be the probability that given sample follows the true distribution 'D (WWT, b) Assume that there exist (kd(1 - 1/2j. 5 (0, 1/2), and S (0, 25) such that the batch size NB of Algorithm satisfies Ng = [c-xd(1-p)) log 1/2 and NB S log(2/p) log 2(1-6) 1+6
Then,
under Assumptions the outputs E and b of Algorithm satisfy
TV (D((
(W.b)) b)) Sc.
(W.
(14)
with probability at least 1 if the number of samples - Ō ((e-xd(1-p)) Here, (-). denotes the total variation distance between the argument distributions. All the order constants and the step size in Assumplion 3 depend only the algorithm parameter
28
log d
We note that when 1, we have satisfied.
2xd 2 1/4 and the bound on p in Theorem is automatically
The last result of this section gives lower bound on sample complexity of the problem of learning ReLU NN described in Section We restrict the analysis to specific class of ReLU distributions where W is scaled identity matrix.
Theorem 2. Consider the ReLU parameter estimation problem with p the probability that a given sample follows the true distribution. Suppose that the true distribution belongs to (D (W b) aI, Rd, b, OVi}, where = O(1). Then, any algorithm that learns to satisfy samples.
6 b [| with success probability least 2/3 requires Q
pc
Comparing the sample complexity achieved by our algorithm (Theorem I and the above lower bound, we can see that the second term of our sample complexity matches the derived bound up to log factors. However, there is gap between the sample complexity of our algorithm and the lower bound due to the first term that varies 1/p² (ignoring the log factors). This is interesting direction for future work to if there are better bounds.
7

---

0.4
0.5
3.5
Brorin bize vector
0.4
0.3
1.3
8.
in
in
0.1
0.5
1.5
100
200
300
400
500
Probability samples (p)
No.ot samples
x100
Dimension
8.5
Enror in weggt manrx
Enor in weight metris
0.6
Enror in weights
2.5
0.6
1.5
0.2
0.5
1.5
100
600
Probobiliit
true samples (P)
No.ot
(a) d = 5 and N 20000.
(b) p= 0.95 and d= 5.
(c) p= 0.95 and N = 20000.
SGD with Median + GD with Median -B Oracle SGD
4 Oracle GD
Figure 2: Comparison of GD and SGD schemes function of p (first column). NN (second column), and d (third column). We infer that SGD is more sensitive to corrupted samples compared GD.
Table 1: Runtime of various schemes when 0.95, N 20000, and
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 s
17.73
34.44
60.78 s
SGD
1.24 s
1.60
2.11
3.62
5 Simulation Results
In this section, we provide numerical results to verify the performance of our algorithm. In our simulation setup, the columns of W 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 a sample comes from DWW, b) with probability and from Dout with probability 1 p. The I outlier distribution Dont = (5, 1) and the algorithm hyper-parameteer are r = 3 and 7(k) 0.IK We use the batch-splitingg approach to compute the gradient, inducing randomization. Also, from our experiments, we observe that the errors flatten certain number of iterations (see Figures 3 and 4 in the supplementary material) around 1/ 1/100-th of the number of positive output samples which chosen as the number of GD and SGD iterations K. We compute two error metrics from the and l| bll2/11 [/... Further,
estimated parameters and the ground truth, ا WWT compare algorithm with two other schemes: the oracle schemes (estimation using the true samples only) and schemes without a filter. Our results are shown in Figures] [ and and Table [] and the observations from them are as follows.
[||]
Effect of the filters: From Figure the GD schemes perform better than the corresponding SGD schemes. Also from Figures and 2 we infer that using filters along with GD SGD reduces the effect of the outliers, and the curves are closer to the oracle schemes. We also infer that the median--bseed approach performs slightly better than the trimmed mean-based approach.
Dependence on the probability of sample being uncorrupted p. From Figures La and 2a the performance of all the schemes except the oracle schemes improves with because the fraction of outliers in the observed samples decreases with increasing p. However, the schemes without filters show considerable difference in performance as they are not able to handle the outliers effectively. The performance of oracle schemes does not change with as they assume the knowledge of true samples. Further, all the schemes converge to the corresponding oracle schemes when p 1.

---

Dependence on the number of samples N and dimension d: Figures and show that the estimation performance the oracle schemes and the schemes with the filter improves with the number of samples N. However, the schemes without a filter do not always improve with N because the number of outliers also increases with N, which are not handled by the algorithm. In Figures [T] and [cc we varied the dimensions up to 500 and observed that there is a slight increase in the errors as the dimension increases for our proposed schemes as well as oracle schemes. We also observe that the emrors increase d increases for GD without filter due to the presence of arbitrary outliers.
Comparison of runtimes: From Table I the SGD schemes run faster as SGD utilizes only one sample for the gradient, whereas GD utilizes all the samples. The filter-based schemes have higher computation times than the ones without filters, but the runtimes of the trimmed mean- mean-based schemes are significantly higher than those of the median-basee schemes.
Overall, the median-based GD algorithm is the most effective approach to estimating the NN parameters in the presence of the outliers and is faster than the trimmed mean-based GD algorithm. Also, the median-based scheme is parameter-free and enjoys solid theoretical guarantees.
Conclusion
In this paper, we proposed an algorithm for the estimation of the parameters of a single-layer ReLU neural network from the truncated Gaussian samples where each sample assumed to be an arbitrary outlier with a fixed probability. Our only assumption was that bias vector was non- negative. We analyzed the sample and time complexities of the GD-based estimation algorithm combined with median- based filters to handle the outliers. The efficacy of our approach was also demonstrated using numerical experiments. Removing the non-negativity assumption the bias vector and extending our results to multi-layer neural networks are two promising directions for future work.
References
Allen-Zhu Zeyuan, Li Yuanzhi, Song Zhao convergence theory for deep learning via over- parameterization // International Conference Machine Learning. 2019. 242-252.
Arjovsky Martin, Chintala Soumith, Bottou Léon. Wasserstein generative adversarial networks International Conference Machine Learning. 2017. 214-223.
Bakshi Ainesh, Jayarum Rajesh, Woodruff David P. Learning two layer rectified neural networks in polynomial time // Conference on Learning Theory. 2019. 195-268.
Cao Yuan, Gu Quanquan. Tight sample complexity of learning one-hidden- layer convolutional neural networks Advances in Neural Information Processing Systems. 2019. 32.
Chen Sitan, Klivans Adam R, Meka Raghu. Learning deep RELU networks perameer tractable // IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 2022. 696-707.
Chen Yudong, Su Lili, Xu Jiaming. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent // Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2017. 1, 1-25.
Daskalakis Constantinos, Gouleakis Themis, Tzamos Chistos, Zampetakis Manolis. Efficient statistics, in high dimensions, from truncated samples 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 2018. 639-649.
Diakonikolas Iliss, Kamath Gautam, Kane Daniel, Li Jerry, Moïtra Ankur, Stewart Alistair. Robust estimators in high-dimensions without the computational intractability // SIAM Journal Computing. 2019, 48, 2. 742-864.
Diakonikolas Haas, Kane Daniel M. Recent advances in algorithmic high-dimensional robust statistics I1 arXiv preprint arXiv:19) 191.00911.1 2019.

---

Du Simon, Lee Jason, Li Haochuan, Wang Liwei, Zhai Xiyu. Gradient descent finds global minima of deep neural networks // International Conference on Machine Learning. 2019. 1675-1685.
Frei Spencer, Cao Yuan, Gu Quanquan. Agnostic learning of a single neuron with gradient descent // Advances in Neural Information Processing Systems. 2020. 33. 5417-5428.
Goel Surbhi, Karmalkar Sushrut, Klivans Adam. Time/accuracy tradeoffs for learning ReLU with respect to Gaussian marginals // Advances Neural Information Processing Systems. 2019. 32.
Goel Surbhi, Klivans Adam, Meka Raghu. Learning one convolutional layer with overlapping patches International Conference on Machine Learning. 2018. 1783-1791.
Goodfellow lan, Pouget-Abadie Jean, Mirza Mehdi, Xu Bing, Warde-Farley David, Ozair Sherjil, Courville Aaron, Bengio Yoshua. Generative adversarial nets // Advances in neural information processing systems. 2014. 27.
Hampel Frunk R, Ronchetii Elvezio M, Rousseeuw Peter J, Stahel Werner A. Robust statistics: The approach based on influence functions. 196. 2011.
Huber Peter J. Robust Estimation of Location Parameter The Annals of Mathematical Statistics. 1964. 35, 1. 73 101.
Huber Peter J. Robust statistics. 523. 2004.
Johnson Norman I, Kotz Samuel, Balakrishnan Narayanaswamy. Continuous univariate distributions, volume 289. 1995.
Kane Daniel M. Robust learning of mixtures of Gaussians // Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). 2021. 1246-1258.
Kingma Diederik P, Welling Max. Auto-encoding variational Bayes // arXiv preprint arXiv: 2013.
Lai Kevin A., Rao Anup B., Vempala Santosh. Agnostic Estimation of Mean and Covariance // 2016 IEEE 57th Annual Symposium on Foundations Computer Science (FOCS). 2016. 665-674.
Lei Qi, Lee Jason, Dimakis Alex, Daskalakis Constantinos. SGD learns one-layer networks in WGANs // International Conference on Machine Learning. 2020. 5799-5808.
Mazumdar Arya, Rawat Ankit Singh. Representation learning and recovery in the ReLU model // arXiv preprint arXiv: 11.11803.0000 04304. 2018
Mukherjee Anirbit, Muthukumar Ranchandran. Guarantees learning depth-2 neural networks under a data-poisoning attack arXiv preprint (XXi:22005.0169 2020.
Oymak Samet. Stochastic gradient descent learns state equations with nonlinear activations // Conference on Learning Theory. 2019. 2551-2579.
Radford Alec, Metz Luke, Chintala Soumith. Unsupervised representation learning with deep convo- lutional generative adversarial networks // arXiv preprint 11Xiv:1511.0644 2015.
Van Oord Aaron, Kalchbrenner Nal, Kavukcuoglu Koray. Pixel recurrent neural networks //
International Conference on Machine Learning. 2016. 1747-1756.
Vempala Santosh, Wilmes John. Gradient descent for one-hidden-layer neural networks: Polynomial convergence and SQ lower bounds // Conference on Learning Theory. 2019. 3115-3117.
Williamson David P. Shmoys David B. The design of approximation algorithms. 2011.
Wu Shanshan, Dimakis Alexandros G, Sanghavi Sujay. Learning distributions generated by one-layer ReLU networks // Advances in Neural Information Processing Systems. 2019. 32. 8107-8117.
Yin Dong, Chen Yudong, Kannan Ramchandran, Bartlett Peter. Byzantine- Robusst Distributed Learning: Towards Optimal Statistical Rates // International Conference Machine Learning. 2018. 5650-5659.
Zhang Xiao, Yu Yaodong, Wang Lingxiao, Gu Quanquan. Learning one-hidden-layer ReLU networks via gradient descent // The 22nd International Conference on Artificial Intelligence and Statistics. 2019. 1524-11 1534.
10

---

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


Reviews:
[{"review_id": "ZwMj-jrSBU", "reviewer": "Reviewer_cvUF", "summary": "The authors study the problem of learning the distribution of a generative model in the form of a one hidden-layer ReLU in the presence of arbitrary outliers (according to Huber's contamination model). The problem without outliers has been studied by Wu et al. 2019. Authors here show that $\\tilde{O}(1/p^2+(1/\\varepsilon^2p))$ samples and $\\tilde{O}(d^2/p^2+(d^2/\\varepsilon^2p))$ time is sufficient to estimate the NN parameters within error $\\varepsilon$, where the outlier probability is 1-p.  They do this by providing a Robust GD algorithm . They also provide some experiments to back their theoretical analysis.\n\nReferences:\n\nWu, Shanshan, Alexandros G. Dimakis, and Sujay Sanghavi. \"Learning distributions generated by one-layer ReLU networks.\" Advances in neural information processing systems 32 (2019).", "questions": "Please see weaknesses mentioned above.\n\nMinor comment: Line 242 has a missing link.", "limitations": "I don't see the limitations of this are addressed adequately. The authors say it is in Section 3 and 4, but I am unable to find them.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis is an interesting model and the problem of trying to learn generative models from NNs are useful to study, especially the approach taken here in the view point of robust statistics. \n\nWeakness:\n\n1) Even in the problem of learning a single high dimensional untruncated Gaussian, a coordinate wise filter would give an error $O(p\\sqrt{d})$. Here, the analysis heavily relies on a coordinate wise learning method that was proposed by Wu et al. 2019, which works without any outliers. I think one needs to use new techniques for this problem when dealing with it through the lens of Robust statistics, that works on all the dimensions. \n\n2) Most of the techniques in Robust statistics literature also works for more powerful adversaries. Do these methods go through for those adversaries?\n\n3) Is there an equivalent of Corollary 1 in Wu et al. 2019 that can be obtained here, that connects the TV distances?\n\n4) The experiments here are performed for very low dimensions upto 20, which is not as enlightening. \n\n5) Most of the techniques are a combination of Wu et al. 2019 and Daskalakis et al. 2018.\n\nUPDATE:\nAfter going through the rebuttal, I believe that the authors have responded convincingly. I still believe that this is somewhat incremental in the light of previous work Wu et al. 2019 and Daskalakis et al. 2018 and to improve the bounds one has to move beyond a coordinate wise approach, as done in Robust statistics literature and maybe look at more powerful adversarial models. But I will increase my score from 3 to 5.\n\nReferences:\n\nDaskalakis, Constantinos, et al. \"Efficient statistics, in high dimensions, from truncated samples.\" 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018.\n\nWu, Shanshan, Alexandros G. Dimakis, and Sujay Sanghavi. \"Learning distributions generated by one-layer ReLU networks.\" Advances in neural information processing systems 32 (2019).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QwO_FDl4gGj", "reviewer": "Reviewer_eN7y", "summary": "This paper proposes an algorithm to learn the distribution generated by single layer ReLU generative models. Prior work of Wu et al showed that an algorithmic adaptation of Daskalakis et al can be used to learn the weights (upto rotation) and biases of the neural network.\n\nThis work shows that a similar algorithm can be used to learn the network parameters, even in the presence of outliers under Huber's contamination model. The authors propose an algorithm that combines Wu et al with robust estimation algorithms such as median-of-means and trimmed mean estimators.", "questions": "- I do not understand how this algorithm can possibly work for all $0 \\le p < 1$. It's easy to see that $p < 0.5$, then this would imply that the majority of batches are corrupted and hence the median estimate will also be corrupted. This can also be verified in the Appendix, Line 456, where the inequality cannot be satisfied for any $N_B$ if $p^+$ is smaller than 0.5. In fact, the bound in line 456 places a strong upper bound on $N_B$ and I think that satisfying this along with the lower bound may not be as trivial as the authors claim.\n\n- Please comment on the non-independence of the gradients after the first iteration.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The algorithm is intuitive and easy to understand, and the presentation is mostly clear. The proofs seem mostly correct and the evaluation shows that it is competitive with Wu et al for $p=1$ and is better for $p < 1$ (as expected).\n\nWeaknesses:\n- The algorithm feels like a merge of median-of-means with the SGD approach of Wu et al and Daskalakis et al, and the authors should clarify what are the novel technical challenges they faced in the proof of the main Theorem.\n\n- This algorithm cannot work if $p \\le 0.5$, in which case the majority of batches are corrupted, and the median estimate is not useful. This is not mentioned in the paper, and the authors claim it works for all $ 0 < p \\le 1$.\n\n- After the first gradient step, the per-sample gradients computed in later batches are no longer independent of one another, and the concentration bounds used are no longer valid. I think this can be fixed assuming a fresh batch of samples is received at each time step, and a union bound should give the failure probability as $ K \\delta $. But the authors should be more careful and include this dependence in their bounds. I think this also affects the number of batches needed, but I'm not sure.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LeghoLNSg3H", "reviewer": "Reviewer_KLJj", "summary": "The authors consider the problem of learning a one layer generative model with adversarial corruptions. A one layer generative model is a standard Gaussian input followed by a linear transformation then a ReLU activation. They consider the contamination model where a fraction of the data comes from an arbitrary outlier distribution.\n\nThey show that the gradient descent algorithm of Wu et al. can be made into a robust algorithm. Specifically, they show that you can do robust gradient descent to learn the mean and variance of each coordinate, then do robust estimation of the angle coordinates to get the full covariance matrix. They experimentally verify their algorithm and show that robust gradient descent can outperform the non-robust algorithm on corrupted data.", "questions": "Why is a new strong convexity proof required? I see Wu et al. mentions strong convexity and the parameter r but the discussion is somewhat different.\n\nIt is interesting that the $b$ parameter error is not affected by the outlier probability. What is the intuition for this?", "limitations": "I found no issues here.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe authors establish a clean result on robust learning of 1 layer generative models with ReLU activations.\n\nThe paper is well written and easy to understand.\n\nThe authors present empirical evaluations.\n\nWeaknesses:\n\nThe approach of Wu et al. breaks the problem down into a series of scalar optimization and estimation problems. Robust statistics is significantly easier in scalar situations, so making the algorithm of Wu et al. robust is somewhat incremental.\n\nOne way to improve the paper would be to discuss lower bounds based on the outlier fraction.\n\nMinor Issues:\n\n242: There is a missing reference.\n\nThe theorems are not in latex theorem blocks, which makes it hard to isolate them from the surrounding text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept