Year: 2021

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. Our main contribution is the sample complexity for robust estimation rather than the algorithm itself. Here, we prove that Ω( 1 p4 log d δ ) samples 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 a sample being uncorrupted, the number of samples, and the problem dimension.

text: d δ ) 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 a sample being uncorrupted, the number of samples, and the problem dimension.

heading: 1 INTRODUCTION
text: A fundamental challenge in machine learning and statistics is to estimate a high dimensional distribution given a set of observed data samples from the distribution. One solution technique is the deep generative method that models the unknown distribution as the output distribution of a neural network (NN) when the input of the NN is drawn from a 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 et al. (2015); Kingma & Welling (2013); 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. (2014); Arjovsky et al. (2017); Radford et al. (2015)), variational autoencoders (Kingma & Welling (2013)), and autoregressive models (Van 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 computing the sample complexity for the parameter estimation of a 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 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 NN parameter estimation has been considered under both supervised and unsupervised learning frameworks. The estimation rely on the stochastic gradient descent (SGD)-based algorithms (Goel et al. (2018); Allen-Zhu et al. (2019); Chen et al. (2020); Oymak (2019); Mazumdar & Rawat (2018); Wu et al. (2019); Lei et al. (2020)); or the gradient descent (GD)-based approach (Cao & Gu (2019); Du et al. (2019)). A major shortcoming of these works is that they assume that the available samples are not corrupted by noise or outliers. Several works in the literature have addressed the problem of corrupted samples in the
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 (2020)) and GD-based algorithms(Zhang et al. (2019); Frei et al. (2020); Vempala & Wilmes (2019)). However, to the best of our knowledge, the estimation of a NN in the presence of noise or outliers in the unsupervised learning framework has not been studied in the literature.
Our setting of unsupervised parameter estimation is 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 using corrupted output samples assuming that the input distribution is Gaussian. Mathematically, this problem is equivalent to estimating the parameters of a truncated Gaussian distribution (see Section 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. (2011); 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 a 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 Ω( 1 p4 log d δ )
samples to estimate the network parameters within an error of with probability 1− δ when the probability of a sample being uncorrupted is p. Here, > 0 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. 1 and 2). We see 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 error increases slowly as the dimension grows for a fixed number of samples in 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 a single-layer NN with ReLU activation in the presence of arbitrary outliers. The results obtained in this paper provide insights to generalize to a multi-layer NN with various activation functions and obtain generalization bounds.

