Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The author(s) propose a computationally efficient mean estimator for generative distribution that are "heavy-tailed" in nature. The phenomenon of heavy tailed distributions for gradients in the training stage of generative models are common in nature and the proposed method aims to alleviate this problem by constructing a robust gradient estimator in such situation. The proposed methodology is well backed up by synthetic and real data examples. The topic is interesting and the proposed methodology is novel.

I have the following queries for the author(s)

-In the definition of bounded 2K-moments why the vector v needs to be in a (p-1) dimensional sphere? Is it necessary for the vector to be rotationally invariant?

-Along the lines of the first query, does the definition of bounded 2K-moment has any relation with sub-gaussian moment condition?

-In the streaming filterpd algorithm (Algorithm 3) how robust is the rank-1 approximation of C_{t-1} by the leading eigen-pair?

-I am a bit skeptical with the bounded 8th moment condition in the linear model example?

-In theorem 2 do you allow dimension p to grow or is the result not tenable for the high dimensional case?

- It would be interesting to see an experiment between RGD-GMOM and RGD-Filterpd under different signal-to-noise ratio for heavy tailed mean estimation in the linear regression setting.


review_title: A good paper and marginally above acceptance threshold

final_score: rating: 6: Marginally above acceptance threshold
review_content: I thank the authors for their detailed reviews. I have updated my score

---

The submission presents a robust estimator for the mean of heavy-tailed distributions for application to neural network training. Understanding and dealing with the distribution of the noise in stochastic optimization for machine learning is relevant to both practical and theoretical aspects of machine learning and relevant to the ICLR community.

The main weakness of the submission is a lack of clarity in the contributions and presentation. Key statements are vague, basic notation is not defined and the writing and supporting figures would benefit from an additional pass. More details below.

My initial recommending is towards a rejection. I think the paper needs major revisions to improve the presentation rather than a set of minor improvements that are easily fixed. But I am open to increase my score depending on the results of the discussion period if the issues below are addressed.

**Major issues**

* Unclear theoretical contributions.

  It is unclear from Section 2 whether the proposed algorithm and Theorem 1 are novel theoretical contributions or $\epsilon$-modification to existing work, such as the works of Diakonikolas et al. and Lugosi et al., that is more amenable to. Either are valuable contributions, but this needs to be made clear. If Thm. 1 is a significant theoretical contribution, the theoretical novely needs to be expanded upon and the differences with existing work made explicit. If the results are straightforward from existing theory but Alg. 1 more convenient for applications, the issues with existing estimators need to be clearly highlighted

* Basic notation is not defined. I could only infer the following by reading referenced material
  
  * the dimensionality $p$ (p.2 or Eq. 3)
  * the unit ball $\mathcal{S}^p$ (p. 2)
  * an outer product $(v)^{\otimes 2}$ (Alg. 1)
  * a constraint set $\Theta$ (Alg. 2)
  * the constant $d^2$ (Thm. 2, Eq. 5) is still mysterious

* Clarity about the heuristic nature of Alg. 3.

  There is nothing wrong with simplifications to allow the method to scale to large datasets, even if at the cost of some rigor. But the section needs to make clear that the simplifications are heuristic in nature, and not attempt to cover it with technical but wrong language. Eg: "reusing previous gradient samples to improve concentration" (p. 6) is inaccurate as the samples are not independent.
"it is unreasonable to expect that [the distribution of gradients] are vastly different in most cases, due to the smoothness of the objective" (p. 6) Reasonability is subjective, and the presented argument is wrong. Neural network objectives are most often non-smooth. This holds whether smoothness refers to differentiability, due to ReLU activations, or the Lipschitzness of the function or the gradient due to multiple layers.

**Minor comments:**

* The figures need additional work as they are currently unreadable when printed.
* The writing needs improvement, as some sentences are incomplete or contain duplicated words. Eg "This eigenpair is not required to be recomputed the current iteration" (p. 6), "sufficiently large enough" (remarks), "achieves the the optimal sub-Gaussian" (remarks)
* Some of the cited preprints have been published (eg Che et al., Cherapanamjeri et al.). Please make sure your references are accurate and up-to-date.
review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: 

## Summary

The paper studies the problem of high-probability mean estimation for heavy-tailed distributions, i.e., constructing a high-probability confidence intervals for the mean, when the underlying distribution has only finite low-degree moments.  The paper motivates this problem from the view-point of machine learning algorithms, where the gradients are heavy-tailed. 	Especially in deep generative networks, the paper  highlights the heavy-tailed nature of gradients via experiments. On a theoretical side, the paper derives bounds for mean estimation when the distribution has bounded fourth-moments.

--- 
## Pros

+ The paper highlights the heavy-tailed nature of gradients in the intermediate stage of training deep generative models via experiments.
+ The paper derives theoretical bounds for their mean estimation algorithm, and then applies it to study generalized models via gradient aggregation.
+ A streaming heuristic of Algorithm 1 is proposed that has promising results in experiments.

---
## Cons

The key concern is that despite several claims of "near-optimality" in the paper, the theoretical results in the paper are significantly lacking in the sample complexity (I understand the rates are subgaussian after this stringent sample complexity is satisfied). Please see below for detailed comments on mean estimation and linear regression.

**Mean estimation**
+ Theorem 1 requires the sample complexity of $n \geq r^2(\Sigma) \log(1/\delta)$ (and a bounded 4-th moment condition), whereas the "true subgaussian bound" has a sample complexity of only $n \geq \log(1/\delta)$ without any higher moments. 
+ This difference is considerable, especially, in high-dimensions, which is the focus of this work. For example, a typical example is when $r(\Sigma) = p$ and $\delta = 2^{-p}$ (high-probability confidence typically required for union bound over covers), Theorem 1 requires $n \geq p^3$, whereas the information-theoretically optimal is only $n \geq p$.
- As a result, the theoretical results in Theorem 1 are not even applicable in several interesting modern regimes, including the experiments in this paper. I am thus skeptical of the recurring claim of near-optimality of Theorem 1 in the paper (abstract, Section 2 heading, etc. ).
- As mentioned in Appendix, without any higher-moments assumption, the rates in Theorem 1 are worse than GMOM. A more thorough comparison of Theorem 1 with GMOM should be added (preferably in the main text). For example, even though the error in GMOM is large, the sample complexity is dimension-independent.	
- The results should also be compared with the paper Diakonikolas, Kane, Pensia (see below), where the algorithm doesn't seem to require more hyperparameters than Algorithm 1 (which is claimed to be as the primary shortcoming of prior works and motivation for Theorem 1).

**Linear Regression**:
- The aforementioned drawbacks in Theorem 1 are also reflected in Theorem 2, when the mean-estimation sub-routine is applied to linear regression.Again, I believe that the claim of "near-optimality" is somewhat misleading. In the same parameter regime of \delta = 2^{-p}, the sample complexity in Theorem 2 is at least $n \geq p^3$, compared to the optimal of $n \geq p$ given in Lugosi and Mendelson, 2016 (see below for reference).
- Cherapanamjeri et al. (2019b) (CHKRT) is discussed in Appendix B.2, but I believe their results have been misrepresented. Again considering the parameter regime of $\delta = 2^{-p}$, the sample complexity of Theorem 2 is at least $n\geq p^3$, which is incorrectly stated in Appendix as $p^2$ (Please let me know if I miscalculated the sample complexity of Theorem 2).
- In general, the sample complexity in [CHKRT, Theorem 5.1] is $p\sqrt{\log(1/ \delta)}$ as compared to $p^2 \log(1/\delta)$ in Theorem 2. Thus I believe the claim of "best known result" in the remark after Theorem 2 is incorrect (see also Depersion, 2020). 
- Moreover, the sample complexity in Thm. 2 increases with $T$, and $T$ depends on $|| \theta^* ||$ (which has been hidden in $O(.)$ notation in Appendix B.2).  This is in stark contrast with results in CHKRT, where only the time complexity (and not sample complexity) depends on $||\theta^*||$. Actually, they use OLS to warm-start their algorithm, reducing their running time to linear independent of $||\theta^*||$. But doing the same here, would further increase the sample-complexity in Theorem 2.
- Theorem 2 should also be compared with the paper Depersin (2020) (see below), preferably, in the main paper. 

---
## Score

Overall, I vote for rejection. The current theoretical results (Theorem 1 and Theorem 2) have significantly large sample complexity, and do not explain the experimental results of the paper ($n = O(p)$ and $ r(\Sigma) = p$ in experiments). The significance of these shortcomings are also not discussed in the main text, where the results are repeatedly claimed as near-optimal. I liked the experiments in the paper but they are currently not extensive for an acceptance on its own. Perhaps authors can focus more on the experiments in a resubmission.


---
### Other major comments

**Streaming algorithm, Section 4**

+ *Moreover, it is not viable to run* $T^*$ *leading eigenvector computations for models with millions of parameters, since the time complexity of this operation is proportional to* $p$.  
I am confused by this statement: even the simple baseline of sample mean would have time complexity of np. This line should be clarified.
+ *Recall that in Filterpd, we require to compute 1)* $ T^*$ *covariances and 2)* $T^*$ *leading eigenpairs*  
This line implies that the filter algorithm needs to calculate these covariance matrices explicitly. As the prior work as shown (see, for e.g., Lei et al. (2019) and Depersin and Lecue (2019)), a simple power iteration can be used which only requires dot products (achievable $O(np)$ time). This is a standard procedure in this literature. 
+ In experiments with Streaming-Filterpd, the runtime (wall-clock time) should also be reported with respect to baselines (Mean, Clip, NrmRmv). 
+ Seeing that the performance of GMOM closely matches the performance of Filterpd in Figure 3 and simplicity of computing GMOM, I would like to see the comparison of GMOM with Streaming-Filterpd in Table 1 and Figure 4.


