Heteroskedastic and Imbalanced Deep Learning with Adaptive Regularization
Authors: Kaidi Cao
Yining Chen
Junwei Lu
Nikos Arechiga
Adrien Gaidon
Tengyu Ma
Venue: ICLR 2021 Poster (2021)
Keywords: deep learning
noise robust learning
imbalanced learning

Abstract: Real-world large-scale datasets are heteroskedastic and imbalanced --- labels have varying levels of uncertainty and label distributions are long-tailed. Heteroskedasticity and imbalance challenge deep learning algorithms due to the difficulty of distinguishing among mislabeled, ambiguous, and rare examples. Addressing heteroskedasticity and imbalance simultaneously is under-explored. We propose a data-dependent regularization technique for heteroskedastic datasets that regularizes different regions of the input space differently. Inspired by the theoretical derivation of the optimal regularization strength in a one-dimensional nonparametric classification setting, our approach adaptively regularizes the data points in higher-uncertainty, lower-density regions more heavily. We test our method on several benchmark tasks, including a real-world heteroskedastic and imbalanced dataset, WebVision. Our experiments corroborate our theory and demonstrate a significant improvement over other methods in noise-robust deep learning. 

Published as a conference paper at ICLR 2021
HETEROSKEDASTIC AND IMBALANCED DEEP LEARN- ING WITH ADAPTIVE REGULARIZATION
Kaidi Cao', Yining Chen', Junwei Lu", Nikos Arechiga', Adrien Gaidon', Tengyu Ma' Stanford University, "Harvard University, 'Toyota Research Institute Paidicao, cynnjjs, tengyuma] @ @stanford.ec edu
ABSTRACT
Real-world large-scale datasets are heteroskedastic and imbalanced - labels have varying levels of uncertainty and label distributions are long-tailed. Heteroskedas- ticity and imbalance challenge deep learning algorithms due to the difficulty of distinguishing among mislabeled, ambiguous, and rare examples. Addressing heteroskedasticity and imbalance simultaneously is under-explored. We propose a data-dependent regularization technique for heteroskedastic datasets that regu- larizes different regions of the input space differently. Inspired by the theoretical derivation of the optimal regularization strength in a one-dimensional nonpara- metric classification setting, our approach adaptively regularizes the data points in higher-uncertainty. lower-density regions more heavily. We test our method on several benchmark tasks, including real-world heteroskedastic and imbalanced dataset, WebVision. Our experiments corroborate our theory and demonstrate a significant improvement over other methods in noise-robust deep learning."
INTRODUCTION
In real-world machine learning applications, even well-curated training datasets have various types of heterogeneity. Two main types of heterogeneity are: (1) data imbalance: the input or label distribution often has long-tailed density, and (2) heteroskedasticity: the labels given inputs have varying levels of uncertainties across subsets of data stemming from various sources such as the intrinsic ambiguity of the data annotation errors. Many deep learning algorithms have been proposed for imbalanced datasets (e.g., see (Wang et al., 2017; Cao et al., 2019; Cui et al., 2019; Liu et al., 2019) and the reference therein). However, heteroskedasticity, classical notion studied extensively in the statistical community (Pintore et al., 2006; Wang et al., 2013; Tibshirani et al., 2014), has so far been under-explored in deep learning. This paper focuses on addressing heteroskedasticity and its interaction with data imbalance in deep learning.
Heteroskedasticity often studied regression analysis and refers to the property that the distribution of the error varies across inputs. In this work, we mostly focus on classification, though the developed technique also applies to regression. Here, heteroskedasticity reflects how the uncertainty in the Ir, or the entropy of are often heteroskedastic. For example, Li et al. (2017) shows that the Web dataset has a varying number of ambiguous true noisy examples across classes.?
conditional distribution
varies function of z. Real-world datasets
Conversely, we consider a dataset to be homoscedastic every example is mislabeled with fixed probably e, assumed by many prior thcoretical and empirical works label corruption (Ghosh et al., 2017; Han et al., 2018; Jiang et al., 2018; Mirzasoleiman et al., 2020). We note that varying uncertainty in i can come from least sources: the intrinsic semantic ambiguity of the input, and the (data-dependent) mislabeling introduced by the annotation process. Our approach can handle both types of noisy examples in a unified way, but for the sake of comparisons with past methods, call them "ambiguous examples" and "mislabeled examples" respectively, and refer to both of them "noisy examples".
1 'Code available at https / //gitttt /ggttbb...../ com/ ka d C/HAR. SSee Figure of (Li al., 2017), the number of votes for each example indicates the level of uncertainty of that example.

---

Published as a conference paper at ICLR 2021
rare examples (weigh up)
Density
1.0
freq & clean
freq & noisy
0.5
0.0
1
2
3
4
Density
1.0
rare & clean noisy
mislabeled examples (weigh down)
0.0
ambiguous examples (not clear)
Training loss
Figure 1: Histogram of the distributions of losses on an imbalanced and noisy CIFAR-10 10 dataset. Clean but rare examples tend to have larger losses, similar to the noisy examples in frequent classes.
Figure 2: Real-world datasets have various sources of heterogeneity and it could be hard to distin- guish one from another. They require mutually- exclusive reweighting strategy, but they all benefit from stronger regularization.
Overparameterized deep learning models tend to overfit more to the noisy examples (Arpit et al., 2017; Frénay & Verleysen, 2013; Zhang et al., 2016). To address this issue, common approach is to detect noisy examples by selecting those with large training losses, and then remove them from the (re-)training process. However, an input's training loss can also be big because is rare or ambiguous (Hacohen & Weinshall, 2019; Wang et al., 2019), as shown in Figure 1. Noise-cleaning methods could fail distinguish mislabeled from rare/ambiguous examples (see Section 3.1 for empirical proofs). Though dropping the former is desirable, dropping the latter loses important information. Another popular approach is reweighting methods that reduce the contribution of noisy examples in optimization. However, failing to distinguish between mislabeled and rare/ambiguous examples makes the decision of the weights tricky mislabeled examples require small weights, whereas rare / ambiguous examples benefit from larger weights (Cao et al., 2019; Shu et al., 2019).
We propose a regularization method that deals with noisy and rare examples observe that mislabeled, ambiguous, and rare examples all benefit from stronger regularization (Hu et al., 2020; Cao et al., 2019). We apply a Lipschitz regularizer (Wei Ma, 2019a;b) with varying regularization strength depending on the particular data point. Through theoretical analysis in the one-dimensional setting, we derive the optimal regularization strength for each training example. The optimal strength is larger for rarer and noisier examples. Our proposed algorithm, heteroskedastic adaptive regularization (HAR), first estimates the noise level and density of each example, and then optimizes a hüpschitz-regularizze objective with input-dependent regularization with strength provided by the theoretical formula.
unified way. We
In summary, our main contributions are: (i) propose to learn heteroskedastic imbalanced datasets under a unified framework, and theoretically study the optimal regularization strength on one- dimensional data. (ii) we propose an algorithm. heteroskedastic adaptive regularization (HAR), which applies stronger regularization to data points with high uncertainty and low density. (iii) we experimentally show that HAR achieves significant improvements over other noise-robust deep learning methods on simulated vision and language datasets with controllable degrees of data noise and data imbalance, as well as a real-world heteroskedastic and imbalanced dataset, Web Vision.
2 ADAPTIVE REGULARIZATION FOR HETEROSKEDASTIC DATASETS
2.1 BACKGROUNDS
We first introduce general nonparametric tools that use in our analysis, and review the dependency of optimal regularization strength on the sample size and noise level.
prerpparameterized neural networks nonparametric methods. We use nonparametric method as a surrogate for neural networks because they have been shown to be closely related. Recent work (Savarese al., 2019) shows that the minimum norm two-layer ReL.U network that fits
2

