GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning

Introduction

With the quest to achieve human-like performance for machine learning and deep learning systems, the cost of training and deploying machine learning models has been significantly increasing. The wasted computational and engineering energy becomes evident in deep learning algorithms, wherein extensive hyper-parameter tuning and network architecture search need to be done. This results in staggering compute costs and running timeshttps://medium.com/syncedreview/the-staggering-cost-of-training-sota-ai-models-e329e80fa82.

As a result, efficient and robust machine learning is a very relevant and substantial research problem. In this paper, we shall focus on three goals: Goal 1: Train machine learning and deep learning models on effective subsets of data, thereby significantly reducing training time and compute while not sacrificing accuracy. Goal 2: To (iteratively) select effective subsets of labeled data to reduce the labeling cost. Goal 3: Select data subsets to remove noisy labels and class imbalance, which is increasingly common in operational machine learning settings.

A number of papers have studied data efficient training and robust training of machine learning and deep learning models. However, the area of data efficient training of models that are also robust is relatively under-explored. Below, we summarize papers based on efficiency and robustness.

Reducing Training Time and Compute (Data Selection): A number of recent papers have used submodular functions as proxy functions (Wei, Iyer, and Bilmes 2014; Wei et al. 2014b; Kirchhoff and Bilmes 2014; Kaushal et al. 2019). These approaches have been used in several domains including speech recognition (Wei et al. 2014a, b; Liu et al. 2015), machine translation (Kirchhoff and Bilmes 2014), computer vision (Kaushal et al. 2019), and NLP (Bairi et al. 2015). Another common approach uses coresets. Coresets are weighted subsets of the data, which approximate certain desirable characteristics of the full data (e.g., the loss function) (Feldman 2020). Coreset algorithms have been used for several problems including $k$-means clustering (Har-Peled and Mazumdar 2004), SVMs (Clarkson 2010) and Bayesian inference (Campbell and Broderick 2018). Coreset algorithms require specialized (and often very different algorithms) depending on the model and problem at hand and have had limited success in deep learning. A very recent coreset algorithm called Craig (Mirzasoleiman, Bilmes, and Leskovec 2020), which tries to select representative subsets of the training data that closely approximate the full gradient, has shown promise for several machine learning models. The resulting subset selection problem becomes an instance of the facility location problem (which is submodular). Another data selection framework, which is very relevant to this work, poses the data selection problem as that of selecting a subset of the training data such that the resulting model (trained on the subset) perform well on the full dataset (Wei, Iyer, and Bilmes 2015). (Wei, Iyer, and Bilmes 2015) showed that the resulting problem is a submodular optimization problem for the Nearest Neighbor (NN) and Naive Bayes (NB) classifiers. The authors empirically showed that these functions worked well for other classifiers, such as logistic regression and deep models (Kaushal et al. 2019; Wei, Iyer, and Bilmes 2015).

Reducing Labeling Cost (Active Learning): Traditionally, active learning techniques like uncertainty sampling (US) and query by committee (QBC) have shown great promise in several domains of machine learning (Settles 2009). However, with the emergence of batch active learning (Wei, Iyer, and Bilmes 2015; Sener and Savarese 2018), simple US and QBC approaches do not capture diversity in the batch. Among the approaches to diversified active learning, one of the first approaches was Filtered Active Submodular Selection (FASS) (Wei, Iyer, and Bilmes 2015) that combines the uncertainty sampling method with a submodular data subset selection framework to label a subset of data points to train a classifier. Another related approach (Sener and Savarese 2018) defines active learning as a core-set selection problem and has demonstrated that the model learned over the $k$-centers of the dataset is competitive to the one trained over the entire data. Very recently, an algorithm called Badge (Ash et al. 2020) sampled groups of points that have a diverse and higher magnitude of hypothesized gradients to incorporate both predictive uncertainty and sample diversity into every selected batch.

Robust Learning: A number of approaches have been proposed to address robust learning in the context of noise, distribution shift and class imbalance. Several methods rely on reweighting training examples either by knowledge distillation from auxilliary models (Han et al. 2018; Jiang et al. 2018; Malach and Shalev-Shwartz 2017) or by using a clean held out validation set (Ren et al. 2018; Zhang and Sabuncu 2018). In particular, our approach bears similarity to the learning to reweight framework (Ren et al. 2018) wherein the authors try to reweight the training examples using a validation set, and solve the problem using a online meta-learning based approach.

Submodular Functions: Since several of the data selection techniques use the notion of submodularity, we briefly introduce submodular functions and optimization. Let $V=\{1,2,\cdots,n\}$ denote a ground set of items (for example, in our case, the set of training data points). Set functions are functions $f:2^{V}\rightarrow\mathbf{R}$ that operate on subsets of $V$. A set function $f$ is called a submodular function (Fujishige 2005) if it satisfies the diminishing returns property: for subsets $S\subseteq T\subseteq V,f(j|S)\triangleq f(S\cup j)-f(S)\geq f(j|T)$. Several natural combinatorial functions such as facility location, set cover, concave over modular, etc., are submodular functions (Iyer 2015; Iyer et al. 2020). Submodularity is also very appealing because a simple greedy algorithm achieves a $1-1/e$ constant factor approximation guarantee (Nemhauser, Wolsey, and Fisher 1978) for the problem of maximizing a submodular function subject to a cardinality constraint (which most data selection approaches involve). Moreover, several variants of the greedy algorithm have been proposed which further scale up submodular maximization to almost linear time complexity (Minoux 1978; Mirzasoleiman et al. 2014, 2013).

Our Contribution

Most prior work discussed above, either study robustness or efficiency, but not both. For example, the data selection approaches such as (Wei, Iyer, and Bilmes 2015; Mirzasoleiman, Bilmes, and Leskovec 2020; Shinohara 2014) and others focus on approximating either gradients or performance on the training sets, and hence would not be suitable for scenarios such as label noise and imbalance. On the other hand, the approaches like (Ren et al. 2018; Jiang et al. 2018) and others, focus on robustness but are not necessarily efficient. For example, the approach of (Ren et al. 2018) requires 3x the standard (deep) training cost, to obtain a robust model. Glister is the first framework, to the best of our knowledge, which focuses on both efficiency and robustness. Our work is closely related to the approaches of (Wei, Iyer, and Bilmes 2015) and (Ren et al. 2018). We build upon the work of (Wei, Iyer, and Bilmes 2015), by first generalizing their framework beyond simple classifiers (like nearest neighbor and naive bayes), but with general loss functions. We do this by proposing an iterative algorithm Glister-Online which does data selection via a meta-learning based approach along with parameter updates. Furthermore, we pose the problem as optimizing the validation set performance as opposed to training set performance, thereby encouraging generalization. Next, our approach also bears similarity to (Ren et al. 2018), except that we need to solve a discrete optimization problem instead of a meta-gradient update. Moreover, we do not run our data selection every iteration, thereby ensuring that we are significantly faster than a single training run. Finally, we extend our algorithm to the active learning scenario. We demonstrate that our framework is more efficient and accurate compared to existing data selection and active learning algorithms, and secondly, also generalizes well under noisy data, and class imbalance scenarios. In particular, we show that Glister achieves a 3x - 6x speedup on a wide range of models and datasets, with very small loss in accuracy.

Problem Formulation

Notation: Denote ${\mathcal{U}}$ to be the full training set with instances $\{(x^{i},y^{i})\}_{i\in{\mathcal{U}}}$ and ${\mathcal{V}}$ to be a held-out validation set $\{(x^{i},y^{i})\}_{i\in{\mathcal{V}}}$. Define $L(\theta,S)=\sum_{i\in S}L(\theta,x^{i},y^{i})$ as the loss on a set $S$ of instances. Denote $L_{T}$ as the training loss, and hence $L_{T}(\theta,{\mathcal{U}})$ is the full training loss. Similarly, denote $L_{V}$ as the validation loss (i.e. $L_{V}(\theta,{\mathcal{V}})$ as the loss on the validation set ${\mathcal{V}}$). In this paper, we study the following problem:

