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: Submitted to ICLR 2023 (2023)
Keywords: Data Subset Selection
Efficient Learning

Abstract: Subset selection, in recent times, has emerged as a successful approach toward efficient training of models by significantly reducing the amount of data and computational resources required. However, existing methods 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 data subset selection for an unseen architecture, one cannot use the subset chosen for a different model. In this work, we propose SubSelNet, a non-adaptive  subset selection framework, which tackles these problems with two main components. First, we 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 leads us to develop two variants of  SubSelNet. The first variant is transductive (called as Transductive-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 as Inductive-SubSelNet) which computes the subset using a trained subset selector, without any optimization.  Most state-of-the-art data subset selection approaches are adaptive, in that the subset selection adapts as the training progresses, and as a result, they require access to the entire data at training time.  Our approach, in contrast, is non-adaptive and does the subset selection only once in the beginning, thereby achieving resource and memory efficiency along with compute-efficiency at training time. Our experiments show that both transductive and inductive variants of our models outperform several methods on the quality of the subset chosen and further demonstrate that our method can be used for choosing the best architecture from a set of architectures.


Under review as a conference paper at ICLR 2023
EFFICIENT DATA SUBSET SELECTION TO GENERALIZE TRAINING ACROSS MODELS: TRANSDUCTIVE AND IN- DUCTIVE NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Subset selection, in recent times, has emerged successful approach toward efficient training of models by significantly reducing the amount of data and computational resources required. However, existing methods 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 data subset selection for an unseen architecture, one cannot use the subset chosen for a different model. In this work, we propose SUBSELNET, non- adaptive subset selection framework, which tackles these problems with two main components. First, we introduce an attention-bant 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 leads us to develop two variants of SUBSELNET. The first variant is transductive (called as Transductive-S SEE which computes the subset separately for each model by solving 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-SUBSEEII
neural gadget that leverages
which computes the subset using a trained subset selector, without any optimization. Most state-of-the-a data subset selection approaches are adaptive, in that the subset selection adapts as the training progresses, and as a result, they require access to the entire data at training time. Our approach, contrast, is non-adaptive and does the subset selection only once in the beginning, thereby achieving resource and memory efficiency along with compute-efficieng at training time. Our experiments show that both the variants of our model outperform several methods on the quality of the subset chosen and further demonstrate that our method can be used for choosing the best architecture from set of architectures.
INTRODUCTION
In the last decade, deep neural networks have enhanced the performance of the state-of-the-art ML models dramatically. However, these neural networks often demand massive data to train, which renders them heavily contingent on availability of high performance computing machinery, e.g., GPUs, CPUs, RAMs, storage disks, etc. However, such resources entail heavy energy consumption, excessive CO2 emission and maintenance cost.
Driven by this challenge, a recent body of work focus on suitably selecting a subset of instances, so that the model can be quickly trained using lightweight computing infrastructure (Boutsidis et al. 1013,Kirchhbp & Bilmes 2014] 4|| Wei et al. 3014a] Bairi et al., 2015 Liu et al., 2015 Wei et al. 2015
Lucic et al. 2017 Mirzasoleiman et al. 2020b Kaushal al. 2019 Killamsetty al. 2021 c).
However, these existing data subset selection algorithm are discrete combinatorial algorithms, which share three key limitations. (1) Scaling up the combinatorial algorithms is often difficult, which imposes significant barrier against achieving efficiency gains compared to training with entire data. (2) Many of these approaches are adaptive in nature, i.e, the subset changes as the model training progresses. As a result, they require access to the entire training dataset and while they provide compute-efficiency, they do not address memory and resource efficiency challenges of deep model training. (3) The subset selected by the algorithm tailored to train only given specific model and cannot be used to train another model. Therefore, the algorithm cannot be shared across different models. We discuss the related work in detail in Appendix

---