---

Published as a conference paper at ICLR 2021
Figure 3: A one-dimensional example with a three-layer neural network in heteroskedastic and imbalanced regression setting. The curve in blue is the underlying ground truth and the dots are observations with heteroskedastic noise. This ex- ample shows that uniformly weak regularization overfits on noisy and rare data (on the right half), whereas uniformly strong regularization causes underfitting on the frequent and oscillating data (on the left half). The adaptive regularization does not underfit the oscillating data but still denoise the noisy data. We note that standard nonparamet- ric methods such as cubic spline do not work here because they also use uniform regularization.
Ground Truth
Weak Unif-reg
Strong Unif-reg Adapt-reg (HAR)
the training data is in fact linear spline interpolation. Parhi & Nowak (2019) extend this result to broader family of neural networks with broader family of activations.
Given a training dataset {z 9:) } nonparametric method with penalty works as follows. Let F: R + R be wwice-differentiabll model family. We aim to fit the data with smoothness penalty
1 Σ (((())) (((a)) TE
miny
Lipschitz regularization for neural networks. Lipschitz regularization has been shown be effective for deep neural networks as well. Wei & Ma (2019a) proves generalization bound of neural networks dependent on the Lipschitzness of each layer with respect to all intermediate layers on the training data, and show that, empirically, regularizing the Lipschitzness improve the generalization. Sokolić al. (2017) shows similar results data-limited settings. In Section 2.3, we extend the Lipschitz regularization technique to heteroskedastic setting.
Regularization strength as function of noise level and sample size. Finally, we briefly review existing thcoretical insights the optimal choice of regularization strength. Generally, the optimal regularization strength for a given model family increases with the label noise level and decreases in the sample size. As a simple example, consider linear ridge regression ming 1 >E=1 (z, 31)²²
22 where F;. 0 Rd and y E IR. We assume y/s x 0 E for some ground truth parameter 0*, and ~ . (O, o²). Then the optimal regularization strength Appt do² /n2|@" 1|3. Results of similar nature can also be found in nonparametric statisties (Wang et al., 2013; Tibshirani al., 2014).
2.2 HRTEROSKEDASTIC NONPARAMETRE CLASSIFICATION ON ONE- DIMENSINNNION DATA
We consider a oieddimenio binary classification problem where X' [0, 1] R and y (-1,1}. We assume Y given X follows a logistic model with ground truth function f i.c.
Pr Y y/ X z] exp(-yf*(x))
(2)
The training objective is cross-entropy loss plus Lipschitz regularization, i.e.
f = argmin, i(f) 2 Σ (((())))))) + of pl))(
(3)
where f(a.y) y) = - log(1 + exp(-ya)) and p(z) is a smoothing parameter as a function of the noise level and density of æ. Let I (x) be the fisher information matrix conditioned the input, i.c. I(x) & E
= z). When (X,Y) follows the logistic model in equation 2,
T(x) (1+ exp(f
exp(-f cxxp((())) Var(Y x))
3

---

Published as a conference paper at ICLR 2021
Therefore, [(x) captures the aleatoric uncertainty of For example, when Y is deterministic conditioned on X 2, we have [xx = 0, indicating perfect certainty.
Define the test metric as the meea-squared-erroo on the test set {(I,, 4))-=i.i...
[ (00))(())) ((m155))
MSB(f) A
E
(4)
Our main goal is to derive the optimal choice of p(x:) that minimizes the MSE. We start with an analytical characterization of the test error. Let W2 = (f' is absolute continuous and f" [,2 1]}- We denote the density of X ((x). The following theorem analytically computes the MSE under the regularization strength p(.), building upon (Wang et al., 2013) for regression problems. The proof of the Theorem is deferred to Appendix A.
Theorem 1. Assume that f", I W3- Ler r(t) -1 1 (((())(()) and Lo 1_x _ exp(-2)t))o 22/ we choose À 22/5 for some constant Co O, the asymptotic mean squared error is
lim MSE( On CC, X2PP(1) [1000))0))] n-000
-
p(t)
in probability, where Cn is scalar that only depends on n.
Using the analytical formula of the test error above, we want to derive an approximately optimal choice of p(x). precise computation is infeasible, so we restrict ourselves to consider only p(x) that is constant within groups of examples. We introduce an additional structure we assume the data can be divided into groups (ag: 01), [01, (2). [4x-1,4)) Each group [a,, ()+1) consists of an interval of data with approximately the same aleatoric uncertainty. We approximate p(t) is constant on each of the group (a:, ac+1) with value Ps. Plugging this piece-wise constant p into the asymptotic
MSE in Theorem 1, we obtain
lim MSB(J) Σ 220
a5+1
(1)
di de (
d dt + Pj 1/2
Lo
|
A5+1
j
a;
Minimizing the above formula over Pl....,PP separately, we derive the optimal weights, Pj
2/5
Lo 12 /2
In practice, we do not know f and q(x), so we make the following
1 (0)) a [o]
simplifications. We assume that (t) and [(t) are constant on each interval [ay. aj+1]. In other words, we assume that qt)) = qj and I(t) = I, for all t E [aj, a1+1]. We further assume that di (t) is close to a constant on the entire space, because estimating the curvature in high dimension is difficult.
de
This simplification yields Pj x 1// 2/5
3/5 ///5 = "
We find the simplification works well
in practice.
Adaptive regularization with importance sampling, It is practically infeasible to implement the integration in equation for high-dimensional data. We use importance sampling to approximate the integral:
n Σ (()())).))) + Σ mf (xi)²
minimize, L(f) A
(5)
Suppose x, E [ay, 1)+1). we have that T; should satisfy that T:q Pj so that the expectation of the regularization term in equation 5 is equal to that in equation 3. Hence,
1
2/5 = 1 (zx,) 3/5 ((x:))())))))))) 3/5 4
Adaptive regularization for multi-class classification and regression. In fact, the proof of Theorem 1 is proved for general loss É(a, y). Therefore, we can directly generalize it multi- class classification and regression problems. For regression problem, f(a, y) is the square loss: f(y, a) 0.5(y a) the Fisher information T(x) 1. Therefore, for regression problem, we can choose regularization weight ;; = q(x;)- 2/5
Note that integrate the error without weighting hecause interested the balanced test performance.
4

---