---
### Other minor comments

+ The claims of near-optimality should be replaced with something objective.
+ For an $\alpha^*$-heavy-tailed distribution, the quantity $E X^{\alpha}$ only exists if $\alpha$ is "strictly" less than $\alpha^*$. The equality should be removed from the paragraph below Definition 1.
+ The citation to Minsker (2015) before Eq. (2) should be modified: in the current form, the text suggests that the Minsker (2015) showed a lower bound on the sub-optimality of GMOM.
+ I am not sure if citation to Catoni and Giulini (2007) is correct. The bounds in that paper were not *truly subgaussian* as the results depended on the raw moments of the distribution.
+ The paper uses $d$ and $p$ interchangeably. For example, Eq. (5) has both, but only $p$ is defined.
+ It is a bit confusing to use T in Algorithm 3, where T is the iteration number of optimization algorithm vs T^* in Algorithm 1 which is the parameter of sub-routine.
+ Figure 3 (c): It seems that the dependence on $p$ is linear as opposed to $\sqrt{p}$. Is there a reason for this?
+ Section 4: "This eigenpair is not required to be recomputed the current iteration"
+ Section 5: "For comparison, we other DCGANs with the same initialization" 
+ as -> are on Page 2: "This is because sample mean estimates as ..."

---
### Other References:

Ilias Diakonikolas, Daniel Kane, Ankit Pensia. Outlier Robust Mean Estimation with Subgaussian Rates via Stability. 2020.
Jules Depersin. A spectral algorithm for robust regression with subgaussian rates. 2020.
Gabor Lugosi and Shahar Mendelson. Risk Minimization by Median-of-Means Tournaments. 2016. 
There are other recent works for both mean estimation and linear regression, but they were made public after the ICLR guideline of Aug 2, 2020.

review_title: Interesting experiments but sub-optimal theoretical results

final_score: rating: 6: Marginally above acceptance threshold
review_content: In summary, this paper proposes a novel estimator for the mean estimation of heavy-tailed distribution. 

In general, I think this paper makes a good contribution. However, my major concern is that I am missing an important metric for the experiments: the running time. In my view, the authors *must* report the running time of their algorithm and others to make a fair comparison.

In the synthetic experiment, it would be good to include the Streaming - Filterpd algorithm as well so we can compare it with the usual Filterpd, in terms of both accuracy and running time. The author mentioned "at least 4X speed up", but we didn't see the numbers in experiments.

The key part in Algorithm 1 is to discard samples according to their score as in Step 5. It would be good to provide more intuitions for this step. Why the samples with the large score are not good and why discarding them improve the performance? Also, what if we discard a few samples with the largest score instead of randomly select samples? Would that be worse than the current randomized algorithm and why is that?

In theorem 2, what is $d$? I believe it is not the same as the $d$ in Algorithm 3. Is that a similar quantity as $r(\Sigma)$ in equation (3)? Here if $\Sigma = I_p$, then $r(\Sigma) = p$, so the sample complexity is more than p^2 in Theorem 2? It would also be helpful to clearly state that $\theta \in R^p$ at an early stage.

In the line just above Algorithm 1, it is claimed that other methods are impractical because "they have several hyperparameters". This is not convincing. Lasso also has hyperparameters but it does not limit its usage. 

In Section 3 when talking about $\alpha$, it might be better to be more quantitative. It is mentioned that the $\alpha$-index is close to 2 when samples are close to Gaussian. How close? I think 1.85 as in Figure 2(a) and 2(b) is also close to 2.

Step 2 in Algorithm 2: the "$log(\delta/T)$" should be a typo, is that "$log(T/\delta)$" instead?
review_title: This paper seems to make reasonable contribution. I am missing running time in experiments

Meta-review: This paper studies the problem of multivariate mean estimation with a focus on the heavy-tailed setting.
The authors give an algorithm for this estimation task and then use it (in essentially a black-box manner) to obtain heavy-tailed
estimators for various supervised learning tasks. As pointed out by one of the reviewers and my own reading, the theoretical
contributions of the paper are weak and are subsumed by related work (some of which is not cited in the submission). 
More generally, the extensive recent literature on the topic is not accurately represented in both the submission itself and the response to the reviewers comments. On the other hand, the experimental results of the paper hold some promise. However, at this stage, these experimental contributions by themselves are in my opinion insufficient to merit acceptance.


Decision: Reject