Why Fine-grained Labels in Pretraining Benefit Generalization?
Authors: Guan Zhe Hong
Yin Cui
Ariel Fuxman
Stanley H. Chan
Enming Luo
Venue: Accepted by TMLR ()

Abstract: Recent studies show that pretraining a deep neural network with fine-grained labeled data, followed by fine-tuning on coarse-labeled data for downstream tasks, often yields better generalization than pretraining with coarse-labeled data. While there is ample empirical evidence supporting this, the theoretical justification remains an open problem. This paper addresses this gap by introducing a "hierarchical multi-view" structure to confine the input data distribution. Under this framework, we prove that: 1) coarse-grained pretraining only allows a neural network to learn the common features well, while 2) fine-grained pretraining helps the network learn the rare features in addition to the common ones, leading to improved accuracy on hard downstream test samples.

Published in Transactions on Machine Learning Research (10/2024)
Why Fine-grained Labels in Pretraining Benefit Generaliza- tion?
Guan Zhe Hong Purdue University
hong2888purdue..om edu
Yin Cui NVIDIA
ginc
Ariel Fuxman Google Research
afuamon www.nglennoo.ooooooooo com
Stanley H. Chan
Spurchan edu
Purduc University
Enming Luo Google Research
enming@@oogge..om com
Reviewed on OpenReview: https: opwprevveeeeeeeeee.. net/ forum? AdjFoojA7700
Abstract
Recent studies show that pretraining a deep neural network with fine-grained labeled data, followed by fine-tuning on coarse-labeled data for downstream tasks, often yields better generalization than pretraining with coarse-labeled data. While there is ample empirical evidence supporting this, the theoretical justification remains open problem. This paper addresses this gap by introducing a "hicrarchical multi-vicw" structure to confine the input data distribution. Under this framework, we prove that: 1) coarse gaarseegrained pretraining only allows a neural network to learn the common features well, while 2) fine-grained pretraining helps the network learn the rare features in addition to the common ones, leading to improved accuracy on hard downstream test samples.
1 Introduction
We consider the theory of label granularity in deep learning. By label granularity, we mcan a hicrarchy of training labels specifying how detailed each label subclass needs to be (See Figure D
Having access to different gramularity of labels offers the freedom of training classifier using different train classifier to
level of precision. For example, instead of differentiating between dogs and cats, differentiate Poodle dog and Persian cat. The latter classification task is undoubtedly harder. However, recent studies found that if one uses fine-grained labels to pre-train a backbone, the pre-trained backbone will help the downstream neural networks generalize better (Chen et al. 2018). Vision transformers, for example, are well-known to require pretraining on large datasets with thousands classes for effective downstream generalization Dasovitskiy et al. 2021 He et. al. 2016 Krizhevsky et al. 2012).
To convince readers who are less familiar with this particular training strategy, we conduct an experiment ImageNet with details described in Appendix A.2 (we also include experiments iNaturalist 2021 in Appendix Our experiment is limited in scale due to its high demand the computing resources. Figure shows an experiment of pre-training on ImageNet21k and fine-tuning the pre-trained network using Image Nel.k. The labels used in the ImageNet21k is based on WordNet Hierarchy. The downstream lask Work done Google Research.

---

Published in Transactions on Machine Learning Research (10/2024)
Golden Retriever
Briard
Pekinese
Appenzeller
Dog Coarse Label
Gran-Grained
Pre-training
Pre-training
Fine-tuing
Fine-tuning
Downstream
Downstream
Backbone
Backhone
Figure 1: The goal of this paper is to provide thcoretical justification of why fine- Eie-graaied labels in pre- training benefit generalization.
is ImageNetlk classification. The r-axis of this plot indicates the number of pre-training classes whereas the y-axis shows the validation accuracy for the ImageNetlk classification task. It is evident from the plot that as we increase the number of classes (hence finer label granularity pre-training), the downstream classification task's performance is improved.
ImageNet1k Validation Accuracy
82
78
76
74
Baseline Hierarchy (ImageNet1k)
Fine-grained Hierarchy (WordNet ImageNet21k)
72
102
103
10
Label Granularity, i.e., Number of Classes in Pretraining
Figure 2: ImageNetlk--mmgeNellk transfer using ViT-B/16 model. [Blue]: pretrained on the WordNet hicrarchy of ImageNet21k, finetuned on ImageNetIk. [Rod]: basclinc, trained and evaluated on ImageNet1k.
1.1
Goal of this paper
The above experimental finding may sound familiar to practitioners who frequently train large models. In
fact, experimental evidence on this subject is abundant (Mahajan al. 2018 Singh al.) 2022 Yan al.
2020
Shnarch al. 2022 Juan et. al. 2020 Yang al. 2021 Chen al. 2018 Ridnik et. al. 2021 Son
et al. 2023 Ngiam al. 2018 Cui et al. 2018 2019a). However, the theoretical explanation remains
open problem. Our goal in this paper is to provide theoretical justification. The core question we ask is:
Theoretical Question
Why docs pretraining at high label gramularity benefit gencralization?
Certainly, this grand challenge can be impossible answer in full because of the uncontrollable complexity of the practical situations. To say something concrete, we focus tractable (sub-)problent under controlled setting:
Simple scheme: We pretrain backbone classification task and then finetune it for target problem;
2

---

Published in Transactions on Machine Learning Research (10/2024)
Assume negligible distribution shift between the imput distributions of the source and target datasets;
The label functions for both datasets align well in terms of the features which they consider discriminative;
The labels are error-free.
1.2 Main results and theoretical contributions
Our main result based on analyzing a two-layer convolutional neural network with ReLU activation. We assume that the data distribution satisfies a certain hierarchical multi-viww condition (to be discussed in Section 4.1 The optimization algorithm is stochastic gradient descent. Such problem settings consistent
with published works on this subject (Allen-Zhu & Li 2023b 2022
Shen et al. 2022b Jelassi & Li 2022
Our conclusions are as follows.
Theoretical results
1. Course-grained pretraining only allows the neural network to learn the common features well. Therefore, when testing, the test error on casy samples is o(1) (i.c., small) whereas the error on hard samples is 2(1) (i.e., large).
2. Fine-grained pretraining helps the network learn the rare features in addition to the common ones, thus improving its test error on hard samples. In particular, the test error rate on both easy and hard test samples are o(1) (i.c., small).
To our knowledge, a precise characterization of the test error presented in this paper has never been reported in the literature. The key enablers of our theoretical finding are the concepts of hierarchical multi-vien and representation-lael correspondence. We summarize these two concepts below:
1. Hierarchical mulli-view. To understand the label granularity problem, we argue that it necessary for coarse and fine-grained classes to be distinguished by their corresponding input features. This is consistent with the multi-view data property pioneered by Allen-Zhu & Li (2023b). We call this hierarchical multi-ciew structure. The hierarchical multi-view structure on the data makes us different from many
other deep learning theory works that assume simple or no structure in the input data (Kawaguchi 2016
Allen-Zhu & Li 2023a Ba et al. 2022 2023 Damian et al. 2022 Kumar et al. 2023 Ju et al. 2021).
2. Representation-lan label correspondence. Representation learning aims recognize features in the input data. As will be shown later in the paper, under the hierarchical multi-view data assumption, label complexity (i.e., how complex the labels are) during training influences the representation complexity (i.e., how many and what types of features are learnt), which further influences the model's generalization performance, Studying label gramularity through understanding the neural network's feature-learning process is a departure from the literature which focuses on feature selection (Jacot et al. 2018 Ju et al. 2021
2022 Pezeshki et al. 2021 Arora et al. 2019), i.e., selecting a subset of pre-determined features.
2 Related Work
2.1
Our theoretical setting compared to the literature
The subject of label granularity is immensely related to how to make a deep neural network (DNN) generalize better. In the existing literature, this is mostly explained through the lens implicit regularization and bias towards simpler solutions to prevent overfitting even when DNNs are highly overparamcterized (Lyu et al., 2021 Kalimeris et al.) 2019 Ji & Telgarsky 2019 De Palma et al. 2019 Huh et al.) 2017). An alternative approach is the concept of shorteut learning which argues that deep networks can learn overly simple solutions. As such, deep networks achieve high training and testing accuracy on in-distribution data but generalize poorly to challenging downstream tasks (Geirhos et al. 2020
Shah et al. 2020
Pezeshki et al. 2021 ).
By examining these papers, we believe that Shah et al.
2020
Pezeshki et al.
2021 are the closest to ours
because they demonstrate that DNNs perform shorteut learning and respond weakly to features that have a
weak presence the training data. However, our work departs from Shah al. 2020 Pezeshki et al. 2021 in several key ways.
3

---

Published in Transactions on Machine Learning Research (10/2024)
1. We focus on how the pretraining label space affects classification generalization, while Shah et al. (2020)
Pezeshki et al. 2021) primarily focus demonstrating that simplicity bias can be harmful to generalizen lization.
2. The core theoretical tool used by Pezeshhi et al. (2021) is the neural tangent kernel (NTK) model, which is unsuitable for analyzing the label granularity problem bocause the feature extractor an NTK model barely changes after pretraining.
3. The theoretical setting Shah et al. (2020) limited because they use the hinge loss while we use more standard exponential-tailet cross-entropy loss.
4. Our data distribution assumptions more realistic, they capture feature hierarchies in natural images, which has direct impact on the downstream generalization power of the pretrained model.
2.2 Our analytic tool compared to literature
Our theoretical analysis is inspired by recent line of work by Allen-Zhu & Li 2002 2023b); ; Shen al
(202bb). These papers analyze the feature learning dynamics of neural networks by tracking how the hidden neurons of shallow nonlinear neural networks evolve lo solve diclionary-learning- mullii-iiww approach to the data distribution which was first proposed in Allen-Zhu & Li (2023b). However, the learning problems we analyze and the results we aim to show are fundamentally different. As such, we derive the gradient descent dynamics the neural network from scratch.
problems. We adopt a
2.3 Consistency with existing empirical results
We stress that our theoretical findings are consistent with the reported empirical results in the literature, especially those that aim improve classification accuracy by manipulating the pre-training label space
MMahajan et al.) 2018 Singh ct al. 2022 Yan et al.) 2020 Shnarch et al. 2022 Juan et al.) 2020 Yang ct al.
2021 Chen et al. 2018 Ridnik et al. 2021 Son et al. 2023 Ngiam et al. 2018 Cui et al. 2018 2019a
For example, Mahajan et al. [2018] 8 [ingh et al.
(0022) use hashtags from Instagram as pretraining labels,
Yan et al. [2020); Shnarch et al. (2022) apply clustering on the data first and then treat the cluster IDs as
pretraining labels, Juan et al. (2020) use the queries from image search results, Yang et al. (2021) apply
image transformations such as rolation to augment the label space, and Chen et al. (2018); Ridnik al.
(2021) include fine-gra -ne-grained manual hierarchies in their pretraining processes. Our results corroborate the utility of pretraining on fine-grained label space.
On the empirical end, there is also work focusing exploiting the hierarchical structures present in (human-
generated) label space to improve classification accuracy Yaan et al. 2015 Zhu & Bain 2017 Goyal & Ghosh
2020 Sun et al. 2017 Zelikman et al. 2022 Silla & Freitas 2011
Shkodrani et al. 2021 Bilal el al. 2017
Goo et al. 2016 For example, Yan et al. (2015) adapt the network architecture to learn super-classes at
each hicrarchical level, Zhu Bain (2017) add hierarchical losses in the hierarchical classification task, Goyal
& Ghosh| (2020) propose hierarchical curriculum loss for curriculum learning. Our results do not directly validate these practices because more interested in understanding the influence of label granularity on model generalization.
3 Notations and Intuitions
3.1 Notations and training schemes
For a DNN-based classifier, given input image X, we can write its (pre-logit) output for class as
Fo(X pro-logit output for class e
h
x))
(1)
linear classifier
backhope network
network
parameter
where ag is the linear classifier for class c, ((:):) ) is the network backbone with parameter θ.
Referring to Figure label granularity concerns about two datasots: arre for the source (typically fine-grained) and ge for the target (typically coarso-grained). The corresponding labels are pore and ytæt, respectively. A
dataset can be represented as D (X,)). For instance, the source training dataset is Dere (Xue )rren)
Mare
4

---