Published as a conference paper at ICLR 2021
2.3 PRACTICAL IMPLEMENTATION ON NEURAL NETWORKS WITH DIGE-DIMENSIONAL DATA
We heuristically extend the Lipschitz regularization technique discussed in Section 2.2 from non- parametric models over-parameterized deep neural networks. Let (x, y) be example and fo be r-layer neural network. We denote by h55) the j-th hidden layer of the network, by JGL (x) ((f v). i..., the Jacobian of the loss w.r.t h6)) We replace the regularization 1/2
term f'(x)² in equation by R(z) = (E=
which was proposed by (Wei & Ma, 2019a). As proof of concept, we visualize the behavior of our algorithm in Figure 3, where we ob- serve that the rare and noisy examples have significantly improved error due to stronger regularization. In contrast, uniform regularization either overfits underfits different subsets.
Note that the differences from the I-D case include the following three aspects. 1. The derivative is taken w.t.t to all the hidden layers for deep models, which has been shown to have superior generalization guarantees for neural networks by (Wei & Ma, 2019a;b). 2. An additional square root taken in computing R(x). This modified version may have milder curvature and be easier tune. 3. We take the derivative of the loss instead of the derivative of the model, which outputs k numbers for multi-class classification. This is because the derivative of the model requires & times more time to compute. The regularized training objective is consequently
R
minimize,
L(f)
e 72
Σ
(l(f(x.). + AT,(x))))
(6)
where 7; is chosen to be T; [1z, //x=))////((xx/))////)) following the formula equation 5 in Section 2.2 and is a hyperparameter to control the overall scale of the regularization strength. We note that we do not expect this choice of 7; to be optimal for the high-dimensional case with all the modifications above the optimal choice does depend on the nuances. However, we also observe that the empirical performance is not sensitive to the form of 7 as long as it's increasing in (xx) and decreasing in g(z)). That is, the more uncertain or rare an example is, the stronger regularization should be applied.
In order to estimate the relative regularization strength тı, the key difficulty lies in the estimation of uncertainty (xx). As in the 1-D setting, we divide the examples into & groups Gi...., GR (e.g.. each group can correspond to class), and estimate the uncertainty on each group. In the binary setting, [(x) = Var(Y| X = x) = Pr = 1 X] Pr(Y = 0 X] can be approximated by [(x) = - (a Pr[Y = x = x| up to a factor of at most 2. We use the same formula for multi-class setting as the approximation of the uncertainty. (As sanity check, when Y is concentrated on single outcome, the uncertainty is 0.) Note that f(x:) is essentially the minimum possible error of any deterministic prediction on the data point x. Assume that we have a sufficiently accurate pre-trained model, we can use its validation error to estimate I [(x):
Then for all x E Gj. we estimate ((x) and ((x) by
Vx E Gj, ((x) x |Gyl. (x) average validation error of a pre-trained model fø on G2
The whole training pipeline is summarized in Algorithm 1.
Algorithm 1 Heteroskedastic Adaptive Regularization (HAR)
Require: Dataset D (x),, A parameterized model fo
1: Split training set D into Derain and D
2: fø Standard SGD Training on Dinin
3: Estimate [(xx), q(x) with equation using fg on D and compute т; = /a.)))/////3)////
4:
5: Initialize the model parameters randomly
6: fo < SGD with the regularized objective in equation 6 on the full dataset D
3 EXPERIMENTS
We experimentally show that our proposed algorithm HAR(Algorithm 1) improves the test perfor- mance of the noisier and rarer groups of examples (by stronger regularization) without negatively
5

---

Published as a conference paper at ICLR 2021
affecting the training and test performance of the other groups. We evaluate our algorithms three vision datasets and one NLP dataset: CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2009),
IMDB-review (Maas et al., 2011) (see Appendix C.1), and WebVision (Li et al., 2017), real-world heteroskedastic and imbalanced dataset. Please refer to Appendix B for low-level implementation details.
Baselines. We compare our proposed HAR with the following baselines. The simplest one is (1)
Empirical risk minimization (ERM): the vanilla cross-entropy loss with all examples having the same weights of losses. We select two representatives from the noise-cleaning line of approach. (2) Co-teaching (Han et al., 2018): two deep networks are trained simultaneously. Each network aims to identify clean data points that have small losses and use them to guide the training of the other network. (3) INCV (Chen et al., 2019): extends Co-teacing to an interative version to estimate the noise ratio and select data. We consider three representatives from the reweighting-base based methods, including two that learn the weighting using meta-learning. (4) MentorNet (Jiang et al., 2018): pretrains a teacher network that outputs weights for examples that are used train the student network with reweighting. (5) L2RW (Ren et al., 2018); it directly optimizes weights of each example in the training set by minimizing its corresponding loss small meta validation set. (6) MW-Net (Shu et al., 2019): it extends L2RW by explicitly defining a weighting function which depends only on the loss of the example. We also compare against two representatives from the robust loss function. (7) GCE (Zhang & Sabuncu, 2018): it generalizes mean average error and cross-entropy loss to obtain new loss function. (8) DMI (Xu et al., 2019): designs a new loss function based on generalized mutual information. In addition, as an essential ablation study, we consider vanilla uniform regularization. (9) Unif-reg: we apply the Jacobian regularizer on all examples with equal strength, and tune the strength to get the best possible validation accuracy.
3.1 SIMULATING HETEROSKEDASTER AND IMBALANCED DATASETS ON CIFAR
Setting. Unlike previous works that test on uniform random asymmetric noise, which is often not the case in reality, in this paper we test our method on more realistic noisy settings, as suggested by Patrini et al. (2017); Zhang& & Sabuncu (2018). In order to simulate heteroskedasticity, we only corrupt semantically-simiee simiilr classes. For CIFAR-10, 10, we exchange 40% of the labels between classes 'cat' and 'dog', and between 'truck' and 'automobile'. CIFAR-100 has 100 classes grouped into 20 super classes. For each class of the 5 classes under the super class "vehicles I' and 'vehicles 2', we corrupt the labels with 40% probability uniformly randomly the rest of four classes under the same super class. As a result, the 10 classes under super class 'vehicle I and 'vehicle 2' have high label noise level and the corruption are only within the same super class. Heteroskedasticitt of the labels and imbalance of the inputs commonly coexist in the real world settings. HAR can take both of them into account. To understand the challenge imposed by the entanglements of heteroskedasticity and imbalance, and compare HAR with the aforementioned baselines, we inject data imbalance concurrently with the heteroskedastic noise. We remove samples from the corrupted classes to simulate the most difficult scenario - the rare and noisy groups overfit significantly. (A more benign interaction between the noises and imbalance is that the rare classes have lower noise level, we defer it Appendix C.3.) We use the imbalance ratio denote the frequency ratio between the frequent (and clean) classes to the rare (and corrupted) classes. We consider imbalance ratio to be 10 and 100.
Result. Table summarizes the results. Since examples from rare classes tend to have larger training and validation loss regardless of whether the labels are correct or not, noise-cleaning based methods might drop excessive examples with correct labels. We examined the noise ratio of dropped samples for INCV under the setting of imbalance ratio equals 10. Among all dropped examples, there is only 19.2% of true noise examples. In addition, the rare class examples selected still have 29.8% of label noise. This explains that the significant decrease of accuracies of Co-teaching and INCV on corrupted and rare classes. Reweighting -bated based methods tend to suffer from the loss of accuracy in other more frequent classes, which is aligned with the findings in Cao et al. (2019). While the aforemmntioned baselines struggle to deal with heteroskedasticity and imbalance together, HAR is able to put them under the same regularization framework and achieve significant improvements. Notably, HAR also shows improvement over uniform regularization with optimally tuned strength. This clearly demonstrates the importance of introducing adaptive regularization among all examples for a better trade-off. A more detailed ablation study on the trade-off between training accuracy and validation accuracy can be found in Section 3.3.

---

Published as a conference paper at ICLR 2021
Table I: Top-1 validation accuracy (averaged over runs) of ResNet-32 on heteroskedastic and imbalanced CIFAR-10. HAR significantly improves noisy and rare classes, while keeping the accuracy on other classes almost unaffected.
Imbalance ratio
10
100
Method
Noisy&Rare
Cls.
Clean Cls.
Noisy&Rare Cls.
Clean Cls.
ERM
52.9 + 1.2
94.4 0.1
18.9 + 1.0
94.2 1: 0.1
Co-teaching
30.2 + 2.3
88,9 0.3
15.4 2.8
0.7
INCV
48.9 1 1.7
94.0
25.8 1 1.8
93.8 1 0.2
MentorNet
54.1 1.0
9.5
28.3 1.5
90.2 0.4
L2RW
44.3
9..
11.2
89.7 0.7
MW-Net
55.4
91.7
35.6
923 0.5
GCE
48.2
913
14.1
9..7
DMI
44.7 2.3
90.7
91.8 1.88:00 0.6
Unif-reg (optimal)
53.9 0.9
92.1 0.2
36.7 1.0
92.4 0.3
Ours (HAR)
63.5 + 0.8
94.3 + 0.2
42.4 + 0.7
94.0 + 0.2
3.2 ABLATION STUDY ON CIFAR
We disentangle the problem setting show the effectiveness of our unified framework.
Simulating heteroskedastic noise on CIFAR. We study the uncertainty part of HAR by testing under the setting with only heteroskedastic noise. The type of noise injection is the same Section 3.1.
We report the top-1 1 validation accuracy of various methods Table 2. Aligned with our analysis in Section 4, observe that both noise-cleaning and reweighting based methods don't 't get comparable accuracy on noisy classes with applying strong regularization (A = 0.1) under this heteroskedastic setting. We observe the behavior that too strong regularization impede the model from fitting informative samples, thus it could lead to decrease on clean classes' accuracy. On the contrary, too weak regularization leads to overfitting the noisy examples thus the accuracy noisy classes do reach the optimal.
Interestingly, we find that even the well-studics CIFAR- -EFAR-100 dataset has intrinsic heteroskedasticity and HAR can improve over uniform regularization to some extent. Please refer to Appendix C.2 for the results on CIFAR-100 and Appendix C. for results on IMDB-review.
Table 2: Top-1 validation accuracy (averaged over 3 runs) of ResNet-32 on heteroskedastic CIFAR-10 and CIFAR- 100 for the noisy classes and the clean classes.
Dataset Method
CIFAR-10
CIFAR-100
Avg. Noisy Cls.
Avg. Clean Cls.
Avg. Noisy Cls.
Avg. Clean Cls.
ERM
68.6 + 0.2
93.6 + 0.2
65.3 + 0.3
67.8 + 0.2
Co-teaching
64.7 + 0.4
89.1 0.3
59.8 + 0.4
65.3
INCV
76.7 0.6
93.0 0.2
66.2 1
68.6 68.610..
MentorNet
71.1 1.4
93.7
65.9 1 0.3
67.5
L2RW
0.3
0.3
05.1
67.0 0.3
MW-Net
0.3
94.4
6.3
69.1
GCE
1.1
9.2
6.6
66.9 0.2
DMI
0.7
9.2
64.8 0.5
67.1
Unif-reg (A 0.1)
77.5
92.3
69.3 + 0.5
66.6 0.3
Unif-reg (optimal)
75.3 + 0.3
94.1 1 0.2
68.5 - 0.3
68.6 0.2
Ours (HAR)
80.7 - 0.3
94.5 + 0.2
74.2 - 0.3
69.3 1 0.2
Simulating data imbalance on CIFAR. We study the density part HAR by testing under the setting with only data imbalance. We follow the same setting Cao et al. (2019) to create imbalanced CIFAR. Long- imbalance follows an exponential decay in sample sizes across different classes. For step imbalance setting. all rare classes have the same sample size, do all frequent classes. Our approach achieves better results than LDAM-DRW and comparable to recent state-of of the-art ant methods under the imbalanced setting.

---

Published as a conference paper at ICLR 2021
Table 3: Top-1 validation errors of ResNet-32 on imbalanced CIFAR-IO and CIFAR-100.
Dataset
Imbalanced CIFAR-10
Imbalanced CIFAR-100
Imbalance Type
long-tailed
step
long-tailed
step
Imbalance Ratio
100
10
100
10
100
10
100
10
ERM Focal
29.64
13.61
36.70
17.50
61.68
44,30
61.45
45.37
29.62
13.34
36.09
16.36
61.59
44.22
61.43
46.54
CB Focal
25.43
12.90
39.73
16.54
63.98
42.01
80.24
49.98
LDAM-DRW
22.97
11.84
23.08
12.19
57.96
41.29
54.64
40.54
BBN (Zhou et al., 2020)
20.18
11.68
21.64
11.99
57.44
40.88
57.44
40.36
HAR-DRW
20.46
10.62
20.27
11.58
55.35
38.98
51.73
37.54
Table 4: Validation accuracy of ResNet-50 when tuning the regularization strength mini WebVision. HAR stands out of the trade-off constraint of fitting and generalization.
Train Ace
Val Acc
Reg Strength
Top
Top 5
Top
Top 5
0
69.01
88.64
59.40
80.84
Unif-reg (A = 0.01)
68.96
88.54
64.32
86.
Unif-reg (A = 0,02)
67.02
87,51
64,40
85,92
Unif-reg (A 0.05)
65.11
86.33
65.80
86.84
Unif-reg (A = 0.1)
63.35
84.98
65.04
86.56
Adaptive (HAR)
69.12
88.41
69.20
88.96
3.3 EVALUATION ON WEB VISION WITH REAL-WORLD HETEROGENEITY
Wibvis (Li et al., 2017) contains 2.4 million images crawled from Google and Flickr using 1,000 labels shared with the ImageNet dataset. Its training set is both heteroskedastic and imbalanced (detailed statistics can be found in (Li et al., 2017)), and it is considered as popular benchmark for noise robust learning. As the full dataset is very large, we follow (Jiang et al., 2018) to use a mini version, which contains the first 50 classes of the Google subset of the data. Following the standard protocol (Jiang et al., 2018), we test the trained model on the Web Vision validation set and the ImageNet validation set. We use ResNet-50 for ablation study and InceptionResNet-22 for fair comparison with the baselines. We report results comparing against other state-of-the-an approaches in Table 5. Strikingly, HAR achieves significant improvement.
Ablation study. We demonstrate the trade-off off between training accuracy and validation accuracy on mini WebVision with various uniform regularization strength and HAR in Table 4. It's evident that when we gradually increase the overall uniform regularization strength, the training accuracy contin- ues to decrease, and the validation accuracy reaches its peak at 5e-2. While a strong regularization could improve generalization, it reduces deep networks' capacity to fit the training data. However, with our proposed HAR, we only enforce strong regularization on a subset so that we improve the generalization on noisier groups while maintaining the overall training accuracy not affected.
RELATED WORK
Our work is closely related the following methods and directions.
Noise-cleaning, The key idea of noise-cleaning is to identify and remove (or re-label) examples with wrong annotations. The general procedure for identifying mislabeled instances has a long history (Brodley & Friedl, 1999; Wilson & Martinez, 1997; Zhao & Nishida, 1995). Some recent works tailored this idea for deep neural networks. Veit et al. (2017) trains a label cleaning network on small set of data with clean labels, and uses this model to identify noises in large datasets. To circumvent the requirement of a clean subset, Malach & Shalev-Shward (2017) train two networks simultaneously and perform update steps only in case of disagreement. Similarly, in co-teaching (Han et al., 2018), each network selects certain number of small-loss samples and feeds them to its peer network. Chen et al. (2019) further extends the co-training strategy and comes up with iterative
8

---

Published as a conference paper at ICLR 2021
Table 5: Validation accuracy of InceptionResNet-22 on WebVision and ImageNet validation sets.
HAR demonstrates significant improvements over the previous state-of-the-art
Train
mini WebVision
full WebVision
Test
WicVisson
ImageNet
WchVision
ImageNet
Method
Top I
Top 5
Top 1
Top 5
Top 1
Top 5
Top 1
Top
ERM
62.5
80.8
58.5
81.8
69.7
87.0
62.9
83.6
Co-teaching
63.6
85.2
61.5
84.7
INCV
65.2
85.3
61.6
85.0
MentorNet
63.0
81.4
57.8
79.9
70.8
88.0
62.5
83.0
Ours (HAR)
75.5
90.7
70.3
90.0
75.0
90.6
67.1
86.7
version that performs better empirically. Recently Song al. (2020) discovers that it is not necessary to maintain two networks. Removing examples whose training loss exceeds a certain threshold before learning rate decay can also get robust performance.
Reweighting. Reweighting training data has shown its effectiveness on noisy data (Liu & Tao, 2015). Its challenge lies in the difficulty of weights estimation. Ren al. (2018) proposes a meta-learning algorithm to assign weights to training examples based on its gradient direction with the one on clean validation set. Recently, Shu et (2019) proposes learn an explicit loss-weight function to mitigate the optimizing issue of (Ren et al., 2018 8). Another line of work resorts to curriculum learning by either designing an easy-to-hard strategy of training (Guo al., 2018) or introducing an extra network (Jiang et al., 2018) to assign weights.
Noise-cleaning and reweighting methods usually rely on the empirical loss to determine a sample is noisy. However, when the dataset is heteroskedastic, each example's training/validation loss no longer correlates well with its noise level. In such cases, we argue that changing the strength of regularization is more conservative adaption and suffers less from uncertain estimation, compared to changing the weights of losses (Please refer to Section C.4 for empirical justifications).
Robust loss function. Another line of works has attempted design robust loss functions (Ghosh et al., 2017; Xu et al., 2019; Zhang & Sabuncu, 2018; Patrini et al., 2017: Cheng et al., 2017; Menon al., 2016). They usually rely on prior assumption about latent transition matrix that might not hold in practice. On the contrary, we focus on more realistic settings.
Regularization based techniques have also been explored combat label noise. Li et al. (2019) proves that SGD with early stopping is robust to label noise. Hu et al. (2020) provides theoretical analysis of two additional regularization methods. While these methods consider a uniform regularization on all training examples, our work emphasizes on adjusting the weights of regularizers in search of a better generalization than uniform assignment.
Regularization.
5 CONCLUSION
We propose a unified framework (HAR) for training on heteroskedastic and imbalanced datasets. Our method achieves significant improvements over the previous state-of-the-arr on a variety of benchmark vision and language tasks. We provide theoretical results as well as empirical justifications by showing that ambiguous, mislabeled, and rare examples all benefit from stronger regularization. We further provide the formula for optimal weighting of regularization. Heteroskedasticity of datasets a fascinating direction worth exploring, and it is important step towards better understanding of real-world scenarios in the wild.
ACKNOWLEDGEMENTS
Toyota Research Institute ("TRI") provided funds and computational resources to assist the authors with their research but this article solely reflects the opinions and conclusions of its authors and not TRI or any other Toyota entity. YC supported by Stanford Graduate Fellowship. TM acknowledges support of Google Faculty Award. The work is also partially supported by SDSI and SAIL. Stanford.

---

Published as a conference paper at ICLR 2021
REFERENCES
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio. et al. A closer look at memorization in deep networks. In Proceedings of the 34th International Conference on Machine Chomning-Volume 70, pp. 233-242. JMLR. org, 2017.
Carla Brodley and Mark Friedl. Identifying mislabeled training data. Journal of artificial intelligence research, 11:131-167, 1999.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with aabel-distribution-awwew margin loss. In Advances in Neural Information Processing Systems, pp. 1 1565-1576, 2019.
Pengfei Chen, Ben Ben Liao, Guangyong Chen, and Shengyu Zhang. Understanding and utilizing deep neural networks trained with noisy labels. In International Conference on Machine Learning. pp. 111100020000 2019.
Jiacheng Cheng, Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance-and and label-dependent label noise. arXiv preprint arXiv: 170.03779 2017.
Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9268-999999 9277, 2019.
Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: a survey. IEEE Iransactions on neural networks and learning systems, 25(5):845-869, 2013.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Sheng Guo, Weilin Huang, Haozhi Zhang, Chenfan Zhuang, Dengke Dong, Matthew Scott, and Dinglong Huang. Curriculumnet: Weakly supervised learning from large-scale web images. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 135-150, 2018.
Guy Hacohen and Daphna Weinshall. On the power of curriculum learning in training deep networks. In International Conference on Machine Learning, pp. 2535-2544, 2019.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in neural information processing systems, pp. 8527-8537. 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
W Hu, Z Li, and D Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference on Learning Representations, 2020.
Zhiheng Huang, Wei Xu, and Kai Yu. Bidirectional Istm-crf models for sequence tagging. arXiv preprint arXiv:1508.0/99) 2015.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data- driven curriculum for very deep neural networks on corrupted labels. In International Conference on Machine Learning, pp. 2304-2313, 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Mingchen Li, Mahdi Soltanolkotabi. and Samet Oymak. Gradient descent with early stopping is prov- ably robust to label noise for overparameterized neural networks. arXiv preprint arXiv:1903. 11680, 2019.
10

---

Published as a conference paper at ICLR 2021
Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Luc Van Gool. Webvision database: Visual learning and understanding from web data. arXiv preprint arXiv: 2017.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Trunsactions on pattern analysis and machine intelligence, 38(3):447-461, 2015.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu. Large-scale long-tailed recognition in an open world. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2537-2546 2019.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguisties: Human language technologies-volume I, pp. 142-150. Association for Computational Linguistics, 2011.
Eran Malach and Shai Shalev-Shwartz.
Decoupling" when to update" from" how to update". In Advances in Neural Information Processing Systems, pp. 960-970, 2017.
Aditya Krishna Menon, Brendan Van Rooyen, and Nagarajan Natarajan. Learning from binary labels with instance- mnstance-depeneent corruption. arXiv preprint 1605 00000000.07,,... 2016.
Baharan Mirzasoleiman, Kaidi Cao, and Jure Leskovec. Coresets for robust training of neural networks against noisy labels. Advances in Neural Information Processing Systems, 33, 2020.
Rahul Parhi and Robert D Nowak. Minimum" norm" neural networks are splines. arXiv preprint arXiv:1910.02333: 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1944-1952, 2017.
Alexandre Pintore, Paul Speckman, and Chris C Holmes. Spatially adaptive smoothing splines. Biometrika, 93(1):113-125, 2006.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference on Machine Learning, pp. 4334 4343, 2018.
Pedro H. Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In COLT, 2019.
Zuofeng Shang, Guang Cheng, al. Local and global asymptotic inference in smoothing spline models. The Annals of Statistics, 41(5):2608-25) -2338, 2013.
Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta-weight net: Learning an explicit mapping for sample weighting. In Advances in Neural Information Processing Systems, pp. 1917-1928, 2019.
Sokolić, R. Giryes, G. Sapiro, and M. R. D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions Signal Processing, 62666)4426544288 2017.
Jiaming Song, Lunjia Hu, Yann Dauphin, Michael Auli, and Tengyu Ma. Robust and on-the-fly dataset denoising for image classification. arXiv preprint arXiv:2003. 10647, 2020.
Ryan Tibshirani et al. Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics, 42(1))285-323. 2014.
Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie. Learning from noisy lcrge-scale datasets with minimal supervision. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 839-847, 2017.

---

Published as a conference paper at ICLR 2021
Xiao Wang, Pang Du, and Jinglai Shen. Smoothing splines with varying smoothing parameter. Biometrika, 100(4):955-97) 9700, 2013.
Yiru Wang, Weihao Gan, Jie Yang, Wei Wu, and Junjie Yan. Dynamic curriculum learning for imbalanced data classification. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5017-5026, 2019.
Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning to model the tail. In Advances in Neural Information Processing Systems, pp. 7029-7039, 2017.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In Advances in Neural Information Processing Systems, pp. 9722-9733, 20.
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via an all-layer margin. arXiv preprint UrXiv:1910.0428x 2019b.
D Randall Wilson and Tony R Martinez. Instance pruning techniques. In ICML, volume 97, PP. 400-411, 1997.
Yilun Xu, Peng Cao, Yuqing Kong, and Yizhou Wang. L L_dmi: novel information-thheortie loss function for training deep nets robust label noise. In Advances in Neural Information Processing Systems, pp. 1222-62333 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 2016.
Zhilu Zhang and Mert Sabuneu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, pp. 1178-8788, 2018.
Qi Zhao and Toyoaki Nishida. Using qualitative hypotheses to identify inaccurate data. Journal of Artificial Intelligence Research, 3:119-145, 1995.
Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen. Bbn: Bilateral-branch network with cumulative learning for long-tailed visual recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9719-9728, 2020.
12