Equation (1) tries to select a subset $S$ of the training set ${\mathcal{U}}$, such that the loss on the set ${\mathcal{V}}$ is minimized. We can replace the loss functions $L_{V}$ and $L_{T}$ with $\log$-likelihood functions $LL_{V}$ and $LL_{T}$ in which case, the argmin becomes argmax:

Finally, we point out that we can replace $L_{V}$ (or $LL_{V}$) with the training loss $L_{T}$ (or log-likelihood $LL_{T}$), in which case we get the problem studied in (Wei, Iyer, and Bilmes 2015). The authors in (Wei, Iyer, and Bilmes 2015) only consider simple models such as nearest neighbor and naive bayes classifiers.

Special Cases: We start with the naive bayes and nearest neighbor cases, which have already been studied in (Wei, Iyer, and Bilmes 2015). We provide a simple extension here to consider a validation set instead of the training set. First consider the naive bayes model. Let $m_{x_{j},y}(S)=\sum_{i\in S}1[x^{i}_{j}=x_{j}\wedge y_{j}=y]$ and $m_{y}(S)=\sum_{i\in S}1[y_{j}=y]$. Also, denote ${\mathcal{V}}^{y}\subseteq{\mathcal{V}}$ as a set of the validation instances with label $y$. Furthermore, define $w(i,j)=d-||x^{i}-x^{j}||^{2}_{2}$, where $d=\max_{i,j}||x^{i}-x^{j}||^{2}_{2}$. We now define two submodular functions. The first is the naive-bayes submodular function $f_{NB}^{v}(S)=\sum_{j=1:d}\sum_{x_{j}\in\mathcal{X}}\sum_{y\in\mathcal{Y}}m_{x_{j},y}({\mathcal{V}})\log m_{x_{j},y}(S)$, and the second is the nearest-neighbor submodular function: $f^{NN}_{V}(S)=\sum_{y\in\mathcal{Y}}\sum_{i\in{\mathcal{V}}^{y}}\max_{s\in S\cap{\mathcal{V}}^{y^{i}}}w(i,s)$.

The following Lemma analyzes Problem (2) in the case of naive bayes and nearest neighbor classifiers.

Maximizing equation (2) in the context of naive bayes and nearest neighbor classifiers is equivalent to optimizing $f^{NB}_{V}(S)$ and $f^{NN}_{V}(S)$ under the constraint that $|S\cap{\mathcal{V}}^{y}|=k\frac{|{\mathcal{V}}^{y}|}{|{\mathcal{V}}|}$ with $|S|=k$, which is essentially a partition matroid constraint.

This result is proved in the Appendix, and follows a very similar proof technique from (Wei, Iyer, and Bilmes 2015). However, in order to achieve this formulation, we make a natural assumption that the distribution over class labels in $S$ is same as that of $U$. Furthermore, the Lemma above implied that solving equation (2) is basically a form of submodular maximization, for the NB and NN classifiers. In the interest of space, we defer the analysis of Linear Regression (LR) and Gaussian Naive Bayes (GNB) to the appendix. Both these models enable closed form for the inner problem, and the resulting problems are closely related to submodularity.

Glister-Online Framework

In this section, we present Glister-Online, which performs data selection jointly with the parameter learning. This allows us to handle arbitrary loss functions $L_{V}$ and $L_{T}$. A careful inspection of equation (2) reveals that it is a nested bi-level optimization problem:

The outer layer, tries to select a subset from the training set ${\mathcal{U}}$, such that the model trained on the subset will have the best log-likelihood $LL_{V}$ on the validation set ${\mathcal{V}}$. Whereas in the inner layer, we optimize the model parameters by maximizing training log-likelihood $LL_{T}$ on the subset selected $S$. Due to the fact that equation (3) is a bi-level optimization, it is expensive and impractical to solve for general loss functions. This is because in most cases, the inner optimization problem cannot be solved in closed form. Hence we need to make approximations to solve the optimization problem efficiently.

Our first approximation is that instead of solving the inner optimization problem entirely, we optimize it by iteratively doing a meta-approximation, which takes a single step towards the training subset log-likelihood $LL_{T}$ ascent direction. This algorithm is iterative, in that it proceeds by simultaneously updating the model parameters and selecting subsets. Figure 1 gives a flowchart of Glister-Online. Note that instead of performing data selection every epoch, we perform data selection every $L$ epochs, for computational reasons. We will study the tradeoffs associated with $L$ in our experiments.

Glister-Online proceeds as follows. We update the model parameters $\theta_{t}$ on a subset obtained in the last subset selection round. We perform subset selection only every $L$ epochs, which we do as follows. At training time step $t$, if we take one gradient step on a subset $S$, we achieve: $\theta^{t+1}(S)=\theta^{t}+\eta\nabla_{\theta}LL_{T}(\theta^{t},S)$. We can then plug this approximation into equation (3) and obtain the following discrete optimization problem. Define $G_{\theta}(S)=LL_{V}(\theta+\eta\nabla_{\theta}LL_{T}(\theta,S),{\mathcal{V}})$ below:

Next, we show that the optimization problem (equation (4)) is NP hard.

There exists log-likelihood functions $LL_{V}$ and $LL_{T}$ and training and validation datasets, such that equation (4) is NP hard.

The proof of this result is in the supplementary material. While, the problem is NP hard in general, we show that for many important log-likelihood functions such as the negative cross entropy, negative logistic loss, and others, $G_{\theta^{t}}(S)$ is submodular in $S$ for a given $\theta^{t}$.

If the validation set log-likelihood function $LL_{V}$ is either the negative logistic loss, the negative squared loss, negative hinge loss, or the negative perceptron loss, the optimization problem in equation (4) is an instance of cardinality constrained submodular maximization. When $LL_{V}$ is the negative cross-entropy loss, the optimization problem in equation (4) is an instance of cardinality constrained weakly submodular maximization.

The proof of this result, along with the exact forms of the (weakly) submodular functions are in the supplementary material. Except for negative squared loss, the submodular functions for all other losses (including cross-entropy) are monotone, and hence the lazy greedy (Minoux 1978) or stochastic greedy (Mirzasoleiman et al. 2014) give $1-1/e$ approximation guarantees. For the case of the negative squared loss, the randomized greedy algorithm achieves a $1/e$ approximation guarantee (Buchbinder et al. 2014). The lazy greedy algorithm in practice is amortized linear-time complexity, but in the worst case, can have a complexity $O(nk)$. On the other hand, the stochastic greedy algorithm is linear time, i.e. it obtains a $1-1/e-\epsilon$ approximation in $O(n\log 1/\epsilon)$ iterations.

Before moving forward, we analyze the computational complexity of Glister-Online. Denote $m=|\mathcal{V}$ (validation set size), and $n=|\mathcal{U}|$ (training set size). Furthermore, let $F$ be the complexity of a forward pass and $B$ the complexity of backward pass. Denote $T$ as the number of epochs. The complexity of full training with SGD is $O(nTB)$. Using the naive (or lazy) greedy algorithm, the worst case complexity is $O(nkmFT/L+kTB)$. With stochastic greedy, we get a slightly improved complexity of $O(nmFT/L\log 1/\epsilon+kTB)$. Since $B\approx 2F$, and $m$ is typically a fraction of $n$ (like 5-10% of $n$), and $L$ is a constant (e.g. $L=20$), the complexity of subset selection (i.e. the first part) can be significantly more than the complexity of training (for large values of $n$), thereby defeating the purpose of data selection. Below, we study a number of approximations which will make the subset selection more efficient, while not sacrificing on accuracy.

Approximations:

We start with a simple approximation of just using the Last layer approximation of a deep model, while computing equation (4). Note that this can be done in closed form for many of the loss functions described in Theorem 1. Denote $f$ as the complexity of computing the function on the last layer (which is much lesser than $F$), the complexity of stochastic greedy is reduced to $O(nmfT/L\log 1/\epsilon+kTB)$. The reason for this is that Glister-Online tries to maximize $LL_{V}(\theta+\eta\sum_{j\in S}\nabla LL_{T}(\theta,j),\mathcal{V})$, and the complexity of evaluating $LL_{V}$ is $O(mf)$. Multiplying this by the complexity of the stochastic or naive greedy, we get the final complexity. While this is better than earlier, it can still be slow since there is a factor $nm$ being multiplied in the subset selection time. The second approximation we make is the Taylor series approximation, which computes an approximation $\hat{G}_{\theta}(S\cup e)$ based on the Taylor-series approximation. In particular, given a subset $S$, define $\theta^{S}=\theta+\eta\sum_{j\in S}\nabla LL_{T}(\theta,j)$. The Taylor-series approximation $\hat{G}_{\theta}(S\cup e)=LL_{V}(\theta^{S})+\eta\nabla_{\theta}LL_{T}(\theta,e)^{T}LL_{V}(\theta^{S},\mathcal{V})$. Note that $LL_{T}(\theta,e)$ can be precomputed before the (stochastic) greedy algorithm is run, and similarly $LL_{V}(\theta^{S},\mathcal{V})$ just needs to be computed once before picking the best $e\notin S$ to add. With the Taylor series approximation, the complexity reduces to $O(k[m+n]fT/L+kTB)$ with the naive-greedy and $O([km+n\log 1/\epsilon]fT/L+kTB)$ with the stochastic greedy. Comparing to without using the Taylor series approximation, we get a speedup of $O(m)$ for naive-greedy and $O(n\log 1/\epsilon/k)$ for the stochastic greedy, which can be significant when $k$ is much smaller than $n$ (e.g., 10% of $n$). With the Taylor series approximation, we find that the time for subset selection (for deep models) is often comparable in complexity to one epoch of full training, but since we are doing subset selection only every $L$ epochs, we can still get a speedup roughly equal to $n/k+1/L$. However, for shallow networks or 2 layer neural networks, the subset selection time can still be orders of magnitude slower than full training. In this case, we do one final approximation, which we call the $r$-Greedy Taylor Approximation. In this case, we re-compute the validation log-likelihood only $r$ times (instead of $k$). In other words, we use the stale likelihoods for $k/r$ greedy steps. Since we are using the same likelihood function, this becomes a simple modular optimization problem where we need to pick the top $k/r$ values. While in principle, this approximation can be used in conjunction with stochastic greedy, we find that the accuracy degradation is considerable, mainly because stochastic greedy picks the best item greedily from $O(n/k\log 1/\epsilon)$ random data instances, which can yield poor sets if a large number of items are selected every round of greedy (which is what happens in $r$-greedy). Rather, we use this in conjunction with naive-greedy. The complexity of the $r$-taylor approximation with naive-greedy algorithm is $O(r[m+n]fT/L+kTB)$. For smaller models (like one or two layer neural network models), we set $r=0.03k$ (we perform ablation study on $r$ in our experiments), thereby achieving 30x speedup to just the Taylor-series approximation. For deep models, since the complexity of the gradient descent increases (i.e. $B$ is high), we can use larger values of $r$, and typically set $r\approx k$. As we demonstrate in our experiments, even after the approximations presented above, we significantly outperform other baselines (including Craig and Random), and is comparable to full training while being much faster, on a wide variety of datasets and models.

Regularization with Other Functions

Note that since the optimization problem in equation (4) is an instance of submodular optimization, we can also regularize this with another data-selection approach. This can be particularly useful, if say, the validation dataset is small and we do not want to overfit to the validation loss. The regularized objective function is ($\lambda$ is a tradeoff parameter):

We consider two specific kinds of regularization functions $R(S)$. The first is the supervised facility location, which is basically NN-submodular function on the training set features (Wei, Iyer, and Bilmes 2015), and the second is a random function. The random function can be thought of as a small perturbation to the data selection objective.

Implementation Aspects

The detailed pseudo-code of the final algorithm is in Algorithm 1. GreedyDSS in Algorithm 1 refers to the greedy algorithms and approximations discussed above to solve equation (5). The parameters of GreedyDSS are: a) training set $\mathcal{U}$, validation set: $\mathcal{V}$, current parameters $\theta^{(t)}$, learning rate $\eta$, budget $k$, the parameter $r$ governing the number of times we do taylor-series approximation, and finally the regularization coefficient $\lambda$. In the interest of space, we defer the detailed algorithm to the supplementary material. We use the PyTorch (Paszke et al. 2017) framework to implement our algorithms. To summarize the implementation aspects, the main hyper-parameters which govern the tradeoff between accuracy and efficiency are $r,L$, the regularization function $R$, coefficient $\lambda$ and the choice of the greedy algorithm. For all our experiments, we set $L=20$. For our deep models experiments (i.e. more than 2-3 layers), we use just the Taylor-approximation with $r=k$ and stochastic greedy, while for shallow models, we use $r\approx 0.03k$ with the naive greedy. We perform ablation studies in Section Experimental Results to understand the effect of these parameters in experiments, and in particular, the choices of $r$ and $L$. We do not significantly tune $\lambda$ in the regularized versions and just set in a way so both components (i.e. the Glister loss and regularizer) have roughly equal contributions. See the supplementary material for more details of the hyper-parameters used.

Convergence Analysis

In this section, we study conditions under which Glister-Online reduces the objective value, and the conditions for convergence. To do this, we first define certain properties of the validation loss. A function $f(x):\mathcal{R}^{d}\rightarrow\mathcal{R}$ is said to be Lipschitz-smooth with constant $\mathcal{L}$ if $\|\nabla f(x)-\nabla f(y)\|\leq\mathcal{L}\|x-y\|,\forall x,y\in\mathcal{R}^{d}$. Next, we say that a function $f:\mathcal{R}^{d}\rightarrow\mathcal{R}$ has $\sigma$-bounded gradients if $\|\nabla f(x)\|\leq\sigma$ for all $x\in\mathcal{R}^{d}$

The following result studies conditions under which the validation loss reduces with every training epoch $l$.

Suppose the validation loss function $L_{V}$ is Lipschitz smooth with constant $\mathcal{L}$, and the gradients of training and validation losses are $\sigma_{T}$ and $\sigma_{V}$ bounded respectively. Then the validation loss always monotonically decreases with every training epoch $l$, i.e. $L_{V}(\theta_{l+1})\leq L_{V}(\theta_{l})$ if it satisfies the condition that $\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})^{T}\nabla_{\theta}L_{T}(\theta_{l},S)\geq 0$ for $0\leq l\leq T$ and the learning rate $\alpha\leq\min_{l}\frac{2\|\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})\|\cos(\Theta_{l})}{\mathcal{L}\sigma_{T}}$ where $\Theta_{l}$ is the angle between $\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})$ and $\nabla_{\theta}L_{T}(\theta_{l},S)$.

The condition basically requires that for the subset selected $S_{i}$, the gradient on the training subset loss $L_{T}(\theta_{l},S_{i})$ is in the same direction as the gradient on the validation loss $L_{V}(\theta_{l},{\mathcal{V}})$ at every epoch $l$. Note that in our Taylor-series approximation, we anyways select subsets $S_{i}$ such that the dot product between gradients of subset training loss and validation loss is maximized. So, as long as our training data have some instances that are similar to the validation dataset, our model selected subset $S_{i}$ should intuitively satisfy the condition mentioned in Theorem 2. We end this section by providing a convergence result.

The following theorem shows that under certain conditions, Glister-Online converges to the optimizer of the validation loss in $\mathcal{O}(1/{\epsilon}^{2})$ epochs.

