Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

This 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.
strengths_and_weaknesses: Strengths:
- 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).

Weaknesses:
- 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.

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

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

- Please comment on the non-independence of the gradients after the first iteration.
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

They 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.
strengths_and_weaknesses: Strengths:

The authors establish a clean result on robust learning of 1 layer generative models with ReLU activations.

The paper is well written and easy to understand.

The authors present empirical evaluations.

Weaknesses:

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

One way to improve the paper would be to discuss lower bounds based on the outlier fraction.

Minor Issues:

242: There is a missing reference.

The theorems are not in latex theorem blocks, which makes it hard to isolate them from the surrounding text.
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.

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

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

References:

Wu, Shanshan, Alexandros G. Dimakis, and Sujay Sanghavi. "Learning distributions generated by one-layer ReLU networks." Advances in neural information processing systems 32 (2019).
strengths_and_weaknesses: Strengths:

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

Weakness:

1) 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. 

2) Most of the techniques in Robust statistics literature also works for more powerful adversaries. Do these methods go through for those adversaries?

3) Is there an equivalent of Corollary 1 in Wu et al. 2019 that can be obtained here, that connects the TV distances?

4) The experiments here are performed for very low dimensions upto 20, which is not as enlightening. 

5) Most of the techniques are a combination of Wu et al. 2019 and Daskalakis et al. 2018.

UPDATE:
After 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.

References:

Daskalakis, Constantinos, et al. "Efficient statistics, in high dimensions, from truncated samples." 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018.

Wu, 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.

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

Meta-review: metareview: This paper learns the distributions created by single layer ReLU generative models. The paper extends previous work on this problem in the presence of outliers under Huber's contamination model. 

The key innovation of the new algorithm is the use of robust estimation and its combination with the previous method to robustify it. The authors argued about the technical issues that arise in robustifying the work of Wu et al. and did a good job in addressing all the reviewer comments. 

This paper is novel, well written and well motivated.
Unfortunately the problem setting is still narrow because the authors can only learn single layer generative models, but still this turns out to be non-trivial. The proposed solution involves solid technical contributions that were well explained. 

confidence: Certain
Decision: Accept