Characterizing Structural Regularities of Labeled Data in Overparameterized Models
Authors: Ziheng Jiang
Chiyuan Zhang
Kunal Talwar
Michael Curtis Mozer
Venue:  (2021)

Abstract: Humans are accustomed to environments that contain both regularities and exceptions. For example, at most gas stations, one pays prior to pumping, but the occasional rural station does not accept payment in advance.
Likewise, deep neural networks can generalize across instances that share common patterns or structures yet have the capacity to memorize rare or irregular forms. We analyze how individual instances are treated by a model via  a consistency score. The score characterizes the expected accuracy for a held-out instance given training sets of varying size sampled from the data distribution. We obtain empirical estimates of this score for individual instances in multiple data-sets, and we show that the score identifies out-of-distribution and mislabeled examples at one end of the continuum and strongly regular examples at the other end. We identify computationally inexpensive proxies to the consistency score using statistics collected during training. We apply the score toward understanding the dynamics of representation learning and to filter outliers during training, and we discuss other potential applications including curriculum learning and active data collection.

Under review as a conference paper at ICLR 2021
CHARACTERIZING STRUCTURAL REGULARITIES OF LABELED DATA IN OVERPARAMETERIZED MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Humans are accustomed to environments that contain both regularities and ex- ceptions. For example, at most gas stations, one pays prior to pumping, but the occasional rural station does not accept payment in advance. Likewise, deep neural networks can generalize across instances that share common patterns or structures, yet have the capacity to memorize rare or irregular forms. We analyze how individ- ual instances are treated by model via consistency score. The score characterizes the expected accuracy for a held-out instance given training sets of varying size sampled from the data distribution. We obtain empirical estimates of this score for individual instances in multiple data sets, and we show that the score identifies out- of de-distribution and mislabeled examples one end of the continuum and strongly regular examples at the other end. We identify computationally inexpensive proxies to the consistency score using statistics collected during training. We apply the score toward understanding the dynamics of representation learning and to filter outliers during training.
INTRODUCTION
Human learning requires both inferring regular patterns that generalize across many distinct examples and memorizing irregular examples. The boundary between regular and irregular examples can be fuzzy. For example, in learning the past tense form of English verbs, there are some verbs whose past tenses must simply be memorized (GO-+WENT, EAT- HIT-+ and there are many regular KICK-KICKED, BREW BBREWED
verbs that obey the rule of appending "ed" (KISS etc.). Generalization to a novel word typically follows the "ed" rule, for example, BINK MINK->BINKE BINKED. Intermediate between the exception verbs and regular verbs are subregularities verbs that have consistent structure (e.g., the mapping of SING->SANG, RING~RANG)) Note that rule-governed and exception cases can have very similar forms, which increases the difficulty of learning each. Consider one-syllable verbs containing 'ee", which include the regular cases well exception cases like SEEK SEOU-S. Generalization from the rule- governed cases can hamper the learning of the exception cases and vice-versa. For instance, children in environment where English is spoken over-regularize by mapping GO-GG early in the course of language learning. Neural nets show the same interesting pattern for verbs over the course of training (Rumelhart McClelland 1986).
set of exception
NEED
Memorizing irregular examples is tantamount to building a look-up table with the individual facts accessible for retrieval. Generalization requires the inference of statistical regularities in the training environment, and the application of procedures or rules for exploiting the regularities. In deep learning, memorization often considered failure of network because memorization implies no generalization. However, mastering a domain involves knowing when to generalize and when not to generalize, because the data manifolds are rarely unimodal. Consider the two-class problem of chair vs non-chair with training examples illustrated in Figure [b. The iron throne (lower left) forms a sparsely populated mode (sparse mode for short) as there may not exist many similar cases in the data environment. Generic chairs (lower right) lie in region with consistent labeling (a densely populated mode, or dense mode) and thus seems to follow a strong regularity. But there are many other cases in the continuum of the two extreme. For example, the rocking chair (upper right) has a few supporting neighbors but it lies in a distinct neighborhood from the majority of label instances (the generic chairs).

---

Under review as a conference paper at ICLR 2021
Onay
Tafis
Hule
Gulor de
high C-ccon
(a)
regder
sanchaam spampi
low C-score
(b) 0-p
Figure 1: Regularities and exceptions in binary chairs non-chairs problem. (b) illustration of consistency
profiles. (c) Regularities (high C-scores) and exceptions (low C-scores) in ImageNet.
In this article, we study this continuum of the structural regularities of data sets in the context of training overparameterized deep networks. Let & P be an i.i.d. sample of size n from the underlying data distribution P, and f(:; D) be model trained on D. For an instance æ with label y. we trace out the following consistency profile by increasing n:
Cp,nls, Exp (P((, DV( DN(,)))) v),
n 0,1,
This quantity measures the per-instance generalization on (z, For fixed it characterizes how consistent (z. y) is with a sample D from P. Formally, it is closely tied to the fundamental notion of generalization performance when take an expectation over (I. Without the expectation, the quantity gives us a fine fine-grain characterization of the regularity of each individual example. This article focuses on classification problems, but the definition can be easily extended to other problems by replacing the 0-1 classification loss with another suitable loss function.
The quantity ( y) has interpretation that matches our high-level intuition about the structural regularities of the training data during (human or machine) learning. In particular, we can characterize the multimodal structure of an underlying data distribution by grouping examples in terms of model's 'ssse generalization profile for those examples when trained on data sets of increasing size. For 0, the model makes predictions entirely based on its prior belief. As increases, the model collects more information about PP and makes better predictions. For an (z;, y) instance belonging to dense mode (e.g., the generic chairs in Figure the model prediction accurate even for small n. because even small samples have many class-consistent neighbors. The blue curve in the cartoon sketch of Figure Tb illustrates this profile. For instances belonging to sparse modes (e.g., the iron throne in Figure Ta), the prediction will be inaccurate for even large as the red curve illustrates. Most instances fill the continuum between these two extreme cases, as illustrated by the purple curves in Figure Dp. To obtain a total ordering for all examples, we pool the consistency profile into scalar consistency score, or C-score by taking expectation over n. Figure D shows examples from the ImageNet data set ranked by estimated C-scores, using methodology we shortly describe. The images show that on many ImageNet classes, there exist dense modes of center- center-cropped close-up shot of the representative examples; and at the other end of the C-score ranking, there exist sparse modes of highly ambiguous examples (in many cases, the object is barely seen or can only be inferred from the context in the picture).
With strong ties to both theoretical notions of learning and human intuition, the consistency profile is an important tool for understanding the regularity and subregularity structures of training data sets and the learning dynamics of models trained on those data. The C-score based ranking also has many potential uses, such as detecting duitt--distiibution and mislabeled instances; balancing learning between dense and sparse modes to ensure fairness when learning with data from underrepresented groups; or even as a diagnostic used to determine training priority in a curriculum learning setting (Bengio et al.] 2009 Saxena et al. 2019). In this article, focus formulating and analyzing consistency profiles, and apply the C-score to analyzing the structure of real world image data sets and the learning dynamics of different optimizers. We also study efficient proxies and further applications to outlier detection.
Our key contributions follows:
2

---

Under review as a conference paper at ICLR 2021
144
14
104
3.-
Consistency profiles of training examples. Each curve in the figure corresponds to the average pro- file of set of examples, partitioned according to the under the profile curve of each example.
Figure 2:
644
2.
63
33
9.2
3.0
MNIIT
20
Sudestratie 150
60
20
90
Cifar10
Subbet rafre (96)
40
62
03
Cifar
20
Subset ratio
40
62
00
We formulate and analyze a consistency score that takes inspiration from generalization theory and matches our high level intuitions.
We estimate the C-scores with a series of approximations and apply the measure to analyze the structural regularities of the MNIST, CIFAR-10, CIFAR-100 100, and ImageNet training sets.
We demonstrate using C-scores to help analyze the learning dynamics different optimizers and consequences for generalization.
We evaluate a number of learning-speed based measures as efficient proxies for the C-score, and find that the speed at which an example is learned is strong indicator of its C-score ranking. While this observation may be intuitive in retrospect, it is nontrivial because learning speed is measured on training examples and the C-score is defined for hold-out generalization. An efficiently computable proxy has practical implications, which we demonstrate with an outler--detccton experiment.
Because the C-score is generally useful for analyzing data sets and understanding the mechanies of learning, we have released the pre-computed C-scores at (URL anonymized), together with model checkpoints, code, and extra visualizations can also be downloaded.
RELATED WORK
Analyzing the structure of data sets has been central topic for many fields like Statistics, Data Mining and Unsupervised Learning. In this paper, we focus on supervised learning and the interplay between the regularity structure of data and overparameterized neural network learners. This differentiates work from classical analyses based on input or (unsupervised) latent representations. The distinction especially prominent in deep learning where supervised learner jointly learns the classifier and the representation that captures the semantic information in the labels.
In the context of deep supervised learning, Carlini et al. (0088) proposed measures for identifying prototypical examples which could serve as a proxy for the complete data set and still achieve good performance. These examples are not necessarily the center of dense neighborhood, which is what our high C-score measures. Two prototype measures explored in Carlini et al. (2018), model confidence and the learning speed, are also measures we examine. Their holdout retraining and ensemble agreement metrics are conceptually similar to our C-score estimation algorithm. However, their retraining a two-stage procedure involving pre-training and fine-tuning; their ensemble agreement mixes architectures with heterogeneous capacities and ignores labels. Feldman (2020) and Feldman& & Zhang (2020) studied the positive effects of memorization on generalization by measuring the influence of training example
test example, and identifying pairs with strong influences. To quantify memorization, they defined a memorization score for each (I. y) in a training set as the drop in prediction accuracy on when (ar, y) is removed. A point evaluation of our consistency profile on a fixed data size n resembles the second term of their score. A key difference is that we are interested in the profile with increasing n, i.e. the sample complexity required correctly predict (Ir,)) y).
We evaluate various cheap-to-compute proxies for the C-score and found that the learning speed has strong correlation with the C-score. Learning speed has been previously studied in contexts quite different from our focus on generalization of individual examples. Mangalam & Prabhu 2019
show that examples learned first are those that could be learned by shallower nets. HHrdd al. 2016
present theoretical results showing that the generalization gap is small if SGD training completes in relatively few steps. [oneva et al. (2019) study forgetting (the complement of learning speed) and informally relate forgetting to examples being outliers or mislabeled. There is a large literature of criteria with no explicit ties to generalization as the C-score has, but provides a means of stratifying instances. For example, Wu et al. (2018) measure the difficulty of an example by the number of residual blocks in a ResNet needed for prediction.
THE CONSISTENCY PROFILE AND THE C-SCORE
The consistency profile (Equation I encodes the structural consistency of example with the underlying data distribution P via expected performance of models trained with increasingly large data sets sampled from P. However, it is not possible to directly compute this profile because P is
3

---

Under review as a conference paper at ICLR 2021
top ranked exzmples in CIFAR-10
botcem rarkedd nicamppiss with annocationn
7 9
1
5
9
7
P
7
4
/
J
6
4
7
top examples CIFAR-190
Figure 3: (a) Top ranked examples in CIFAR-10 and CIFAR-100. (b) Bottom ranked examples with annotations.
generally unknown for typical learning problems. practice, we usually have a fixed data set D consisting of N i.d. samples from P. So we can estimate the consistency profile with the following empirical consistency profile:
(x. v) END [Pff DV((..))) v),, n 0.0......A -
where D is a subset of size n uniformly sampled from D excluding (x, y). and E" denotes empirical averaging with r i.i.d samples of such subsets. To obtain reasonably accurate estimate (say, r = 1000), calculating the empirical consistency profile is still computationally prohibitive. For example, with each of the 50,000 training example in the CIFAR-10 training set, we need to train more than 2 trillion models. To obtain an estimate within the capability of current computation resources, we make two observations. First, model performance generally stable when the training set size varies within a small range. Therefore, we can sample across the range of n that we're re concerned with and obtain the full profile via smooth interpolation. Second, let D be a random subset of training data, then the single model f(: D) can be reused in the estimation of all of the held-out examples (x, y) D. As result, with clever grouping and reuse, the number of models need to train can be greatly reduced (See Algorithm !
in the Appendix).
In particular, we sample dynamically according to the subset ratio E available training set. We sample 2,000 subsets for the empirical expectation of each n and visualize the estimated consistency profiles for clusters of similar examples in Figure 2 One interesting observation is that while CIFAR- is generally more difficult than CIFAR-TO, TO, the top ranked examples (magenta lines) in CIFAR-100
of the full
more likely to be classified correctly when the subset ratio is low. Figure 3 visualizes the top ranked examples from the two data sets. Note that in CIFAR-10. 10. the dense modes from the truck and automobile classes are quite similar.
In contrast, Figure indicates that the bottom-ranked examples (cyan lines) have persistently low probability of correct classification sometimes below chance- even with a 90% subset ratio. We visualize some bottom- bottom-ranked examples and annotate them as (possibly) mislabeled, ambiguous (easily confused with another class or hard to identify the contents), and atypical form (e.g.. burning "forest", fallen "bottle"). As the subset ratio grows, regularities in the data distribution systematically pull the ambiguous instances in the wrong direction. This behavior is analogous to the phenomenon mentioned earlier that children over-regularize verbs (GO- (GOD>GOE)) as they gain more exposure to a language.
To get a total ordering of the examples in data set, we distill the consistency profiles into scalar consistency score, or C-score, by taking the expectation over n:
Co(a, v) FF, (C (x..))
(3)
4

---

Under review as a conference paper at ICLR 2021
CIFAR-ID
03%
CIFAR-ID
CIFAR-100
70%
50%
Pg
0%
30%
10%
2%
Sq Sieee Bano (e)
10%
02
0%
0%
(5.1))
0.30
0.00
0.00
8.50
1.
(p(r:e)
Op(F:a)
Figure 4: (a) Histogram of C.D,, for each subset ratio CIFAR-10, (b) Histogram of the C-score
Cp
averaged over all subset ratios on 3 different data sets.
2 .2 2
2
2
3
3
8
erb
3
2
2
3
2 2
3
3
2 7
3
3
2.
d
3
2
2
2
3 3
Figure 5: Examples from MNIST (blocks 1, 2), CIFAR-10 (blocks 3-6), and CIFAR-100 (blocks 7-10). Each block shows a single class; the left, middle, and right columns a black depict instances with high, intermediate, and low C-scores, respectively.
For the case where n is sampled according to the subset ratio 8, the expectation is taken over a uniform distribution over sampled subset sizes.
THE STRUCTURAL REGULARITIES OF COMMON IMAGE DATA SETS
We apply the C-score estimate to analyze several common image data sets: MNIST, CIFAR- 10, CIFAR-100 100, and ImageNet. See Appendix for details architectures and hyperparameters.
Figure 4a shows the distribution of Ö. CIFAR-10 for the values of corresponding to each subset ratio s E (... 90). For each s, 2000 models are trained and held-out examples are evaluated. The Figure suggests that depending s, instances may be concentrated near floor or ceiling, making them difficult to distinguish (as we elaborate further shortly). By taking an expectation over s, the C-score is less susceptible to floor and ceiling effects. Figure 4 shows the histogram of this integrated C-score on MNINT, CIFAR-10, 10, and CIFAR-100. The histogram of CIFAR-10 in Figure is distributed toward the high end, but is uniformly spread than the histograms for specific subset ratios in Figure Tt.
For MNIST, CIFAR-10, and CIFAR-100, Figure presents instances that vary in C-score. Each block of examples is one category; the left, middle, and right columns have high, intermediate, and low C-scores, respectively. The homogeneity of examples in the left column suggests dense modes generally consist of central cropped images of well aligned instances in their typical poses, with highly uniform color schemes. In contrast, many of the examples in the right column are in atypical forms or even ambiguous.
Next we apply the C-score analysis to the ImageNet data set. Training standard model ImageNet costs one to two orders of magnitude more computing resources than training on CIFAR, preventing us from running the C-score estimation procedure described early. Instead, investigated the feasibility of approximating the C-score with point estimate, i.e., selection of the s that best represents the integral score. This is equivalent taking expectation of with respect a point-mass distribution, as opposed to the uniform distribution over subset ratios. By 'best represents," we mean that the ranking of instances by the score matches the ranking by the score for a particular 8.
Figure Go shows the rank correlation between the integral score and the score for a given 8, function for our three smaller data sets, MNIST, CIFAR- 10, and CIFAR-100, Examining the green CIFAR-10 curve, there is peak at = 30, indicating that 30 yields the best point-estimate approximation for the integral C-score. That the peak is at an intermediate s is consistent with the observation from Figure that the C-score bunches together instances for low and high For MNIST (blue curve), a less challenging data set than CIFAR- 10, the peak is lower, at 10; for CIFAR-100 (orange curve), challenging data set than CIFAR-10, the peak is higher,
40
5

---

Under review as a conference paper at ICLR 2021
1.0
0.41
Figure 6: (a) Rank correlation between integral C-score and the C-score for a particular subset ratio, 8. The peak of each curve indicates the training set size that best reveals generalization of the model. (b) Joint distribution of C-score per-class means and standard deviations on Ima- geNet. Samples from representative classes (*'s) are shown in Figure
Injalla
0.0
10
(a)
Subred Ratio
322
vreddio
Camo
C-rrve H deggon
Figure 7: Example images from ImageNet. The classes are chosen have representative per-class C-score erean-standardaaae -eviaadde profiles, as shown in Figure Op. For each class, the three columns show sampled images from the (C-score ranked) top 99%, 35%, and 1% percentiles, respectively. The bottom pane shows the histograms of the C-scores in each of the 5 classes.
or s = 50. Thus, the peak appears to shift to larger for more challenging data sets. This finding is surprising: more challenging data sets require greater diversity of training instances in order to observe generalization.
Based on these observations, we picked 70 for a point estimate on ImageNet. In particular, train 2,000 ResNet-50 models each with random 70% subset of the ImageNet training set, and estimate the C-score based on those models.
The examples shown in Figure Te are ranked according to this C-score estimate. Because ImageNet has 1,000 classes, we cannot offer a simple overview over the entire data set as in MNIST and CIFAR. Instead, we focus on analyzing the behaviors of individual classes. Specifically, we compute the mean and standard deviation (SD) of the C-scores of all the examples a particular class. The mean C-scores indicates the relative difficulty of classes, and the SD indicates the diversity of examples within each class. The woo-dimensional histogram Figure depicts the joint distribution mean and SD across all classes. We selected several classes with various combinations of mean and SD, indicated by the *'s in Figure 64. We then selected sample images from the top 99%, 35% and 1% percentile ranked by the C-score within each class, and show them in Figure 7
Projectile and yellow lady's 's slipper represent two extreme cases of diverse and unified classes, respectively. Most other classes lie in the high density region of the 2D histogram in Figure (b, and share a common pattern of a densely populated mode of highly regular examples and a tail of rare, ambiguous examples. The tail becomes smaller from the class car wheel to upright and school bus.
ANALYZING LEARNING DYNAMICS WITH THE C-SCORE
In this section, we use the C-score to study the behavior of different optimizers for training deep neural networks. For this study, we partition the CIFAR-10 training set into subsets by C-score. Then we record the learning curves-model accuracy over training epochs-for each set. Figure g plots the learning curves for C-score-binned examples. The left panel shows SGD training with stagewise constant learning rate, and the right panel shows the Adam optimizer (Kingma & Ba 2015). which scales the learning rate adaptively. In both cases, the groups with high C-scores (magenta) generally learn faster than the groups with low C-scores (cyan). Intuitively, the high C-score groups consist of mutually consistent examples that support one another during training, whereas the low C-score

---

Under review as a conference paper at ICLR 2021
Tr wrw.rrryy seeehggoo
1.-
1.0
0.8
Learning speed of CIFAR-10 examples grouped by
Figure 8:
0:003
133..00
03011
133..55
0100311
143.0.9
C-score. The thick transpar- ent curve shows the average ac- curacy over the entire training
0.4
1626.00
0.4
01:221
1126.00
025-11
1750.00
025-33
1756.00
02-
0,000 14
0.304 63
115-.00
62
63303.0
115-.00
set. SGD achieves test accu- racy 95.14%. Adam achieves 92.97%.
150 125
150 125
(a) SGD
(b) Adam
groups consist of irregular examples forming sparse modes with fewer consistent peers. In the case of true outliers, the model needs to memorize the labels individually as they do not share structure with any other examples.
The learning curves have wider dispersion in SGD than in Adam. Early in SGD training where the learning rate is large, the examples with the lowest C-scores barely learn. Figure Dp shows SGD with constant learning rate corresponding to values used in each of the learning rate stages in Figure Ba, confirming that with large learning rate, the groups with the lowest C-scores are not learned well even after the full 200 epochs of training. In comparison, Adam shows less spread among the groups and as a result, converges sooner. However, the superior convergence speed of adaptive optimizers like Adam does not always lead to better generalization (Wilson al. 2017 Keskar & Socher 2017 Luo et al. 2019). We observe this outcome as well: SGD with a stagewise learning rate achieves 95.14% test accuracy, compared to 92.97% for Adam.
To develop our intuitions for this phenomenon, we are assisted by the C-score partitioning of examples in Figure 8 Starting training with a large learning rate effectively enforces sort of curriculum in which the model first learns only the strongest regularities. At a later stage when the learning rate is lowered and exceptions or outliers representation based on domain regularities, However, when training starts with a small learning rate or uses Adam to adaptively scale the learning rate, all the examples are learned similar pace. In this case, it is difficult to build simple and coherent representations that need to account for all different modes even the early stage of learning, which eventually lead to a model with less generalization power.
able to be learned, the model has already built solid
6 C-SCORE PROXIES
We are able to reduce the cost of estimating C-scores from infeasible to feasible, but the procedure is still very expensive. Ideally, we would like to have more efficient proxies that do not require training multiple models. We use the term praxy to refer to any quantity that is well correlated with the C-score but does not have a direct mathematical relation to it, as contrasted with approximations that are designed to mathematically approximate the C-score (e.g., approximating the expectation with empirical averaging). The possible candidate set for C-score proxies is very large, as any measure that reflects information about difficulty or regularity of examples could be considered. Our Related Work section mentions a few such possibilities. We examined a collection of proxies based on inter-example distances in input and latent space, but none were terribly promising. (See Appendix for details.) Inspired by our observations in the previous section that the speed-of-learning tends correlate with the C-score rankings, we instead focus on a class of learning-speed based proxies that have the added bonus of being trivial compute. Intuitively, a training example that consistent with many others should be learned quickly because the gradient steps for all consistent examples should be well aligned. One might therefore conjecture that strong regularities in a data are not only better learned at asymptote- -ledding to better generalization performance- but are also learned sooner in the time course of training. This learning speed hypothesis is nontrivial, because the C-score is defined for held-out instance following training, whereas learning speed is defined for training instance during training. This hypothesis qualitatively verified from Figure [ In particular, the cyan examples having the lowest C-scores are learned most slowly and the purple examples having the highest C-scores are learned most quickly. Indeed, learning speed is monotonically related to C-score bin.
Figure 9p shows a quantitative evaluation, where we compute the Spearman's 's rank correlation between the C-score of an instance and various proxy scores based on learning speed. In particular, we test accuracy (0-1 correctness), Pr. (softmax confidence on the correct class), Pmax (max softmax confidence across all classes) and entropy (negative entropy of softmax confidences). We use
7

---

Under review as a conference paper at ICLR 2021
Ireoccos
F=5.0008
1-3
05 R030
Knta
123
110
200
233
(0) Tranigg 10700
(4)
The Lond
Figure 9: (a) Learning speed of CIFAR-I0 examples grouped by C-score with SGD using constant
learning rate. The 4 learning rates correspond to the constants in the stage-wist wise scheduler in Figure Bh. The test accuracies for those models are 84. 44.84% 91.19%, 92.05%, and 90.82%, respectively. (b) Rank correlation (Spearman's is p) between C-score and training statistics based proxies. (c) Using C-score proxies to identify outliers on CIFAR-10.
cumulative statistics which average from the beginning of training to the current epoch because the cumulative statistics yield a more stable measure- and higher correlation than statistics based on single epoch. We also compare to a forgetting-even statistic (Toneva et al. 2019), which simply a count of the number of transitions from "learned" to "forgotten" during training. All of these proxies show strong correlation with the C-score. PL reaches o z 0.9 at the peak. pmax and entropy perform similarly, both slightly worse than pL. The plot also shows that examples with low escores are more likely to be forgotten during training. The forgetting event based proxy slightly under-perform other proxies and takes a larger number of training epochs reach its peak correlation. We suspect this is because forgetting events happen only after an example is learned, so unlike other proxies studied here, forgetting statistics for hard examples cannot be obtained in the earlier stage of training.
Finally, we present a simple demonstration of the utility of our proxies for outlier detection. We comrppt a fraction y = 25% of the CIFAR- 10 training set with random label assignments. Then during training, we identify the fraction y with the lowest ranking by three C-score proxies-cumulatte accuracy, PL. and forgetting-event statistics. Figure :: shows the removal rate-the fraction of the lowest ranked examples which are indeed outliers; two of the C-score proxies successfully identify over 95% of outliers.
7 DISCUSSION
We formulated a consistency profile for individual examples in a data set that reflects the probability of correct generalization to the example as function of training set size. This profile has strong ties to generalization theory and matches basic intuitions about data regularity in both human and machine learning. We distilled the profile into a scalar C-score, which provides a total ordering of the instances in data set by essentially the sample complexity-the amount of training data required-to ensure correct generalization to the instance. To leverage the C-score to analyze structural regularities in complex data sets, we derived C-score estimation procedure and obtained C-scores for examples in MNIST, CIFAR-10, CIFAR-100, and ImageNet. The C-score estimate helps to characterize the continuum between a densely populated mode consisting of aligned, centrally cropped examples with unified shape and color profiles, and sparsely populated modes of just one or two instances. We also used the C-score as a tool to compare the learning dynamics of different optimizers to better understand the consequences for generalization. To make the C-score useful in practice for new data sets, we explored number of efficient proxies for the C-score based on the learning speed, and found that the integrated accuracy over training is strong indicator of an example's ranking by C-score, which reflects generalization accuracy had the example been held out from the training set.
In the 1980s, neural nets were touted for learning rule- gole-governed behavior without explicit rules (Rumelhart & McClelland 1986). At the time, Al researchers were focused on constructing expert systems by extracting explicit rules from human domain experts. Expert systems ultimately failed because the diversity and nuance of statistical regularities in a domain was too great for any human to explicate. In the modern deep learning era, researchers have made much progress in automatically extracting regularities from data. Nonetheless, there is still much work to be done to understand these regularities, and how the consistency relationships among instances determine the outcome of learning. By defining and investigating a consistency score, we hope to have made some progress in this direction.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https: www.w.ensorffoo. org/ from tensorflow.org.
Software available
Yoshua Bengio. Jérôme Louradour, Ronan Collobert, and Jason Weston. Currieulum learning. In Proceedings of the 26th anmual international conference on machine learning, pp. 41-48. ACM, 2009.
Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. Lof: identifying density- based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp. 93-104, 2000.
Nicholas Carlini, Ulfar Erlingsson, and Nicolas Papernot. Prototypical examples in deep learning: Metrics, characteristics, and utility. Technical report, OpenReview, 2018.
Vitaly Feldman. Does learning require memorization? A short tale about long tail. In ACM Symposium on Theory of Computing (STOC), 2020.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Preprint, 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International Conference on Machine Learning, pp. 1225-1234. PMLR, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances neural information processing systems, pp. 8571-8580, 2018
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam sgd. arXiv preprint arXiv: 1711v:171..07628. 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In International Conference on Learning Representations, 2019.
Karttikeya Mangalam and Vinay Uday Prabhu. Do deep neural networks learn shallow learnable examples first? In ICML 2019 Workshop Identifying and Understanding Deep Learning Phenomena, 2019.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 1(8):9, 2019.
D. E. Rumelhart and J. L. McClelland. On Learning the Past Tenses of English Verbs, pp. 216-271. MIT Press, Cambridge, MA, USA, 1986.
Shreyas Saxena, Oncel Tuzel, and Dennis DeCoste. Data parameters: A new family of parameters for learning a differentiable curriculum. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 11093-11103. Curran Associates, Inc., 2019.
Tyler Scott, Karl Ridgeway, and Michael C Mozer. Adapted deep embeddings: A synthesis of methods for k-shot inductive transfer learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gameet (eds.), Advances in Neural Information Processing Systems 31, pp. 76-85. Curran Associates, Inc., 2018.

---

Under review as a conference paper at ICLR 2021
Mingxing Tan and Quoc V Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint arX.v:1905.1199000 11946, 2019.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. In International Conference on Learning Representations, 2019.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stem, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148-4158, 2017.
Zuxuan Wu, Tushar Nagarajan, Abhishek Kumar, Steven Rennie, Larry S Davis, Kristen Grauman, and Rogerio Feris. Blockdrop: Dynamic inference paths in residual networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 8817-8826, 2018.
10

---

Under review as a conference paper at ICLR 2021
A EXPERIMENT DETAILS
The details on model architectures, data set information and hyper-parameteed used in the experiments for empirical estimation of the C-score can be found in Table [T. We implement our experiment in Tensorflow (Abadi et al., 2015). The holdout subroutine used in C-score estimation is listed in Algorithm 1 Most of the training jobs for C-score estimation are run on single NVidia @ Tesla P100 GPUs. The ImageNet training jobs are run with 8 P100 GPUs using single-node multi-GPU data parallelization.
The experiments on learning speed are conducted with ResNet-18 CIFAR-10, trained for 200 epochs while batch size is 32. For optimizer, we use the SGD with the initial learning rate 0.1, momentum 0.9 (with Nesterov momentum) and weight decay is 5e-4. The stage-wise constant learning rate scheduler decrease the learning rate at the 60th, 90th, and 120th epoch with a decay factor of 0.2.
Algorithm Estimation of ČD,,.
Input: Data set D (X, Y) with N examples
Input: n: number of instances used for training
Input: k: number subset samples
Output: Ó RV; (C=,,, (z, y) (L.))ED
Initialize binary mask matrix M <- OkxN Initialize 0-1 loss matrix L t O for 21. k) do Sample n random indices I from {1...., N}
Mí, r] <-
Train from scratch with the subset X(Л, : + 1x)(X) # Y]
end for
Initialize score estimation vector Ô <- 0
j E (1, ., N) do
Q Q [:]]]
Cli sum (TT[; (um)m)((())))
end for
B TIME AND SPACE COMPLEXITY
The time complexity of the holdout procedure for empirical estimation of the C-score is O(S(AT F.). Here the number of subset ratios, & number of holdout for each subset ratio, and the average training time for neural network. E. is the time for computing the score given the k-fold holdout training results, which involves elementwise computation on matrix of size x N, and is negligible comparing to the time for training neural networks. The space complexity is the space for training a single neural network times the number of parallel training jobs. The space complexity for computing the scores is (k&N).
For kernel density estimation based scores, the most expensive part is forming the pairwise distance matrix (and the kernel matrix), which requires ((N2) space and O(N2d) time, where d is the dimension of the input or hidden representation spaces.
C MORE VISUALIZATIONSS OF IMAGES RANKED BY C-SCORE
Examples with high, middle and low C-scores from few representative classes of MNIST, CIFAR-10 and CIFAR-100 are show in Figure 5 In this appendix. we depict the results for all the 10 classes of MNIST and CIFAR- 10 in Figure and Figure II respectively. The results from the first 60 out of the 100 classes on CIFAR- 100 is depicted in Figure 12] Figure [3 and Figure [4show more examples from ImageNet. Please see (URL anonymized) for more visualizations.
11

---

Under review as a conference paper at ICLR 2021
MNIST
CIFAR-I0 10
CIFAR-100
ImageNet
Archilecture
MLPS11.226.100
Inception!
Inception"
ResNet-50 (V2)
Optimizer
SGD
SGD
SGD
SGD
Momentum
0.9
0.9
0.9
0.9
Base Learning Rate
0.1
0.4
0.4
x.1
Learning Rate Schedulerr
AC ((15%))
A(15%))
A( (15%))
Batch Size
256
512
512
128x7
Epochs
20
80
160
100
Data Augmentation
.......
Random Padded Cropping
@ Random Left-Right Flipping
Image Size
28 28
x2
32
224
Traninn Set Size
60,000
50,000
30,000
1,281,167
Number
A simplified Inception model suitable small image sizes, defined as follows: Inception :: Conv(3x3, 96) + Stagel + Stage2 + Stage3 + GlobalMaxPool + Linear.
Stagel :: Block(32, 32) + Block(32, 48) + Conv(3 x 33, 160, Stride=2).
Stage2 :: Block( 12, 48) Block(96, 64) + Block(80, 80) + Block (48, 96) + C3,v(3
240, Stridc=2).
Stage3 :: Block(176, 160) - Block(176, 160).
Block(C1, C2) Concat(Conv(Ix11, Ct). Conv(3x3.C3))
Cony :: Convolution -> BatchNormalliztion -> ReLU.
A(15) learning rate scheduler linearly increase the learning rate from 0 the base learning in the first 15% training steps, and then from there linear decrcase 0 the remaining training steps. learning rate scheduler lincarly increase the learning rate from 0 to the base learning rate in the first 15% training steps. Then the learning rate remains piccewisc constant with 10x decay 30%, 60% and 90% of the training steps, respectively. Random Padded Cropping pad pixels of zeros all the four sides of MNIST, CIFAR-IO, CIFAR-100 images and (randomly) crop back the original image size. ImageNet, a padding of 32 pixels is used for all four sides of the images.
** SinearRampppicccciicCCm
Table Details for the experiments used in the empirical estimation of the C-score.
| 7
2
2 0
3 3 8
4 4 4
5 5
969
7 7 4
8 8 $
9
9 9 9
1
2 2 >
3 3 9
4
4 9
5
5 5
99
7 7
8
8
9
9 0 9 4 S
/1
1
2 / 2 2 2 2
2
3 3 3
4
4 9
5
5
999
7 1
8 8 P 8 3
9
999
!( 7
3 33
3
4
4
5 5
999
7 7
8
9
3
/ 2
2 2 à
7
3 3
3
4
4 7
55 8
6
717
8 8
9
0
/
(
3
3 >
4
4
5
5
6665
7
8 8 5
9
0
D
6
1
1
2 2 3
3
3
9
4 4
5
5
5
6
6 6
7
7
4
8 8
/
9
4
Figure 10: Examples from MNIST. Each block shows single class; the left, middle, and right columns a block depict instances with high, intermediate, and low C-scores, respectively.
Figure 1:: Examples from CIFAR-10. Each block shows a single class; the left, middle, and right columns of block depict instances with high, intermediate, and low C-scores, respectively.
12

---

Under review as a conference paper at ICLR 2021
Figure 12: Examples from CIFAR-100. Each block shows single class; the left, middle, and right columns of block depict instances with high, intermediate, and low C-scores, respectively. The first 60 (out of the 100) classes are shown.
13

---

Under review as a conference paper at ICLR 2021
502
1000
Cancre listogrm
Cocere
llstogmm
Cesora lileggmn
Figure 13:
Example images from ImageNet. For each class, the three columns show sampled images from the (C-score ranked) top 99%, 35%, and 1% percentiles, respectively, The bottom pane shows the histograms of the C-scores in each of the classes.
200
500
Hatsgrum
Cacere
Figure 14: Example images from ImageNet. For each class, the three columns show sampled images from the (C-score ranked) top 99%, 35%, and 1% percentiles, respectively. The bottom panc shows the histograms of the C-scores in each of the classes.
14

---

Under review as a conference paper at ICLR 2021
Č
C
Ö#
CIFAR-I0
0..64
-0.009
0.083
0.103
P
CIFAR-I00
-0.998
0.117
0.105
0.151
CIFAR-10
0.012
0.006
0.055
0.070
CIFAR-I00 100
-0.066
0.078
0.070
0.101
Table 2: Rank correlation between C-score and pairwise distance based proxies on inputs. Measured with Spearman's 's and Kendall's rank correlations, respectively.
D C-SCORE PROXIES BASED ON PAIRWISE DISTANCES
We study C-score proxies based on pairwise distances here. Intuitively, an example consistent with the data distri- bution if it lies near other examples having the same label. However, if the example lies far from instances in the same class or lies near instances of different classes, might not expect it to generalize. Based on this intuition, we define relative local-density score:
-04
CIFAR-10
CIFAR-100
(+,
1 N
Σ ==1
2 = v.] 1) ((,,,)),,
(4)
Figure 15: Spearman rank correlation be- tween C-score and distance-based score on hidden representations.
where K(x,2' exp(-IIa ~'11==111//'' /12)//>>>>> is an RBF kernel with the bandwidth h, and 1[-] is the indicator function. To evaluate the importance of explicit label information, we study two related scores: Cd that uses only same-class examples when estimating the local density, and that uses all the neighbor examples by ignoring the labels.
N
1
(x,
1ly ),),),
(5)
N
N
((x)
Σ x),,,)).
(6)
We also study proxy based on the local outlier factor (L.OF) algorithm (Breunig et al. 2000), which measures the local deviation of each point with respect to its neighbours. Since large LOF scores indicate outliers, we use the negative LOF score as a C-score proxy, denoted by C (x)
Table 2 shows the agreement between the proxy scores and the estimated C-score. Agreement is quantified by two rank correlation measures on three data sets. As anticipated, the input-density score that ignores labels, C(x), and the class-conditional density, Č¹ (z, y). have poor agreement. (=*((x, y) and Óf are slightly better, However, none of the proxies has high enough correlation to be useful, because it is very hard obtaín semantically meaningful distance estimations from the raw pixels.
Since proxies based on pairwise distances in the input space work poorly, we further evaluate the proxies using the penultimate layer of the network as representation of an image: Ö#L Cj C₁. and C with the subscript h indicating that the score operates hidden space. For each score and data set, we compute Spearman's 's rank correlation between the proxy score and the C-score.
In particular, we train neural network models with the same specification as in Table Ton the full training set. We use RBF kernel K (z,z') exp(-II -ppl-llx--''1////1 //²/ where the bandwidth parameter is adaptively chosen as 1/2 of the mean pairwise Euclidean distance across the data set. For the local outlier factor (LOF) algorithm (Breunig et al. 2000),
the neighborhood size i 3. See Figure 16 for the behavior of LOF across a wide range of neighborhood sizes.
Because the embedding changes the network is trained, plot the correlation function of training epoch in Figure [5] For both data sets, the proxy score that correlates best with the C-score C+t (grey), followed by Öilif (brown), then O% (pink) and Cn (blue). Clearly, appropriate use of
15

---

Under review as a conference paper at ICLR 2021
0.25
0.20
input space
hidden space
Spearman's tho
Spearman's rho
0.20
0.15
input space hidden space
0.15
0.10
0.05
0.00
25
50
75
100
25
75
100
k
(a) CIFAR-I0
(b) CIFAR -00
Figure 16: The Spearman's 's correlation between the C-score and the score based on LOF with different neighborhood sizes.
Figure 17: Examples from CIFAR-10 (left 5 blocks) and CIFAR- 100 (right 5 blocks). Each block shows single class; the left, middle, and right columns a block depict instances with top, intermediate, and bottom ranking according to the relative local density score Ö+ in the input space, respectively.
labels helps with the ranking. However, our proxy ĆrP² uses the labels in an ad hoc manner. We will discuss a more principled measure based on gradient vectors shortly and relate it to the neural tangent kernel Jacot et al. 2018).
The results reveal interesting properties of the hidden representation. One might be concerned that as training progresses, the representations will optimize toward the classification loss and may discard inter-class relationships that could be potentially useful for other downstream tasks (Scott et al. 2018). However, our results suggest that C does not diminish as a predictor of the C-score, even long after training converges. Thus, at least some information concerning the relation between different examples is retained in the representation, even though intra- and inter-class similarity is not very relevant for a classification model. To the extent that the hidden representaiion-ccrffeedd through discriminative loss preserves class structure, one might expect that the C-score could be predicted without label reweighting; however, the poor performance of C₁ suggests otherwise.
Figure [7and and Figure 18 visualize examples in local density scores in the input and learned hidden space, respectively. The ranking calculated in the input space relies heavily on low level features that can be derived directly from the pixels like strong silhouette. The rankings calculated from the learned hidden space correlate better with C-score, though the visualization shows that the ranking are sometimes still noisy even for the top ranking examples (e.g. the class "automobile" in CIF.
100 ranked by the class weighted
D.1 PAIRWISE DISTANCE ESTIMATION WITH GRADIENT REPRESENTATIONS
Most modern neural networks are trained with first order gradient descent based algorithms and variants. In each iteration, the gradient of loss mini-batch of training examples evaluated the current network weights computed and used to update the current parameter. Let V.(.) be the function that maps lnput-label training pair (the case of mini-batch size one) the corresponding
16

---

Under review as a conference paper at ICLR 2021
Figure 18: Examples from CIFAR-10 (left 5 blocks) and CIFAR-100 (right blocks). Each block shows single class; the left, middle, and right columns of block depict instances with top, intermediate, and bottom ranking according to the relative local density score C+2 in the latent representation space of a trained network, respectively.
gradient evaluated at the network weights of the t-th iteration. Then this defines a gradient based representation which we can compute density based ranking scores. The intuition is that in gradient based learning algorithm, an example is consistent with others if they all compute similar gradients.
Comparing to the hidden representations defined the outputs of neural network layer, the gradient based representations induce more natural way of incorporating the label information. In the previous section, we reweight the neighbor examples belonging to different class by 0 or -1. For gradient based representations, no ad hoc reweighting is needed the gradient is computed on the loss that has already takes the label into account. Similar inputs with different labels automatically lead to dissimilar gradients. Moreover, this could seamlessly handle labels and losses with rich structures (e.g. image segmentation, machine translation) where an effective reweighting scheme is hard to find. The gradient based representation is closely related to recent developments on Neural Tagent Kernels (NTK) (Jacot et al. 2018). It is shown that when the network width goes to infinity, the neural network training dynamics can be effectively approximately via Taylor expansion at the initial network weights. In other words, the algorithm is effectively learning linear model on the nonlinear representations defined by V.(.). This feature map induces the NTK, and connects deep leamning to the literature of kernel machines.
Although NTK enjoys nice theoretical properties, it is challenging to perform density estimation on it. Even for the more practical case of finite width neural networks, the gradient representations are of extremely high dimensions as modern neural networks general have parameters ranging from millions billions (e.g. Tan Le 2019; Radford et al./ (019).. As result, both computation and memory requirements are prohibitive if a naive density estimation is to be computed on the gradient representations. We leave as future work to explore efficient algorithms to practically compute this score.
E WHAT MAKES AN ITEM REGULAR OR IRREGULAR?
The notion of regularity is primarily coming from the statistical consistency of the example with the rest of the population, but less from the intrinsic structure of the example's is contents. To illustrate this, we refer back to the experiments in Section 5 on measuring the learning speed groups of examples generated via equal partition on the C-score value range [0, 1]. As shown in Figure 4p. the distribution is uneven between high and low C-score values. As a result, the high C-score groups will have more examples than the low C-score groups. This agrees with the intuition that regularity arises from high probability masses.
To test whether an example with top-ranking C-score is still highly regular after the density of its neighborhood is reduced, we redo the experiment, but subsample each group to contain an equal number (~ 400) of examples. Then we run training on this new data set and observe the learning speed in each (subsampled) group. The result is shown in Figure 19 which is to be compared with the results without group-size-equalizing in Figure & in the main text. The following observations can be made:
1. The learning curves for many of the groups start overlap with each other.
17

---

Under review as a conference paper at ICLR 2021
1.0
Training accuracy of each group
0.05-0.10
0.55-0.60
0.10-0.15
0.60-0.65
0.15-0.20
0.65-0.70
0.20-0.25
0.25-0.30
0.75-0.80
0.30-0.35
0,80-0.85
0.35-0.40
0.85-0.90
0.45 0.50
All
0.50-0.55
50
100
125
150
175
200
training epoch
Figure 19: Learning speed of group of examples ranked by C-scores, with equal number (400) of examples each group via subsampling.
2. The lower ranked groups now learns faster. For example, the lowest ranked group goes above 30% accuracy near epoch 50. In the original experiment (Figure (8), this groups is still below 20% accuracy at epoch 50. The model is now learning with a much smaller data set. Since the lower ranked examples are not highly consistent with the rest of the population, this means there are fewer "other examples" to compete with (i.e. those "other examples" will move the weights towards direction that less preferable for the lower ranked examples), As result, the lower ranked groups can now learn faster.
3. On the other hand, the higher ranked groups learn slower, which is clear from direct comparison between Figure 8a and Figure 19 This is because for highly regular examples, reducing the data size means removing consistent examples that is, there are now less "supporters" as oppose to less "competitors" in the case of lower ranked groups. As result, the learn speed is now slower.
4. Even though the learning curves are now overlapping, the highest ranked group and the lowest ranked group are still clearly separated. The potential reason is that while the lower ranked examples can be outliers in many different ways, the highest ranked examples are probably regular in single (or very few) visual clusters (see the top ranked examples in Figure 5). As a result, the within group diversities of the highest ranked groups are still much smaller than the lowest ranked groups.
In summary, the regularity of an example arises from its consistency relation with the rest of the population. A regular example in isolation is no different to outlier. Moreover, it is also not merely an intrinsic property the data distribution, but is closely related to the model, loss function and learning algorithms. For example, while picture with red lake and purple forest is likely be considered an outlier in the usual sense, for model that only uses grayscale information it could be highly regular.
F SENSITIVITY OF C-SCORES TO THE NUMBER OF MODELS
We used 2,000 models per subset ratio to evaluate C-scores in our experiments to ensure that we get stable estimates. In this section, we study the sensitivity of C-scores with respect to the number of models and evaluate the possibility use fewer models in practice. Let Co-2k be the C-scores estimated with the full 2,000 models per subset ratio. We split the 2,000 models for each subset ratio into two halves, and obtain two independent estimates Co- and CIR-2k. Then for m E (1,2,4 4, 8, 16, 32, 64, 128, 256 512, 1000), we sample m random models from the first 1,000 split, and estimate C-scores (denoted by C,,) based those models. We compute the Spearman's p correlation between each C,,, and Cik-20 2k- The results are plotted in Figure[0) The random sampling of models is repeated 10 times for each and the error bars show the standard deviations. The
18

---

Under review as a conference paper at ICLR 2021
1.0
Spearman rho correlation
0.8
0.6
$=
0.4
$=30
5=40
s=50
0.2
s=60
integral C-score
2
2
29
number of models each subset ratio
Figure 20: The correlation of C-scores estimated with varying numbers of models (the x-axis) and C-scores estimated with 1,000 independent models. The simulations are run with CIFAR-10, and the error bars show standard deviation from runs.
figure shows that good correlation found for as few m 64 models. However, the integral C-score requires training models for various subset ratios (9 different subset ratios in our simulations). so the total number of models needed is roughly 64 x 9. we want obtain a reliable estimate of the C-score under single fixed subset ratio, we find that we need 512 models in order to get > .95 correlation with C1k-2t- So appears that whether we are computing the integral C-score or the C-score for particular subset ratio, we need to train on the order of 500-600 models.
In the analysis above, we have used Cik-20 24 as the reference scores to compute correlation to ensure no overlapping between the models used to compute different estimates. Note CiR-2s itself is well correlated with the the full estimate from 2,000 models, as demonstrated by the following correlations: p(Co-1k, C1k-2x) 0.9996, p(Co-1k Co-2k) 0.9999, and p(CIk-2k Co-2k) 0.9999.
G CODE AND PRE-COMPUTED C-SCORES
We provide code implementing our C-score estimation algorithms, and pre-computed C-scores and associated model checkpoints for CIFAR-1O, CIFAR-100 and ImageNet at (URL anonymized). The exported files are in Numpy's data format saved via numpy. savez. For CIFAR-10 10 and CIFAR-100, the exported file contains two arrays labels and scores. Both arrays are stored in the order of training examples defined by the original data found at bttttp:: /www. edu/~kri ci far. html] The data loading tools provided in some deep learning library might not be following the original data example orders, provided the label 1 array for easy sanity check of the data ordering.
toronto
For ImageNet, since there no well defined example ordering, we order the exported scores arbitrarily, and include a script to reconstruct the data set with index information by using the filename of each example help identify the example-score mapping.
19


Reviews:
[{"review_id": "aWoadjVzCg", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 proposes yet another score, the consistency score, to evaluate the importance of individual data samples built on held-out performance. This time the authors focus on a dynamic training perspective by studying the effect of different sample sizes. The paper is generally well written and easy to follow, despite some long confusing lines. The experiments are quite comprehensive, equipped with proper discussions. In particular, this work offers an insightful characterization of the better generalization ability of SGD through sample-level stratification according to C-score. \n\nNevertheless, I still have a few concerns about the motivation and the novelty of the paper:\n1. Lack of theoretical or empirical justification of the proposed metric. As motivated by the authors, consistency score is designed to tell regular examples from exception examples, measured by the held-out performance. But it seems more reasonable to use the relative accuracy (standard acc - held-out acc), i.e., the influence value (Feldman and Zhang 2020), to measure the learning difficulty of each individual example. Perhaps the authors should put more discussions on this topic and show the difference between the two metrics. Similarly, the authors also lack a discussion of the necessity of designing such a new metric based on held-out acc, which is hard to compute. As pointed out in Figure 9, there is a high correlation between C-score and accuracy (or prediction entropy), which also seems a good criterion for evaluating the quality of an individual example and is also quite easy to compute. Hence, an involved discussion/comparison of the choice of the particular formulation is needed, either theoretically or empirically. Without this, the novelty and motivation of this work would be questionable.\n2. Despite the inspiring introduction, the main part of the paper lacks a clear storyline and seems verbose sometimes. For example, Figure 1,3,4,5 basically tell the same natural story (C-score proportional to sample complexity) without much additional insight on the problem. The authors should focus on discussing the interesting phenomena indicated by the new metric, rather than listing every possible experiment result. As for as I can tell, a major difference/contribution of this work is that it involves the dependence on sample size, which allows it to study the dynamic training behavior. I think the authors should focus on this perspective. For example, I do not see the necessity of discussing the average C-score of different sample sizes. Except for computational stability, I wonder whether this metric really means something, not to mention that the authors do it in a rather heuristic way, by assuming a uniform distribution over sliced sample sizes. Also, Figure 6 seems to deal with a technical issue with limited computation (again a trivial phenomenon), and it could be deferred to the appendix.\n3. Personally, I find two insightful phenomena in this work worth more involved discussion. First, Figure 2 demonstrates quite different behaviors of examples with different C-scores, that the bad ones can get even worse with a large subset! Second, Figure 8 shows the C-score helps understand the superiority of SGD from a (not only intuitively understood but also empirically shown) sample-level perspective. If the authors could stick to these two stories and dig deeper, I believe the paper would be more impressive.\n\nIn all, I find this paper is well written with thorough experiments around the proposed metric. However, as mentioned above, it would be a regret that the paper lacks more in-depth discussion. I would be pleased to upgrade the score with positive feedbacks from the authors.\n\n \nMinor points:\n1. The interplay between generalization and overparameterization is not discussed at all in this paper, so the authors had better not include it in the title.\n\n\nReference:\nFeldman, V., & Zhang, C. (2020). What neural networks memorize and why: Discovering the long tail via influence estimation. arXiv preprint arXiv:2008.03703.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QgIvgxhbwbi", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 proposes a consistency score (C-score) that measures the expected accuracy of a held-out instance averaged over different training sample sizes, which can be useful for analyzing learning dynamics and generalization performance.\n\nI see some problems with the proposed approach. First of all, the proposed metric is computationally very expensive since 2,000 models need to be trained for each s. Can't we simply use the learning speed of each test sample to achieve similar goals? Measuring learning speed should be computationally much simpler since it does not require training 2,000 models if we measure the learning speed for test or validation samples. Those test samples are automatically held out since they are not in the training dataset. In fact, authors show strong correlations between C-score and other measures based on learning speed in Fig. 9. Are there *real* benefits of using C-score over simpler alternatives such as measures based on learning speed, e.g., better outlier detection performance, better accuracy for detecting mis-labeled samples, better analysis of learning dynamics and generalization performance, etc.? If there's no such *real* benefit, then it's hard to justify the use of C-score considering its high computational cost.\n\nAt s=70,80,90%, there will be a lot of overlap of samples among 2,000 subsets and I don't see much value in distinguishing such cases (70%, 80%, 90%) with such fine granularity. In Fig. 4(a), they (70%, 80%, 90%) do not show much different anyway while there's a huge difference in the histograms between 10% and the rest (20% ~ 90%). To solve this problem, I suggest using something like s=1%, 2%, 4%, 8%, ..., 64% (log scale) instead of 10%, 20%, ..., 90% (linear scale). This way, we can also see the effect of very small n, which I believe is an interesting regime to study. Using log scale may also be better for comparing consistency profiles for different datasets such as CIFAR-10 and CIFAR-100. Fig. 2 shows the consistency profile curves start at around 0.2 for CIFAR-10 at s=10% while they are more spread from 0.0 to 0.85 for CIFAR-100 at s=10%. This may be an artifact of having coarse-grained intervals for s. By using log scale, we may be able to see a similar behavior between CIFAR-10 and CIFAR-100 only shifted in log scale, e.g., the consistency profile curves for CIFAR-100 may also start around 0.2 when s=1%.\n\nI am not sure how to justify the definition of C-score that simply averages the consistency profile over uniform s from 10% to 90%. Why uniform instead of non-uniform? Why consider averaging instead of max, min, etc.? There are many other possibilities. Taking an average over uniform s seems ad hoc to me. Can authors provide a good justification? If there's no good justification, it may make sense to define C-score at a particular value of s (what authors call a point estimate) without even defining C-score averaged over s. But, this issue does not seem crucial.\n\nHow about using a higher learning rate for samples with low C-scores to facilitate learning from small number of irregular samples? This seems to be the opposite of what authors are suggesting in Figs. 8 and 9. \n\nIt would be great if authors can improve the performance of optimizers based on the observations made in Figs. 8 and 9.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Nu6_ZVjK_3E", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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:\nThis paper formulates a consistency score (C-score, which characterizes\nthe expected accuracy for a held-out instance given training sets of varying size\nsampled from the data distribution) to measure the regularity of an example. It also proposes approximations for C-score and study structural regularities of MNIST, CIFAR-10, CIFAR-100, and ImageNet. C-score is also used to learn dynamics of different optimizers and consequences for generalization. It further provides proxies (in particular, the learning speed) for C-score for practical tasks such as outlier-detection. \n\n################################################\n\nReasons for score:\nThe paper is overall well-written and presents some interesting findings about a newly proposed measure C-score. However, the novelty of the consistency score and the experiments on utilizing it for outlier detection are relatively limited. \n\n\n################################################\n\nPros:\n\n+well-written and easy to follow\n\n+interesting observations and good visualizations\n\n+experiments in general support claims\n\nCons:\n\n-Not enough results shown to demonstrate how useful this measure is and no baselines are provided.\n\n-The idea of regular/irregular is not new.\n\n-Pure empirical findings; more discussions on the theoretical side is needed\n\n\nOne of my main concerns is the practical implication of the proposed measure. Only a simple mislabelling experiment on one model and dataset is shown and no baseline methods are compared with.\n\nThe idea of attributing examples into regular examples and irregular examples is also not new. The learning speed and generalization as the authors mentioned has been previously observed. Using C-score to analyze the dynamics of different optimizers is interesting but is not explored deeper / more extensively.\n\n################################################\n\nQuestions:\n\n-Why choosing s=70 for ImageNet? rather than 50 or other numbers? Since ImageNet is much more complex than CIFAR, it is hard to tell if similar observations (other than the examples given) hold.\n\n-Ablation study on the number of models (2000 is used currently for all experiments) to train for each subset ratio should be provided at least for one dataset.\n\n-I believe the code can be made public anonymously?\n\n################################################\n\nPost-Rebuttal:\n\nI want to thanks the authors for their detailed responses. It addresses my concern of hyperparameter choices. However, after going through the responses and paper again, I decide to maintain my initial assessment. The main reasons are that 1.conceptually C-score is not very novel. The addition of this paper to our existing understanding is not that much. 2.practically the C-score does not improve the-state-of-art of outlier detection (comparison with traditional methods is lacking).\n\nI encourage the authors to further explore using C-score on improving outlier detection and comparing with existing traditional methods. Besides, diving a bit deeper into using C-score to analyze the dynamics of different optimizers will be very interesting. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes the c-score, which is the aggregation of a "consistency profile" that measures per-instance generalization.  Naive computation of the c-score is expensive and thus requires an approximation.  The paper then uses the c-score to analyze several image benchmarks and their learning dynamics.  

While the reviewers found the experiments to be well-done, their primary concern was over the novelty and ultimate usefulness of the c-score.  As R1 and R4 point out, the c-score correlates with other known measures such as accuracy and training speed.  The authors claim this is a contribution.  In turn, it is hard to tell if the c-score is a true metric of interest or a recapitulation of what is already known.  No reviewer was in favor of acceptance.
Decision: Reject