---

Published as a conference paper at ICLR 2021
A PROOFS OF THEOREM
We prove a general theorem here. In particular, we have the general theorem below.
Theorem 2. Assume that f* q, I E W2. Suppose (1) E(a, y) is convex and three times continously differentiable with respect to a, (2) there exist constants almost surely, and c & V.l(f*()) almost surely. Let r(t) = -I/( and Lo = - i
c < < oo such that с S [(X) S C
satisfies [[c[X] = 0, E X = I(X) and E[c| < 00
)tt. Ie choose = Con 225
for some constant Co > 0, the asymptotic mean squared error of by equation 4 is
lim MSE(f) On f. (0) [ (1
(or())
in probability, where Cn is scalar that only depends on n.
is easy to check that the logistic loss satisfies the condition of the theorem.
The proof strategy of Theorem 2 is adopted from the proof of Theorem 2 of (Wang et al., 2013) by generalizing it from the least square loss to logistic loss.
The high level idea is to reformulate f as solutions to ordinary differential equations. Let (7os he) be the (normalized) solution of the following equation
- -((()," (1) 7o (1)(()))))))
(8)
(0 11 0, and h" (0) (1) 0.
(9)
We define the the leading term of f - 1 (n))(
(fx(f*) = K,,, -Wxf" where
A7e he (-). K2(-) Σ k.(() h.)+) and W.ho(-) I Aro 1+ Ari
By Proposition 2.1 and Theorem 3.4 of Shang et al. (2013), we have sup (f(x) (x) (f)) op(n-1/3)
(10)
Following the same proof of Theorem 2 of (Wang et al., 2013), we can simplify the definition of K₁ and W as
I(1) J(I and (1) = =Ar(1) | (oor))YO))
K((x)
(11)
where st, = ((t)
- Q3(s))) and Qs(t,s) = (6(r(s)((s)) + O(B-)))ds and 3 = 1/VA. Plugging equation into equation 10, we then have
lim MSE(S) C. L X2P(1) L [1000)0)))) Lor(1)' 1/2 100000
B IMPLEMENTATION DETAILS
We develop our core algorithm in PyTorch (Paszke et al., 2017).
Implementation details for CIFAR. We follow the simple data augmentation used in (He et al., 2016) with only random crop and horizontal flip. We use ResNet-32 as our base network and repeat all experiments for 3 runs. We use standard SGD with momentum of 0.9, weight decay of 1 x 10-4 for training. The model is trained with a batch size of 128 for 120 epochs. We anneal the learning rate by factor of 10 at 80 and 100 epochs. We group the data by class labels, and by default we split D equally and randomly into Dunin and Dvat- As for the Jacobian regularizer, we sum over the frobenius norm of the gradients of all normalization layers' (BN by default) activations with respect to the classification loss. For experiments of HAR, we tune À so that the largest enforced regularization strength (Arz) is 0.1. We train each model with NVIDIA GeForce RTX 2080 Ti.
13

---

Published as a conference paper at ICLR 2021
Implementation details for IMDB-review. We train two-layer bidirectional LSTM (Huang et al., 2015) with 256 units followed with 0.5 dropout before the linear classifier. The network is trained for 20 epochs with Adam optimizer (Kingma & Ba, 2014). For HAR, tune À so that the largest enforced regularization strength (Arz) is 0.1. We train each model with NVIDIA GeForce RTX 2080 Tí.
Implementation details for Web Vision. We use the standard data augmentation same as (He et al., 2016) including random crop and horizontal flip. For mini WehVision, We train the network for 90 epochs using standard SGD with a batch size of 128. The initial learning rate is 0.1 and is annealed by factor of 10 at epoch 60 and 90. For full WebVision, We train the network for 50 epochs using standard SGD with batch size of 256. The initial learning rate is 0.1 and is annealed by a factor of 10 epoch 30 and 40. For experiments of HAR, tune that the largest enforced regularization strength (AT,) is 0.1. We train each model with 8 NVIDIA Tesla V100 GPUs.
Runtime analysis. Because the pre-trained model only trains on half of the training data and is only done once, the run-time of HAR is at most twice of the time for ERM. Many baselines in our paper use sophisticated pipelines and slower than HAR. For example, INCV trains 2 models simultancously for 4 times from random initialization to get clean training set. MW-Net has very slow convergence rate, which is a common issue for meta-learning.
C ADDITIONAL RESULTS
C.1 SIMULATING HETEROSKEDASTIC NOISE ON IMDB- REVVEE.
IMDB-review dataset has a total of 50,000 (25,000 positive and 25,000 negative reviews) movie reviews for binary sentiment classification (Maas et al., 2011). To simulate heteroskedastic noise for this binary classification problem, we project 5% of the labels of negative reviews to positive, and 40% in the reverse direction. Table 6 summarizes the results. The proposed HAR outperforms the ERM baseline with various strength of uniform regularization.
Table 6: Top-1 validation accuracy (averaged over 3 runs) on heteroskedastic IMDB-review dataset.
Reg Strength
Acc. of neg. reviews
Acc. of pos. reviews
Mean Acc
0
91.9 + 2.0 94.3 1 1.8
50.9 + 1.8
71.4 + 0.5
Unif-reg (A = 0.01)
51.9 + 2.0
73.1 1 0.3
Unif-reg (A = 0.1)
91.5 1 1.9
64.3 1 1.6
77.9 + 0.4
Ours (HAR)
93.1 1 1.5
72.8 1 1.7
83.0 1 0.3
C.2 EVALUATION ON C1FAR-100 WITH REAL-WORLD HETEROSKEDDSSTICIT
is acknowledged that CIFAR-100 training set contains noisy examples. For instance, some "tiger" examples labeled "leopard" ('tiger" defined class well). There are also noisy examples that contain multiple objects, or are more ambiguous in terms of indentity (Song et al., 2020). We find that HAR can improve over uniform regularization the well-studied CIFAR-100 due to its heteroskedasticity and the results are reported in Table 7.
Table 7: Top-1 validation accuracy (average over runs) of ResNet-32 on the original CIFAR-100
Reg Strength
Train Acc
Val Acc
0
96.0 0.1
69.8 + 0.2
Unif-reg (A 0.001)
96.4 0.1
70.0 0.2
Unif-reg (A 0.01)
95.7 0.1
70.6 0.1
Unif-reg (A = 0.1)
88.8 0.1
70.5 4 0.1
Adaptive (HAR)
96.2 0.1
71.4 0.1
14

---

Published as a conference paper at ICLR 2021
C.3 SIMULATING HETEROSKEDAS AND IMBALANCED DATASETS ON CIFAR
As mentioned in Section 3.1, we consider another variant of heteroskedastic and imbalanced dataset such that the rare classes have low noise level. To simulate this setting, make the clean classes have fewer labels than the corrupted classes on the heteroskedastic CIFAR-10 we created in Section ??.
Table 8 summarizes the results. For the setting of imbalance ratio equals 10. INCV automatically drops 34, I % of examples from the clean and rare classes, which results in decrease of mean accuracy on the rare and clean classes. HAR is able achieve improvements on both noisy classes and rare classes by enforcing the optimal regularization.
Table 8: Top-1 validation accuracy (averaged over runs) of ResNet-32 on heteroskedastic and imbalanced CIFAR-IO.
Imbalance ratio Method
10
100
Noisy Cls.
Rare
Noisy Cls.
Rare Cls.
ERM
59.9 1.1
65.2 + 0.7
60.4 + 0.9
7.9 + 1.3
Co-teaching
63.1 2.3
59.4 + 1.4
53.8 + 1.9
4.4 + 1.8
INCV
74.5 + 1.2
63.7 + 0.8
68.3 3.3+15 1.8
2.1 1.3
MentorNet
67.3 = 1.6
65.5 + 1.2
63.3
10.8 1.9
L2RW
65.8 1.4
66.3 1
2.14
11.3
MW-Net
714 0.6
0.6
65.0
13.5
GCE
64.6 1.1
6.3
7..2
DMI
72.3 = 1.5
63.3 1.2
70.8 1.7
6.2 = 1.9
Ours (HAR)
76.1 0.8
72.1 1.0
73.0 + 1.6
26.1 0.8
C.4 COMPARING THE EFFECT OF WEIGHTS ON LOSSES AND REGULARIZERS
As discussed in Section 4, we train several classifiers with alternative weights selection scheme which are not optimal. We consider the following two alternatives. (I) random: we draw the weights from a uniform distribution with the same mean as the weights of MW-Net and HAR. (2) inverse: we take the inverse of the weights learned by MW-Net and HAR and then normalize them to ensure the average reveighting/regularzztiooo strength remains the same.
We conducted experiments on the heteroskedastic CIFAR-10 introduced in Section ?? and the results are summarized Table We could conclude that changing the weights the regularizer more conservative adaption and less susceptible to uncertain estimation than reweighting.
Table 9: Top-1 I validation accuracy (averaged over 3 runs) of ResNet-32 on heteroskedastic CIFAR-10 by changing the weighting scheme.
Method
Avg. Noisy Cls.
Avg. Clean Cls.
ERM
68.6 0.2
93.6 + 0.2
Reweight (MW-Net)
75.0 0.3
94.4 1
Reweight (random)
62.1 = 0.5
92.9 1 0.5
Reweight (inverse)
13.1 0.9
90.9 + 0.3
Unif-reg (optimal)
75.3 = 0.3
94.1 0.2
Adap-reg (HAR)
80.7 0.3
94.5 0.2
Adap-reg (random)
74.8 0.4
44.2
Adap-reg (inverse)
73.2 0.5
94.0
C.5 VISUALIZZAION
In order to better understand how the proposed HAR works real-world heteroskedastic datasets, we plot the per-class key statistics used by HAR and validation errors in Figure 4. We observe that HAR outperforms the tuned uniform regularization baseline on the majority of the classes.
15

---

Published as a conference paper at ICLR 2021
method
0.6
Unif-Reg
0.4
HAR
0.2
0.0
1.0
reg strength
0.5
0.0
0.75
uncertainty
0.50
0.25
0.00
3000
cass size
2000
1000
class
Figure 4: Visualizations of per-class top-1 error and regularization strength of HAR on mini WebVi- sion dataset. The classes are sorted the ascending order of applied regularization strength.
16


Reviews:
[{"review_id": "coYqaM1C8Jr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "**Summary.** This paper presented a novel data-adaptive regularization scheme to adjust for the heteroskedasticity and non-uniformity (i.e., imbalance) of data distribution. Heuristically, solutions are subjected to heavier penalties in regions with either higher aleatoric (large variance) and epistemic (low-sample) uncertainties. While the exact proposal is, in theory, computationally intractable, the author(s) have made some clever relaxations, which lead to a very practical solution.  I very much enjoyed reading this paper. \n\n**Quality & Clarity.** This paper is well organized and clearly written. The. author(s) start the discussion with very intuitive examples,  followed by rigorous mathematical development on how to derive a theoretically justified adaptive penalty. To reach practical solutions, relaxations and surrogates are carefully elaborated. The experiment section is also well-executed, covering convincing synthetic and real-world examples to demonstrate the effectiveness of this proposal, comprehensively compared to SOTA alternatives. \n\n**Originality & Significance.** Although the idea of developing uncertainty-aware models have been repetitively explored in literature, I do find the HAR model proposed in this submission fresh & appealing. One of the main novelty that I appreciate is the fact the author(s) have scaled the gradient penalty for model complexity to deep neural nets, which in the final solution is replaced by the Lipschitz estimate. Although the stratification of sample space feels a bit hacky, I believe that is a necessary compromise to be made. I am reasonably positive this paper is expected to make some impact. \n\n**Minor issues.** There is a missing bracket in the last equation on pp 3. Eqn (6) should perhaps be more explicit on the dependence for $f$. I would love to see discussions, preferably preliminary experiments, to explore the use of nonparametric density estimation schemes to replace sample stratification. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LyP6-Yp_3Y", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 9, "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 authors propose a novel regularization approach aimed at addressing issues of class imbalance and heteroskedasticity. This adaptive approach uses a Lipschitz regularizer with varying strength in different parts of the input space, regularizing harder in cases of rare and noisy examples. The authors derive the optional regularization strength in the one-dimensional setting, to set ground for the proposed approach and its application in higher-dimensional settings. The approach is evaluated on multiple image datasets, and a textual dataset - and compared to a number of baselines, including those involving noise-cleaning, reweigthing-based methods, meta learning, robust loss functions, as well as tuned uniform regularization. The improvements seem quite strong, and clearly demonstrate the utility of the proposed approach. The paper is well structured, clearly written - and was a pleasure to read.\n\nI only have brief comments:\n\n- Unless I am mistaken (I could have missed it), I didn’t see a concrete mention of a statistical test that was used to determine statistical significance. The authors do use the word ‘significant’ to qualify the observed differences, but that should only be phrased as such if appropriate statistical testing has been done and has been outlined when describing the evaluation. That being said, the improvements are quite stark and I don’t doubt the validity of the claims - I am merely suggesting that the authors should include this information for clarity.\n\n- While the evaluation clearly shows the benefits of the proposed approach, and there is a detailed ablation study, I think that it would be interesting to additionally discuss and analyze in more detail the resulting regularization coming from the proposed approach, on WebVision (or one of the other datasets, wherever it’s easiest) - to show how the distribution of how many examples are being regularized by which factor - and contrast that with the optimal uniform regularization. There could also be a correspondence with Figure 1, if constraining the comparison to freq,rare ; noisy, clean input types. Visualizing some such distributions would help understand the method better - and add to the presented analysis.", "extra_scores": {}, "extra_text": {}}, {"review_id": "KKsM1ZrG7dP", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors propose a regularization approach for heteroskedastic data that regularizes in a data-dependent fashion, so different regions of the data spaces may be regularized differently by preferentially targeting high uncertainty and low density regions. This is achieved by estimating the noise level and density of each training example and then optimizing a regularized objective with input-dependent regularization.\n\nHow is k selected in (5)? Also, what is the purpose of Section 2 if neither the one-dimensional case nor the nonparametric model will be used in the experiments. The whole section seems distracting from the main message of the paper.\n\nWhat is the definition of rare classes in the experiment in Table 1? it seems accuracy for the rare and noisy classes is calculated on all examples, including the 40% for which labels were exchanged. It would be interesting to see the accuracy also calculated for the correct (non-exchanged) labels, is that Table 4?.\n\nWhy are the test accuracies in Table 3 better than the validation accuracies in Table 2?\n\nThe results in Table 3 are certainly impressive, however, additional results in the Appendix are less so. Particularly, the experiment where HAR is compared to uniform regularization. It would be interesting to see similar results for WebVision. Also, why only exchange 5% of the negative samples but 40% of the positive labels in the IMDB experiment?\n\nMinor:\n- $f$, $l$ and $\\lambda$ not defined in (1).\n- $P(Y=y|X=x)$ in (2) should not be a function of $y$.\n- why write the results for HAR and clean classes in bold?\n- If the expectation in (4) is explicitly over the dataset why not simply write is as an average?", "extra_scores": {}, "extra_text": {}}, {"review_id": "3rXJ7-motOd", "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": "This paper proposed an adaptive regularization method to handle heteroskedastic and imbalanced datasets, which are closer to real-world large-scale settings. The framework applies a Lipschitz regularizer with varying regularization strength depending on the particular data point. The authors first theoretically study the optimal regularization strength on a one-dimensional binary classification task. By applying some simplification, the result can be extended to high-dimensional multi-class tasks and finally HAR algorithm is proposed. Experiments show that HAR achieves significant improvements over other noise-robust deep learning methods on simulated vision and language datasets with controllable degrees of data noise and data imbalance, as well as a real-world heteroskedastic and imbalanced dataset. The experiments show great improvement. However, since the derivations involve many approximations, the reliability needs to be confirmed by more experiments.\n\n1. Assuming the pre-trained model is sufficiently accurate is not reasonable, especially in your complicated setting. \n2. This algorithm divides data into groups according to classes, and assume density and fisher information is constant within each group. This kind of division automatically takes class imbalance into account, which is not necessary according to your theory. Since heteroskedasticity means uncertainty varies between instances, not between classes, what if we divide data into groups with equal size? \n3. Synthetic experiments should be conducted to prove at least two things: (1) your algorithm can correctly estimate the regularization strength. (2) your algorithm can be applied to real heteroskedastic datasets, which vary uncertainty between instances, not classes. \n4. The imbalanced (long-tail) experiments did not compare with current SOTAs, i.e., BBN (CVPR20).\n5. You should compare your method to other methods with similar ideas, i.e., MetaReg.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper got 2 clear acceptance and 2 borderline recommendation. The main concerns lie in the clarity of the experiment results and settings (AR3). The authors address these questions in their response. AR2 has two important questions. One is whether the simplified assumption holds in the considered very complicated settings (i.e., the labels are noisy and long-tailed). The other one is the lack of comparison with SOTA method for long-tailed classification. The authors did good job in their response. They provide additional experiment results to address these questions. Overall, the quality of this submission meet the bar of ICLR acceptance, though AC has concerns on the complicated settings and the marginal performance improvement over the existing long-tailed works.
Decision: Accept (Poster)