Under review as a conference paper at ICLR 2023
1.1 PRESENT WORK
Responding to the above limitations, we develop SUBSELNET, a trainable subset selection framework, which- once trained on a set of model architectures and a dataset- can quickly select small training subset such that it can be used to train new (test) model, without significant drop in accuracy. Our setup is non-adaptive in that it learns to select the subset before the training starts for a new architecture, instead of adaptively selecting the subset during the training process. We initiate our investigation by writing down an instance of combinatorial optimization problem that outputs a subset specifically for one given model architecture. Then, gradually develop SUBSELNET, by building upon this setup. SUBSELNET comprises of the following novel components.
Neural model approximator. The key blocker in scaling up model-specific combinatorial subset selector across different architectures is the involvement of the model parameters as optimization variables along with the candidate data subset. To circumvent this blocker, we design neural model approximator which aims to approximate the predictions of a trained model for any given architecture. Thus, such a model approximator can provide per instance accuracy provided by a new (test) model without explicitly training it. This model approximator works in two steps. First, it translates given model architecture into a set of embedding vectors using graph neural networks (GNNs). Similar to the proposal of Yan et al. (2020) it views a given model architecture as directed graph between different operations and, then outputs the node embeddings by learning a variational graph autoencoder (VAE) in unsupervised manner. Due to such nature of the training, these node embeddings represent only the underlying architecture- they do not capture any signal from the predictions of the trained model. Hence, in the next step, we build neural model encoder which uses these node embeddings and the given instance to approximate the prediction made by the trained model. The model encoder is transformer based neural network which combines the node embedding using self-attention induced weights to obtain an intermediate graph representation. This intermediate representation finally combines with the instance vector provide the prediction of the trained architecture.
Subset sampler. Having computed the prediction of a trained architecture, we aim to choose a subset of instances that would minimize the predicted loss and at the same time, offers a good representation of the data. Our subset sampler takes the approximate model output and an instance as input and computes a selection score. Then it builds logit vector using all these selection scores, feeds it into a multinomial distribution and samples a subset from it. This naturally leads to two variants of the model.
Sww.rdduciiveSSSSE....... The first variant transductive in nature. Here, for each new architecture, we utilize the predictions from the model approximator to build a continuous surrogate of the original combinatorial problem and solve it to obtain the underlying selection scores. Thus, we still need to solve fresh optimization problem for every new architecture. However, the direct predictions from the model approximator allow us to skip explicit model training. This makes this strategy extremely fast both in terms of memory and time. We call this transductive subset selector as Sonndductive-UBBSEL..
In contrast to Transductive-SURSS SUBSEI, the second variant does not require to solve any optimization problem. Consequently, it is extremely fast. Instead, it models the scores using a neural network which is trained across different architectures to minimize the entropy regularized sum of the prediction loss. We call this variant as Inductive-SUBSELL
We compare our method against six state-of-the-art methods on three real world datasets, which show that Transductive-S SEB (Inductive-Suu -SBriiie--SUSSSS SSI-SSBBBNENNEN SEL. provides the best (second best) trade off between accuracy and inference time as well as accuracy and memory usage, among all the methods. This is because (1) our subset selection method does not require any training at any stage of subset selection for new model; and, (2) our approach is non-adaptive and does the subset selection before the training starts. In contrast, most ffte-offthhearr data subset selection approaches are adaptive, in that the subset selection adapts as the training progresses, and as a result, they require access to the entire data at training time. Finally, we design hybrid version of the model, where given budget, we first select a larger set of instances using Inductive-SuBSELNEE SUBSELNET, and then extract the required
number of instances using allow us to make a smooth transition between the trade off curves from Inductive- Siriiivev-SuBSaae SUBSELNET to Seattiettvve-S-SSSSSSSS NET.
SUB.LLE We observe that such a hybrid approach
2

---

Under review as a conference paper at ICLR 2023
2 DEVELOPMENT OF PROPOSED MODEL: SUBSELNET
In this section, we setup the notations and write down the combinatorial subset selection problem for efficient training. This leads us to develop a continuous optimization problem which would allow us to generalize the combinatorial setup across different models,
2.1 NOTATIONS
We are given a set of training instances {(T; BE) where we use D to index the data. Here, I; E Rd are features and y/ E Y as the labels. In our experiments, we consider ) as a 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 map We also use M to denote the set of neural architectures. Given an architecture m E M, Gn = (Vm, Em) provides the graph representation of m, where the nodes E Vn represent the operations and the 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 (-)) to denote the entropy of a probability distribution and (m)) y) as the cross entropy loss hereafter.
(um, Um)
2.2 COMBINATORIAL SUBSET SELECTION FOR EFFICIENT LEARNING
We are given a dataset (ar; y:)] (r)}eep DDD and a model architecture m .M with its neural parameteri- zation mg- The goal of subset selection algorithm is to select small subset of instances S with |S] = n << [D] such that, training mg on the subset gives nearly same accuracy as training on the entire dataset D. Existing works (Killamsetty et al. 202 Sivasubramanian et al. 202 Killamsetty ett al., 2021a) adopt different strategies to achieve this goal, but all of them aim to simultaneously optimize for the model parameters 6 as well the candidate subset S. At the outset, we may consider the following optimization problem.
Σ ((mo(z;)) u) DIVERSITY(S)), D:SCD
minimize
ES
where is the budget, DIVERSITY measures the representativeness of S with respect to the whole dataset D and is a regularizing coefficient. One can use submodular functions (Fujishige) 2005 Tyer 2015) like Facility Location, graph cut, Nog-Determinants model DIVERSITY(S) Here, À trades off between training loss and diversity. Such an optimization problem indeed provides an optimal subset S that results in high accuracy.
Bottlenecks of the combinatorial optimization. The optimization problem I imposes the following challenges. (1) demands explicit training of my which can be expensive terms of both memory and time. (2) The training of ma every time for a new architecture m prevents the subset S from being generalizable- one needs to solve the optimization ① again to find S for an unseen model architecture. We address these challenges by designing a neural surrogate of the objective (I). which would lead to generalization of subset selection across efficient training of different models.
2.3 COMPONENTS OF SUBSELNET MODEL
Next, we sketch our proposed model SUBSELNET that leads to substituting the optimization (I with its neural surrogate. It consists of two key components: (i) neural approximator of the trained model and (ii) the subset sampler. Figure 4 in Appendix illustrates our model.
Approximator of the trained model mo- First, we design neural network Fg which would approximate the predictions of the trained model mø- for different architectures m M. Given the dataset ((x; y1 ) } and a model architecture m M, we first feed the underlying DAG Gm into graph neural network GNN, with parameter a, which outputs the representations of the nodes the Gms i.e., H m (hw) Next, we feed Hm and the instance æ, into an encoder 93
mg-(xx) for m M. Here, (G x;)) = ga (GNNN
Fa(Gm,
(3)
Here, @ (a, B). and 0* is the set of learned parameters of the model mo the dataset D.
Subset sampler. We design a subset sampler using a probabilistic model (+) Given a budget |S| 5 b, it sequentially draws instances S {,1,..,, 3.} from softmax distribution of the logit vector E RIPI where n (x, y:) indicates score for the element (æ,, y:). Having chosen the
3

---

Under review as a conference paper at ICLR 2023
first t instances S, {s1) from D, it draws the (t 1)-th element (æ, y) from the remaining instances D with probability proportional to exp(#T æ. y)) and then repeat it for b times. Thus, the probability of selecting the ordered set of elements 5 = (1..... Sb is given by
exp(T( Uoet1
Pr (
II t= EEDI,
(4)
exp(x( expet Us.))
We would like to highlight that we use S as an ordered set of elements, selected in 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.
Training objective. Using the Eqs. 2 and 44) we replace the combinatorial optimization problem in Eq. (1) with continuous optimization problem, across different model architectures m M. To that goal, we define
AT Eies ((F& (G,, M.) (H(
(5)
minimize J.P
Σ
E (EP)+())
AT + Σ (KL(Fa xz), mo- (2:))
(6)
MEM
iES
Here, we use entropy on the subset sampler H (Pr, to model the diversity of samples in the selected subset. We call our neural pipeline, which consists of the model approximator Fg and the subset selector æ, as SUBSELNET. model approximator and the prediction made by the trained model, which allows us to generalize the training of different models m & .M through the model Fo FG(G (Gm,
the above, 7 penalizes the difference between the output of
2.4 TRANSDUCTIVV--SUSSELNN
AND INDUCTIVE-
MODELS
The optimization
(6) suggests that once F& is trained, we can use it to compute the output of the trained model mg- for an unseen architecture m' and use it to compute This already removes significant overhead of model training and facilitates fast computation of æ. This leads us to develop two types of models based on how
compute æ, follows.
The first variant of the model is transductive in terms of computation of Here, once we train the model approximator Fa, then compute by solving the optimization problem explicitly with respect to n, every time when we wish to select data subset for a new archi- tecture. Given a trained model F& and new model architecture m' M, solve the optimization problem: min, EsEPr, [AS;; m, ग. F&]] to find the subset sampler Pr, during inference time for a new architecture m'. Such an optimization still consumes time during inference. However, is still significantly faster than the combinatorial methods (Killamsetty al. (202 Mirzasoleiman et al. 2020a; Sivasubramanian et al.) 2021) thanks to sidestepping the explicit model training using model approximator.
Transductive-SUBEEI
Induetive-SusSEL.N In contrast to the transductive model, the inductive model does not require explicit optimization of π in the face of new architecture. To that aim, we approximate æ using a neural network Tg. This takes two signals as inputs the dataset D and the outputs of the model approximator for different instances (Fo 2x) i E D), and finally outputs score for each the optimization 6 becomes:
instance x (m, v:). Under
minimize V.d
Σ
E (EP)+a())
A(S: To. Fa) Σ [KT[(F(GGm R.), mo- (2r:))
MEM
FES
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 0 or searching for the underlying subset.
NEURAL PARAMETERIZATION OF SUBSELNET
In this section, we describe the neural parametrization of SUBSELNET. SUBSELNET consists of two key components, F3 and T.. Specifically, SonnsductiveSSBBELLNY has only one neural component which is Fs. whereas, Snductive-SUurSiELNETT has both Fe and nØ.
3.1 NEURAL PARAMETERIZATION OF Fs
The approximator F, consists of two components: (i) a graph neural network GNN,, which maps G., the DAG of architecture, to the node representations Hm (hw)vev. and (ii) model encoder
4

---

Under review as a conference paper at ICLR 2023
93 which takes H. and the instance 2, imput and approximates my. (z,), i.e., the prediction made by the trained model. Therefore, Fo x) =
Z.). Here, Φ = {a,
Computation of architecture embedding using GNN Given model m M, compute the representations H = { u E Vm by using graph neural network GNN parameterized with a, following the proposal of Yan et al. (2020). We first compute the feature vector fu for each node u E Vm using the one-hot hot encoding of the associated operation (e.g., max, sum, etc.) and then feed into neural network compute an initial node representation, as given below.
n [0] = (fITNODE...a)
Then, we use a message passing network, which collects signals from the neighborhood of different nodes and recursively compute the node representations (Yan et al. 2020 Xu et al., [20 8b; Gilmer et al. 2017). Given a maximum number of recursive layers K and the node u, we compute the node embeddings Hm [h.,b ju 3 by gathering information from the k < K hops using K recursive
layers as follows.
((,,)) [k- 1] EDGEEMBED,, [k 11, holh: 1I)
h [k 1] SYMMAGGR, (u, 1] Nbr(u)))
h,,[k] UPDATE, (h,, [k: 11, h 1)).
Here, Nbr(u) the set of neighbors of u. We use SYMMAGGR as a simple sum aggregator and both UPDATE and EDGEEMBED are injective mappings. as used in (Xu et al. 2018b). Note that trainable parameters from EDGEEMBED, SYMMAGGR and UPDATE are decoupled. They are represented as the set of parameters Finally, we obtain our node representations as:
(10) Model encoder ga. Having computed the architecture representation { |u E Vn we next design the model encoder which leverages these embeddings to predict the output of the trained model mo. (z;). To this aim, we developed a model encoder ga parameterized by 3 that takes Hn and æ; as input and attempts to predict ma- (2;) i.e., g: (Hm, X.) = mg- mg-(x;) (x;). ). It consists of three steps. In the first step, we generate a permutation invariant order on the nodes. Next, we feed the representations {h.,} in this order into self-attention based transformer layer. Finally, combine the output of the transformer and the instance æ using a feedforward network to approximate the model output.
h hh.. -., h., [K -]]-
Node ordering using BFS order. We first sort the nodes using breadth-firsee first-search (BFS) order p. Similar to You et al. (2018), this sorting method produces a commutation-invariaan sequence of nodes and captures subtleties like skip connections in the network structure Gm
Attention layer: Given the BFS order p. we pass the representations Hm (hu u E Vor in the sequence P through self-attention based transformer network. Here, the Query, Key and Value functions are realized by matrices W Quurry Wkey: Wvalue E [kdm(())) x where k is tunable width. Thus, for each node u E Vm. we have:
Query( = W Waueryhun hur Using these quantities, we compute attention weighted vector Su given by:
Key(h.)) = WIT has Value(h..) = W WiThuete Per
(11)
Att. = W. Σ au,v Valuo(h.) with, au,v SOFTMAX, (Query(h..) Key(h.))VR Kebyrr(h
(12)
Here l is the dimension of the latent space, the softmax operation is over the node v, and W. E R dim(h)))) Subsequently, for each node u, we use feedforward network, preceded and succeeded by layer normalization operations, which are given by the following set of equations.
/1, S,,1 = LA(Att, + h.: 71, 72), Sa.2 = W. RELU(W] Sa.1). Cu.3 = LN(G...1 + +w.22 74)
Here, LN is the layer normalization operation [Ba et al. 2016). Finally, we feed the vector Çu,3 for the last node u in the sequence p. i.e., u = p( Vm.. along with the feature vector æ; into a feed-forward network parameterized by WF to model the prediction mg- mg.(x;;. Thus, the final output of the model encoder go Hm,, æX,) is given by
Om FFg, (Sp/ysn
(13)
Here, W. and % trainable parameters and collectively form the set of parameters B.
5

---

Under review as a conference paper at ICLR 2023
3.2 NEURAL ARCHITECTURE OF SERUCTIVE-SUSELNNE
We approximate æ using a neural network using a neural network which takes three inputs (az, Vj), the corresponding output of the model approximator, i.e., Om,n, Fo F2) and the node representation matrix H and provides a positive selection score Ty [H,,, m: T. Uj. mm, ). In practice, Te is three-layer forward network, which contains Leaky-ReLL activation functions for the first two layers and sigmoid activation at the last layer.
4 PARAMETER ESTIMATION AND INFERENCE
Given dataset {(T; M4) i E D} and the output of the trained models {mg- (x:)) our goal is to estimate & and и (resp. ) for the transductive (inductive) model. We first illustrate the bottlenecks that prevent us from end-to-end training for estimating these parameters. Then, we introduce multi-stage training method to overcome these limitations. Finally, we present the inference method.
4.1 BOTTLENECK FOR END TO END TRAINING
End end optimization of the above problem is difficult for the following reasons. (i) Our architecture representation H,, only represents the architectures and thus should be independent of parameter of the architecture and the instances æ. End to end training can make them sensitive these quantities. (ii) To enable the model approximator Fo accurately fit the output of the trained model mas need an explicit training for é with the target vig. Adding the corresponding loss as an additional regularizer imposes an additional hyperparameter tuning.
4.2 MULTI-STAGE TRAINING
In our multi-stage training method, we first train the model approximator Fg by minimizing the sum of the KL divergence between the gold output probabilities, and then train our subset sampler Pr. (resp. Prxg)) for the transductive (inductive) model as well as fine-tuning Φ
Training the model approximator Fg. We train Fg two steps. In the first step, we perform unsupervised training of GNN using graph variational autoencoder (GVAE). This ensures that the architecture representations Hm remain insensitive to the model parameters. We build the encoder and decoder of our GVAE by following existing works graph VAEs (Yan et al. (020) in the context graph based modeling of neural architectures. Given a graph Gm, the encoder q (Zm (m) which takes the node embeddings (hm) uev., and maps it into the latent space Zm {zu) Juv... Specifically, model the encoder ( (..) as: q(zu Gm,) ((((hu) E(hw))) Here, both and V are neural networks. Given a latent representation Zn = { uey., the decoder models generative distribution of the graph G,, where the presence of edge is modeled as Bernoulli distribution BERNOULLI 2.)). Thus, we model the decoder as:
p(Gm 2) = [I(,,,) (=, zv) [[,,,) [1 ( (2.]2.))
(14)
Here, a is a parameterized sigmoid function. Finally, we estimate a, n4, E and by maximizing the evidence lower bound (ELBO) as follows:
max Ez Ez~g(- (G. Z)] (L(g( Gm lprior a.
(15)
Next, we train our model encoder ga by minimizing the KI.-Divergenc between the approximated prediction g (H,, a.) and the ground truth prediction mg- (æ:),, where both these quantities are probabilities across different classes. Hence, the training problem is as follows:
minimize ΣIED.MEM (m (x:))lgs² (H. ax))
(16)
Training of the subset sampler. Finally, we fine-tune ga and train by solving (6) for the Soadductive-SuSSELNNG (likewise train Ty by solving 7 for Inductive- Setuctive-SuBSENNETT
4.3 INFERENCE
During inference, our goal to select a subset S with |S| b for a new model m', which would facilitate efficient training of m'. As discussed in Section 2.4] we compute т for Transductive-
m: m, F&)] and SUBSELNET by explicitly solving the optimization problem: minl (s)
then draw S ~ (r,()). For Induccive-SUnSSLLEET, we draw S ~ Prag where & is the learned value of & during training.

---

Under review as a conference paper at ICLR 2023
4.4 OVERVIEW OF TRAINING AND INFERENCE ROUTINES
Algorithms Jand summarize the algorithms for the training and inference procedure.
Training Subroutines. The training phase for both, Srrndduuctiv-SURSELL..
Algorithm 1 Training procedure
first utilizes the TRAINAPPROX routine to train the model approximator given the dataset, trained model parameters, and the set of neural architectures. Internally, the routine calls the TRAINGNN sub- routine to train the parameters (a) of the GNN network, BFSORDERING subroutine to reorder the embeddings based on the BFS order and the TRAINMODELEEN subroutine to train the attention-based model encoder's parameters (9)) The TRAININDUCTIVE routine further calls the TRAINPI subroutine to train the parameters of the neural subset selector.
1: function TRALINTRANDDUCTIVEEDDD.. (8*))
2:
à, B, H.n TTRIINAPPROX(D,MM, (0*))
1: function TRAININDUCTTVE(.,,,, (0*))
2:
â, B, Hm *TRAINNPPROX(DD,. M, {0*))
3:
o f- [gg(( (.: J..))lmm
4:
4 < TRAINPI(O, {mm). {x;1)
1:
function TRAINAPPROX D, M, {0*))
2:
â 6 (RAINGNN(M)
3:
for m E M do
4:
Hm t a
5:
POS BFSORDERINGG
6: B B TRAINMODELENC((z.) POs, (0*))
Inference Subroutines. Given an unseen ar- chitecture and parameters of the trained neural networks, the inference phase for both variants of SUBSEL.ET first generates the model en- coder output for all the data points. Post this, the INFERTRANSDUCTI
Algorithm 2 Inference procedure
1:
function INFERTRANSSDUCTIVE
routine solves the optimization problem on π explicitly for the un- seen architecture and selects the subset from the dataset. On the other hand, INFERINDUC- TIVE utilizes the trained parameters of the neural subset selector. Finally, both routines call the TRAINNEW to train and evaluate the unseen architecture on selected subset.
2:
Hm' &- GNN)(m²)
3:
F Fa ...) + 93 am) E
4:
x² f- min, Eser (A(S:) Fo)l
5:
S ~ PI.-
6:
TRAINEEWMODEL(
1:
function INFERINDUCTIVE 6,
2:
Hm' &- GNN&(mm)
3:
Fo x..) + 93 H m' x.) Vi D
5 EXPERIMENTS
4: Compute π (Z Vi) ViED
5:
S Pr..
In this section, we provide comprehensive eval- uation of SUBSELNET against several strong baselines on three real world datasets. In Ap- pendix D. we present additional results.
6:
(RDENNE
5.1 EXPERIMENTAL SETUP
Datasets. We use FMNIST (iao et al.] 2017), CIFARIO (Krizhevsky et al. 2014] and CI- FARI00 (Krizhevsky et al. 2009) datasets for our experiments. We transform an input image X; to vector æ; of dimension 2048 by feeding it to a pre-trained ResNet50 v1.5 (?) model and using the output from the penultimate layer as the image representation.
Model architectures and baselines. We use model architectures from NAS-Bench-101 (Ying et al. 2019) for our experiments. We compare against two non-adaptive subset selection methods- (i) Facility location (Fujishige 22055 Iver
and Strtuctive-SBBSE...
2015
where we maximize FL(S)= = ΣjED maxies 2; æ; to find S, (ii) Pruning (Sorscher et al. 2022
and four adaptive subset selection methods (iii) Glister (Killamsetty et 202 (IV) Grad-
Match (Killamsetty et al. 2021a). (v) EL2N (Paul et al., 2021), (vi) GraNd (Paul et al. 202T): );
and;
(vii) Full selection where we use complete training data. The non-adapiive 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 Conttins additional details about the baselines.
Evaluation protocol. We split the model architectures M into 60% training (M₂),, 20% validation (Mya) and 20% test (Mis)) folds. Similarly, we split the dataset D into Drr Dval and Dest We present M Myat, Dr and Deat to our method and estimate & and & (for Inductive-SURSEINNE
7

---

Under review as a conference paper at ICLR 2023
Ttunsductive-SuuSeleeett Induattive-SubSeeeNee
FI.
GLISTER
GraNd
Pruning
Grad-Match
EL2N
1.00
0.75
0.3
full selection:
0.75
1.0,0.91
0.50
0.2
0.50
Pr(y
0.25
full selection
Pr(y
0.25
full selection:
Pr(y
0.1
(1.0, 0.97)
(1.0, 0.96)
0.00
0.00
0.0
50
150 200 250
50
150 200 250
50
150 200 250
Speed up (Ty/T)
Speed up (2'/2T) +
Speed up (Ty/T)
1.00
0.75
full selection:
0.3
full selection:
0.75
(2.4 x 10 0.96)
(2.7 10
0.50
0.50
0.25
full selection:
0.25
Prly
0.1
(2.1 10 0.97
0.00
0
25
50
75
100
0.00
0
50
75
100
0.0
50
75
100
So memorry df)dt (GB-min)
J (e)o (CB-min)
I," memory(()dd (CB-min)
(a) FMNIST
(b) CIFARIO
(c) C1FAR100
Figure 1: Trade off between accuracy and speedup (top row) and accuracy and memory consumption
(bottom row) for all the methods- - Facility location (Fujishige 2005 Iyer| 2015). Pruning (Sorscher
al. 2022), Glister (Killamsetty et al., 2021b). Grad-Match (Killamsetty et al.) 2021 ab, EL2N (Paul
al. 202 1) GraNd (Paul et al.) 2021): and; Full selection on all three datasets FMNIST, CIFARIO and CIFAR100. In all cases, we vary [S] = & e (0.005) D), 0.05 and measure accuracy on 20% test architectures and 20% test instances.
model). None of the baseline methods supports any generalizable learning protocol across different model architectures and thus cannot leverage the training architectures during test.
Given architecture m' Misss select the subset S from Du using our subset sampler (Pr, for Transductive- SuBSeSuSSSELEEEE or Pr#ę for Inductive-Su SUTSEL Similarly, all the non- non-adaptive subset selectors select S C Da using their own algorithms. Once S is selected, we train the test models m E Must on S. We perform our experiments with different |S] 6 E (0.005) D), 0.05 D)) and compare the performance between different methods using three quantities: (I) Accuracy Pr(y = 9) measured using |Peall ΣieDE, Em (mmax m/- (ax)[[] y/). (2) Computational efficiency, i.e., the speedup achieved with respect to training with full dataset. It is measured with respect to T/TT. /T. Here, T'y 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 subsets across the test models m' MMesa plus the average training time of these test models 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(t) dt where memory(t) is amount of memory consumed at timestamp t.
5.2 RESULTS
Comparison with baselines. Here, we compare different methods in terms of the trade off between accuracy and computational efficiency as well accuracy and resource efficiency. In Figure [] we probe the variation between these quantities by varying the size of the selected subset |S| b E (0.005 0.05 DI). We make the following observations. (I) Our methods trade-off between accuracy vs. computational efficiency as well as accuracy vs. resource efficiency more effectively than all the methods. For FMNIST, both the variants of our method strikingly output 75% accuracy, whereas they are 100 times faster than full selection. Transductive- SUBSELNET performs slightly better than Sew.uciive-SuSSELL... for FMNIST and CIFARIO datasets. However, for CIFAR1 100, Saassducivv--SUBSELL... significantly better than Inductive-SUBSELLN and Inductive-SUu SEB seems comparable- this is because the subset selection time for both of them are significantly less than the final training time on the selected subset. (2) EL2N is the second best method. It provides the best trade-off between accuracy and time as well as accuracy and GPU memory, among all the baselines. aims at choosing difficult training instances having high prediction error. As result, once trained on them, the model can predict the labels of easy instances
in terms of the overall trade-off between accuracy and efficiency performs The time taken for both Saunsductive-SuBSLLJ
8

---

Under review as a conference paper at ICLR 2023
too. However, it chooses instances after running the initial few epochs. (3) FL adopts greedy algorithm for subset selection and therefore, it consumes a large time and memory during subset selection itself. Consequently, the overall efficiency significantly decreases although the complexity of the training time on the selected subset remains the same as our models in terms of time and memory. (4) In addition to EI.2N, Glister, Grad-Match and GraNd are adaptive subset selection methods that operate with moderately small (>> 5%) subset sizes, In a region, where the subset size is extremely small, i.e., 1% 5%, they perform very poorly. Moreover, they maximize a monotone function at each gradient update step, which results in significant overhead in terms of time. These methods process the entire training data to refine the choice of the subset and consequently. they end up consuming a lot of memory. (5) GraNd selects the instances having high uncertainty after running each model for five epochs and often the model not well trained by then.
Finer analysis of the inference time. 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 2 summarizes the results for top three non-adaptive subset selection methods for b 0.005 D CIFARI00. We observe that: (1)
Table 2: Inference time in seconds
Trans.
Inclurr.
Pl.
Subeet selection
0.23
0.067
226.29
Training
20.1
70.1
70.1
the final training times of all three methods are roughly same; (2) the selection time for Transductive- although it remains extremely small
NET is significantly more than Stuuctive-SUBELL..
as compared to the final training on the inferred subset; and, (3) the selection time of FL. is large- as close as 323% of the training time.
From Figure D we observe that Transductive-Sure SUni-SSSSSSEEEEEE performs sig- nifieantly better than SoductiveSSuBSENNDR However, since Saannddutive-uuBSEEE solves fresh optimization problem for each new architecture, it performs better at the cost of time and GPU memory. On the other hand, Inductive- SUBSELNET performs significantly worse as it relies on trained neural network to learn the same optimization problem. Here, we design a hybrid version of our model, called as Hlybrid-SuBSELNNE
WebriidSSUBSENNY
25000
45000
B 30000
Transductive (B 50000)
B 35000
Inductive (B- NA)
0.3
0.3
0.2
Here, given the budget of the subset b, we first choose B= > b instances using Inductive- SUBSELNET and the final b instances by running the explicit optimization routines in Transductive-Su SS marizes the results for B (25K, 30K, 45K, 50K). We observe that the trade off curves for the Hybrid-Supp SSLLNN lie in between Maductive-SuBSEENNE and Transductive- SUBBiV remains close to As we increase B, the trade-off curve of accuracy vs speed up as well as the accuracy vs GPU usage becomes better, which allows Hybrid-SUBSEI from the trade off curve of InductiveSSUBSELNN trade-off curve almost coincides with Saansductiv--SUBSELNNVE Such properties allow a user to choose an appropriate B that can accurately correspond to target operating point in the form of (Accuracy, Speed up) or (Accuracy, memory usage).
0.1
Pr(y
0.1
0.0
100
200
300
Speed up (Ty/T) +
Ju memory(())t (GB-min) +
Figure 3: Hybrid-SUBSELNer
Figure 3 sum-
For low value of B, i.e. B 25K, the trade off line of HlyrridSSBSEEL.. Inductive-SUBSELNN
to smoothly transition At B 45K, the
to Transductive-SUnss.
CONCLUSION
In this work, we develop SUBSELNET, subset selection framework, which can be trained on set of model architectures, to be able to predict a suitable training subset before training a model, for an unseen architecture. To do so, we first design neural model approximator, which predicts the output of a new candidate architecture without explicitly training it. We use that output to design transductive and inductive variants of our model. The transductive model solves small optimization problem to compute the subset for a new architecture m every single time. In contrast, the inductive model resorts to a neural subset sampler instead of an optimizer.
Our work does not incorporate the gradients of the trained model in model approximator and it would be interesting to explore its impact on the subset selection. Further we can extend our setup to an adaptive setting, where we can incorporate signals from different epochs with a sequence encoder to train a subset selector.

---

Under review as a conference paper at ICLR 2023
7 ETHICS STATEMENT
We do not foresee any negative impact of our work from ethics viewpoint.
REPRODUCIBILITY STATEMENT
We uploaded the code in supplementary material. Details of implementation given in Appendix C
REFERENCES
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint 160.::6607.06450. 2016.
Ramakrishna Bairi, Rishabh Iyer, Ganesh Ramakrishnan, and Jeff Bilmes. Summarization of multi- document topic hicrarchies using submodular mixtures. In ACL, pp. 553-563, 2015.
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architec- tures using reinforcement learning. In 5th International Conference on Leurning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, net wet.t/eoorrm..amll2222e21111
2017. URL
Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail. Near-optimal coresets for least-squares regression. IEEE transactions on information theory, 59(10)6680--682 2013.
Abir De, Paramita Koley, Niloy Ganguly, and Manuel Gomez-Rodriguez, Regression under human assistance. AAAI, 2020.
Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez-Rodriguez. Classification under human assistance. AAAI, 2021.
Xuanyi Dong and Yi Yang. Nas-bench-201. 201: Extending the scope of reproducible neural architecture search, 2020. URL httttt://axxii...oo
abs. 00326
Dan Feldman. Core-sets: Updated survey. In Sampling Techniques for Supervised or Unsupervised Tasks, pp. 23-44. Springer, 2020.
Satoru Fujishige. Submodular functions and optimization. Elsevier, 2005.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Sariel Har-Peled and Soham Mazumdar, On coresets for k-means and k-median clustering. In Proceedings of the thitty-sixth annual ACM symposium Theory of computing, pp. 291-300, 2004.
Rishabh Krishnan Iyer. Submodular optimization and machine learning: Theoretical results, umifying and scalable algorithmss, and applications. PhD thesis, 2015.
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), pp. 1289-1299, IEEE, 2019.
Krishnateja Killamsetty, Durga Sivasubramanian, Baharan Mirzasoleiman, Ganesh Ramakrishnan, Abir De, and Rishabh lyer. Grad-match: A gradient matching based data subset selection for efficient learning. arXiv preprint arXiv:2103.00122 00123, 2021a.
Krishnateja Killamsetty, Durga Subramanian, Ganesh Ramakrishnan, and Rishabh Tyer. Glister: generalization based data selection framework for efficient and robust learning. In AAAI, 2021b.
Krishnateja Killamsetty, Xujiang Zhao, Feng Chen, and Rishabh Iyer. Retrieve: Coreset selection for efficient and robust sumi-super learning. Advances in Neural Information Processing Systems, 2021c.
10

---

Under review as a conference paper at ICLR 2023
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), pp. 131-141, 2014.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. In online: 2014.
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. URL
https://arxis: /ttp:s///axvvv.oo wttp:////////...../..... 00559
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search, 2018.
URL httptt//aaaxxi...oooo org. abs 1806. 09055
Yuzong Liu, Rishabh Iyer, Katrin Kirchhoff, and Jeff Bilmes. Svitchboard ii and fisver High-quality limited-complextty corpora of conversational english speech. In Sixteenth Anmual Conference of the International Speech Communication Association, 2015.
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-599, 2017.
Jovita Lukasik, David Friede, Arber Zela, Frank Hutter, and Margret Keuper. Smooth variational graph embeddings for efficient neural architecture search. In International Joint Conference Neural Networks, IJCNN 2021, Shenzhen, China, July 18-22, 2021, 2021.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Van Liu. Neural architecture optimiza- tion. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018 URL htctts::/procsediiiic ngs. neurips wwtpppppr//....../. /tter///1///ffeeee pdf
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6950-6960.
PMLR, 2020a.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In Proc. ICML, 2020b.
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 on Educational Advances Artificial Intelligence, AAAI'19/IAM 19/1AA 19. AAAI Press, 2019.
ISBN 978-1-57735-809-11 1. doi: T609/aa81.v3322 33311313111111112222333 33014602]
URL
Xuefei Ning. Changcheng 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.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters, 0abss/995.09555
2019. URL
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34: 10596-206077 2021.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4095-4104. PMLR, 10-15 Jul 2018. URL httpss://proceecingg m wtr.press/v8l hham/ Ba html
11

---

Under review as a conference paper at ICLR 2023
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc Le, and Alex Kurakin. Large-scale evolution of image classifiers, 2017. URL https
//axxiv.org/abaat.. wttp:///ww.ab///1..11111.0
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search, 2018. StLhttts:// //rpiv..//xvvv..o/ wwg. abs 1802. 01548
Durga Sivasubramanian, Rishabh K. Iyer, Ganesh Ramakrishnan, and Abir De. Training data subset selection for regression with controlled generalization error. In ICML, 2021.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. arXiv preprint arXiv:2206.144886 2022.
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: 10.48550/
ARXIV.1807.1 1626. URI.htts:: httppp:ss/aaxxv./g//eeeemm http:////.////...../ 1807 626
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Fast multi-stage submodular maximization. In International conference on machine learning, pp. 1494-1502. PMLR, 2014a.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes. Submodular subset selection for large-scale speech training data. 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 331 1-3115,,, IEEE, 2014b.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Unsupervised submodular subset selec- tion for speech data. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4107-4111, IEEE, 2014c.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pp. 1954-1963, 2015.
Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. A study on encodings for neural architecture search. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 20309-20319 Curran As- sociates, Inc., 2020. URL https:: .nw.ueeeedinnn...up...........
nww.ips ctteiiss.ccpppaea http:ppss..ppppeee////////////
Pwwp2233372-PPp....e1e- Paper. pdf
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXi:: 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 00826]
networks?, 2018a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1810.0001 2018b.
Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representa- tion learning help neural architecture search? In NewrIPS, 2020.
Shen Yan, Kaigiang Song, Fei Liu, and Mi Zhang. Cate: Computation-awe aware neural architecture encoding with transformers. In ICML, 2021.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NAS- bench-101. 101: Towards reproducible neural architecture search. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 7105-7114, PMLR, 09-15 Jun 2019.
htt.:/eeddennn......rress/ss///e wwtppppssssspippppepp 19..
mlr.
Jiaxuan You, Rex Ying, Xiang Ren, William I.. Hamilton, and Jure Leskovee. Graphrnn: A deep generative model for graphs. CoRR, abss/102.00873, 2018. URL httpttt:///xxx..o/////b// 1802.08 08773
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: A variational autoencoder for directed acyelic graphs. pp. 1586-1598, 2019.
12

---

Under review as a conference paper at ICLR 2023
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning, 2016. URL
01578
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition, 2017. URL https: /ttp:s::/axxvvvviao wttps//..rr//ab///700000000
13

---

Under review as a conference paper at ICLR 2023
Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks
(Appendix)
A 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 (Zhang al.] 2019 Ning al. 2020 Yan et al. 2020:] Lukasik et al.,
202T). 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 on the structure of the network, White et al. (2020); Yan et al.
(202I) produce computation-awar aware encodings that map architectures with similar performance the same region in the latent space. Following the work of Yan et al. (2020), we use graph isomorphism network as an encoder but instead of producing a single graph embedding, our method produces a collection of node embeddings, ordered by breadth-firste sirrt- (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.
Network architecture search. There is an ever-increasing demand for the automatic search of neural networks for various tasks. The networks discovered by NAS methods often come from an underlying search space, usually designed to constrain the search space size. One such method is to use cell-based search spaces (Luo et al. 2018 Zoph et al. 2017 Liu et al. 2017 Pham et al. 2018, (Yng al., 2019 Dong & Yang] 2020). Although utilize the NAS-Bench- 101 search space for architecture retrieval, our work is fundamentally different from NAS. In contrast to the NAS methods, which search for the best possible architecture from the search space using either sampling or gradient-descent based methods (Baker et al. 2017 Zoph & Lej 2016: Real et al.) 2017 2018
Liu et al. [0188] Tan al. 2018), 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 to a continuous latent space, 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.
Data subset selection. Data subset selection is widely used in literature for efficient learning, coreset selection, human centric learning. etc. Several works cast the efficient data subset selection task as instance of submodular or approximatc-submodde
optimization problem (Killamsetty et al.. 2021 Wei et al.] 2014a blc: Killamsetty al.) 2021b Sivasubramanian et al. 2021). 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 (Feldman 2020 Mirzasoleiman et al. 2020bb Har-Peled & Mazumdar] [004] [Boutsidis et al.] [013] Lucic et al. 2017). Our work is closely connected simultaneous model learning and subset selection (De et al. 2021; 2020 Sivasubraaaniaan et al., 202I). 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 (De et al. 2021 2020) focus on distributing decisions between human and machines, whereas (Sivasubramanian et al. 202T) 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.
14

---

Under review as a conference paper at ICLR 2023
B ILLUSTRATION OF SUBSELNET
BFS
ULDATE,
hg p
W
hi pos
GNN,
W
W
{Atta lu Vin
Fa {a,
INIENODE
SyaMAGGHt
by poofo
Bu pos(a)
(a) Overview
Om...
FF P
LogerSor RoLU LegerNorm
EDGEEMBED
93
GNN
(d) Neural model approximator F {a.9)
[at;
(o) Training
(b/rransductive SUBSELNET
10
(c) Inductive
(a.
3).
SUBSEINNT
Transductive
Inductive
Figure 4: Illustration of SUBSELNET. (a) Overview of SUBSELNET: Given model architecture m M, SUBSELNET takes the graph structure model architecture Gm and dataset D input to neural model approximator Fsa, which predicts the output of the trained model mg- (æ). Then this is fed as input the subset sampler (for transductive model) or T. (for inductive model) to obtain the training subset S. F consists of a graph neural network GNN, and model encode gø. Given the dataset D and the predictions (Om.ar, lj E D} from the model approximator Fg, we compute the training subset by solving an optimization problem for each E .MM (c) Anductve-SUBBSELNVV
(b)
Here, we do not have to solve the optimization problem each time for a new architecture m. Instead, we use a neural network T which learns to solve the optimization problem of the transductive model during training and thus, directly provides the training subset S during test. (d) Architecture of the neural model approximator Fş. first feeds GT,, into graph neural network GNN which outputs the node representations {h.). Together with sequence of positional encoding obtained from a BFS ordering, {h.} J are fed into attention network followed by feed forward network, which outputs {Om.m;) for an instance (æ;, 9:). (e) The output of training procedure for the two variants of our model.
15

---

Under review as a conference paper at ICLR 2023
C
ADDITIONAL DETAILS ABOUT EXPERIMENTAL SETUP
C.I DATASET
Datasets (D).
Table 5: brief description of the datasets used along with the transformations applied during training
Dataset
No, of
Train-Test Split
Shape
Transformations
Classes
Applied
CIFARIO
10
(0K),
32x32x3
RandomCrop, Nornall lize RendonCrop, Normall
CIPARIO0
100
(0K),10K)
32x32x3
FMNIST
10
(0KK,
28x
Normall iie
Architectures (M). Although our task not Neural Architecture Search, we leverage the NASBench- 101 search space architecture pool. The cell-based search space was designed for the bench- marking of various NAS methods. It consists 423, 624 unique architectures with the following constraints (1) number of nodes in each cell is at most 7, (2) number of edges in each cell is most 9, (3) barring the input and output, there are three unique operations, namely x convolution, x 3 convolution and 3 x 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.
C.2 IMPLEMENTATION DETAILS ABOUT BASELINES
Facility Location (FL). We implemented facility location all the three datasets using the apricot ! library. The similarity matrix was computed using Euclidean distance between data points, and the objective function was maximized using the naive greedy algorithm.
It selects subset from the entire dataset based on the uncertainty of the datapoints while partial training. In our setup, we considered ResNet-18 dataset for 5 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 learning rate of 0.025.
Pruning.
master model, which is trained on each
Glister and Grad-Match. We implemented GLISTER (Killamsetty al. 2021b) and Grad-Match (Killamsetty et al. 202 la) 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 was minimized using SGD with learning rate of 0.01, momentum of 0.9 and weight decay with regularization constant of 5 10 We used cosine annealing for scheduling the learning rate with Tmaz of 50 epochs, and used 10% of the training data 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 on the data points of each mini-batch. Online-Gllister approximates the objective function with a Taylor series expansion up arbitrary number of terms to speed up the process; we used 15 terms in our experiments.
applies the orthogonal matching (OMP) pursuit algorithm to the data points of each mini-batch to match gradient of a subset to the entire training/validatin set. Here, we 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 an error margin of 14
GraNd. This is an adaptive subset selection strategy in which the norm of the gradient of the loss function is used trained on the full dataset for the first few epochs. For the rest of epochs, the model is 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.
score rank a data point. The gradient scores are computed after the model has
EL2N. When the loss function used to compute the GraNd scores is the cross entropy loss, the norm of the gradient for data point x can be approximated by EE] Ex]p(x) - vll2, where p(x) the discrete
16

---

Under review as a conference paper at ICLR 2023
probability distribution over the classes, computed by taking softmax of the logits, and is the one-hot encoded true label corresponding to the data point x. Similar to our implementation GraNd, computed the EL2N scores after letting the models train the full data for the first 5 epochs.
C.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 one of five operations and the one-hot- encoded feature vector f.. Since the set is cell-based, there is injective mapping between the neural architecture and the cell structure. We aim to produce a sequence embeddings for the cell, which in turn corresponds to that of the architecture. For each architecture,
the initial feature f, E Ro in (8) as a five dimensional one-hot encoding for each operation. This is fed into INITNODE 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 ED and UPDATE consists of
(8) obtain
X 128 Brrear-BatchNomm-PR ReLU cascaded with a 128 16 linear layer. Moreover, the symmetric aggregator is sum aggregator.
We repeat this layer K times, and each iteration gathers information from < K hops. After all the iterations, we generate embedding for each node, and following (You et al. 2018) we use the BFS-tree 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 (Ihma) weV..) and a exp (FCN ((tu))ev.))
The decoder aims to reconstruct the original cell structure (i.e the nodes and the corresponding operations), which one-hot encoded. It is modeled using single-layer fully connected networks followed by a sigmoid layer.
2.5
t
2.5
Mi-Divorgence
2.0
2.0
KI-Divergende
1.5-
1.0-
1.0
0.5
0.5
0.0
0.0 0
20
40
80
40
60
Epochs
Epochs -
(a) FMNIST
(b) CIFARIO
Figure 6: Kullback-Leibe divergence values (KL(mp- (x:) go H xx))) computed during the training of the model encoder ga over 80 epochs.
Model Encoder gs- The model encoder gæ is essentially single-head attention block that sequence node embeddings Hn = (hu u E Vn The Query, Key and Value matrices, W queery Wsey and Wvalue E 16 and the matrix We E 8x816 The fully connected network acting on Su.1 consists of matrices W1 E R 16x64 and W2 E 16 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 encoder is trained by minimizing the KL-divergence between ga (,.. xx)) and mg- (x;)) We used an AdamW optimizer with learning rate 10 10-3 e = 10-8 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 encoder ga H m, æ.,) with the outputs of the model mg- (mx))
17

---

Under review as a conference paper at ICLR 2023
Neural Network Ty. The inductive model is a three-layer fully-connected neural network with two Leaky ReLU activations and a sigmoid activation after the last layer. The input to To is the concatenation (H Om, 2i V/). 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 2;- While training Th add regularization term iE T m Om,i, 3i ys) - -(I)) ensure that nearly [S] samples have high scores out of the entire dataset D. Both the regularization constants À (in equation 6 and X 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 the leg-derivative trick to compute the gradient of the objectíve. During each computation step, we use one instance of the ranked list to compute the unbiased estimate of the objective in (6)
D ADDITIONAL EXPERIMENTS
D.1 ABLATION STUDY
We perform ablation study of SUBSELNET from three perspectives.
Impact of ablation of subset sampler. First, we attempt to understand the impact of the subset sampler. To that aim, we compare the performance of SUBSELNET against two baselines, namely In Bottom-b-loss, their predicted loss ((Fs(G x), y) and consider those points with the bottom values. In Bottom- b-loss+gumbel, we add noise sampled from the gumbel distribution with μ and 0.025, and sort the instances based on these noisy loss values, i..,, (G x), y) + Gumbel 3 0.025).
Bottom-b-loss and Bottom-b-loss+gumme
sort the data instances based on
We observe that Bottom-b-loss and being efficient in terms of time and memory. Figure 7 compares the performance of the variants of SUBSELNET, Bottom-b-loss and Bottom-b-loss-gummee
do not perform that well in spite of
Transdlucivve-SnbSeeNeet
Loss
InduetriveSubbSelNet
Loss + Gumbel
1.00
0.75
Prty 3)
0.75
0.50
0.2
0.50
0.25
Pr(y
0.1
0.00
50
150
200
250
50
150
200 250
50
150 200 250
Speed up (Ty/T)
Speed (Ty/T)
Speed up (Ty/T)
1.00
0.75
0.3
0.75
0.50
0.2
0.50
Priy
0.25
Pr(
0.1
0.25
0.00
0.00
0.0
00
20
10
20
20
30
Io memory((f)d (GB-min)
f memoory(()dt (GB-min)
memory (t)xtt (GB-min
FMNIST
(b) CIFAR10
CIFAR100
Figure 7: Comparison of SaassductiveSSuBSEE.... (Loss) and Bottom-b-lloss gummel (Loss + Gumbel). the former, we select top-b instances in terms of their predicted loss ((F (Gmm x), y) computed using the model approximator In Bottom- b-loss+gumbel, we add gumbel noise Gumbel(O, 0.025) to the loss and sort the instances based on these noisy loss values.
and Inductive-SURSEIINN with Bottom-b-loss
Exploring alternative architecture of the model encoder ga. We consider three alternative architecture to our current model encoder ga-
FEEDFORWARD: We consider two-layer cullecconeected network, in which concatenate the mean of Hm with x;, We used ReLu activation between the layers and the hidden dimension was set to 256. We used dropout for regularization with probability 0.3.
18

---

Under review as a conference paper at ICLR 2023
We consider permutation invariant networks of the form pl Shef ((h); where p and & are neural networks and H is the sequence under consideration. We p is conly-connected network with 4 layers, ReLU activation, and hidden dimension of 64, and o is two-layer fully- connected network with ReLU activation and has output dimension 10.
DEEPSET:
LSTM: We consider LSTM-based encoder with hidden dimension of 16 and dropout probability of 0.2. The output of the last LSTM block is concatenated with a; and fed to linear layer with hidden dimension 256, dropout probability of 0.3 and ReLU as the activation function.
Since the goal of the model encoder is to produce outputs which mimic the architectures, we measure the KL divergence between the outputs of the gold models and of the encoder denote the closeness of the output distribution. Table. [ summarizes performance of different model encoders. We make the following observations: (1) Transformer- model encoder outperforms every other method by a significant margin across both the datasets. (2) The BFS sequential modeling of an architecture with transformers leads to better representation that enables closer model approximation compared to other sequential methods like LSTM. (3) Non-sequential model approximators like Feedforward and DeepSets led to poor model approximation.
Table 8: Comparison of the performance of several model encoder architectures ga on the CIFAR-10 and FMNIST datasets, based on the Kullback-Leebler divergence values between the gold model outputs and predicted model outputs.
Model approximator
CIEAR-10
FMNIST
Feedforward
0.171
0.124
DeepSet
0.105
0.122
LSTM
0.102
0.113
Self-Attention Based
0.089
0.109
Performance of subset selectors using different model encoders. We consider three different design choices of model approximator (our (Transformer), Feedforward, and LSTM) along with three different subset selection strategies (Our subset sampler, top-b instances based on uncertainty, and top-b based on loss) which result in nine different combinations of model approximation and subset selection strategies. We measure uncertainty using the entropy of the predicted distribution of the target classes and report the average test accuracy of the models when they are trained on the underlying pre-selected subset in the following table
Table 9: Test accuracy of the nine combinations of model approximators and selection strategies on the pre-selected CIFAR10 subset of size 5%.
Design
Accuracy
Feedforward + SUBSELNET
0.527
Feedforward + Uncertainty
0.329
Feedforward + Loss
0.296
LSTM + SUE
0.526
LSTM + Uncertainty
0.417
LSTM + Loss
0.283
Transformer SUBSELNET
0.548
Transformer Uncertainty
0.198
Transformer Loss
0.210
We make the following observations
1. The complete design of our method, i.e., Our model approximator (Transformer) Our subset sampler (SUBSeLNET) performs best.
2. If we use simple unsupervised subset selection heuristics, e.g., loss or uncertainty based subset selection, then model approximator performs much worse than Feedforward or
19

---

Under review as a conference paper at ICLR 2023
LSTM, whereas this trend is opposite if we subset sampler for selecting the subset. This may be due to overfitting of the transformer architecture in presence of uncertainty or loss based selection, which is compensated by subset sampler.
D.2 RECOMMENDING MODEL ARCHITECTURE
When dealing with 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 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, we gather top 15 architectures A when trained on the subset provided by our models. Then, we compare A and AA* using the Kendall tau rank correlation coefficient (KTauu) along with Jaccard coefficent |A A" 1/ A U AAI
Figure 10 summarizes the results for top three non-adaptive subset selectors in terms of the accuracy. namely TransduciveeSSUBSELNNE SUBSELLET, Inductive-Subst SUESELN and FL. We make the following ob- servations: (1) One of our variant outperforms FL in most of the cases in CIFARIO and CIFAR100. (2) There no consistent winner between Transductive- -SBBS and Inductive-SuBSELNN although Inductive-SUBer SUBSEL.ET outperforms both Transducive-SURSSE... and FL. consistently in CIFARI00 100 in terms of the Jaccard coefficient.
Transductiv-SSuuSeNN
Subbelive-SubSelNee
FL
0.5
1.0
0.8-
Caellecieat
0.4
Coeffecieut
Coeffocient
Jaccard
Jaceard
0.3
0.2
0.4
300
600
1800
3000
250
500
1500
2500
250
500
1500
2500
Subset. Sizo
Subeet Size
Subeet Size
0.8
0.7
0.6
f
0.6-
0.6
M 0.4
0.4
1800 3000
0.2
250
1500
2500
0.4
250
1500
2500
Subset Size +
Subset Size -
Subset Size -
(a) FMNIST
(b) CIFAR10
(c) CIFARI00
Figure 10: Comparison of the top three non-adaptive subset selectors (Transductive-Suee) Inductive-SuB.. SUB FL) ranking and choosing of the top-15 architectures the basis of Jaccard Coefficient and Kendall tau rank correlation coefficient (K,).
D.3 AVOIDING UNDERFITTING AND OVERFITTING
Since the amount of training data is small, there is possibility of overfitting. However, the coefficient À of the entropy regularizer X. (Prr), can be increased to draw instances from the different regions 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 Transductive-SusSSHt and SELLN in [
We make the following observations:
1. From training to test, 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%.
We perform early stopping using the validation set which acts as an additional regularizer and therefore, the amount of overfitting is significantly low.
20

---

Under review as a conference paper at ICLR 2023
Table 11: Variation of accuracy with subset size of both the variants of SUBSELNET on training, validation and test set of CIFAR10
Training
Validation
Testing
Subset Size
Transductive
Inductive
Transductive
Inductive
Transductive
Inductive
10%
0.728
0.660
0.702
0.632
0.678
0.606
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
70%
0.942
0.738
0.912
0.717
0.884
0.698
D.4 PERFORMANCE OF SUBSET SELECTION STRATEGIES ON LARGER SUBSET SIZES
We conducted similar experiments Section 5.1 for CIFARIO and FMNIST larger subset sizes (b) of 0.1 D). D) 0.4 and 0.7 DJ For each dataset and the above mentioned subset sizes, we evaluate the decrease in accuracy (ratio of the accuracy on the subset accuracy the full dataset), speed-up (ratio of the time taken to train the full dataset to the sum of times taken for subset selection and subset training), and GPU usage in GB-min. We report the variation of these metries with respect to the subset sizes in the following tables
Table 12: Decrease accuracy (Accuracy on selected subset/Accuracy on full data) for CIFARIO and FMNIST for b E (..1
Subset Size
Transductive
Inductive
Faclooc
Pruning
GLJSTER
GradMatch
GraNd
BL.2N
10%
0.70
0.69
0.56
0.40
0.78
0.72
0.28
0.70
0.81
0.61
0.87
0.79
CIFARIO
40%
0.86
0.80
0.78
0.78
0.93
0.93
0.39
0.85
70%
0.93
0.87
0.85
0.88
0.96
0.96
0.71
0.91
10%
0.92
0.90
0.86
0.42
0.95
0.95
0.35
0.91
20%
0.94
0.91
0.90
0.62
0.96
0.96
0.40
0.93
FMNIST
40%
0.95
0.92
0.93
0.73
0.97
0.97
0.50
0.95
0.96
0.95
0.97
0.97
0.79
0.96
Table 13: Speed-up (Time for full training/(Time taken for subset selection + Training on the selected subset)) for CIFAR10 and FMNIST for (0.1 OI7
Subset Size
Dataset
Transductive
Inductive
Facl.oc
Pruning
GLISTER
GradMatch
GraNd
BL.2N
10%
24.13
24.13
5.89
16.81
6.15
7.23
17.76
17.76
20%
11.82
11.83
4,70
9.74
4.19
4.91
10.06
10.06
CIFARIO
40%
5.75
5.75
3.31
5.21
2.69
3.20
5.29
5.29
3.43
3.23
1.72
2.07
3.26
3.26
10%
25.68
25.67
4.32
15.60
7.70
7.77
12.28
12.28
20%
10.57
10.57
3.48
8.35
5.42
5.47
7.29
7.29
FMNIST
40%
6.04
6.04
2,79
5.24
3,30
3.04
4.81
4.81
70%
3.38
3.38
2.05
3.12
1.96
2.30
2.96
2.96
21

---

Under review as a conference paper at ICLR 2023
Table 14: GPU memory (GB-min) for CIFARIO and FMNIST for (0.1]))00.7|D)
Subset Size
Datasct
Transductive
Inductive
FacLoc
Pruning
GLISTER
GradMatch
GraNd
EL2N
10%
32.66
32.65
461.77
41.41
370.08
314.87
67.80
107.70
20%
66.65
66.64
495.75
74.88
543.75
463.62
101.26
190.19
CIFARIO
40%
137.15
137.13
566.26
144.31
847.87
711.67
170.69
361.32
70%
229.97
229.95
659.07
235.73
1326.46
1101.66
262.11
586.65
10%
23.73
23.73
641.65
32.21
168.70
167.32
88.69
87.85
20%
57.64
57.64
675.56
66.12
239.84
237.38
122.60
121.76
FMNIST
40%
100.85
100.85
718.77
109.32
394.35
427.87
165.80
164.97
70%
180.03
180.04
797.95
188.50
664.70
565.88
244.98
244.15
Note that in the case of CIFAR10, we denote the decrease factors of 0.91-0.96 in green, and the decrease factors of 0.85 0.88 in purple. In case of FMNIST, we denote the decrease factors of 0.94-0.97 in green and the decrease factors of 0.90 0.93 in purple. We make the following observations:
1. We show a better trade-off between accuracy and time and accuracy and memory than almost all the baselines.
2. Observations CIFARIO: When we tuned the subset sizes, we notice that SURTE GLISTER, Grad-Match and EI.2N can achieve comparable decrease factor of 0.91-0.93. In terms of speed-up and memory usage, we see that
(a) SUBSELNET achieves 1.3x speed-up compared to GLISTER and 1.1x speed-up as compared to Grad-Match and EL2N
(b) GLISTER consumes 3.7x GPU memory, Grad-Match consumes 3.1x GPU memory and EL2N consumes 2.5x GPU memory as compared to SUBSELNET
We notice that none of the other subset selection strategies achieve high-enough accuracy, and we beat them in terms of speed-up and memory usage. Moreover, for the case when the subset selection methods achieve a decrease factor of 0.85 0.88, we see that
(a) SUBSELNET achieves a 2.4x speed-up as compared to FacLoc, 1.8x speed-up as compared to Pruning, 1.4x speed-up as compared to GLISTER, 1.2x speed-up as compared to Grad-Match and 1.1x speed-up compared to EL2N
(b) FacLoc consumes consumes 4x GPU memory, Grad-Match consumes 3.4x GPU memory and EL2N consumes 2.6x GPU memory as compared SUBSELNET.
GPU memory, Pruning consumes 1.7x GPU memory, GLISTER
3. Observations in FMNIST: When tuned the subset sizes, notice that SUBSELNET, Facloc, GLISTER, Grad-Match and EL2N can achieve a comparable decrease factor of 0.94-0.97. In terms of speed-up and memory usage, see that
(a) SUBSEL achieves a 3.8x speed-up as compared to FacLoc, 1.4x speed-up as compared GLISTER and Grad-Match, and 2.2x speed-up as compared EL2N. (b) FacLoc consumes 12.5x GPU Memory, and GLISTER, Grad-Match and EL2N con- sume 2.9x GPU memory compared SUBSELNET.
We notice that none of the other subset selection strategies achieve high-enough accuracy, and we beat them in terms of speed-up up and memory usage. Moreover, for the case when the subset selection methods achieve a decrease factor of 0.90-0.93, we see that (a) NET achieves 7.4x speed-up as compared to Facloc, 2.1x speed-up as compared to GLISTER, 2.9x speed-up compared to Grad-Match and 2 speed-up as compared to EL2N
(b) FacLoc consumes 28.5x GPU memory, GLISTER consumes 4.5x GPU memory, Grad- Match consumes 6.1x GPU memory and EL2N consumes 3.7x GPU memory as compared to SUBSELNET.
We present the trade-off between the accuracy and speed-up, and accuracy and memory consumption
in Figure 15
22

---

Under review as a conference paper at ICLR 2023
Transductive-SubeelNe.
FI. Pruning
GLISTER Grad-Match
GraNd EL2N
Industivee-SubSelNNe
1.0
1.0
full selection:
t
0.8
0.8
(1.0, 0.96)
full selection: (1.0, 0.97)
=
0.6
0.6
Pr(y
Pr(y
0.4
0.4
0.20
0.2
10
20
30
40
10
20
30
Speed up (T₃/T)
+
Speed up (T
1.0
1.0
0.8
0.8
0.6
0.6
Pr(y
full selection:
Pr(y
0.4
(2.1 X 10 0.97)
0.4
full selection:
(2.4 x 10 0.96)
0.2
0.2
50
250
450
650
850
100
400
700 1000 1300
memory (t)dt (GB-min)
S
memory (t) (GB-min) +
(a) FMNIST
(b) CIFARIO
Figure 15: Trade off between accuracy and speedup (top row) and accuracy and memory consumption (bottom row) for all the methods Facility location (Fujishige 2005 Iyer 2015). Pruning (Sorscher
et al. 2022). Glister (Killamsetty al. 2021b). Grad-Match (Killameetyy et al. 2021ab. EL2N (Paul
et al. 2021 ;; GraNd (Paul et al. (021): y); and; Full selection on FMNIST and CIFARTO. In all cases,
vary [S] E (0.T]2],00.) 0.7 D)).
E
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 following reasons
1. Message passing between the nodes (which may be the input, output, any of the operations) allows 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 a large extent.
2. It has been shown by (Morris et al. 2019) and (Xu et al. 201 Sa) that GNNs are powerful as the Weisfeiler-Lehman algorithm and thus give a powerful representation for the graph. Thus, obtain smooth embeddings of the nodes/edges that 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 it operates on only the nodes and edges the structure of the architecture and does not the parameter values input data.
However, the GNN faces the following drawbacks
1. GNN symmetric aggregator for message passing over node neighbors ensure that the representation of any node should be invariant to permutation its neighbors. Such symmetric aggregator renders it low-pass filter, shown in (NT & Maehara 2019). which attenuates important gigh-frequency signals.
2. We are training one GNN using several architectures. This can lead 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 s output can significantly change. However, the embedding of GNN may become immune to such changes, since the GNN is being trained over many architectures.
23

---

Under review as a conference paper at ICLR 2023
F CHOICE OF SUBMODULAR FUNCTION FOR THE OPTIMIZATION PROBLEM
In (T we introduced the original combinatorial problem for subset selection where optimization variable S- the subset of instances makes the underlying problem combinatorial. Here, can use submodular functions like Graph-Cut, Facility-Location and Jog-Determinant as the diversity functions, which would allow us use greedy algorithms maximize the objective in I But, as discussed in Section 4.1 this suffers from two bottlenecks - lack of generalizability. Therefore, we do not follow these approaches and resort to our proposed approach called SUBSELNET.
expensive computation issues and
In contrast to the optimization problem in ( which was combinatorial set optimization problem, the optimization problem in SUBSELNETT is continuous optimization problem where the goal to estimate Pr.. In such a problem, where the probability distribution is the key optimization variable, entropy is more natural measure of diversity than the other submodular measures.
24


Reviews:
[{"review_id": "t7S7LPqaZQ", "reviewer": "Reviewer_a8HM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a SUBSELNET to select a subset of training data. SUBSELNET is a non-adaptive method as it is agnostic to model architecture and training stage and. The authors design a neural model approximator to approximate the output of any given architecture. Two variants of subset sampler are proposed.  SUBSELNET is compared against state-of-the-art methods on three datasets to demonstrate the tradeoff advantage between accuracy and speed up.", "summary_of_the_review": "I would recommend weak rejection because of the experiment results. It is hard to judge the effectiveness of the proposed method when all methods exhibit significant accuracy drops.  I would increase my score if the authors could demonstrate the efficiency advantage of the proposed method at no or negligible accuracy loss. ", "strength_and_weaknesses": "Strength:\n\n(1)\tWell-motivated problem. Data selection for an unseen architecture is an important problem with real-world impact.\n\nWeakness:\n\n(1)\tThe main problem of this work is the experiment. The authors choose 0.5% and 5% of training data, however, with such a low subsample rate, we notice a dramatic accuracy drop in Figure 1.  It is hard to judge the effectiveness of any methods with such a significant accuracy drop. The experiment should reflect at what speed up, the model can maintain the same accuracy. Essentially, focusing on the left side of Figure 1. The authors may consider a larger range of sampling rates (5%, 10%, 20%,30%, 40%, 50%, 60%, 70%), following the setup of previous work such as GraNd and Gister. \n\nQuestion:\n\n(1)\tWhen calculating inference time, are you assume selection and training are conducted in sequential? Is it possible to perform selection in parallel with training when loading a batch of data?\n\n(2)\tWhat is the training cost of training the model approximator? Have the authors evaluated the approximator error? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nzK5ddbTsE0", "reviewer": "Reviewer_B3Rj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors present SUBSELNET - a non- adaptive subset selection framework for solving a particular aspect of subset selection problem - improving generalizability of the subset selection approach; with existing methods, the algorithm has to be executed from the beginning for each new model.\nThe authors introduce an attention based neural approach that uses the graph structure of the architectures, which is then used to build subset samplers. Their approach has 2 variants: transductive and inductive.\nThey claim that their approach is more efficient than the existing approaches since the subset is chosen at the beginning of the training process, and the entire dataset is not required through the training process. ", "summary_of_the_review": "The approach overall is interesting since, they are able to preselect the dataset for the training process. The authors introduce an attention based neural approach that uses the graph structure of the architectures, which is then used to build subset samplers. Their approach has 2 variants: transductive and inductive. They claim that their approach is more efficient than the existing approaches since the subset is chosen at the beginning of the training process, and the entire dataset is not required through the training process.\n\nOverall, there are a few areas that are not clear from the paper, including the implementation and the evaluation of the approach. ", "strength_and_weaknesses": "The authors have provided the motivation for the problem, and presented the solution to address the problem. They have also evaluated their approach against 6 other approaches, and 3 different datasets, showing the speed up and memory utilization. \nThe approach overall is interesting since, they are able to preselect the dataset for the training process. \n\nHowever, there are a few areas that are not clear from the paper.\n1. It would have been great if the authors spent more time discussing the pros- and cons- of their graph network. In general, graph networks themselves can be large, slow and memory consuming. It seems like the comparison is performed on the output of the graph network rather than the end-to-end approach.\nThe details about the GNN and the graph embedding are important.\n\n2. Much of the details, including the step-by-step algorithm and the details are added to the appendix. For instance, the diagram in appendix B and Pseudocode in C, both would have helped understand the paper better, if it was in the main text.\n\n3. Since the approach relies on pre-selecting, it is not clear how the approach is able to avoid overfitting or underfitting. The authors have split the data into train, validation and test sets. Including a report on the accuracy on these datasets, and the time/ computation resources required for these would have been helpful.\n\n4. The loss function (eq 1) and the objective functions (5 and 6) require more explanation. For intance, the authors state in page 3 after eq1 that: \"One can use submodular functions (Fujishige, 2005; Iyer, 2015) like Facility Location, graph cut, or Log-Determinants to model DIVERSITY(S)\". However, they havent mentioned the approach they have used in the paper. \nLater, they mention the use of entropy on the subset sampler H(Prπ(•)) to model the diversity in page 4 after eq 5 and  KL after eq 6. The choice of the functions needs to be elaborated to appreciate the approach better. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "b6R2wmRkGK3", "reviewer": "Reviewer_VJSk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In  this paper,  a new non-adaptive data subset selection method is proposed. The traditional adaptive method mixed the training and  subset selection. While for the new proposed method, the subset processing is done before the training. Furthermore, the paper also proposed the transductive and inductive variants. The experimental results verified that both variants output perform the baselines on subset selection and also an be used to choose the best architecture.\n", "summary_of_the_review": "In summary I think this paper makes a good presentation on a new method for the non-adaptive methods and verifies the contributions in the experimental studies. It will be better to fix some annotations and have more ablation studies and show more results.", "strength_and_weaknesses": "This paper has a clear decomposition on the model into parts including model approximator and subset sampler. And for each part, it has clear annotations to explain the whole process. \nFor the subset sampler, 2 variants are proposed and the experimental results show the tradeoff between them, and furthermore, a combination of these 2 variants are tested too.\nThe comprehensive experimental results proved the effectiveness of the proposed method.\nSome questions:\n1. some writing errors such as “viz.” appeared a couple of times.\n2. both formula (5) and (6) has the E_S, is that correct? \n3. for the E_S optimization objective such as (6), as the parameter \\pi is under the prob distribution and needs sampling, how do you optimize the \\pi? do you use some reparameterization trick which is now shown in the paper.\n4. Can you elaborate more on why you don’t jointly optimize the gnn parameter and transformer parameter?\n5. In the experimental setup, the paper mentions all the baselines are non-adaptive, is it correct?\n6. Do you have any results to show the accuracy gap between the neural model approximator and the fully trained model?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject