Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks
Authors: Eeshaan Jain
Tushar Nandy
Gaurav Aggarwal
Ashish V. Tendulkar
Rishabh K Iyer
Abir De
Venue: NeurIPS 2023 poster (2023)
Keywords: Data Subset Selection
Efficient Learning
TL;DR: We propose an efficient and generalizable non-adaptive subset selection method to quickly select subsets for a set of architectures.

Abstract: Existing subset selection methods for efficient learning predominantly employ discrete combinatorial and model-specific approaches, which lack generalizability--- for each new model, the algorithm has to be executed from the beginning. Therefore, for an unseen architecture, one cannot use the subset chosen for a different model. In this work, we propose $\texttt{SubSelNet}$, a non-adaptive subset selection framework, which tackles these problems. Here, we first introduce an attention-based neural gadget that leverages the graph structure of architectures and acts as a surrogate to trained deep neural networks for quick model prediction. Then, we use these predictions to build subset samplers. This naturally provides us two variants of $\texttt{SubSelNet}$. The first variant is transductive (called Transductive-$\texttt{SubSelNet}$), which computes the subset separately for each model by solving a small optimization problem. Such an optimization is still super fast, thanks to the replacement of explicit model training by the model approximator. The second variant is inductive (called Inductive-$\texttt{SubSelNet}$), which computes the subset using a trained subset selector, without any optimization.  
Our experiments show that our model outperforms several methods across several real datasets.

Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks
Eeshaan Jain Tushar Nandy", Gaurav Aggarwal', Ashish Tendulkari, Rishabh Iyer* and Abir De
IIT Bombay, !Goglee "UT Dallas (eeshaan, tnandy abir) www.eiiibba...... (gauravaggarval, agoi bgg com, rishabh. iyer@utdallas, edu
Abstract
Existing subset selection methods for efficient learning predominantly employ discrete combinatorial and model-specific approaches which lack generalizability. For an unseen architecture, one cannot use the subset chosen for different model. To tackle this problem, we propose SUBSELNET, trainable subset selection framework, that generalizes across architectures. Here, we first introduce an attention-baser neural gadget that leverages the graph structure architectures and acts as surrogate to trained deep neural networks for quick model prediction. Then, we use these predictions to build subset samplers. This naturally provides us two variants of SUBSELNET. The first variant is transductive (called Transductive- SUBSELNET) which computes the subset separately for each model by solving small optimization problem. Such optimization is still super fast, thanks the replacement of explicit model training by the model approximator. The second variant is inductive (called as SeauutiveSSBSEeNNN using a trained subset selector, without any optimization. Our experiments show that our model outperforms several methods across several real datasets.
which computes the subset
Introduction
In the last decade, neural networks have drastically enhanced the performance of state-of-the-art ML models. However, they often demand massive data to train, which renders them heavily contingent on the availability of high-performance computing machineries such GPUs and RAM. Such resources entail heavy energy consumption, excessive CO2 emission, and maintenance cost.
Driven by this challenge, recent body of work focuses suitably selecting subset of instances so that the model can be trained quickly using lightweight computing infrastructure 23 51 32
54 37
21 36). However, these methods are not generalizable across architectures the subset selected by such method is tailored to train only one specific architecture and thus need not be optimal for training another architecture. Hence, select data subsets for architecture, they need to be run from scratch. However, these methods rely heavily on discrete combinatorial algorithms, which impose significant barriers against scaling them for multiple unseen architectures. Appendix C contains further details about related work.
1.1 Our contributions
Responding the above limitations, develop SURSEI.NET, trainable subset selection framework. Specifically, we make the following contributions.
Novel framework subset selection that generalizes across models. SUBSELNET is subset selector that generalizes across architectures. Given a dataset, once SUBSELNET is trained on a set of model architectures, it can quickly select small optimal training subset for any unseen (test) architecture, without any explicit training of this test model. SUBSELNET is a non-adaptive method 37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

since it learns to select the subset before the training starts for a new architecture, instead of adaptively selecting the subset during the training process. Our framework has several applications in the context
For example, Network Architecture Search (NAS) can have a signficant speed-up when the architectures during selection can be trained on the subsets provided by our method, as compared to the entire dataset. In hyperparameter selection, such as the number and the widths of layers, learning rates or scheduler-specifie hyperparameters, we can train each architecture on the corresponding data subset obtained from our method to quickly obtain the trained model for tross-validation.
of AutoMI. 35
68
30
43
61
2
24
22 3
Design of neural pipeline to eschew model training for new architecture. We initiate our investigation by writing down a combinatorial optimization problem instance that outputs a subset specifically for one given model architecture. Then, we gradually develop SUBSELNET, by building upon this setup. The key blocker in scaling up a model-specific combinatorial subset selector across different architectures is the involvement of the model parameters optimization variables along with the candidate data subset. We design the neural pipeline of SUBSELNET to circumvent this blocker specifically. This neural pipeline consists of the following three components: (1) GNN-guided architecture encoder: This converts the architecture into an embedded vector space. (2) Neural model approximator: It approximates the predictions of trained model for any given architecture. Thus, it provides the accuracy of a new (test) model per instance without explicitly training it. (3) Subset sampler: It uses the predictions from the model approximator and an instance to provide selection score of the instance. Due to the architecture encoder and the neural approximator, we do not need to explicitly train a test model for selecting the subset since the model approximator directly provides the predictions the model will make.
Transductive and Inductive SUBSELNET. Depending on the functioning of the subset sampler in the final component of our neural pipeline, we design two variants of our model.
The first variant is transductive in nature. For each new architecture, we utilize the the model approximator's predictions for replacing the model training step in the original combinatorial subset selection problem. However, the candidate subset still remains involved as an optimization variable. Thus, we still solve fresh optimization problem with respect to the selection score provided by the subset sampler every time we encounter a new architecture. However, the direct predictions from the model approximator allow us to skip explicit model training, making this strategy extremely fast in terms of memory and time.
SemndrrctiveSUBBELL.
Inductive SUBiieeee-SSSSS SUB In contrast to Sransductive-SuBSEL... to solve any optimization problem and instead models the selection scores using a neural network. Consequently, is extremely fast.
the second variant does not require
We compare our method against six state-of of-the-art methods on five real world datasets, which show that SUBSELNET provides the best trade-off between accuracy and inference time as well as accuracy and memory usage, among all the methods.
2 Preliminaries
Setting. We are given a set of training instances { W))eDD where we use D index the data. Here, æ; E dRd denotes the features, and y/s E )' denotes the labels. In our experiments, we consider ) as set of categorical labels. However, our framework can also be used for continuous labels. We use m to denote a neural architecture and represent its parameterization as ma. We also use M to denote the set of neural architectures. Given an architecture E M. Gm (Vm. Em) provides the graph representation of m, where the nodes u E Vm represent the operations and the = (ums Um) indicates an edge, where the output given by the operation represented by the node um is fed to one of the operands of the operation given by the node um- Finally, we use H(-) to denote the entropy of probability distribution and ((m((x), y) the cross entropy loss hereafter.
2.1 Combinatorial subset selection for efficient learning
Given a dataset ((.,, y4) J.ee and model architecture m E .M with its neural parameterization ma. the goal of subset selection algorithm is to select a small subset of instances S with |S| = << [ such that training ma on the subset S gives nearly the same accuracy as training on the entire dataset
D. Existing works (20 47 [9] adopt different strategies to achieve this goal, but all of them aim to simultancously optimize for the model parameters 0 as well as the candidate subset S. At the outset,

---

M
BES
98
Or W
UPDATE,
pee
Attention Layer
LayerNorm
ReLU
FFw
m..
t or me
GNN
S
INTTNODE, EDGEEMBED,
poe
LayerNomn
93
(a) Overview
GNN
(b) Neural architecture of different components
Figure 1: Illustration of SUBSEL NET. (a) Overview: Given model architecture E M, SUB- SEI.ET takes graph G. as input to the architecture encoder GNN, to compute the architecture embedding. This, together with æ is fed into the model approximator gø which predicts the output of the trained model mg. (æ). Then this is fed as input to the subset sampler т to obtain the training subset S. (b) Neural architecture of different components: GNN, consists of recursive message passing layer. The model approximator g3 performs BFS ordering on the emebddings Hm = {ha} and feeds them into transformer. Subset sampler optimizes for π either via direct optimization for (Transductive) or via a neural network Ty (Inductive).
we may consider the following optimization problem.
minimize D: =b
Σ {(mo (a;;) ((mo(az)) v.) DIVERSITY((2, | S)),
(1)
where b is the budget, DIVERSITY( / 5}} measures the representativeness of S with respect to the whole dataset D and À is regularizing coefficient. One can use submodular functions [7 like Facility Location, Graph Cut, or -og-Determinant model DIVERSITY (fz; | E S)). Here, trades off between training loss and diversity.
Bottlenecks of the combinatorial optimization (.. For every new architecture m, needs to solve a fresh version of the optimization ①1 problem from scratch to find S. Therefore, this is not generalizable across architectures. Moreover, the involvement of both combinatorial and continuous optimization variables, prevents the underlying solver from scaling across multiple architectures.
We address these challenges by designing neural surrogate of the objective (T) which would lead to the generalization subset selection across different architectures.
3 Overview of SUBSELNET
Here, we give outline of our proposed model SUBSELNET that leads substituting the optimiza- tion (1] with its neural surrogate, which would enable us to compute the optimal subset for an unseen model, once trained on of model architectures.
3.1 Components
At the outset, SUBSELNET consists of three key components: (i) the architecture encoder, (ii) the neural approximator of the trained model, and (iii) the subset sampler. Figure | iillustrates our model.
GNN-guided encoder for neural architectures. Generalizing any task across the different archi- tectures requires the architectures to be embedded in vector space. Since a neural architecture is essentially graph between multiple operations, this goal. Given a model architecture m E .M, we first feed the underlying DAG Gm, into a GNN (GNN,) with parameters a, which outputs the node representations for Gm, i.e., Hm = (hu)nev;
use graph neural network (GNN) [59] to achieve
Approximator of the trained model mg- To tackle lack of generalizability design neural model approximator gø which approximates the predictions of any trained model for any given architecture m. To this end, g3 takes input as Hm and the instance I; and compute go Hm: x,) mg- (æx). Here, 8" is the set of learned parameters of the model my dataset D.
the optimization (T.
Subset sampler. We design a subset sampler using probabilistic model (rz()). Given a budget b, it sequentially draws instances S (s1,..., } from softmax distribution of the logit vector E R [2] where πt (Z;, yi) indicates score for the element (z,, y:). We would like to highlight that we use S as an ordered set of elements, selected in a sequential manner. However, such an order does not affect the trained model, which is inherently invariant of permutations of the training data; it only affects the choice of S. Now, depending on how we compute и during test, we have two variants of SUBSELNET: Sirerductive-SuSSELLL. and Inductive-Sure SEL.N..

---

Transductive-SUBSENNEE During test, since we have already trained the architecture encoder GNN, and the model approximator g3, we do not have to perform any training when we select subset for an unseen architecture m', since the trained model can then be replaced with g Hm', 2;). Thus, the key bottleneck of solving the combinatorial optimization [ training the model simulta- neously with exploring for S- is ameliorated. Now, we can perform optimization over x, each time for a new architecture. However, since no model training is involved, such explicit optimization is fast enough and memory efficient. Due to explicit optimization every time for an unseen architecture, this approach is transductive in nature.
Inductive-SuBSELL SUBTELNET: Here, we introduce neural network to approximate x, which is trained together with GNN and g3. This allows us to directly select the subset S without explicitly optimizing for n, unlike Transuctive-SUBSELNN..
3.2 Training and inference
Training objective. Using the approximation g3(H 2..) Rd mg. (æ;),, we replace the combinatorial optimization problem in Eq. ① with a continuous optimization problem, across different model architectures m .M. To that goal, we define
(S; m; H, ga, GNN.) = Eies (g x.), vi) - AH a (+)) with, Hm = (N (2) and seek to solve the following problem:
min Σ 37,0,
E S-PTT
A(S;m 93. GNN.) Σ (KL (Hm, 2.), (H,; ma- (ax;))
MEM
SES
Here, we use entropy on the subset sampler (Pr, ()) to model the diversity of samples in the selected subset. We call our neural pipeline, which consists of architecture encoder GNN the model approximator gs, and the subset selector тT, SUBSELNET. In the above, penalizes the difference between the output of the model approximator and the prediction made by the trained model, which allows us to generalize the training of different models m E M through the model ga (H, D.).
4 Design of SUBSELNET
Bottlenecks of end-to-end training and proposed multi-stage approach. End-to-end optimization of the above problem is difficult for the following reasons. (i) Our architecture representation Hn, only represents the architectures and thus should be independent of the parameters of the architecture 0 and the instances End-to-end training can make them sensitive to these quantities. (ii) To enable the model approximator da accurately fit the output of the trained model ma, we need explicit training for 3 with the target mg.
In our multi-stage training method, we first train the architecture encoder GNN then the model approximator d3 and then train subset sampler Pr, (resp. Pr,,.) for the transductive (inductive) model. In the following, we describe the design and training of these components in details.
4.1 Design of architecture encoder using graph neural network
Architectures can be represented as directed acyclic graphs with forward message passing. Dur- ing forward computation, at any layer for node v. the output a(v) can be represented as a(v) = Act (Euetante(e)) (a(())))) with the root output as the input. Here, Act is the activation function and Op, are operation on node of the network. Given a GNN has a similar computation process, the cermutation-equivarinn node representations generated are good representations of the operations within the architecture. This allows further coupling with mansformer-basee architectures since they are universal approximators of permutation equivariant functions [63]
Neural parameterization. Given model m E M, we compute the representations Hn, (h,]u E V., by using a graph neural network GNN parameterized with a, following the proposal Vm using the ooe-hot encoding of the associated operation (e.g., max, sum) and then feeding it into a neural network to compute an initial node representation (0, INITNODE,, (f.)) Then, we use a message-passing network, which collects signals from the neighborhood of different nodes and recursively computes the node representations
of Yan et al. [59]. We first compute the feature vector fa for each node
[59] 58 12]. Given maximum number of recursive layers K and the node

---

u, we compute the node embeddings Hm = (2ule E Vm by gathering information from the k < K hops using K recursive layers as follows.
h (u, [k] EDGEEMB. ho [A]),, h. [k: + +1] UPDATE, [ DueNDr(u) (u.,)) [k]]
Here, Nbr(u) is the set of neighbors of EDGEEMB is injective mappings, as used in [88 Note that trainable parameters from EDGEEMB and UPDATE are decoupled. They are represented as the set of parameters Finally, obtain our node representations as h. = [ [0] h,(k - 1]].
Parameter estimation. We perform unsupervised training of GNN, using a variational graph autoencoder (VGAE). This ensures that the architecture representations H,, remain insensitive to the model parameters. We build the encoder and decoder our GVAE by following existing works on graph VAEs [59] 46). Given graph Gm, the encoder (m Gm)) ), which takes the node embeddings (huJuev,, and maps into the latent space Z.. = {Zuhve V..." Specifically, we model the encoder q(2m Gm) as: gzz, Gm) = (u(w)), I(h,)) Here, both ju and Σ are neural networks. Given a latent representation Zm = { uev... V.,, the decoder models a generative distribution of the graph Gmm where the presence of an edge is modeled as Bernoulli distribution BERNOULLI(((2,) =,)). Thus, we model the decoder as p(Gm 2)
[ (z ze) [I - (2 z,)]. Here, is parameterized sigmoid function. Finally, we estimate a, ut, Σ. and a by maximizing the evidence lower bound (ELBO): ma E,o Bz GGm Ipt(G 2)] (L(g( (m))lpp()))
4.2 Design of model approximator
Neural parameterization. Having computed the architecture representation Hm = (h. E Vn next design the model approximator, which leverages these embeddings to predict the output of the trained model mæ- (æt). To this aim, we developed a model approximator gs parameterized by 3 that takes H, and æ; as input and attempts to predict mg- (x;),, i.e., go ( xx,) z ma- (I;). consists of three steps. In the first step, we generate an order on the nodes. Next, we feed the representations {h., } in this order into self-attention-bas based transformer layer. Finally, combine the output of the transformer and x; using a feedforward network to approximate the model output.
Node ordering using BFS order. We first sort the nodes using breadth-first-eene first-search (BFS) order p. Similar to You al. 62, this sorting method produces a sequence of nodes and captures subtleties like skip connections in the network structure Gm
Attention layer. Given the BFS order P. pass the representations H., (hn Iu E Vin } in the sequence through self-attention-bert based transformer network. Here, the Query, Key, and Value functions are realized by linear networks on h.. We compute attention- vector Su
Att.- = W Σn On,, Value(h)))))) with, au,e SOFTMAX, (Query(h...) (0nery(h.)"KKyy(a.))///
(5)
Here i is the dimension of the latent space, and the softmax operation is over the node v. Subsequently, for each node u, we operations to obtain an intermediate representation Ç.. for each node u. We present additional details in Appendix D Finally, we feed Ç. for the last node u in the sequence p. i.e., u p(IV..) |), along with the feature c;; into a feedforward network parameterized by WP to model the prediction mg- (x:)). Thus, the final output of go H x;) is
feedforward network, preceded and sueceeded by layer normalization
Om, 2e; FFW, (Sap:SSS(i (So(V...)) xz)
(6)
Here, W. parameters of Query, Key and Value and layer normalizations form B.
Parameter estimation. We train our model approximator ge by minimizing the KL-Divergence between the approximated prediction go (m,, 2:)) and the ground truth prediction ma- (a::). where both these quantities are probabilities across different classes. The training problem is as follows:
minimizo, ΣiED.mEM KL (x; )))gg xz))
Generalization across architectures but not instances. Note that the goal of the model approximator is to predict the output on æ in the training set Dr for unseen architecture m' so that using these predictions, our method can select the subset S from D,r in a way that vn' trained on S shows high accuracy on Dres- Since the underlying subset S has to be chosen from the training set D,, for an arbitrary architecture m', it is enough for the model approximator to mimic the model output only on the training set Dr- it need not have to perform well in the test set Dres.
5