Assume that the validation and subset training losses satisfy the conditions that $\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})^{T}\nabla_{\theta}L_{T}(\theta_{l},S)\geq 0$ for $0\leq l\leq T$, and for all the subsets encountered during the training. Also, assume that $\delta_{\min}=\min_{l}\frac{\nabla L_{T}(\theta_{l})}{\sigma_{G}}$. Then, the following convergence result holds:

Since our Taylor approximation chooses a subset that maximizes the dot-product between the gradients of the training loss and the validation loss, we expect that the angle between the subset training gradient and validation loss gradients be close to 0 i.e., $\cos{\theta_{l}}\approx 1$. Finally, note that $\delta_{\min}$ needs to be greater than zero, which is also reasonable, since having close to zero gradients on the subset gradients would imply overfitting to the training loss. In Glister-Online we only train on the subset for $L$ epochs, ensuring the training gradients on the subset do not go to zero.

Glister-Active Framework

In this section, we extend Glister to the active learning setting. We propose Glister-Active for the mini-batch adaptive active learning where we select a batch of B samples to be labeled for T rounds. This method is adaptive because samples selected in the current round are affected by the previously selected points as the model gets updated. The goal here is to select a subset of size B from the pool of unlabeled instances such that the subset selected has as much information as possible to help the model come up with an appropriate decision boundary. Glister-Active is very similar to Glister-Online except for three critical differences. First, the data-selection in Line 6 of Algorithm 1 is only on the unlabeled instances. Second, we use the hypothesized labels instead of the true labels in the greedy Taylor optimization (since we do not have the true labels). The usage of hypothesized labels(, i.e., predictions from the current model) is very similar to existing active learning approaches like Badge and Fass. Thirdly, instead of selecting $k$ examples every time and running only on that subset, Glister-Active selects a batch of $B$ instances over the unlabeled examples and adds it to the current set of labeled examples (after obtaining the labels). Similar to Glister-Online, we consider both the unregularized and regularized data selection objectives. In the interest of space, we defer the algorithm and other details to the supplementary material.

Experimental Results

Our experimental section aims to showcase the stability and efficiency of Glister-Online and Glister-Active on a number of real world datasets and experimental settings. We try to address the following questions through our experiments: 1) How does Glister-Online tradeoff accuracy and efficiency, compared to the model trained on the full dataset and other data selection techniques? 2) How does Glister-Online work in the presence of class imbalance and noisy labels? 3) How well does Glister-Online scale to large deep learning settings? and 4) How does Glister-Active compare to other active learning algorithms?

Baselines in each setting: We compare the following baselines to our Glister framework. We start with data selection for efficient training. 1. Random: Just randomly select $k$ (budget size) training examples. 2. CRAIG: We compare against CRAIG (Mirzasoleiman, Bilmes, and Leskovec 2020) which tries to approximate the gradients of the full training sets. 3. SS + FNN: This is the KNN submodular function from (Wei, Iyer, and Bilmes 2015), but using the training set. We do not compare to the NB submodular function, because as demonstrated in (Wei, Iyer, and Bilmes 2015) the KNN submodular function mostly outperformed NB submodular for non Naive-Bayes models. For the case of class imbalance and noisy settings, we assume that the training set is imbalanced (or noisy), while the validation set is balanced (or clean). For data selection experiments in this setting, we consider the baselines 1-3 above, i.e. CRAIG, Random and SS + FNN, but with some difference. First, we use a stronger version of the random baseline in the case of class imbalance, which ensures that the selected random set is balanced (and hence has the same class distibution as the validation set). For SS + FNN baseline, we select a subset from the training data using KNN submodular function, but using the validation set instead of the training set. In the case of noisy data, we consider 1, 2 and 4 as baselines for data selection. Finally, we consider the following baselines for active learning. 1. FASS: FASS algorithm (Wei, Iyer, and Bilmes 2015) selects a subset using KNN submodular function by filtering out the data samples with low uncertainty about predictions. 2. BADGE: BADGE algorithm (Ash et al. 2020) selects a subset based on the diverse gradient embedding obtained using hypothesized samples. 3. Random: In this baseline, we randomly select a subset at every iteration for the data points to be added in the labeled examples. For data selection, we consider two variants of Glister, one with the Facility Location as a regularized (F-Glister), and the second with random as a regularizer (R-Glister). In the case of active learning, we add one more which is diversity regularized (D-Glister), where the diversity is the pairwise sum of distances.

Datasets, Model Architecture and Experimental Setup: To demonstrate effectiveness of Glister-Online on real-world datasets, we performed experiments on DNA, SVMGuide, Digits, Letter, USPS (from the UCI machine learning repository), MNIST, and CIFAR-10. We ran experiments with shallow models and deep models. For shallow models, we used a two-layer fully connected neural network having 100 hidden nodes. We use simple SGD optimizer for training the model. The shallow model experiments were run on the first five datasets, while on MNIST and CIFAR-10 we used a deep model. For MNIST, we use LeNet model (LeCun et al. 1989), while for CIFAR-10, we use ResNet-18 (He et al. 2016). Wherever the datasets do not a validation set, we split the training set into a train (90%) and validation set (10%).

Data Selection for Efficient Learning: We begin by studying the effect of data selection for efficiency (i.e., to reduce the amount of training time and compute). For this purpose, we compare for different subset sizes of 10%, 30%, 50% in the shallow learning setting. We demonstrate the results on MNIST and CIFAR-10 (for deep learning). In the supplementary material, we show results on the other datasets (i.e., the UCI datasets). The results are shown in Figure 2 (top row). The first two plots (i.e., a and b) show that Glister and its variants significantly outperform all other baselines (including Craig and Random). To make Craig comparable to Glister, we run the data selection with $L=20$ (i.e. every 20 epochs). This is mainly due to computational reasons since when run every epoch, our implementation of Craig was much slower than full training, effectively defeating the purpose of data selection. We also included Craig Every baseline for the MNIST dataset, which is CRAIG run every epoch to showcase the performance of CRAIG run every epoch. From the results, we observed that GLISTER still performs better than CRAIG run every epoch for MNIST data selection. We also observe that with just 50% of the data, Glister achieves comparable accuracy to full training. We also note that facility location and random selection regularization help, particularly for larger subsets, by avoiding the overfitting to the validation set. What is also encouraging that Glister-Online performs well even at very small subset sizes, which is important for data selection (e.g., for doing hyper-parameter turnings several times on very small subsets). Perhaps surprisingly, Craig performs very poorly at small data-sizes. Plots c and d show the timing results on CIFAR-10 and MNIST. We see that on CIFAR-10, Glister achieves a 6x speedup at 10%, 2.5x speedup at 30%, and 1.5x speedup at 50%, while loosing 3%, 1.2% and 0.2% respectively in accuracy. Similarly, for MNIST, we see a 3x speedup at 10% subset, with a loss of only 0.2% in accuracy. This timing also includes the subset selection time, thereby making the comparison fair. Robust Data Selection: To check our model’s generalization performance when adversaries are present in training data, we run experiments in class imbalance and Noisy label settings for the datasets mentioned above. We artificially generate class-imbalance for the above datasets by removing 90% of the instances from 30% of total classes available. For noisy data sets, we flip the labels for a randomly chosen subset of the data where the noise ratio determines the subset’s size. In our experimental setting, we use a 30% noise ratio for the noisy experiments. The class imbalance setting results are shown in Figure 2 e,f, and g for CIFAR-10, MNIST, and DNA. The results demonstrate that Glister-Online again significantly outperforms the other baselines. We note that two of the baselines (random with prior and KNN-submodular with validation set information) have knowledge about the imbalance. It is also worth noting that for CIFAR-10, R-Glister achieves a significant improvement over the other baselines (by around 7%) for subset sizes 30% and 50%. Figure 2 h shows the results of a noisy setting in the DNA dataset. On the smaller dataset DNA, Glister and its variants outperform even full training, which is again not surprising because the full data has noise. In contrast, our approach essentially filters out the noise through its data selection. Glister and its variants outperform other baselines by more than 10%, which is very significant. We provide additional results for both the class imbalance and noisy settings in the supplementary material and show similar gains on the other five smaller datasets.

Active Learning: Next, we compare Glister-Active to state-of-the-art active learning algorithms including FASS and Badge. The results are shown in Figure 3 (right two plots) on SVM-Guide, Letter, and DNA datasets. Again, we see that Glister and its variants (particularly, with diversity) outperform the existing active learning baselines, including Badge, which is currently the state-of-the-art batch active learning algorithm. Since Badge and FASS have been shown to outpeform techniques like uncertainty Sampling (Settles 2009) and Coreset based approaches (Sener and Savarese 2018), we do not compare them in this work. In our supplementary material we compare our algorithms on many more datasets and also consider active learning in the class imbalance scenario.

Ablation Study and Speedups: We conclude the experimental section of this paper by studying the different approximations. We compare the different versions of Taylor approximations in Figure 4 and study the effect of $L$ and $r$ on the DNA dataset. In the supplementary material, we provide the ablation study for a few more datasets. For the ablation study with $L$, we study $L=20,35$ and $50$. For smaller values of $L$ (e.g., below 20, we see that the gains in accuracy are not worth the reduction in efficiency), while for larger values of $L$, the accuracy gets affected. Similarly, we vary $r$ from $1$ to $20$ (which is 5% of $k$ on DNA dataset). We observe that $L=20$ and $r=3$% of $k$ generally provides the best tradeoff w.r.t time vs accuracy. Thanks to this choice of $r$ and $L$, we see significant speedups through our data selection, even with smaller neural networks. For example, we see a 6.75x speedup on DNA, 4.9x speedup on SVMGuide, 4.6x on SatImage, and around 1.5x on USPS and Letter. Detailed ablation studies on SVMGuide, DNA, SatImage, USPS, and Letter are in the supplementary.

Conclusion

We present Glister, a novel framework that solves a mixed discrete-continuous bi-level optimization problem for efficient training using data subset selection while pivoting on a held-out validation set likelihood for robustness. We study the submodularity of Glister for simpler classifiers and extend the analysis to our proposed iterative and online data selection algorithm Glister-Online, that can be applied to any loss-based learning algorithm. We also extend the model to batch active learning (Glister-Active). For these variants of Glister, on a wide range of tasks, we empirically demonstrate improvements (and associated trade-offs) over the state-of-the-art in terms of efficiency, accuracy, and robustness.

References

Appendix A Proof of NP-Hardness (Lemma 2)

In this section, we prove the NP-Hardness of the data selection step (equation (4)), thereby proving Lemma 2

There exists log-likelihood functions $LL_{V}$ and $LL_{T}$ and training and validation datasets, such that equation (4) is NP hard.

We prove that our subset selection problem is NP-hard by proving that an instance of our data selection step can be viewed as set cover problem.

Our subset selection optimization problem is as follows:

Let $(x_{i},y_{i})$ be the $i^{th}$ data-point and $x_{i}\in\mathcal{R}^{d}$ in the validation set $\mathcal{V}$ where $i\in[1,|\mathcal{V}|]$. Let $(x_{i}^{t},y_{i}^{t})$ be the $i^{th}$ data-point and $x_{i}^{t}\in\mathcal{R}^{d}$ in the training set $\mathcal{U}$ where $i\in[1,|\mathcal{U}|]$. Let $k$ be the number of classes and $\theta$ be the model parameter. We assume that the number of training points is equal to the number of features in the training data point i.e.,$|\mathcal{U}|=d$.

Assuming our validation log-likelihood is of the form $LL_{V}(\theta,\mathcal{V})=\sum_{i=1}^{\mathcal{V}}\min(y_{i}\theta^{T}x_{i},1)$ and that all the data-points in the validation set $\mathcal{V}$ have a label value of 1 i.e., $\forall i,y_{i}=1$. Also assume that our validation data point vector is of form $x_{i}=[w_{1i},w_{2i},...,w_{di}]$. As we shall see below, the $w$ vector actually comes from our set-cover instance (i.e. given an instance of a weighted set cover, we can obtain an instance of our problem). Also, note that the loss function above is a shifted version of negative hinge loss, since $-LL_{V}(\theta,\mathcal{V})=\sum_{i=1}^{\mathcal{V}}-\min(y_{i}\theta^{T}x_{i},1)=\sum_{i=1}^{\mathcal{V}}\max(-y_{i}\theta^{T}x_{i},-1)=\sum_{i=1}^{\mathcal{V}}[\max(1-y_{i}\theta^{T}x_{i},0)-1]$

We assume our model to be of simple linear form $y_{i}=\theta^{T}x_{i}$ and our model parameters to be a zero-vector i.e., $\theta^{0}=0$. We also make an assumption that our training set is in such a form that the log-likelihood gradients for $i^{th}$ data-point is a one-hot encoded vector such that $i^{th}$ feature in the vector is equal to 1. Let us denote this one encoder vector using $1_{i}$. Under the above assumptions, our subset-selection optimization problem is as follows:

The above equation (8) is a instance of Set-Cover Problem which is ”NP-hard”. Hence, we have proved that an instance of our subset selection problem can be viewed as set cover problem.

Therefore, we can say that there exist log-likelihood functions $LL_{V}$ and $LL_{T}$ and training and validation datasets, such that equation (4) is NP hard. ∎

Appendix B Proof of Submodularity of the Data Selection in Glister-Online (Theorem 1)

In this section, we prove the submodularity of the data selection step (equation (4)) with a number of loss functions, thereby proving Theorem 1. For convenience, we first restate Theorem 1.

If the validation set log-likelihood function $LL_{V}$ is either the negative logistic loss, the negative squared loss, nagative hinge loss or the negative perceptron loss, the optimization problem in equation (4) is an instance of cardinality constrained non-monotone submodular maximization. When $LL_{V}$ is the negative cross-entropy loss, the optimization problem in equation (4) is an instance of cardinality constrained weakly submodular maximization.

We start with the negative-logistic loss. Let $(x_{i},y_{i})$ be the $i^{th}$ data-point in the validation set $\mathcal{V}$ where $i\in[1,|\mathcal{V}|]$ and $(x_{i}^{t},y_{i}^{t})$ be the $i^{th}$ data-point in the training set $\mathcal{U}$ where $i\in[1,|\mathcal{U}|]$. Let $\theta$ be the model parameter.

For convenience, we again provide the discrete optimization problem (equation (4)). Define $G_{\theta}(S)=LL_{V}(\theta+\alpha\nabla_{\theta}LL_{T}(\theta,S),{\mathcal{V}})$. Then, the optimization problem is

Note that we can express $LL_{T}(\theta,S)$ as $-\log{L_{T}(\theta,S)}$ and $-\log{LL_{V}(\theta,\mathcal{V})}$ as $-\log{L_{V}(\theta,\mathcal{V})}$ where $L_{T}$ is training loss and $L_{V}$ is validation loss. The lemma below, shows that this is a submodular optimization problem, if the likelihood function $LL_{V}$ is the negative logistic loss.

If the validation set log-likelihood function $LL_{V}$ is the negative logistic loss, then optimizing $G_{\theta^{t}}(S)$ under cardinality constraints is an instance of cardinality constrained monotone submodular maximization.

For simplicity of notation, we assume our starting point is $\theta_{0}$ instead of $\theta_{t}$. Also, we will use $G(S)$ instead of $G_{\theta_{0}}(S)$. Given this, and since $LL_{V}$ is a negative logistic loss, the optimization problem can be written as:

To the above equation we can add a term $L_{MAX}$ to make the entire second term positive. Since the term $L_{MAX}$ is going to be constant it doesn’t affect our optimization problem.

Let, $g_{ij}={-\nabla_{\theta}L_{T}(x_{j}^{t},y_{j}^{t},\theta_{0})}^{T}x_{i}y_{i}$,

We can transform to $g_{ij}$ to a new variable $g^{{}^{\prime}}_{ij}$ such that $g_{ij}=g_{min}+g^{{}^{\prime}}_{ij}$ where $g_{min}=\underset{i,j}{\min}g_{ij}$. The above transformation ensures that $g^{{}^{\prime}}_{ij}\geq 0$.

Let $\exp(-y_{i}\theta_{0}^{T}x_{i})=c_{i}$ and we know that $c_{i}\geq 0$,

Since we are considering an subset selection of selecting an subset $S$ where $|S|=k$, we convert our set function $G(S)$ to a proxy set function $\hat{G}(S)$,

Where we define $C_{i}=c_{i}\exp(-\alpha kg_{min})$ in the last equation. Note that $g(x)=-\log(1+C\exp(-x))$ is a concave function in $x$ (since $C>0$), and given that $g^{{}^{\prime}}_{ij}\geq 0,\forall i,j$, the function above is a concave over modular function, which is submodular. Note that $g(x)$ is also monotone, and hence $\hat{G}(S)$ is in fact a monotone submodular function. Finally, since we have a cardinality constraint, the optimal solution (as well as the greedy solution) of $\hat{G}(S)$ and $G(S)$ will be the same since they will both be of size $k$. Hence, maximizing $\hat{G}(S)$ is the same as maximizing $G(S)$ under cardinality constraint, which is equivalent to maximizing the likelihood function with the negative logistic loss under cardinality constraints. ∎

Negative Squared Loss

Similar to the negative logistic loss case, define the notation as follows. Let $(x_{i},y_{i})$ be the $i^{th}$ data-point in the validation set $\mathcal{V}$ where $i\in[1,|\mathcal{V}|]$ and $(x_{i}^{t},y_{i}^{t})$ be the $i^{th}$ data-point in the training set $\mathcal{U}$ where $i\in[1,|\mathcal{U}|]$. Let $k$ be the number of classes and $\theta$ be the model parameter. Define $G_{\theta}(S)=LL_{V}(\theta+\eta\nabla_{\theta}LL_{T}(\theta,S),{\mathcal{V}})$. Then, recall that the optimization problem is

Note that we can express $LL_{T}(\theta,S)$ as $-L_{T}(\theta,S)$ and $LL_{V}(\theta,\mathcal{V})$ as $-L_{V}(\theta,\mathcal{V})$ where $L_{T}$ is training loss and $L_{V}$ is validation loss. The lemma below, shows that this is a submodular optimization problem, if the likelihood function $LL_{V}$ is the negative squared loss. Finally, note that we have cardinality equality constraint (i.e. the set must have exactly $k$ elements) instead of less than equality. It turns out that the cardinality equality constraint is required in this case, because the resulting function is non-monotone, and this requirement will become evident in the proof below.

If the validation set log-likelihood function $LL_{V}$ is the negative squared loss, then the problem of optimizing $G_{\theta^{t}}(S)$ under a constraint $|S|=k$ is an instance of cardinality constrained non-monotone submodular maximization.

Again, for convenience, we assume we start at $\theta_{0}$, and we use $G(S)$ instead of $G_{\theta_{0}}(S)$. With the negative squared loss, the optimization problem becomes:

Since, $\nabla_{\theta}L_{V}(x_{i},y_{i},\theta_{0})=-2(y_{i}-x_{i}^{T}\theta_{0})(x_{i})$ when $L_{V}$ is squared loss.

Assuming $S_{jk}=\sum_{i=1}^{|\mathcal{V}|}(x_{i}^{T}\nabla_{\theta}L_{T}(x_{j}^{t},y_{j}^{t},\theta_{0}))(x_{i}^{T}\nabla_{\theta}L_{T}(x_{k}^{t},y_{k}^{t},\theta_{0}))$, we have:

Since, $S_{jk}$ is not always greater than zero, we can transform it to $\hat{S}_{jk}$ such that ${S}_{jk}=\hat{S}_{jk}+S_{min}$ where $S_{min}=\underset{j,k}{\min}S_{jk}$. This transformation ensures that $\hat{S}_{jk}\geq 0$.

Since we are considering an subset selection of selecting an subset $S$ where $|S|=K$, we convert our set function $G(S)$ to a proxy set function $\hat{G}(S)$,

In the above equation, the first part $(-\sum_{i=1}^{|\mathcal{V}|}\left\|(y_{i}-x_{i}^{T}\theta_{0})\right\|^{2}-\alpha^{2}K^{2}{S}_{min})$ is constant and does not depend on subset $S$. The second part $\alpha\sum_{j=1}^{|S|}\sum_{i=1}^{|\mathcal{V}|}\nabla_{\theta}L_{V}(x_{i},y_{i},\theta_{0})^{T}\nabla_{\theta}L_{T}(x_{j}^{t},y_{j}^{t},\theta_{0})$ is a non-monotone modular in subset $S$. Note that the third part $-\alpha^{2}\sum_{j=1}^{|S|}\sum_{k=1}^{|S|}\hat{S}_{jk}$ is similar to a graph cut function since $\hat{S}_{jk}\geq 0$. Hence it is a sub-modular function.

Therefore, the proxy set function $\hat{G}(S)$ is a non-monotone constrained submodular function. Finally, note that under a cardinality equality constraint, optimizing $G(S)$ is the same as optimizing $\hat{G}(S)$ since the solution by the randomized greedy algorithm and the optimal solution will both be of size $k$. Finally, note that fast algorithms exist for non-monotone submodular maximization under cardinaltity equality constraints (Buchbinder et al. 2014). ∎

Negative Hinge Loss and Negative Perceptron Loss

Again, we define the notation. Let $(x_{i},y_{i})$ be the $i^{th}$ data-point in the validation set $\mathcal{V}$ where $i\in[1,|\mathcal{V}|]$ and $(x_{i}^{t},y_{i}^{t})$ be the $i^{th}$ data-point in the training set $\mathcal{U}$ where $i\in[1,|\mathcal{U}|]$. Let $k$ be the number of classes and $\theta$ be the model parameter. Define $G_{\theta}(S)=LL_{V}(\theta+\eta\nabla_{\theta}LL_{T}(\theta,S),{\mathcal{V}})$. Then, recall that the optimization problem is

Note that we can express $LL_{T}(\theta,S)$ as $-L_{T}(\theta,S)$ and $LL_{V}(\theta,\mathcal{V})$ as $-L_{V}(\theta,\mathcal{V})$ where $L_{T}$ is training loss and $L_{V}$ is validation loss. The lemma below, shows that this is a submodular optimization problem, if the likelihood function $LL_{V}$ is the negative hinge loss (or negative perceptron loss).

If the validation set log-likelihood function $LL_{V}$ is the negative hinge loss (or negative perceptron loss), then the problem of optimizing $G_{\theta^{t}}(S)$ under cardinality constraints is an instance of cardinality constrained monotone submodular maximization.

Similar to the proofs earlier, we assume we start at $\theta_{0}$, and we use $G(S)$ instead of $G_{\theta_{0}}(S)$. With the negative hinge loss, we obtain the following problem:

Note that the expression for the Perceptron loss is similar, except for the $1$ in the Hinge Loss. Hence, we just prove it for the Hinge loss. Next, define $c_{i}=-1+y_{i}x_{i}^{T}\theta_{0}$ and $g_{ij}=-y_{i}x_{i}^{T}\nabla_{\theta}L_{T}(x_{j}^{t}.y_{j}^{t},\theta_{0})$,

Since, $g_{ij}$ is not always greater than zero, we can transform it to $\hat{g}_{ij}$ such that ${g}_{ij}=\hat{g}_{ij}+g_{min}$ where $g_{min}=\underset{i,j}{\min}g_{ij}$. This transformation ensures that $\hat{g}_{ij}\geq 0$.

Since we are considering an subset selection of selecting an subset $S$ where $|S|=K$, we convert our set function $G(S)$ to a proxy set function $\hat{G}(S)$,

Note that $g(x)=\min\left(0,C+x\right)$ is a concave function in $x$ and given that $\hat{g}_{ij}\geq 0$, the function above is a concave over modular function, which is sub-modular. Note that $g(x)$ is also a monotone function, and hence the above proxy set function $\hat{G}(S)$ is a monotone constrained sub-modular function. Finally, because $\hat{G}(S)$ is a monotone function, the optimal solution as well as the greedy solution will both achieve sets of size $K$, and hence optimizing $\hat{G}(S)$ is equivalent to optimizing $G(S)$ (under cardinality constraints), which is the problem of optimizing the likelihood function with the negative hinge loss. We can obtain a very similar expression for the negative perceptron loss, with the only difference that $c_{i}=y_{i}x_{i}^{T}\theta_{0}$ instead of $c_{i}=-1+y_{i}x_{i}^{T}\theta_{0}$. ∎

Negative Cross Entropy Loss

Let $(x_{i},y_{i})$ be the $i^{th}$ data-point in the validation set $\mathcal{V}$ where $i\in[1,|\mathcal{V}|]$ and $(x_{i}^{t},y_{i}^{t})$ be the $i^{th}$ data-point in the training set $\mathcal{U}$ where $i\in[1,|\mathcal{U}|]$. Let $k$ be the number of classes and $\theta$ be the model parameter. Define $G_{\theta}(S)=LL_{V}(\theta+\eta\nabla_{\theta}LL_{T}(\theta,S),{\mathcal{V}})$. Then, recall that the optimization problem is

Note that we can express $LL_{T}(\theta,S)$ as $-L_{T}(\theta,S)$ and $LL_{V}(\theta,\mathcal{V})$ as $-L_{V}(\theta,\mathcal{V})$ where $L_{T}$ is training loss and $L_{V}$ is validation loss. Unlike the negative logistic, squared and hinge loss cases, with the negative cross-entropy loss, the optimization problem above is no longer submodular. However, as we show below, it is approximately submodular. Before stating the result, we first recall the definition of approximate submodularity.

Definition: A function is called $\beta$-submodular (Gatmiry and Gomez-Rodriguez 2018), if the gain of adding an element $e$ to set $X$ is $\beta$ times greater than or equals to the gain of adding an element $e$ to set $Y$ where $X$ is a subset of $Y$. i.e.,

While this definition is different from the notion of approximate submodularity (Das and Kempe 2011). However, they are closely related since (following Proposition 4 in (Gatmiry and Gomez-Rodriguez 2018)), the approximate submodularity parameter $\gamma\geq\beta$. This immediately implies the following result:

(Das and Kempe 2011; Gatmiry and Gomez-Rodriguez 2018) Given a $\beta$-approximate monotone submodular function $G$, the greedy algorithm achieves a $1-e^{-\beta}$ approximation factor for the problem of maximizing $G$ subject to cardinality constraints.

Next, we show that $G_{\theta_{t}}(S)$ is a $\beta$-approximate submodular function. To do this, first define $R$ as the largest value of $||x_{i}||$ in the validation and training datasets (i.e. we assume that the norm of the feature vectors are bounded). Note that this is common assumption made in most convergence analysis results. Then, we show that with the cross entropy loss, $G_{\theta_{t}}(S)$ is a $\beta$-approximate with $\beta=1/(2R^{2}+1)$.

If the validation set log-likelihood function $LL_{V}$ is the negative cross entropy loss and training set loss function $L_{T}$ is cross entropy loss, then the optimization problem in equation (4) is an instance of cardinality constrained $\beta$-approximate submodular maximization, where $\beta=1/(2R^{2}+1)$ ($R$ satisfies $||x_{i}||\leq R$ for the training and validation data).

Before proving our result, we note that if we normalize the features to have a norm of $1$, the approximation guarantee is $1-e^{-0.3}$.

Similar to the proofs earlier, we assume we start at $\theta_{0}$, and we use $G(S)$ instead of $G_{\theta_{0}}(S)$. With the negative cross entropy loss, we obtain the following problem:

Since, the term $(\theta_{0}^{y_{i}})^{T}x_{i}$ does not depend on the subset $S$, we can remove it from our optimization problem,

Assume $g_{ijk}=\nabla_{\theta}{L_{T}(x_{j}^{t},y_{j}^{t},\theta_{0}^{k})}^{T}x_{i}$,

Let $c_{ik}=\exp(\theta_{0}^{k^{T}}x_{i})$ and also note that $c_{ik}\geq 0$.

Since $g_{ijk}$ is not always greater than zero, we need to make some transformations to convert the problem into a monotone submodular function. First, we define a transformation of $g_{ijk}$ to $g_{ijk}^{{}^{\prime}}$ such that $g_{ijk}=g^{{}^{\prime}}_{ijk}+g_{min}-1$ where $g_{min}=\underset{i,j,k}{\min}g_{ijk}$. This transformation ensures that $g_{ijk}^{{}^{\prime}}\geq 1$. Also, define $g_{negmin}=\underset{i,j,k}{\min}(-g_{ijk})$, and then we define a transformation of $g_{ijk}$ to $g_{ijk}^{{}^{\prime\prime}}$ such that $-g_{ijk}=g^{{}^{\prime\prime}}_{ijk}+g_{negmin}$. Note that both $g^{{}^{\prime}}_{ijk}$ and $g^{{}^{\prime\prime}}_{ijk}$ are greater than or equal to zero after these transformations.

Since we are considering an subset selection of selecting an subset $S$ where $|S|=K$, we convert our set function $G(S)$ to a proxy set function $\hat{G}(S)$.

Next, define $C_{ik}=c_{ik}\exp(K(g_{min}-1))$. Also, since $\alpha|\mathcal{V}|K(g_{negmin})$ is a constant, we can remove it from the optimization problem and we can define:

In the above equation, the first part $G_{1}(X)=\sum_{i=1}^{|\mathcal{V}|}\sum_{j\in S}\alpha(g^{{}^{\prime\prime}}_{ijy_{i}})$ is monotone modular function in $S$. The second part $G_{2}(X)=-\sum_{i=1}^{|\mathcal{V}|}\log\left(\sum_{k}C_{ik}\exp(-\alpha\sum_{j\in S}(g^{{}^{\prime}}_{ijk}))\right)$ is a monotone function, but is unfortunately not necessary submodular. In the next part of this proof, we focus on this function and show that it is $\beta$-submodular. Moreover, since the first part is positive modular, it is easy to see that if $G_{2}(X)$ is $\beta$ submodular (for $\beta<1$), $G_{1}(X)+G_{2}(X)$ will also be $\beta$-submodular. To show this, recall that a function $h(X)$ is $\beta$-submodular if $h(j|X)\geq\beta h(j|Y)$ for all subsets $X\subseteq Y$. If we assume that $G_{2}$ is $\beta$-submodular, then it will hold that $G_{2}(j|X)\geq\beta G_{2}(j|Y)$ for all subsets $X\subseteq Y$. Furthermore, since $G_{1}$ is modular, it holds that $G_{1}(j|X)=G_{1}(j|Y)\geq\beta G_{1}(j|Y)$ since $G_{1}$ is positive modular. Hence $G_{1}+G_{2}$ is $\beta$-submodular.

First notice that $G_{2}(e|X)$ of adding an element $e$ to set $X$ is:

where $g^{{}^{\prime}}_{min}=\underset{i,j,k}{\min}g^{{}^{\prime}}_{ijk}$. This then implies:

where $g^{{}^{\prime}}_{max}=\underset{i,j,k}{\max}g^{{}^{\prime}}_{ijk}$. This implies that:

So, from the above two bounds on $G_{2}(e|X)$, we have:

Since, $g_{ijk}=\nabla_{\theta}L_{T}(x_{j}^{t},y_{j}^{t},\theta_{0}^{k})^{T}x_{i}$ and $g^{{}^{\prime}}_{ijk}=g_{ijk}-g_{min}+1$, we have:

Since, $L_{T}$ is also a cross-entropy loss, we know that $\nabla_{\theta}L_{T}(x_{j}^{t},y_{j}^{t},\theta_{0}^{k})=(1_{y_{j}}-p)x_{j}$ where $1_{y_{j}}=1$ when $k=y_{j}$ for final layer parameters. Hence,

Similarly, the norm of validation set data points is bounded by R, and therefore we obtain that $g^{{}^{\prime}}_{min}=1$ and $g^{{}^{\prime}}_{max}=2R^{2}+1$. As a result,

Hence, this implies that $G_{2}$ is $\beta$ submodular with $\beta=\frac{1}{2R^{2}+1}$, which further implies that $\hat{G}$ is $\beta$-submodular. Finally, we are interested in the constraint that $|S|=K$, the optimal solution as well as the greedy solution will both obtain sets of size $K$ and hence the optimizer of $G$ will be the same as the optimizer of $\hat{G}$. Hence the greedy algorithm will achieve a $1-e^{-\beta}$ approximation factor, for the data selection step with the cross entropy loss. ∎

Appendix C Convergence of Glister-Online and Reduction in Objective Value

This section provides the proof for Theorem 2 and Theorem 3.

Suppose the validation loss function $L_{V}$ is Lipschitz smooth with constant L, and the gradients of training and validation losses are $\sigma_{T}$ and $\sigma_{V}$ bounded respectively. Then the validation loss always monotonically decreases with every training epoch $l$, i.e. $L_{V}(\theta_{l+1})\leq L_{V}(\theta_{l})$ if it satisfies the condition that $\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})^{T}\nabla_{\theta}L_{T}(\theta_{l},S)\geq 0$ for $0\leq l\leq T$ and the learning rate $\alpha\leq\min_{l}\frac{2\|\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})\|\cos(\Theta_{l})}{L\sigma_{T}}$ where $\Theta_{l}$ is the angle between $\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})$ and $\nabla_{\theta}L_{T}(\theta_{l},S)$.

Suppose we have a validation set $\mathcal{V}$ and the loss on the validation set is $L_{V}(\theta,\mathcal{V})$. Suppose the subset selected by the Glister-Online framework is denoted by $S$ and the subset training loss is $L_{T}(\theta,S)$. Since validation loss $L_{V}$ is lipschitz smooth, we have,

Since, we are using SGD to optimize the subset training loss $L_{T}(\theta,S)$ model parameters our update equations will be as follows:

Plugging our updating rule (Eq. (66)) in (Eq. (65)):

Since we know that ${\left\|\nabla_{\theta}L_{T}(\theta_{l},S)\right\|}^{2}\geq 0$, we will have the necessary condition $\nabla_{\theta}^{T}L_{V}(\theta_{l},\mathcal{V})\nabla_{\theta}L_{T}(\theta_{l},S))\geq 0$.

We can also re-write the condition in (Eq:(69)) as follows:

The Eq:(70) gives the necessary condition for learning rate i.e.,

The above Eq:(71) can be written as follows:

Since, we know that the gradient norm $\left\|\nabla_{\theta}L_{T}(\theta_{l},S)\right\|\leq\sigma_{T}$, the condition for the learning rate can be written as follows,

Since, the condition mentioned in Eq:(73) needs to be true for all values of $l$, we have the condition for learning rate as follows:

Convergence Result

Assume that the validation and subset training losses satisfy the conditions that $\nabla_{\theta}L_{V}(\theta_{l},{\mathcal{V}})^{T}\nabla_{\theta}L_{T}(\theta_{l},S)\geq 0$ for $0\leq l\leq T$, and for all the subsets encountered during the training. Also, assume that $\delta_{\min}=\min_{l}\frac{\left\|\nabla L_{T}(\theta_{t})\right\|}{\sigma_{G}}$ and the parameters satisfy $||\theta||\leq\frac{R}{2}$. Then, with a learning rate set to $\alpha=\frac{R}{\sigma_{T}\sqrt{T}}$, the following convergence result holds:

Suppose the validation loss $L_{V}$ and training loss $L_{T}$ be lipschitz smooth and the gradients of validation loss and training loss are sigma bounded by $\sigma_{V}$ and $\sigma_{T}$ respectively. Let $\theta_{l}$ be the model parameters at epoch $l$ and $\theta^{*}$ be the optimal model parameters. From the definition of Gradient Descent, we have:

We can rewrite the function ${\nabla_{\theta}L_{T}(\theta_{l})}^{T}(\theta_{l}-\theta^{*})$ as follows:

Combining the equations Eq:(77) ,Eq:(78) we have,

Assuming $\delta_{min}=\min_{l}\delta_{l}$ and summing up the Eq:(80) for different values of $l\in[1,T-1]$ we have,

Since ${\left\|\theta_{T}-\theta^{*}\right\|}^{2}\geq 0$, we have:

We know that $L_{V}(\theta_{l})-L_{V}(\theta^{*})\leq{\nabla_{\theta}L_{V}(\theta_{l})}^{T}(\theta_{l}-\theta^{*})$ from convexity of function $L_{V}(\theta)$. Combining this with above equation we have,

Since, $\left\|L_{T}(\theta)\right\|\leq\sigma_{T}$ and assuming that $\left\|\theta-\theta^{*}\right\|\leq R$, we have,

Assuming $\delta_{l}=\frac{\left\|\nabla_{\theta_{l}}L_{T}(\theta_{l})\right\|}{\left\|\nabla_{\theta_{l}}L_{V}(\theta_{l})\right\|}$, we can write as follows:

Since $\left\|\nabla_{\theta}L_{T}(\theta_{l})(1-\cos(\Theta_{l}))+\widehat{\nabla_{\theta}L_{T}(\theta_{l})}\sin(\Theta_{l})\right\|\leq\left\|\nabla_{\theta}L_{T}(\theta_{l})\right\|\sqrt{1-\cos(\Theta_{l})}$, we have:

Since $\left\|\nabla_{\theta}L_{T}(\theta)\right\|\leq\sigma_{T}$, we have:

Choosing $\alpha=\frac{R}{\sigma_{T}\sqrt{T}}$, we have:

Since, $\min_{l}(L_{V}(\theta_{l})-L_{V}(\theta^{*}))\leq\frac{\sum_{l=1}^{T-1}L_{V}(\theta_{l})-L_{V}(\theta^{*})}{T}$, we have:

Therefore, we conclude that our algorithm will converge in $\mathcal{O}(1/\sqrt{T})$ steps when the validation data and training data are from similar distributions since $\cos(\Theta_{l})\approx 1$. ∎

Appendix D Derivation of Closed Form Expressions for Special Cases

In this section, we derive the closed form expressions of the special cases discussed in section Problem Formulation.

We consider the case of discrete naive bayes model and see how the log likelihood function for the training and validation look like in terms of parameters obtained from a subset of training data.

Some notation: The training data set is ${\mathcal{U}}=\{(x^{i},y^{i})\}_{i=1:m}$ with each $x^{i}$ being a d-dimensional vector with values from the set $\mathcal{X}$. Similarly each label $y^{i}\in\mathcal{Y}$ and $\mathcal{Y}$ is a finite label set. We can think of ${\mathcal{U}}$ as being partitioned on the basis of labels: ${\mathcal{U}}=\cup_{y\in{\mathcal{Y}}}{\mathcal{U}}^{y}$ where ${\mathcal{U}}^{y}$ is the set of data points whose label = $y$. We calculate the (MLE) parameters $\theta(S)$ of the model on subset $S\subseteq{\mathcal{U}}$. These involve the conditional probabilities $\theta_{x_{j}|y}(S)$ for a feature $x_{j}$ (along each dimension $j=1..d$) given a class label $y$ and the prior probabilities for each class label $\theta_{y}(S)$