summaries: This paper addresses an interesting problem in retrieval system - compatible features learning. Given the old feature extractor and a new dataset, the objective is to learn a new feature extractor, so that the features extracted by two (old and new) feature extractors are comparable to each other. In the proposed setting, the old dataset (including its statistics), old classifier, and the parameters of the old model are not available.

summaries: This paper deals with an interesting problem of feature compatible learning that the features produced by new model should be compatible with old features. The proposed method uses nearest class–mean classifier instead of linear classifier. Random walk is applied to refine the class means. The proposed method is compared with several baseline methods and shows good performance.

summaries: This work proposes a new problem setting by adding extra constraints to the Feature Compatible Learning problem. The new constraints avoid using old training data and the old model’s parameter when learning a new model. The paper gives a baseline method and its variants for the problem by generating pseudo classifiers to regularize a new model’s learning. The experiments show that the proposed method can satisfy the empirical criterion about success.

abstractText: The need of Feature Compatible Learning (FCL) arises from many large scale retrieval-based applications, where updating the entire library of embedding vectors is expensive. When an upgraded embedding model shows potential, it is desired to transform the benefit of the new model without refreshing the library. While progresses have been made along this new direction, existing approaches for feature compatible learning mostly rely on old training data and classifiers, which are not available in many industry settings. In this work, we introduce an approach for feature compatible learning without inheriting old classifier and training data, i.e., Non-Inherent Feature Compatible Learning. Our approach requires only features extracted by old model’s backbone and new training data, and makes no assumption about the overlap between old and new training data. We propose a unified framework for FCL, and extend it to handle the case where the old model is a black-box. Specifically, we learn a simple pseudo classifier in lieu of the old model, and further enhance it with a random walk algorithm. As a result, the embedding features produced by the new model can be matched with those from the old model without sacrificing performance. Experiments on ImageNet ILSVRC 2012 and Places365 data proved the efficacy of the proposed approach.

title: Lower bounds for covering times for reversible markov chains and random walks on graphs

venue: Journal of Theoretical Probability,

authors:
Gedas Bertasius
Lorenzo Torresani
Stella X Yu
Jianbo Shi

title: Convolutional random walk networks for semantic image segmentation

authors:
Mateusz Budnik
Yannis Avrithis

title: Asymmetric metric learning for knowledge transfer

venue: arXiv preprint arXiv:2006.16331,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

authors:
Jiankang Deng
Jia Guo
Niannan Xue
Stefanos Zafeiriou

title: Arcface: Additive angular margin loss for deep face recognition

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Diederik P Kingma
Jimmy Lei Ba

title: Adam: A method for stochastic gradient descent

venue: In ICLR: International Conference on Learning Representations,

authors:
Yixuan Li
Jason Yosinski
Jeff Clune
Hod Lipson
John E Hopcroft

title: Convergent learning: Do different neural networks learn the same representations

venue: In NIPS,

authors:
Zhizhong Li
Derek Hoiem

title: Learning without forgetting

authors:
Chen Change Loy
Chunxiao Liu
Shaogang Gong

title: Person re-identification by manifold ranking

venue: IEEE International Conference on Image Processing,

authors:
Lawrence Page
Sergey Brin
Rajeev Motwani
Terry Winograd

title: The pagerank citation ranking: Bringing order to the web

venue: Technical report, Stanford InfoLab,

authors:
Sylvestre-Alvise Rebuffi
Alexander Kolesnikov
Georg Sperl
Christoph H Lampert

title: icarl: Incremental classifier and representation learning

venue: In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition,

authors:
Yantao Shen
Yuanjun Xiong
Wei Xia
Stefano Soatto

title: Towards backward-compatible representation learning

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Christian Szegedy
Wei Liu
Yangqing Jia
Pierre Sermanet
Scott Reed
Dragomir Anguelov
Dumitru Erhan
Vincent Vanhoucke
Andrew Rabinovich

title: Going deeper with convolutions

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Chien-Yi Wang
Ya-Liang Chang
Shang-Ta Yang
Dong Chen
Shang-Hong Lai

title: Unified representation learning for cross model compatibility

venue: arXiv preprint arXiv:2008.04821,

authors:
Hao Wang
Yitong Wang
Zheng Zhou
Xing Ji
Dihong Gong
Jingchao Zhou
Zhifeng Li
Wei Liu

title: Cosface: Large margin cosine loss for deep face recognition

authors:
Zhirong Wu
Yuanjun Xiong
Stella X. Yu
Dahua Lin

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Tong Xiao
Shuang Li
Bochao Wang
Liang Lin
Xiaogang Wang

title: Joint detection and identification feature learning for person search

authors:
Jiahui Yu
Linjie Yang
Ning Xu
Jianchao Yang
Thomas Huang

title: Slimmable neural networks

venue: In International Conference on Learning Representations,

authors:
Bolei Zhou
Agata Lapedriza
Aditya Khosla
Aude Oliva
Antonio Torralba

title: Places: A 10 million image database for scene recognition

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

heading: 1 INTRODUCTION

text:
In recent years, deep learning based methods achieved huge success in various of computer vision tasks, especially for visual searching since they could provide powerful feature representations. In a typical visual search system, the deployed deep learning model extracts the features of both gallery and query images as discriminate representations. During the retrieval stage, gallery images will be ranked based on their feature distances (e.g. Euclidean distance) to query images. In conventional approaches, the query and gallery features are generated by the same model. Once the deployed model of retrieval system is updated, the entire set of gallery features need to be ‘backfilled’ or ‘reindexed’ (Shen et al., 2020). As time goes by, the gallery becomes extremely large and ‘backfilling’ could be a painful process since millions even billions of images need to be re-processed by the new model, which is computationally expensive. There has to be a new mechanism that processes gallery images and the query image with two different models, while still maintaining the retrieval accuracy. In other words, the new deployed model extracted features should be ‘compatible’ to the existing ones without sacrificing accuracy. Such feature compatible learning problem is also named as ‘Backward-Compatible Training’ (Shen et al., 2020), or ‘Asymmetric Metric Learning’ (Budnik & Avrithis, 2020).
Existing approaches for feature compatible learning assumed significant overlap between new and old training sets. In Shen et al. (2020), the training set for new embedding model is a superset of the old set. In Budnik & Avrithis (2020), the training set for large and small models is the same, which means obtaining new model in an incremental way is not possible. Besides, in Shen et al. (2020), the classifier for old model is also needed for computing the influence loss, which is a strong requirement in real applications. As an example, a model deployed in a recommendation system as a black-box API takes images as input and returns the processed features, but the parameters of the model are not accessible. In addition, its classifier and training details are not available, neither does the formula of the loss function. This kind of setting is quite common for various practical reasons in search, recommendation, content understanding and review applications.
To address the limitation, we propose an approach for non-inherent feature compatible learning, which only exploits the old model backbone and new training data. Despite the lack of old training data or old classifier, the new model extracts compatible features without sacrificing accuracy. The proposed approach has three contributions including:
• Study and formulate the non-inherent setting of the FCL problem for the first time
• Establish a baseline with a data-incremental approach, where performance degradation is prevented by regularizing the training process of the new model
• Extend the baseline with a random walk algorithm that further improves accuracy
The experiments conducted on several standard data sets validated the effectiveness of the proposed approach.

heading: 2 RELATED WORK

text: Our approach is most relevant to feature compatible learning (Shen et al., 2020; Budnik & Avrithis, 2020; Wang et al., 2020), which has drawn attention from the research community due to the increasing size of gallery sets, and the heavy workload of re-generating gallery features.

heading: 2.1 FEATURE COMPATIBLE LEARNING

text:
Shen et al. (2020) first formulated the ‘backward-compatible’ problem by deriving influence loss from an empirical criterion, and solved it by utilizing the old model to regularize the optimization process.
In Budnik & Avrithis (2020), authors investigated the problem of asymmetric test, where the gallery images are represented by a teacher model and query images are represented by a student model. A pair-based metric for instance-level image retrieval was proposed to achieve the goal. In Wang et al. (2020), authors proposed Residual Bottleneck Transformation (RBT) blocks for feature embedding transferring. Some previous works (Li et al., 2015; Yu et al., 2018) discussed the connection between features that learned by different models. However, all methods mentioned above either can not achieve the model compatibility in a data-incremental way or need to exploit old classifier for training. Our proposed method could achieve compatibility without old training data or utilizing any old classifier.

heading: 2.2 INCREMENTAL LEARNING

text: Incremental learning and Life-long learning (Rebuffi et al., 2017; Li & Hoiem, 2017) approaches aimed to stabilize model predictions when updating with new training data. Different from feature compatible problem, incremental learning focuses on maintaining performance on ‘old’ classes after introducing ‘new’ ones. In Li & Hoiem (2017), authors utilized knowledge distillation (Hinton et al., 2015) and teacher-student models for regularizing features on new data, where model distillation was used as a form of regularization when introducing new classes. In Rebuffi et al. (2017), authors proposed to use old class centers to regularize the model learning when new classes were introduced. Most approaches of incremental learning focus on the stability of classifier output, while feature compatible learning try to solve the feature compatibility problem among different models.

heading: 2.3 EMBEDDING LEARNING

text: Our approach is also relevant to the embedding learning problem that optimizes a distance metric to improve discriminative power and robustness of embedded features. There were efforts on designing powerful network architectures (He et al., 2016; Simonyan & Zisserman, 2014; Szegedy et al., 2015), discriminative loss functions (Deng et al., 2019; Wang et al., 2018), and model optimizers (Kingma & Ba, 2015), but few of them set FCL as a part of their objectives.

heading: 3 APPROACH

text: This section re-visits the basic criterion for feature compatible learning, and presents the formulation and solutions to the Non-Inherent Feature Compatible Learning problem.

heading: 3.1 FORMULATION AND CRITERION FOR FEATURE COMPATIBLE LEARNING

text:
Following the FCL formulation in learning (Shen et al., 2020; Budnik & Avrithis, 2020), an old embedding model φold trained on old training set Dold maps an image x to a feature vector f = φold(x), f ∈ RKold , where Kold is the feature vector dimension of f . After a period of time, a new embedding model φnew trained on Dnew is obtained. The new embedding model φnew maps the image x into a feature vector f with dimension of Knew, where Kold and Knew are not necessarily equal. In our setting, as explained in Sec.1 , the old training setDold is disjoint with the new training set Dnew (Dold ∩Dnew = ø). In addition the old classifier, training details, and the loss function are not available.
The gallery set is defined as G. Since the amount of images in G could be extremely large, the images in G are usually presented as extracted feature vectors by an old embedding model, φold, to save the test time and a query image will be presented as a feature vector with the same embedding model. However, once the embedding model is updated, all the images in G must be presented by the new embedding model φnew, leading to an expensive refresh of the index. To avoid such computation, we need to make it feasible to directly compare G’s embeddings produced by φold with the query embedding by φnew.
In Shen et al. (2020), a strict criterion for feature backward compatible is defined as,
d(φnew(xi), φold(xj)) ≥ d(φold(xi), φold(xj)), ∀(i, j) ∈ {(i, j)|yi 6= yj}.
and,
d(φnew(xi), φold(xj)) ≤ d(φold(xi), φold(xj)), ∀(i, j) ∈ {(i, j)|yi = yj}, (1)
where the d(·, ·) is the Euclidean distance metric, xi and xj are the ith query image and jth gallery image respectively, yi and yj are their labels. Such a strict criterion needs every query-gallery pair fulfills the distance requirement, which is not feasible. Alternatively, authors in Shen et al. (2020) proposed a empirical criterion as the following:
M(φnew, φold) > M(φold, φold). (2)
where M is a evaluation metric for the corresponding retrieval test set, consisting of gallery set G and query set. M(φnew, φold) means to extract query features with new model φnew and gallery features with old model φold, which is defined as cross test. Such a criterion requires the cross test performance between the new and the old model must be better than the test using only the old model, which is defined as self test.
To achieve the backward compatibility defined by Eq. 2, authors in Shen et al. (2020) proposed as below an influence loss term to add into the loss function for regularizing the new embedding model training: LBCT(wc, wφ;Dnew) = L(wc, wφ;Dnew) + λL(wc old, wφ;Dold), (3) where L is the loss function (normally a softmax-like loss), wc, wc old, and wφ denote the classifier weights of the new embedding model, the classifier weights of the old embedding model, and the weights of the new embedding model’s backbone, respectively. The influence loss is the second term in Eq. 3, which fixes wc old and regularizes the feature output of φnew to be compatible with φold, generating relatively small loss on the old classifier. Meanwhile, the new training set Dnew is a superset of Dold. Different from the setting in Shen et al. (2020), we do not assume there is overlap between the old and new embedding training set Dold and Dnew. Moreover, the parameters of old classifier wc old are not available, which means we need to make the feature compatibility happen in a incremental way, without knowing the old classifier.

heading: 3.2 ACHIEVING NON-INHERENT FEATURE COMPATIBLE LEARNING

text:
In this section, we will introduce our proposed feature backward training scheme without using old model’s classifier wc old or old training data Dold. Although we could not obtain the ‘old’ classifier on old training data, which is essential for influence loss in Eq. 3, we can still try to generate a ‘pseudo’ old classifier. Inspired by Rebuffi et al. (2017), Wu et al. (2018) and Xiao et al. (2017), we found that the classifier weights actually act as feature embedding centers so that they can generate large score with positive images’ features, which suggests that even simply averaging images features processed by φold in each class, we could still obtain a reasonable classifier weight for that class, which could be denoted as,
wa−psec old (n) = 1
m ∑ i∈Dnew(n) φold(xni), (4)
wherem is the image amount in n−th class, i is the i-th image in that class, φold is the old embedding model. wa−psec old (n) could be served as n−th column in the pseudo classifier. In practice, we found that using averaged feature vectors as classifier may not converge, classifier consisted of normed feature vector could lead to a much better result,
wan−psec old (n) = wa−psec old (n)
‖wa−psec old (n)‖ . (5)
Another advantage of the proposed approach is that the old training set is not compulsory to use. The ‘pseudo’ classifier for Dnew could be generated with the old embedding model easily, no data in Dold is required, then the loss function in Eq. 3 becomes to
LBCT(wc, wφ;Dnew) = L(wc, wφ;Dnew) + λL(wan−psec old , wφ;Dnew). (6)

heading: 3.3 RANDOM WALK REFINEMENT FOR PSEUDO CLASSIFIER GENERATION

heading: 3.3.1 LIMITATION OF BASELINE APPROACH

text: The baseline method proposed in Section 3.2 exploits the old embedding model and new training set for ‘pseudo’ classifier generation and it can provide us a reasonable result for non-inherent feature compatible learning without ‘old’ classifier. However, due to mis-labeling or low quality, there are some outlier images in each class, simply averaging the feature vectors extracted by old embedding could not eliminate their negative effects. In this section, we will present our random walk approach for refined pseudo classifier generation.

heading: 3.3.2 RANDOM WALK FOR CLASSIFIER GENERATION REFINEMENT

text:
Random walk algorithm (Aldous, 1989) has been widely used for ranking system (Page et al., 1999) or retrieval results refinement (Loy et al., 2013; Bertasius et al., 2017). Random walk is operated on a fully connected undirected graph G = (V,E), where V is the vertice and E is the edge. The similarities between different vertices could be defined as a symmetric matrix S. Each element on the matrix, S(i, j), represents the similarity between vertices i and j (e.g. normalized cosine similarity).
In our context, in n-th class, i-th image’s feature fni ∈ RK could be represented as a vertice V . All of the images’ features in one class can be concatenated as a matrix Fn ∈ RK×m, where m is the image amount of n-th class. The edges, E, among vertices are the similarity scores between different vertices. With notations mentioned above, random walk operation could be denoted as,
F tn = F t−1 n S, (7)
where t is the iteration times, S ∈ Rm×m is the normalized similarity matrix between different images, which is denoted as,
S′(i, j) = { exp(S(i,j)/T )∑ j 6=i exp(S(i,j)/T )
, i 6= j 0, i = j , (8)
where lower temperature T leads to a more concentrate probability distribution.
In practice, the refinement by random walk also needs to be weighted with the initial feature matrix F 0n , which is computed as,
F tn = λF t−1 n S ′ + (1− λ)F 0n , (9) where λ ∈ [0, 1] is the weight parameter. If t tends to infinity, the Eq. 9 has a converaged close form, which is,
F∞n = (1− λ)F 0n(I − λS′)−1, (10) where I is the identity matrix and ( )−1 denotes matrix inverse operation.
Once the F∞n is obtained, the w rw−pse c old (n) could be computed with column-wised average pooling
wrw−psec old (n) = 1
m m∑ i=1 F∞n (:, i). (11)
The refined classifier is also column-wised normalized like Eq. (5), which is denoted as wrwn−psec old and the influence loss changes to,
LBCT(wc, wφ;Dnew) = L(wc, wφ;Dnew) + λL(wrwn−psec old , wφ;Dnew). (12)
Compared with baseline method introduced in Section 3.1, our proposed random walk refinement approach incorperates more information among images’ feature within one class to conduct the pseudo classifier generation, which could largely eliminate the outlier effects. In the experiments, we further show the effectiveness of the proposed method.

heading: 4 EXPERIMENTS

text: We validate the effectiveness of the proposed Non-Inherent Feature Compatible Learning approach on two large public datasets. In this section, We firstly demonstrate the datasets we use and then illustrate the baseline method performance and the effectiveness of the proposed random walk based method. Finally, we analysis the influence of hyperparameter choosing.

heading: 4.1 DATASETS AND METRIC

text: We utilize ImageNet ILSVRC (Deng et al., 2009) and Place365 (Zhou et al., 2017) datasets for training and evaluation. ImageNet dataset contains more than 1.2 million of images with 1,000 classes, Place365 contains about 1.8 million images with 365 classes. We conduct the retrieval process on these two datasets’ validation sets, which means each image will be considered as a query image and all other images will be considered as gallery images. The Euclidean distance is used for ranking. The evaluation metric is Top-1 and Top-5 accuracies. We use the final global averaged pooled feature (before feed into classifier) for the feature distance computing. When conducting the cross test, both old and new model will be utilized for extracting features and distance metric will be computed with old and new feature. If dimensions of old and new features are different, zero padding will be used for dimension alignment. Following the backward-compatibility measuring setting in Shen et al. (2020), we consider backward compatibility achieved when the cross test accuracy using new model for queries and old model for galleries surpasses the self test result of only using old model.

heading: 4.2 TRAINING DETAILS

text: We use 4 NVIDIA P40 GPUs for training. For each class on the training set, 30% of training data will be used for old model training and 70% data will be used for new model training. We adopt two widely used backbones, ResNet-18 and ResNet-50 (He et al., 2016), to serve as old model and new model, the output feature dimensions of them are 512 and 2048 respectively. The image input size is set to 224 × 224. Only random crop and random flip are used for data augmentation. We adopt standard stochastic gradient descent (SGD) to optimize the model parameters. The learning rate is set to 0.1 and decreases 10 times every 30 epochs and the training stops after 90 epochs. The weight decay is set to 10−4 and momentum is 0.9. The weights of two terms in Eq. 3 are equal. The batch size is set to 1024. Both old and new model are random initialized (from scratch). For random walk based refinement, we set λ to 0.9.

heading: 4.3 BASELINE AND PROPOSED APPROACHES ANALYSIS

text:
In this section, we conduct several naive baseline approaches for feature compatible learning without old classifier and old training data. The cross test between old model and these approaches trained new models verified the effectiveness of the method. Besides, surprisingly, the self test of these proposed method even outperform the new model trained without any regularization.
No regularization between φnew and φold We firstly test a simple case which was verified in Shen et al. (2020), directly comparing the isolatedly trained new model (denoted as φnew 70%) and old model (denoted as φold 30%). As illustrated in Section 4.2, we use 30% of training data in each class to train φold 30% and 70% of data is used for training φnew 70%. For aligning their output feature dimensionality, we directly use zero-padding for φold 30%’s feature output to pad it from 512 to 2048. The results on ImageNet and Places365 are shown in Table 1, such directly comparison is an epic failure, which has already been verified in Shen et al. (2020).
L2 regression between φnew and φold output feature A simple baseline that could be proposed is using L2 loss to minimize the output features’ Euclidean distance between ‘old’ and ‘new’ model, which is denoted as φL2new 70% in Table 1. Such simple baseline could not meet the requirement of the feature compatible learning. The possible reason for L2 loss failure is that L2 loss only focuses on decreasing distance between feature pairs from the same image, however, it ignores the distance restriction between negative pairs.
Trained pseudo classifier with new data and φold output feature Another baseline we compared is using old model backbone to process new training data for obtaining the corresponding features, then these features will be fed into a linear layer. The output of this linear layer will be sent into a softmax layer and optimized with cross-entropy loss and new training data label. The loss function could be denoted as,
L = − 1N ∑ i∈Dnew log( exp(wT fi[Li])∑ j exp(w T fi[j]) ), (13)
where fi is the i-th image’s feature processed by φold 30%, Li is the corresponding label, N is the new training data amount, w is the linear classifier weight.
With minimizing the loss denoted in Eq. 13, we can obtain a linear classifier w which produces relatively small loss with fixed old backbone φold 30% on new training data, which could be used in influence loss (Eq. 3) to serve as wold. The ‘new’ model trained with such regularization is denoted as φt−psenew 70%, the cross test result in Table 1 shows that although it is not a total failure, but they can not beat the self test result of φold 30%, which is the basic requirement for feature compatible learning.
Feature averaging pseudo classifier As illustrated in Section 3.2, we could make a pseudo classifier with averaged feature representation of all images in each class on new training dataset. Then we utilize such pseudo classifier to regularize the new model training as shown in Eq. 6. The model is denoted as φan−psenew 70%. As illustrated in Table 1, such simple approach could actually satisfy the feature compatible learning requirement, which surpasses the self test performance of using φold 30% by 15.4% in terms of top-1 accuracy on ImageNet dataset and 8.7 % on Places365 dataset.
Feature averaging pseudo classifier with random walk refinement Following the algorithm introduced in Section 3.3, we conduct random walk refinement for generating classifier, we set temperature parameter T in Eq. 8 to 0.05 and the λ in Eq. 7 to 0.9. Then the refined classifier wrwn−psec old will be served as old classifier in Eq. 12. The trained new model with such regularization is denoted as φrwn−psenew 70%. As illustrated in Table 1, the proposed random walk refinement approach not only fulfill the requirement of feature compatible training, but also outperforms all compared methods.
Better self test performance In Table 1, we show that with our proposed method, the self test results of φan−psenew 70% and φ rwn−pse new 70% even surpass the performance of φnew 70%, which means with the proposed approach, the feature could be improved with the information that provided by old model.

heading: 4.4 HYPERPARAMETERS ANALYSIS FOR RANDOM WALK

text:
Temperature T setting for softmax normalization We firstly investigate the influence of softmax normalization temperature in Eq. 8. High temperature in softmax function leads to a softer distribution, while based on our analysis in Section 3.3, there are some noisy images in each class. We need to make the averaged feature more concentrate on the non-noisy images, so the temperature of the softmax should be low. As illustrated in Table 2, such assumption is verified. Lower temperature provides better results.
Effect of choosing different λ Another investigation is about the choice of λ in Eq. 10, larger λ means the larger weight for random walk refined feature and less for original feature. As shown in Table 2, larger λ will provide slightly better performance.

heading: 5 CONCLUSION

text: In this paper, we investigate several approaches to achieve non-inherent feature compatibility, which aims at achieving feature compatibility without utilizing old training data and old classifier. We conduct comparison experiments on two large public datasets. Compared with other simple baselines, our approach achieved better performance with limited offline computing cost increasing. Furthermore, the proposed method could even improve the feature learning and achieves better self test result compared with model trained without any feature compatible regularization. In the future, we would like to investigate more about the regularization scheme for filling up the accuracy gap between cross test and self test.

title: NON-INHERENT FEATURE COMPATIBLE LEARNING


summaries: This paper studies the gradient norm as a measure of generalization in deep learning. The authors first an approximation to the gradient norm (GN) that is the norm of the gradients for only fully connected layers (AGN). Then they empirically evaluate the correlation between AGN and GN as well as GN and the generalization error. In Section 2.1, the authors conclude that AGN is highly correlated with GN and both are correlated with generalization error. In Section 3, the authors conclude that the correlation between AGN and generalization error is not consistent in a wider family of models. In Section 4, authors propose to use AGN for model selection and conclude that AGN is not good for model selection unless the hyperparameter for mixing AGN with another metric is optimal.

summaries: The paper empirically investigates the sum of gradient norms as a measure to determine the generalization abilities of a neural network. The approach is inspired by the theoretical work of Li, et al. 2020 which showed that the generalization gap can be upper bounded by a function of the sum of the full gradient norms of the training path.

summaries: In this paper, they provide the empirical studies  to understand the effectiveness and efficiency of the use of the gradient norm (induced by [the Li et al., 2020]) as the model selection criterion. To speed up the calculation process the of the gradient norm, they first propose an approximate gradient norm (AGN) based on the depth-wise, sample-wise and epoch-wise accelerations.  Their empirical studies find that the use of AGN can select the models with lower generalization error, but fails for bandit-based or population-based algorithms, and fails to predict the generalization performance of models based on different architectures.  In conclusion, they do not recommend using (approxiamte) gradient norm for model selection in practice.

abstractText: The recent theoretical investigation (Li et al., 2020) on the upper bound of generalization error of deep neural networks (DNNs) demonstrates the potential of using the gradient norm as a measure that complements validation accuracy for model selection in practice. In this work, we carry out empirical studies using several commonly-used neural network architectures and benchmark datasets to understand the effectiveness and efficiency of using gradient norm as the model selection criterion, especially in the settings of hyper-parameter optimization. While strong correlations between the generalization error and the gradient norm measures have been observed, we find the computation of gradient norm is time consuming due to the high gradient complexity. To balance the trade-off between efficiency and effectiveness, we propose to use an accelerated approximation (Goodfellow, 2015) of gradient norm that only computes the loss gradient in the Fully-Connected Layer (FC Layer) of DNNs with significantly reduced computation cost (200∼20,000 times faster). Our empirical studies clearly find that the use of approximated gradient norm, as one of the hyper-parameter search objectives, can select the models with lower generalization error, but the efficiency is still low (marginal accuracy improvement but with high computation overhead). Our results also show that the bandit-based or population-based algorithms, such as BOHB, perform poorer with gradient norm objectives, since the correlation between gradient norm and generalization error is not always consistent across phases of the training process. Finally, gradient norm also fails to predict the generalization performance of models based on different architectures, in comparison with state of the art algorithms and metrics.

authors:
James S Bergstra
Rémi Bardenet
Yoshua Bengio
Balázs Kégl

title: Algorithms for hyper-parameter optimization

venue: In Advances in Neural Information Processing Systems,

authors:
Yuan Cao
Quanquan Gu

title: Generalization bounds of stochastic gradient descent for wide and deep neural networks

authors:
Gavin C Cawley
Nicola LC Talbot

title: On over-fitting in model selection and subsequent selection bias in performance evaluation

venue: Journal of Machine Learning Research,

title: Coherent gradients: An approach to understanding generalization in gradient descent-based optimization

authors:
Ekin D Cubuk
Barret Zoph
Dandelion Mane
Vijay Vasudevan
Quoc V Le

title: Autoaugment: Learning augmentation strategies from data

authors:
Hugo Jair Escalante
Manuel Montes
Luis Enrique Sucar

title: Particle swarm model selection

authors:
Stefan Falkner
Aaron Klein
Frank Hutter

title: Bohb: Robust and efficient hyperparameter optimization at scale

venue: In International Conference on Machine Learning,

authors:
Spencer Frei
Yuan Cao
Quanquan Gu

title: Algorithm-dependent generalization bounds for overparameterized deep residual networks

title: Efficient per-example gradient computations

venue: arXiv preprint arXiv:1510.01799,

authors:
Fengxiang He
Tongliang Liu
Dacheng Tao

title: Control batch size and learning rate to generalize well: Theoretical and empirical evidence

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

authors:
Wenqing Hu
Zhanxing Zhu
Haoyi Xiong
Jun Huan

title: Quasi-potential as an implicit regularizer for the loss function in the stochastic gradient descent

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

authors:
Yiding Jiang
Pierre Foret
Scott Yak
Behnam Neyshabur
Isabelle Guyon
Hossein Mobahi
Gintare Karolina
Daniel Roy
Suriya Gunasekar
Samy Bengio

title: Predicting generalization in deep learning, competition at neurips 2020

authors:
Yiding Jiang
Behnam Neyshabur
Hossein Mobahi
Dilip Krishnan
Samy Bengio

title: Fantastic generalization measures and where to find them

title: A study of cross-validation and bootstrap for accuracy estimation and model selection

venue: In International Joint Conference on Artificial Intelligence,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Yann LeCun
Corinna Cortes
CJ Burges

title: Mnist handwritten digit database

venue: AT&T Labs [Online]. Available: http://yann. lecun. com/exdb/mnist,

authors:
Jian Li
Xuanyuan Luo
Mingda Qiao

title: On generalization error bounds of noisy gradient methods for non-convex learning

authors:
Lisha Li
Kevin Jamieson
Giulia DeSalvo
Afshin Rostamizadeh
Ameet Talwalkar

title: Hyperband: A novel bandit-based approach to hyperparameter optimization

venue: The Journal of Machine Learning Research,

authors:
Ilya Loshchilov
Frank Hutter

title: Cma-es for hyperparameter optimization of deep neural networks

venue: ICLR Workshop,

authors:
Wenlong Mou
Liwei Wang
Xiyu Zhai
Kai Zheng

title: Generalization bounds of sgld for nonconvex learning: Two theoretical viewpoints

venue: arXiv preprint arXiv:1707.05947,

authors:
Vaishnavh Nagarajan
J Zico Kolter

title: Generalization in deep networks: The role of distance from initialization

venue: arXiv preprint arXiv:1901.01672,

authors:
Jeffrey Negrea
Mahdi Haghifam
Gintare Karolina Dziugaite
Ashish Khisti
Daniel M Roy

title: Information-theoretic generalization bounds for sgld via data-dependent estimates

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

authors:
Benjamin Recht
Rebecca Roelofs
Ludwig Schmidt
Vaishaal Shankar

title: Do cifar-10 classifiers generalize to cifar-10

venue: arXiv preprint arXiv:1806.00451,

authors:
Valentin Thomas
Fabian Pedregosa
Bart van Merriënboer
Pierre-Antoine Mangazol
Yoshua Bengio
Nicolas Le Roux

title: Information matrices and generalization

authors:
Vladimir N Vapnik
A Ya Chervonenkis

title: On the uniform convergence of relative frequencies of events to their probabilities

venue: In Measures of complexity,

authors:
Han Xiao
Kashif Rasul
Roland Vollgraf

title: Fashion-mnist: a novel image dataset for benchmarking machine learning

venue: algorithms. ArXiv,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

venue: arXiv preprint arXiv:1611.03530,

authors:
Zhanxing Zhu
Jingfeng Wu
Bing Yu
Lei Wu
Jinwen Ma

title: The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects

venue: In Proceedings of International Conference on Machine Learning,

heading: 1 INTRODUCTION

text:
Generalization performance of deep learning through stochastic gradient descent-based optimization has been widely studied in recent work (Li et al., 2020; Chatterjee, 2020; Negrea et al., 2019; Thomas et al., 2019; Zhu et al., 2019; Hu et al., 2019; Zhang et al., 2016; Mou et al., 2017). These studies initialize the analysis from the learning dynamics’ perspectives and then extend to the upper bound estimation of generalization errors (Mou et al., 2017). More recently, researchers have shifted their focuses onto providing some theoretical or empirical measures on generalization performance (Li et al., 2020; Negrea et al., 2019; Thomas et al., 2019; Cao & Gu, 2019; He et al., 2019; Frei et al., 2019) with respect to deep architectures, hyper-parameters, data distributions, learning dynamics and so on. This work studies the use of generalization performance measures (Li et al., 2020; Negrea et al., 2019) for model selection purposes (Cawley & Talbot, 2010).
Prior to the endeavor of deep learning, the generalization gap has been used as a straightforward measure. Given a set of N training samples{x1, x2, x3, . . . xN}, a deep learning model θ and a loss function L(θ;x) based on the sample x, the generalization gap G is defined as
G(θ) = E x∼X L(θ;x)− 1 N N∑ i=1 L(θ;xi), (1)
where X is defined as the distribution of data, and Ex∼X L(θ;x) refers to the expected loss. To quantify the generalization gap, validation or testing samples have been frequently used to measure the expected loss (Kohavi et al., 1995). Such that given a validation/testing dataset with M samples
{y1, y2, y3, . . . , yM}, the empirical generalization gap ĜM is estimated as
ĜM (θ) = 1
M M∑ i=1 L(θ; yi)− 1 N N∑ i=1 L(θ;xi), (2)
and limM→∞ ĜM = G. However, due to the limited amount of samples, the accurate estimation of generalization gap is not always available (Cawley & Talbot, 2010). It has been evidenced that performance tuning based on validation set frequently causes overfitting to the validation set (Recht et al., 2018) in deep learning settings.
Rather than the use of empirical generalization gap, some advanced measure has been proposed (Li et al., 2020; Negrea et al., 2019; Thomas et al., 2019) to provide data-dependent characterization on the generalization performance for deep learning. For example, Thomas et al. (2019) derived the Takeuchi information criterion (TIC) using the Hessian and covariance matrices of loss gradients with low-complexity approximation. They then propose to use TIC as an empirical metric that correlates to the generalization gap. As the calculation of TIC relies on the use of validation set, TIC for deep learning is a posterior measure. Further, Negrea et al. (2019) improved mutual information bounds for Stochastic Gradient Langevin Dynamics via some data-dependent measure. More specifically, the squared norm of gradients have been used as the data-dependent priors to tightly bound the generalization gap through measuring the flatness of empirical risk surface.
More recently, the squared norm of gradients over the learning dynamics has been studied as the measure to upper-bound the generalization gap (Li et al., 2020; Negrea et al., 2019). All above methods connect the generalization gap of deep learning to the gradients and Hessians of loss functions. While Thomas et al. (2019) is a posterior measure relying on the validation datasets, the two studies (Li et al., 2020; Negrea et al., 2019) provide “prior” measure that uses training datasets. More specifically, Li et al. (2020) proves that the generalization error is upper bounded by the empirical squared gradient norm along the optimization path. Formally, they show that, given a model trained with n samples in dataset X = {x1, x2 . . . xn} for a total of T iterations using a C-bounded loss function is used, the theoretical generalization gap of the DNN θT is bounded as follows,
G(θT ) ≤ 2 √ 2C
n √√√√E X [ T∑ t=1 γ2t σ2t ge(t) ] , (3)
where ge(t) = Eθt−1 [ 1n ∑n i=1 ‖∇L(θt−1, xi)‖ 2 2] is the empirical squared gradient norm in the t th iteration, γt is the learning rate and σt indicates the standard deviation of Gaussian noise in the stochastic process. Their result directly shows that empirical squared gradient norm along the optimization path is a good indicator of a model’s generalization ability. Therefore, we are interested in using this signal as a criterion in model selection, so as to find an optimal set of hyper-parameters.
Our Contributions. In this work, we follow the theoretical investigation in (Li et al., 2020) and try to use the squared gradient norms (GN) over the optimization path as a data-dependent generalization performance measure for DNN model selection. In an empirical manner, the proposed metric GN here should be able to measure the generalization gap of the DNN model θT , which has been trained with T iterations and N training samples, as follows
GN(θT ) = T∑ t=1
[ 1
N N∑ i=1 ‖∇L(θt;xi)‖22
] , (4)
where ∇L(θt;xi) refers to the loss gradient using the model of the tth iteration and the ith training sample in {x1, x2, . . . , xN}. Based on the data-dependent measure GN, our work make three pieces of significant technical contributions as follows
(1) Approximated Gradient Norm (AGN) as an accelerated and low-complexity approximation to GN. Despite the fact that GN can measure the generalization error of a DNN model, the time consumption for GN is high, due to the complexity of gradient estimation using every training sample in every iteration. To lower the computational complexity, we propose Approximated Gradient Norm (AGN) that only uses the summation of loss gradients of the Fully-Connected (FC) Layer in DNN by the end of every epoch (rather than every iteration) as an approximation of GN. Furthermore, the calculation of FC Layer gradient per sample could be further accelerated by Goodfellow
(2015) with extremely low costs. Our empirical evaluation finds that, over various DNN models trained with different hyper-parameters, the metrics GN(θT ) and AGN(θT ) behave identically with respect to empirical generalization gap ĜM (θT ). This approximation makes it feasible to carry out experiments that evaluate the effectiveness of GN for model selection.
(2) To validate the correlations between generalization performance and AGN(θT ), we carry out extensive experiments using various deep neural networks, such as Multi-Layer Perception (MLP), LeNet (LeCun et al., 1998), and ResNet (He et al., 2016), on top of benchmark datasets including MNIST (LeCun et al., 2010), Fashion-MNIST (Xiao et al., 2017), SVHN (Netzer et al., 2011), and CIFAR (Krizhevsky et al., 2009). Observation 1: It has been observed that, when the models are well-fitted (i.e., with low training loss or high training accuracy), AGN(θT ) well corresponds with the empirical generalization gap ĜM (θT ) while models with lower/higher AGN(θT ) are consistently with lower/higher ĜM (θT ) and better/poorer generalization performance. On the other hand, when models are not well-fitted or namely under-fitted, either due to the use of inappropriate hyperparameters or a training process not converged (e.g., T is small), the correlations between ĜM (θT ) and AGN(θT ) are not always consistent while the direction of correlation somtimes is even opposite to the theoretical investigation in Li et al. (2020) and Eq. (3).
(3) To understand the effectiveness and efficiency of using AGN(θT ) for model selection, we extend our experiments to use AGN(θT ) as an objective for hyper-parameter selection, under both blackbox optimization (Escalante et al., 2009; Loshchilov & Hutter, 2016) and bandit-based search (Li et al., 2017; Falkner et al., 2018) settings. Observation 2: We find that, through the combination with training or validation loss, AGN(θT ) can help black-box optimization algorithms, such as particle swarm (PSO) (Escalante et al., 2009) or covariance matrix adaption based evolving strategies (CMA-ES) (Loshchilov & Hutter, 2016), search the models (hyper-parameters) with equivalent or marginally better performance than using validation loss/accuracy as the search objective. The training procedure can somehow avoid the potential overfitting to the validation set (Recht et al., 2018). However the use of AGN(θT ) requests more prior knowledge (additional parameters) to balance the weights of training/validation loss and AGN(θT ) in the combined objective during the search, which might be sensitive for model selection. Observation 3: Further, our research finds that bandit-based search algorithms, such as Bayesian optimization over HyperBand (BOHB) (Falkner et al., 2018), cannot work well with gradient norms. Because BOHB selects and drops models during the learning process with respect to the intermediate measures on performance, while within an end-to-end learning process AGN(θt) (for θ1, θ2, θ3 . . . , θT ) cannot always provide consistent measures on the generalization performance. Observation 4: In addition to hyper-parameter selection for deep learning, our experiment finally finds that AGN(θT ) fails to predict the the generalization performance of the models based on different deep architectures, in comparison to some state of the art algorithms and metrics (Jiang et al., 2019; Nagarajan & Kolter, 2019).
We believe the most relevant studies to this work are those done by Li et al. (2020); Negrea et al. (2019); Thomas et al. (2019) (that measure the generalization performance of DNN using derivatives, such as gradients and Hessian matrices, of the loss), and the contribution made by our work is unique. Compared to Thomas et al. (2019), the measure AGN studied here is also a data-dependent metric to characterize the generalization performance. AGN uses gradients and avoids the use of validation sets, while Thomas et al. (2019) is based on Hessian matrices and relies on validation data. Compared to Li et al. (2020); Negrea et al. (2019), our work studies the feasibility of using gradient norms over learning process for model selection in empirical settings, where we first provide AGN as a low-complexity implementation to accelerate the computation of gradient norms, then we conduct extensive results to demonstrate the pros and cons of using gradient norms or AGN for model selection in two major hyper-parameter search settings. Our result demonstrates the potentials but also limitations in the adoption of current theoretical results (Li et al., 2020; Negrea et al., 2019) as an objective for model selection.

heading: 2 GRADIENT NORM AND ITS APPROXIMATION

text:
Given a DNN model θT that has been trained with T iterations, the straightforward way to compute GN(θT ) is to first collect and store the weights of the model for every iteration during the training process (i.e., θ1, θ2, . . . , θT ), then compute the gradient for every training sample (N in total) on every model (T in total) through backpropagation (BP) over the whole DNN for N × T times. In
practice, such computation cost is far too high. In this section, we present AGN(θT ) as a lowcomplexity approximation to GN(θT ) and then discuss the approximation performance.

heading: 2.1 AGN: APPROXIMATED GRADIENT NORM

text:
We propose AGN(θT ) as a low-complexity approximation to accelerate the computation of GN(θT ) using acceleration strategies as follows.
Depth-wise Acceleration. While DNNs frequently composes hundreds of layers, AGN(θT ) approximates to GN(θT ) using the gradients of last Fully-Connected (FC) Layer of DNNs.
Sample-wise Acceleration. While the computation of GN(θT ) needs to run time-consuming BP for every training sample, AGN(θT ) uses the low-complexity per-sample gradient estimation algorithm (Goodfellow, 2015) to compute the gradients of FC layers without BP.
Epoch-wise Acceleration While the computation of GN(θT ) aggregates the gradient norms for every iteration, AGN(θT ) approximates to GN(θT ) via the summation of squared norms of gradients collected by the end of every epoch. Given the batch size B for every iteration, each epoch consists of NB gradient descent iterations, the learning process with T iterations takes TBN epochs for completion, and θ τNB for τ = 1, 2, . . . , TBN refer to the model obtained by the end of every epoch.
In this way, we propose to compute AGN(θT ) as follows
AGN(θT ) = TB/N∑ τ=1
[ 1
N N∑ i=1 ∥∥∥∇LFC(θ τN B ;xi) ∥∥∥2 2 ] ,
(5) where ∇LFC(θ;x) refers to the gradient of FC layer based on the model θ and the sample x and is accelerated by using the algorithm proposed by Goodfellow (2015).

heading: 2.2 APPROXIMATION PERFORMANCE

text:
We discuss the approximation performance of AGN(θT ) to GN(θT ) from efficiency and effectiveness perspectives, in comparison with validation accuracy, as ways of generalization performance measurements.
Effectiveness Comparison. We find that AGN(θT ) preserves the effectiveness of GN(θT ) as a generalization performance indicator. In Figure 1, we illustrate the comparison
between AGN(θT ) and GN(θT ) using 9 Multi-Layer Preceptors (MLP) models and 12 LeNet-5 models trained using 9 and 12 sets of random hyper-parameters on MNIST datasets. For every model here, we train the model with 40 epoch, measure the generalization gap using the validation set, and estimate GN(θT ) and AGN(θT ) respectively. In Figure 1(a) and (c), we plot GN(θT ) and AGN(θT ) of these models against their generalization gaps. It shows that, despite the different scales of the two measures, the trends of GN(θT ) and AGN(θT ) behave identically with respect
to the generalization gaps. Further, we correlate GN(θT ) and AGN(θT ) for every model and demonstrate the correlations in Figure 1 (b) and (c). We carry out additional experiments on larger neural networks. The results in Fig. 1e and Fig. 1f also validate that the correlations between GN(θT ) and AGN(θT ) are strong, significant, and consistent.
Efficiency Comparison. We find that the computation of AGN(θT ) is much faster than GN(θT ) while it still consumes significantly more time than using validation set for the measurement of generalization performance. In Figure 2, we plot the time consumption per epoch of the three generalization performance measurements, i.e., AGN(θT ),
GN(θT ), and validation accuracy, using LeNet-5, ResNet-20, and ResNet-56 on (parts of) MNIST, SVHN, and CIFAR-100 datasets. To simulate the settings of realistic hyper-parameter search, we collect time consumption of the three measurements using full and reduced (20%) datasets separately. The comparison results show that AGN(θT ) is 220x∼20,489x faster than GN(θT ) while it still consumes 95%∼ 1845% more time than using validation accuracy. Note that, for the comparison, we originally collect the time consumption of GN(θT ) for a single iteration, and then rescale the figures to one epoch.
In summary, we conclude that AGN(θT ) is a low-complexity but tight approximation to GN(θT ) for generalization performance measurement.

heading: 3 USING AGN AS A GENERALIZATION PERFORMANCE INDICATOR

text:
To understand the correlations between AGN(θT ) and generalization performance, we propose to measure ĜM (θT ) and AGN(θT ) of a wide range of DNN models using ResNet-20, ResNet-56, ResNet-110, and DenseNet100x24 (Huang et al., 2017) based on CIFAR-10 datasets. For each architecture, we train 32 DNN models, each of which is with a random set of hyper-parameters and the same number of epochs. Specifically, we hope to discuss the correlations in two scenarios – the model is well-fitted or under-fitted. With sufficient number of training iterations and appropriate settings of hyper-parameters, the models are usually trained to well-fit the training datasets with low training loss and high training accuracy. However, due to the lack of convergence or inappropriate setting, some models are under-fitted even using a large number of iterations.
Observation 1 The correlations between AGN(θT ) and ĜM (θT ) are not consistent from models to models. AGN(θT ) is positively correlated with ĜM (θT ) when models are well-fitted. Otherwise, an opposite trend is observed for underfitted models. Fig. 3 illustrates that the inconsistent correlations between AGN(θT ) and ĜM (θT ) appear in all these architectures. For each architecture, 32 random hyperparameter configurations were chosen to train 32 models, and we obtain each model’s AGN(θT ) at the end of 160 epochs as well as its generalization error, plotted in Fig. 3a. We observe that the scatters exhibit a trend that looks like an inverted checkmark. This shape indicates that
the correlation between AGN(θT ) and generalization error behave differently based on model con-
vergence. Due to this inconsistent behavior, it is not always possible to use AGN(θT ) as an indicator of generalization performance unless the models are well-fitted.
Positive correlation between AGN(θT ) and ĜM (θT ) for well-fitted models We identify the models with top 50% training accuracy. These models have fitted the training set with at least 88% accuracy and hence they are well-fitted models. These models show positive correlation between AGN(θT ) and ĜM (θT ), as shown in Fig. 3b. It is feasible to use AGN(θT ) as an alternative generalization performance indicator, in addition to the validation loss/accuracy, under these settings. This observation coincides with the theoretical findings in Li et al. (2020) and Eq. (3). However, the p-values for Pearson correlation in Fig.3(b) are 0.336, 0.039, 0.036, and 0.053 respectively. These values overall indicate weak positive correlation between generalization gap and AGN(θT ) as three of them are close to or lower than 0.05. This weak correlation is most likely a result of that GN(θT ) does not work very well as a metric in practice, since we have already shown the experimental results that indicate good approximation of AGN(θT ) to GN(θT ) in Fig. 1.
Negative correlation between AGN(θT ) and ĜM (θT ) for under-fitted models In contrast, we also identify the models with bottom 50% training accuracy. Such models are under-fitted models due to inappropriate settings of hyper-parameters or lack of convergence in the training process. Fig. 3c shows that AGN(θT ) is negatively correlated with ĜM (θT ) for under-fitted models. We however do not consider this observation conflicts with the theoretical findings in Li et al. (2020) or Eq. (3), because Li et al. (2020) actually studied the learning dynamics of DNN in asymptotic settings, where authors derived the upper bound of generalization error using gradient norms when T → ∞ (the training procedure has been well converged and models are well-fitted). Nonetheless, it still seems to be surprising that there is a negative correlation between AGN(θT ) and ĜM (θT ). We offer an intuitive explanation here. The trend is that gradient norm gradually decreases as training proceeds while generalization gap increases (also reported in Li et al. (2020)). Across models with different hyper-parameters, these two quantities could possibly change their magnitude at very different speed. A model that remains under-fitted throughout training has low generalization gap (it makes almost random guesses on both training and test sets), but the training samples are likely to consistently produce large gradients. As a result, under-fitted models with smaller generalization gaps have larger AGN(θT ), contributing to the negative correlation shown in Fig. 3c.

heading: 4 USING AGN FOR MODEL SELECTION

text: In this section, we investigate the feasibility of using AGN(θT ) as a generalization performance indicator for model selection. We consider two possible applications of AGN(θT ), where the first one is to incorporate AGN(θT ) as an objective for hyper-parameter search for a fixed architecture, and the second one is using AGN(θT ) to predict cross-architectural models’ generalization error.

heading: 4.1 USE CASE 1: HYPER-PARAMETER SEARCH FOR DEEP NEURAL NETWORKS

text:
To address the fitness issues from Observation 1, we propose to include the training loss and/or validation loss as the search objectives as follows
ObjectiveAGN+Train(θT ) = α ·AGN(θT ) + 1
N N∑ i=1 L(θT ;xi),
ObjectiveAGN+Val(θT ) = α ·AGN(θT ) + 1
M M∑ i=1 L(θT ; yi),
(6)
where {x1, x2, . . . , xN} and {y1, y2, . . . , yM} refer to the training and validation sets respectively, and α is a weight to balance the training/validation loss and AGN(θT ).
We test the effectiveness of the above two search objectives by conducting hyper-parameter search using ResNet-20 and ResNet-56 on Fashion-MNIST, SVHN, and CIFAR datasets respectively. The results of Fashion-MNIST and SVHN are found in the appendix. On top of the two objectives in Eq. (6), we try multiple settings of α and adopt two commonly-used black-box optimization algorithms, including CMA-ES (Loshchilov & Hutter, 2016) and PSO (Escalante et al., 2009), for hyper-parameter search with a computation budget of 5,120 GPU×epochs, where we take a reduced training set with 20% training samples (Cubuk et al., 2019) to accelerate the search procedure. The search space is with Batch Size [32, 1000], Learning Rate [1 × 10−7, 0.50], Momentum [0, 0.99], and Weight Decay [5 × 10−7, 0.05], while initial settings are Batch Size = 100, Learning Rate = 0.01, Momentum = 0.6, and Weight Decay = 0.0005.
Default hyper-parameter setting For every pair of dataset and the DNN architecture, there exists a “default” set of hyper-parameters that has been frequently used/suggested by practitioners, or published in their official releases. For example, the hyper-parameters including Batch Size = 128, Learning Rate = 0.1, Momentum = 0.9, and Weight Decay = 10−4 have been frequently used to train ResNet-20 on CIFAR-10. In the tables following, “Default” refers to models trained with the default hyper-parameter configuration.
Observation 2.When combining AGN(θT ) with training or validation loss as search objectives, black-box optimization algorithms can search the hyper-parameters with performance marginally better than using validation accuracy only, whilst models can avoid overfitting to the validation set (Recht et al., 2018). However, such practice requests prior knowledge (i.e., α in Eq. (6)) to balance the two factors in the search objective. Table 1 and Table 4 (in appendix) present the results of comparisons, where we include the testing accuracy of the models trained using full training set and the hyper-parameters found by black-box optimization algorithms. For every set of searched hyper-parameters, the model has been trained and tested three times with error bars estimated. For both CMA-ES and PSO algorithms, the two objectives can help search the models with significantly better or worse testing accuracy than the one selected by using validation accuracy as objectives.
Furthermore, the use of these two objectives can fix the issues of overfitting to the validation set for model selection. For example, the result of ResNet-20 on Fashion-MNIST using validation set in Table 4 has a lower test set accuracy than the model trained with default hyper-parameters. This phenomenon is likely due to overfitting the validation set since ResNet-20 has a rather large capacity to learn and Fashion-MNIST is a relatively easy dataset. In contrast, AGN+Train or AGN+Val leads to slightly better result than the default model, significantly outperforming using validation loss. The final model selection highly depends on the choice of α. We however do not know such prior in advance, while trends of performance over α are not consistent or obvious. In this way, we can conclude that there exists potentials of using AGN(θT ) as part of search objectives for black-box hyper-parameter optimization when the prior knowledge on the settings of α is known. Otherwise, the use of AGN(θT ) might even hurt the hyper-parameter search, no matter whether it is combined with training or validation loss.
Observation 3. AGN(θT ) sometimes cannot work well with bandit-based hyper-parameter search, as the correlation between AGN(θT ) and generalization performance is not always consistent during the training process from under-fitted to well-fitted status. We carry out the similar hyper-parameter search experiments using BOHB algorithm under the same settings (search space, initial values, and computation budget). For fair comparison, BOHB normalizes AGN(θt) in the objectives (and the setting of α is slightly different from the black-box optimization settings), since BOHB has to compare AGN(θt) of models obtained from different iterations t of the training process while the scale of AGN(θt) varies significantly.
In Table 2, we present the testing accuracy of the models that are trained using the hyper-parameters searched by BOHB with the objectives. The results show that, though it is able to outperform the default one (such as ResNet-20 on Fashion-MNIST using AGN+Train, α = 0.1), using AGN(θt) within BOHB cannot produce better results than the default setting in most cases. Since the correlation between AGN(θt) and ĜM (θt) is not always consistent over the optimization path, AGN gives BOHB inaccurate feedback on model generalization performance in early stage of training. Consequently, BOHB tends to early terminate some good models and continue training the inferior ones. This results in deteriorated model performance through the bandit-based search.

heading: 4.2 USE CASE 2: CROSS-ARCHITECTURAL GENERALIZATION ERROR PREDICTION

text:
We evaluate a series of complexity measures to test their effectiveness of predicting generalization error using the public dataset provided in a competition at NeurIPS 2020 named “Predicting Generalization in Deep Learning” (Jiang et al.). The descriptions of experimental setup and public dataset are available in the official document of competition details. Briefly, we use 150 trained VGG-like architectures (along their datasets used during training, namely SVHN and CIFAR-10) as datum and predict their generalization error with the listed theoretical complexity measures in Table 3. The predictions are evaluated using conditional mutual information. The possible scores are between 0 and 100. A higher score indicates that the complexity measures is able to more accurately and consistently predict the generalization error. The results in Table 3 show that although AGN(θT ) is able to outperform some baseline theoretical complexity measures in predicting generalization error, its effectiveness is largely limited. The ineffectiveness of using AGN(θT )
to perform cross-architectural generalization error prediction implies it is also ineffective to use GN(θT ) in practice since we have shown that AGN(θT ) approximates GN(θT ) very well.

heading: 5 CONCLUSION

text: In this paper, we have studied the feasibility of using AGN(θT ), an approximated form of squared norms of loss gradients over optimization path (Li et al., 2020), to measure generalization error in practice. We find the correlations between AGN(θT ) and ĜM (θT ) are completely opposite for under-fitted and well-fitted models, where the positive correlations between the two variables found in well-fitted models coincide with the theorems by Li et al. (2020). Furthermore, the use of AGN(θT ) to complement the validation accuracy as the objectives can marginally improve the performance of hyper-parameter optimization, however the computational overhead caused by AGN(θT ) estimation and the lack of some prior knowledge makes such paradigm neither efficient nor effective. In the meanwhile, the same set of objectives does not bring any improvements for bandit-based algorithms such as BOHB, partially due to the inconsistent correlation between the objective and generalization performance throughout the training phase. As a result, using the gradient norms for model selection in practice remains challenging due to the high computation overhead (using the approximated version is up to 18 times slower than standard training) and limited effectiveness. Our experiments also show that AGN(θT ) cannot effectively predict generalization error given different architectures. In conclusion, we do not recommend using GN(θT ) or AGN(θT ) for model selection in practice.

heading: A EXPERIMENTS

text:
A.1 EXPERIMENTAL SETUP
Datasets and Data Augmentation We briefly introduce the benchmark datasets used in this paper and the data augmentation methods we applied when loading the data.
• Fashion-MNIST (Xiao et al., 2017) is a benchmark dataset similar to the popular MNIST dataset (LeCun et al., 2010). It has 70,000 grayscale images in the size of 28×28, dividing into 10 classes. The training set has 6,000 images from each class while the rest make up the test set. We normalize the input data as done in common practice.
• SVHN is a benchmark dataset composing house-number signs in street level images (Netzer et al., 2011). We use the cropped digits dataset for training and testing. We normalize the input data as done in common practice.
• The CIFAR-10 dataset has 6,000 examples of each of 10 classes and the CIFAR-100 dataset has 600 examples of each of 100 non-overlapping classes (Krizhevsky et al., 2009). We apply standard data augmentation the same way as the Pytorch official examples on CIFAR10 and CIFAR-100 classification tasks. Specifically, we pad the input images by 4 pixels, and then randomly crop a sub-region of 32 × 32 and randomly do a horizontal flip. We normalize the input data as done in common practice.
Reduced Dataset To reduce the expensive computation cost for training a model for multiple rounds, we train the model on the reduced dataset when searching for hyper-parameters, where only a random but fixed 20% subset of the standard dataset participates in the training. Training on the reduced dataset gives us a set of hyper-parameters, which is then used to train a separate model with the standard training set. The newly trained model is then validated on the standard test set. We report the final test performance in the main paper. The strategy of using a reduced dataset for hyper-parameter search is also used by Cubuk et al. (2019).
ResNet Training Details For different architectures of ResNet, we train them for 160 epochs. For the default baseline model, we set the initial learning rate to be 0.1 and decay it by 1/10 and 1/100 at epoch 80 and 120 respectively. Momentum is set to be 0.9 and weight decay is 0.0001. The default batch size is 128. The loss function used for all experiments in the paper is cross entropy loss.
Blackbox Optimization Setup The process of blackbox hyper-parameter optimization is split into 4 rounds. We train 8 models with different sets of hyper-parameters in parallel in one round. At the end of each round, a blackbox optimization algorithm is run based on the model score computed by using a validation set or using our metric. The algorithm generates the next 8 sets of hyper-parameters to search for the optimal ones. We use two blackbox optimization algorithms for hyper-parameter search, which are Covariance Matrix Adaptation - Evolution Strategy (CMAES) (Bergstra et al., 2011) and Particle Swarm Optimization (PSO) (Escalante et al., 2009).
BOHB Hyper-parameter Search Setup We use BOHB (Falkner et al., 2018) to test how our proposed objectives work with bandit based training hyper-parameter optimization algorithms. For all ResNet architectures, the minimum budget is 40 and maximum is 160. We pick η to be 2 so that the total number of training epochs using BOHB would be the same as that using blackbox optimization algorithms. This ensures fair comparison across the two types of hyper-parameter optimization algorithms.
A.2 NOTES ON TIME CONSUMPTION ANALYSIS
Interpretation of Figure. 2 in the Main Paper Each bar in the plot represents the total time consumption in one epoch, including time spent forwarding the data, updating the model parameter with backpropagation, and computing GN(θT ) or AGN(θT ) if needed. The results are obtained by running models multiple times on 1080Ti GPUs.
GPU×epochs We define 1 GPU×epoch as iterating through the training set for one round on one GPU. Note that 1 GPU×epoch corresponds to different amount of wall clock time depending on the
architecture, dataset as well as batch size. Figure 2 in the main paper shows some examples of the wall clock time that 1 GPU×epoch costs under those settings. When running hyper-parameter search algorithms, we keep GPU×epochs as a constant variable to ensure each algorithm iterates through the training set the same number of times. As mentioned in the main paper, we set the total budget to be 5,120 GPU×epochs for all hyper-parameter search algorithms. Blackbox optimization algorithms used in this paper, namely CMA-ES and PSO, explores 32 sets of hyper-parameters whereas BOHB, as a more efficient search algorithm with early termination of poorly performing models, explores 36 sets of hyper-parameters in total.
Specific time cost for hyper-parameter search. The time cost for hyper-parameter search using the reduced training set with validation accuracy as the criterion for ResNet-56 on CIFAR-10 is 856s per model on average. When AGN is used to complement validation accuracy, the average is 3,633s for one model.
A.3 DISCUSSION ON TRAINING BEHAVIOR
Fig. 4 shows the training behavior of ResNet-20 on Fashion-MNIST with four different hyperparameter settings. We analyze how the training and test losses vary under these settings and obtain the observations below.
AGN Helps Reduce the Generalization Gap First, Fig. 4a indicates a gradually enlarging gap between the training loss and testing loss. This phenomenon is likely due to that we train ResNet-20 models for 160 epochs, which is easy to overfit the Fashion-MNIST dataset. As a result, there exists a generalization gap, where the training loss is very close to zero, but test loss is about 0.325. In contrast, when AGN and training loss are used as a combined objective in CMA-ES hyper-parameter optimization (Fig. 4d), the final generalization gap is 0.259, which is 20.3% lower than the generalization gap using the default hyper-parameter. This decrease in the magnitude of generalization
gap demonstrates the effectiveness of using AGN to complement hyper-parameter optimization algorithm.
AGN Helps Avoid Overfitting the Validation Set An interesting observation is that using the method HS1 + Val to search for hyper-parameters yields worse test set performance than the model trained with default hyper-parameters. This is likely because the model is able to overfit the validation set after multiple rounds of training during hyper-parameter optimization. Consequently, the model cannot generalize well on the test set. In contrast, when AGN is used in the metric, we can further improve the baseline model with default hyper-parameters by 0.21% (the test performance using default hyper-parameter is 93.34 ± 0.07 whereas using CMA-ES(AGN+Train,α=0.1) is 93.51± 0.19.
AGN Helps Hyper-parameter Optimization Algorithm Find More Stable Settings When compared to Fig. 4b and Fig. 4c, Fig. 4d shows that the incorporation of AGN enables the search algorithm to find a set of hyper-parameters that gives rise to better and more stable performance on the test set as the model is being trained. The magnitude of test loss in both RS(Val) and CMA-ES(Val) can be 10 times bigger than training loss or even worse, whereas CMA-ES(AGN+Train) finds a set of hyper-parameters that keeps test loss relatively close to training loss throughout. The test loss of method CMA-ES(Val) can be as high as 7 in the midst of training. However, the loss curve is far more smooth in the case of CMA-ES(AGN+Train), as shown in Fig. 4d.