Published in Transactions on Machine Learning Research (10/2024)
"Cat" feature
"D "Dog" feature
"Persian" feature
"Poodle" feature
"Cat" feature
"Dog" feature
"Siamese" feature
"G olden retriever" feature
Figure 3: A simplified symbolic representation of the cat versus dog problem.
The relevant training and testing datasets denoted Dere Dist Digt train: test Finally, the granularity of
label set is denoted G()), which represents the total number of classes.
The two learning methodologies of interest are as follows.
1. Baseline: Train Fe(.) using Dig Test Fe(-) using Dist
2. Fine-to-coarse: Train F.(.) using Dirain- This gives us the pretrained feature extractor (Oraiii)) Then finetune Fo(-) using Degt
train" Test the resulting Fe(-) using D'gt
3.2 Intuition: why higher granularity improves generalization
Consider the following toy example. There are two classes: cat and dog. Our goal is to build a binary classifier. Let's discuss how the two training schemes would work, with an illustration shown in Figure 3
1. Baseline. The baseline method tries to identify the common features that can distinguish most of the cals from dogs, for instance, the shape of the animal's ear as shown in Figure 3 These features are often the most noticeable ones because they appear the most frequently. Of course, there are hard samples, e.g., close-up shot of cat's fur. They pose limited influence during training because they relatively rare in natural images.
2. Fine-to-coarse With fine gre-grained labels, each subclass has its own unique visual features that are only dominant within that subclass. However, fine-grained features are not as common in the dataset, hence making them more difficult to be noticed. Therefore, we only present the coarse labels in the pre-training stage, the learner allowed take shortcuts by learning only the common features achieve low training loss. One strategy to force the learner learn the rarer features is explicitly label the fine-grained classes. This means that within each fine-grained class, the fine-grained features become easy to notice the common features. As result, even if common features weakly present missing in hard test sample, the network can still be reasonably robust to distracting irrelevant patterns due to its ability to recognize (some of) the finer-grained features.
4 Problem Formulation
Our first thcoretical contribution is a new data model, the hicrarchical multi-viow model. This model consists of four definitions. Compared to existing theories studying feature learning of neural networks in the literature (Allen- ChllnnZZuu & Li 2023b 2022 Shen et al. 2022b Jelassi & Li (022), these four definitions are better formulated to the label granularity problem. For the sake of brevity, we present the core concepts of our data model here, and delay its full specification Appendix B Following data model specifications, we also discuss characteristics of the learner, two-layer nonlinear convolutional neural network.
5

---

Published in Transactions on Machine Learning Research (10/2024)
4.1 New data model: hierarchical multi-view
We consider the selling where an input sample X E RdP consists of P patches æt, .., with up E Rd, where d is sufficiently large, and all our asymptotic statements are made with respect to d.
For analytic tractability, we consider two levels label hierarchy. The root of this hicrarchy has two superclasses +1 and -1. The superclass +1 has kt subclasses. We denote these k+ subclasses as We can do the same for the superclass -1 which has k- subclasses. Each sub- class has two types of features: the common features and the fine-grained features. The two types of features are sufficiently different in the sense they have zero correlation and equal magnitude. This leads to the following definition.
Definition 4.1 (Features). We define features as elements of a fixed orthonormal dictionary V = (v:) C Rd The common and fine-grained features are
Common feature: 8 V and v- V
Fine-grained feature of subclass U+,c and U- EV
The usage of an orthonormal dictionary is again choice of our model. We choose so because it is more tractable. With features defined, we can now specify patches in an input sample.
Definition 4.2 (Input patches). We define three types of patches for y E {+,-}:
(Common-feature patches) defined as Fy Uy y Sp. where op 1, and Sp oN(0, (Subclass-feature patches) are defined as up = app Sp. where op 1, and Sp ~ (00, La (Noise patches) are defined as Tp
Sp.
Within input sample X (#1 #2: Ep), there approximately s" common-feature patches and s* fuatuues- patches, the rest are all noise patches. Moreover, within a sample, the choice of has to be consistent across the feature patches. Lastly, the positions of the features patches are random.
These definitions of the input patches are illustrated in Figure
Bp =
Dp
ap
U+
Sp
ap V +tppersian
Sp
Common
Fine-grained
"cat" feature patch
"Persian" feature patch
Figure 4: Illustration of features and patches.
Some comments: An easy sample is generated according to Definition 4.2 A hard sample is generated in the same way as easy samples, except the common-featee feature patches are replaced by noise patches, and we replace a small number of noise patches by "feature-noise" patches, which are the form Fp = af. + Sp. where a. E o(1), and set one of the noise patches to C NO La) with oc- >> σe; these patches serve the role of "distracting patterns".
Definition 4.3 (Source dataset's label mapping). We say a sample X belongs to the +1 superclass if any one of its common- or subclass-featie patches contains v4 or v+,e for any [k It belongs the (+,c) subclass if any one of its cubbllss-feattrre patches contains V+.e-
Definition 4.4 (Source training set... We assume the input samples of the source training set as A are generated as in Definition 4.2 the corresponding labels are generated following Definition 4.3 Overall, we demole the source training dataset Dere...
Relation to multi-view. Our data model is inspired by the multi-view concept first proposed in Allen Zhu & Li (023b), we (1) orthonormal dictionary to define the features, (2) define input consisting

---

Published in Transactions on Machine Learning Research (10/2024)
of many disjoint high-dimensional patches, and (3) assume the existence of muitiple discriminative features per class. The reason why the original multi-view property is insufficient for our problem is that it does not consider any label hierarchy nor its link to the input structure. We resolve this issue by following our intuition that classes at different hicrarchy levels should be distinguished by their corresponding features: this naturally defines a feature hierarchy, with an exact correspondence with the label hierarchy.
Target dataset. To ensure that baseline and fine-grained training have no unfair advantage over each other, post set of new characterizations on the target dataset:
1. The input samples in the target dataset is generated according to Definition 4.2
2. The true label function is identical across the source and target datasets.
3. Since we are studying the "fine-to-coarse" transfer direction, the larget problem's label space is the rool of the hierarchy, meaning that any element of Viraia or Jest must belong to the label space (+1,-1}.
Therefore, our setting, only yor and you can differ (in distribution) due to different choices in the label granularity level. In this idealized selting, we have essentially made baseline training and coarse-grained pretraining the same procedure. Therefore, an equally valid way to view our theory's setting is to consider Dist the same as Dirain except with coarsc-grained labels. In other words, we pretrain the network on two versions of the source dataset Dere.roarse and Dare,fine and then compare the two models Dist (which has coarse garseegrained labels).
4.2 Characteristics about the learner
Our model about the learner is consistent with Allen-Zhii & Li (2023b learner a two-layer average-pooling convolutional ReLU network:
2022 : Shen et al.
(022b
The
(x =
Ocr
alwer: + ber),
(2)
p=1
where m is a low-degree polynomial in and denotes the width of the network, ( max -) is the ReLU nonlincarity, and e denotes the class. We perform a random initialization of wer ~ N of Ix) with of = 1/poly(d); we set (0) = - (ro/In(d) and manually tune it, similar to Allen-Zhu & Li (0022) Cross- entropy is the training loss for both baseline and transfer training. To simplify analysis and to locus solely on the learning of the feature extractor, we freeze der during all baseline and transfer training phases, and we use the fine-grained model for binary classification as follows: F, (X) = max.e(k: ] F (X), F-
max (X). See Appendix B.2 and the beginning of Appendix G for details learner characteristics and training algorithm.
5 Theoretical results and proof strategy
Our second theoretical contribution lies in establishing correspondence between the complexity of the labels and complerity of the network's 's representations. Under the assumption of the hierarchical multi-view data structure, the following are truc:
1. If trained with coarse-grained labels (i.e. overly simple labels), the network only learns the common features well, so its representations of the data is overly simple;
2. In contrast, training with fine-grained labels helps the network learn the fine-graines features well in addition to the common ones, ils representation of the data is more complex.
The difference in representation complexity leads to the difference in the network's downstream test accuracy.
5.1 Main results
Theorem 5.1 (Coarse-label training: baseline). (Summaryy. Let the number of subclasses be dower-bounded ky 2 polylog(d). With high probability, with proper choice of step size, there exists time T E poly(d) such
7

---

Published in Transactions on Machine Learning Research (10/2024)
that for any T [T", poly(d)), the training loss is upper bounded according to
((F())
(3)
Moreover, for an easy lest sample (X easys u), the probability of making a classification mistake is small:
P F (X S F (X (Xeeev) S o(1). for y +
(4)
However, for all E [0, poly(d)), given a hard test sample (Xhand: v), the probability of making a classification mistake is large:
P F(O 9
(Xhara) I
F(() X hara) 2 2((1, for y/ + y.
This theorem essentially says that, with a mild lower bound on the number of fine-grained classes, if we only train on the easy samples with coarse labels, it is virtually impossible for the network to learn the fine-grained features even if we give it as much practically reachable amount of time and training samples as possible. Consequently, the network would perform poorly on the hard downstream test samples: if the sample is missing the common features, then the network can be easily misled by the noise present the sample. To see the full sctup and statement of this theorem, please see Appendix and E Its proof spans Appendix to F
Theorem 5.2 (Fine- Saate-rrined--lbbe training). (Summory). Assume the same setting as in Theorem 5. except let the labels be fine-grained and ky S d (number of subclasses not pathologically large; see Section for discussion). Within poly(d) time, the probability of making classification mistake is small:
P
S o(1) for 3' $y.
(6)
the largel binary problem on both easy and hard lest samples.
The full version of this result presented in Appendix G.4 and its proof in Appendix G After fine-grained
pretraining, the network's feature extractor gains a strong response to the fino-grained features, therefore its accuracy on the downstream hard Lest samples increases significantly.
Remark. One concern about the above theorems is that the neural networks are trained only easy samples. As noted in Sections 1 and 3.2 easy samples should make up the majority of the training and testing samples. Pretraining at higher label granularities only improves network performance on rare samples. Our theoretical result presents the feature-learning bias of a neural network in an exaggerated fashion. Therefore, it is natural to start with the case of no hard training samples. In reality, even a small portion of hard training samples is present, finite-sized training datasets can have many flaws that can cause the network overfit severely before learning the fine-grained features, especially since rarer features learnt more slowly and corrupted by greater amount of noise. We leave these deeper considerations for future theoretical work.
5.2 Proof strategy: representation-late label correspondence
The key idea of the proof is to establish correspondence between the complexity of the labels and complesity of the network's 's representations We show that when trained on coarse- grained labels (i.e. overly simple labels), the network only learns the common features well, so its representations of the data is overly simple. In contrast, training with fine-grained labels helps the network learn the fine mne-grained features well in addition to the common ones, so its representations are more complex.
We first sketch the proof of baseline training which uses coarse-grained labels.
Feature detector neurons. We show that, at initialization, with high probability, for every feature V, there exists small group of "lucky" neurons, denoted S7 (v) (with y indicating the superclass), that only activate u-dominated feature patches. We prove that if v is feature of class y, then with high probability,
8

---

Published in Transactions on Machine Learning Research (10/2024)
the lucky neurons will remain activated v-dominated patches throughout training, and dominate the feature extractor's response to the feature v. In particular, given any o-dominated patch up = Op Sp.
Σ ( ( kp)
a ((w kp) + b..) t poly(d)
(7)
4.
rESy (v)
network representation of p-dominated patch 2pp
detector neurons' response to u-dominated patch iy
Therefore, we call neurons in (n) the detector neurons of feature v.
The significance of equation is that, we may now argue about the network's represenlation of the inpul data solely based on the behavior of the feature detector neurons.
Impartial representation at initalization. At initialization, the feature extractor's response to common and fine-grained features are very close. The reason is that, (v) ~ (u') for all superclasses y and features v, v', and they all have a similar magnitude of activation strength. Written explicitly, given any common-feature patch Zcom = any + Ç and subclass-feate feature patch @anh = a Uyu. c + S (from the training or testing distribution), with high probability.
Σ
((ws)) (o auy only + 5) +
a ((w a'u Dgec + 5¹) + ((0))
(8)
rES, (0) (v,)
rESt (ey.c)
network representation of commmon-fenture patch Woom at
network represeutation of subclass-feature patch Webh at
So what happened during training which caused a strong imbolance of representation of the common and fine-grained features in the end? The answer below is the core of the proof.
Overly simple labels = overly simple representations. The imbalance of growth a result of the subclass-feature patches occurring with less frequency in the training set than the common-feature patches. Recall that the number of subclasses ky: for any subclass (y. c), subclass-featur patches dominated by dg.e are about. by times
than the common feature patches. This has direct impact. the growth speed of the common and ine-grained detector neurons: for any neuron Feom E S. s0)( (vy) and any Time E ( (Dy.c), (Awy..cmm Un) x (Kgg) x (Aw Vg.c)-
With careful arguments on the influence of noise and bias the activation values, we show that, for sufficiently large, the fine-grained detector neurons are about O(ky) times weaker in strength:
o ((wol a +c) b(1))) ~ θ (ky) x
Σ
((w a' uy 5¹) + ((e)
(9)
rest (0) (w,)
rES, (0) (v,
network representation of common-feature patch deom at large
network representation of subclase-feature patch aoub at large
Furthermore, we prove that, due to the exponential tail of cross-cntropy, by the end of training,
m
o ((wuf)) (AAuffrr on, + +c) + y.r = (log(d))
(())
(10)
rES (wy)
which causes the representation of subclass-feature patches to be vanishing in strength:
o (ww + <¹) + 6(0) 00 log(d)
< o(1), t t poly(d).
(11)
ky
PEST (1).e)
In other words, the neural network almost cannot detect subclass features by the end of bascline training. Therefore, though it classify the easy test. samples correctly since it learned the common features

---

Published in Transactions on Machine Learning Research (10/2024)
well, it simply cannot classify the hard ones, which requires the model to solely rely gubblasssfcaturre patches for inference.
Fine-grained training alleviates this issue.
Complex labels = complex: representations. The proof of fine-grained training proceeds a very similar fashion as the case of coarso-grained training. The main difference lies the gradient updates. During training, for any neuron From E (y.e) (by) and any Vhine E (v.c) (%),)),
(0)
Aun( (t)
(Mic) vb) ( 10
(rne)) Vy.c
(12)
In other words, the common and fine-grained detector neurons for each subclass grow at similar speeds now, because the common- and subclass-featur patches occur with similar frequency in each subclass. Again with careful analysis of how the noise and bias influence the activation values, we arrive at
(10 (v.e))) only 5) (u.e)rr)
a ( 5¹) + 6.0 (8.c).r)
a' oy
r (2.c) (g.0) (wy)
rESt (w.e) (mpie)
(13)
network representation of common-festure patch #coms end of training
network representation of subclass-feature patch Baubi end of training
2 2(1)
2 9(1)
Therefore, both the common and fino-grained features are learnt well. It follows that the model can correctly utilize the common- and subclass-fealure patches in the input, so it can classily easy and hard test samples with high accuracy.
6 Empirical Results
Building on our theoretical analysis in an idealized setting, this section discusses conditions on the source and target label functions that we observed to be important for fine-grained pretraining work in practice while remaining in the controlled setting described in Section I for the sake of tractability. We present the core experimental results obtained on ImageNet21k and iNaturalist 2021 in the main text, and leave the experimental details and ablation studies to Appendix A
6.1 ImageNet21K=IImgeeNee transfer experiment
This subsection provides more details about the experiment shown in Figure 2 Specifically, we show that the common practice of pretraining on ImageNet21k using leaf labels is indeed better than pretraining at lower granularities in the manual hierarchy.
Hierarchy definition. The label hierarchy in ImageNet22k is based on WordNet Miller 1995 Deng el al. (2009). To define fine-grained labels, we first define the leaf labels of the dataset as Hierarchy level For each image, we trace the path from the leaf label to the root using the WordNet hierarchy. We then set the k-th synset (or the root synset, if it is higher in the hierarchy) procedure also applies to the multi-label samples. This is how we generate the hierarchies shown in Figure 2
the level-k label of this image. This
Network choice and training. For this dataset, we use the more recent Vision Transformer ViT-B 16 Dosovitskiy et al. (2021). Our pretraining pipeline is almost identical to the one in Dosovitskiy et al. 2021
For fine-tuning, we experimented with several strategies and report only the best results the main text; the finer details are discussed in Appendix AA.12 and A.2 To ensure fair comparison, we also used these strategies to find the best baseline result by using Digt train for pretraining.
6.2 Transfer experiment on iNaturalist 2021
We conduct a systematic study of the transfer method within the label hierarchies of iNatualiist 2021 (Horn) & macaodha 2021). This dataset is well-suited for analysis because it has manually defined label
10

---

Published in Transactions on Machine Learning Research (10/2024)
hierarchy that is based on the biological traits of the creatures in the images. Additionally, the large sample size of this dataset reduces the likelihood of sample-starved pretraining on reasonably fine-grained hierarchy levels.
Our experiments on this dataset again demonstrate that, as long as the finer-graine labels contain little noise, are well-aligned with the target label space, and sample count per subclass is not too limited, then we observe improvement in the model's generalization performance. However, we also show negative results outside of the aforementioned "nice regime": when sample count per sub-class is limited, or the fine- the-grained labels are noisy, potentially misaligned with the target label space's, finer-grained labels do not necessarily improve generalization significantly.
Relevant datasets. We perform transfer experiments within INaturalis More specifically, we set Peaan and Amain both equal to the training split of the input samples in NNtuuaaist2021, and set & to the testing split of the input samples in NNtuuralist2221. To focus on the "fine-to-coarse" transfer sctting, the largel problem is to classify the root. level of the manual hierarchy, which contains 11 superclasses. To generate greater gap between the performance of different hierarchies and to shorten training time, we use the mini version of the training set in all our experiments.
Alternative hierarchies generation. To better understand the transfer method's operating regime, we experiment with different ways of generating the fine-grained labels for pretraining: we perform kMeass clustering on the ViT-L/14-based CLIP embedding Radford et al. (2021); Dehghani et al. (2022) of every sample in the training set and use the cluster IDs as pretraining class labels. We carry out this experiment in two ways. The green curve in Figure 5 comes from performing kMeans clustering on the embedding of each superclass seporately, while the purple onc's cluster IDs are from performing kMeans on the whole dalaset. The former way preserves the implicit hierarchy of the superclasses in the cluster IDs: samples from superclass & cannot possibly share cluster ID with samples belonging to superclass k' * k. Therefore, its label function is forced to align better with that of the 11 superclasses than the purple curve's. We also assign random class IDs to samples.
Network choice and training. We experiment with ResNet 34 and 50 on this dataset. For pretraining on Dirain with fine-grained labels, we adopt standard 90-epoch bate--batc--size training procodure commonly used on ImageNet He et al. (2016] : Goyal et al. (0117). Then we finetune the network for 90 epochs and test it on the 11-superclass a fair comparison, we trained the baseline model using exactly the same training pipeline, except that the pretraining stage uses Dist We observed that this "retraining" bascline consistently outperformed the naive one-pass 90-epoch training baseline on this dataset. Due to space limilations, we leave the results of ResNet50 to the appendix.
D. train and Dis respectively, using the pretrained backbone h h( To ensure
Interpretation of results. Figure shows the validation errors of the resulting models on the 11-superclass problem. We make the following observations.
Reasonably fine-grained labels benefit generalization, but there is catch. We can observe that in the blue curve of Figure 5 that, as long as the number of subclasses is less than 10 we see obvious decline in the validation error on the target labels. In other words, reasonably fine-grained pretraining is indeed beneficial in this setting. We should note, however, the overall curve exhibits a U shape: overly fino-grained labels are not beneficial to downstream generalization. This is intuitive. If the pretraining granularity is too close to the target one, we should not expect. improvement. On the other extreme, if we assign a unique label to every sample in the training data, it is highly likely that the only differences a model can find between each class would be frivolous details of the images, which would not be considered discriminative by the label function of the target coarse-label problem. In this case, the pretraining stage is almost meaningless and can be misleading, as evidenced by the very high sabe-lee error (red star in Figure 5)
High gronularity can be helpful, but aasil-assigmment consistency is critical. Random class ID pretraining (orange curve) performs the worst of all the alternatives. The label function of this type does not generate meaningful hierarchy because it has no consistency in the fcatures it considers discriminative when dccomposing the superclasses. This is in stark contrast to the manual hierarchies, which decompose the superclasses based on the finer biological traits (mostly visual in nature) of the creatures in the image.
11

---

Published in Transactions on Machine Learning Research (10/2024)
6.5
Validation Error
5.5
Baseline: Retraining
Baseline: One-pass
SubclassiD Random
88
SubclassID KMean/Class
SubclassiD kMean/All
SubclassID Manual
4.5
10
102
103
10
10
10
Label Granularity, i.e., Number of Classes in Pretraining
Figure 5: In-dataset transfer. ResNet34 validation error (with standard deviation) of finctuning 11 superclasses of iNaturalist 2021, pretrained on various label hierarchies. The manual hierarchy outperforms the baseline and every other hierarchy, and exhibits U-shaped curve.
Alignment between fine-grained and target label spaces important. For fino-grained pretraining to be effective, the features that the pretraining label function considers discriminative must align well with those valued by the label function of the 11-superclass hierarchy. To see this point, observe that for models trained on cluster IDs obtained by performing kMcans on the CLIP embedding samples in cach superclass separately (green curve in Figure 5 their validation errors are much lower than those trained on cluster IDs obtained by performing kMeans on the whole dataset. (purple curve Figure 5). As expected, the manually defined fine-grained label functions align best with that of the 11 superclasses, and the results corroborate this view.
7 Discussion
Q: Are there other reasons why fine-grained labels benefit neural network generalization?
A: Yes, it is possible, c.g., the optimization landscape induced by finer-grained labels could contain less saddle points, making it friendlier to SGD. We did not analyze this because our focus is primarily the generalization instead of optimization aspect of the problem.
Q: Does a higher label granularity always imply better generalization?
A: No. There an operating regime. Training a model with pathologically high label granularity harmful. For example, if we assign unique class every sample in the dataset, the model will be forced to rely on the frivolous differences between each sample. We verify this intuition in Figure 5 in Appendix A..11 on the iNaturalist 2021 dataset. These extreme scenarios do not arise in common practice, we do not focus them in this paper.
Q: The theoretical selling appears restrictive.
A: Our theoretical sctting consistent with Cao al. (2022); Allen-Zhu & Li (2023b 2022);
Shen al.
(2022b); Jelassi Li (2022). With limited number available analytic tools the literature, we believe these singsngs necessary to keep things tractable.
12

---

Published in Transactions on Machine Learning Research (10/2024)
8 Conclusion
In this paper, we formally studied the influence of pretraining label gramlarity on the generalization of DNNs, and performed large-scale experiments to complement our theoretical results. Under the new data model, hierarchical multi-view, we theoretically showed that higher label complexity leads to higher representation complexity, through which we explained why pretraining with fine-grained labels is beneficial to generalization. We complement our theory with experiments on ImageNet and iNaturalist, demonstrating that in the controlled setting of this paper, pretraining on reasonably fine-grained labels indeed benefits generalization.
Broader Impact Statement
This paper presents work whose goal is to advance the theory of deep learning. There are potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Zeyuan Allen-Zhi and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In FOCS, 2022.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep (hierarchi- cal) learning. In COLT, 2023a.
Zeyuan Allen- Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. In ICLR, 2023b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact. computation with an infinitely wide neural net. In NewrIPS, 2019.
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High-dimensional asymptotics of feature learning: How one gradient step improves the representation. In NewrIPS, 2022.
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu. Learning in the presence of low-dinensional structure: A spiked random matrix perspective. In NewrIPS, 2023.
Alsallakh Bilal, Amin Jourabloo, Mao Ye, Xiaoming Liu, and Liu Ren. Do convolutional neural networks learn class hierarchy? IEEE transactions on visualization and computer graphics, 2017.
Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. In NeurIPS, 2022.
Zhuo Chen, Ruizhou Ding, Ting-Wu Wu Chin, and Diana Marculescu. Understanding the impact of label gramularity on can-basod image classification. In ICDMW, 2018.
Yin Cui, Yang Song, Chen Sun, Andrew Howard, and Serge Belongic. Large scale fine-grained categorization and domain-specific transfer learning. In CVPR, 2018
Yin Cui, Zeqi Gu, Dhruv Mahajan, Laurens Van Der Maaten, Serge Belongie, and Ser-Nam Lim. Measuring dataset gramularity. arXiv preprint arXiv:1912.10155 2019a.
Yin Cui, Menglin Jia, Tsung-Yr Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In CVPR, 2019b.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In COLT, 2022.
Giacomo De Palma, Bobak Kiani, and Seth Lloyd. Random deep neural networks are biased towards simple functions. In NeurIPS, 2019.
Mostafa Dehghani, Alexey Gritsenko, Anurag Arnab, Matthias Minderer, and Yi Tay. Scenie: A jax library for computer vision research and beyond. In CVPR, 2022.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
Robert Geirhos, Jörn- Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A. Wichmann. Shortcut learning in deep neural networks. In Nature Machine Intelligence, 2020.
Wonjoon Goo, Juyong Kim, Gunhee Kim, and Sung Ju Hwang. "axoonomy-regulaiize semantic deep convolutional neural networks. In ECCV, 2016.
Palash Goyal and Shalini Ghosh. Hierarchical 2020.
curriculum loss. arXiv preprint (XXx:2006.0362)
Priya Goyal, Piotr Dollar, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming Hc. Accurate, large miníbatch sgd: Training imagenct in 1 hour. vrXii:1706.000 02677, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Grant Van Horn and macaodha. inat challenge 2021 fgvc8, 2021. URL inaturalist-2021
Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks. arXiv:2108.10427 2017.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In NewrIPS, 2018.
Samy Jelassi and Yuanzhi Li. Towards understanding how momentum improves generalization in deep learning. In JCML, 2022.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In ICLR, 2019. Ralph P. Boas Jr. and Jr. John W. Wrench. Partial sums of the harmonic series. The Americun Mathemationl Monthly, 1971.
Peizhong Ju, Xiaojun Lin, and Ness Shroff. On the generalization power of overfitted two-layer neural tangent kernel models. In ICML, 2021.
Peizhong Ju, Xiaojun Lin, and Ness Shroff. On the generalization power of the overfitted three-layer neural tangent kernel model. In NewrIPS, 2022.
Da-Cheng Juan, Chun-Te Ta Lu, Zhen Li, Futang Peng, Aleksei Timofeev, Yi-Ting Chen, Yaxi Gao, Tom Duerig, Andrew Tomkins, and Sujith Ravi. Ultra fine-grained image semantic embedding. In WSDM, 2020.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang. Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. In NeurIPS, 2019.
Stefani Karp, Ezra Winston, Yuanzhi Li, and Aarti Singh. Local signal adaptivity: Provable feature learning in neural networks beyond kernels. Tn NewrIPS, 2021.
Kenji Kawaguchi. Deep learning without poor local minima. In NewrIPS, 2016.
Alex Krizhevsky, Πya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In NeurIPS, 2012.
Tanishq Kumar, Blake Bordelon, Samuel J. Gershman, and Cengiz Pehlevan. Grokking as the transition from lazy to rich training dynamics. arXi::2310006110, 2023.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Béatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Stalislics, 28(5); 2000.
Kuang-Huei Lee, Amurag Arnab, Sergio Guadarrama, John Canny, and Tan Fischer. Compressive visual representations. In NewrlPS, 2021.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. In NeurIPS, 2021.
Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens Van Der Maaten. Exploring the limits of weakly supervised pretraining. In ECCV, 2018.
George A Miller, Wordnet: a lexical database for english. Communications of the ACM, 1995.
Jiquan Ngiam, Daiyi Peng, Vijay Vasudevan, Simon Kornblith, Quoe V Le, and Ruoming Pang. Domain adaptive transfer learning with specialist models. arXiv preprint arXiv:1811.07055 2018.
Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron C Courville, Doina Precup, and Guillaume Lajoie. Gradient starvation: A learning proclivity neural networks. In NewrIPS, 2021.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and llya Sutskever. Learning transferable visual models from natural language supervision. In ICML, 2021.
Tal Ridnik, Emanuel Ben- Baruch, Asaf Noy, and Lihi Zelnik. mnagenct-21k pretraining for the masses. In NewrIPS Track on Datasets and Benchmorks, 2021.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. In NewrIPS, 2020.
Ruoqi Shen, Sebastien Bubeck, and Suriya Gunasckar. Data augmentation as feature manipulation. In JCML, 2022a.
Ruoqi Shen, Sebastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipulation. In ICML, 2022b.
Sindi Shkodrani, Yu Wang, Marco Manfredi, and Nóra Baka. United we learn better: Harvesting learning improvements from class hicrarchies across tasks. arXiv preprint arXi::2107.13627, 2021.
Eyal Shnarch, Ariel Gera, Alon Halfon, Lena Dankin, Leshem Choshen, Ranit Aharonov, and Noam Slonim. Cluster & tune: Boost cold start performance in text classification. arXiv preprint arXiv:2203.105: 2022.
Carlos N Silla and Alex A Freitas. A survey of hierarchical classification across different application domains.
Data Mining and Knowledge Discovery, 2011.
Mannat Singh, Laura Gustafson, Aaron Adcock, Vinicius de Freitas Reis, Bugra Gedik, Raj Prateek Kosaraju, Dhruv Mahajan, Ross Girshick, Piotr Dollár, and Laurens Van Der Maaten. Revisiting weakly supervised pre-training of visual perception models. In CVPR, 2022.
Donghyun Son, Byounggyu Lew, Kwanghee Choi, Yongsu Baek, Seungwoo Choi, Beomjun Shin, Sungjoo Ha, and Buru Chang. Reliable decision from multiple subtasks through threshold optimization: Content. moderation in the wild. In WSDM, 2023.
Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data in deep learning era. In ICCV, 2017.
Xueting Yan, Ishan Misra, Abhinav Gupta, Deepti Ghadiyaram, and Dhruy Mahajan. Clusterfit: Improving generalization of visual representations. In CVPR, 2020.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Zhicheng Yan, Hao Zhang, Robinson Piramuthu, Vignesh Jagadeesh, Dennis DeCoste, Wei Di, and Yizhou Yu. Hd-cnm: hierarchical deep convolutional neural networks for large scale visual recognition. In ICCV, 2015.
Chuanguang Yang, Zhulin An, Linhang Cai, and Yongjun Xu. Hierarchical self-supervised augmented knowledge distillation. arXiv preprint arXi::2107.13715, 2021.
Eric Zelikman, Jesse Mu, Noah D Goodman, and Yuhuai Tony Wu. Star: Self-taught reasoner bootstrapping reasoning with reasoning. In NewrIPS, 2022.
Xinqi Zhu and Michael Bain. B-cnn: branch convolutional neural network for hierarchical classification. arXiv preprinl or Xiv: 109. 709. 09890, 2017.
16

---

Published in Transactions on Machine Learning Research (10/2024)
Appendix
A Additional Experimental Results
In this section, we present the full details of our experiments and relevant ablation studies. All of our experiments were performed using tools in the Scenie library DDhggaan et al. (2022).
A.1 In-dataset transfer results
To clarify, in this transfer setting, we are essentially transferring within a dataset. More specifically, we set x = x and only the label spaces yare and yıst may differ (in distribution). The baseline in this setting is clear: train on Digt and test on Digt In contrast, after pretraining the backbone network h(O:.) on ysee finetune or linear probe it Digt train using the backbone and then test on Digt
test.
A.1.1 iNaturalist 2021
INaturalist 2021 is well-suited for our analysis because it has a high-quality, manually defined label hierarchy that is based on the biological traits of the creatures in the images. Additionally, the large sample size of this dataset reduces the likelihood of samplo-starved pretraining on reasonably fine-grained hicrarchy levels. We use the mini training dalaset with size 500,000 instead of the full training dalaset to show greater gap between the results of different hierarchies and speed up training.
We use the architectures ResNet 34 and 50 He et al. (016))
Training details. Our pretraining pipeline on iNaturalist is ealentially the same as the standard large-batch- size ImageNet-type training for ResNets He et al. (0016) to model protraining on any hicrarchy.
Goyal et al. (2017). The following pipeline applies
Optimization: SGD with 0.9 momentum coefficient, 0.00005 weight decay, 4096 batch size, 90 epochs lotal training length. We perform 7 epochs of linear warmup in the beginning of training until the learning rate reaches 0.1 x 4096/256 1.6, and then apply the cosine annealing schedule. Each training instance is run on 16 TPU v4 chips, taking around 2 hours per run.
Data augmentation: subtracting mcan and dividing by standard deviation, image (original or its horizontal flip) resized such that its shorter side is 256 pixels, then a 224 x 224 random crop is taken.
For finetuning, we keep everything in the pipeline the same except setting the batch size to 4096/4 1024 and base learning rate 1.6/4= 0.4. We found that finetuning at higher batch size and learning rate resulted in training instabilities and severely affected the final finetuned model's validation accuracy, while finetuning at lower batch size and learning rate than the chosen one resulted in lower validation accuracy at the end even though their training dynamics was stabler.
For the bascline accuracy, as mentioned in the main text, to ensure fairness of comparison, addition only training the network on the target 11-superclass problem for 90 epochs (using the same pretraining pipeline), also perform "retraining": follow the exact training process of the models trained on the various hierarchies, but use Digt train the training dataset in both the pretrianing and finetuning stage. We observed consistent increase in the final validation accuracy of the model, so we report this as the bascline accuracy. Without retraining (so naive one-pass 90-epoch training on 11 superclasses), the average accuracy with standard deviation is 93.13, 0.025.
Clustering. To obtain the Mister-ID-baaseee labels, we perform the following procedure.
1. For every sample X, in the mini training dataset of iNaturalist 2021, obtain its ViT-L/14 CLIP embedding E,,-
2. Per-superclass kMeans clustering. Let C be the predefined number of clusters per class.
17

---

Published in Transactions on Machine Learning Research (10/2024)
Table 1: In-dataset transfer, iNaturalist 2021. ResNet34 average finetuning validation error and standard deviation on 11 superclasses in iNaturalist 2021, pretrained on various label hierarchies with different label granularity. Baseline (11-superclass) and best performance are highlighted.
Manual Hierarchy
(()"
11
13
51
273
1103
4884
6485
Validation error
5.25++0.051
5.40++0.075
5.10=0.038
4.83++00041
4.79+0.045
4.82++0.056
4.84++0.033
Random class ID
(()
22
88
352
1,408
5,632
11,264
600,000
Validation error
6.61+0.215
0.30:10,070
6.12+0.77
6.10+1.053
6.12+0.042
6.10:700057
6.5440.758
CLiP+kMeans
([]
22
88
352
1408
2816
5632
22528
per superclass
Validation error
5.14+0.049
5. 0.00330033
5.17=0.027
5.24+000299
5.30=0.029
5.31=0.077
5.37+00032
C per supclass
G()
88
218
320
608
1040
1984
Class rebalanced
Validation error
5.1810.054
5.17:10.038
5.23-0.052
5.2811.0115
5.2610.003
5.21+0.004
CLIP+KMeans
(()
352
1408
2816
whole dataset
Validation error
5.52+0.015
5.42+00044
5.45+0.049
0.469
5.60++.029
5.50++0009
5.47++0.029
(a) For every superclass k for the set of embedding {(En: V/. = k)} belonging to that superclass, perform kMeans clustering with cluster size set to C.
(b) Given a sample with superclass ID k {1, 11} and cluster ID E {1,2, Cj2 define its fine-grained ID C k c.
Whole-datasct kMeans clustering. Let C. be the predefined number of clusters on the whole dataset.
(a) Perform kMeans on the embedding of all the samples in the dataset, with the number of clusters set to C. Set the fine-grained class TD of a sample to its cluster ID.
Some might have the concern that having the same number of kMeans clusters per superclass could cause certain classes to have too few samples, which could be a reason for why the cluster TD hierarchies perform worse than the manual hierarchies. Indeed, the number of samples per superclass on iNaturalist is different, so in addition to the above "uniform- Vuniforn-number-oo cumber--f-chuster-eeee perssstrrppesssperlllssssss hicrarchy, we add an extra label hierarchy by performing the following procedure balance the sample size of each cluster:
1. Perform kMeans for each superclass with number of clusters set to 2, 8, 32, 64, 128, 256, 512, 1024 and save the corresponding maage-ID-to-clustern dictionaries (so we are basically reusing the clustering results of the CLiP+kMeans per superclass experiment)
2. For each superclass, find the -attge----t---uuster----- dictionary with the highest granularity while still keeping the minimum number of samples for each cluster predefined threshold (e.g. 1000 samples per subclass)
3. Now we have nonuniform granularity for each superclass while ensuring that the sample count per cluster is above some predefined threshold.
This simple procedure somewhat improves the balance of sample count per cluster, for example, Figure 6 shows the sample count per cluster for the cases of total number of clusters = 608 and 1984. Unfortunately, we do not observe any meaningful improvement on the model's validation accuracy trained on this more refined hierarchy.
Experimental procedures. All the validation accuracies we report on ResNet34 are the averaged results of experiments performed on at least 6 random sceds: 2 random scods for backbone pretraining and random seeds for finetuning. We report the average accuracies with their standard deviation on various hierarchies in Table
An additional experiment we performed with ResNet34 is small grid scarch over what checkpoint of a pretrained backbone we should use for finetuning on the 11-superclass method; we tried the 50-, 70- and 90-epoch checkpoints of the backbone on the manual hierarchies. We report these results in Table [ As we can see, 90-epoch checkpoints performs almost equally well as the 70-epoch checkpoints and botter than the 50-epoch ones by a nontrivial margin. With this observation, we chose to use the pretraiiir 90-epoch checkpoints in all our other experiments without further ablation studies those hierarchies.
18

---

Published in Transactions on Machine Learning Research (10/2024)
Table In-dataset transfer, iNaturalist 2021. ResNet34 average finetuned validation error and standard
deviation on 11 superclasses in iNaturalist 2021, pretrained on the manual hicrarchies, with different backbone checkpoints.
90-Epoch ckpt
9(
13
51
273
1103
4884
6485
Validation error
5.40:10.075
5.10.10.038
4.83:10.041
4.79-10.045
4.82.100066
4.84-10.033
70-Epoch ckpt
(()
13
273
1103
4884
6485
Validation error
5.43+0.055
5.08+0.009
4.86+0.037
4.82+00034
4.83+00064
4.85++0.018
50-Epoch ckpt
(()
13
1103
4884
6485
Validation error
5.53
5.2=0.031
4.90::0003
4.9:0.0422
4.91
4.95:t0.026
Table 3: In-dataset transfer, iNaturalist 2021.
ResNet50 finetuned average validation error and standard deviation on 11 superclassos in iNaturalist 2021, pretrained on label hicrarchies with different label granularity.
Manual Hierarchy
G())
11
13
51
273
1103
4884
6485
Validation error
4.43
00009
4.44+00063
4.36+0.062
4.22++0.21
4.20++0.035
4.23++0.054
4.33++0.03
Randor class ID
22
88
352
1,408
5,632
11,264
500,000
Validation error
5.36:10.111
5.31910.079
5.24
5.38:10.052
5.303
5.40:10.03
5.13:10.072
Sa Sample count cluster. Number clusters 1984
Sample count cluster, Number clusters 608
10P
Sample Couit
Sample Count
10p
Subclase 1D (sortod)
Subclass 1D (serted)
Figure 6: In-dataset transfer, iNaturalist 2021. Number of samples per cluster in the case of 608 and 1984 total clusters, after applying the sample size rebalancing procedure described in subsection A.1.1
Observe that the sample sizes are reasonably balanced across almost all the subclasses.
Table 4: In-dataset transfer. ViT-B/16 validation error on the binary problem "is this object a living thing?" of ImageNet2lk. Pretrained on various hierarchy levels of ImageNet2lk, finetuned on the binary problem. Obscrve that the maximal improvement appears the Icaf labels, and as g() approaches 2, the percentage improvement approaches
Hierarchy level (()
Validation error
Baseline
2
7.90
(lcaf)
21843
6.56
5995
6.76
2281
6.70
4
519
6.97
6
160
7.31
38
7.55
Our ResNet50 results are not as extensive as those on ResNet34. We present the average accuracies and standard deviations in Table
19

---

Published in Transactions on Machine Learning Research (10/2024)
A.1.2 ImageNet21k
The ImageNet21k dataset we experiment on contains a total of 12,743,321 training samples and 102,400 validation samples, with 21843 leaf labels. small portion of samples have multiple labels.
Caution: due to the high demand on computational resources of training ViT models on ImageNet21k, all of our experiments that require ppre-)training or finetuning/ /innar probing on this dataset were performed with one random seed.
Hierarchy generation. To define fine-grained labels, we start by defining the leaf labels of the dataset to be Hierarchy level 0. For every image, we trace from the leaf synset to the root synset relying on the WordNet hierarchy, and set the k-th synset (or the root synset, whichever higher in level) as the level-k label of this image; this procedure also applies to the multi-label samples. This the way we generate the manual hierarchies shown in the main text.
Due to the lack of a predefined coarse-label problem, we manually define our target problem to be a binary one: given an image, if the synset "Living Thing" is present on the path tracing from the leaf label of the image to the root, assign label 1 to this image; otherwise, assign O. This problem almost evenly splits the training and validation sets of ImageNet21k: 5,448,549:7,29947777 for training, 43,745:58,655 6,5 for validation.
Network choice and pretraining pipeline. We experiment with the ViT-B/16 model Dosovitskiy et al. (2021). The pretraining pipeline of this model follows the one in Dosovitskiy et al. (2021) exactly: we train the model for 90 epochs using the Adam optimizer, with 81 0.9, 32 0.999, weight decay coefficient equal to 0.03 and batch size of 4096; we let the dropout rate be 0.1; the output dense layer's bias is initialized to - 10.00 to prevent huge loss value coming from the off- dfagoiaa classes near the beginning of training Cui et al. (2019b); for learning rate, we perform linear warmup for 10,000 steps until the learning rate reaches 10-3, then it is linearly decayed to 10 10-5, 5, The data augmentations are the common ones in ImageNet-type training Dosovitskiy et al. (2021): : He et al.] (2016): random cropping and horizontal flipping. Note that we use the sigmoid cross-entropy for training since the dataset has multi-label samples.
Each training instance (90 epochs) is run 64 TPU v4 chips, taking approximately 1.5 to 2 days.
Evaluation on the binary problem. After the 90-epoch pretraining on the manual hierarchies, we evaluate the model on the binary problem. We report the best accuracies on each hierarchy level in Table g To get a sense of how the relevant hyperparameters influence final accuracy of the model, we try out the following finetuning/line probing strategies on the backbone trained on the leuf labels and the target binary problem of the dataset, and report the results in Table 5 (similar to our experiments on iNaturalist, we include the backbone trained on the binary problem in these ablation studies to ensure that our comparisons against the baseline are fair):
1. 90-epochs finetuning in the same fashion as the pretraining stage, but with small grid search over
(batch size, base learning rate) =((4066, 0.001), (4096/4 = 1024, 0.001/4 = 0.00025), (4096/8 512, 0.001 1/ 88 0.000125)).
2. Linear probing with 20 epochs training length, using exactly the same training pipeline in pretrain- ing. We ran a small grid search over (batch size, base learning rate) = ((4096, 0.001), (4096/8 512,0.001/8 0.000125)).
3. 10-epochs finetuning, no linear warmup, 3 epochs of constant learning rate in the beginning fol- lowed by 7 epochs of linear decay, with small grid search over (batch size, base learning rate) = ((4096,0.00 0.001). (4096/8 = 512,0.001 0.001/8 /8 = 0.000125)).
Table 5 helps us decide the best accuracies to report. First, as expected the linear probing results are much worse than the finetuning ones. Second, the "retraining" accuracy of 92.102 is the best baseline we can report (the same thing happened in the iNaturalist case) (the naive one-pass training) on the binary problem, then the model's final validation accuracy is 91. 91.746%, which is lower than 92.102% by nontrivial margin. In contrast, the short 10-epoch finetuning strategy
we only train the model for 90 epochs
20

---

Published in Transactions on Machine Learning Research (10/2024)
Table In-dataset transfer, ImageNet21k. VIT-B/16 validation accuracy on the binary problem "Is the object a Living Thing" on ImageNet21k. Ablation study on the exact finetuning/ /lincar probing strategy.
Eval strategy
90-epoch finetune
Linear probe
10-epoch finetune
Lenf-pretrained
[Batch size, buse
(e096,
(1024.2.5e-4)
(512,1.250-4)
(4096, 1o-3)
(512. 1.25o.4)
(4096,1o-3)
Validation error
92.782
93,177
93.295
87.497
87.493
92.294
93.439
(Batch size, buse Ir)
(1024,2.5e) (4096,1e-3)
4e.44
(512,1.25e-4)
(4096, 1o:3) (512, 1.25c-4)
(4096,1o-3)
(512,1.25e-4
Baseline
Validation ervor
92.102
91.971
91.339
91.703
91.719
92.002
91.856
Table 6: In-dataset transfer, ImageNet1k, Res.Net50 finetuned average validation error and standard deviation on the vanilla 1000 classes, pretrained on label hicrarchies with different label granularity
ResNet50 Chea+s
g() Validation error
2000
4000
8000
per-class
23.4++0.13
23.48-+00.098
23.49-+0.204
VIT-L/14 CLIp+kMeans
g()src)
2000
4000
8000
per-class
Validation error 9()
23.41::.127
23.47::0.074
23.78:10.048
Random ID
2000
4000
8000
per-class
Validation crror
23.4+00068
23.4=0.070
23.65=+0.071
works best for the backbone trained on the leaf labels, therefore, we also use this strategy to evaluate the backbones trained on all the other manual hierarchies. peculiar observation we made was that, finetuning the ceaf-labels-pretrainee backbone for extended period of time on the binary problem caused it overfit severely: for batch size and base learning rate in the set {(4096, 0.001), (1024, 0.00025), (512, 0.000125)), throughout the 90 epochs of finetuning, although its training loss exhibits the normal behavior of staying mostly monotonically decreasing, its validation accuracy actually reached its peak during the linear warmup period!
A.1.3 ImageNetlk
Our ImageNet in-dataset transfer experiments are done in a very similar fashion to the iNaturalist ones. In particular, the pretraining and finetuning pipeline for ResNet50 is exactly the same as the one in the iNaturalist case, so we do not repeat it here.
Due to a lack of more fine-grained manual label on this dataset, we generate fine-grained labels by performing kMeans on the ViT-I,/14 CL.IP embedding of the dataset separately for each class; the exact procedure is also identical to the iNaturalist case. The CLIP backbones we use here are the ResNet50 version and the ViT-L/14 version. We report the average accuracies and their standard deviation in Table obtained from at least one random seed during pretraining and 3 random seeds during finetuning.
0 All results are
The best baseline we report is the one using retraining: if we adopt the pretrain-then-finetee finettne procedure but with Dist (i.e. the vanilla 1000-class labels) set as the pretraining dataset, then we obtain an average validation error of 23. 28% with standard deviation of 0.103, averaged over results 3 random seeds. Tn comparison, if we only perform the naive ono-pass 90-cpoch training, we obtain average valiation error 24.04%, with standard deviation 0.057.
that there is virtually difference between the baseline and the best errors obtained by the models trained on the custom hicrarchies: they are almost equally bad. Noting that the sample size of each class in ImageNetlk is only around 10s, and the fact that ImageNetlk classification is a "hard problem" it is a problem of high sample complexity - further decomposing the classes causes each ane-grained class have too few samples, Icading the above negative results. This reflects the intuition that higher label gramularity does not necessarily mean better model generalization, since the sample size per class might become too small.
From Table 6
21

---

Published in Transactions on Machine Learning Research (10/2024)
Table 7: Cross-dataset transfer. ViT-B/16 average finetuning validation accuracy on ImageNetlk along with standard deviation, pretrained on various hicrarchy levels of ImageNet21k, and a small grid search over the base learning rate.
Pretrained on / Base Ir
3 x 10-3
3 X 10-2
6 X 10-2
3 X 10-1
ImageNet21k, Hier. lv. 0
80.87#0.012
02.48
82.51=0.042
81.40#0.041
ImageNet21k, Hier. lv. 1
77.387
81.03+0.054
81.28+0.044
80.40+0.0887
ImageNet21k, Hier. lv. 2
74.91
79.76:10.021
80.26:0.05
79.7
ImageNet21k, Hier. lv.
63.65+0.052
76.43:00.033
77.32=0.088
77.53+0.078
ImageNet2lk, Hier. lv.
62.17:0.012
73.65=0.033
73.92=0.073
75.53+0.024
ImageNet21k, Hier. lv. 9
53.68+00034
69.33+00.045
71.08=0.068
72.75+0.071
Table 8:
Cross-dataset transfer. VIT-B/16 average linear-probing validation accuracy on ImageNet along with standard deviation, pretrained on various hierarchy levels of ImageNet21k.
Pretrained on
Hier. lv (leaf)
(())
Validation acc.
IM21k
21843
81.45=0.022
1
5995
78.33 0.018
2
2281
75.66=+0.005
4
519
68.95=000051
6
160
63.65 0.035
9
38
57.35++0.016
A.2 Cross-dataset transfer, ImageNee21k-1ImagNeett
In this subsection, we report the average validation accuracy and standard deviation of the cross-dataset transfer experiment from ImageNet21k to ImageNet1k, discussed in Figure 2 and Section in the main text.
Network choice. We use the same architecture ViT-B/16 1 as the one in the in-dataset ImageNet21k transfer experiment and follow the same training procodure, which we repeat here for the reader's convenience. The pretraining pipeline of this model follows the one Dosovitskiy et al. (2021): we train the model for 90 epochs using the Adam optimizer, with 31 = 0.9, 82 = 0.999, weight decay coefficient. equal to 0.03 and batch size of 4096; we let the dropout rate be 0.1; the output dense layer's bias is initialized to 10000 to prevent huge loss value coming from the off-diagonal classes near the beginning of training CCu al. (2019b); for learning rate, perform linear warmup for 10,000 steps until the learning rate reaches 10-3, then it is linearly decayed to 10-5, The data augmentations are the common ones in ImageNet-type training Dosovitskiy et al.] (2021) ; He et al. (2016): random cropping and horizontal flipping. Note that we use the sigmoid cross-entropy for training since the dataset has multi-label samples.
Additionally, cach training instance (90 epochs) is run on 64 TPU v4 chips, taking approximately 1.5 to days.
Finetuning. For finetuning ImageNetlk, procedure is very similar to the one in the original VIT paper Dosovitskiy et al. (2021), described in its Appendix 1.1.1. We optimize the network for 8 epochs using SGD with momentun factor set to 0.9, zero weight. decay, and batch size of 512. The dropout rate, unlike in pretraining, is set to Gradient clipping at 1.0 is applied. Unlike Dosovitskiy et al. (202)), we still finetune at the resolution of 224x224. For learning rate, we apply lincar warmup for 500 epochs until reaches the base learning rate, then cosine annealing applied; we perform a small grid search of base learning rate- (3 10-3 x 10-2 2 6 x 10-2,3 3 10-1). Every one of these grid search is repeated over
22

---

Published in Transactions on Machine Learning Research (10/2024)
random seeds. We report the ImageNetlk validation accuracies and their standard deviations in Table In the main text, we report the best accuracy for each hierarchy level.
Linear probing. For linear probing, we use the following procedure. We optimize the linear classifier for 40 epochs (similar to Lee et al. (022])) using SGD with Nesterov momentum factor set to 0.9, a small weight decay coefficient 10=b, and batch size 512. We start with base learning rate of 0.9, and multiply it by 0.97 per 0.5 epoch. In terms of data augmentation, we adopt the standard ones like before: horizontal flipping and random cropping of size 224x224. We repeat this linear probing procedure over random seeds given the pretrained backbone, and report the average validation accuracy and standard deviation in Table
Baseline. The baseline accuracy on ImageNetlk is directly taken from the VIT paper Dosovitskiy et al. (see Table in it), in which the ViT-B/16 16 model is trained for 300 epochs on ImageNetlk.
2021
23

---

Published in Transactions on Machine Learning Research (10/2024)
B Theory, Problem Setup
B.1 Data Properties
1. Coarse classification: a binary task, +1 vs. -1.
2. An input sample X E R consists of P patches, each with dimension d. In this work, always assume is sufficienlly large
M|
3. Assume there cxists h4 subclassos of the superclass "+", and k_ subclasses of the superclass Let hi+ k
4. Assume orthonormal dictionary V = (u,, fa C Rd, which forms an orthonormal basis of Rd. Define U+ E V to be the common feature class "+". For each subclass (+,c) (where c E [k+]], denote the subelass feature of it as V+,c E V. Similar for the "_" class.
For an easy sample X belonging to the (+, c) class (for C [k+]), we sample its patches as follows:
Definition: we define the function P R x V V [P] (so (X:v) + I [P]) to extract, from sample X, the indices of the patches on which the dictionary word a E D dominates.
(a) (Cammon-fcature patches) With probability p. patch Tp in X is common-feature patch, which zp ape+ + Sp for some (random) ap E (VI-Lvi+y)
(b) Seabuue patches) With probability P-IP(X;,,])
patch with index p e ([P) - P(X; is a subclass-featur patch, on which Up = ag + Sp. for random
Ap E [v1 - vv+
(c) (Noisc patches) For the remaining P IP(X; x4)1 e+)))l patches, Fp = Sp.
6. A hard sample Xhard for class (+,c) is exactly the same as an easy one except:
(a) Its common-feature patches are replaced by noise patches;
(b) (Feature noise patches) With probability p-Ip(Xxx+.)) a patch with index p E ([P) P(X:
at
is a feature-noise patch, on which V, = ab. v- Sp for some (random) op (owwers Uppeer) (c) Set one of the noise patches to n ~ NN0, 02 Ia)-
7. A sample X belongs to the "+" superclass if (P(X; > 0 or v..;; > 0 for any e (excluding feature-noise patches).
8. The above sample definitions also apply to the 4_" classes by switching the class signs.
9. A training batch of samples contains exactly N/2k samples for each (+, and (-,c) subclass. This also means that each training batch contains exactly N/2 samples belonging to the +1 superclass, and N/2 samples for the -1 superclass.
10. As discussed in the main text, for both coarso-grained (baseline) and fino-grained training, we only Irain on easy samples.
B.2 Learner Assumptions and Training Algorithm
Assume the learner is a two-layer convolutional ReLU network:
m
Fx
Σ p=1
a alWerrs xp) ber)
(14)
To simplify analysis and only focus on the learning of the feature extractor, we freeze ac,r = 1 throughout training. The nonlinear activation o(.) = max(0, -) is ReLU. Note that the convolution kernels have dimension d and stride d.
Consider each d-dimensional patch of input as embedding of the input image generated by, instance, an intermediate layer DNN.
24

---

Published in Transactions on Machine Learning Research (10/2024)
Remark. One difference between this architecture and CNN used in practice is that do not allow feature sharing across classes: for each class e, we are assigning disjoint group of neurons Warr to it. Separating neurons for each class is somewhat common trick to lower the complexity of analysis in DNN theory literature Allen- Zhu & Li (2023b); Karp et al. (2021); Cao et al. (2022), as it reduces complex coupling between neurons across classes which not the central locus of our study this paper.
Now we discuss the training algorithm.
Initialization.
Sample w N/ Ia), and set Uo - -ooh V log(d).
Training.
We adopt the standard cross-entropy training:
NN C(F)= = Σ Uw) = log
exp(F Un (X,)) Σ exp( Fx(X
(15)
n=1
==1
This induces the stochastic gradient descent update for each hidden neuron (c E [k],, [ml) per minibatch of N iid samples:
N
Σ w (1+1) = -w! + 11 NP
1
1( c}(1 - llogi (0)
(X
n
Σ
o' ((w
(0) a!(p)) + b2)
PE[P]
(16)
1yn # fc]/ clggit (1)
(x(1)) (x(()
Σ
o' d'((w (t)
c,p: x2(0p) ) + B 2010
PE[P]
where
exp(Fa(X)
(17)
Eg exp( Fy (X)
As for the bias,
((+1)
w woil l|
(1+1) 60r
((0
Wa.r
(18)
log (d)
Remark.
1. The initialization strategy is similar to the one in Allen-Zhu & Li 2022
Since the only difference between the training samples of coarse and fine grained pretraining is the label space, the form of SGD update is identical. The only difference is the number of output nodes of the network: for coarse training, the output nodes are just F- and F- (binary classification), while for fine-grained training, the output nodes Ft,1, F+.2. F+,4,, F-11, F- F-2...., F-,--, total of k4 + k_ nodes.
The bias is for thresholding out the neuron's 's noisy activations that grow slower than 1/ log (d) times the activations on the features which the neuron detects. This way, the bias does not really influence updates to the neuron's response to the (common and/or fine-grained) features which it activates strongly on, since 1 [o] s 1, while it removes useless low-magnitude noisy activations. This in fact creates a (generalization) gap ween the nonlinear model that we are studying and linear models. Due to our parameter choices (as discussed below), if the model has no nonlinearity (remove the ReLU activations), then even if the model can be written F4 (X) = Epe C4 (u,, pp) + (v.11 up) + ...+ ... C+. (M+ Zxp) and F-( = Epe(p| e- (v_ pp) + c_ 1 (0__1, 1, xp)) + ... + C- (w_,.,,a for any sequence of nonnegative real numbers c4,c_, (c+J 1 وو- /h_ (which is the ideal situation since the true features are not corrupted by anything), is impossible for the model reach o(1) error on the input samples, because the number of noise patches will accumulate to variance of (P-O(s")) oe > O(s"), which significantly overwhelms the signal from the true features. On the
25

---

Published in Transactions on Machine Learning Research (10/2024)
other hand, each noise patch is sufficiently small in magnitude with high probability (their strength is o(1 /llo""()))) so slightly negative bias, as described above, can threshold out these noise-based signals and prevent them from accumulating across the patches.
An important difference between our bias update rule and the one in Allen-Zhu & Li 2022 is that, our rule depends on the lz norm of the neuron's 's update, while the one in Allen-Zhu & Li (2022) is hard-coded and not dependent bias update rate is that, the neurons that are responsible for detecting the common features will grow more quickly in norm than those responsible for detecting the fine-grained features, therefore, to ensure fairness between the different groups of neurons (i.e. only using the bias to remove useless activations on the noise patches while creating minimal disturbance to the neurons' activation on feature-dominated patches), we rely on our neuron-dependent bias update rule.
the neuron weights. The reason that should not hard code the
B.3 Parameter Choices
The following are fixed choices of parameters for the sake of simplicity in our proofs.
Always assume is sufficiently large. All of our asymptotic results are presented with respect to d:
2. poly(d) denotes the asymptotic order "polynomial in d";
3. polylog(d) aymptolic order "polylogarithe in d";;
4. polylog(d) I k+ = k= S a and s* (dg S k+ (i.e. K+ lower bounded by polynomial of log(d) of sufficiently high degree);
5. Small positive constant E (0,0.1);
6. For crarse-grained (baseline) training, set c / 2co, and for fine-graine grained training, set с
v2+ 20p;
7. 0 5. polylog(d)
8. t Hlwwrr 2 log ld] and st st uupper S 0 log(d]
s² 1:
10. 8* E polylog(d) with a degree > 15;
11. 0g- = (dva
12. ac. E [w ( polylor(a) ) polylog(d)) ]:
13. Poς 2 (ppoyylog(d),, and P S poly(d);
14. σo 50 0 tog(a))))))) ) and set 7 O(oo) for simplicity;
15. Batch of samples (()) al every iteration has a deterministic size of N E (0(polylog(4)k..dl (d)).
16. Note: we sometimes abuse the notation x = a + b as an abbreviation for x E [a - b, +
Remark. We believe the range of parameter choice can be (asymptotically) wider than what is considered here, but for the purpose of illustrating the main messages of the paper, we do not consider a more general set of parameter choice necessary because having wider range of it can significantly complicate and obscure the already lengthy proofs without adding to the core messages.
26

---

Published in Transactions on Machine Learning Research (10/2024)
B.4 Plan of presentation and central ideas
We shall devole the majority of our effort to proving results for the coarse-label learning dynamics, starting with appendix section C and ending on D and only devote section G to the fin-grained-labbe learning dynamics, since the analysis of fine-grained training overlaps significantly with the coarse-grained onc.
One technical difficully making the above ideas rigorous lies the ReLU activation (with time-dependent. bias): due randomness in the gradient updates and the initialization, it is possible for individual hidden neurons that activate on v-dominated patches one time iterate no longer do so the next iterate, and the opposite can happen. This can be problematic: for instance, it is possible that certain "lucky" neurons for 84 at one iterate become dead on b4-dominated patches at the next iterate, while some "unlucky" neurons that were dead on domminnnd patches before start activating on these patches at the current iterate. In our proof, we show that this kind of situation does not happen too frequently nor do they contribute too much to the overall behavior of the neural network, by carefully keeping track of each hidden neuron's 's response feature vectors and noise vectors throughout training.
27

---

Published in Transactions on Machine Learning Research (10/2024)
C
Coarse Coarse-grained training, Initialization Geometry
For coarse-grained training, assume m (r22+2r))
Definition C.1. Define the following sets of interest of the hidden neurons:
4 (0 E V frr b) 2 oov4 200 log(d) (dg
(0)
Given v E V, st (v) S + x [m] satisfies:
(a) (wi v) 2 00o4 / + 200 log(d) + ldg
(b) Ye' s.t. o' v, (w) 0') 0004 + 200 log(d) log"(d (d)
(0)
3. Given v D, 1 C + x [m] satisfies:
(a) (w u) 2 80v / 200 log(d) ld)
4. For any (+,r)= St.rgg C + im]:
(a) (w t.r: v) S /lg((d) Vo e v
(0)
(b) 4 < 0(1)
Proposition 1. Assume m (c2+2000) iee. the number of neurons assigned to the + and - class are equal and sel to (dR2+co))
ttt= = 0, for all E V, the following properties are true with probubility least d over the rondomness of the initialized kernels:
( deo
1. 1 (0)),1+{ (v) - (ToRiia)
|s (w)] (v')
1/.
|s (v) 1s (v')
In particular, for any v. v' EV,
Toge(a))
s(0) [m]
Proof. Recall the tail bound of g 1) for every e >> 0:
1
212 < P
1 2/2
(19)
2 2m 2 +1
2 v
2m
First note that for any r E [m], ") vilvvv is a sequence of iid random variables with distribution \i(0, og).
The proof of the first point proceeds in two steps.
28

---

Published in Transactions on Machine Learning Research (10/2024)
1. The following properties hold at t 0:
P1
(wr tir: 1) 2 00v4 + / log(d) log 6 (d)
(0)
1
d - ( (d)
E
V 8
(4 200) (log(d) + log"(d))
(20)
(4 + 200)
(log(d) + lag"(a)) +
V (1+ 2co)
(log(d) + log"(d)
-
d d2000
Iog(d))
and
P2 P P
(w (0)
t,r: v) 2 00 =00V++200 /
log(d)
1
log 9 (d)
d --00 (-22---22-0) (-2-c0)/lox(14
v /T
(4 + 200)
(log(d)- - Tog"
(21)
x
(4 + 2co)
(log(d) Toge((r))
/ (4+))))
200)
(log(d) Top"(a))
=0
d -2-00
Vlog(d)
Therefore, for any E [m], the random event described in S holds with probability
d-1
P1 (1 - p2) p2) =
2-c0 2
1-0
2 (Viezta) d
Iog(d)
(22)
1
d 2-000
Mog(d))
The last equality holds because defining f(d) = d 2-co and d being sufficiently large,
((d) = ((d log(1 f(d)) s (d 16-1] x (S(d) (()()))) O(d-1)
(23)
which means
(1 (1- (- =e oo (1 (1-
(24)
2. Given v E V, (x)) is a binomial random variable, with each Bernoulli trial (ranging over
(v)
E [m]) having success probability pi(1 p2) Therefore, E [ss:((o)] mmpp1 p2) =
d
log(d)
Now recall the Chernoff bound of binomial random variables. Let (X,, )m be an iid sequence of Bernoulli random variable with success rate p, and S, = Em X,, Then for any 5 E (0,
82mp
P(S, 2 (1 8)mp) & exp
3
(25)
82mp
P(S, $ (1 8)mp) S exp
2
29

---

Published in Transactions on Machine Learning Research (10/2024)
follows that, for each E V, (x) o (Togla)
( do with probability at least
(oo(-Q(lo-""(()""9) Taking union bound over all possible E D, the random event still holds with probability at least. 1 exp(-xp(eee ((loo-//(dd)d O(log(d))) exp( exp(-S((0.5ev)) (in sufficiently high dimension).
The proof for 5 (v) proceeds in virtually the same way, so we omit the calculations here,
s (w)
To show the second point, in particular bounds of the relevant sets. In particular, we need to directly use the CDF of gaussian random variables:
< 0 log we need to be bit more careful in our
P
W r, v) 2 20ov4+ 200 log(d) (d)
(1 O(d
(w (0) P
.r. v²) 2 20o 1004+00 log(d) log"(d))
1
1
1+200 logld)+ Tc c 12 +0
2T
V14200 log(d) (4)
d3+00 Mog(d)
(26)
1
d d- 22-c0212t00) 1og (d) / 200
(log(()) +
V (lg(()) log"(d)
(
2T
log"
+0
dotc log(d)
2 co (2+e0)/ log (d) /4 200
log" (4)
2T
/log(d) (d] + /og(d)) log"(d)
d3tco log(d)
The expected difference in number between the two sets is just the above expression multiplied by (dd++20), and with probability at least 1 exp(-S((d-coA)) the difference term satisfies
1
(1 + d' co/2 (d ee(2to)) log' /4 2co
log
(d)
2x2x
/ /lg(dd) + log"(d) V log(d) lag
222
+
(27)
dittss Iog(d)
1
doa
Vlog(a)
log
(d)
u (v)) 1s (e'))
By further noting from before that |s (v) = (ioglt
do
follows. The
Tog
proof of (s) (wil
5 Inge follows very similar argument, so we omit the calculations here.
(010)
Now, for the set S:O know for any E [m] and v; E D,
P (1o vz) ao TO Tog(d) so sof
(
1 Vlog(d)
d
(28)
Taking the union bound over and i yields
(0) PP 3r and (.t. t.r v.) 2 VooiiO/logoo
< md0
(Vog(aa
1
d
a 2
(29)
30

---

Published in Transactions on Machine Learning Research (10/2024)
Finally, to show [ - ((1) holds for every (+,r), we just need to note that for any arbitrary (+.r)
neuron, the probability of [ > no greater than
P2
4
0
log d
d 8 do0 d² 5o log d -ec Aco
(30)
Taking union bound over all m S 0 (d2+20o) neurons yiclds the desired result.
31

---

Published in Transactions on Machine Learning Research (10/2024)
D
Coarse- Coarse-grained SGD Phase I: (Almost) Constant Loss, Neurons Diversify
Definition D.1. We define To to be the first time which there exists some sample such that
F To)
(To))
2 d'
(31)
Without loss of generality assume c= Define phase to be the time t E To).
D.1 Main results
Theorem D.1 (Phase 1 SGD update properties). The following properties hold with probabilily al least
PK+t) (O (R)))))))())))) for every E (0, poly(d)
1. (On-diagonal common-feature neuron growth) For every (t,r), (+,r") E S7 (u+),
(8) (0) (1) (0)
w +.r
w
4.,"
(32)
Moreover,
Aw (t) -1 ((= 111) VI= (1+ (
log logg"(()) ))
8* 2p + Ac#
+ 0
(33)
where ACto) NO, o ())
ACI. I), σ 2.. =noo (1t ()) v1 v
Vsa PV2N'
and 1& sd!
Furthermore, every (+,r) E (x=) activates on v. uu-dominated patches at time t.
2. (On-diagonal finegrained-feauure neuron growth) For every possible choice of c and every (+,)) St (v+.c);
(1)) (1) (0) (1) t.y' 4.
(1) (0)
(34)
Moreover,
Awiy (1) -o ((++m) V1 t (1=(11111100) + log (1og(((a)) )
s*
2k P ute AC
(35)
where (1 NO a (1)2 Act,r I) and 000 Act.r noae (G v/) vI= st 1/3
P P
Furthermore, every (+,r) st (w+c) activates 4+ dominaate patches at time t.
The above results also hold with the "4" and 4 signs flipedd.
Proof. The SGD update rule produces the following update:
(++1)
=w 4.
(1) + 77 NP
1
(36)
1(yn = +](1 logit (4) (x(1))
Σ
d'(ww tyr .n())))) + (1) 1 ya!!)
(37)
n=1
PE[P]
1/8
logg- (x, Σ o d(l foy
x n.p! + t.r ((())
(38)
PE(P]
32

---

Published in Transactions on Machine Learning Research (10/2024)
In particular,
N
1 (un = +3 (2 1/ x
equation
37
1((((x(() 2044 > 0f
Σ
d'(w t.r (0
a
aa + (( + b4%) (all) 2+ + +/hpp)
PEP( ! w+))
d'((w (1) 20 b_. )ar
PEP m4)
+ 111( 04) = E
d'((w (6) 1nn) + ( )
ME(P)
(39)
N
1/ = = ( wi x
Σ
n=1
1 ((P(( 0}
Σ
1/
(1)
+ (1.p)) 2 b
( + +
D :m,)
Σ
1 fffwoff (12p)) b4rr
1
(t)
In.
(EPIX 184
:04)
+ 11p((X 0 =0 Σ
1
20 (1)
2 64.2
m.p
anp
PETPI
The rest of the proof proccods by induction (in Phase 1).
First, recall that we set b / 20o v log(d), and Ab 19
lAw! lla ldg'(d)
for all in phase 1, and for any
+-class sample X, with p E P( P (1) v)); al vI+ by our data assumption. Base case t = 0.
1. (On-diagonal Common-feature neuron growth) The base case for the neuron expression point 1. is trivially true.
We show that the neurons (+.r) (+)) only activate on u_-dominated patches at time t = 0.
With probability at least 1 - O ). by Lemma H.3 we have for all possible choices of r,
mNP poly(a]
(wr t/ (10))
O(ano v vd dlog(d)) so
σ
(40)
[og"(a) (d)
It follows that
(w (w: a 0+ + c((0))
(0) (0)
vi (V4+200 20o log(d)) + 1/log"(d), (d), VI0 V10 +
=00
Tog (d)
(41)
[V11 200 2 + 1/log" (d), v1 LV 10 log(d))
=00
log"(d)
33

---

Published in Transactions on Machine Learning Research (10/2024)
Employing the basic identity - b d'=b² have the lower bound
a+b
(0) 0 ( t,r n. v- + (m.p) + 64.
2 (1 - () + (log + 1/ log (d)) v(4 + 20p) log(d)
- 0
log"
(1 - 2co - 1/ log" (d)) (4 + 20o) log(d)
1
v( () 2c 20) (log(d) - 1/log" logo (d)) v(4 200) log(d)
log
(42)
(4 2c0 + (1 - /) log²(() (d)
((1 + (co) -
log (d)) + /44 + 2co log(d)
log"
0
The last inequality holds since i polying(d] and d is sufficiently large such that (dg does not drive the positive term down past 0.
Therefore, the neurons in (*))
(v+) indeed activate on the u--dominated patches at = 0.
(0) The rest of the patches æn.p is either a feature patch (not dominated by u. or noise patch. By definition, (+,r)= E (++) = (+,r) E (v_). Therefore, by Theorem F.1 with probability at least 1 - O NP) ), at time t = 0, the (+,r) E (+*)(++) neurons we are considering cannot activate on any feature patch dominated by v I u+, nor on any noise patches.
(v+)
It follows that the expression equation 37 at time 0 is follows:
Σ 1 (un = +} ( rh1
equalion 37
X1 (0; 0+ ;0 01
(VI+ 10+ +(110) +
0
(( (x
(x 10) (.))
+
+1(PP(X (0) ; = 0} Σ
PE[P]
N
(43)
- 4/
Σ
1 = IP(X (0) ; >
Σ
(VI + +5.00)
=
2
n=1
pEP(X (0) m))
1
4/ x
(m. [N] x ||] yn = = x+
; x ( (VT+ ix+)
( +} (1- #/ 1/2 C.)))
n=
PEP(X (.+)
On average,
K (n.p) E [N] x [P] : vo = (PX(0 O :04) (44)
E
N
s 2
Furthermore, with our parameter choices, and by concentration of binomial random variables, with probability at least 1 - ((polyyoog))))
K(m.p) E x = 1(X () v x > 0,p (0x
s*N
(1+ 1113)
(45)
2
34

---

Published in Transactions on Machine Learning Research (10/2024)
must be true. It follows that
x N
equation 37
2 - w1
1 1 1==---1/7 x (v1 = (w++)
2
(46)
fun = +} (2- +//
1/1 $.
n=l
PEP (0) (-)
The other component expression equation 38 is zero with probability at least 1 0
mk, NP) pollld] by Theorem
By noting that
Var (Ac = Var
Σ
tu = +} ( + +//
Sh
NP
n=
pEP(X 2 ;
(47)
1
=
+ v1
1 + 8 oz.
2
2N
and
N
A = E
Σ
Σ
{yn = +} ( w/
=
ch.p 0,
(48)
NP n=1
pEP(X.";... (44)
we finish the proof of the base case for point 1.
2. (On-diagonal finegrained-fentee fenture neuron growth)
The proof of the base case of point 2. is virtually identical to point 1, we omit the computations here.
Inductive step: We condition the high probability events of the induction hypothesis for t [0,2) (with
T < To of coursc), and prove the statements for t = T 1.
1. (On-diagonal common-fealure neuron growth)
By the induction hypothesis, up to time T, with probability at least 1-0 O [ poly(d) ) for all (+,r) e
(T (u+),
Aw!h (t) -11 ( wh v1 v + + 1-13
2P 4+ + AC(0)
s²
(49)
where Acl0 o
(2) D), o a nos (e + vin) v1 +
V= PV2N
Expression of w (T+1)
Conditioning the high-probability event of the induction hypothesis, at time t = T 1,
T
w
(T+1)
w
+,
+
(w
+.r
7m0
(50)
-/p
( ونا
vI (1=5-1133
2p u+ + 500
s*
where (0) ~ NOO, of
(02 1), o (022),
notT (t (1) V1
- PV2N
Let compute (ff24 (T+1)
35

---

Published in Transactions on Machine Learning Research (10/2024)
We first want lo show that w+r activates vy-dominated patches zn. need to show that the following expression is above 0:
(T+1)
(T+1)
v1 + 10+
Sn.p
(T++))
We
(T+1) to n.
(T+1) (T+1))
+ D4r"
= -Ww VI= 124 + ( bbf
(0)
+
n/
{ + v1 V (1 + 81=181113) +0
log 10
(d)
2p
2P v
8*
+ (2+1)
+ + ((T+1) Sn.p
(51)
Ab (r)
Let us treat the three terms (on three lines) separately.
First, following virtually the same argument as in the base case, the following lower bound holds with
probability al least. - 0
mNP for all n, and (+,r) E (v+):
poly(d]
(w) (0) vI + 10+ + C. (T+1)) +b4
200 (V(- () (1-1)(4+
(log(() + +1/ log (d)) - v 2co) log(d) - 0
}
(52)
loo (d)
>
Now consider the second term.
We know, with probability at least - e -(((d)) for all and p.
(c( u4) ( 00
(
1 (d))
(53)
therefore,
(2 w1 (vr((t
(nT/
v1 + (1 01 1-11/3) +0
log (d) )
s*
((T+1))
2P
u
Sn.p
(54)
STfT s* 2P
1
0
log 10 (c)
Moreover, with probability at least -Q(d)
TVV Vs-
(T+1) (c+,r ,
x
(55)
PV2N
Iog
and with probability at least 1 - -A(d)
((+DD)) ( Shp
x 0o (0(0 (T) 0 =0 nVT
V
2)
nVT
V
(56)
Pv2N log 20 (d)d
PV2N log (d)
therefore
(T+1) v1 m4
c( S nVT
Vs* PV2N
o
(1ogg(()))
1
(57)
36

---

Published in Transactions on Machine Learning Research (10/2024)
It follows that with probability at least 1 - (())))
1 + wi VI= (1
5r
1/
(2
2P u+
Str
VI + 124 + c(T+1)
(nT
(()
( ((
VI (1 -
2P U4 v1 (1+)
8r
(n1
1h (2+ +
v 1 1 1/3)
5²
11T+1))
(58)
Sn.p
2P
+ (n 11++) vI + 4a + Snp c(Tpt>>
2 [ - -w- (1T+) - 1) (1 (1-8--1/3)
8*
nVT V8*
0
2P
PV2N
log
(d)
Now we compute the third term. By the induction hypothesis,
Abll)
|Aw! l1z
ldg
( +1) vT= (1=
17
2p 2p + A
(59)
logo(a)
(1
2 +
V1+ (1 (1+1(+ -1+3
8
|1+1l2
+
T
Acc0
log (d)
2P
(d)
1=
t 1h vi+ ( + x-133
8*
Act.rl1
log (d)
2P
log
log'(d) (d)
1=
With probability at least 1-0
polyya]) ) for all E [o, T] and r in consideration,
Vs*
Ac S ''P//N'' o
"dg
(60)
Therefore,
T
Ab
(t)
+.r
t=0
(61)
1 log
1/T
11
+ +// )
vi+i
i
( (1+8--1/3)
8²
TT V8*"
log (d)
(d)
2P
P/2N"
37

---

Published in Transactions on Machine Learning Research (10/2024)
Combining calculations of the three terms from above, find the following estimate:
( +ir
(T+1)
xn.pp + b,r
(T+1))
> 0
1
(1 (1 (1-3)- 8¹
Vs*
+ 1/
V1
nTT
ldg
2
2P
PV2N
1
+ + + + 118 *+11///
8*
+
T/T
Vs*"
log (d) (10g((())
(62)
log (d)
2P
PV2N
>yy (3
1/ (1 - 1) s-- -
1
5*
log (d)
2P
On the other hand, by Theorem F.1 with probability at least 1 1-0 mk__N none of the (+, E (v+) can activate on Dn.p
poly(d)
(T+1) that are feature-patcher dominated by v 1 V4 or noise patches.
Combining the above observations, with probability least 1- 0 (kk poly(d) to time ( = + 1 can be written follows:
NP(T++)), the update expressions up
Amf4. (- +//
(n. [N]
3h 0, ((X (VI=
(63)
N Σ
(2
+ U2
(A) Sn.p
m=1
REP(X! mL)
The rest of the derivations proceeds virtually the same as in the base case; we just need to rely on the concentration of binomial random variables to calculate
(m. E [N] [P]: ya +, PPX v+)] 0, P(X
s (1 (1+ 81=8)1133)
(64)
2
which completes the proof of the expression of (w! Additionally, to show
+,-
w
(T-1) w 4.0"
4,p"
(65)
just need to note that, by the above sequence of derivations, for every (+,r) (v+), these neurons receive exactly the same update at time t = +1
(v. +)]1= ; ( logit (T+1) (T+)))
Σ
(T+1) u. + Snip c(77t)). (66)
Cn.
PEP(X!T+!) [4)
2. (On-diagonal finegrained-featee fenture neuron growth)
For point? 2, the proof strategy is almost identical, the only difference is that at every iteration, the expected mumber of patches in which subclass features appear in is
K (n.p) p) E [N] x ([P) - P(X : yn +, (T) > 0.p e ((X vt
(67)
N 11=
2k_
which holds with probability least - ((l for the relevant. neurons.
38

---

Published in Transactions on Machine Learning Research (10/2024)
Corollary D.1.1. To <0
(((71) -1
poly(d).
Proof. Follows from Theorem D.1
D.2 Lemmas
Lemma D.2. During the time E [0, To), for any x
1 1 logil (2)
1 (x)
+ O(d
(68)
2
The some holds for - logit! (x Therefore, Wil & O(d-l) for E [0, To).
Proof. By definition of To: for any t E [0, Tol, we have F!!) (x.()) < d=' +0 for all n, therefore, using
Taylor approximation,
- logit (t) (x)
exp(F_ (x('))
exp(d-1)
+
1
(69)
exp(F x exp(F! (x!"))
1+1
The lower bound can be proven due to convexity of the exponential:
expl (1()) (xp(F(1)
1
1
1
exp(-d-
>
(70)
exp(F (x + exp( pLt) (X!
2
2
2d
39

---

Published in Transactions on Machine Learning Research (10/2024)
E
Coarse- Coarse-grained SGD Phase II: Loss Convergence, Large Neuron Movement
Recall that the desired probability events in Phase I happens with probability at least 1 - o(1).
In phase II, common-feature neurons start gaining large movement and drive the training loss down to o(1) We show that the desired probability events occur with probability at least 1 o(1).
We study the case of Ti S poly(d), where T1 denotes the time step at the end of training.
E.1 Main results
Theorem E.1. With probability least 1 O
(
mm NPT) poly(d) ) the following events take place:
1. There exists time T E poly(d) such that for any t [T" poly(d)), for any [N], the training loss L(F; x ya) E o(1).
2. (Easy sample lest accuracy is nearly perfect) Given an easy lest sample (X (aasy v), sor E {+1,-11 {y}, for t E " poly(d),,
(X S F (X (aaa)) s o(1).
(71)
3. (Hard sample test accuracy is bad) However, for all E [0, poly(d)), given a hard test sample (X (Kordd y),
P p(t) (X hand)
pll) y' hand) 2 2(1).
(72)
Proof. The training loss property follows from Lemma time beyond it (and upper bounded by poly(d)).
E33 and Lemma E.4
We set T Ti, any
The test accuracy properties follow from Lemma E.8 and Lemma E.9
E.2 Lemmas
Lemma E.2 (Phase II, Update Exprcssions). For any Ti E poly(d), with probability at least 1 O
(mNPPk)) poig(d)
during E [To, Ti), for any (+,r) E 5: (v+),
Aw
(!)
+.r
N
=1)
Σ
1 (yn = +] exp
exp { (x
(73)
n=1
exp(F (1) (x((1))
1 (x!!)) F (x!!) (1=
s*
(Vi+ + cc(0))
NP
cxp
(where c denotes the subclass index of sample x!!)) and for any (+.r) E s (v+.c;
Aw (1) +r
log (1=0(1121)) 8* (AM)) ( A (o-o)) (74)
- -1 8 1113/ 1 1+0
=xxepp
16yn (+,
(xp( (x(()))
(1 + 1133 5¹
(VI= <11))
exp pp()) (x(()) - (x
NP
+
40

---

Published in Transactions on Machine Learning Research (10/2024)
In Jaci, for any {v+) } U (0+.e) every newron in (t) remain aclivaled (on vo v-dominated palches) and receive exactly the same updates at every iteration as shown above.
For simpler exposition, for any (+,r") E (+) (w+,r); for neurons (+,r*) 5100 (v+.o)
(1) (v+), we write AT (10 (w0 v4); similarly for At,er
Moreover, "+ cllass samples, the neural network response satisfies the estimate for every (+,r*) E s4 (o+):
log (og ) ))) 5 (A:9) (w)) +
(75)
(110
(1) A.ch.r (5
The same claims hold for the =_ " class neurons (with the class signs flipped).
Proof. In this proof we focus on the neurons in S (w+); the proof for the update expressions for those in (r(0) (1+,c) are proven virtually the same way.
Base case, To-
First define A = (w-rr,,4), (+,r*) E St (04); similarly for Attor (w+rr* v+.c). Note that the choice of r* does not really matter, since we know from phase that every neuron in S evolve (Ta)
exactly the same rate, so by the end of phase I, [ -w wofol122 & (+,r), (+, st (w+). Let (+,r) (
(To)
m 1| for any
(v_). Similar to phase I, consider the update equation =w
w (t+1)
(1) +.r 17 NNP"
1
(76)
1lyn = +}|1 - logit (t)) Σ
d'(w (t)
(. x (1) + (10 (a
(77)
n=1
PE(P)
1/yn -lgggt (xx
Σ
o' +.r
(() n.p! +
+6 (00 (0
(78)
PE(P]
For the on-diagonal update expression, have
1un +}|1 logit (1) (
Σ
d'((w(()))) o'((ff),, 2000) + 6000 )of0
n=1
PELP
N Σ
1fy = +1111 logit (t) (x(())
==1
1(IP(X(0: :+)) > 00
Σ
(w trr, a 2 + +102)) 2 61%/} (al)) 4 + +c1
(79)
PXP (9:))
Σ
1 1f
(1) > ((4
(t)
pEP(X!"):oL) (04)
11Ip 2 - Σ 1
(10 (0
(1)
(0))
2
(2)
(
PE(P
41

---

Published in Transactions on Machine Learning Research (10/2024)
Following from Theorem D.1 and F.1 the neurons' non-activation on the patches that do not contain #+, and activation on the u4-dominated patches hold with probability at least 1 - 0 the above update expression reduces
[NNNP
poly(d) at time To- Therefore,
N
Σ
1 (yn = +. P( : > 0H1 logit (x
(X)
Σ
(a + S..
(80)
PEP(X." (04)
Note that for samples
X (0) with yn +,
exp(F (x(())
- logit (t) (x(())
(81)
exp(F (t) + exp(Ft (F()) (x!
Now we need estimate the network response F (x!"). With probability least exp(-S((x*133)) we have the upper bound (let (+, (t,) denote the subclass which sample x belongs to):
14 (
Σ
Σ
(w t.r, 4t + (L b4r
PEP(X(M)
(t
Σ
Σ
(w (1)
twrs D4.ct + +(1lp) + 100)
(82)
+
p
.d (tr))s (vt.c)
(1+0 log" Log"(d)) ((=
18"
(A:f0) 5 (v (()
A000)
- (o+ctt))))
The second inequality is true since max, (w (w u-) s A + 00oo log(d)) and for any (+,r) 5 (u+),
(w0)) ( - ((1/log" (d)) The bias value is negative (and so less than 0).
To further refine the bound, recall (0 / 15 (: (v) Therefore, we obtain the bound
15 = 1 0(1/log (d)).
1 (10 (1)E)(a))
1
(ogg(()) (1a(11))))
S(1 11 15=+s=-11p 1-11////+ 1s* [10
(og"(d)
(83)
(A s --
(v+)
A A
S7
(ct.tt))
Following a similar argument, we also have the lower bound
(
Σ
Σ
o (foff) U+ + (11))) + ((00))
(0 (+ (ttr)ss 10 (b+)
Σ
Σ
(fotf 0+ + c((t) 64f)
(84)
PEP(X
(+.r)ss (xt.et)
2(1 3'11/3)
(1-0 (og"(d))
(1-0(1921a))
(1-1
log (1)0(())))))
(AN 5 (v+) + ((1)
1 +.
(w+re)))
42

---

Published in Transactions on Machine Learning Research (10/2024)
The neurons in 5- have to activate, therefore they serve key role in the lower bound, the bias bound for them is simply -A (l)/) the neurons in $ (v+.o) contribute at least 0 due to the ReLU activation; the rest of the neurons do not activate. The same reasoning holds for the 5 (v+.c).
Knowing that neurons in 54 (v+) cannot activate on the patches in samples belonging to the -_" class, now we may write the update expression for every (+,r) (5 (e+) as (their updates are identical, same in phase I):
Aw (t)
n
1yn +}[1 logi (x
Σ o'
d'(ww (1)
r. (1)) + +00 (o
NP
pE[PI
n
1ly = + ;4)] > 03 exp( ( (x(())
NP
exp( (x.
E
a 2+ (:b
(1 (X (1)) expl 14 (x (x(())) + pEP(X.
exp
(85)
(1 1 1-133) 1/$ (1+0(102()))
1 log"(a) (108((1)))
1 1( = =)xxp
5 (A
(1+))
+ A (1 t 1- (w:t)))))
exp(F((((x!!))))
(1 a1 11/3) 8*
(VT= w1++w++ 11+ + c(t)
x
exp ( (x(1))
1 -22 (x +1
NP
This concludes the proof of the base case.
Induction step. Assume the statements hold for time period [To, 4], prove for time & + 1.
At step / ++ 1, based on the induction hypothesis, we know that with probability at least 1-0 0 during time T E [To t), for any (+,r) E (T (v+),
/mNPk_t poly(d)
Aw (T)
(1 s"-133 11+111/111 (1+0 (1o((())))
Σ 18yn +]eepp
(4
(v+))
(T)
( (0+.tt))
(86)
t,ch.r-
(1 (1 1-13/
8"
(VI= c177))
exp (مم (x( - expl | (x +1
NP
43

---

Published in Transactions on Machine Learning Research (10/2024)
and for the bias,
Ab(7)
4rr
1y +] +)expp {
(1 + --11//// 1/11//111111 +s0 (1+0)
log (d) (1)011=)0))
1
< log (d) n=1
(A
S+ (0)
(w+)
(T)
|5t (c+cc)))
(87)
tichir
exp(F(T) (X
(1 - 8- 1/3)
8"
NP
(F log (d) exp ( exp(F1 ) (x!(
+
Conditioning the high-probability events of the induction hypothesis,
(t+1)
(Ta)
N
(1 + ---1/3 / V is* (1+0 (ogg(a)) (1)))(a))
1
7
Σ
fyln = +) exp +xxexp
T=To n=1
(88)
5 (4
(w+) + A7 A
exp( (x (1)
(1 =1
8"
(VT+ + +c(77)
(
exp exp( (x(()) +1
NP
exp
It follows that, with probability at least 1 0
mNP poly(a)
for all u.-dominated patch (t+1)
44

---

Published in Transactions on Machine Learning Research (10/2024)
( - m.
) + 11(+11)
(w (T)
vI - 184 + ( + (TT)
N
1y = + exp {
(1 -11+6-113//11 1 10" (1+0(19((a)) 1
(ogg(a)) )
T=16 n=
(A
( (h+) + 17 t. |5 (0102))
exp(F!7) (x
(1 11+5-11/0
FL (x(()) (T) F (x! +1
NP
exp
(VI1 10+ + (1(7) vI = 10+ +
c1 Ab4
(89)
0
+1
Σ
Σ
1y = +xxexp {
111+-11)))) -11+5-1/3/11tt (1 log'(d)
(1
1
T=To n=1
(Ar(T)
(0110 (1+) + 1- - | (0100))))))))
exp(F!T) (x((
1/3) 5*
(1 + 5-
F1(7] ( F (x. +
NP
exp
1 1 - 0 ( (ogg(())
x
>
0
Therefore the neurons (+.r)= E (5t(0)( (14) activate on the u4-dominated patches xn. (c+1), We also know that they cannot activate on patches that are not dominated by 4+ by Theorem F.] Following a similar derivation to the base case, arrive at the result that, conditioning the events of the induction hypothesis, with probability at least - 0 poly(a) ), for all (+,r) E (
Aw!t! (t+1)
N
1gyn = +)exp { - --1+5- 11+1s" is" (1+0 log" ((0)(a))
(5 (A((ttt)
+,((t+1) | (0+ t-ch,r--
(90)
exp(p(t+1)) (x((
(1 + 5* 11/3) 5¹
(VI+ + c((+1))
NP exp p(ttt)) (x(++)) - p((+l) x!! x +1
45

---

Published in Transactions on Machine Learning Research (10/2024)
Consequently, with probability at least --0 0
m.p poly[a]
1
Σ 11 1yn +]mexp { (1 80 8- 1/3 11/////11 + (1+0)
(1+(11r2((0)
1
log (d)
log
(A 1
5 (w+)
A (-(1))))
8 (000 (00t..t))
(91)
exp(F((+1) )
8x 1/3)
5²33 s*
(1(ttt) (x((1))
1((+t) ( x((+))) +
NP
exp
1---- log" (d) (1gg(())
Utilizing the definition of conditional probability, conclude that the expressions for Aw (r) and Ab are
indeed as described in the theorem during time T E [Lo, t + with probability at least (1-O O
MN poly(d) ))
(1 (1-0
mN Pk+
)) 2 O m. (N+(k) poly(d)
poly(d)
Morcover, based on the expression of Aw (T) and Ab following virtually the same argument as in the base case, estimate the network output for any (x (t+1), y/ +):
F+ p((+1) (x++)((((++)) (x((+))) =(1 + 1 - 113
110 ( 1
log (1o5((a))
(92)
x (A7 |5+10) (++) + (t))
| (v++))))
Lemma E.3. Define time Ti,1 to be the first point in time which the following identity holds on all x(!))
belonging to the "+" " class:
(X (x!!))
2 21-0 O
(93)
exp(F() (x!1) - -F +
(dg
Then Ti,1 S poly(d), and for all t [Ti,,; Ti], the above holds. The following also holds for this time period:
)
[1 - logit( (x!")) 2
(10g((a)
(94)
The same results also hold with the class signs flipped.
Proof. We first note that, the training loss [1 logit (1)
( on samples belonging to the *4" class any
time during E [To, Ti] is, asymptotically speaking, monotonically decreasing from 1 O This can be casily proven by obscrving the way (A*(9) |x:(0) (w+) A A (st(0) (o+.e)) monotonically increases
from the proof of Lemma E.2 before p() (x!")) log (d) all x(()
(() belonging to the "4" class, there
46

---

Published in Transactions on Machine Learning Research (10/2024)
must be some samples X which
exp(F!") (xx
1 logit (x
exp F xx + exp (f (x!
- O log log(d)ss*
(95)
( log(d)s* dc)) + log
20
(dg
Therefore, by the update expressions in the proof of Lemma E.2 F(0) (x." ( can reach log (d) in time at most O ( (oloo((d) E poly(d) (in the worst case scenario). At time Ti, and beyond,
178"
(x) exp( ( ( (x F (x
exp(1 (0and
3
+1
exp(1 Oooddou s*)) log" +1
(96)
00 log)(d))
Lemma E.4. Denote C = 12 s' p. and write (for any c E [k+])
Ac(t) 5² (Ar()) s (t (v+) + A |s (o...))
(97)
(see Lemma E.2 for definition of A. Define te.0 exp(A. We write A(t) and to below for cleaner notations.
Then with probubility at least - o(1), during Til,
A(t) log(C(( Ti,1) + to) + Ett)
(98)
where [F(tt] < O
[ag Er=c-% T to S 0
(og(()) (og(t)-loge) -ooloogiC-- 'to)
log'(d)
The same results also hold with the class signs flipped.
Proof. Sidenote: To make the writing a bit cleaner, we assume in the proof below that C-14 is an integer. The general case easy to extend to by observing that - --..+0--10
(I-Ti,+ to Kt- : which can be absorbed into the enror term at every iteration since - Taj due to C- 2 M(55 (ppolyoog(ddd')) >> (d).
Based on result from Lemmas E.2 and E.3 as long as A(t) < O (log(d)), we know during time t E [Ti,. Ti] the update rule for A(t) is as follows:
A(t + 1) - A(1) =Cexp exp { - 11* -- 1+0
(1)g((()
)) A(1))
x (10 (1)
(1 (1
5 -113)
(vI
(og
log (og)
(99)
1
}
=0 -xexp (-A(1)) exp +0
(ogg(a))
1
log log
-Cepp(A(()) (1
Ci
log*(d)
where we write C1 in place of O(.) for concrete update expression.
47

---

Published in Transactions on Machine Learning Research (10/2024)
The base case t 1 is trivially true. We proceed with the induction step. Assume the hypothesis true for t E [T),,,T), prove for t 1+1= T++ 1. Note that by Lemma E.10
A(L + 1) = lo + + + E(t)
CCexp (ooo--loCCCC (C(t ( + to) - E(t))) 11
Ci log (d)
=log(C) + log(t T1,1 + (0) + E(t)
+C C(t-Ti,,) + to
1
(1- - E(t) = ((E(t)?))
(1
Ci log (d)
+- 16-1
1 1
1
1
= =log(C) +
+
+
0.
2t T1,1 + C-1to
8(( (t-
T2,1 co
C
+ T-1 + C-
+
(100)
log (d) t- - Ti,1 + C-1lt
1
Ci
+ E((I) + 1- CC-1
(-E(I) + 0(E(1))))
1
log (d)
1-T1,1+011 t0
= =log(C)+ +
Σ
1
1
21 Tí, + C-140
(1 -Ti, + (o
+ C1
log (d)
Ti, C-ilo
+ E(t) -- -i,1 + 0- = (1+
1
G1 log (d)
Invoking Lemma E.10 again,
A(t 1) log(C) + log(t + 11 T1, Co)
C- +
21+ 1- - Ti,
21 Tí,
26-Ti,1 + C-11
+ 1
1
0
+ 0, 1
1
8t -T,, C-
8
-
C
1
log (d) t T₁, + C-1to
(-B()) =((((=((B(())) (1+ Tog
C1
+ E(I) + T-,,,, C-11
(101)
log(C((t (0 +to)
1
+0
2t+11 1 Tı, + C- C- Tı, + C-
(t+1 Ti,1 + Co
+ C
1
log (d) (d)+-Ti Ti,1 +C
Ci (1+ log
+ (l)) + t Tı, + C-1to
(-E(1) (-E()+0(F((3))
48

---

Published in Transactions on Machine Learning Research (10/2024)
To further refine the expression, first note that the error passed down from the previous step t does not grow in this step (in fact it slightly decreases):
(1+
Gi log log((a))
E(t) + -- T1, 111+0-14 (-E(t)
< E())
(102)
t- t-T1,+0 t1
00 (10g"((a)
(dg
T=C 1t
Moreover, notice that at step & + 1, since
+11 41-111+0-10 to (d) the error term [E + 1)1 |A(t + 1)
log(C(( + - -T,1) t0)1 S 0 log
Σ
which finishes the inductive step.
Lemma E.5. With probability at least
MNPk polyid)
) for all t E [0,Ti], all c E [k4],
(A
t.a."
1
A41(
h4
(103)
(())
1
(0)
K4
The identily holds for the =_ "-classes.
Proof. The statements in the lemma follow trivially from Theorem D.1 for time period [o] Let us focus the phase (To, T:].
In this proof, we condition on the high-probability events of Lemma E.4 and Lemma E.2
First of all, based on Lemma E.4 we know that A (- (u+) s Olog(d)) We will make use this fact later.
Base case, 1 = To-
The base case directly follows from our Theorem D.1 Induction step, assume statement holds for [To, t), prove statement for 1.
By Lemma
F.2 know that.
(1
[ogg(()) (1gg((a))) x (A ( (0+) + + }
- -13 (1#0*
exp
-
8*
(v (
log (d)) ))
x [1/3, 1)(1 + x=11/3)
2h P
(104)
and for any CE [k+],
(1) (1)
t.r."
(1 - V1 (1=0
(1x0
log" (log"(a) (an))) (Ar()) 57(0(()))))))))))))) 1, 4 | (otao) }
=xexp
x [1/3, 1](1 + 5-11/3 8*
( (10g 1 log" (d) ))
2
(105)
49

---

Published in Transactions on Machine Learning Research (10/2024)
Relying the induction hypothesis, can reduce the above expressions to
AATO
(4)
(dg ))
( 1 +
)
- -1 1/3 1+0
s A A0t))
(0+)
exp
K+
V (109))
(109((a))
x [1/3, 1] + 8" 1/3) 1113 2k+P P
log (og"
(106)
=nexp {
- (1 s- 1/3) 1 1=0
log (og)(a)) )
1
(1 1
)
[
|
(
k+
x (1) x 2P'
and for any e C [
(1 trar*
=1+ 1/3 (1+0 log'(a)) (a)) (1 ( k- ) s A-A
(
(1gg(1)(())))
s 1 (0+))
=neep
-
(107)
(()) x
2k P
By invoking the property that s* A
(x+) Ollo(dd)), we find that for all E [k+],
(A7
}
AA
exp
+
log"
1
AA
(w+) s (000)((4)))))))
x
K4
1
(1
log 1og"(an)
1
))
x +
(108)
k+
h+
Therefore, we can finish our induction step:
(1+1)
-.. t.e.- + AA7())
(1)
A,e.r- + A1a
A.t.
1
(109)
A (t+1)
AA
θ (k+) x (A + AA7 A.er)))
h4
Lemma E.6. Let Ta()) be the first point in time such that either s' A
1s (0)))))))))))))
2 2(1) or
((1) (0(()) (v-) 2 2(1). Then for any < Ta(D).
A0
O(1)
(110)
A 10))
and for any E [Texa), Ti],
4 (()
(1)
2 Ω
(111)
(0)
(1)
log(d)
.
50

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. This lemma is consequence of Theorem D.1 Lemma E.2 and Lemma E.4
Due to Theorem D.1, we already know that
20 = (11) up to time To. In addition, with Lemma E.2 we
know that before s* AA (()) +.r* | 2 2(1), the loss torm (on a +-class sample) - logit (x,(9) (1)
10
(the same holds with the class signs flipped), in which case it is also easy to derive
(1) by noting
that the update expressions AA AAA = ((1).
Beyond time Ta()), by Lemma E.4 the understanding that s* A of these functions, and the property follows.
we know that 8 A s (w+) 8 A 5- S O(logd))) With
(v+)
(t) 8
(-((0) (v_) ) 2 S1(1) beyond Ta( due to the monotonicity
p
(8
S 0
[dg from Proposition the rest of the lemma
|s (w+)1
Lemma E.7. With probabilily at least
(/NKk+)) polvid)
)
for all E [o, Ti] and all (+,r) E St (u+),
Ab
θ
log (105"(a)))
(112)
The same holds with the +-class signs replaced by the - -laas signs.
Proof. Choose any (+,r)= E ( (m+).
The statement in this lemma for time period 1 E [b, follows easily from Theorem D.1 and its proof. Let examine the period e [To,Ti)
Based on Lemma E.2 and its proof and Lemma E.5 we know that for E [To, Ti]. with probability at least
1-0 0
m
poly(d)
- -1 -11=5-113/111 (100 (og
)) (10)(()
8" A | (oo))
-xexp
1+0
h+
(113)
N
exp(F(") (x(())
x (1 5*
NP (VIEI+O
Σ
Linn = +}
(d))(d)
( (x
F (x! (1))
n=1
exp
Furthermore,
(b +.r
( 2|22
log log (d)
1
(1 5- 11/3 1111 V 1+0 (10))(a)) ))
1
(1
( (2)
A s:
( } (114)
11 log (d)
exp
N
exp(F (1) (X (x(())
8*
(1+
1+++
1 (1/n = +)
NP
log 2 (d)
(
(1) F (x (1)
exp
+
With the understanding that 8* * sc (0+))
< O(log(d)) from Lemma E.4 and the fact. that
exp(F (x)
exp (x F (x( (x("))) = =(1), we have
51

---

Published in Transactions on Machine Learning Research (10/2024)
Ab
1 (o) )) S'Ai s (v+) }
A4
log)(d)
exp
)
1
(115)
log (d)
log log
+
log (d)
Lemma E.8 (Probability of mistake on hard samples is high). For all E [i], given hard test sample hhorts f), y # y,
P P F hhrdd) S (X 2 2(1).
(116)
Proof. We first show that at time t O, the probability of the network making mistake hard test samples is (2)1), then prove that for the rest of the time, i.e. E (0, Ti], the model still makes mistake hard test samples with probability ((1).
time = 0, by Lemma
H.3. we know that for any r E [m]. with probability 22(1),
w (0)
5*) A(oooc. Vd) 2 M(oopolylog(d)) > Ω (oov (og(/))()))
(117)
Relying on concentration of the binomial random variable, with probability at least -((pollylogd))
Σ (10 5*) + -..) 2 (
(118)
is which is asymptotically larger than the activation from the features, which, following from Proposition 1 upper bounded by O (ooylog(d)s* dr)) ) The same can be said for the " "_" class. In other words,
(0) (X hard) - (0) (Xhard) >
( .r. 5*) + 6 > OW (*)
(0)
(119)
1[
4. (*) + 6 (-))
(0)
f/ (3) (") (1 o(1)
which clearly holds with probability 2(1).
Now consider E (0,
During this period of time, by Theorem D.1 and Lemma E.2 we note that for any [k4] and (+, r) e (4)2 (7(0) (v+.c), Actt) f.r ~ W/ 0 AC..- Iz), with Act.r θ AA t.or
2k
os) The same can be said for (+,r) e
st
(0(0)) (x4), although with the (9
2k N
factor replaced by (4 x Also from the proofs of Theorem
D.1 and Lemma. E.2 and using the property (4 < O(1) from Proposition 1 know that for all neurons,
the updates to the neurons also take the feature-plu-CCuuusin--nnin form of >, Eee ((') + (((!) with
A f.r if v' 0. (because the o' component of o' sisiinleeoon neuron's update is already the maximum possible).
(t)) (v') < (1+0( [o)"(a]
A far if o' U+.e for some c e [k4], or ( (v') S (1+0 Tor
52

---

Published in Transactions on Machine Learning Research (10/2024)
Moreover, if U+ E u then Ai. s so ( - + (Adffar xxxoe) so vxx
otherwise, if o. only contains the fine-grained features, then ACt.r so /AAferr
22
With the understanding that only neurons in Sy 0)) (vy)) and Sy (0y,e) can possibly activate the feature patches of sample when < Ti (coming from Theorem F.1.. we have
1 (X S
Σ
E o (w
(wo (0)
Aw (7) vI t0 t. (p) + 64.
+
(tr)es (w_,a) PEP( 1
0=0
(w0
(0)
Aw (T)
tor 5²) + 6
(120)
rE[m]
T=U
Σ
Σ
(w (0)
Aw (7)
tor afv + (p) + b+r
(tr))s (v_ (v_)
PEP(X
T=U
To further refine this upper bound, we first note that with probability at least 1 1 0 ), the following holds with arbitrary choice of (+,r*) E 5 (v+.)):
poly(d)
Σ
Σ
Aw (2) 4,r Vl+ + Sp) 5o 8* ( (w+.c)
Σ
AA(T)
(121)
(+.r)ss (v+,e) PEP(X
0=0
Invoking Lemma E.5
we obtain (for arbitrary (+,r*) E (0+)):
Tu + Sp) 0 (
1-1 (u+.e)
Σ
(r tir:
1 (
Σ
(()) +i--
(122)
kt
(+ (v+.c) (e
r=0
Let us examine the term Ereimi (fw0 + 1-1 Awft. (*) + 110) more carefully. First of all, denoting (t ش (4+
((0)
(ss UU (e-), neurons (+,r) & s(() cannot receive any update
at all during training due to Theorem
F.1 Therefore can rewrite the term
Σ
(w
(0)
Aw (r) t.r: 5²) + +600
re
[m]
T=0
(123)
Aw (7) ri 5*) + 640/ )
Σ
(w
+.
(0)
+
+ Σ o
(wwfor 5*) +b4)
(+r))ss!)
0=
(+r))es
Relying on Corollary F.1.I we know
Ω /polylog(d)
Σ
Ab
(124)
log (d)
7=0
Therefore, we know that for r E [m],
Aww t.ri (*) + A6 50
(125)
53

---

Published in Transactions on Machine Learning Research (10/2024)
As consequence, we can write the naive upper bound
Σ
ww
Aw (F) t,r: 5" + +b4
+.r
re[m]
T=U
<
Σ
(1r (ww (0)
tw++r 5 + b4t + Σ
o
(1o 5*) b
(0)
(126)
(+.r)es!)
(+r)es+
Σ
(ww 5*) + 04.)
rE(m]
Additionally, due Theorem F.1 (and its proof), we know that
1-1
Σ
Σ
(0) o (w
+.r + Σ S ajv + Sp) + 5
(trr)ss (v_ (EP(Xinriio))
(127)
a 6p) + +b4
ajv-
(tr))s ( (pE((Xanciio)
It follows that
(())
(X (hard)
1-1
<0
1
(()
(V+.e)
Σ
Aイ
tipe
+
Σ
E
(w v1 + + + Spl
k+
T=0
(t.r)ss (u+,c) (v+.,) PEP(XInaiUt.))
(128)
+ Σ
(w (w tire 5*) + +bbb))
+
Σ
Σ
(10tor)) + +pp) + +b/%)/
rE(m]
(+.r)s (o_) REP(Xhadii_.
On the other hand, for the s_ neurons, denoting 5 = s (v+ Sto) sth (w= ( (य+ ( (v_),
F (nard) 2
Σ
Σ
(w0 +
Aw (T) afv + (pp) - b(4)
(tir)ss (v_) (ennddid))
(129)
+ Σ a
5*) (t)
(tr)gs!!)
note that the last line is true because neurons outside the set ((()) cannot receive any update during training with probability at least 1 1
mNPkkL due to Theorem F.1 Estimating the activation value of the neurons
poly(d)
from (t (v_) on the feature noise patches requires some care. We define time t.. to be the first point time such that any (-,r*) s=(0) satisfics - 2 do log" (d), and beyond this point in time, i.e. for & [t_, the neurons in (0) have to activate with high probability, since
(w (0) +
1-1 (F) rr afv_ + (o) ( + (10) 2 1-
(10g<(a))
1
)) oo log (d)/ (d)/log" log (d) O(oov/og(o) (130)
>0.
Now we can proceed prove the lemma for t E (0, Ti) by combining the above estimates for F Xaadd and p()) p(0)(Xard))) (Xhard)-
54

---

Published in Transactions on Machine Learning Research (10/2024)
For & E (0,4-), relying argument similar to the situation of 0 and the fact that m - o11)m,
Σ (+r))ss
1((w (0)
(*) + +b 03(200)) (0)
(7 5*)
m
(131)
Σ
1 1( for: (*) + b > 03(w f.rr 5*) (1 o(1)) >0
(0)
(1)
(hard)) F4 (Xhard) > 0
which has to be true with probability (2(1). On the other hand, with t E (il, we have
p(t) X hard) -F (Xhard)
1og" (d) )
1 - 0
8 "0 (W-)AA - O(00 Vlo(d))
0=0
1-1
0
s*
((0) (w++c)
Σ
k+
==U
(132)
Σ
5") + +bbh))
E
(w v1 + +1+ a + Sp)
(+.r)es
(+.))ss ()) (e_.c) PEP( ((Xnarditt.o))
Σ rE[m]
(*) +bb)
Σ
(110 (wu a. + 6p) + b1.0))
(w+t
(t.)es)) (v_ PEP (eE((Xaad:
Let us begin analyzing the first {+) bracket.
By Proposition we know that (tth ( (1 (5 (o+.0) and by Lemma E.5 we know
that AA(T) (log(d))AA therefore,
1-1
log(d)
t-1
k4 8¹
500)
(
(0- .c)
Σ (T) tipo
0
5²
(5 (v_)
Σ
h4
r=0
7=
(133)
[-1
1-0
(ogg(a))
8 s0 (v (o)) - -O0o log(d))
r=0
Therefore, we obtained the simpler lower bound
(1) X hardd
( (2((XNaad)) hardd
Σ a (110
(0) 5*) + +b40
Σ
Σ
+.r v1 + + + Sp)
(0)
(+rr)es(0)
(+r))s))) (o) PE ((Xhardi0+.c)
(m
(134)
Σ rE[m]
(w +.r:: 5²) + 6(0)
Σ
o (ww + +p) + 640)
(+i))ss (w-) (w-)) PEPrX
which is greater than 0 with probability ?(1) (by relying on an argument almost identical to the t = 0 case again, and noting that m - [s(0] = (1 - --(1))m) This concludes the proof.
55

---

Published in Transactions on Machine Learning Research (10/2024)
Lemma E.9 (Probability of mistake easy samples is low after training). For t [T,1, Til, given easy test sumple (X casy, V);
P F F
(Xeasy) S F (X cassy)] - o(1).
(135)
Proof.
Without loss of generality, assume the true label of Xeasy is +1. Assume t 12 T1,1-
Firstly, conditioning the events of Theorem F.1 the following upper bound on F (X holds with
probability least 1-0 0 poly(d)
F(t) (Xeary)
Σ
E
o
(1we VI 180 + (x) + +b",,
(-ir)es (o_) pEp( X Xxmy:m=)
Σ
o (110 (1) vI + cu+.0 + Sn) + (0)
+
(-r))s (m) (PM,)))PPPXXXX DEP(XauritHi..
o (120 VI c04 + +p) (-))+ + +6-
(136)
(-ir)ss()) (v. (EP((euuyit))
o ((000)) vI VI Vl
c0+.c + Sp) + (0)
(-r))ss (v+.e) DEP(())E
<0 (6*d o0)
So(1),
and on the other hand,
p(t) easy) 2
Σ
Σ
(wo
(t) v1 V1 10 + +G) + 6%%))
(+rr)ss (w,) PEP )
E
a ((wffr VI= + (p) + (11)
(137)
+
(tr))ss (or.d pEP(Xanitt.))
>f((1).
Therefore, ( > (())
(easy), which completes the proof.
Lemma E. Jr. & John W. Wrench 1971 ) The parläal sum of harmonic series salisfies the following identity:
1
log(n) + 2n
En
(138)
where is the Mader-Mascheron constant (approrimately 0.58), and en [0, 1/8n|.
56

---

Published in Transactions on Machine Learning Research (10/2024)
F Cearse-grained SGD, Poly-time properties
In this section, set Te E poly(d).
Please nole that we are performing stochastic gradient descent on easy samples only. Theorem F.1. Fix any L E [0, Te].
1. (Non-activation invariance) For any T 2 t, with probability at least mkk
poly(d) )
any feature
(v+,c)e=1
) U (fo U (v+,00 v-}, any S i, (+,r) & 1 (v) and v-dominated patch sample
Cn.p anpu (5)) the following holds:
(r)
σ (110f2 m + +b4) =0
(139)
2. (Non-activation noise patches) For any T 2 t, with probability at least 1 - O
mNNt
)
for every
poly(d)
t' st, str r [m]] and noise patch (r) Sh.p, the following holds:
o (1wf2) (r) (()) + +647 =
(140)
3. Off-diigonna nonpositive growth) For any T 2 t, with probability at least 1 1
(
mk, N.t.
for
polyyas
any S i, uny feature v (v_,c)²= k [w_}, any (+,r) E 540 (v) and u-dominated patch ax and + Shpp a (ww xnn) + b(.)) so (w xnnh)) + +
Proof. Base case t= 0. 1. (Nonactivation invariancc))
Choose any t 2 0, v" from the set (0+.clmm "4" class in this proof; the "_"-class case can be handled in the same way.
the u (v- u (04, Jー J. We will work with neuron sets in the
First, we need to show that, for every n such that (P(X v0)) > 0 and e P(X()) ;*), for every (+,r) neuron index,
(w (0) v²) < 4 / log(d) log log"(d)
(0) x1))) o ((w)
[011)) + 600)
(141)
This is indeed true. The following holds with probability at least 1 - 0 all such xmpp:
mNP poll(a))
for all (+,r) & 1 and
)
f. (r)) + tht SooV1 + // (4 2co) 1/ log" 0
(0)
dg
/ + 200 Vlog(d)oo
log"
(4 2cp) + (log(d) - log" (d) (4 200) log(d)
(
=00
log
/ (4 (ag(loo(d)11/olg -
/ 200 / /lo(dd)
(142)
(4 2co) lo log (d)
1
-00
0
log (d)
(4 + (co)(l)g(d) - 1/ log" + /4+ 200 Log(d)
<0,
The first equality holds by utilizing the identity a- b= 22-
As consequence, a(w (0)
x (1,)1) + (10) = 0.
a+b
57

---

Published in Transactions on Machine Learning Research (10/2024)
2. (Non-activation noise patches) Invoking Lemma H.3 for any 0, with probability at least
- - (polyld)). ). we have for all possible choices of r E [m] and the noise patches and = Sn.p-
(0) ch - Olours /dlog(d) so (10g ou (w
6b
(143)
log
Therefore, no neuron can activate on the noise patches at time t 0.
3. diffodiagnaal nonpositive growth) This point is trivially true at
Inductive step: we assume the induction hypothesis for t E [0, (with T < Te of course), and prove the statements for 11.
1. (Nonactivation invariance)
- Choose any vt from the set {u+.elott U (v-_,ll U fo v_ We will work with neuron sets in the "4" class in this proof; the *-"-class case can be handled in the same way.
( for every &' TT+1.
We need to prove that given 2 T + 1, with probability at least 1 1 poly(d)
(+,r) neuron index and u"-dominated patch æn.p.
(7) (+,r) $ 54 = o ((1 (7))) + b42) 0.
(144)
Conditioning the (high-yrobability) event of the induction hypothesis of point 1., the following is already true all the o*-dominated patches at time t' < T:
(+,r) $ th (w*) = a a + +42) = =0.
(145)
(T) Dp.p) + b2.) 0. In particular, (ww
In other words, no r) 1 (o") be updated the dominnaee patches at time t t= T. Furthermore,
the induction hypothesis of point 2. also states that the network cannot activate any noise patch MNPT Therefore, the neuron update for those (+,r) $ poly(d))
(T) = ChP with probability at least 1 - O
takes the form
N Σ Σ ([P((X()) > 03118n = +} - logit logit("((X))) (x(TT)
A A
NP
DEC(D-)n=1
(146)
x
Σ
1(
(T) t. A + c(7) + ((T) > 0} (T v + C(T)
PEP(X 1))
Now we can invoke Lemma F.2 and obtain that, with probability at least 1 for all relevant neurons and dominated patches:
.mNP
the following holds
poly(d))
(Awl (T) (5) AD?) < 0.
(147)
conclusion, with 2 + 1, with probability at least relevant (n, p)'s
0
mNP poly[a]
for every (+,r) & and
(wr 4. Aur (T) (T(T)) 627 AD (w (w((+)) (T+1) (r))
(T+1)
<0,
(148)
58

---

to Published in Transactions on Machine Learning Research (10/2024)
which leads to (wf ( + b <0 for all t' S T with probability at least 1 - 0 mk NP((+1)
(also
poly(a)
taking union bound over all the possible choices of v*). This finishes the inductive step for point
2. (Non-activation on noise patches)
Relying the event of the induction hypothesis, for any 2 T, the following holds for every E [m]] (r) noise patch 2T,) Cn.p.
and
(T) (w 4.r
(
(T) 4. O.
(149)
Conditioning this high-probability event, this means neuron w (2') can be updated on the noise patches. Denoting the set of features M = (v+.cla Rt Uf f u (o+, vー , for every r E [m], its update is reduced
Aw
(IP(X > (v +) - llogt (T) (X(
NP
vEMn=l
(150)
Σ
1(w
Farl ( (h + b > 0} (al)) u+ (1
(T)
PEP(X. 3))
Invoking Lemma F.3 we have that, for any 2 T++,, the following inequality holds with probability at least 0
MNP for every [m] and noise patches,
poly(d)
Aw (T)) ADT) <.
(151)
Consequently, for any + 2 ++1, 1, the following inequality holds with probability at least. 1 - every r E [m]] and noise patches wn.p </t).
!mNP
for
poly(d)
(w (2)
Aw (T) (T)) + b Ab (wff+))
(T+1) (((T)) ((++2) 0.
(152)
This finishes the inductive step for point 2.
3. (Off- diogonia nonpositive growth) Choose any o" {f-Hu fe-
Choose any neuron with index (+,r). Similar our proof for point 2., we know that its update, when taken inner product with v" -dominnated patch Ta.p v1 + + in + Cn.,. has to take the form
(Aw t.m
VI c0 + +(T)))
Σ Σ
1(P (P))) 1b +} logit (eeit(T)((()) (x(
NP
#E n=1
Σ
1( (T)) (T)
(T)) + 677 () + C.. vi + clT))
1 n.p
PEP(X (T):)
N
n
Σ
Σ (0)
= +} - -logt (T) (x(
NP
(153)
VEM-(U-)REE
Σ
Hww ( U ( (3) > 0) (1S17) vT iv0) ) + (a + C1T c177)
x
PE
m))
N
(1P(( (T), ; loggit (T) (x(
NP
Σ
1w (T) (T) (T)
b,, 0) (2 + (0) VI c(T)))
(T)
!TP
59

---

Published in Transactions on Machine Learning Research (10/2024)
With probability at least 1-0 (T) Sn.p <hip)) < O(1//og"(dd) (d)). Therefore,
NP poly(d)
(anpe + Sn.p: vI +ch 0, and (G VI= =
(T)
+ann U+
log"
N Σ
(Aw (1) 0²)
E
1( ;0] > 03 +} logil+ (2)) (X
NP
9EM- (v" n==1
(154)
(19g1(a)
Σ
1((w (T) (T)
<hop) b b > 070 log" (d)
4.r0 On.p
PEP(X (
(0)
Invoking Lemma F3 know that
$ log'(d) (d) NP
?
VV-
log
ldg (d)
N
Σ Σ
(TP(( ;)) > 0) 16 =+} -logit (x
(155)
neM
1(( a + ( + +b4 > 01)
Σ
(T)
PEP(X!") (
It follows that
(Awl) (T) t.P
VI 1 10"
+ ((F))
Sn.p/ + Ab
<0
n
Σ
1P (T): R)) > 03118,, =} -logit (T) (X!")
Idg
NP
NEM (v*)
Σ
1(100 + nn v
(
+ > 0]
Sn.p
PEP(X(())
(156)
(1
N
lt
Σ Σ BEEM n=1
1(P(
(3) ;0] > 0} 1(sn = +} -logit (xx)t))
(dg
NP
Σ
1( (T) (T) u (T) + 01
( (0)
<0.
Consequently,
(T+1) +.r VI 1v" c(7l) + (T+)))
(
VI 10 + c(T)) + (0 + (Aw (T)
vI 110" + + + +
(157)
(w (T)
Fir vI 1v" + (())) + (T)
4.)
Sa
(w
V1 + c(r)) (0)
Corollary F.1.1 (Bias update upper bound). Choose any Te I poly(d). With probability at least O PPT for all E [0, Tol, any neuron W4.r, and any v (0)
poly(d)
(1 < - polylog(d)
(Aw!) 5*)
(158)
log
60

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. Conditioning the high-probability events of Theorem F.1 above, we know that for any neuron indexed (+, at any time 1. S Te, its update takes the form
N Σ
Aw
7
Σ
0H1 = +} - logit+((X)) (x
NP
PE n=1
(159)
Σ
1/w
(4)
v + Ship) + + > 0} (a n. 2 + chup
x
tort m.
PEP(X: (0)
Tt follows that, with probability at least 1 1 0
polytas)
N
(Awfr
7
Σ
Σ
1 [IP( 1 w) > 0)(1 = =+} -logit (x(")) [
NP
vE
n=1
x Σ
1(w f.r: (1) Skipp + 1 > 03/on 20 + (() S*)
PEP(X (0)
(160)
I "
Σ
Σ
Ligh = +3 -logit (x (x)
NP
(1)
1/ 0 u + c(1)) + 1 > 030 ( (polylog(a)
Σ
PEP(X. (0)
On the other hand,
(1) Aw
17
Σ
Σ
[IP((()0))) > OHL = +3
+} - logit (1)
(x( (xx
+.r
2
NP
!E x=1 for
Σ
1[(w a + c((Pp) + 6 > 03a!!
PEP(X (0) (v)
Σ
1(P(( (v, +} - logit (2) (X
(161)
Σ
1(
10
(()) + 600 > 035(0)
n.
!T m)
2
NP Σ [HIP(X
:)) 03 = +} - logit (2 (x(
(0 n=1
Σ
1/ (1)
tor (0) 10
+c(()) + +b00 > 0} (VI- (1og"(a))
1
! m)
Clearly,
Awl (t) | 2 S2 (polylog(d) (Aw()) (0) (Aw(),.))))
(162)
The conclusion follows.
61

---

Published in Transactions on Machine Learning Research (10/2024)
Lemma F.2 (Nonactivation invariance). Let the assumptions in Theorem D.1 hold.
Denote the set of features C(e*) = (0+.clmm fv- U fo+. m_ {or}. If the update term for neuron (t) be written follows
w -r
Aw
"
Σ
Σ
1 ((X e) fyr = +} (x((t)
NP
vEC(e")
(163)
Σ
1ww
(1)
anp v + ch.p) 610 03 (a + 6nip)
P
then given any T > t, the following inequality holds with probebility at least 1 1-0 patch (T)
NP polyla)
for all v" dddominatedd
(ww (1) t,m a//Tp)) + Ab4i/ < 0
(164)
Proof. Let us fix a neuron wa,r satisfying the update expression in the Lemma statement, and fix some 7 Firstly, the bias update for this neuron be upper bounded via the reverse triangle inequality:
| +.-
Ab(0)
log 3 (d)
N
$ (d) NP
17
Σ Σ ((I(((!)))) > OHl(un +} - logit (x(()))
DEC(u*)
x Σ
H(w t.m anp
(1)
(())
+ +000 > 0)a 2
(165)
PEP(X m)
N Σ
Σ
(1))
0ff18nn +} logit (x("))
logo(d (d) NP
vEC( n=l
Σ
1( +. 1
10
)h.p) + 100 -3
!0 ())
62

---

Published in Transactions on Machine Learning Research (10/2024)
Let us further upper bound the two || lll terms separately. Firstly,
N
Σ vEC((') n==
Σ
[| > 0f11 = - -logit 4 (x(()) )
E
1/w2 (1) t.p 10 v + </ + b 03 1
PEP(X
2
Σ =EC(
Σ
11P(X(0) n2 w1) > 0H1(Em = +} - logit (1) (x(!))
Σ
1(1 (0) + (/ap)) + + > 0)a 20
x
PEP(X 1 (w)
2
(166)
N
E mEC(n") n=l
Σ
11P((X
n w) > 0} I/8n = = - -logit (1) (x.
Σ
1/ (9)
t.y 10 v + ( + +600 > >0aaf1 1/11/2
pEP(X!").))
N
2 Σ Σ
((P((
n2 [0] > 03 1/8n = - -ogiit (x
vEC(v")n=L n=1
X Σ
(1)
t.y 1 v + c/1) + +60 >0/11 -
Secondly, with probability at least 1 - O _NP
poly(d))
N Σ vEC(p=) n=l
Σ
[IP(X("):)) u) > () = =+}- - + -logit (x(())
Σ
1((10 o00 + c( + b(0) > c)
(0000
x
REP(X m))
1
Σ Σ
1(P((
03 1 11h
=
- login (x(())
vEC(#* ) n=
(167)
Σ
1((w tyr a..00 + (()))) + b(0 > 03 ||::00111
X
(EP(X
S Σ Σ
11P(((0)
R .b) > 00 1fn = =}}- - -logit (t) (x((1)
vECle*) n=1
Σ
k( (t)
+ +b10 =((
0} log (d)
!EP(X!!).. ())
63

---

Published in Transactions on Machine Learning Research (10/2024)
Therefore, with probability at least 1 - 0
.P puly[d]
we can bound the update to the bias as follows:
Ab
(
T
(VI-
log" NP
log"(d)
N
Σ Σ
(0) :)) 03 13 = = -logit 4 (x
(168)
vEC( mml
Σ
1(w +.rg n. + (hip) + 110 > >0]
x
PEP(X ())
Furthermore, with probability at least 1 - --- -0(0))+0((0((1) > -
NP poly(a))
the following holds for all n, p:
(1
(a u, chT)), (Shpp al")0"), (Ch <hip) < 0
Togg(())
(169)
Combining the above derivations, they imply that with probability at least 1-O O poly(ay): for any an.p dominated by v²,
(Aw +. x (T)) + Ab
(t)
=(Aw (t)
() v + C(T))
(b
N
Σ
Σ
H(P(X
(1 w) > (u, = -logit -xo (x(
NP
vEC(U-) n=1
Σ
1(( t.m 00 (l + + (a c(t) a
(li))) Ab
N
Σ Σ
1[P((
(0 :0) > fv. = +} - logit (x
NP
VEC(U-) n=1
Σ
1/
0 v + (10p) + + > 0} (laff) v, c/..)) + (c
22 (000")))) )+0++ + (Sh.p (/,7))
(T)
X
t.m n.p
PEP(X m))
+ (1(0) +.
(170)
1
Σ Σ
I(IP(X())))) > 03 +} logit (2) (x(
NP
DEC(P-) n=1
Σ
11(w 2 c(0)) + +000 0} 0
1
(0
PEP(X((0
1 ( log)(d)
NP
(o)
(d)
Σ
Σ
11P((X
( w) ;
0} 1f8m +} logit (2) (1((X (()
vEC(UL)nE)
Σ
11( t.r: (1) -(()) + +000 00
(EP(X(!).)) ())
<0.
64

---

Published in Transactions on Machine Learning Research (10/2024)
This completes the proof.
Lemma F.3 (Nonactivation noise patches). Let the assumptions in Theorem D.1 hold.
Denote the set of features M = (v+,)== - fv- 1. ueo, v-}. If the update term for neuron (1) can written as follows
N
Aw
(1)
Σ Σ
1
(1) x) (3 =+} (xx)i(((X (X!1))
NP
BE n=1
(171)
Σ
1ww (8) 11)
+ (1 b > 0) (a 12 + 5.1
X
+.r: Onp
PEP(X ()
then
(1)
(1 V1---- log"(d)
log (d) NP
x Σ
(()(())) > 07 1fy0 = +} - logith (x (x)())((x(())
(172)
PEM n=1
Σ
1(w t.r, 2np + +1 + D > 03)
pEP(X(")0) m))
Moreover, for any о > 1, the following inequality holds with probability at least -0 (T) (1)
for all noise
poly(d)
patches an.) Sn.p
(t) (Aw
t.m a!lTi) + A < 0
(173)
Proof. Similar to the proof of Lemma F.2 we can estimate the update to the bias term
(b
+.r
11
(VT-L-
[d) NP
log (d)
N
Σ (1)(((()) (1) > t3 11 = - loogi (4)
(xx (x
(174)
x
==
10 + ((()) + ((1) >0} 03)
Σ
1(w
(t)
(9)
(0 (0)
65

---

Published in Transactions on Machine Learning Research (10/2024)
Then for any wap = - with 7 > t, with probability at least 1-0 0
mNp poll(d)
(Aw +.r x n.pl
( A6
-Aw
<hip) Ab
N
7
(I > 0) +} - l ( (x(
NP
VEM n=
Σ
1iw +.r anp u + (1 + b0 > 0)(a! v + Sn.ps S.ip)) + A6
(1)
x
PEP(X) ())
N
7
Σ
Σ
HIP(X
; > 13 = +} logit (2) (X(
NP
n
VEM n=1
x Σ
1( (2)
4,p+ On.p v + (h.p)) + b 0) (1a v2 (lip)) + (Ch c(())) + Ab(
pEP(X ())
N
(175)
1
Σ Σ
1 HIP((
;)) > 03 [/nn =
(1)
= +} -logit (1) (x((0)) (x
NP
R
1EM
Sn.p) +b. > 0} x 0 ( log)(a)) ) + 204
x
Σ
1( (1)
t.p- (1) v + c(t)
PEP(X(" (0)
(d) v1 log" (d)
NP
(d)
N
Σ
(1) w)1 11P(x
0} 18yn = - -logit (x(
x
NE
Σ
1(w (t)
(1) v + ((0) +60 03
x
<0.
66

---

Published in Transactions on Machine Learning Research (10/2024)
G Fine- grained Learning
This section treats the learning dynamics of using fine-grained labels to train the NN; the analysis will be much simpler since the technical analysis overlaps significantly with that in the previous sections.
The training procedure is exactly the same as in the coarse carse-grained training setting. We explicitly write them out here to avoid any possible confusion.
The learner for fine-grained classification written follows for e [k+]:
F+
())
a4,or
Σ
[o((wter mp) + bt.er), E [k+]
(176)
with frozen linear classifier weights a, 1. Same definition applies to the classes.
The SGD dynamics induced by the training loss is now
N
(1+1) w -er + 11 NP
Σ
16m (+, logit (x)
Σ
o' d'((10
f,o, (11) + 100) 1
+,0,
n=1
RE(P)
(177)
1yn (+, (+.c)}[-loiit (0)
(1))
Σ
d(w (0)
t.arr ( + 20
ME(P)
The bias is manually tuned according to the update rule
Aww (1)
f.r.rll l1
(1
(178)
log" (d)
We assign m+,e- (dd2+200) neurons each subclass (+,c). For convenience, we write m dm+
The initialization scheme is identical to the coarse-training case, except choose slightly less negative (0 0oo2 2 (og(d).
The parameter choices remain the same before.
G.1 Initialization geometry
Definition G.1. Define the following sets of interest of the hidden neurons:
1. 400) t.ar {v V: (1) taam v) 2 oov2 200 log(d) log
(0)
Given v E V, s0 (v) C (+) x [m+eel satisfies:
(a)
(w fer v) 2 20 + 200 log(d) + (ag
(b) Yo' V.t. o' v, (w (0)
thr 0²) 2 + 200 log(d)
log Tog"(d) (d)
3. Given v E V, (00) (v) C (+) x [m+.e] satisfies:
(a) (w (we v) 2 2 + 200 log(d) [aj
4. For any (+,c,)) E Sterrey C (+ [m+
(0)
(a) (w v) v o 10 Vo E
(0) (b) t.er < 01)
67

---

Published in Transactions on Machine Learning Research (10/2024)
The same definitions apply to the --class neurons. Proposition 2. At t 0, for all D, the following properties are true with probability at least 1 - -d- over the randomness of the initialized kernels:
1. | (b)l, (sc = ( d
Vlogdd)
(w))
sy (v')l -1
(m)))) and
0 (mmp2(a))
(s)) (w)) (5)00(0)) (v')) - o 0 (mn
In particular,
for any y. e
((+,c)] uu(- cf( and common or fine-grained features v, v'.
( Stageg = -im+e]
The same properties apply to the --class neurons.
Proof. This proof proceeds in virtually the same way as in the proof of Proposition ! so we omit it here.
G.2 Poly-time properties
Thcorem G.1. Fir any E Tel, assuming Te poly(d).
I. (Non-activation invariance) For any 2 with probability at least - 0 mk NPt polyid)
for any feature
, U (v-,cle=m U fu+. v- for every t' S t, (+,c,r) $ (1)(() and v-dommnaated patch E (v-clar sample Zny = an - Shp, the following holds:
a (1ulfom s.(p)))) + (10))
(179)
(Non-activation noise patches) For any F 2 t, with probability at least 1 O
for every polyldt
mNNt
C (k+), E [mm] and noise palch whip = clip, the sollowing holds:
o (ww (ort 2(( + +66)
(180)
3. Soff-iagonal nonpositive growth) Given fine-grained class (+, c) and any T 2 t, with probability at least O mk,NPt for any 1' S t, any feature E {v- U [v=) (v-)us (otte Despes any neuron (r)
poly(d)
W4.or E (v) and any v-dominated patch ahihp an + Snips
(F) +b00 S
(1)
(ww km.p) b4...)
(0) (T) (0)
Proof. The proof of this theorem is similar to that of Theorem F.1 but with some subtle differences.
Base case 1 0.
1. (Nonactivation invariance)
Choose any v² from the set ol U (v U Ufe+,o_ class in this proof; the "_"-class case can be handled in the same way.
We will work with neuron sets in the "4"
First, given r 2 0, we need to show that, for every a such that (P(X!") > and P(X!") 30)) for every (+, (t,,,r) neuron index,
(wi v²) < 0ov2 + 200 log(d) Idg a ( 2(TT)) + +b000.))
(181)
68

---

Published in Transactions on Machine Learning Research (10/2024)
This is indeed true. The following holds with probability at least 1 - 0 all such w/7..
mNP poly(d]
for all (+,r) & (v) and
W 4,0,3 2. (T)) n.p. + b
50ov 1 + / (2 2co) 1/ (d) +0 ( do
)
-v2 + 2c0 200v/og((doo
ldg
(2 + 200) + (log(d) - 1/ (oggllgggg))) (d)) (2 + 2co) log(d)
=00
v (2 + (cog(c))(d) 1/ log (d)) + / 2co (lg(d))
log" (d)
(182)
(2 200 (c0) - (2-2 log
+0
=00
log log (d)
V (2 (log(()) 1/ log" /2 + 2cu log(d)
<0,
The first equality holds by utilizing the identity a a- o²-h² As a consequence, ((w team (1) + + = 0.
o4b
2. (Non-uclivatiion on noise patches) Invoking Lemma H.3 for any 2 0, with probability at least. (7). 1-0 O poly(d] ). we have for all possible choices of r [m] and the noise patches æn. = Cn.-
(0) [w
<hip)) s O v dlog(d)) O (1022
6
(183)
(og
Therefore, no neuron can activate on the noise patchos at time t 0.
3. (Of-ddiogonal nonposilive growth) This point is trivially true at = 0.
Inductive step: assumne the induction hypothesis for 1 L [0,T] (with T < Ta of course), and prove the statements for = T
1. (Nonactivation invariance)
Again, choose any x² from the set (u+ k- U ( k- U 0=),
We need to prove that given 7 2 T1, with probability at least 1 - O (mh,, N for every t' + 1, poly(d)
(+,,,r) neuron index and v" dominated patch x!7).
(0') (+,c,r) & (00c(o") o (fwlffr 2(()) (T) bb())
(.terr))
(184)
By the induction hypothesis of point 1., with probability at least O ( true on all the o*-dominated patches at time t' < T:
[mk_NPT poly(d)
the following is already
(+,0,) & (10((0)) = o (( x + ((9) =
(185)
In particular, ( (fffdr.r and) + b4oo))
In other words, no (+,cr)) & 50% can be updated on the v*-dominated patches time T. Furthermore, the induction hypothesis of point 2. also states that the network cannot activate any noise patch an. Ship with probability at least poly(a]
mNPT Therefore, the neuron update for those
69

---

Published in Transactions on Machine Learning Research (10/2024)
(+,or) & $400 (v*) lakes the form
Aw ter
"
Σ Σ
((P((X
n :0) > (1 = =(,,)) logit
(T)
(X (
NP
+,0 12
DEC(U-) ==1
(186)
x Σ
1(( f.
( a n.
+ (lp) + t,e, 0} ( (a Ch.
PEP(X
Conditioning on this figh-probabilityy event, we have
Aw
tor
Ab tor
(d)
1 77
Σ
Σ
(IP(((())))) .)] > 0H = (+,c)} - logit (x(
(d) NP
MEC( n=1
Σ
11 (t)
2 + (( .ttrr > 030
x
t.r n.p
(187)
(9))
1
Σ Σ
1IP(X (1) ا)] 0H (+,c)} - logit 4% (x("))
+
log (d) NP
VEC(v*) n=1
X Σ
1( (t)
a u + <lopp) + +b4 bffer > 0} ((0))
t.c.
PEP(X 19) :))
Let us further upper bound the two || - ll2 terms separately. Firstly,
N
Σ vEC(U-) x=
Σ ((P(((00)) () > 0H118m = (+,c)] - (o (x(
(t)
x Σ
1(( (o
(000 u + c()) + ((0) > 0]a!!)
PEP(X m))
2
Σ
Σ
1(P((X)) m) 0} (ym (+, - (.git (t)
(x()))
vEc(v-) n=1
(188)
Σ
1((1 (0)
tic,, o + (((h)) + (1)) > 03a!! ||0||2
x
PEP(X m))
Σ
Σ
H(I(((()
(0; w) > 03 1(yn = (+. - logii (x!)))
DEC(v-) n=l
Σ
1( Fer a v + c(())) 640 > 03VI-1
X
(X m))
For the second| ||- ||2 term consisting purely of noise, note that since all the (()) 's are independent Gaussian random vectors, the standard deviation of the sum is in fact
ΣΣ Σ vEC(v-) n=1 !EP(X!") ())
1|P((X b) 0}1 (w cr.
(()
+ + (1) b. > 0}
(189)
1/2
x [1(2 = (+,c)) - logit ". (x())))
Oc-
70

---

Published in Transactions on Machine Learning Research (10/2024)
With the basic property that e م E, leyl for any sequence real mumbers c12 .2,..., we know this standard deviation can be upper bounded by
N
Σ
Σ
Σ
((P((x())))) :0) > 031((1
-,0,0 + ((0) + [ > 0}
(1)
vEC(v-) n=1 pEP(X x :a))
(190)
|1 (), logit (1) 4. (x 0c
It follows that with probability at least 1 - O (pOtVaa)
N
Σ
Σ
((P(X > 0311 {yn = (+, - logit (2)
+.c (x)
vEC( n=1
x Σ
1( (1)
+ <hip) + ((0) > 035112
+.0,1 a
PEP(X! ())
(191)
Σ
Σ
(X; 03 11y (+. logii (4) (
vEC(U-) ( n=1
x Σ
(t) hirm
(0) + ((o))) + ((() > 0)
log (d)
PXP m)
Therefore, we can upper bound the bias update as follows:
(0
1
"
VI
1
log'(d)
(d) NP
log (d)
N
Σ
((P((x()
n (1) w1)l > 03
01/ [1 = -+, - logit 20 (x
(192)
DEC(v-)n=l
x Σ
1 1((0 (t)
tor on + c( + (0)
btoor > 08
PEP(X!"'..) m))
Furthermore, with probability at least --0 0 .PP.
the following holds for all n,
poly(at)
1 (o cl (C, ol))0) (c.)) <(r)) <0 (ogg(())
)
(193)
71

---

Published in Transactions on Machine Learning Research (10/2024)
Combining the above derivations, they imply that with probability at least O (pot(ass ) for any ahih dominated by v",
(Aw+ar 2 (r))
(t)
n.pl + A64 t.ar
= (Aw tarrs ang 0 (TT) + Abtfer
"
E vEC(v-)
Σ
1| ; U)) (ym c). logit (1)
NP
+.c
Σ
1(
(1) u+ (h.p) + + > 0)(a! + Sh.p a 2 o0 + ((7)) + Ab
x
tiam
PEP(X.. :))
"
Σ
Σ
H(P((X
;0) (v = (+, logit (t) (x()))
logit
NP
vEC(v") n=
Σ
1(W an u (()) + +b40 > 03 (a/he v <h.7)) (G -() + (5 ch.p))
(1)
x
PEP(X. m)
+ (b 6,
(194)
7
Σ Σ
1(P(( > 03 1u 00/111n = (+, - -logi (1)
+ (x
NP
vEC(v-)n=l
Σ
Hww
(0) +ior On + (h(p) + (1) > 03 x
+ Abbi
x
log"
t.c.
:EP(X!"..) ;D)
7 NP
(0
(110)(())
(d) (V1- 10g((a))
log" (d)
log"(() (d) (d)
Σ
Σ
(1P((x
(4 - /
ulu = -(,c)) logit (x
x
vEC(v-) n=1
Σ
tirr a anp + + ((0) + (1) > 0}
() m)
<0.
Therefore, with probability at least 1 - O mNP dominated patches:
poly(d) the following holds for the relevant neurons and v*-
AAwll (wweer
(T) her x
(r) npp) + AbfT2r < 0.
(195)
In conclusion, with 2 T + 1, with probability at least 1 - 0 relevant (n, p)'s,
mNP for every (+,c,r) & (f and poly(d)
( (w
t.e.r + Aw (T)
t.c.
(.(T)) + b + (T) ter (w (T!
(T) n.pp
(T-1) H.c.r < 0,
(196)
which leads to (w (t)
t.c.r kn.p) + b. < 0 for all &' <T with probability at least O NP(T+)
(T)
poly(d)
(also by taking union bound over all the possible choices of v² at time T + 1). This finishes the inductive step for point 1.
2. (Non-activation on noise patches)
The inductive step for this part is very similar to (and even simpler than) the inductive step of point 1, so we omit the calculations here.
72

---

Published in Transactions on Machine Learning Research (10/2024)
8. (Off-diagonal nonpositive growth) By the induction hypothesis's high-probability event, already have that, given any fino-grained class (+. c), T T + 1, for any feature v" E fu_ u {v-} U (u+ le and any neuron w4.ars a (ww
(7) (T) -., Fn.p/ + +.or) S (woter a + b....) We just need show that
(1) (Aw taar ( + Ab47 I 0 to finish the proof: the rest proceeds in similar fashion to the induction step of point 3 in the proof of Theorem F.1
Similar to the induction step of point 1, denoting M to be the set of all common and fine-grained features, the updale expression of any neuron (+, (,,,,) r) has to be
N
Aw .CT
Σ
0H1lHn = (+,c)} logit ( (x (X 1(P(X())))
NP
DEMRES R=1
BE
(197)
Σ
1(W (T)
t.crs 100 + Snpp + (T)
t.er > 0} (a + Sn.p
+
x
PEP(XX m))
Written more explicitly,
N
Aw (T)
Σ
Σ
1I (2) x0) 031 [1, 1alll-loge l.0 (x!"))
+,00
NP
#E (vr) n=1
Σ
(T) 1(wwerr a v+ (T)) +b > >0} (a Sh.p
PEP(X! (T) ())
(198)
Hym # (t,c))1(IP(X (T); ;0)) 0llgit (T) (x(()
NP
Σ
1(
1 tiog np D v* + (LT) + toar 0} (T + c12)
(T)
PEP(X
It follows that with probability at least 1 1-0
mNP poly(d]) ), for relevant n, n,P,r, p, we have
Awwl (T)
(T( 20
((T))
1
Σ
Σ
11IP(X > = (lo.igt (T) +.c (x(
NP
(199)
DEM-(utt n=
(111
x
Σ
1 ((
a a + (T) + (T)
t.or
030
log (d)
(T
Furthermore, similar the induction step of point 1, we can estimate the bias update as follows:
(t)
4.0.
N
<- - 1
7
Σ
Σ
H1P(X (1 w)) 13/ = (+,c)) 1fg
(og
NP
(200)
1(w1 (t)
(1)
(0
Sn.)) + (1)
> 0
It. follows that, indeed, (Aw!f)
(T)
kmpp) + Ab 0, which completes the induction step of point 3.
(T)
73

---

Published in Transactions on Machine Learning Research (10/2024)
G.3 Training
Choose arbitrary constant B E [S(1), (og(3/2)
Definition G.2. Let (B( 0 be the first time that there exists some x and c such that
Fy F(T((B) (x, (
2 B for any n E [N] and y {(+,c)) u((-,c))em
We write (B) as To for simplicity of notation when the context is clear.
Lemma G.2. With probability at least 1 O
1m+++ ) the following holds for all t [0, To): polg(d)
1. (On-diagonal common-feature neuron growth) For every E [k+], every (+, (t,rr) E St.0 (u+),
(t) w t.c.r w.c.r =w wter w tter
(0)
(201)
Moreover,
Aw (1) -11/4,2/33
V [ s²-1/3)
2h u+ + ACt)
(202)
where ACt. (O, Act.er D) o (1)
(2)
Vs" Act.er Act.er- (11) 1106 PV2N
The bias updates satisfy
Ab tet -
ns
(203)
kig
log"(d) (d)
Furthermore, every (+,r)= E St (w-) activates on all the v4 v--dominated patches at time t.
(On-diagonal finegronnedfeattu neuron growth) For every e E [h+] and every (t, (t,cr))(t.crr)) e 54.0 (u+.e),
w (1)
tter
w 0))
w.er
w t.r."
(0)
(204)
Moreover,
Aw t.e. 1 (1+0 k++) (11) v1 VI + (1=5=~1/3) 17 2k pepp U4.c + Ac
5*
(205)
(t)2 where She. NOO, Action
I), and (1)
AGt.. (1=0 ( (1 s- 1/3) 1105 PP /NN
v
The bias updales salisfy
lb t,cr - ns
(206)
k4 Plog Poog'(d)
Furthermore, every (+,c,r) E ( activales on all the 04 o4-dominaled palches al time L.
3. The above results also hold with the "+" and 4_ class signs flipped.
Proof. The proof of this theorem proceeds in a similar fashion to Theorem D.1 with some variations for the common-feature neurons.
We shall prove the statements in this theorem via induction. We focus on the +-class neurons; --class neurons' proofs done in the same fashion.
First of all, relying the (high-probabilityy event of Theorem G.1 we know that can simplify the update expressions for the neurons (*(0) (v4.0) the form
Aw! (1)
1
Σ Hyn
(x
(1)
NP
(207)
Σ
19(w(() (t)
tram a u+e + c(()) + b(0)
(1)
b 0) (a.t), + c(!))
PE (..cc)
74

---

Published in Transactions on Machine Learning Research (10/2024)
and for the neurons in st (o+), the updates take the form
Au
7
1 = -ogi (x())
Σ
1inn = -(t,e))[[ (x(
NP
(208)
c'E(ki]-(cc) (c)
x
Σ
1(w u
u+ + ((0) +b0
teer > 0]
(a
p -_ 6h.pp
PEP(X m44
By definition of To and the fact that B S log(3/2), for any [M] and t < To, we can write clwn simple upper bound of logit (.cit+.cX.n" (x!!)):
sep(Ft,eXx,"0
logit (1)
+,c (x)
Ee' exp( Ft (x("))) (X.
E=== ex
(209)
3
2k
4k4
and we can lower bound it as follows
logit (x.( 2 2k x 3 3k
(210)
The inductive proof for the fine-gr ane-grained neurons (0 (u+ is almost identical to that in the proof of Theorem D.1 The only notable difference here is that [1 logit (t) (xx(") }]
has the estimate (1
The inductive proof of the common-feature neurons $t (u+) requires more care its update expression equation 208 is qualitatively different from the coarse-grained training case in Theorem D.1 the full proof here.
we present.
Base case, t t= 0.
With probability at least - -
mNP ) for every E [k+] and every (+,gr) ST(00 (v+), polyta])
(w t.c.r.
(0) (0)
a. 04 (00) + btter
(0)
(1 1)(2 + 2e0 2co) + 1/ / (2 log(d)
80
log (d)
(1 1)(2 200) (log(
(d) (2 + 2cr) log(d)
log (o)) )
o
(211)
() + (log
(2 + 2c0 log(d)
(2 + 20p) 2o0) - /) log 2 (d)
0 log
0o
(2 + 200 2002 (log(d) + 1/log" (d)) + / (2 + 2c0 log(d)
>
75

---

Published in Transactions on Machine Learning Research (10/2024)
This means all the uy-singleton neurons will be updated on all the v4-dominated patches at time t 0. Therefore, we can write update expression equation 208 as follows
Aw (0)
1/ - (+, logit (.) (X +
E
1( (+. (o.t))][ (0) (X (x
NP
(212)
d'E (c)
Σ
(100) u+ -5%
By concentration of the binomial random variable, we know that with probability at least. - -O((lgg(dd) for
all n,
p(x (0) n m+) = (1+ (11
(213)
+.0 (x!1)) at the beginning of the proof and the independence of Now, with the estimates we derived for logit (4) all the noise vectors Sn.p's. i,, we arrive at
Aw (0)
-11/4,2/33 # (1 (1
11 2k p 4+ + AC
5"
(214)
(0) where Act.or ((1) NJI PV2N
VE
Additionally, a byproduct of the above proof steps is that all the 5t. (v+) neurons indeed activate on all the u4-dominated palches at 1 = with high probability.
Now we examine the bias update. We first estimate
Aw (0)
With probability least O
(
tar
(oly
the following upper bound holds for all neurons in S0(0) (U+):
Aw
(0)
50
17
|4 +
ACto/
k
00
1
+
n1t
Vd
(215)
k P
PVN
50
k
and the following lower bound holds (via the reverse triangle inequality):
Aw
(0)
t.r. ||2
20
17
14P
8
||
112 - || A 1
0 1106 (110c
V
20
" P
Vd
(216)
PVN N
20
k
It follows that Aw
f.c.r
(0)
(1TFP)
which means
Aw
(0)
Ab
(0)
.e,r
-
ns 14 Plogg
(217)
log
This completes the proof of the base
76

---

Published in Transactions on Machine Learning Research (10/2024)
Induction step. Assume statements for time [0, prove for t ++ 1.
First, by the induction hypothesis, we know that neurons in St (u+) must activate on all the 04-dominated patches at time Therefore, we can write the update expression equation 208 as follows:
Aw
(1) +.or
7
Σ
1yy = - (4) (X)
E
1(ym (+, [o,c)]][loogte (4) (x
NP
(218)
n=l
c'E(k+l-(c)
Σ
(ali) + +1+
X
PEP(X. 144)
Following the same argument as in the base case, we have that with probability at least - O
LmN
poll(dd)
Aw (t) t.o.
-1144.2/3 -1
(1+ 11 2 P A.t.r
5 + AC(0
(219)
and 0f Ac+.er = (1) X g PV2N
V
Now we need to show that w tee indeed activate all the oo-doiinteed patches time 4.4 with high probability.
()+1)
So far, we know that for r E 10, 1].
(T) Aw t.r 1//4. /
8* u+ + AC(
11 2k: p
t,grt
(220)
(T) and 0 Act.er
=1( x n0
v/"
follows that
PV2N
5* (1+ 2/33) 81= "22,, p St.ert
w W+r
(t+1)
(0)
U+
(1+1)
(221)
where of Ct...-
(t+1) O(1) vt+ Injo PVIN
The following holds with probability at least 1 - 0 mNP over all the u4-dmmintted patches Zn.p (++1)
((+1)
poly(d)
04 + Sn.p (which are independent of (((tt))) and the sinigggleton neurons:
an,p
Sn.p (w (w-r anp vy + clt+1))
(+1) (t-1)
=w (1+.) u+ Sn.p ((++1)) + (t 11144//33/33 (1=5-113)) 11=0 [ogg(d) ))
s*
" 2kk
(222)
+ (c(tt)) anp
(1+1) + 1!
Note that with probability least - O (0 )
((+1)24) x 50(1) VTnee Vs*
(c (hta anp
P/2N Vdlog(d),
(223)
and since vt+I +++1, V < s", σev dlog(d)
and N dk4, we know that
(dy
(Sterr onp 04)
(141) (t+1)
0 1 x (t + 1)m 2k.
8*
(224)
77

---

Published in Transactions on Machine Learning Research (10/2024)
Similarly, with probability at least 1 - O (poly(a))
(C ((+1) n. 04 + Shp & 0(1) x VTno (dlog(d) (o0g(d)=(0 (2
x + 1) 2k P
(225)
PV2N
It follows that with probability at least 1 1
mNP poly(aj)
(w (t+1) 10+1)
u4 + 1
toor m.
2(w 11+1) ut + Cli + 4
Onp
(t + 1)(1 - (1)
(1-0(109((0)
"22 P
8
(226)
Next, let us estimate the bias updates for [0, + 1].
Estimating -eer follows an almost identical argument as in the base case (with the only main difference patches), so we skip its calculations.
(b
being relying on Theorem G.1 for non-activation on
Therefore, 4,er
6
(0)
ne (e+11) Plgg This means
t,e.
( tworr
(++1)
14 + (1 + (++1)
Anp
w tar nnp 04 + (( 1.
(1+1)
+ (++ 1)(1 - () (1 (1- s1-8) (1 (1-0)
1 (())(())) (1)) 722kPP -0 nss (t +
(227)
Plog
>0.
This completes the inductive step.
Corollary G.2.1. At lime & Too ne"
E.P x 8* (
(v+)
ne' P.P
x
s s-(0 (v+.oo) = O(1)
Proof. Directly follows from Lemma G.2 and Theorem
G.1
G.4 Model error after training
In this subsection, we show the model's error after fine-grained training. We also discuss that finetun- ing the model further increases its feature extractor's response to the truc features, so it is even more robust/ bbbust/generalizing in downstream classification tasks.
Theorem G.3. Define (X) = max,e(k,) Fx,,(X), Fx)) max,e (
mkk_ NPTo) m ). the following events take place: poly(d)
With probability at least O
1. (Fine-gruined easy & hard sample test accuracies are nearly perfect) Given an easy or hard fine-grained test sample (X,y) where y E {)+, u((-,c)).mm. P [[-(TT) (X) S max,' du 1 (x) & o(1).
2. (Course-gruined easy & hard sample lest accuracy are nearly perfect) Given easy or hard coarse- grained lest sample (X,y) where E (+1,-1)) P (Ta)
(X) < F (x) S o().
Proof. Probability of mistake on easy samples.
Without loss of generality, assume X (+, class easy sample.
Conditioning the events of Theorem G.1 and Lemma G.2 we know that for all d' [k_],
< O(m log(d) & o(1):
(228)
78

---

Published in Transactions on Machine Learning Research (10/2024)
and for all c' [k+] {c},
Σ Σ of ((wSr,
(o) anp + Sm.p) + +bf.),
t.C,,) ) + 1m 20v
(T))
+.c
pEP(X;0+] (t.r)s (.o((44)
(229)
~s² 5 (w+)
[ (1+1)
(1+ (1+5-1/3) (1
(105"(a))
1
))
n/To nTo2 5*
3
2k
moreover,
F(1b)
Σ
Σ
o ((wfforr anp + Sn.p) + +bb ((T6)
(T))
+ic
(ep(X:u+)
(t (v+)
Σ
a ((w (T))
Wi + Sn.p) + (4ter))
(Fa)
pEP(X:0t.ol (+.r) (0t0)) (vtie)
(230)
28* 5 (u+) (1 1) (1 1 (1- -1---118) (1 log (d) ) nTo s
1
2
+ 8 s410 ( (o+.0) (1-0 (
(1 (1 - --s-1//3) (1- (105((a) k+
1 [11]]
1
s*
1/To TToo2i
2k:
Relying on Proposition
2 we know
|c(0) (1+) = (1+ (mggtaa)) ))
s (m+))
(u+)
and | (o+c)
(TT)) (1+ (log((a)) )) | (u+), therefore (TTT) (X) > maXe' +,o'
(X) has to be true. With Corollary G.2.1
we also have F(TO) (x) 2 2(1) > o(1) 2 maxcre(k-) PTT)) (X). Tt follows that the probability of mistake on an easy test sample indeed at most o(1).
Probability of mistake on hard samples. Without loss of generality, assume X is (+, cl-class hard sample.
By Theorem G.1 (and its proof) and Lemma G.2 we know that for any d' E [k++], the neurons w4.e', can only possibly receive update on v-dominated patches for E (U() te and the updates to the neurons take the
feature-lass form of Eveeyo c(o')e' + Ac(() Ae with c(v') S v1 +1 (1 + s*-1/3) 22 p if
o' is fine-grained feature, or c(v') < 3 (1+ s-~ 1/3) n if u+ (because the v' component of (t) u'-singleton neuron's update is alrcady the maximum possible). Morcover, a dcc.dd SO (nos
V
P/2N
Relying on Theorem G.1 Lemma G.2
Corollary G.2.1 and previous observations, we have
r [1
(X)
Σ
Σ
(Tb) a ( (w (f Unp Sn.p) +b(() )
pEP(X: (t.or))s 20 (wtte)
28" st (
(1-0()
)) (1- 1) () (1-5- 111/ (1-0(192(())
1 s* (ogg(a)
(231)
riTo 2
h4
20(1),
79

---

Published in Transactions on Machine Learning Research (10/2024)
and for d' + c,
t.e
F F(1o)
X I
(ww
(T6)
5*) + t(0
Σ
o ((w (To)
On (n Sn.p) + [
pEP(X . (4. (0t.c)
Σ
Σ
o (lwof upip u_ + Gn.p) + b4.e),,
pEP(X:o-) (+)d (v.)
20(1)
Σ
Awl (T)
ww (w) (0)
t. (*)
(232)
relm+
ticlir
Σ
an + Smip) + (0 bloer))
pEP(Xiu+.a)
(thdr)) (04.e)
Σ
Σ
o (oo
(1w0t
oh + Go.p) + t....)
p (t 1. (v.)
1
00
polylog(d)
Moreover, for any d E [ similar to before,
m
(To)
(m0 (10 (To)
ee 5") + (booor))
X
S
r=1
Σ
o ((w + Sn.p) + b (TT)
(g( .r)
+
p .e) (-,d (-
- (utwe)
+ Σ
Σ
o ( at - Cn.) + +b )
(T))
PEP(X:0-)
(-)))))S (or()) (v))
20(1) x
Σ
(w (To)
-.e/r: 5*) +
Σ
(wo (erre S*)
(233)
(-.0))))
rE(m serl
+ Σ
Σ
(mw -e U+. Sn,p) + 6(0) )r))))
PEP(X:u
(-,6' (E (v).))
+ O(1) st (((0) ((00((()))
(Nupper + + log(d))
1
+0 (00vlog(()) +0 log(d)
50
(polyoo(a))
So(1).
Therefore, (Ta) (X) max,f((+.c F- (Ta) (X), which means (Ta)) (x) (T)) (X) indeed.
Remark. First of all, note that the feature extractor, after fine-grained training, already well-performing, it responds strongly (I(1) strength) to the true features, and very weakly (o(1) strength) any off-diagonal features and noise. In other words, stop training when the margin is at least Ω(1), i.e. when have
((T) (x(")) 2 221) for all n at some T S poly(d), and with high probability, we just F(T) (m) (x(T)) max (
80

---

Published in Transactions on Machine Learning Research (10/2024)
need To time to reach it. This already help explain the linear- linear-probing result ImageNet21k in Appendix A.2. since linear probing does not alter the the feature extractor after fine-grained pretraining (on ImageNet21k), it only retrains a new linear classifier on top of the feature extractor for classifying on the target ImageNetlk datasct.
At high level, fineluning F can only further enhance the feature extractor's response the features, therefore making the model even more robust for challenging downstream classification problems; it will not degrade the feature extractor's response to any true feature. A rigorous proof of this statement is almost repetition of the proofs for fine-grained training, need to note that the properties stated in Theorem G.1 will continue to hold during finetuning (as long we stay in polynomial time), and with similar argument to those in the proof of Lemma G.2 we note that
do not repeat them here. Intuitively speaking, we just
the neurons responsible for detecting fine-gres grained features, i.e. the ( (U+.c), will continue to only receive (positive) updates the dommintee patches of the following form:
N
Aw +.0.
Σ
1 = (+,c)][1 - logit (x!!
NP
(234)
Σ
11 feer a (t) upp + ((t) + (
(t > 0f (anpu++ + (1.0))
x
PEP(X
(1.))
and similar update expression be stated for the St.0 (u+) neurons:
Aw
(t)
18y = -+, -logtt (x (x("))
NP n=1
(235)
1(ww 222 44 + (h + (1))
0) (ofl) + 1...7)
x
PEP(X
(4) (4))
Indeed, these feature-detector neurons will continue growing in the direction of the features they are responsible for detecting instead of degrade in strength.
81

---

Published in Transactions on Machine Learning Research (10/2024)
H
Probability Lemmas
Lemma H.1 (Laurent-Massart X2 Concentration (Laurent & Massart 2000 Lemma 1)). Let N(O, I2).
Por any vector a E IR 20 any & > 0, the following concentration inequality holds:
Σ ag 2 aa + 2|la|l2v/ + 21|a||xt
Set
(236)
Lemma H.2. Let g ~ N(0, (2))) Then,
| 2 50 S eed
(237)
Proof. By Lemma H.1 setting a, = for all and t = d yiclds
P [ 2 o2d 202 20²d sed
(238)
0
Lemma H.3 (Shen et al. (2022a)). Let 91 of and g2 NN oğla) be independent. Then, for any (0, and sufficiently large d, there ezist constants cı, C2 such that
P Kg1. 92)1 @o1o2vdlog(1/))) 2 1 - 8
(239)
1 (2) 22 2
(240)
82


Reviews:
[{"review_id": "bDuxxxpfRp", "reviewer": "Reviewer_bHAS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:  \n1. This paper studies an intriguing phenomenon on neural network generalization, where pretraining with fine-grained labels lead to better representations. The authors provided a theoretical analysis on explaining the reason behind this phenomenon.  \n\n\n2. The authors provided detailed background introduction for the theoretical framework and summarize the results in plain and useful insights.  \n\n\nWeaknesses:  \n1. The authors should have more discussions on the practical implications of the results. Given that pretraining on more labels are beneficial, should we be using this more often in practice? Since unsupervised pretraining is the standard of representation learning nowadays, can the results of supervised learning in this paper provide any insights in the current regime?  \n\n2. Are the learning dynamics the same between pretraining with coarse-grained labels and fine-grained labels? Given that the supervised tasks are different, is one necessarily harder than the others? Some analysis comparing the training dynamics of these two settings would be better.  \n\n3. The studied setting in this paper is that we should do pretraining with fine-grained labels and fine-tuning with coarse-grained labels. I am confused about the fine-tuning part. Why not always fine-tune using the same label space as pretraining? Is it necessarily inferior to fine-tuning with coarse-grained labels? I think the authors should have more discussions on this part or add clarifications on the settings where the claim holds.\n\n4. Another relevant question would be about whether we can gradually interpolate from coarse-grained labels to fine-grained labels during pretraining, or the reversed way. Given the results presented in this paper, do the authors have any intuition about how one should do this interleaved style training? How does it compare to only training in either coarse-grained or fine-grained labels?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a theoretical framework to explain why pretraining deep neural networks (DNNs) with fine-grained labels enhances generalization when fine-tuning on coarse-labeled downstream tasks. The authors introduce a \"hierarchical multi-view\" data model and prove that fine-grained pretraining enables DNNs to learn both common and rare features, leading to better accuracy on challenging test samples. They also show that higher label complexity in pretraining increases the complexity of learned representations, which is key to improved generalization. These theoretical insights are supported by large-scale experiments on datasets like ImageNet and iNaturalist, confirming the practical benefits of fine-grained pretraining.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses.", "broader_impact_concerns": "I do not have concerns regarding the broader impact of this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1BdroTmGbj", "reviewer": "Reviewer_zbHi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. I found the writing in the main part of the text to be very clear. The authors clearly present the intuition behind the technical proofs in the appendices.\n2. The model seems to be reasonably constructed and considered (though limited, necessarily; see below). The model allows for analysis, while being complicated enough to perhaps model the simplest relevant scenario for image classification.\n3. I did not have time to check the theoretical proofs carefully, so I must give the benefit of the doubt on their correctness. At a quick glance the arguments seem to be well-structured and nontrivial.\n\nWeaknesses:\n1. There are many simplifying assumptions in the model that could limit the applicability of the analysis (and the authors admit as much), e.g., the model used is a simple two-layer convolutional network, and both classes and subclasses are represented with a single feature vector each. In reality, models are far more complicated (and would be harder to analytically characterize) and the features that represent a class may be a collection of local patch features in conjunction. \n2. More of a question: The relationship between the common feature vectors and the subclass feature vectors is simply that of orthogonal unit vectors. This does not seem to capture any explicit hierarchical relationship between the common feature vectors and the subclass vectors, e.g., the common vectors being some linear combination of subclass vectors. Was any such modelling attempted, or can you give justification for the choice made here?\n3. The empirical results simply show the effectiveness of pre-training with fine-grained labels, but do not aim to verify the intuitive argument. In particular, it'd be nice to try and show the presence of such \"detector\" neurons and to measure their approximate relative growth. \n4. While the theoretical results are on a simple two-layer ReLU network, the experiments run are with a transformer vision model VitB.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper models and comes up with a theory for the effectiveness of pre-training on fine-grained labels. The intuitive argument (which is represented in their proofs) is that use of many (or an equal number of) subclass labels in pre-training ensures that an equal number of \"detector\" neurons for these subclass labels is produced during training. When only coarse labels are used, the common class labels are overrepresented. \n\nThe theoretical model considers a two-layer convolutional ReLU network and an orthonormal dictionary of feature vectors. The input is represented as a collection of patches and dataset modelling is considered as simple isotropic Gaussian noise on top of feature vectors. Hard test examples are generated by including feature-noise patches and \"high-noise\" patches, which serve as distracting patterns.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, I am in favor of this article, as it seems to be a reasonable attempt at an analytical theory for explaining the effectiveness of fine-grained pretraining. The only thing I would ask for is further discussion of the weaknesses that I've noted above. If experimental evidence backing up the intuitive argument (as noted in point 3) was provided, I'd be willing to champion the article, I think.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "joUsugUKuW", "reviewer": "Reviewer_kxTv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. This topic is very interesting.\n\nWeakness:\n1. Many definitions are not clarified clearly. For example, why and what is the meaning of two superclasses +1 and −1? Can authors take a vivid example to explain this? Moreover, in definition 4.1, what is the difference between \"v_{+}\" and \"v_{-}?\" In definition 4.2, what is the definition of \"v_{y}?\"\n\n2. Why easy sample and hard sample can be defined through Definition 4.2? Any experimental results to support the definition of easy sample and hard sample?\n\n3. This paper is not self-contained, since experimental results are reported in Appendix.\n\n4. I suggest that authors can explain each definition/theorem immediately after introducing each definition/theorem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explains why the generalization performance of a DNN pre-trained using fine-grained labels is better than that of a DNN pre-trained using coarse-labeled data.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Stated in Weakness.", "broader_impact_concerns": "This work does not require adding a Broader Impact Statement", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I suggest the paper should be accepted with minor revision. This is because of the outstanding concern that the paper is not self-contained as the experimental results are entirely in the Appendix. Also, it would be important that the authors emphasise in the text how the provided empirical setting reflects the assumptions of the theoretical analysis (Q1 and Q4 of Reviewer zbHi).
Decision: Accept (poster)