---

4.3 Subset sampler and design of transductive and inductive SUBSELNET
Subset sampler. We draw S. an ordered set of elements, using и as follows. Having chosen the first t instances St = {si. from D with S. = 0, it draws the (t 1)-th element (x, y) from the remaining instances in D with probability proportional exp( (TT((( az, y)) and then repeat for b
times. Thus, the probability of selecting the ordered set of elements 5 ( .......)]] is given by
exp(IT(Xs111 :eet))
Pr ( = II
(8)
1=0 Σ., L.,EDrS, exp(T(xeer) Vs-))
The optimization suggests that once GNN and 93 are trained, we can use them to approximate the output of the trained model mg- for an unseen architecture m' and use compute т. Thus, this already removes significant overhead of model training and facilitates fast computation of æ, and further leads us to develop can compute π, described at the end of Section 3.1
and Inductive-SUBSELNN based on how we
Soreduuctive-SSSEELNLEE The first variant of the model is transductive in terms of the computation of т. Once we train the architecture encoder and the model approximator, we compute и by solving the optimization problem explicitly with respect to π every time when we wish select a data subset for new architecture. Given trained model GNN&, 99 and a new architecture m' E M, we solve the optimization problem to find the subset sampler Pr, during inference time for new architecture mn' min, EsePr= A
93. : GNNa)
Such optimization still consumes time during inference. However, is still significantly faster than the combinatorial methods [20] 37 47 thanks to sidestepping the explicit model training using a model approximator.
Inductive-SusSEL.NV In contrast to the transductive model, the inductive model does not require explicit optimization of in the face of new architecture. To that aim, approximate using neural network T. which takes two signals as inputs the dataset D and the outputs of the model approximator for different instances { (Hm: 2x. | D} and finally outputs score for each instance Tp (mi, V:). Here, the training of Tे follows from the optimization 33
miny ΣmEM Es-Pt., A(S; m; 9z. G
(10)
Such an inductive model can select an optimal distribution of the subset that should be used to efficiently train any model mg, without explicitly training & or searching for the underlying subset.
Architecture of Th for Inductive-SURSEENNE. We approximate using Te using neural network which takes three inputs (ac,, yy ), the corresponding output of the model approximator, ie.. Om,æ, go (G.)), 22y) from Eq. 6 and the node representation matrix Hm, and provides us a positive selection score T. H Fj Uj: Om..ay). In practice, T. is three-layer feed-forwart network containing Leaky-Rel.J activation functions for the first two layers and sigmoid activation at the last layer.
4.4 Training and inference routines
Algorithm 1 Training Pipeline
Training. The training phase for both trans- ductive and inductive variants, first utilizes the TRAINPIPELINE(AII)) (Algorrthh IT) routine to train
function TRAINPIPELINE (0*)) â + TRAINGNN(M))
2:
3:
for m E MM do
the GNN (TRAINGNN), re-order the embed- dings based on BFS ordering (BFS), train the model approximator (TRAINAPPROX). to obtain 2) routine doesn't require any further training, while the TRAININDUCTIVEAAggoriin (3) routine uses the TRAINPI to train v for computing
4:
H + GNGNN (m), pos BFS(Gm; Hm) 3 - TRAINAPPROX (., ( pos, {0")
5:
6: return à 3, H.
3. BRAINTRANSDDUCTIVVAAAAgooo
Algorithm 2 Transductive Procedure
1: function TRAINTRANSDUCHIVE(... (0"))
Inference. Given a new architecture m', our goal is to select subset S. with [S] = b which would facilitate efficient training of m'. Given trained SUBSELNET, we compute Hn 2: o"+min, EseP, (o) m²; m, GNNa)
2: 6,3, Hm, <TRRAINPPPELINE {0*))
1: function D
3: S"~
~ Pr
GNN, (Gmz). compute the model approximator output 93 (Hm)). ). Using them compute for
4: TRAINNEW

---

Fransductive-SuSSELNY by explicitly solving the optimization problem stated in Eq. and draw S ~ Pr For the inductive variant, we draw S mr where & is the learned value of v..
Algorithm 3 Inductive Procedure
1: function TRAININDUCTIVE(D M. (0*})
2: á, B. Hm < (TRAINPPPHLINE ()*)
3:
o <- [g3( k.
Given unseen architecture m' and trained pa- rameters of SUBSELNET, i.e., à, B and vi, the IN- DERTTAANSDUCTIVEAAgorito
4:
J + TRAINPI {Hm (2:))
1:
function INFERINDUCTIVE(D. &, v. m')
routine solves
2: Compute Ta(H
(H me 3i, Vi, Omn mx Vi
the optimization problem on π explicitly to com-
3:
S" ~ Prog
pute x, where A(-) is defined in Eq. 2
4: TRAINNEW (ODEL
INFERINDUCTIVE (Algorithm utilizes & ie.. trained parameters from the subset sampler to compute Ti- Then the subset S" is drawn from πt or uy and is used to train m' using TRAINNEW- MODEL.
5 Experiments
In this section, provide comprehensive evaluation of SUBSELNET against several strong baselines on five real world datasets. In Appendix [E] we present additional results. Our code is in https //gi wttpb///oo//sttttllaaaaniaa swwpg//uubbeeeeeeeeeeeee
5.1 Experimental setup
Datasets. We use FMNIST (6 CIFARIO 266.. CIFARI00 25
Tiny-mmagenet-200 27 and C5l6ech-256 [13] (Cal-256). Cal-256 has imbalanced class distribution; the rest are balanced. We transform an input image X; to vector 2; of dimension 2048 by feeding it to a pre-trained ResNet50 v1.5 model [16] and use the output from the penultimate layer the image representation.
Model architectures and baselines. We use model architectures from NAS-Bench 101chh-011111 61 in our experiments. We compare Srundducivv-SSUBSELNNE
and Inductive- SUBSSLY against
three non-adaptive subset selection methods (i) Facility location [TT 17 where we maximize
FL(S)= = Eje D maxes x. 3j to find S, (ii) Pruning 48 and (iii) Selection-via-Prov
[ and
four adaptive subset selection methods- (iii) Glister (20). (iv) Grad-Match [19]. (v) EL2N 42 and
(vi) GraNd +2. The non-adaptive subset selectors select the subset before the training begins and
thus, never access the rest of the training set again during the training iterations. On the other hand, the adaptive subset selectors refine the choice of subset during training iterations and thus they need to access the full training set at each training iteration. Appendix contains additional details about the baselines and Appendix F contains experiments with more baselines.
Evaluation protocol. We split the model architectures M into 70% training (Mu). 10% validation (Mval and 20% test (Misst) folds. However, training model approximator requires supervision from the pre-trained models mg-. Pre-training large number of models can be expensive. Therefore, we limit the number of pre-trained models diverse set of size 250, that ensures efficient representa- tion over low-parameter and aagh-parameter regimes, and using more than this showed no visible advantage. We show the parameter statistics in Appendix D However, for the architecture encoder, we use the entire set My for GNN training. We split the dataset D into Du. D and Deest in the similar 70: 10:20 folds. We present Mr. MMal. Dur and Dial to our method and estimate ā, 3 and model). None of the baseline methods supports any generalizable learning protocol for different architectures and thus cannot leverage the training architectures during test. Given an architecture m' E MMssst we select the subset S from Dú using our subset sampler (Pr, for Transductive-SuBee SELNEN or Prw3 ; for Inductive-S SUBBLE- Similarly, all the non non-adaptive subset selectors select S C Drr using their own algorithms. Once S is selected, we train the test mod- els m' E Miess on S. We perform our experiments with different [S] = b (0.005) DJ, 0.9 D)) and compare the performance between different methods using three quantities: (1) Relative Accuracy Re- duction (RAR) computed as the drop in test accuracy on training with a chosen subset as compared to training with the entire dataset, i.c, RAR(S,
T (for Inductive-SuRSEENNG
Min Em'eMa. (1 Acc(mé 353/cccmm' D))
where Acc(m' X) denotes the test accuracy when m/ trained on the set X. Lower RAR indicates better performance. (2) Computational efficiency, i.e., the speedup achieved with respect to training with full dataset. is measured with respect to TT/T. Here, Ty is the time taken for training with full dataset; and, T' is the time taken for the entire inference task. which is the average time for selecting
7

---

FacLoc
Pruning
Incluctive-SubSelNee
Proxy
Transductive-SuuSedii
1.0
1.0
1.0
1.0
0.0
0.6
0.6
0.6
0.0
0.4
0.4
0.4
0.4
0.2
0.2
10
10
10a
10
10P
10
10a
10
10a
10
10P
10
109
Speed up (T)
Speed up (1y
Speed up (2) -
Speed up (22 -
Speed up (2y/2)
1.0
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.2
10
10"
4 (c)oor(t)dd:
memorr(()jc
momoory
memnory (C)dt
In mcmmory (O)de
(a) FMNIST
(b) CIFARIO
(c) COFARIO0
(d) TINY-IN
(e) CAL-256
Figure 2: Trade-off between RAR (lower is better) and speedup (top row) and RAR and memory
consumption GB-min (bottom row) for the non-adaptive methods Facility location 17]
Pruning [88. Selection-via-
[5] all five datasets FMNIST, CIFAR1Ó CIFARIOO, Tiny- ImageNet and Caltech-256. In all cases, we vary |S] = b E (0.005) D.9
GLISTER
GraNd
Transductive-SuhSeelie
GRAD-MATCH
EL2N
Inductive-SubSelle
1.0
1.0
1.0
0.5
0.8
0.0
0.6
0.6
0.6
0.4
0.2
0.2
0.2
10
10
10P
10
10
10
10'
10'
10'
10'
10
10'
10'
Speed up (Ty/T) -
Speed up (Ty/7) +
Speed up (7,/T) +
Speed up (7,/T) +
Speed up (7//7)
1.0
1.0
1.0
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.2
100
10P
10a
102
10
10
10
10P
10a 10
10P
10
memmory (1)d
meemory(f]dt
memnory())cc
I (e)nory(()dt
1 momoory
(a) FMNIST
(b) CIFARIO
(c) CIFAR100
(d) TINY-IN
(e) CAL-256
Figure 3: Trf between RAR (lower is better) and speedup (top row) and RAR and memory
consumption in GB- min (bottom row) for the adaptive methods Glister (20). Grad-Match [I9],
EL2N (4):: GraNd 44] on all five datasets FMNIST, CIFAR10 CIFARI00, ImageNe and
Caltech-25t 256 In all cases, we vary [S] =
DJ,
subsets across the test models m' E Miess plus the average training time of these test models on the respective selected subsets. (3) Resource efficiency in terms of the amount of memory consumed during the entire inference task, described in item (2), which is measured as fo memory(() dl where memory(t) is amount of memory consumed at timestamp f in the unit of GB-min.
5.2 Results
Comparison with baselines. Here, compare different methods in terms of the trade-off between Relative accuracy reduction RAR (lower better) and computational efficiency as well as RAR and resource efficiency. In Figures 2 and we probe the variation between these quantities by varying the size of the selected subset S b E (0.005) DJ, 0.9) DI9 for non-adaptive and adaptive baselines, respectively. We make the following observations. (1) Our methods trade-off' between accuracy vs. computational efficiency as well as accuracy vs. resource efficiency more effectively than all the methods, including the adaptive methods which refine their choice of subset as the model training progresses. (2) In FMNIST, our method achieves 10% RAR at ~4.4 times the speed-up and using 77% lesser memory than EL2N, the best baseline (Table [ tables for other datasets are in Appendix E. (3) There is no consistent winner across baselines. However, Glister and Grad-Match mostly remain among top three baselines, across different methods. In particular, they outperform others in Imageett and Cal-256, in high accuracy (low RAR) regime.

---

B 25000
B 45000
Speedup
Memory
B 30000
Transucttvee (B = 50000)
RAR
10%
20%
10%
20%
Inductive (D = NA)
GLISTER
5.64
7.85
116.36
98.51
0.9
0.9
GrudMatch
4.17
5.24
243.75
136.40
F1.2N
6.50
16.42
139.89
77.63
0.8
RAR
Inductive
28.64
69.24
22.73
8.24
0.7
Transductive
28.63
68.36
21.25
8.24
0.7
Table I: Speedup and memory (GB-min) in reaching 10% and 20% RAR on FMNIST
0.6
100
10
20
30
Speed up (Ty/T)
5o memory (t)dt
+
Figure 4:
Hybrid-SURSSENNET. In FMINST, CIFAR10 and CIFARI00, we observe that Transductive- Here, we design a hybrid version SUBSELNET offers better traded off than and evaluate it regime where the gap between of our model, called transductive and inductive SUBSELNET is significant. One of such regimes is the part of the trade-off' plot in CIFAR 100, where the speed up T 2 28.09 (Figures and 3). Here, given the budget of the subset b, we first choose B > b instances using running the explicit optimization routines in Srausducciiv-SUBSELLEET Figure 4 shows the results for B = [25K, 30K, 35K, 45K, 50K}- We observe that Hybrid-SSBSEELNET allow us to smoothly SSBtuctive-SBSSLLLN. and TrandductveeSSuRSSELNN
and the final b instances by
trade off between to effectively use resource-constrained setup with limited GPU memory, wherein the larger subset B can be selected using Inductive-SURREELNNN on CPU, and the smaller refined subset can then be selected by solving transductive variant on GPU.
by tuning B. It allows us
Ablation study. Here, we experiment with three candidates of model approximator ga (Feedfor- ward, LSTM and our proposed attention based approximator) with three different subset samplers (uncertainty based, loss based and our proposed subset sampler). Thus, we have nine differ- ent combinations of model approximator and subset selection strategies. In the uncertainty and loss based subset samplers, we take top-b instances based on the uncertainty and loss. We mea- sure uncertainty using the entropy of the predicted distribution of the target classes. We compare also evaluate
the performance in terms of the test RAR of the test architectures. Moreover, the model approximator Og alone- - without the presence of the subset sampler- - using KI. di- vergence between the gold model outputs and predicted model outputs on the training instances Dhrl Maal Di.mE.. KL (x:))las (H., z.)). Table 3 summarizes the results for 3%, 5% and 10% subsets for CIFAR10. We make the following observations: (1) The complete design of our method, i.e., Our model approximator (Transformer) Our subset sampler (SURSELNET)) performs best in terms of RAR. (2) Our neural-network for model approximator mimics the trained model output better than LSTM and Feedforward architectures.
Can model approximator substitute our subset selector pipeline? The task of the model approximator 9a is to predict accuracy for unseen architecture. Then, natural question that is possible to use the model approximator to directly predict accuracy of the unseen architecture m'. instead of using such long pipeline to select subset followed with training on S. However, as discussed in the end of Section 4.2 the model approximator 93 is required to generalize across unseen architectures but not the unseen instances, as its task is to help select the training subset. Table 3
already showed that gs closely mimics the output of the trained model for the unseen architecture m' E Mist and on training instances (KL div. column). Here, we investigate the performance of ga on the test instances and test architectures.
bii %
90%
70%
20%
RAR(our [] RAR(gs)
-0.487
-0.447
-0.277
Table 2: RAR using Is on CIFAR10
Table [ shows that the performance of ga on the test instances is significantly poorer than our method. This is intuitive as generalizing both the model space and the instance space is extremely challenging, and we also do not need it in general.
Using SUBSELNET in AutoML. AutoML-related tasks can be significantly sped-up when we replace the entire dataset with a representative subset. Here, we apply SUBSELNET to two AutoML applications: Neural Architecture Search (NAS) and Hyperparameter Optimization (HPO).
Neural Architecture Search: We apply our method on DARTS architecture space to search for an architecture using subsets. During this search process, at each iteration, the underlying network is traditionally trained on the entire dataset. In contrast, we train this underlying network on the subset returned by our method for this architecture. Following Na et al. [39], we report test misclassification

---

RAR
KL-div
Design choice gi and x
b
0.03 D
b
0.05 D
b 0.1
(does not depend on b)
Feedforward [g Uncertainty (x)
0.657
0.655
0.547
Feedforward [gg)+ Loss (ar)
0.692
0.577
0.523
0.171
Feedforward Inductive (our) (m)
0.451
0.434
0.397
LSTM [ga + Uncertainty (x))
0.566
0.465
0,438
LSTM (Ms ++ Loss (T)
0.705
0,541
0,455
0.102
LSTM (ys )+ Inductive (our) (Ir)
0.452
0,412
0.386
Altn. (our) [9/ + Uncertainty (TT)
0.794
0,746
0,679
Attn. (our) [gB + Loss (T)
0.781
0.527
0.407
0.089
Attn. (our) (ga + Inductive (our) (T)
0.429
0.310
0.260
Table 3: RAR and KL-divergence for different ga + ग on CIFARIO for 3%, 5% and 10% subset sizes
b (in %)
10%
20%
40%
Method
b=
5%
b
10%
Method
Test Architectures
Full
2.78
TE
S/U
TE
S/U
200
300
400
Full
2.48 1
2.48
1
Full
7111
7111
7111
Random
3.02
2.88
2.96
Random
5.4
16.66
3.72
11.29
GLISTER
3419
3419
3419
Proxy (3
2.92
2.87
2,88
AUTOMATA
5.26
0.51
3.39
0.20
GRAD-MATCH
2909
2909
2909
Our
2.82
2.76
2.68
Our
4.11
16.11 2.70
10.96
Our
1844
1635
1496
Table 4: Test Error (%) archi-
Table 5: Test Error (%) (TH) and
Table 6: Amortization cost (sec-
tecture given by NAS on CIFARIO
Speed-up (S/U) for the hyperparame-
onds) after querying test architec- tures on CIFARIO
ters selected by HPO CIFARIO
error of the architecture which is selected by the corresponding subset selector guided NAS methods, Le., our method (transductive), random subset selection (averaged over runs) and proxy-data [39].
Table|]shows that our method performs better than the baselines.
Hyperparameter Optimization: Finding the best set of hyperparameters from their search space for a model computationally intensive. We look at speeding-up the tuning process by searching the hyperparameters while training the model on small representative subset S instead of D. Following Killamsetty al. 222] we consider optimizer and scheduler specific hyperparameters and report average test misclassification error across the models trained on optimal hyperparameter choice returned by our method (transductive), random subset selection (averaged over runs) and AUTOMATA (22). Table [3 shows that we are outperforming the baselines in terms of accuracy- speedup tradeoff. Appendix contains more details about the implementation.
Amortization Analysis. and show that our method is substantially faster than the baselines during inference, once we have our neural pipeline trained. Such inference time speedup is the focus of many other applications, E.g., complex models like LLMs are difficult and computationally intensive, but their inference is fast for several queries once trained. However, we recognize that there is a computational overhead in training our model, arising due to the pre-training of the models ma- used for supervision. Since the prior training is only a one-time overhead, the overall cost is amortized by querying multiple architectures for their subsets. We measure amortized cost Twest MMouall (time in seconds), where Tows is the total time used from beginning of the pipeline to end of reporting final accuracy on the test architectures and Mivial is the total number of training and test architectures. Table shows the results for 10% subset on the top baselines for CIFAR16 10, which shows that the training overhead of our method (transductive) quickly diminishes with number of test architectures.
6 Conclusion
In this work, we develop SUBSELNET, subset selection framework, which can be trained on set of model architectures, to able to predict suitable training subset before training a model, for an unseen architecture. To do so, we first design neural architecture encoder and model approximator, which predicts the output of new candidate architecture without explicitly training it. We use that output to design transductive and inductive variants of our model.
Limitations. The SUBSELNET pipeline offers quick inference-time subset selection but a key limitation of our method is that it entails pre- me--raining overhead, although its overhead vanishes as we query more architectures. Such expensive training can be reduced by efficient training methods [65]. In future, it would be interesting to incorporate signals from different epochs with a sequence encoder train a subset selector. Apart from this, our work does not assume the distribution shift of architectures from training to test. If the architectures vary significantly from training to test, then there is significant room for performance improvement.
10

---

Acknowledgements. Abir De acknowledges the Google Research gift funding.
References
[1] Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architectures using reinforcement learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France. April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https:://ppenreviine .et.f/oorrmmm/ds11cceeeeee
[2] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Proceedings of the 24th International Conference Neural Infor- mation Processing Systems, NIPS' 1 1, page 2546-2555555 2554, Red Hook, NY, USA, 2011. Curran Associates Inc. ISBN 9781618395993.
[3] James Bergstra, Daniel Yamins, and David Cox. Making science of model search: Hyperpa- rameter optimization in hundreds of dimensions for vision architectures. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learming Research, pages 115-123, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL httpppss/pprooeedddnneeeeeee mmr.nngssmrrrr......m..m.....mm. mlr press/ /v28/ bergstrai3. html
[4] Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail. Near-optimal coresets for least-squares regression. IEEE transactions on information theory, 59(10):680-6892, 2013.
[5] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning, arXiv preprint arXiv:1906. 1 1829, 2019.
[6] Abir De, Paramita Koley, Niloy Ganguly, and Manuel Gomez-Rodriguez. Regression under human assistance. AAAI, 2020.
[7] Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez-Rodriguez. Classification under human assistance. AAAI, 2021.
[8] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248-255, 2009. doi: 10. 11..0//VRR.20095520684..
[9] Xuanyi Dong and Yi Yang. architecture search, 2020.
Nas-bench-201: Extending the scope of reproducible neural
[10] Dan Feldman. Core-sets: Updated survey. In Sampling Techniques for Supervised or Unsuper- vised Tasks, pages 23-44. Springer, 2020.
[11] Satoru Fujishige. Submodular fanctions and optimization. Elsevier, 2005.
[12] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning. pages 1263-1272. PMLR, 2017.
[13] Gregory Griffin, Alex Holub, and Pietro Perona, Caltech-256 object category dataset. 2007.
[14] Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. In Database and Expert Systems Applications: Conference, DEXA 2022, Vienna, Austria, August 24-24, 2022, Proceedings, Part I, pages 181-195. Springer, 2022.
33rd International
[15] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering, In Proceedings of the shirty-sixth annual ACM symposium on Theory of computing, pages 29 291-300, 2004.
[16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CoRR, https//52..3338.3 2015. URL http: httt:///axxiv. org/ aaaaabas/111 03385

---

[17] Rishabh Krishnan Iyer. Submodular optimization and machine learning: Theoretical results, unifying and scalable algorithms, and applications. PhD thesis, 2015.
[18] Vishal Kaushal, Rishabh Iyer, Suraj Kothawade, Rohan Mahadev, Khoshrav Doctor, and Ganesh Ramakrishnan. Learning from less data: A unified data subset selection and active learning framework for computer vision. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1289-1299. IEEE, 2019.
[19] Krishnateja Killamsetty, Durga Sivasubramanian, Baharan Mirzasoleiman, Ganesh Ramakrish- nan, Abir De, and Rishabh Iyer. Grad match: A gradient matching based data subset selection for efficient learning. arXiv preprint arXiv:2 103.:21033.0023, 2021.
[20] Krishnateja Killamsetty, Durga Subramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: generalization based data selection framework for efficient and robust learning. AAAI, 2021.
[21] Krishnateja Killamsetty, Xujiang Zhao, Feng Chen, and Rishabh Iyer. Retrieve: Coreset selection for efficient and robust supersuper learning, Advances in Neural Information Processing Systems, 34: 1 (448--14500 2021.
[22] Krishnateja Killamsetty, Guttu Sai Abhishek, Aakriti, Alexandre V. Evfimievski, Lucian Popa, Ganesh Ramakrishnan, and Rishabh Iyer. Automata: Gradient based data subset selection for compute-efficient
tuning, 2022.
[23] Katrin Kirchhoff and Jeff Bilmes. Submodularity for data selection in machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 131-141, 2014.
[24] Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast bayesian optimization of machine learning hyperparameters on large datasets, 2017.
[25] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[26] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. In online: 2014.
[27] Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N. 2015.
[28] Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Benjamin Recht, and Ameet Talwalkar. A system for massively parallel hyperparameter tuning, 2020.
[29] Richard Liaw, Erie Liang, Robert Nishihara, Philipp Moritz, Joseph E. Gonzalez, and Ion Stoica. Tune: A research platform for distributed model selection and training, 2018.
[30] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy, Progressive neural architecture search, 2017.
htllhttts://aet wwwpeiiivoorreeeee abs/ 1712. 00559
[31] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search, 2018. URL htt.:httt///aa.tt. orgg brrg/bbs//in abs//80...... 09055..
[32] Yuzong Liu, Rishabh Iyer, Katrin Kirchhoff, and Jeff Bilmes. Svitchboard ii and fisver i: High-quality limited-complexity corpora conversational english speech. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
[33] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, 18(1):5885-500 5900,, 2017.
[34] Jovita Lukasik, David Friede, Arber Zela, Frank Hutter, and Margret Keuper. Smooth variational graph embeddings for efficient neural architecture search. In International Joint Conference on Neural Networks, IJCNN 2021, Shenchen, China, July 18-22, 2021, 2021.
12

---

[35] Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture op- timization. In S. Bengio, H. Wallach, H. Larochelle. K. Grauman, N. Cesa- resa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL httpp:://proceeednggss http:/ceeddnn...rrrp...ppppeeeee pttppppapppe//////eeeee aft.:/aaaaaaaaapaaaa
pdf
[36]
Sören Mindermann, Jan M Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, and Yarin Gal. Prioritized training points that are learnable, worth learning, and not yet learnt. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 16630-15649. PMLR, 17-23 Jul 2022. .ttml
URL htt.:ittts//proceedigg..... .mlr ppress/v1622mmmderrrar
[37] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In Proc. ICML, 2020.
[38] Christopher Morris, Martin Ritzert, Matthias Fey, William L.. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium Educational Advances in Artificial Intelligence, AAAI 19/EAAI 19, doi: 10. 160966600......aa.a (0099/aai.v333011.330044000
AAAI Press, 2019. ISBN 978-1-57735-809.
URL
https://doi. org 10. 1609 aaai v33101. 3301440033344
[39] Byunggook Na, Jisoo Mok, Hyeokjun Choe, and Sungroh Yoon. Accelerating neural architecture search via proxy data. CoRR, abs/2106.04784, 2021. URL http:/tttt::/arxi..rrr wrgg/bs/210/555
04784
[40] Xuefei Ning. Changeheng Tang, Wenshuo Li, Songyi Yang. Tianchen Zhao, Niansong Zhang, Tianyi Lu, Shuang Liang, Huazhong Yang, and Yu Wang, Awnas: A modularized and extensible nas framework, 2020.
[41] Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters, 2019. URL httpttttss///ai....../ wwwooogggboo.ooo....
www./aa////////.eo..oo//gee abt/a/ass//11// 1905. 095500
[42] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 22220996220077, 2021.
[43] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4095-4104, PMLR. 10-15 Jul 2018. /RLphtps://prrocediin
mlr. wwwppppwsssspeppppppppppppp..eee hwtp:/0hhaamma. haml
[44] Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoe Le, and Alex Kurakin. Large-scale evolution of image classifiers, 2017. URL iattps://ate http//axxvvvg.///eee///// http//bb//1000 01041
[45] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc Le. eeguuaa for image classifier architecture search, 2018.
[46] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. CoRR, abs/1802.034800, 2018. UtL.http://arxiv..o /bs// 1802.03480
[47] Durga Sivasubramanian, Rishabh K. Iyer, Ganesh Ramakrishnan, and Abir De. Training data subset selection for regression with controlled generalization error. In ICML, 2021.
[48] Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S Morcos. Be- yond neural scaling laws: beating power law scaling via data pruning. arXiv preprint arXiv:220.. 14486, 2022.
13

---

[49] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe V. Le. Mnasnet: Platform-aware neural architecture search for mobile. 2018, doi: 10448555/ARXX..887..
URL. hnttps://arxiv. wwwp/rgg///aa..eeeeeeeeeeeee/a/o /807. 11626
[50] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprini 1r1iv:/812.05//88 2018.
[51] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Fast suati-stage submodular maximization. In International conference on machine learning, pages 1494-1502. PMLR, 2014.
[52] Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes. Submodular subset selection for large-scale speech training data. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3311-3315. IEEE, 2014.
[53] Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Unsupervised submodular subset selection for speech data. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4 4107-4111. IEEE, 2014.
[54] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pages 1954-1963, 2015.
[55] Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. study on encodings for neural architecture search. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20309-20319. Curran Associates, Inc., 2020. https:///:// www.rcceedinss.uuriiiss..s.... cc/ cc/pappr/2020/ file/ //t/:///668222301110000000222212
pdf
[56] Han Xiao, Kashif Rasul, and Roland Vollgraf. cahhion-mnist. a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 178hv:1708.07747 2017.
[57] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2018. URL
[58] Keyulu Xu, Weihua Hu, Jure Leskovec and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0082. 2018
[59] Shen Yan, Yu Zheng, Wei Ao. Xiao Zeng, and Mi Zhang. Does unsupervised architecture representation learning help neural architecture search? In NeurIPS, 2020.
[60] Shen Yan, Kaiqiang Song, Fei Liu, and Mi Zhang. Cate: Computation neural architecture encoding with transformers. In ICML, 2021.
[61] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NAS-bench-101: Towards reproducible neural architecture search. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7105-7114, PMLR, 09-15 Jun 2019. URL htttt:::/ppocceediii
mlr www.spres///e..o ppress/v7//ee v97 v97/yingg9a. html
[62] Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: A deep generative model for graphs. CoRR, abs/1802.08771 2018. URL http:ttt////ii..../ org/ 0ba/1802.08773
[63] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are transformers universal approximators of -eguueecett--seueenee functions?, 2020.
[64] Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae; A variational autoencoder for directed acyclic graphs. pages 1586-1598, 2019.
[65] Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Curriculum learning by optimizing learn- ing dynamics. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Pro- ceedings of Machine Learning Research, pages 433-441. PMLR, 13-15 Apr 2021. URL attps://proceedingg mlr wwwpppeesssaeee wttpe///130/hohhoa// html
14

---

[66] Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Curriculum learning by optimizing learning dynamics. In International Conference on Artificial Intelligence and Statistics, pages 433 441. PMLR, 2021.
[67] Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning, 2016. URL
01578
[68] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition, 2017. URL httpttt//axxii..oot www.g//////aa/aae aa//a/b////// /107
07012
15

---

Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks ( (Appendix)
A Limitations
While our work outperforms several existing subset selection methods, it suffers from three key limitations,
(I) We acknowledge that there indeed is a computation time for pre-training the model approximator. However, as mentioned in amortization analysis in Section 5.2 the one-time overhead is offset quickly by the speed and effectiveness of the following selection pipeline for the subset selection of unseen architectures. Since the prior training is only one-time overhead, the overall cost is amortized by the number of unseen architectures during inference time training. In practice, when used to predict the subset for a large number of unseen architectures, the effect of training overhead
quickly vanishes. As demonstrated by our experiments (Figures 2 and 3] Table (6), once the pipeline of all the neural networks is set up, the selection procedure is remarkably fast and can be easily adapted for use with unseen architectures.
To give analogy, premier search engines invest lot of resources in making fast inferences rather than training. They build complex models that are difficult and computationally intensive, but their inference is fast for several queries once trained. Thus, the cost is amortized by the large number of queries. Another example is locality-sensitive hashing. Researchers design trainable models for LSH whose purpose is make fast predictions. Training LSH models take lot of time, but again this cost amortized by the number of unseen queries.
Finally, we would like to highlight many efficient model training methods without complete training (running a few epochs via curriculum learning [66]), which one can easily explore and plug with our method for a larger dataset like Imagenet-IK,
(2) We use the space of neural architectures which comprises only of CNNs. We did not experiment with sequence models such as RNNs or transformers. However, we believe that our work can be extended with RNNs transformer based architectures.
(3) the distribution of network architectures varies widely from training to test, then there is significant room for performance improvement. In this context, one develop domain adaptation methods for graphs to tackle different outoof-distribution architectures more effectively.
B Broader Impact
Our work can be used to provide significant compute efficiency by the trainable subset selection method we propose. It can be used to save lot of time and power, that ML model often demands. Specifically, it can be used in the following applications in the context of AutoML.
Fast tuning of hyperparameters related to optimizer/traaiingg. Consider the case where we need to tune non-network hyperparameters, such learning rate, momentum, and weight decay. Given the architecture, we can choose the subset obtained using our method to train the underlying model parameters for different hyperparameters, which then be used for coss-vvliidttion. Note that would use the same subset in this problem since the underlying model architecture is fixed, and we obtain subset for the given architecture independent of the underlying non-network hyperparameters. We have shown utility of our method in our experiments in Section 5.2
Fast tuning of model related hyperparameters. Consider the case where need to tune network- related hyperparameters, such as the number of layers, activation functions, and the width of interme- diate layers. Instead of training each instance of these models on the entire data, can train them on the subset data obtained from our method to quickly obtain the trained model, which can then be used for cross-validation.
Network architecture search. As we shown in our experiments, our method can provide speedup in network architecture search. Here, instead of training the network the entire network during
16

---

architecture exploration, we can restrict the training on a subset of data, which can provide significant speedup.
Note that, the key goal of our method is design a trainable subset selection method that generalizes across architectures. As we observed in our experiments, these methods can be useful in the above applications- however, our method is a generic framework and not tailored to any one of the above applications. Therefore, our method may need application specific modifications before directly deploying it practice. However, our method can serve as base model for the practitioner who intends to speed up for one of the above applications.
We do not foresee any negative social impact of our work.
C Additional discussion on related work
Our work is closely related representation learning for model architectures, network architecture search, data subset selection.
Representation learning for model architectures. Recent work in network representation learning use GNN based encoder-decoder to encapsulate the local structural information of a neural network into fixed-length latent space [64 40 [59 34] By employing an asynchronous message passing scheme over the directed acyclic graph (DAG), GNN-based methods model the propagation of input data over the actual network structure. Apart from encodings based solely the structure of the network, White et al. (55), Yan et al. [60] produce
conputation-wwar encodings that map architectures with similar performance the same region in the latent space. Following the work of Yan et al. [59], we use a graph isomorphism network as an encoder but instead of producing a single graph embedding, our method produces collection of node embeddings, ordered by breadth- first-search (BFS) ordering of the nodes. Our work also differs in that we do not employ network embeddings to perform downstream search strategies. Instead, architecture embeddings are used in training a novel model approximator that predicts the logits of a particular architecture, given an architecture embedding and a data embedding.
in our method. This dataset was built in the context of network architecture search (NAS). The networks discovered by NAS methods often come from an underlying search space, usually designed to constrain the search space size. Although we utilize the NAS-Bench-100 101 search space for architecture retrieval, our work is fundamentally different from NAS. In contrast the NAS methods. which search for the best possible architecture from the search space using either sampling or gradient-descen based methods [I 67 44, 45) 31 (4], our work focuses on efficient data subset selection given a dataset and an architecture, which is sampled from a search space. Our work utilizes graph representation learning on the architectures sampled from the mentioned search spaces to project an architecture under consideration utilize the model expression from the latent space as proxies for the actual model and proceed with data subset selection using the generated embedding, model proxy and given dataset.
Machine learning on architecture space. We use
One such method is use cell-based search spaces [35 68, 30 43
61 9
continuous latent space,
Data subset selection. Data subset selection is widely used in literature for efficient learning, coreset selection, human centric learning, elc. Several works cast the efficient data subset selection task as instance of submodular or approximate-submoddue Another line of work focus on selecting coresets which are expressed as the weighted combination of subset of data, approximating some characteristics, e.g., loss function, model prediction [10 37 [5]
optimization problem [99 51
53 20, 47].
4 33
Among other works, Toneva al. [50) showed coresets can be selected by omitted several instances based on the forgetting dynamics at the time of training. Na et al. [39] selects proxy data
based on entropy of the model. Coleman et al. [S] uses proxy model and then use for coreset selection. Guo et al. [14] develop a library on coreset selection.
These existing works focus on jointly optimizing the training loss, with respect to the subset of instances and the parameters of the underlying model. Among them 6 focus on distributing decisions between human and machines, whereas [47] aims for efficient learning. However, these methods adopt combinatorial approach for selecting subsets and consequently, they are not generalizable across architectures. In contrast, our work focuses on differentiable subset selection mechanism, which can generalize across architectures.
Our work is closely connected simultaneous model learning and subset selection 7 6 47
17

---

D Additional details about experimental setup
D.I Dataset
Datasets (D).
Classes
Intolareed
Train-Tost Split
Stage
Traaformations Applial
FMNIST
10
x
(0KK,1OK)
28x28x1
Normalize
CIFAR1O
10
x
(OKK,TOK)
32x32x3
Randonfor slontallipp. RandenCrop, Korsalixe
CIFAR100
100
(50K,10K)
32x3233
BandontBoriisstsFFFipp RandonCrop, Norzalize
Tin--mmggeet
(1OOK,
MandonfoortoontllPPl RandonVertiiellF1 Normaliza
(24.5K661K))
RandodBoriaaataF11pp Besizo, Normalize
Table 7: A brief description of the datasets used along with the transformations applied during training
Architectures (M). We leverage the NASBench-101 101 search space as an architecture pool. consists of 423, 624 unique architectures with the following constraints (1) number of nodes in each cell at most 7, (2) number of edges in each cell most 9, (3) barring the input and output, there are three unique operations, namely x 1 convolution, 3 x 3 convolution and 3 3 max-pool. We utilize the architectures from the search space in generating the sequence of embeddings along with sampling architectures for the training and testing of the encoder and datasets for the subset selector. As mentioned in the experimental setup, pre-training large number of models can expensive.
0.4
Mir with [MM.l 4234
Probability
Sumpled My with [Mrrl = 250
0.2
0.0
5
Parameters + x10
Figure 5: Distribution of parameters of architectures in Mir when [ul = 423k (blue), and Mr. with the sampled set of 250 architectures (orange).
Therefore, we choose diverse subset architectures from Mir of size 250 that ensures efficient representation over ow-parameter and high-parameter regimes. The distributions of true and sampled architectures are given in Figure [
Note that the pre-training can be made faster by efficient model training methods without complete training (running a few epochs via curriculum learning (66) which can be easily plugged with our method.
D.2 Implementation details about baselines
Facility Location (FL). We implemented facility location all the three datasets using the apricot IT library. The similarity matrix was computed using Euclidean distance between data points, and the objective function was maximized using the naive greedy algorithm.
Pruning. selects subset from the entire dataset based on the uncertainty of the datapoints while partial training. In our setup, we considered ResNet- 18 master model, which is trained on each dataset for epochs. Post training. the uncertainty measure is calculated based on the probabilities of each class, and the points with highest uncertainty are considered in the subset. We train the master model at a learning rate of 0.025.
Proxy. It selects a subset
Glister and Grad-Match. We implemented GLISTER 20 and Grad-Match 19 using the CORDS library. We trained the models for 50 epochs, using batch size of 20, and selected the subset after every 10 epochs. The loss minimized using SGD with learning rate of 0.01, momentum of 0.9 and weight decay with regularization constant of 5 x 10-4 We used cosine annealing for scheduling
18

---

the learning rate with Tmar of 50 epochs, and used 10% of the training data as the validation set. Details of specific hyperparameters for stated as follows.
Glister uses a greedy selection approach to minimize a bi-level objective function. In our implemen- tation, used stochastic greedy optimization with learning rate 0.01, applied the data points of each mini-batch. Online-Glliser approximates the objective function with Taylor series expansion up to an arbitrary number of terms to speed up the process; we used 15 terms in our experiments.
Grad-Match applies the orthogonal matching (OMP) pursuit algorithm to the data points of each mini-batch to match gradient of subset to the entire training/validatton set. Here, set the learning rate is set to 0.01. The regularization constant in OMP is 1.0 and the algorithm optimizes the objective function within error margin of 10-4.
This is an adaptive subset selection strategy in which the norm of the gradient of the loss function is used as score to rank a data point. The gradient scores are computed after the model has trained on the full dataset for the first few epochs. For the rest of epochs, the model trained only on the top-k data points, selected using the gradient scores. In our implementation, we let the model train on the full dataset for the first 5 epochs, and computed the gradient of the loss only with respect to the last layer fully connected layer.
GraNd.
EL2N. When the loss function used to compute the GraNd scores is the cross entropy loss, the norm of the gradient for data point can be approximated by E| pp() -yll,, where p(x) is the discrete probability distribution over the classes, computed by taking sof tmax of the logits, and y is the
one-hot encoded true label corresponding to the data point x. Similar to our implementation of GraNd,
we computed the EL,2N scores after letting the models train on the full data for the first 5 epochs.
D.3 Implementation details about our model
GNN As we utilize NASBench-101 space as the underlying set of neural architectures, each computational node in the architecture can comprise of one of five operations and the one-hot- encoded feature vector fz. Since the set is cell-based, there is an injective mapping between the neural architecture and the cell structure. We aim to produce a sequence of embeddings for the cell, which in turn corresponds to that of the architecture. For each architecture, we use the initial feature f, R2 in as five dimensional one-hot encoding for each operation. This is fed into INITNODE to obtain an 16 dimensional output. Here, INITNODE consists of 5 x 16 linear, ReLU and 16 x 16 linear layers cascaded with each other. Each of EDGEEMBED and UPDATE consists of 5 x 128 linear-Batte -ee---BathNh--Reee- a sum aggregator.
cascaded with a 128 16 linear layer. Moreover, the symmetric aggregator
We repeat this layer K times, and each iteration gathers information from k < K hops. After all the iterations, we generate an embedding for each node, and following (62 we use the BFSStree based node-ordering scheme to generate the sequence of embeddings for each network.
The GVAE-based architecture was trained for 10 epochs with the number of recursive layers K set to 5, and the Adam optimizer was used with learning rate of 10-3, The entire search space was considered as the dataset, and a batch-size of 32 was used. Post training, we call the node embeddings collectively as the architecture representation.
To train the latent space embeddings, the parameters are trained in encoder-decoder fashion using a variational autoencoder. The mean ju and variance a on the final node embeddings h, are:
p = FCN (Ihmn) and o exp (FCN (Ihm) uev..)
The decoder aims reconstruct the original cell structure (i.e the nodes and the corresponding operations), which are one-hot encoded. It is modeled using single-layer fully connected networks followed by sigmoid layer.
Model Approximator gø- The model approximator ga is essentially a single-head attention block that acts a sequence of node embeddings Hm = {hh lu E V.. The Query, Key and Value are three linear networks with parameters: Wquery- Wkey and Waltue E R 16x8 Note that the matrix We E 8x16 in Eq. (5). As described in Section 4.2, for each node u, we use a feedforward network, preceded and succeeded by layer normalization operations, which are given by the following set of
19

---

2.5
t 2.5
KL- Mi-Divergenes
2.0
(i-Divergence
2.0
1.5-
1.5
1.0-
1.0
0.5
0.5
20
40
60
80
0.0
0
20
40
60
80
Epochs
Epochs ->
(a) (a) FMNIST
(b) (b) CIFARIO
Figure 6: Kullback-Leibler divergence values (KL(mg- (xx:) go (gs(Et Hm, x.))) computed during the
training of the model encoder do over 80 epochs.
equations (where LN the denotes Layer-Normalizatioon operation):
fa. (Att, + h 71, 72),
S.. = W RELU(W, Su,1),
Su.3 LS, + S3.2773.77 74)
The fully connected network acting on Su,1 consists of matrices Wi E 1616664 and W2 E R61x16 All the trainable matrices along with the layer normalizations were implemented using the Linear and LayerNorm functions in Pytorch. The last item of the output sequence Su,3 is concatenated with the data embedding æ; and fed to another 2-layer fully-connected network with hidden dimension 256 and dropout probability of 0.3. The model approximator is trained by minimizing the KL-divergence between go m, 2.) and ma- (z.). We used an AdamW optimizer with learning rate of 10 10-3 =0 betas (0.9, 0.999) and weight decay of 0.005. We also used Cosine Annealing to decay the learning rate, and used gradient clipping with maximum norm set to 5. Figure shows the convergence of the outputs of the model approximator ga H w:;) with the outputs of the model mg- (z:.).
Neural Network Tg. The inductive model is a three-layer fully-coneected neural network with two Leaky ReLU activations and a sigmoid activation after the last layer. The input to Ty is the concatenation (H.. i Ft; y:). The hidden dimensions of the two intermediary layers are 64 and 16, and the final layer is a single neuron that outputs the score corresponding to a data point æ;- While training &h add regularization term X(E Te [H m,,is 3e ya) - -(S)) ensure that nearly |S| samples have high scores out of the entire dataset D. Both the regularization constants À (in equation 3 and are set to 0.1. We train the model weights using an Adam optimizer with a learning rate of 0.001. During training, at each iteration draw instances using Pr, and use the log-derivative trick to compute the gradient the objective. During each computation step, we use one instance of the ranked list to compute the unbiased estimate of the objective in (3).
D.4 Hyperparameter Optimization
The hyperparameter search was done over optimizer and scheduler-based hyperparameters using Ray Tune [29]. We set the possible optimizers to be SGD, Adam and RMSprop. and the possible schedulers to be CosincAnncaling and StepLR. The search space parameters are given below:
Optimizers
SGD: learning_rate (0.001, 0.1), momentum (0.7, 1.0), weight_decay
(0.01, 0.0001)
Adam: Learning_rate e (0.001, 0.1), weight_ e (0.01, 0.0001)
3. RMSprop: learning_rate (0.001, 0.1), momentum E (0.7, 1.0), briigh_ddecas
E (0.01,0.000),
Schedulers
StepI.R: step_size E [10, 200,20,20 30, 40), gamma E (0.05, 0.5)
2. CosineAnnealingL.R
We employ TPE (2) as the hyperparameter search algorithm, and ASHA
the hyperparameter scheduling algorithm. The hyperparameter search runs for 100 epochs in all cases. The random baseline is run for 5 runs, and we report the average speedup and test error.
20

---

E
Additional experiments
E.1 Comparison with additional baselines
Here, we compare the performance of SUBSELNET against two baselines. They are the two variants of our method-Bottom-b-ee and Bottom---los-ggumbel.
In Bottom-b-loss, we sort the data instances based on their predicted loss Eggs Hm, x), y) and consider those points with the bottom b values.
Bottonn-blloss-ummbel we add noise sampled from the gumbel distribution with Hgumbel = 0 and gumnell = 0.025, and sort the instances based on these noisy loss values, i.., Egga Hm, z) v) Gumbel 3gumbel = 0.025).
Figure compares the performance of the variants of SUBSELNET, Bottom-b-loss, and Bottom-b- loss+gumbel. We observe that Bottom-b-loss and Bottom-b-losstummbel do not perform that well in spite of being efficient in terms of time and memory.
Transductive--SubeelNett
Bottom-b-loss Bottom-b-loss gumbel
Induetive-SnbSSelNett
1.0
0.8
0.8
0.8
0.8
1
0.6-
0.6
0.6
0.8
0.4
0.4
0.2
0.2
0.2
10
10a
10
10
10
10
Spred up (Ty/T)
Spred up (Ty/P)
Spueel up (T)/T)
up (7)/T)
Sperdl (7//7)
1.0
1.0
0.8
0.8
0.5
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.2
10'
10a
102
10
10"
10"
10
10'
10
I momorry (1)zl
mennory(()jt
memmory (C)ll
mummoryy (A)dt
(a) FMNIST
(b) CIFARIO
(c) CIFAR100
(d) TINY-IN
(e) CAL-256
Figure 7: Comparison of Transductive-SuBSELLL and Bottom-b b-oos--uuellel.. In Bottom-b-loss, select top-b instances in terms of their predicted loss (gs Hm. x). y) computed using the model approximator. In Bottom- bortommmb-lss-tuubeell. we add
and Anductie-SUBSELLN with Bottom-b-lon
gumbel noise (0m 0.025) to the loss and sort the instances based these noisy loss values.
E.2 Comparison of performance on ImageNet
Here, compare the performance of SUBSELNET against two baselines: Selection-vias Pia-Proxy and Pruning (88) on ImageNet-IK (1.28M images) g for b E (0.05]D), DI) Figure compares
Seeeduutvvv-SSSSELVVVE and Inductive-SuSSENNET with the baselines on basis of speedup, memory and budget.
Transdnctive-SSuSSllNee
Pruning
Mnduetive-SuuSSelN
Proxy
0.8
0.8
0.8
0.6
0.6
0.6
RAR--
0.4
0.4
0.4
0.2
0.2
0.2
100
10a
10"
2x10'
3x
20
40
80
Speed up (T//T)
Jo
memory(t)dt
Budget (%)
Figure 8: Comparison of performance of the top four non-adaptive subset selectors (Transductive- SUBSELNET, Inductive-SUnSEENETT Pruning, and via-Proxy) on ImageNet-IK (
21

---

Figure g summarizes the results for three non-adaptive subset selectors in terms of the accuracy, Inductive-SUBSELNNRR and FL. We make the following ob- E.3 Analysis of compute efficiency in high accuracy regime
We analyze the compute efficiency of all the methods, given an allowance of reaching 20% and 10% of the relative accuracy reduction (RAR) (80% and 90% of the accuracy) achieved by training on the full data. We make the following observations:
1. Transductive-SUBSEENN
achieves the best speedup and consumes the least memory, followed by Inductive-SUBSEENNS
2. For CIFARI00, Tiny-lmagenet and Caltech-256, Bottom-6-loss and Bottom--blosstgunnn achieve better performance than the baselines which are able reach the desired RAR milestones (10% or 20%).
3. For CIFAR100, Tiny-Imagens Imagenet and Caltech- 256, most baselines could not achieve an accuracy of either 10% or even 20% of the RAR on full data.
PMNIST
CIFARIO
CIFAR100
Speedup
Memory
Speedup
Memory
Speedup
Memory
Method
10%
20%
10%
20%
10%
20%
10%
20%
10%
20%
10%
20%
GLISTER
5.64
7.85
98.51
116.36
1.52
2.12
515.96
365,05
0.54
1,02
1427.77
758.55
GradMarch
457.67
917.04
EL2N
6.50
16.42
77.63
139.89
1.93
4.78
413.90
170.03
GraNd
1.18
450.73
FacLoc
0.82
2.37
652.67
81.01
0.80
558.56
Pruning
3.12
4.68
559.44
19.55
3.54
5.53
221.10
139.41
1.71
452.09
Seleciionvvi--Pong
410.26
765.05
Rettom-b-loss
1.68
2.98
993.28
190.40
433.00
465.39
Bottom Bottom-d-losseteee d-losseguumbel
2.70
10.18
203.83
59.37
1.63
2.04
189.30
363.07
1.78
446.95
Inductive SUBSELNET
Lnducive-SuaSELNET
28.61
69.24
22.73
8.24
3.63
8.99
231.99
99.51
1.93
2.82
417.16
274.17
Trasductiv-SSuSS
53.67
331.45
Tiny Imagenet
Caltech: 256
Speedup
Memory
Speedup
Memory
Method
10%
20%
10%
20%
10%
20%
10%
20%
GLISTER
1:65
2.18
26705.5
22687.6 6
1.31
1.76
16904.5
13921
GradMatch
1.53
2.08
28249.9
25530.4
B1,2N
2.30
21811.1
GraNd
2.16
24822.6
FacLoe
Pruning
Selection-via-Poo
1.04
30717.2
Bottom-b-loss
2:54
15947.6
bosstm--lloss-guuneeel
15085.9
9910.12
Inductive-Sinn NET
2.00
3.54
17326.6
14505.4
2.43
3.16
9597.22
7406.23
StansducivveSLuuS.....
2.54
3.99
16281.1
12447.1
2:33
3.12
9983.88 86
7747.82
Table Time and memory in reaching 10% and 20% RAR (90% and 80% of maximum accuracy
of Full selection) in tradeoff curve in Figure 2 and 3 for all datasets. In the table. "_" denotes that under the current setup of experiments, i.c., the range of subsets considered, the method could not attain accuracy equal to less than 20% 10% of RAR. Note that Bottom-b-low and Nottom-b-llos-gumbee are variants/ablations our method.
E,4 Recommending model architecture
When dealing with a pool of architectures designed for the same task, choosing the correct architecture for the task might be daunting task since it is impractical to train all the architectures from scratch. In view of this problem, we show that training on smaller carefully chosen subsets might be beneficial for quicker alternative to choosing the correct architectures. We first extract the top 15 best performing architectures AA" having highest accuracy, when trained on full data. We mark them as "gold". Then, gather top 15 architectures A when trained the subset provided by our models. Then, we compare A and A'' using the Kendall tau rank correlation coefficient (KTTau) along with Jaccard coefficent [A A" //|/ U A*)
namely Sransductive-SusSSee
22

---

servations: (1) One of our variant outperforms FL in most of the cases in CIFARIO and CIFARI00. (2) There no consistent winner between Transductive-SuBsS and Seuetive-SuBBLLNET.. although Inductive-SUBSEE.NN outperforms both TransductvveSSURSSHNNH and FI. consistently in CIFARIO 100 terms of the Jaccard coefficient.
TranshuctiveSSuheeleett
Inductive-SuhSelle
0.5
1.0
0.8
Coellscien!
0.4
Coeffecient
Coeffecient
Juccard
Jaccart
Jarcara
0.6
0.5
0.3
300
600
1800
3000
250
500
1500
2500
250
500
1500
2500
Suhset Size
Subset Sizee
Subact Size
0.8
0.6
0.6
0.6
0.4
0.5
0.4
300
600
1800
3000
250
500
1500
2500
0.4
250
500
1500
2500
Subeet Size
Subset Size
Subeet Size
(d) (a) FMNIST
(c) (b) CIFARIO
(f) (C) CIFARIO0
Figure 9: Comparison of the three non-adaptive subset selectors (Transductive-SuBSHH AatuctiveSSURSELNVV and FL.) ranking and choosing of the top-15 architectures the ba- sis of Jaceard Coefficient and Kendall tau rank correlation coefficient (K+).
E.5 Analysis of subset overlap on different architectures
CIFARIO
CIFARI00
GLISTER
0.05
0.06
GRAD-MATCH
0.06
0.08
Our
0.08
0.08
Table 9: Jaccard coefficient for subsets chosen by dissimilar architectures
Different architectures will produce different feature representations of the underlying dataset, and they can be distributed in different manners. Thus generate subset, if the features different, we would expect subsets to change too. We experiment with extremely dissimilar architectures (top-5 ranked by distance in the latent space generated by the GNN) to observe the subset overlap occurring. Table containing Jaccard coefficient of the subsets chosen for dissimilar architectures, where we notice that the overlaps are extremely small for the top adaptive methods, well for method.
E.6 Finer analysis of the inference time
Transductive
Inductive
Subset selection
0.067
226.29
Training
70.1
70.1
70.1
Table 10: Inference time in seconds
Next, we demarcate the subset selection phase from the training phase of the test models on the selected subset during the inference time analysis. Table TO summarizes the results for top three non-adaptive subset selection methods for = 0.005| D on CIFARI00. We observe that: (1) the roughly same; (2) the selection time for Transductive-
final training times of all three methods SUbSeLNet is significantly more than Inductive-SuBSELNNN as compared the final training on the inferred subset; and, (3) the selection time of FL large- as close as 323% of the training time.
although remains extremely small
E.7 Analysis on underfitting and overfitting
Since the amount of training data is small, there is possibility of overfitting. However, the coefficient À of the entropy regularizer XH (Prx). can be increased to draw instances from the different regions
23

---

Training
Validation
Testing
Subset Size
Transductive
Inductive
Transductive
Inductive
Transdactive
Inductive
0.728
0.702
0.632
20%
0.852
0.673
0.809
0.658
0.770
0.644
40%
0,890
0.691
0.856
0.678
0.825
0.666
0.942
0.912
0.717
0.698
Table 11: Variation of accuracy with subset size of both the variants of SUBSELNET on training.
validation and test set of CIFAR10
of the feature space, which in turn can reduce the overfitting, In practice, we tuned on the validation set to control such overfitting.
We present the accuracies on (training, validation, test) folds for both Transhuctive-SusSELL and Inductive-SuBSELNEE in Table II We make the following observations:
1. From training to in most cases, the decrease in accuracy is 7%.
2. This small accuracy gap is further reduced from validation to test. Here, in most cases, the decrease in accuracy 4%.
E.8 Additional results on NAS and HPO
Searched cell for NAS. Figure I0 shows the final Normal and Reduction cells found on the DARTS search space using SUBSELNET the 40% subset of CIFARIO, which gave the lowest test error of 2.68 in the experiments.
d
CL
WILLEID
IKI
2_
KqLESE 545
Sap connec
al 365
<_
Figure 10: Normal [left] and Reduction [right] cells found by SUBSEL during Neural Architecture Search using a 40% subset of the CIFAR10 dataset.
Standard error results on NAS and HPO. Here, present the mean and standard error over the runs for the Test Error (%) on NAS and HPO, which has been presented in the main draft (Section 5.2). Moreover, found that the gain offered by We observe method offers less deviation across
our method is statistically sigmificant with p x 0.05.
Method
b= 0.1|D|
b= 0.2
6 0.1|D)
Random
3.22 + 0.171
2,88 0.167
2.96 + 0.169
Proxy data 39
2.92 : 0.168
2,87 0.167
2.88 :: 0.167
Our
2.82 = 0.166
2.76 :1 0.164
2.68 : 0.161
Table 12: Mean and standard error of Test Error (%) on architectures given by NAS on CIFAR10
Method
0.05
= D.1|
Random
5.44 +: 0.226
3.72 0.189
AUTOMATA
5.26 + 0.223
3.39 0.181
Our
4.11 +:: 0.199
2.70 +: 0.162
Table 13: Mean and standard deviation of Test Error (%) for hyperparameters selected by HPO on CIFARIO
24

---

F Pros and cons of using GNNs
We have used a GNN in our model encoder to encode the architecture representations into an embedding. We chose GNN for the task due to following reasons
1. Message passing between the nodes (which may be the input, output, any of the operations) allows us to generate embeddings that capture the contextual structural information of the node, i.e., the embedding of each node captures not only the operation for that node but also the operations preceding that node to a large extent.
To better illustrate the im- pact of the GNN, we com- pared it with baseline where we directly fed the graph structure to the model approximator using the ad- jacency matrix, in lieu of the GNN-derived node em- beddings. This alteration re-
Variations of embedding
RAR
KL-div
0.05)
0.1|D)
Feedforward (ga, A)
0.481
0.433
0.231
Feedforward (gp, H)
0.434
0.397
0.171
LSTM (ga.A)
0.471
0.436
0.224
LSTM (gp. H)
0.412
0,386
0.102
Attn. (99, A)
0.362
0.317
0.198
sulted in a notable perfor- mance decline, leading 5-6% RAR on subset size of 10% of CIFAR1O.
Attn. (gs, II)
0.310
0.260
0.089
Table 14: RAR KL.-div for different emheddings (A: Adjacency
Matrix, H: GNN embedding) in model approximator
2. It has been shown by 38 and [57 that GNNs are as powerful as the Weisfeiler-Lehman algorithm and thus give powerful representation for the graph. Thus, we obtain smooth embeddings of the nodes/edges that can effectively distill information from its neighborhood without significant compression.
3. GNNs embed model architecture into representations independent of the underlying dataset and the model parameters. This because operates on only the nodes and edges the structure of the architecture and does not use the parameter values or input data.
However, the GNN faces the following drawbacks-
GNN uses a symmetric aggregator for message passing over node neighbors to ensure that the representation of any node should be invariant to permutation of its neighbors. Such a symmetric aggregator renders a low-pass filter, as shown important high-frequency signals.
which attenuates
2. We are training one GNN using several architectures. This can lead to the insensitivity the embedding to change in the architecture. In the context of model architecture, if we change the operation of one node in the architecture (either remove, add or change the operation), then the model's output significantly change. However, the embedding of GNN may become immune to such changes, since the GNN is being trained over many architectures.
G Licensing Information
The NAS-Bench-101 dataset and DARTS Neural Architecture Search are publicly available under the Apache License. The baselines GRAD-MATCH and GLISTER, publicly available via CORDS, and the apricot library used for Facility Location, are under the MIT License.
25


Reviews:
[{"review_id": "xiScwlWqZ9", "reviewer": "Reviewer_KRgz", "summary": "This paper focuses on the Subset Selection problem for selecting the best subsets training samples with which a well-performed model can be trained. This paper focuses on the challenge that previous methods for subsets selection cannot transfer across architectures. Specifically, this paper proposes to use a transformer to predict the accuracy of a model trained on a subset of training samples and use the predicted results as the surrogate to solve the combinatorial optimization problems for the selection (Transductive). This paper also proposes inductive selection, which learns another neural to predict the result of combinatorial optimization. Further, this paper proposes to encode the neural network's architecture using GNN, which will also be fed to the predictor. \n\n__________________________________________________ Post Rebuttal _________________________________________________\n\nThe reviewer has already read the rebuttal. \n\nAll my concerns have been addressed. And the reviewer wishes that the insights discussed in the rebuttal can be accommodated in the final version of the paper. \n\nThe reviewer will maintain the original score since the overall novelty, contribution, and impact cannot reach the reviewer's bar for papers scoring 7, and a score of 6 is already positive for the paper. ", "questions": "To the best of the reviewer's knowledge, analysis over accuracy is an NP-hard problem. It remains elusive to the reviewer that transformer really has the ability to capture the mapping between neural networks and accuracy. ", "limitations": "The proposed methods rely significantly on the pertaining of the model approximation to produce the correct accuracy and largely depend on the transferability of the model approximator. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. In this manuscript, the authors present an innovative approach toward subset selection, putting forward a new framework that emphasizes efficiency and practical applicability.\n\n2. A feature of the proposed framework is its ability to generalize across various architectures. This is a step forward, as it ensures the versatility and universal applicability of the method. The framework is not only confined to a specific architectural layout, but it can adapt to and function effectively within a range of scenarios. \n\n3. Additionally, the paper is substantiated by robust experimental results that highlight the superiority of the proposed method in comparison to existing baselines. The authors provide strong empirical evidence of the efficacy of their approach, demonstrating that it not only meets the performance standards set by previous methods but often surpasses them. \n\nMinor: \nThe authors have also shown how their method can be naturally incorporated into Automated Machine Learning (AutoML) systems. This seamless integration is beneficial, as it minimizes compatibility issues that could arise when introducing a new method into an established system. AutoML stands to gain from this method as it could optimize the automated selection, deployment, and tuning of machine learning models, and the paper illustrates this potential effectively.", "weaknesses": "1. Despite the promising results presented in the manuscript, one key concern that emerges is the absence of a justification for the methods put forward. Specifically, it is not well-established whether the transformer in use is genuinely capturing the intricate mapping between models and data, or if it is merely overfitting to the training samples. Overfitting would lead to a lack of generalizability in unseen or novel data situations, which could severely limit the practical utility of the proposed method. It would greatly strengthen the paper if the authors could provide deeper insights into these theoretical underpinnings, perhaps by conducting additional analysis or testing to definitively establish the veracity of the transformer's operations.\n\n2. Another potential shortcoming that emerges from the work is the limitation inherent in the utilized dataset. The dataset, NAS-Bench-101, contains Convolutional Neural Network (CNN) models with architectures that bear high similarities. Specifically, it is not clear whether the proposed method can be extended to other network architectures, such as Residual Networks (ResNets). It would therefore be beneficial if the authors could test their method with a broader range of architectures and provide evidence to support its efficacy across such a diverse range.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful feedback. We in turn answer the questions below:\n\n> *Despite the promising results presented in the manuscript, one key concern that emerges is the absence of a justification for the methods put forward. Specifically, it is not well-established whether the transformer in use is genuinely capturing the intricate mapping between models and data, or if it is merely overfitting to the training samples. It would greatly strengthen the paper if the authors could provide deeper insights into these theoretical underpinnings, perhaps by conducting additional analysis or testing to definitively establish the veracity of the transformer's operations. [...] To the best of the reviewer's knowledge, analysis over accuracy is an NP-hard problem. It remains elusive to the reviewer that transformer really has the ability to capture the mapping between neural networks and accuracy.*\n\nWe would like to point out that the neural approximator captures the probability distribution across the classes — and does not directly predict the accuracy based on the features.  Note that the task is to choose the subset from the training set and therefore the values of gold labels are available to us. Since the labels are already given to us, they can be directly compared with the predicted outputs from the model approximator to provide the predicted accuracy. Hence, the model approximator does not aim to predict accuracy only based on the features— it simply predicts the model outputs and compares them with the gold labels. \n\nNext, we try to establish a reasoning behind using a transformer-based network along with the architecture encoder for model approximation. Given the hardness of the problem, we will leave the exact formal statement for future work. \n\nFirst note that the architectures under consideration can be represented as directed acyclic graphs, with forward message passing. During the forward computation, at any layer for node $v$, the output $a(v)$ can be represented as\n\n$$a{(v)}=H _v\\left(\\sum  _{u\\in InNbr(v)} op  _v(a(u)) \\right) \\quad \\text{with} \\ a (\\text{root}) = x----- (A)$$ \n\nHere, $op _v$ is the operation on the inputs coming into the node. E.g., $op _v$ can be simply a linear matrix multiplication and $H _v$ is the activation function at node v. \nWe are interested in $a (\\text{OutNode})$ where OutNode is the final node where the output is computed. Now, given the nature of this recursion,  a graph neural network--- which exactly operates like above--- can approximate $a  (\\text{OutNode})$ with appropriate nonlinearities.\n\nSpecifically, GNN will gather messages from $k = 1,...,K$ hop starting with with $h _0 = nodeFeature$ as follows:\n$$h  _{k+1} (v)=NN_1\\left(\\sum  _{u \\in InNbr(v)}NN _2(h   _{k+1}(u)) \\right)$$\n\nHere, $NN_1$ and $NN_2$ are neural networks. Since GNN operates exactly as the computation process (A), it makes sense to assume that $h _K(1),...,h  _K(V)$ are good representations of the operation within the architecture. They, together with the feature $x$ should be able to predict the $a (\\text{outNode})$. \n\nThus, our task is now to find nonlinearities $F$ and $G$ so that  \n\n$a(\\text{outNode}) \\approx  F( G (h _K(1), …, h _K(|V|)), x )$.\n\nNow, the set $(h _K(1), …, h _K(|V|))$ is permutation equivariant with respect to node indexing. \nAs suggested in [1], transformers are universal approximators of permutation equivariant functions. Therefore we use G as a transformer. Furthermore, we apply another neural network F on top of output of G and x to predict $a$(outNode).\n\n[1] Yun, C., Bhojanapalli, S., Rawat, A.S., Reddi, S.J., & Kumar, S. (2019). Are Transformers universal approximators of sequence-to-sequence functions? ArXiv, abs/1912.10077.\n\nWe leave the exact theory for future work.\n\n\n\n> *Another potential shortcoming that emerges from the work is the limitation inherent in the utilized dataset. The dataset, NAS-Bench-101, contains Convolutional Neural Network (CNN) models with architectures that bear high similarities. Specifically, it is not clear whether the proposed method can be extended to other network architectures, such as Residual Networks (ResNets). It would therefore be beneficial if the authors could test their method with a broader range of architectures and provide evidence to support its efficacy across such a diverse range*\n\nWe want to note that the multi-stage training approach can be easily extended to architectures beyond the NAS-Bench search space. In section 5, we have also tested the methods on the DARTS space, and observed that our method outperforms other methods in terms of speed and computation efficiency. As suggested by the reviewer, we add the final results for ResNet below,  which shows the speedup and memory to achieve 10% and 20% RAR values across different methods for the top competitive baselines and observe that we outperform them in both aspects.\n\n\n||Speedup|| Memory (Gb-min)||\n|--|:--:|--:|:-:|--:|\n| **RAR** $\\to$ |  10\\% |  20\\% |   10\\% |   20\\%\n| GLISTER| 1.54 | 2.71 | 84.41 |  40.80 |\n| GradMatch | 1.44 | 3.36 | 79.74 | 35.47 |\n| Inductive | 3.57 | 10.31 | 23.30 |  8.07 |\n| Transductive | 3.61 | 10.35 | 23.04 | 8.03 \n"}, {"review_id": "n5V3sjcmH9", "reviewer": "Reviewer_rt8F", "summary": "The paper proposes a new subset selection method, SUBSELNET, for efficient training of neural network models. SUBSELNET selects optimal subsets for a model based on its architecture with minimal overhead. SUBSELNET outperforms existing subset selection methods in terms of computational efficiency.", "questions": "Assumptions on architecture encoder: \n\nSection 4.1 describes the parameterization of operations in a neural network into node representations, and use them as features in the model approximator to approximate the prediction of a model. This implicitly assumes that the prediction of a model depends only on the structure of the network, which is likely not the case. Hyperparameters like model size, optimizer, learning rate, etc., can all affect model performance and could affect different architectures differently. It may require empirical analysis to show if using architecture alone suffices to approximate model predictions.\n\nAssumptions on using SUBSELNET in AutoML:\n\nThe idea of using adaptive subset selection in NAS, etc., is potentially problematic. The goal of NAS is to select $\\underset{m}{\\operatorname{argmin}} L$, while the proposed method selects $\\underset{m}{\\operatorname{argmin}} \\underset{S}{\\operatorname{min}} L$ which is a different optimization problem. Because the subset can adapt to each particular model, the performance on the model's most advantageous subset might not correlate well with its performance on the whole dataset. For example, it is possible that a generally worse-performing model has a good training subset. On the other hand, non-adaptive subset selection does not risk over-adaptation between subset and model and can be more safely used in NAS to approximate $\\underset{m}{\\operatorname{argmin}} L$.\n\nEvaluation:\n\nThe main results of the paper, Figure 3 and Table 1, are mostly dedicated to comparing the speed (computation time) and memory usage. Here the computation time involves multiple components (e.g., running subset selection, model training) and can be tricky to compare across methods and is implementation-dependent. Because the proposed method uses costly training, to include the amortize training time or not in the comparison could make a large difference. The authors need to be more explicit in the detailed protocol used when comparing computation time.\n\nBecause the training phase involves training many models, the cost is mostly linked to the number of models trained. Therefore, it seems necessary to verify the minimum number of models need to be trained in order to learn a good model approximator.\n\nComparison of efficient training can be evaluated in other dimensions as well, most notably with sample efficiency: would the proposed method be able to select a smaller subset to maintain certain accuracy? Sample efficiency is also a more reliable metric than computation time and allows for more objective comparison.\n\nResults in \"using SUBSELNET in AutoML\" section: why only `random` and `proxy` are evaluated in Table 4, what about other subset selection methods listed in Figure 3? Why are non-adaptive baselines not evaluated in Table 6, which could have low cost?", "limitations": "The authors adequately addressed the main limitations of the proposed method, including dependence on the training dataset and the inability of generalizing model prediction to the test set.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "New data-driven approach to subset selection: the proposed method turns subset selection into a learning problem and learns a subset selection pipeline that can generalize to new architectures. Such approach has the potential of being more universal while also more efficient at certain conditions (see below).\n\nA step towards uncovering the relationship between optimal subsets and model architecture: the proposed method in principle shows that optimal subsets can be determined from a simple representation of the model architecture, which is a quite strong hypothesis worth investigating. This line of research has the potential to better our understanding of the relationship between data and model in deep learning.\n\nEfficient subset selection adaptive to mode architecture: although with significant drawbacks (see below), the proposed method points to a promising possibility of architecture-adaptive subset selection with very little cost. \n\nApplication in NAS and hyperparameter search seem promising: from the results reported in the paper, the proposed method has the potential to significantly accelerate NAS and hyperparameter search if used properly.", "weaknesses": "Method has limited efficiency advantage because of costly training: the proposed method needs to train a large number of models in order to learn a model approximator, therefore though it is more efficient than other adaptive subset method at test time, the computation cost is considerably shifted to the training phase. As a result, the proposed method is only clearly more efficient when it is required to efficiently train a large number of models of different architectures so that cost can be amortized. This situation seems only happen when doing NAS. NAS is undeniably an important task, but otherwise the potential use of the proposed method seem limited.\n\n(minor) Another limitation of the method is that the trained model approximator does not generalize across datasets. The method needs to be retrained for each new dataset, which further limits its scope of application. The method also requires a pre-trained feature extractor suitable for the current data distribution, which may not be available for less common datasets.\n\nInsufficient analysis of the components in the proposed method: to appreciate the merits of the proposed design of approximating model prediction based on architecture, one would want to know how effective is the model approximator. For example, how effective does it generalize to unseen architectures? Also, to what extent is the subset selection dependent on architecture (how much do subsets selected for two different architectures overlap, and does the degree of overlap depend on architecture similarity)? For the GNN architecture encoder, how much does it contribute to the final performance? And what about the pre-trained feature extractor?\n\n(minor) Scope of experiment is kind of limited: experiment is mainly performed on small datasets such as CIFAR100, no experiment on larger datasets such as ImageNet where efficient training is much more meaningful.\n\nSome assumptions made in the paper are likely questionable: see the `Questions` section.\n\nPotentially incomplete evaluation protocol: see the `Questions` section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thorough reading and valuable feedback. Please find our answers below:\n\n> *how effective does model approximator generalize to unseen architectures?*\n\nAblation study (L337) in our paper provides an evaluation on model approximators. Further, the analysis from L349 and Table 2 addresses this exact question. We evaluate the model approximator $g  _{\\beta}$ alone---  without the presence of the subset sampler--- using KL divergence between the gold model outputs $m  _{\\theta^*} (x   _i)$ and predicted model outputs $g   _{\\beta}(H   _m,x   _i))$.  Here we measure $AVG  _{m \\in M  _{test}} KL(m  _{\\theta^*} (x   _i) || g  _{\\beta}(H   _m,x   _i))$. For convenience, we reproduce the numbers from table 2 for CIFAR10.\n|| KLDiv|\n|-|-|\n|FF|0.171|\n|LSTM|0.102|\n|Our|0.089|\n\nFurther, we note that the classification accuracy of the model approximator  on unseen architectures taken from NASBench-101 is 96%, and from DARTS is 94% in CIFAR10\n\n> *to what extent is subset selection dependent on architecture?*\n\nAs per the reviewer’s suggestion, we compute similarities between graphs $s(G _i,G _j)$ and the underlying subsets $|S _i\\cap S _j|$ for each pair of architectures $i,j$. We calculate the Kendall’s-tau between the list of all possible pairs of $s(G _i,G _j)$ and $|S _i\\cap S _j|$ to be 0.42 for CIFAR10 and 0.55 for CIFAR100. This shows that there is a positive correlation between the model structure and the subset chosen.  \nAdditional results in App 7 and Fig 3 in the global-pdf show that existing works, which assume subset for one model can generalize across others, are outperformed by our method.\n\n> *How much GNN contributes to the final performance*\n\nIf we replace GNN embeddings with simple architecture embeddings, we see a 5-6% increase in RAR. We have added the details in the global response (GR.4) and Table 1 of the global-pdf.\n\n> *what about the pre-trained feature extractor?*\n\n We have clarified about the extractor in the global response (GR.3)\n\n\n > *Results on large dataset*\n\nFig 2 in global-pdf and (GR.5) in the global response compares subset selection across baselines on ImageNet, which show the efficacy of our method.\n\n\n> *Hyperparameters like model size, optimizer, learning rate, etc., can all affect model performance and could affect different architectures differently*\n\nGNN encodes structure of the architecture and thus  *does incorporate model size*. Since other hyperparameters (H) are not structure related, we did not include them in the GNN. We also did not incorporate H in the model approximator as its performance as well as the final accuracy deviates by max 2-3% for different H and we noted that they mostly change the rate of convergence rather than the final accuracy for *all methods including training with full subset*. Thus, our plots (speedup/memory v RAR) remain almost the same.\n\n\n> *idea of using adaptive subset selection in NAS, etc., is potentially problematic*\n\nNote that, due to the entropy term (Eq 2), we are minimizing the loss over all representative subsets (over the full dataset). So, the optimal S is itself a representative subset which gives minimum loss. Hence, the model optimized on the subset in NAS also performs well in the full dataset. This is why we observe that this approach works well in practice.\n \n>  *(a) Computation time can be tricky to compare across methods; (b) Amortize training time or not in the comparison make a large difference; (c) the detailed protocol used when comparing computation time;*\n\n(a)  Whenever available, we used the available code of the baselines. All these baselines are specifically optimized for compute efficiency and therefore they did run in their full strength. Every experiment is on the same GPU server in exactly the same setting. During time/memory computation, we ensured that no other processes were running on the server.\n\n(b) Computation time including amortized training is analyzed in (GR.1) in the global-response which shows that our method still stays efficient.\n\n(c) As we mentioned in the paper (L306), “Computational efficiency…  $T$ is the time taken for the entire inference task, which is the average time for selecting subsets across the test models $m'\\in \\mathcal{M} _{test}$ plus the average training time of these test models on the respective selected subsets. “ Hence, this is total time = running subset selection+model training. Comparison on these two aspects separately is given in Tab 10 in the Appendix and Table 4 in the global-pdf.\n\n\n> *verify the minimum number of models need to be trained in order to learn a good model approximator.*\n\nWe trained with different numbers of models $n$ and observed that beyond $n_{min}= 100$, we are able to train a good approximator. (Please refer to Table 3 in the global-pdf).\n\n\n> *Sample efficiency is also a more reliable metric than computation time and allows for more objective comparison.*\n\nWe plot the accuracy-budget tradeoff in Fig 2 of the global-pdf for Imagenet, which shows that our method performs better than the other. Moreover, we also provide a table here which shows the value of $|S|$ required to reach 10–30% drop in max performance for ImageNet, where we notice that we are able to select a smaller subset to achieve the same RAR.\n**RAR**$\\to$|10\\%|20\\%|30\\% \n---|---|---|---\nPruning|0.86|0.80|0.62 \nRandom|0.88|0.81|0.69 \nProxy|0.83|0.74|0.56 \nOur|0.76|0.63|0.44 \n\n\n> *why only random and proxy in AutoML?*\n\nRandom and proxy are the state-of-the-art specifically for NAS. During the rebuttal period, we also experimented with our non-adaptive baselines: Pruning and Facility location. We notice that our methods still selects better architectures for NAS. We put the results in the global-pdf in Table 2\n"}, {"review_id": "sfGphdIhMD", "reviewer": "Reviewer_X3mh", "summary": "The paper presents a model agnostic method of subset selection using a graph neural network a surrogate.", "questions": "See above.\n\nBut on the whole this paper is just needs a thorough restructuring at the very least.", "limitations": "Societal Impact: Would be nice to see the effect of subset selection on fairness.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "- Problem area is an interesting space, and an area of interest to the community at present.\n- Novel application of GNN for subset selection\n- Seems to be a performance gain in some settings for SubSelNet over existing methods (but hard to tell from graphs).", "weaknesses": "- The paper not well written. I found the paper hard to parse. Structure is messy, and the paper visually feels like there's too much going on. The figures are small. The graphs and tables are hard to read. This paper would not have a much of an impact as it stands, simply because it's difficult to read.\n- Doesn't seem to a convincing narrative here on why are existing methods not model agnostic? See Selection via Proxy by Coleman et al and RHO-Loss by Mindermann et al.\n- Datasets are all small. The graphs are hard to read\n- The method seems overly complicated and some of the justifications seems slim (e.g. GNN for architecture encoder? why architecture encoder? Why \"neural approximator\"?\n\n\nMinor Comments:\n- The arrows (on RAR as other metrics) in figure 3 and table 1 are confusing. They don't indicate in the way arrows usually do (i.e. what direction is best). I don't even know why there is an arrow the table 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments.\n\n> *The paper presents a model agnostic method of subset selection using a graph neural network a surrogate.*\n\nWe believe that there is a misunderstanding. Our method is not model agnostic. Rather, it chooses a different subset for each architecture using a neural model which is trained to select optimal subsets given an architecture. This allows us to obtain a subset that is optimal, specifically for a given architecture, without any combinatorial or other expensive subset selection algorithm. \n\nThus, although it does not require to explicitly train any model or solve a combinatorial optimization problem every time, it selects a subset using a neural subset selector, which is indeed different for different architectures. \n \n> *Doesn't seem to a convincing narrative here on why are existing methods not model agnostic?\n\nIn the introduction, we mentioned that many subset selection methods that show good accuracy are required to train everytime from scratch for every new architecture. This is time consuming.\nIndeed  there are works like Selection via Proxy by Coleman et al which selects subsets efficiently, without training the model again and again. However, they perform worse in terms of accuracy with respect to those methods which attempt to select a subset each time for a new architecture. This is natural because the model specific subset selectors tailor their subset selection per each architecture. \n\nOur method attempts to effectively tradeoff between these two aspects. By training on several architectures, we aim to learn to select a subset that is optimal for a new architecture, without explicit training or expensive combinatorial computation.\n\nNote that we already compared Selection via proxy by Coleman et al (2020) in Figure 7 (Appendix E.1), which shows that our approach provides a better trade-off than their method. For convenience, we have shown the plot in Fig 3 of the global-pdf. Moreover,  we show the compute time and memory to reach 10% and 20% RAR values for FMNIST, and observe that our method outperforms others.\n\n||Speedup||Memory (Gb-min)||\n|--|:-:|-:|:-:|:-:|\n||10\\%|20\\%|10\\%|20\\%|\n|Selection by Proxy|3.65|18.09|168.20|35.27|\n|Inductive|28.64|69.24|22.73|8.24|\n|Transductive|28.63|68.36|21.25|8.24|\n\nTo further enhance the fact that the subsets to be chosen depend not only on the dataset but also on the architecture under consideration, we selected 5% subsets from 4 architectures with the lowest number of parameters and used them to train a larger architecture. We observe that this simple baseline gives RAR - (0.36, 0.39, 0.37, 0.37) whereas our method gives RAR of 0.31.\n\n> *Datasets are all small*\n\nWe want to note that Tiny-ImageNet (a 100,000 point subset of ImageNet with 200 classes), and CalTech-256 (a 30,507 point dataset with 257 classes) are challenging real-world datasets, especially for subset selection. We further conducted experiments on ImageNet and presented the results in Fig 2 and also here in the following table which shows the compute time and memory to reach 10% and 20% RAR values. We observe that we perform better than other methods.\n\n|  | Speedup |  | Memory (Gb-min) |  |\n|---|---|---|---|---|\n|**RAR** $\\to$ | 10\\% | 20\\%|10\\% | 20\\% |\n|Pruning|0.99| 1.03 | 7.31e5|6.94e5 |\n|Random|1.06 |1.21 | 6.90e5|5.69e5 |\n|Proxy|0.91| 0.99 | 8.24e5|7.19e5 |\n|Our|1.25|1.47 | 5.77e5|4.87e5 |\n\n> *The method seems overly complicated and some of the justifications seems slim (e.g. GNN for architecture encoder? why architecture encoder? Why \"neural approximator\"?*\n\nOur task is as follows: Given an architecture m and a training D, we should be able to find a subset S *without explicitly training m*, which would give optimal performance across all subsets of the same size. That means we need an algorithm A which would take input m and D and will output S, *without any explicit training of m on D*.  Thus, the goal is to find A such that $A(m,D)=S^* _m$, the optimal subset for the architecture m. \n\nIn general, such an algorithm should solve some candidate optimization problem (Eq 1 in the paper) like the following:\n\n$$\\min _{\\theta, S\\subset D: |S|=b}\\sum _{i \\in S}\\ell(m _\\theta(x _i),y _i)-\\lambda\\texttt{Diversity}(\\{x _i|i\\in S\\})$$\n\n*Why a neural approximator?:* The key bottleneck here is to train $m_\\theta(x)$ every time for a new architecture. Our work focuses on bypassing this expensive step by providing an approximation of the *trained output of $m_\\theta (x)$*, without explicit training of $m_\\theta$.  Hence, whenever we need to train $m_\\theta$, we can use the approximation directly which will replace the entire training stage. \n\nTo do so, we design a neural approximator which takes the architecture of m and the instance x as input and provides the output $m_{\\theta^*} (x)$, the prediction made on x by the trained architecture.  Whenever we require to train the model m during the subset selection procedure, we directly feed the architecture of m and x into the neural approximator and directly obtain the output $m_{\\theta^*} (x)$ — the entire process of training $m_\\theta$ is removed. \n\nOnce we have the approximation of the trained model output, we feed it into another neural network, which directly samples the subset. \n\n*Why architecture encoder?*  The neural approximator aims to make efficient generalization of predicting model output across different architectures. We note that generalizing any task across the different architectures requires the architectures to be embedded in vector space. However, directly using the graph matrices doesn’t encompass the operations or structure completely, as shown in Table 1 in the global pdf. \n\n> *The arrows in RAR*\n\nThe $\\uparrow$ in Figure 3 denotes the axis, and $\\to$ in Table 1 of the main paper denotes that **RAR** refers to 10% and 20%. We will address them in the revised version."}, {"review_id": "pfLaFtMH9H", "reviewer": "Reviewer_VPxr", "summary": "This work proposes a new method to select subsets of valuable training examples, with an emphasis on specializing the selections to new model architectures. The motivation is that selections made for one architecture may not work well when used with a different architecture (a claim that the authors did not show evidence for here). At inference time, the method takes a new network architecture, converts it to a learned embedding via a GNN, feeds it along with new inputs $x$ to a model approximator that estimates predictions from a trained model, and then optimizes over a probability vector from which we can sample a valuable subset. Rather than training the different components all at once, the authors propose separate objectives for each learned module. And intuitively, the final optimization over the probability vector (shown in eq. 1) encourages low loss among the selections, as well as high diversity.", "questions": "Several questions are mentioned in the issue above.\n\nOne of the baselines used here, EL2N, was recently shown to have a serious bug in its implementation that invalidated some of the findings. Can the authors explain the relevance of that issue to their experiments and say whether they're using a corrected implementation here?", "limitations": "The paper does not include much discussion of limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is the first method I've seen that focuses on specializing data subset selection to specific architectures, so that angle is novel. It's also challenging, but the authors manage this complexity by setting up a GNN and model approximator to efficiently estimate predictions from trained models with arbitrary architectures. The full pipeline is involves multiple steps, but the authors show how to train each module independently and the results show that it works well in practice.", "weaknesses": "- One of the main motivators for this method is the idea that data subset selection cannot generalize across architectures. I didn't see any evidence for this claim in the paper, and in fact there are other works that show the opposite conclusion: for example, the selection via proxy approach from Coleman et al (2020) relies on the generalization of valuable data from smaller to larger models. Can the authors explain their focus on this issue? And if they believe it is a serious issue, can they provide evidence of lack of transferability across models, and perhaps of very different selections in their method depending on the architecture used at inference time?\n\n- The authors provide no information about the computational cost of the pre-processing step in this method. If the goal is to perform efficient neural architecture search or hyperparameter tuning, this cost should be accounted for, and it seems to require training at least 250 models with different architectures, plus the GNN and model approximator. Ultimately, it's hard to say if this actually reduces the computational cost of training.\n\n- The terminology for \"transductive\" and \"inductive\" solutions for $\\pi$ didn't make sense to me. I wonder if there's a simpler way to refer to these methods - for example, the \"transductive\" method solves a per-instance optimization problem, and the \"inductive\" method can be viewed as an amortized optimization solution (see \"Tutorial on Amortized Optimization\" by Amos).\n\n- The main objective shown in eq. 1 didn't quite make sense to me. The first part of the objective, which focuses on the loss for the selected examples, seems like it wouldn't capture anything meaningful - many samples will be perfectly predicted and have near-zero loss, and it doesn't seem especially helpful to focus on the easiest examples that are correctly predicted. Am I missing something, or can the authors explain this potential issue?\n\n- It would seem like the diversity term in the eq. 1 objective is intended to ensure diversity in some representation space and minimize redundancy for very similar training examples. Indeed, that's what prior methods aim to accomplish with submodular set functions like facility location. So the choice to instead use the entropy over $P_\\pi$ is strange to me, because it cannot be expected to encourage this diversity. In fact, I'm not sure what it accomplishes because we're already performing sampling without replacement. Can the authors explain this choice, and explain whether it would be possible to test their method with a submodular set function here instead of the entropy term?\n\n- I'm not sure why the authors included eq. 3 given that they don't suggest training all the models end-to-end like this. It's not clear that this end-to-end objective would even result in good models for the GNN and model approximator. I wonder if the authors could skip this somewhat confusing overview objective and proceed directly to the training steps for each module.\n\n- In section 4.1 about the GNN, could the authors confirm which architectural information they encode in the input representation? It sounded like they only indicate the operation performed at each layer, but perhaps not the size of each layer. If so, that seems somewhat limiting for the GNN's ability to distinguish between different architectures.\n\n- The main text doesn't seem to explain how the authors optimize eq. 9 and eq. 10. We optimizing over $\\pi$ here (or a network that outputs $\\pi$), and this would seem to require backpropagating gradients to a large number of logits through a non-differentiable sampling process; in particular, the \"inductive\" solution seems like it could require a forward pass through all the training examples for each gradient step. Algorithms 1 and 2 provide no information, and I didn't see a pointer to an appendix section that explains this point.\n\n- The notation for the \"inductive\" model on line 235 is confusing because it doesn't show the inputs referenced in the same sentence. This is only corrected below on line 241. \n\n- The RAR metric is sensible, but it also leads to a y-axis in Figure 3 that's difficult to interpret. In particular, it's hard to tell at what point the trained models have unacceptably low accuracy due to too much speedup. Would the authors consider instead showing raw accuracy, or absolute accuracy reduction?\n\n- I wonder if the authors could include strong but simple baselines to compare to the existing ones. For example, could they include training on the full dataset for different numbers of epochs, training on a fixed random subset, or training on newly sampled subsets at each epoch? Given the focus on speedup on the x-axis rather than the number of epochs, I could see these baselines outperforming some of the existing ones, which are in some cases quite slow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for detailed feedback which would help us improve our paper.\n\n> *evidence of lack of transferability*\n \nWe provided a comparison with Selection via proxy in Fig 7 of App E.1 (also Fig 3, global-pdf), where we outperform it. Also, we select 5% subsets of CIFAR10 for 4 architectures with the lowest no. of parameters and use them to train another architecture. We observe that this simple baseline gives RAR of (0.36, 0.39, 0.37, 0.37) whereas our method gives RAR=0.31. Thus, the subset obtained from one architecture may not be the best for other architectures.  \n \n>  *cost of pre-training*\n\nGNN is trained only once, irrespective of datasets since it only captures the structure of the architecture. The model approximator indeed involves an overhead, but it is one-time and is amortized by no. of unseen architectures during inference time training. \nTo give an analogy, premier search engines invest a lot of resources in making fast inferences rather than training (e.g., LLM). They build complex models that are difficult and computationally intensive, but their inference is fast for several queries once trained. We have discussed them in detail in Limitations, App.A.\n\nWe have provided this amortization analysis in Table 6 (L387) of our main paper. Here, we show that even when we include training times into total cost, we still gain a better speedup (CIFAR10). \n  \n|# of archs for training approximator|100||||250||||\n|-|-|-|-|-|-|-|-|-|\n||Speedup||Memory (Gb-min)||Speedup||Memory (Gb-min)||\n|RAR $\\to$|10%|20%|10%|20%|10%|20%|10%|20%|\n|GLISTER|1.52|2.12|515.96|365.05|1.52|2.12|515.96|365.05|\n|GradMatch|1.69|2.20|457.67|362.47|1.69|2.20|457.67|362.47|\n|Inductive|3.18|5.23|253.40|171.10|2.94|4.41|274.08|202.91|\n|Transductive|4.25|7.21|188.03|122.97|3.65|4.97|218.94|178.39||\n\nNote that the model approximator and pre-trained models can be trained only once for a large dataset and be fine-tuned for smaller datasets. This allows us to significantly reduce total computation cost at least by a factor of 5, with nearly same performance.\n\n> *New metric: absolute accuracy reduction, Simple baselines:  fixed random subset, newly sampled subsets at each epoch*\n\nWe added new plots in Fig 1 of the global-pdf and show that SubSelNet performs better\n\n> *main objective in eq. 1*\n\nNote that the diversity term allows it to select examples from different areas of the instance space, by adding several hard examples. At the outset, one can think of the problem as $\\min\\sum  _{i \\in S}\\ell(m  _{\\theta}(x _i),y _i)$ s.t. $\\text{Diversity(S)}\\ge a$.\n\nThus, we aim to choose a representative subset $S^*$ among many subsets $S$, which gives minimum training error. As $S^*$ is a representative set, most test examples are likely to be in the regime of S. The trained model $\\hat{\\theta} (S^*)$ gives the lowest error across all other models trained across different representative subsets.  Therefore, it gives lowest loss on most test examples, since they will be fall in the regime of $S^*$.  Indeed, there are some hard examples giving bad accuracy, which, however, is significantly compensated by very high accuracy of most test examples. Explicit training over hard examples leads the model to learn unnecessary on outliers, resulting in overall accuracy drop (26% for CIFAR10). $a$ ($\\lambda$ in our original objective) controls this regularization.\n\nGeneralization of subset selection is already very challenging. As the model is trained on diverse and easy examples, the neural pipeline finds it easy to generalize this task across architectures. In contrast, selecting hard examples is already quite difficult for one architecture. This hardness gets amplified when we try to generalize these across different architectures. \n\n> *$P _\\pi$ is strange*\n\nWe tried to approximate Facility location (FL) using a neural network. For a non-sequential $Pr _\\pi$, we have: $\\sum  _{j\\in D} \\max _{i\\in S} sim _{ij} \\approx \\sum _{j\\in D} \\log(\\sum  _{i\\in D}  e^{sim  _{ij}} Pr _\\pi (i) ) $. We faced several difficulties here. (1) We need to pass all examples twice, so it can be computationally expensive $O(|D|^2)$.  As $|S|>1$, $\\sum _{i} Pr _{\\pi} (i) > 1$ – we cannot relax it with Jensen inequality. (2) The sequential extension when sampling of one instance will affect subsequent sampling is very non-trivial to incorporate here. (3) $sim _{ij}$ is computed in some latent feature space that requires architecture embeddings, model approximator, etc. and thus it demands another neural network on top of all current networks, which would further complicate the training.\n\n\nHence, we choose to increase entropy of $P _{\\pi}$ at each selection step. This leads the softmax probability distribution (Eq 8) across candidate instances to be close to uniform at each step. This will allow us to choose samples uniformly from different regimes. This will lead to choosing a representative subset although we agree that it would not encourage minimum redundancy.  We saw that in practice this works very well, and also allows for log-derivative tricks to perform efficient sampling.\n\n> *What does GNN encode*\n\nThe entire neural architecture is fed to GNN including all layer (thus including model size), structural and operation information.\n\n> *optimize eq. 9 and eq. 10 over $\\pi$*\n\nWe use log derivative trick to compute $\\nabla _{\\psi} \\mathbb{E}  _{S\\sim P  _{\\pi _\\psi}}[ \\Lambda (S,\\psi) ] = \\mathbb{E}   _{S\\sim P  _{\\pi _\\psi}}[ \\nabla  _{\\psi}\\log P  _{\\pi _\\psi} (S)\\Lambda(S,\\psi)+ \\nabla _ {\\psi} \\Lambda(S,\\psi) ]$. This would allow us to (1) compute  gradient for backpropagation and (2) distribute product of softmax probabilities (Eq 8 in the paper) into sum of log probabilities, which allows to compute outer expectation easily.\n\n> *El2N bug*\n\nWe believe to be using the correct (updated) version of the code, where the bug in flax was fixed in April 2021, regarding the loading of checkpoints.\n\n> *lack of limitations*\n\nWe discussed limitations in detail in App A."}, {"review_id": "EoWEdlABYY", "reviewer": "Reviewer_U6Yc", "summary": "Current subset selection methods are architecture specific and requires solving an optimization problem for each architecture individually. The subset selected through solving an optimization for one architecture does not generalize to another model. This paper addresses this problem and introduces an end-to-end training method using multiple architectures (through embedding them via GNN) to select a generalizable subset. The paper addresses an important problem, written thoroughly and consists of sufficient empirical experiments to verify the idea.", "questions": "See Weakness", "limitations": "Overall, I believe that the paper is well-written with good empirical results. Given that the method (although not simple for adoption) offers a significant speedup for new architectures, I would vote for a weak acceptance. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Addresses a relevant practical problem in selecting subsets which can generalize across different architectures. \n- The paper is generally very well written and each component of the method pipeline is very well explained.\n- Good speedup with the proposed design (which is very relevant in practical scenarios) and also lower RAR compared to other baselines. ", "weaknesses": "- While the method is a generalization of the subset selection algorithm — it is inherently complex which can lead to less adoption by the community\n- The paper will be stronger if more complex datasets are added. Currently only smaller datasets are used, which can obfuscate the real-world capabilities of this method. While Tiny-ImageNet is used, a few experiments at ImageNet scale will help verify the efficacy of the method more strongly.\n- I would expect a little bit more analysis on the characteristics of the data subset selected using their method vs. other baselines. Are there difference in the properties of data which are selected by SubSelNet? What is the overlap factor with other methods?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed reading of the paper and their positive feedback. \n\n\n> *The paper will be stronger if more complex datasets are added. Currently only smaller datasets are used, which can obfuscate the real-world capabilities of this method. While Tiny-ImageNet is used, a few experiments at ImageNet scale will help verify the efficacy of the method more strongly.*\n\n\nWe want to note that Tiny-ImageNet (a 100,000 point subset of ImageNet with 200 classes), and CalTech-256 (a 30,607 point dataset with 257 classes) are challenging real-world datasets, especially for subset selection. We further conducted experiments on ImageNet and presented the results in Figure 2 of the global-pdf and also here in the following table which shows the compute time and memory to reach 10% and 20% RAR values. We observe that we perform better than other methods (- means that we couldn’t achieve that RAR with the method).\n\n\n|  | Speedup |  | Memory (Gb-min) |  |\n|---|---|---|---|---|\n| **RAR** $\\to$ | 10\\% | 20\\% | 10\\% | 20\\% |\n| Pruning | 0.99 | 1.03 | 7.31e5 | 6.94e5 |\n| Random | 1.06 | 1.21 | 6.90e5 | 5.69e5 |\n| Proxy | 0.91 | 0.99 | 8.24e5 | 7.19e5 |\n| Our | 1.25 | 1.47 | 5.77e5 | 4.87e5 |\n\n\n\n> *I would expect a little bit more analysis on the characteristics of the data subset selected using their method vs. other baselines. Are there difference in the properties of data which are selected by SubSelNet? What is the overlap factor with other methods?*\n\nNote that the key to our algorithm is to select different subsets that are optimal to different architectures. In that way, we found that the similarity between architectures has positive correlation between subsets.\nWe compute similarity between graphs $s(G _i,G _j)$  and the underlying subsets $|S _i\\cap S _j|$ for each pair of architectures $i,j$. Then we get the Kendall’s-tau (k) between the list of all possible pairs of $s(G _i,G _j)$ and $|S _i\\cap S _j|$ to be 0.42 for CIFAR10 and 0.55 for CIFAR100. This shows that there is a positive correlation between the model structure and the subset chosen.  \n\nWe also observed overlap between subsets returned by other methods with ours. Indeed there is a good amount of overlap. For example, we observe that for CIFAR100, the subset chosen by us has a 31% overlap with the subset chosen by GRAD-MATCH. However, it is to note that our method selects the subset significantly faster than others, as shown in Table 4 of the global-pdf.\n"}, {"review_id": "lnS5lE1HxE", "reviewer": "Reviewer_awrD", "summary": "The authors train 1) an architecture encoder using a GNN with a variational graph autoencoder loss to learn a good representation for model architectures, 2) a model approximator taking the GNN representation and a sample x to predict the output of the model given x. The goal is to learn a probability distribution over the samples of the datasets to obtain a subset of the data with minimum loss while penalizing an entropic objective to encourage maximum diversity. Given a chosen architecture, Transductive-SUBSELNET directly optimizes all probabilities of the samples. Meanwhile, Inductive-SUBSELNET learns a neural network taking the dataset (and both the GNN representation and the model approximator output) to generate a probability for each sample. They also do a hybrid approach for better efficiency.\n\nAlthough I understand the algorithm, this is quite complicated, and I cannot claim to understand all the specifics of every moving part (for example, how the GNN forms a representation for the architecture and learn to be insensitive to the model parameters, and why we need BFS; mainly I am not very familiar with GNNs).", "questions": "Have you considered using pre-trained graph models for the architecture representation? It seems like there should exist some, and they may be trained with more than 250 architectures. If there are, it would be a worthwhile comparison and remove one big step from the algorithm. I know that there are GNNs for weights such as GHN-3, but I am not familiar with those for architecture.\n\nIt would be great to see b in Figure 3, maybe in the top x-axis, because right now, it's difficult to infer which size of the data is used.\n\nYou mention taking the images and then taking the 2048 Resnet-50 embedding as image representation; it seems to have come out of nowhere. Could you add more context to this? Because I assume that the actual images are used for real architectures and possibly in the Inductive-SUBSELNET neural network.\n\nThe notation can sometimes be weird, especially with the big dot in Pr_pi(dot); shouldn't x_i replace the dot?\n\nI think that instead of separating algorithms 1 and 2 as training vs inference, it would be easier to understand by separating them into two algorithms with one Transductive and one Inductive, and each algo could be separated into top and bottom where the top is training and the bottom is inference. TRAINPIPELINE could be separate.\n", "limitations": "Yes, the authors properly address limitations and broader impacts.", "rating": 9, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The results are very in-depth, showing a lot of interesting ways to apply this general method and some useful applications like making NAS and hyperparameter-tuning nearly as good by much faster by reducing the dataset size. They present comparisons to other works, showing significantly improved performance in terms of RAR and memory. They train on many datasets of various image sizes but only in the image domain.\n\nI think that this is great work. ", "weaknesses": "Limited to CNNs for now (but that's okay). The biggest thing that could be improved is the notation and formatting of the paper to make the approach clearer, a lot of the details like in the GNNs could be left to the appendix. I feel like the paper overcomplicates things.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review of the paper!\n\n> *Have you considered using pre-trained graph models for the architecture representation? It seems like there should exist some, and they may be trained with more than 250 architectures. If there are, it would be a worthwhile comparison and remove one big step from the algorithm. I know that there are GNNs for weights such as GHN-3, but I am not familiar with those for architecture.*\n\n\nGNNs embed model architecture into representations independent of the underlying dataset\nand the model parameters (Appendix F page 9, L789). Thus we train GNN  once for all and the same GNN embeddings are used in all datasets. Indeed, this training was done at the very initial stage of the experiments and the resulting embeddings are being used everywhere.\n\nWe did not find any pre-trained graph models for architecture representation. There are pre-trained graph embeddings for social network type graphs, i.e., Amazon recommendation network, open academic graph [1]; and molecular graphs [2]. However, we are not aware about similar pre-trained weights for architectures. If our work gets accepted, we will release the pre-trained graph embeddings, so that it can be directly used for subsequent work without further training from scratch. \n\n[1] Hu et al. GPT-GNN: Generative Pre-Training of Graph Neural Networks, KDD 2020.\n\n[2] Xia et al.  Mole-BERT: Rethinking Pre-training Graph Neural Networks for Molecules, ICLR 2023\n\n\n\n> *It would be great to see b in Figure 3, maybe in the top x-axis, because right now, it's difficult to infer which size of the data is used.*\n\nFollowing the suggestion, we have added the budget to the computational efficiency plots in the top x-axis in Figure 1, and as a separate plot in Figure 2 in the global-pdf.\n\n\n> *You mention taking the images and then taking the 2048 Resnet-50 embedding as image representation; it seems to have come out of nowhere. Could you add more context to this? Because I assume that the actual images are used for real architectures and possibly in the Inductive-SUBSELNET neural network.*\n\n\nWe sincerely apologize for the misunderstanding which arose in Section 5.1 about usage of the ResNet-based embedding for images. To calculate the similarity matrix for facility location, we utilize the penultimate-layer of the ResNet-based feature extractor to represent the image representation, which is common in literature especially for calculating similarity between images. Hence, the feature extractor information on L276 is used **only during the subset selection stage** for the facility location formulation in L281. The input to the model architectures for all the methods and $\\texttt{SubSelNet}$ neural network are the actual images.  \n\n\n\n> *The notation can sometimes be weird, especially with the big dot in Pr _pi(dot); shouldn't x _i replace the dot?*\n\nWe use $\\Pr _\\pi(\\bullet)$ as the distribution itself, which is over the subset $S$. Here, $S$ can replace the dot.\n\n\n> *I think that instead of separating algorithms 1 and 2 as training vs inference, it would be easier to understand by separating them into two algorithms with one Transductive and one Inductive, and each algo could be separated into top and bottom where the top is training and the bottom is inference. TRAINPIPELINE could be separate.*\n\nWe thank the reviewer for this suggestion - we will update the presentation algorithm and split it separately into Transductive and Inductive.\n"}]

Author rebuttal:
We thank all the reviewers for their constructive and insightful comments. We would like to summarize the reviews and the global-pdf (attached with this rebuttal) here.

> (GR.1) *Results after addition of pre-training time* 

Currently, the approximator is trained with 250 architectures. However, we observed that even when we train the approximator with a lesser number of models, we beat the top competitive baselines after accounting for amortization. Below, we show the amortized time and memory to reach 10% and 20% RAR for the CIFAR10 dataset with the model approximator training architecture set of 100 and 250, for the most competitive methods.
|Approximator training size|100||||250||||
|---|---|---|---|---|---|---|---|---|
||Speedup||Memory||Speedup||Memory||
|**RAR**$\to$|10%|20%|10%|20%|10%|20%|10%|20%|
|GLISTER|1.52|2.12|515.96|365.05|1.52|2.12|515.96|365.05|
|Grad-Match|1.69|2.20|457.67|362.47|1.69|2.20|457.67|362.47|
|Inductive|3.18|5.23|253.40|171.10|2.94|4.41|274.08|202.91|
|Transductive|4.25|7.21|188.03|122.97|3.65|4.97|218.94|178.39||
> (GR.2)  *Other applications beyond NAS*

In addition to NAS, our work can be used for hyperparameter selection in the AutoML domain.

Primarily, we address the optimization of network-related hyperparameters such as activation functions and intermediate layer widths. The approach we propose involves training these model instances on a subset of data derived from our method. This expedited model training strategy quickly yields trained models and facilitates efficient cross-validation procedures. 

Moreover, let us consider the case where we need to tune non-network hyperparameters, such as learning rate, momentum, and weight decay. Given the architecture, we can choose the subset obtained using our method to train the underlying model parameters for different hyperparameters, which can then be used for cross-validation.  

> (GR.3) *Clarification regarding the pre-trained feature extractor*

We sincerely apologize for the misunderstanding which arose in Section 5.1 about usage of the ResNet-based embedding for images. To calculate the similarity matrix for facility location, we utilize the penultimate-layer of the ResNet-based feature extractor to represent the image representation, which is common in literature especially for calculating similarity between images. Hence, the feature extractor information on L276 is used **only during the subset selection stage for facility location** as shown in L281. 
Thus, the input to the model architectures for $\texttt{SubSelNet}$ and other methods are the actual images.

  
> (GR.4) *Contribution of the GNN-based architecture encoder* 

Discussion regarding the GNN is present in Appendix F.  Summarizing (1) GNN provides contextual embeddings of each node that captures not only the operation for that node but also the operations preceding that node. (2) GNN gives embeddings that are independent of the underlying dataset allowing us to train the encoder only once and use it for multiple datasets.
As a baseline, we feed the graph structure explicitly into the model approximator using the adjacency matrix instead of the GNN-derived node-embeddings. We note that such a change negatively impacts the performance, resulting in a 5-6% drop in RAR for 10\% subset on CIFAR10 as shown in Table 1 of the global-pdf.

> (GR.5) *Imagenet results*

We have added the results for ImageNet in Fig 2 in the global-pdf. We want to note that the adaptive baselines gave an out-of-memory error, and hence we were not able to experiment on those. Here we report the compute time and memory required to reach 10% and 20% RAR.

| | Speedup || Memory |  |
|---|---|---|---|---|
| **RAR** $\to$| 10\% | 20\% | 10\% | 20\% |
| Pruning | 0.99|1.03 | 7.31e5 | 6.94e5 |
| Random | 1.06 |1.21 | 6.90e5 | 5.69e5 |
| Proxy | 0.91 | 0.99 | 8.24e5 | 7.19e5 |
| Our | 1.25 | 1.47 | 5.77e5 | 4.87e5 |

> (GR.6) Summary of the global-pdf

In the global-pdf, we have added:

**Figure 1**: Tradeoff curves between absolute accuracy reduction (difference of test error of full selection and subset) and Speedup/Memory for the baselines: Random, Random-switch (random subset chosen at each epoch) and Selection-via-Proxy

**Figure 2**: Tradeoff curves between RAR and Speedup/Memory/Budget for ImageNet for the baselines: Random, Random-switch and Selection-via-Proxy

**Figure 3**: Tradeoff curves between RAR and Speedup for Tiny-ImageNet and Caltech-256 for the baseline: Selection-via-proxy

**Table 1**: Comparison of performance of GNN-based embedding and graph matrix embedding in the model approximator

**Table 2**: Test Error of NAS on DARTS search space for all non-adaptive baselines on CIFAR10

**Table 3**: Variation of SubSelNet performance on changing number of training architectures in the model approximator

**Table 4**: Breakdown of selection and training time for top adaptive and non-adaptive baselines on CIFAR100 for 0.5\% dataset


Meta-review: This paper proposes an example selection method called SubSelNet, which generalizes subset selection to unseen models. In discussion, all the reviewers agreed towards acceptance of this paper, and I agree with this consensus. However, there were some significant structure and presentation issues, which I suggest the authors work on for their camera ready submission, taking the reviewers' feedback into account. While the empirical results and overall contributions seem to merit acceptance, this paper will be much more impactful if it is presented more clearly.
Decision: Accept (poster)