Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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.
- 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.
- 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_review: I would make a recommendation for rejecting this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 

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.


main_review: Strengths
+ The paper is well written.
+ The techniques in this paper are fairly natural and intuitive (for the specific assumptions made in this paper -- see below.)
+ The results make sense and are consistent with existing results for learning single-layer NNs without outliers.

Weaknesses
- 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.
- 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?)
- 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? 
- 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.

---
Thanks for the response. Keeping score unchanged.
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: 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.
 
 
 
 
main_review: 
* 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)$.
* In Figure 1(b), the errors for GD with filters do not decrease with increasing sample size. Why is that?
* 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?
 
 
Minor:
* 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$? 
* 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. 
 
 



summary_of_the_review: The error bounds do not seem tight and there are some concerning issues with their simulations.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.  

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.

A few concrete comments I'm hoping the authors can address:

(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.  

(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.  

(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.  

For 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? 

(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.


Some other minor comments/typos encountered while reading:

* p.1, "...datasets impacted by a Byzantine" -- not sure what this refers to?

* p.2, "adversial"

* p.3, "RVe x"

* Regarding the assumption that the bias is negative: Claim 2 of Wu et al. shows that having negative bias would require exponential sample complexity.

* Where is \tilde g_x defined in algorithm 2?

*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?  

* In the appendix, g_t appears everywhere but seems to refer to \tilde g_t.  Are these the same?



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.
review_title: null

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