heading: 2 LEARNING A NEURAL NETWORK MODEL USING CORRUPTED OUTPUT SAMPLES
text: We consider a single-layer ReLU NN. Let the weight matrix of the NN be denoted by W ∈ Rd×k and the bias vector by b ∈ Rd. The input to the NN is denoted by the latent variable z ∈ Rk. 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 a 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 et al. (2017). Thus, the output of the network is the random vector x ∈ Rd given by
x = ReLU(Wz + b), where z ∼ N (0, Ik), (1)
where N (0, Ik) denotes the Gaussian distribution with mean 0 and covariance matrix Ik which is the identity matrix of size k×k. Let the distribution of the random vector x be denoted byD(W,b). Then, our goal is to estimate the unknown parameters W and b of the distribution D(W,b) using
the knowledge of n output samples x1,x2, . . . ,xn. Here, we assume that a fraction of the samples are arbitrary outliers. The distribution of the observed samples are modeled using the Huber’s pcontamination model 1 defined as the following. Definition 2.1 (Huber’s p-Contamination Model Huber (1964)). The observed samples are said to be following Huber’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, Dp(W,b) given by
Dp(W,b) = pD(W,b) + (1− p)G. (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 b 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 ∈ Rd then exponentially large number of samples are required to estimate the bias. This holds true in our case as 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 a filtering technique. Note that the GD algorithm is similar to that in Wu et al. (2019) wherein the authors use the SGD algorithm. The proposed algorithm is presented in the next section.

heading: 3 ESTIMATION OF PARAMETERS OF SINGLE-LAYER NN
text: 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 W2 if W1W T 1 = W2W T 2 then there exists a unitary matrix Q such that W2 = W1Q. As z ∼ N (0, Ik), we have Qz ∼ N (0, Ik). Hence, for any vector b, we have D(W1,b) = D(W2,b) (Wu et al. (2019)). Since our goal is to learn the distribution, learning either W1 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 ∈ Rd×k and b ∈ Rd from the observed samples from Dp(W,b).
Next, we note that (i, j)-th entry ( WWT ) (i, j) of the symmetric matrix WWT is ‖W(i, : )‖2‖W(j, :)‖2 cos(θij), where θij = θji is the angle between vectors W(i, :) and W(j, :) which are the i-th and j-th rows of matrix W, respectively. Also, note that the `p norm of a vector is given by ‖x‖p = ( ∑ i |x(i)|p)1/p. Thus, we can construct the matrix WWT using the row norms {‖W(i, :)‖2}di=1 and angles {θij} d i,j=1.
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 ‖W(i, :)‖2 ∈ R and b(i) ∈ R, for i ∈ [d] = {1, 2, . . . , d}, suppose x ∼ D(W,b). Its i-th coordinate can be written as
x(i) = ReLU(W(i, :)Tz + b(i)), (3)
where W(i, :)Tz + b(i) ∼ N (b(i), ‖W(i, :)‖22). Thus, to compute b(i) and ‖W(i, :)‖22, 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 W(i, :)Tz + b(i) is negative. Consequently, we estimate b(i) and ‖W(i, :)‖22 using the positive entries of the observed samples. Hence, estimation of b(i) and ‖W(i, :)‖2 is equivalent to estimating the parameters of a one-dimensional normal distribution using positive samples, i.e., the samples that belong to the set R>0 := {x(i) ∈ R : x(i) > 0}. We use µ∗ = b(i) and σ∗2 = ‖W(i, :)‖2 to denote the parameters of this one-dimensional normal distribution. The estimation of µ∗ and σ∗2 using corrupted samples is discussed next.
1Our algorithm and its analysis follow even if the outliers are not sampled from the same arbitrary distributions G. However, we need to assume that all the true samples come from the same distribution D.
Algorithm 1: Learning one-layer ReLU NN with outliers Input: Samples x1, . . . ,xn ∈ Rd
1 for i ∈ [d] do 2 X>0 ← {xm,m ∈ [n] : xm(i) > 0} 3 v̂ = ProjGD(X>0) 4 Σ̂i,i ← 1/v̂(1) 5 b̂(i)← max{0, v̂(2)/v̂(1)} 6 for i < j ∈ [d] do 7 Compute θ̂ij using (11)
8 Σ̂(i, j)← √
Σ̂(i, i)Σ̂(j, j) cos(θ̂ij)
9 Σ̂(j, i)← Σ̂(i, j) Output: Σ̂ ∈ Rd×d, b̂ ∈ Rd
Algorithm 2: ProjGD Input: Samples X>0, Parameters T ,γt, and nb
1 Compute {xj(i)}nbj=1 from X>0 using (7) 2 g̃x ← filter ( {xj(i)}nbj=1 ) 3 v0 ← [0 0] 4 for t = 1, 2, . . . , T do 5 µ← vt−1(2)/vt−1(1) 6 σ2 ← 1/vt−1(1) 7 g̃z← [ −(σ̆2 + µ̆2)/2 µ̆ ]T using (5) and (6) 8 g̃t ← g̃x + g̃z 9 ṽt ← vt−1 − γt−1g̃t−1
10 vt ← P (ṽt) using (10) Output: vT ∈ R2
We determine the parameters of the univariate normal distribution using maximum likelihood estimation (Daskalakis et al. (2018)) given by arg minv `(v) where `(v) is the expected negative log-likelihood with respect to x(i) and v = [1/σ2;µ/σ2] ∈ R2. This optimization problem can be solved using a learning algorithm like GD or SGD. SGD utilizes only one sample for the gradient 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 et al. (2018)),∇`(v) = Ex,z[g(i)] where
g(i) = gx(i) + gz(i) = [ x2(i)/2 −x(i) ]T + [ −z2(i)/2 z(i) ]T . (4)
Here, x(i) ∼ N (µ∗, σ∗2;R>0) and z(i) ∼ N (µ, σ2;R>0). Also, µ∗ and σ∗2 are the parameters of the true distribution, and µ and σ2 are functions of v. In (4), Ez[gz(i)] admits a closed form expression (Johnson et al. (1995)), g̃z = Ez[gz(i)] = [ −(σ̆2 + µ̆2)/2 µ̆ ]T . Here, we define
µ̆ = E[z(i)|0 < z(i) <∞] = µ+ φ(−µ/σ) 1− Φ(−µ/σ) σ, (5)
σ̆2 = Var(z(i)|0 < z(i) <∞) = σ2 (
1− µ σ φ(−µ/σ) 1− Φ(−µ/σ)
− (
φ(−µ/σ) 1− Φ(−µ/σ)
)2) , (6)
where φ(·) and Φ(·) denote the probability density function and the cumulative distribution function of the standard normal distribution, respectively. We also need Ex[gx(i)] to compute Ex,z[g(i)]. Since the value of Ex[gx(i)] is not known, we use the sample mean to estimate Ex[gx(i)]. For this, all the positive samples are partitioned into nb batches. Let Sj be the j-th batch. We then compute the vector xj(i) ∈ R2 as follows:
xj(i) = 1 |Sj | [∑ x(i)∈Sj x(i) 2/2 − ∑ x(i)∈Sj x(i) ]T . (7)
We then combine the nb vectors {xj(i)}nbj=1 to estimate Ex,z[g(i)]. Recall that the observed samples are from the mixture distribution Dp(W,b). Therefore, to compute the expectation with respect to the true distribution D(W,b), a filter is applied on this set of nb vectors to mitigate the effect of the arbitrary outliers which is a common tool in the robust statistics literature and obtain Ex[gx(i)]. We consider two filters: median and trimmed mean.
Median: The median based filter possesses the following robustness property. Typically, a median is the value separating the higher half from the lower half of a given set of points. If more than half of a given set of points are in [−M,M ] for some M > 0, then their median must be in [−M,M ]. Thus, the median of {xj(i)}nbj=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 nb vectors with relatively large and small values and computes the estimate of Ex[gx(i)] as the mean of the remaining vectors.
Here, we use the parameter β to indicate the number of vectors to be discarded. This technique prunes the vectors xj(i), j ∈ [nb] that are computed from the batches with outliers having relatively high or low magnitudes. Therefore, we obtain the gradient estimate as
g̃(i) = g̃x(i) + g̃z(i) = filter ({ xj(i) }nb j=1 ) + [ (σ̆2 + µ̆2)/2 µ̆ ]T , (8)
where filter is either median or trimmed mean, and µ̆ and σ̆2 are given in (5) and (6), respectively.
Having computed the gradient estimate, we next present the proposed GD algorithm. In the t-th iteration, the algorithm performs the following three steps: The first step is Gradient Computation Step where the gradient g̃t ∈ R2 is computed from the observed positive samples using (8). The second step is Update Step where the gradient computed in the previous step is used to perform the GD update: ṽt = vt−1 − γt−1g̃t−1, (9) where γt−1 > 0 is the diminishing step size. The last step is Projection Step where the objective function l(v) is a strongly convex function of v, if v belongs to a bounded region. To control the strong-convexity of the objective function, we project the update vector v into the domain Dr ={ v ∈ R2 : 1/r ≤ v(1) ≤ r, |v(2)| ≤ r } . Thus, the projection is
P (v) = [min{max{v(1), 1/r}, r} min{max{v(2),−r}, r}] . (10) The GD algorithm is run for T iterations where T is the algorithm parameter. The overall algorithm is summarized in Algorithm 2. 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.
Finally, using the estimates b̂ and Σ̂ obtained using the GD algorithm, we estimate θ̂ij similar to Wu et al. (2019) using (Williamson & Shmoys, 2011, Lemma 6.7). Specifically, we have
θ̂ij = π − 2π
( 1
n n∑ m=1 1(xm(i) > b̂(i))1(xm(j) > b̂(j))
) , (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 1 where Σ̂ is the estimate of WWT. 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 a 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 1 of Algorithm 2 in Wu et al. (2019)). 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 in the next section.

heading: 4 THEORETICAL GUARANTEES FOR PARAMETER ESTIMATION
text: 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 in 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 to 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 at the main result, we first present the error bounds for the two steps of Algorithm 1, 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 η-strongly-convex and L-smooth, and we show that the parameters η, L are functions of r. Using the properties of the objective function, we the bound on the error between the true gradient ∇l(v) and the estimated gradient g̃t computed from the output samples with arbitrary outliers, obtained in terms of parameter . This bound leads to the following result that shows that
we can estimate b(i) within an additive error of Ξ‖W(i, :)‖ and Σ(i, i) within an additive error of Ξ‖W(i, :)‖2 where Ξ is a function of the above parameters. Proposition 4.1. Suppose we initialize the projected gradient step (Algorithm 2) such that ‖v0 − v∗‖ = V and choose the step size γt = γ and the number of iterations as T . Then, there exists γ > 0 such that for any δ, ∈ (0, 1), the output (Σ̂(i, i), b̂(i)) of the projected GD step of our algorithm with median-based filter for any i ∈ [d] satisfies
|Σ̂(i, i)− ‖W(i, :)‖2| ≤ Ξ‖W(i, :)‖2 and |b̂(i)− b(i)| ≤ Ξ‖W(i, :)‖, (12)
with probability at least 1 − δ if the number of data samples n ≥ 1p2(pΨ −1/2)2 log 1 δ . Here, the error bound is Ξ = V ( 1− Lη+L )T + 2 (L+η)Lη with η, L > 0 being constants that depend only on the parameter r. Also, p is the probability of a sample being uncorrupted and Ψ ∈ [1/2p, 1] is such that O( 3) ≤ Ψ ≤ O( √ ) with > O ( p−1/3 ) where the order constants depend only on r.
The two terms in the error bound Ξ in Proposition 4.1 can be interpreted as the following. The first term V ( 1− Lη+L )T captures the convergence error due to the GD algorithm. For any upper
bound on the convergence error Ω > 0, Algorithm 1 runs in time (log Ω− log V )/ log (
η η+L
) . This
relation shows that smaller convergence errors require more iterations. The second term 2 (L+η)Lη 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 Ψ which is the probability of a sample being uncorrupted deviating from its mean and variance by and as Ψ ≤ O( √ ). Consequently, for smaller error , we need a large number of samples n = Ω( 1 p4 log d δ ). We also note that the lower bound on decreases with p.
The following proposition bounds the estimation error in the second step, i.e., the estimation of the angle between any two row vectors W(i, :) and W(j, :) (where i 6= j ∈ [d]). The result shows that we can estimate θij within an additive error of Ξ. Proposition 4.2. Assume that (12) holds. Then, for a fixed pair of i 6= j ∈ [d] and δ, ∈ (0, 1), the estimate θ̂ij of Algorithm 1 that uses a median-based filter satisfies
| cos θ̂ij − cos θij | < √ 2πp(pΨ − 1/2) + 3π(1− p) + 2π(2− p)Ξ, (13)
with probability at least 1 − δ if the number of data samples n ≥ 1p2(pΨ −1/2)2 log 1 δ . Here, the error bound is Ξ = V ( 1− Lη+L )T + 2 (L+η)Lη with η, L > 0 being constants that depend only on the parameter r. Also, p is the probability of a sample being uncorrupted and Ψ ∈ [1/2p, 1] is such that O( 3) ≤ Ψ ≤ O( √ ) with > O ( 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, Σ(i, i), for i ∈ [d] are obtained from Proposition 4.1. Further, the off-diagonal entries of Σ are obtained by combining the Propositions 4.1 and 4.2 to obtain the final result as follows: Theorem 4.3. Suppose we initialize the projected gradient step (Algorithm 2 with median-based filter) such that ‖v0 − v∗‖ = V and choose the step size γt = γ and the number of iterations as T . Then, there exists γ > 0 such that for δ, ∈ (0, 1), the output of Algorithm 1, (Σ̂, b̂) satisfies
‖Σ̂−WWT‖F ≤ (√ 2πp(pΨ − 1/2) + π(2− p)(3 + 2Ξ) ) ‖W‖2F (14)
‖b̂− b‖ ≤ Ξ‖W‖F , (15)
with probability at least 1 − δ if the number of data samples n = Ω( 1 p4 log d δ ). Here, p is the probability of a sample being uncorrupted and Ψ ∈ [1/2p, 1] is such that O( 3) ≤ Ψ ≤ O( √ )
with > O ( p−1/3 ) where the order constants depend only on r.
We note that in Propositions 4.1 and 4.2, and Theorem 4.3, η, L and the other order constants depend on the parameter r > 0. Recall that the parameter r is required for the convexity region Dr and we can choose r to be a large constant. Thus, r is a relatively insensitive parameter which does not require any hand-tuning.
As the probability of a sample being uncorrupted p 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 are 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 ζ, δ ∈ (0, 1), the number of samples n = O( 1ζ2 log d δ ) are sufficient for the SGD algorithm in Wu et al. (2019) to achieve the following error bounds with probability at least 1− 2δ,
‖Σ̂−WWT‖F ≤ ζ‖W‖2F and ‖b̂− b‖ ≤ ζ‖W‖F , (16) where ζ indicates the parameter estimation error. Comparing the above bounds with (14) and (15), we observe that our bounds are larger due to the presence of arbitrary outliers. In particular, Ξ
consists of two error terms. The first term V ( 1− Lη+L )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+η) Lη quantifies the error due to the gradient estimated from the output samples with arbitrary outliers and is not present in (16). Additionally, in (14), the extra term 3π(2 − 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 (14) and (15). Further, our sample complexity depends on the probability of a 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.

heading: 5 SIMULATION RESULTS
text: 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 a 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 D(W,b) with probability p and from G = N (5, 1) with probability 1− p. The hyperparameters in our proposed algorithm are set as r = 3 and γt = 10.1t . We use the batch-splitting approach to 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 |X>0|/100 where |X>0| 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 a 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>0 for the number of iterations as they do not convey any information about the row norms of W and bias vector b.
We compute two error metrics from the estimated parameters and the ground truth, ‖Σ̂ − WWT‖F /‖W‖2F and ‖b̂−b‖2/‖W‖F . Also, we compare our algorithm with two other schemes: oracle scheme (estimation using the true samples only), and scheme without filter.
The results are shown in Figs. 1 and 2, and Table 1, and the observations from them are as follows.
Effect of filters: From Fig. 2, we observe that the GD schemes perform better than the corresponding SGD schemes. Further, the performance is improved when we use median based filter along with GD or SGD (for instance, as 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. 1, we also infer that the median-based approach performs slightly better than the trimmed mean-based approach.
Dependence on probability of a sample being uncorrupted p: The variation in the error estimation as a function of p is shown in Figs. 1a 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
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 a monotonic behavior with p. This observation shows that these schemes are not able to handle the outliers effectively. Further, all the schemes converge to 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 n. 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 d: In Figs. 1c and 2c, we plot the error in 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 effect of outliers. However, we observe a 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 1, 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 in 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 medianbased filter is computationally more efficient while offering similar or lower estimation error. Moreover, the median-based scheme is parameter free (the trimmed mean depends on the parameter β) and enjoys strong theoretical guarantees (see Theorem 4.3). Overall, the median-based GD algorithm 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.

heading: 6 CONCLUSION
text: 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 to be an arbitrary outlier with a fixed probability. Our only assumption was that the bias vector was nonnegative. 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-negativity assumption on the bias vector is a promising direction for future work. Also, extending our results to multi-layer neural networks is also an interesting problem to consider in the future.

Review summaries:
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.   The approach involves two steps:  * estimating row-wise weight norms using gradient descent with median/trimmed mean gradients. * estimating angles between rows using standard properties of inner products with Gaussian vectors.  

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.   

Given observations $x_1, \cdots, x_n$ assume that a fraction $p$ of the observations are drawn from  $$ x = ReLU(Wz + b), \text{ where } z \sim N(0, I_k) $$ and the rest are drawn from an arbitrary distribution $\mathcal{G}.$  The authors study the problem of estimating $W, b$ in this model.  They assume that $b$ has non-negative entries.  The authors separate the problem in two parts:  * estimate $\| W(i,:) \|, b_i$ from the $i$th coordinates of the observations * estimate the angles between the rows of $W$  They use a gradient descent algorithm for the first part and use a clever random projections based idea for the second part.  They derive error bounds of their method and demonstrate the performance of their method through simulations.