Efficient Estimators for Heavy-Tailed Machine Learning
Authors: Vishwak Srinivasan
Adarsh Prasad
Sivaraman Balakrishnan
Pradeep Kumar Ravikumar
Venue:  (2021)

Abstract: A dramatic improvement in data collection technologies has aided in procuring massive amounts of unstructured and heterogeneous datasets. This has consequently led to a prevalence of heavy-tailed distributions across a broad range of tasks in machine learning. In this work, we perform thorough empirical studies to show that modern machine learning models such as generative adversarial networks and invertible flow models are plagued with such ill-behaved distributions during the phase of training them. To alleviate this problem, we develop a computationally-efficient estimator for mean estimation with provable guarantees which can handle such ill-behaved distributions. We provide specific consequences of our theory for supervised learning tasks such as linear regression and generalized linear models. Furthermore, we study the performance of our algorithm on synthetic tasks and real-world experiments and show that our methods convincingly outperform a variety of practical baselines.

Under review as a conference paper at ICLR 2021
EFFICIENT ESTIMATORS FOR HEAVY-TAILED MACHINE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
A dramatic improvement in data collection technologies has aided in procuring massive amounts of unstructured and heterogeneous datasets. This has conse- quently led to a prevalence of heavy-tailed distributions across broad range of tasks in machine learning. In this work, we perform thorough empirical stud- ies to show that modern machine learning models such as generative adversarial networks and invertible flow models are plagued with such ill-behaved distribu- tions during the phase of training them. To alleviate this problem, we develop a computationalll-effiiies tees which can handle such ill-behaved distributions. We provide specific conse- quences of our theory for supervised learning tasks such linear regression and generalized linear models. Furthermore, we study the performance our algo- rithm synthetic tasks and real-world experiments and show that our methods convincingly outperform a variety of practical baselines.
estimator for mean estimation with provable guaran-
INTRODUCTION
Existing estimators in machine learning are largely designed for "thin-tailed" data, such as those coming from Gaussian distribution. Past work in statistical estimation has given sufficient evidence that in the absence of these "thin-tails", classical estimators based on minimizing the empirical error perform poorly (Catoni, 2012; Lugosi al., 2019). Theoretical guarantees for methods commonly used in machine learning usually place assumptions on the tails of the underlying distributions that are analyzed. For instance, rates of convergences proven for a variety of stochastic optimization procedures assume that the distribution of gradients have bounded variance (for c.g., Zou et al. (2018)) or in some cases are sub- Sab-Gaussian (for c.g., Li & Orabona (2019)). Thus, these guarantees no longer applicable for heavy-tailed gradient distributions.
From a practical point of view however, this is a less than desirable state of affairs: heavy-tailed distributions ubiquitous in variety of fields including large scale biological datasets and finan- cial datasets among others (Fan et al., 2016; Zhou et al., 2017: Fan et al., 2017). While this may be argued as just artifacts of the domain, recent work has found interesting evidence of heavy-tailed distributions in the intermediate outputs of machine learning algorithms. Specifically, recent work by Simsekli et al. (2019) and Zhang et al. (2019) have provided empirical evidence about the ex- istence of such heavy-tailed distributions, especially during neural network training for supervised learning tasks.
Following these empirical analyses of Simsekli et al. (2019) and Zhang et al. (2019), we look for sources of heavy-tailed gradients arising during the training of modern generative model based unsu- pervised learning tasks as well. In our preliminary investigation, we noticed that the distribution of gradient norms i.e., ||ge||2 are indeed heavy-tailed. These are showcased in Figure 1; Figures and lb show the distribution of gradient norms obtained while training the generator of a DCGAN (Rad- ford et al., 2015) and Real- NVV (Dinh et al., 2016) on the CIFAR-10 10 dataset, respectively. These distributions noticeably heavy-tailed, especially when juxtaposed with those obtained from Gaussian distribution (Figure Ic). We discuss more about the empirical setup in Section 5.2.
Interestingly, in all the supervised and unsupervised machine learning problems discussed above, merely need to compute expectations of these varied random heavy-tailed quantitics. For instance, mini-batch gradient descent involves aggregating batch of gradients pertaining to each sample in

---

Under review as a conference paper at ICLR 2021
08
(a) DCGAN
(h) Real -VP
(c) Gaussian
(d) a-stable
Figure I: Distribution of sampled gradient norms while training DCGAN (a) and Real-NVE (b) on the CIFAR-10 dataset. (c) Distribution of norms of Gaussian random vectors and (d) Distribution of norms of a-stable random vectors with a = 1.95. X-axis: norm, Y-axis: Density.
the mini-batch. Typically, this aggregation is performed by considering the sample mean, and this is a reasonable choice due to its simplicity as an estimate of the expectation of the random gradient.
For computing the mean of such heavy-tailed gradient distributions, the sample mean however is highly sub-optimal. This is because sample mean estimates are greatly skewed by samples on the tail. Thus gradient estimates using these sub-optimal sample means of gradients do not necessarily point in the right direction leading to bad solutions, prolonged training time, or mixture both. Thus, a critical requirement for training of modern machine learning models is scalable estimation of the mean of heavy-tailed random vector. Note that such computations gradients done in each iteration of (stochastic) gradient descent, that require that the heavy-tailed mean estimation be extremely scalable, yet with strong guarantees. Note that once we have such scalable heavy-tailed mean estimator, could simply use compute robust gradient estimates Prasad et al. (2020). and learn generic statistical models.
mean of sample
We summarize contributions follows:
We extend recent analyses of heavy-tailed behavior in machine learning, and provide novel em- pirical evidence of heavy-tailed gradients while training modern generative models such gen- erative adversarial networks (GANs) and invertible flow models.
combat the issue of aggregating gradient samples from heavy-tailed distribution, we propose practical and tasy-to-implemen algorithm for heavy-tailed mean estimation with provable guarantees on the error of the estimate.
We the proposed mean estimator to compute robust gradient estimates, which allows us to learn generalized linear models in the heavy-tailed setting, with strong guarantees on the estimation errors.
Finally, we propose a heuristic approximation of the mean estimation algorithm, which scales to random vectors with millions of variables. Accordingly, we use this heuristic compute robust gradients of large-scale deep learning models with millions of parameters. We show that training with this heuristic outperforms a variety of practical baselines.
Notation and other definitions. Let be random vector with mean μ.. We say that the x has bounded 2k-mooenns if for all E SP-1 (unit ball), BB((" (x===))) < Cz. (E((""(r ())))(())))))))))) =*) Throughout the paper, we use c, C1, .2...., C, C1, C2,... to denote positive universal constants.
EFFICIENT AND PRACTICAL MEAN ESTIMATION
We begin by formalizing the notion of heavy-tailed distributions.
Definition 1 (Heavy-Tailed Distribution (Resnick, 2007)). A non-negative random variable X is called heavy-tailed if the tail probability P(X > t) is asymptotically proportional to t t-a", where a" is positive constant called the tail index of X.
Intuitively, this definition states that if the tail of the distribution P(X t) decreases at rate slower that -t, then the distribution is heavy-tailed. An interesting consequence of this definition is the non-existence of higher order moments. Specifically, one can show that the quantity X finite for any a if and only if a < a" and X is heavy-tailed random variable with tail index a.. In recent statistical estimation literature (for e.g.. Minsker (2015); Hopkins (2018); Lugosi & Mendelson (2019)), heavy-tailed distributions are defined by the absence of finite higher order moments.
2

---

Under review as a conference paper at ICLR 2021
In the heavy-tailed mean estimation task, observe samples ..,..., In drawn independently from a distribution P where 2; E RR, which is only assumed to have finite low-order moments, therefore heavy-tailed. The goal of past work (Catoni, 2012; Minsker, 2015; Lugosi et al., 2019; Catoni & Giulini, 2017) has been design an estimator 0n of the true mean μ of which has small eg-error with high-pret probbbbbbbbbtt....
As benchmark for estimators in the heavy-tailed model, we observe that when P the multivariate normal (or equivalently a uub-Gaussian) distribution with mean μ and covariance Σ, the sample mean Fr = 1/1 E; Ty satisfies, with probability at least 8::
M - 1ll2 trace (2)) |E log(1/6) def *PT,,
71
Seminal work by Catoni (2012) showed that the sample mean is extremely sub-optimal, while more recent work by Lugosi et al. (2019) showed that the sub-Gaussian error bound achiev- able while only assuming that P has finite variance i.e., 2nd moment. In the multivariate setting, Minsker (2015) showed that the extremely practical coometric-median -f-nns estimator (GMOM) achieves a sub-optimal error bound by showing that with probability least 1 8:
|0Mom,5 - -11l2 - V /rrace (E) log(1/6)
(2)
Computationally intractable estimators that truly achieve the sub-Gaussian error bound were pro- posed by Lugosi et al. (2019); Catoni & Giulini (2017). Hopkins (2018) and later Cherapanamjeri et al. (2019) developed a sum-of-squares based relaxation of the estimator Lugosi et al. (2019), thereby giving a polynomial time algorithm which achieves optimal rates. More recent work has studied the problem of mean estimation, focusing on constructing theoretically fast polynomial time estimators (Dong et al., 2019; Lugosi & Mendelson, 2019; Diakonikolas & Kane, 2019; Lei al., 2020; Lecué & Depersin, 2019). However, these estimators have several hyperparameters, which require be tuned for practice, making them impractical.
Now, we present our algo- rithm Filterpd for heavy-tailed mean estimation, and is for- mally stated as Algorithm 1. proceeds in iterative fash- ion, by (1) computing the lead- ing eigenvector of the empir- ical covariance matrix (Step (3)), (2) projecting points along this leading eigenvector (Step (4)), and (3) randomly sampling points based on their projection scores (Step (5) and (6)). This procedure is repeated for fixed number steps.
Algorithm Filterpd Heavy Tailed Mean Estimator
Require: Samples S = {2 Iterations T 1: for = 1 to T do
Is| and Ex
[S|
2: Compute Ōg
(z.
0z) 82
S
[
i=1
Let be the leading eigenvector of Eis def
4: For each 2,, let
oF (z: 0s) be its score.
5: Sample a point 2 ~ according to Pr(x;) x
6: Remove sample from S i.e. S = S (z)
7: end for
8: return
S Σ
Our proposed algorithm is primarily based on the SVD-based filtering algorithm, which has ap- peared in different forms (Klivans et al., 2009; Awasthi et al., 2014) and was recently reused in Diakonikolas et al. (2016; 2017) for adversarial mean estimation. For instance, the algorithm in Diakonikolas et al. (2017) follows similar procedure, but remove subset of points at step de- pending on magnitude the projection score.
Our first main result is presented as follows:
Theorem 1. Suppose {2 P with 2, E TRP for all i, where P has bounded 4th moment and satisfies
log" 1p/8()/)
trace (2)
2 Cr2
r(E)
(3)
log(1/8)
Σ
'erre and throughout our paper use the notation S denote inequality with universal constants dropped for conciseness.
3

---

Under review as a conference paper at ICLR 2021
Then, Filterpd when instantiated for T log(1/8) steps returns estimate 85 which satisfies with probability at least 46, 6 E (0, 0.2).))
100 مال 2 O.
Remarks: Theorem shows that when n is sufficiently large, Filterpd returns a mean estimate that achieves the optimal aub-Gaussian deviation bound. This algorithm also extremely practical as compared to existing algorithms (for e.g., Lei et al. (2020)) and engenders development of scalable variants, which we later describe in Section 4. We defer the proofs of Theorem the appendix.
2.1 PROVABLE ALGORITHMS FOR GENERALIZED LINEAR MODELS
At this stage, with an optimal mean estimator in hand, we explore its consequences for general supervised learning tasks, namely linear regression and generalized linear models. The goal is to design efficient estimators which work well in the presence of heavy-tailed data. To this end, we borrow the robust gradient framework in Prasad et al. (2020) and present it in Algorithm 2. In par- ticular, RGD Filterpd proceeds by passing the gradients at the current iterate of through Filterpd Step (5).
Note that Prasad et al. (2020) used similar algorithm in their work, but used GMOM (Minsker, 2015) as their mean estimator, which led to weaker results the heavy-tailed setting. show that using Filterpd the mean estimator automatically results in better bounds. The proofs for the technical results appearing henceforth can be found in the appendix.
Algorithm RGD Filterpd
In this setting, we observe pairs of samples {(x11 y1)..... (2., Yn)), where each (æz, 3/) E IR" x R. We assume that the (x,, y) pairs sam- pled from the true distribution P Pare linked via a linear model:
Robust Gradient Descent (Prasad et al., 2020)
Require: Data {a, ) Loss Function É.
Require: Step size 1), Number of Iterations T, Confidence 6.
Require: Initialization 8 and constraint set O
1: Split samples into T subsets {2, of size ñ |//r]
y xT + wr
(4)
2: Set 7 = C (T/s)
3: for
to 7 do
where w is drawn from a zero-mean distribution with bounded 4th mo- ment with variance o². We suppose RP, that under P the covariates have mean O, covariance Σ, sat- isfying TeIP A Eg I TuTp and bounded 8th moment.
4: Obtain S. = (V 12)) 21) 24 E 2,}
5: Let g" Filterpd( S, )
6: Update 0¹ = argmin 0 (0--1 - n1g') d
7: end for
8: return (0.)--
Theorem 2. Consider the statistical model in (4). Suppose we observe pairs of samples, where n satisfies
n Cip² Tlog (pT/6)
(S)
log(T/6)
RGD Filterpd when initialized at 8 with step size 1 = 2/ (Tuttt)) and confidence parameter returns iterates Y0= which with probability at least satisfy:
1 - 00 k=1 -0 + C2o I K
trace (Ei)
C2o
[ log(E/8)
(6)
n/r
1
a/T
for some contraction parameter
For appropriately chosen T,, achieve the best known result for heavy-tailed lin- ear regression, improving on the previously best known rate by Hsu & Sabato (2016). A detailed exposition with the form of T and detailed comparisons to other work is presented in the appendix due to space constraints.
Remarks:
We also note that RGD Filterpd is also effective for generalized linear models (GLMs) such as logistic regression in the heavy-tailed setting. We extend guarantees for these statistical models in the appendix (Sections B.3 and B.4) due space constraints.
4

---

Under review as a conference paper at ICLR 2021
beraton 10C30
Terston 10000
ta 1530
2,80]
0.00
0.01
0.00
1,500
0.00
Donator
0.00
0.04
0.01
0.02
0.00
0.00
0.00
Gradiens
Gradiens
Gradient
(a) Training DCCAN on CIFAR-10
(b) Training DCGAN on MNIST
(c) Training Real-NVE on CIFAR-10
Figure 2: Variation of gradient distributions across different iterations for different models and datasets. (a) and (b) show the variation of generator gradient norms over iterations for DCGAN and (c) shows the variation of the complete gradient norms over iterations for Real-NVE X-axis: Gradient norm, Y-axis: Density
3 EXISTENCE OF HEAVY-TAILS IN DEEP GENERATIVE MODELS
In this section, elaborate on the preliminary study discussed in Section The evidence of heavy-tailed gradient distributions observed in DCCAN and Real-NVP suggests that the issue of heavy-tailednnes is more pervasive than thought be. While recent analyses have only considered supervised learning models focusing on image classification (Simsekli et al., 2019) and on attention models (Zhang et al., 2019), they miss out a large family of models that benefit from gradient estimates, namely probabilistic models (Mohamed et al., 2019). Examples of probabilistic models are generative adversarial networks (GANs) (Goodfellow et al., 2014) and invertible flow models (Dinh et al., 2014), and these are the models we have considered in our study.
Extending on the study from earlier, we investigate the variation in the norms of the gradients across iterations while training. Zhang et al. (2019) had previously identified the effect of different datasets for their supervised learning setup. Therefore, we also consider an additional dataset in our study with GANs to observe any effects that the data distribution could have this distribution. The plots are showcased in Figure
To quantitatively assess the heavy-tailedness of these gradient norm distributions, mator to measure the heavy-tailedness, which assumes that the underlying distribution is a strictly a-stable distribution. We use the a-index estimator proposed by Mohammadi et al. (2015) and used in Simsekli et al. (2019). While there are some drawbacks of using this estimator, such as the require- ment of symmetric distributions and the assumption that the distribution a-stable, this estimator provides a rough idea about how heavy the tail of distribution is given samples from that distribu-
esti-
tion. Formally, given samples (X;)² and natural numbers K1, K2 such that K₃ K₂ n, the a-index estimate ã is computed as follows
K2 Σ log (o)))
K KI
= =ogg(Kg))
(,,( K2
Y
Xi+(--1)
1=1
j=1
An a-index close to 2 indicates that the samples are closer to being Gaussian, and lower a-index is indicative of heavy-tailedness. In the legend of each plot in Figure 2, we specify the estimated a-index for the gradient norm distributions. An iteration-wise variation is presented in the appendix (Section C), along with alternate method to quantify heavy-tailednnes..
With the presented evidence about the existence of heavy-tailed distributions certain deep gen- erative models, the of heavy-tailed mean estimator could be beneficial. However, Filterpd requires to be scaled to work for models with millions of parameters, and for sample sizes that are much smaller than the number of parameters.
Streaming - Filterpd: A HEURISTIC FOR BARGE-SCALL MODELS
Modern large-scale machine learning models have millions of parameters, and hence, generally trained using stochastic (or such setting, cannot directly Filterpd aggregate gradients. This is because when the
gradient descent (Robbins & Monro, 1951) in practice. In
5

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Streaming Filterpd
Require: History parameter Iterations T. Discard parameter d, Initialization to. Optimizer ALG 1: for / = 0 to 7 do
2: Obtain gradient samples {9t
(0) n Ji=1 of the objective at tz.
3: if t = 0 then
4:
Compute m.
a Σe
and Ci 9
Σ(9 (ot mmm882
(0o2 def
ve?
1=1
5: else
6:
Update mi = (1 amm--1
a
Ci = (1 Ac 96
02
a
g ( me
102
71
n
7:
end if
8:
Construct B, whose columns {v(1 a 1
-m
M=
9:
Cache d and the leading eigenpair of C. B,
10:
Calculate scores T; = (v? (gi m²))² and discard the top-d gradients ordered by scores n-d
11:
Compute final estimate C(O.)
9
(1) obtain update 0.+1 ALG(G(()),
end for return 9T
13:
mini-batch size n is much smaller than the dimension the sample covariance matrix does not concentrate well around the true covariance matrix. Due to this, the leading eigenvector of the sample covariance matrix could be significantly different from that of the true covariance matrix. Moreover, not viable to run T** leading eigenvector computations for models with millions of parameters, since the additional time complexity of this operation is proportional to and is not as efficient as computing the sample mean.
We now look at approaches to mitigate the above issues and present the spirit of the approaches. The first issue is with regard to the concentration of sample covariance. For this, we intend on reusing previous gradient samples to improve concentration. However, the gradient samples from earlier iterations cannot be weighted equally as neither the distributions are the same nor are the samples independent. Thus, given gradient samples at the current iteration and the mean and covariance from the previous iteration, a potential solution could be to compute the current estimates of the samples statistics by an exponential average like so.
m, (1 a-)m--1 + aafi
-1- a..
where The and E, are the mean and covariance of the gradient samples at iteration and m and Ct-1 are the mean and covariance computed the previous iteration. This solution, while promis- ing, is not tractable, as it requires storing the complete covariance matrix. To circumvent this, we approximate C.- 1 by a rank-one matrix, which is given by the eigenpair (A.-1, ut-) of the covari- ance matrix C,-1-
Recall that in Filterpd, we require to compute T" leading eigenpairs. To reduce computational costs, propose running one leading eigenpair computation at every iteration. This leading eigenpair is used in two ways: 1) to compute "outlier scores", and 2) to compute the exponential weighted covariance in the next iteration discussed above.
The heuristic is formally presented Algorithm The aforementioned exponential averaging is performed in Step (6). Step (8) is computational trick used avoid computing the complete covari- ance matrix C.- The leading eigenpair and the scores of the gradient samples are computed in Steps (9) and (10) respectively. We discard points based on scores obtained using the computed eigenvec- tor (the analogous steps in Filterpd are Steps (5) and (6)), and finally pass our robust aggregate to the optimization algorithm of choice in Step (11) this allows us leverage the benefits of certain optimization algorithms. We repeat this for T iterations as done in standard training procedures.
The algorithm is memory efficient due to Steps (8) and (9). This is due the construction of the matrix B, which only requires ((n)) memory. From computation standpoint, we only require the leading left singular vector of B,, which takes ((np) time run. In contrast, a naive implementa- tion of this algorithm is not memory efficient since it would require computing p x p matrix Ce

---

Under review as a conference paper at ICLR 2021
FOR
NZ Far
24
(a) 2s(0m,)) vs. 1=88-/18; for 20 and n 500
(b) Q=(0n, forp 20 and 5 = 0.1
(c) Q= for 1t = 500 and
(d) 2s(0m, vs. for n = 500, 20 and 6
0.1
Figure 3: Results for Heavy-Tailed Linear Regression. Smaller values for Qa (0n,s) better. Legend: (red, cross) RGD Filterpd, (blue, square) - RRD GMOM, (black, circle) OLS
and computing the leading eigenvector which can take (p²²) time. In our real-world experiments described in Section 5.2, we noted that Streaming - rilterpd provides speedups of at least 4x over rilterpd with smaller memory footprint, in addition to better performance on our metrics due to the streaming approximation.
5 EXPHRIMENTS
5.1 SYNTHETIC EXPERIMENTS LINEAR REGRESSION
To corroborate our theoretical results, conduct heavy-tailed linear regression to study the perfor- mance of our proposed algorithms.
Setup We generate covariates I2 from an standard Gaussian distribution. The true regression parameter is set as 8* = [1, 1] E R.. The response is generated by y x 4 + ow where drawn from standardized Pareto distribution with tail- aull-parameter = 3. In this setup, we experiment with different n.p and 8. For each setting of (n. 8). and cumulative metrics are reported over 100 trials. We vary n from 100 to 500, p from 20 to 100, from 0.01 to 0.1 and o from 0.01 to 5 on logarithmic scale.
Methods We compare RGD Filterpd with two baselines: Ordinary Least Squares (OLS) and robust gradient descent which uses Algorithm 2 with GMOM as used in Prasad et al. (2020). Note that Prasad et al. (2020) had previously shown that RGD GMOM outperformed several other estimators such as Hsu & Sabato (2016) and ridge regression, hence we skip them in our comparison.
Metric and Hyperparameter Tuning For any estimator &n,8, use P(....)) 10n.5 A-1 as our primary metric. We also measure the quantile error of the estimator, i.e. Qs(6n,s) = inf Pr(A(Un.s) > a) < åj. This also be thought of as the length of confidence interval for confi- dence level of 1-1. The number of blocks and the number of iterations T is set to 3.5 3.5 log(!/a) in RGD GMOM and RGD Filterpd respectively.
Results Figure 3 shows that our RGD Filterpd elearly outperforms both baselines. Figures 3a, 3b and 3c are generated with 0.1. Figure 3a indicates that for any confidence level - 8, the length of the oracle confidence interval (Qs (U,.s) .)) for our estimator is better than all baselines. We also better sample complexity in Figure 3b, and better dimension dependence in Figure 3c. We also ob- serve that when increased, which corresponds performs better in comparison to the other baselines.
lower signal-to-noiss to-so ratio, RGD Filterpd
We have also conducted synthetic experiments on heavy-tailed mean estimation, and defer the results to the appendix (Section D) due to space constraints. In summary, Filterpd outperforms both GMOM and the sample mean with respect to the metric considered.
5.2 REAL WORLD EXPERIMENTS
With the backing of empirical evidence that the distributions of gradients during training certain generative models are heavy-tailed shown in Section 3, seek apply heavy-tailed mean estimator over the gradient samples to obtain robust estimates of the mini-batch gradient. Due to the size of the models, is infeasible run Filterpd, and hence we use Streaming Filterpd instead.

---

Under review as a conference paper at ICLR 2021
5.2.1 GENERATIVE ADVERSARIAL NETWORKS
Setup We consider a DCGAN architecture for our experiments, same as the one considered in our investigations presented in Section 3. The model architecture is detailed in the code appendix.
Methods We train a DCGAN using Streaming Filterpd (abbrev. StrFpd) with the optimizer ADAM for 50000 iterations the MNIST and CIFARIO datasets. For comparison, train other DCGANs with the same initialization, using ADAM; however, the mini-batch gradients for the generator are aggregated via the following methods: sample mean (abbrev. Mcan), gradient clipping (abbrev. Clip), removal of gradient samples with largest norm (abbrev. NrmRmv). All other relevant training hyperparameters are detailed in the appendix.
Metrics We consider two key metrics: the Inception Score (Salimans et al., 2016) for CIFAR 10 and Mode Score (Che al., 2017) for MNIST, and the Parzen window based ligeliikl estimates as described in Goodfellow et al. (2014).
MODE (MNIST)
Parzen LL
Results We present our results in Table We observe that training with the Streaming - Filterpd provides benefits in terms of high metrics. For CIFARIO, we see significant improvement in the Inception score. For MNIST, the MODE scores are only slightly higher, however there is dis- cernible increase in the log-likelihone when trained using Streaming Filterpd as com- pared to another baselines.
(CIFARIO)
(MNIST)
StrFpd
5.20
8.94
218.95
Mean
5.07
8.91
207.61
Clip
5.09
8.92
214.29
NrmRmv
4.94
8.87
214.25
GMOM
4.97
8.90
205.66
Table 1: Table of comparison metrics incep- tion score (IS), mode score (MODE) and Parzen log-likelihood (Parzen LL)
5.2.2 INVERTIBLE FL.OW MODELS
Setup As done in Section 3, we consider RealNVP - state-of-the-ard model.
Methods We train Rea NVP model using Streaming Filterpd (abbrev. StrFpd) with the optimizer as ADAM for 5000 iterations on the CIFAR10 dataset. For comparison, we train two RealNVP models, both using sample mean for aggregation of gradient samples. How- ever, one of the models does not use norm clipping over the estimated gradient, and neither does Streaming Filterpd. All other relevant training hyperparameters are detailed in the appendix.
Metrics We compute the negative log-like ligeliiil on the test set NLL every 250 iterations. We NLlagg
report the test bits-per-dimension (BPD) given by BPD = of the samples. Additionally, to show stability, we report the average test BPD over the last 2000 iterations.
p-log(2) where is the dimensionality
We present our results in Figure 4 and Table 2. Figure 4 shows the erratic variation in BPD when Streaming - Filterpd is not used and further validates our hypothesis regarding the heavy- tailedness of gradients. Additionally, note that training with Streaming Filterpd is the most stable among the 3. We also see that Streamnig - Filterpd achieves the best average test BPD over the last 2000 iterations.
Results
Muan
Clayknn)
heyel
Average Test BPD over last 2000 iterations
Method
StrFpd
12.97
Mean (no-clipping)
641.66
Mean (with-clipping)
459.16
Table 2: Table of Average Test BPD the last 2000 iterations
Figure 4: Variation of Test BPD with itera- tions
8

---

Under review as a conference paper at ICLR 2021
6 DISCUSSION
In this work, we study methods for mean estimation, which are applicable for aggregating gradients. This is especially useful when the underlying distribution these gradients is heavy-tailed, where the sample-mean estimator by studying distribution of gradients of certain deep generative models. We also develop a heuristic for mean estimation algorithm that scales to models with millions of parameters. One potential avenue of improvement is to make the heuristic applicable to extremely large models, such as to GANs that generate high quality media certain language models. Nonetheless, we hope that this work encourages the development of principles approaches to tackling heavy-tailed distributions arising in machine learning.
be highly sub-optimal. We motivate the need for robust, heavy-tailed mean
REFERENCES
Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing, pp. 449-458. ACM, 2014.
Olivier Catoni. Challenging the empirical mean and empirical variance: deviation study. In Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, volume 48, pp. 1 1148-1185. Institut Henri Poincaré, 2012.
Olivier Catoni and Ilaria Giulini. Dimension-free pac-bayesian bounds for matrices, vectors, and 2017.
linear least squares regression. arXiv preprint
Tong Che, Yanran Li. Athul Paul Jacob, Yoshua Bengio, and Wenjie Li. Mode regularized generative adversarial networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, Frunce, April 24-26, 2017, Conference Track Proceedings. 2017.
Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett. Fast mean estimation with sub- sub-gaussian rates, volume of Proceedings of Machine Learning Research, pp. 786-806, Phoenix, USA, 25-28 Jun 2019. PMLR.
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni. Algorithms for heavy-tailed statisties: Regression, covariance estimation, and be- yond. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 601-609. Association for Computing Machinery, 2020. ISBN 9781450369794. doi: 10. 10.1145/33571333388422
Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statisties. arXiv preprint axXiv:1911.05911, 2019.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 655 IEFE, 2016.
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learming. pp. 999-1008, 2017.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components esti- mation. arXiv preprint arXiv: 14:::/4100 10.5516, 2014.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint 1rXiv:1605.00 08803,, 2016.
Yihe Dong, Samuel Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. In Advances in Newral Information Processing Systems, pp. 6067- 6077, 2019.
Jianqing Fan, Weichen Wang, and Ziwei Zhu. shrinkage principle for heavy-tailed data: High- dimensional robust low-rank matrix recovery, 2016.

---

Under review as a conference paper at ICLR 2021
Jianqing Fan, Quefeng Li, and Yuyan Wang. Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(1)2247-265, 2017.
Simon Foucart and Holger Rauhut. mathematical introduction compressive sensing, volume 1. Birkhäuser Basel, 2013.
Ian Goodfellow. Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Samuel B Hopkins. Sub-gaussian mean estimation polynomial time.
arXiv preprint
arXiv: 1809.07425 2018.
Daniel Hsu and Sivan Sabato.
Loss minimization and parameter estimation with heavy tails, Journal of Machine Learning Research, 17(18):1-44 100, 2016.
Adam R Klivans, Philip M Long, and Rocco Servedio, Learning halfspacces with malicious noise. Journal of Machine Learning Research, 10(Dec):2715-277) 27400, 2009.
Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1035-1046. ACM, 2018.
Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Anmual Symposium on, pp. 665-674. IEEE, 2016.
Guillaume Lecué and Jules Depersin. Robust subgaussian estimation of mean vector in nearly linear time. arXiv preprint 19X.:v:996600005 2019.
Zhixian Lei, Kyle Luh, Prayaag Venkat, and Fred Zhang. A fast spectral algorithm for mean esti- mation with sub- sub-gaussian rates. In Conference on Learning Theory, pp. 2598 2612, 2020.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intellgence and Statistics, pp. 983- 992, 2019.
Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis. High dimensional robust sparse regression. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisticx, volume 108 of Proceedings of Machine Learning Research, pp. 41 1 1-421. PMLR, 2020.
Gabor Lugosi and Shahar Mendelson. Robust multivariate mean estimation: the optimality of trimmed mean. arXiv preprint arXiv:1907. 1391, 2019.
Gábor Lugosi, Shahar Mendelson, al. -abb-gassiian estimators of the mean of random vector. The annals of statistics, 47(2):783-794, 2019.
Stanislav Minsker. Geometric median and robust estimation banach spaces. Bernoulli, 21(4): 2015.
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient esti- mation in machine learning. arXiv preprint arXiv:1906 1906,02,00,, 2019.
Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On estimating the tail index and the spectral measure of multivariate a-stable distributions. Metrika: International Journal for Theoretical and Applied Statistics, 78(5):549-55 161499556,,11 July 2015. doi: 101100775000184-04--555555
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, Pradeep Ravikumar, et al. Robust es- timation via robust gradient estimation. Journal of the Royal Statistical Society Series B, 82(3): 601-627, 2020.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint 15/ 1.06444 2015.
10

---

Under review as a conference paper at ICLR 2021
Sidney I Resnick. Heavy-tail phenomena: probabilistic and statistical modeling. Springer Science & Business Media, 2007.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Tim Salimans, lan Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in neural information processing systems, pp. 2234 2242, 2016.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gra- dient noise in deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceed- ings Machine Learning Research, pp. 5827-5837, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Jacob Steinhardt. Robust Learning: Information Theory and Algorithms. PhD thesis, Stanford University, 2018.
Qiang Sun, Wen-Xin Zhou, and Jianqing Fan. Adaptive huber regression. Journal of the American Statistical Association, pp. 1-24, 2019.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 101 2010.
Huan Xu, Constantine Caramanis, and Shie Mannor. Outlier-robust pea: the high-dimensional case.
IEEE transactions on information theory, 59(1):546-53 572, 2013.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why adam beats sgd for attention models. arXiv preprint
arXiv:1912.03194, 2019.
Wen-Xin Zhou, Koushiki Bose, Jianqing Fan, and Han Liu. new perspective on robust m- estimation: Finite sample theory and applications dependence-adjussed multiple testing. arXiv preprint arXiv:1711.053811 2017.
Fangyu Zou, Li Shen, Zequn Jie, Ju Sun, and Wei Liu. Weighted adagrad with unified momentum. arXiv preprint arXiv: 1808. 03408, 2018


Reviews:
[{"review_id": "tO52JyhEsKQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In summary, this paper proposes a novel estimator for the mean estimation of heavy-tailed distribution. \n\nIn 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.\n\nIn 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.\n\nThe 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?\n\nIn 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.\n\nIn 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. \n\nIn 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.\n\nStep 2 in Algorithm 2: the \"$log(\\delta/T)$\" should be a typo, is that \"$log(T/\\delta)$\" instead?", "extra_scores": {}, "extra_text": {}}, {"review_id": "ra8mhXwJ_Ox", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nI have the following queries for the author(s)\n\n-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?\n\n-Along the lines of the first query, does the definition of bounded 2K-moment has any relation with sub-gaussian moment condition?\n\n-In the streaming filterpd algorithm (Algorithm 3) how robust is the rank-1 approximation of C_{t-1} by the leading eigen-pair?\n\n-I am a bit skeptical with the bounded 8th moment condition in the linear model example?\n\n-In theorem 2 do you allow dimension p to grow or is the result not tenable for the high dimensional case?\n\n- 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "n6fcOxjmver", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I thank the authors for their detailed reviews. I have updated my score\n\n---\n\nThe 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.\n\nThe 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.\n\nMy 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.\n\n**Major issues**\n\n* Unclear theoretical contributions.\n\n  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\n\n* Basic notation is not defined. I could only infer the following by reading referenced material\n  \n  * the dimensionality $p$ (p.2 or Eq. 3)\n  * the unit ball $\\mathcal{S}^p$ (p. 2)\n  * an outer product $(v)^{\\otimes 2}$ (Alg. 1)\n  * a constraint set $\\Theta$ (Alg. 2)\n  * the constant $d^2$ (Thm. 2, Eq. 5) is still mysterious\n\n* Clarity about the heuristic nature of Alg. 3.\n\n  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.\n\"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.\n\n**Minor comments:**\n\n* The figures need additional work as they are currently unreadable when printed.\n* 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)\n* 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VK-kyXv7zK", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\n\n## Summary\n\nThe 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. \tEspecially 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.\n\n--- \n## Pros\n\n+ The paper highlights the heavy-tailed nature of gradients in the intermediate stage of training deep generative models via experiments.\n+ The paper derives theoretical bounds for their mean estimation algorithm, and then applies it to study generalized models via gradient aggregation.\n+ A streaming heuristic of Algorithm 1 is proposed that has promising results in experiments.\n\n---\n## Cons\n\nThe 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.\n\n**Mean estimation**\n+ 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. \n+ 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$.\n- 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. ).\n- 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.\t\n- 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).\n\n**Linear Regression**:\n- 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).\n- 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).\n- 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). \n- 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.\n- Theorem 2 should also be compared with the paper Depersin (2020) (see below), preferably, in the main paper. \n\n---\n## Score\n\nOverall, 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.\n\n\n---\n### Other major comments\n\n**Streaming algorithm, Section 4**\n\n+ *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$.  \nI am confused by this statement: even the simple baseline of sample mean would have time complexity of np. This line should be clarified.\n+ *Recall that in Filterpd, we require to compute 1)* $ T^*$ *covariances and 2)* $T^*$ *leading eigenpairs*  \nThis 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. \n+ In experiments with Streaming-Filterpd, the runtime (wall-clock time) should also be reported with respect to baselines (Mean, Clip, NrmRmv). \n+ 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.\n\n\n---\n### Other minor comments\n\n+ The claims of near-optimality should be replaced with something objective.\n+ 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.\n+ 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.\n+ 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.\n+ The paper uses $d$ and $p$ interchangeably. For example, Eq. (5) has both, but only $p$ is defined.\n+ 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.\n+ Figure 3 (c): It seems that the dependence on $p$ is linear as opposed to $\\sqrt{p}$. Is there a reason for this?\n+ Section 4: \"This eigenpair is not required to be recomputed the current iteration\"\n+ Section 5: \"For comparison, we other DCGANs with the same initialization\" \n+ as -> are on Page 2: \"This is because sample mean estimates as ...\"\n\n---\n### Other References:\n\nIlias Diakonikolas, Daniel Kane, Ankit Pensia. Outlier Robust Mean Estimation with Subgaussian Rates via Stability. 2020.\nJules Depersin. A spectral algorithm for robust regression with subgaussian rates. 2020.\nGabor Lugosi and Shahar Mendelson. Risk Minimization by Median-of-Means Tournaments. 2016. \nThere are other recent works for both mean estimation and linear regression, but they were made public after the ICLR guideline of Aug 2, 2020.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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