Data Summarization via Bilevel Optimization

Let us consider a supervised setting with data set $\mathcal{D}=\{(x_{i},y_{i})\}_{i=1}^{n}$ and let us introduce the nonnegative weight vector $w=[w_{1},\dots,w_{n}]\in{\mathbb{R}}_{+}^{n}$ for representing the coreset $C_{w}$. Here, $(x_{i},y_{i},w_{i})\in C_{w}$ iff $w_{i}>0$, i.e., points with $0$ weights are not part of the coreset. Let us denote the model by $h$, its parameters by $\theta$ and let $\ell$ be the loss function. Furthermore, for brevity, let $\ell_{i}(\theta):=\ell(h_{\theta}(x_{i}),y_{i})$.

We can formalize our coreset requirement stated in the introduction: we want to find a coreset $C_{\hat{w}}$ of size $m$ such that if we solve the weighted empirical risk minimization (ERM) problem on the coreset, $\theta_{\hat{w}}^{*}\in\operatorname*{arg\,min}_{\theta}\sum_{i=1}^{n}\hat{w}_{i}\ell_{i}(\theta)$, then $\theta_{\hat{w}}^{*}$ is a good solution for the ERM problem on the full data set $\min_{\theta}\sum_{i=1}^{n}\ell_{i}(\theta)$. We can write this optimization problem as

where the $m$-sparse vector $\hat{w}$ indicates the selected points’ indices and weights at nonzero positions. We note that, although we formulated the problem in the supervised setting, the construction can be easily adapted to semi-supervised and unsupervised settings, as we will demonstrate in Section 5. Problem (1) is an instance of bilevel optimization, where we minimize an outer objective, here $\sum_{i=1}^{n}\ell_{i}(\theta^{*}(w))$, which in turn depends on the solution $\theta^{*}(w)$ to an inner optimization problem $\operatorname*{arg\,min}_{\theta}\sum_{i=1}^{n}w_{i}\ell_{i}(\theta)$. Before presenting our proposed algorithm for solving (1), we discuss some background on bilevel optimization and its importance in machine learning.

Modeling hierarchical decision-making processes (von Stackelberg and Peacock, 1952; Vicente and Calamai, 1994), bilevel optimization has witnessed an increasing popularity in machine learning recently. Bilevel optimization has found applications ranging from meta-learning (Finn et al., 2017; Li et al., 2017), to hyperparameter optimization (Pedregosa, 2016; Franceschi et al., 2018) and neural architecture search (Liu et al., 2019).

Suppose $g:\Theta\times\Omega\rightarrow{\mathbb{R}}$ and $f:\Theta\times\Omega\rightarrow{\mathbb{R}}$ are continuous functions, then we call

a bilevel optimization problem with the outer (upper level) objective $\min_{w}\!g(\theta^{*}\!(w),w)$ and the inner (lower level) objective $\theta^{*}\!(w)\!\in\!\operatorname*{arg\,min}_{\theta}\!f(\theta,w)$.

Bilevel programming, even in the linear case, is generally NP-hard (Vicente et al., 1994). Despite the challenge of non-convexity, first-order methods for solving bilevel optimization problems are successful in many applications (Finn et al., 2017; Pedregosa, 2016; Liu et al., 2019). A common simplifying assumption for achieving asymptotic convergence guarantees is that the inner problem’s solution set in Equation (2) is a singleton (Franceschi et al., 2018), fulfilled if $f$ is strongly convex in $\theta$.

First-order bilevel optimization solvers can be further categorized based on how they evaluate or approximate the implicit gradient $\nabla_{w}G(w)$, for which it is necessary to consider the change of the best response $\theta^{*}$ as a function of $w$. The first class of approaches defines a recurrence relation $\theta_{t}=\varphi(\theta_{t-1},w)$: the recurrence is unrolled, truncated to $T$ steps, and $\nabla_{w}G(w)$ is approximated by differentiation through the unrolled iterations either by forward- or reverse-mode automatic differentiation (Franceschi et al., 2017). Whereas choosing a small number of unrolling steps $T$ can potentially introduce bias in the gradient estimation (Wu et al., 2018), a large $T$ can incur a high computational cost (either in time or space complexity) when $\Theta$ and $\Omega$ are high-dimensional.

The second class of first-order bilevel optimization solvers obtain the gradient implicitly: under the assumption that $f$ is twice differentiable, the constraint $\theta^{*}(w)\in\operatorname*{arg\,min}_{\theta\in\Theta}f(\theta,w)$ can be relaxed to $\frac{\partial f(\theta,w)}{\partial\theta}\big{|}_{\theta=\theta^{*}}=0$, which is tight when $f$ is strictly convex. A crucial result for obtaining $\nabla_{w}G(w)$ is the implicit function theorem applied to $\frac{\partial f(\theta,w)}{\partial\theta}\big{|}_{\theta=\theta^{*}}=0$. Combined with the total derivative and the chain rule, we get

where the partial derivatives with respect to $\theta$ are evaluated at $\theta^{*}(w)$. However, the Hessian inversion in Equation (3) is computationally intractable for models with a large number of parameters. Efficient inverse Hessian-vector product approximations can be obtained by approximately solving the linear system $\frac{\partial^{2}f}{\partial\theta\partial\theta^{\top}}x=\left(\frac{\partial g}{\partial\theta}\right)^{\top}$ with conjugate gradients (Pedregosa, 2016) or by approximating the inverse Hessian with the Neumann series $\left(\frac{\partial^{2}f}{\partial\theta\partial\theta^{\top}}\right)^{-1}=\lim_{T\to\infty}\sum_{i=0}^{T}\left(I-\frac{\partial^{2}f}{\partial\theta\partial\theta^{\top}}\right)^{i}\quad$ (Lorraine et al., 2020). These approximations enable the scalability of first-order optimization methods based on implicit gradients to high-dimensional $\Theta$ and $\Omega$.

In this work, we use the framework of bilevel optimization to generate coresets. We assume that $f$ is twice differentiable and that the inner solution set is a singleton. We use first-order methods based on implicit gradients for solving our proposed bilevel optimization problems due to their flexibility and scalability.

In the previous section, we presented different approaches for solving bilevel optimization problems. However, an additional challenge in our coreset formulation (1) is the cardinality constraint $||w||_{0}\leq m$. One approach for this combinatorial problem would be to treat $G$ as a set function and increment the set of selected points greedily by inspecting marginal gains. Unfortunately, for general losses, this approach comes at a high cost: at each step, we must solve the bilevel optimization problem of finding the optimal weights for each candidate point we consider to add to the coreset. This makes greedy selection based on marginal gains impractical for large models.

We propose an efficient solution summarized in Algorithm 1 based on cone constrained generalized matching pursuit (Locatello et al., 2017). Consider the atom set $\mathcal{A}$ corresponding to the standard basis of ${\mathbb{R}}^{n}$. Similarly to the Frank-Wolfe algorithm, generalized matching pursuit proceeds by incrementally increasing the active set of atoms that represents the solution by selecting the atom that minimizes the linearization of the objective at the current iteration. Growing the atom set incrementally can be stopped when the desired size $m$ is reached, and thus the $\left\|w\right\|_{0}\leq m$ constraint is active. We note that, by imposing a bound on the weights and optimizing in the convex hull of atoms, this approach would be equivalent to the Frank-Wolfe algorithm, which has already been applied in coreset constructions in settings where $G(w)$ is convex (Clarkson, 2010). The novelty in our work is the bilevel formulation that allows to extend this simple approach to general twice-differentiable models.

Suppose a set of atoms $S_{t-1}\subset\mathcal{A}$ of size $t-1$ has already been selected. Our method proceeds in two steps. First, the bilevel optimization problem (1) is restricted to weights $w$ having support $S_{t-1}$, i.e., $w$ can only have nonzero entries at indices in $S_{t-1}$. Then we optimize to find the weights $w_{S_{t-1}}^{*}$ with support restricted to $S_{t-1}$ that represent a local minimum of $G(w)$ defined in Eq. (2) with $g(\theta^{*}(w),w)=\sum_{i=1}^{n}\ell_{i}(\theta^{*}(w))$ and $f(\theta,w)=\sum_{i=1}^{n}w_{i}\ell_{i}(\theta)$—i.e., we use the algorithm’s corrective variant, where, once a new atom is added, the weights are reoptimized by gradient descent using the implicit gradient with projection to nonnegative weights (line 6 in Algorithm 1). Once these weights are found, the algorithm increments $S_{t-1}$ with the atom that minimizes the first-order Taylor expansion of the outer objective around $w_{S_{t-1}}^{*}$,

where $e_{k}$ denotes the $k$-th standard basis vector of ${\mathbb{R}}^{n}$. In other words, the chosen point is the one with the largest negative implicit gradient.

We can gain insight into the selection rule in Equation (4) by expanding $\nabla_{w}G$ using Equation (3). For this, we use the inner objective $f(\theta,w)=\sum_{i=1}^{n}w_{i}\ell_{i}(\theta)$ without regularization for simplicity. Noting that $\frac{\partial^{2}\sum_{i=1}^{n}w_{i}\ell_{i}(\theta)}{\partial w_{k}\partial\theta^{\top}}=\nabla_{\theta}\ell_{k}(\theta)$, we can expand Equation (4) to get

Thus, with the choice $g(\theta)=\sum_{i=1}^{n}\ell_{i}(\theta)$, the selected point’s gradient has the largest bilinear similarity with $\nabla_{\theta}\sum_{i=1}^{n}\ell_{i}(\theta)$, where the similarity is parameterized by the inverse Hessian of the inner problem.

This section presents the connections of our approach to influence functions, experimental design and discusses its theoretical guarantees.

In the previous sections, we presented and analyzed Algorithm 1, our basic algorithm for coreset selection. There are three potential bottlenecks when applying this algorithm in practice. Firstly, inverting the Hessian directly in Equation (5) is infeasible for models with many parameters, thus we must resort to approximating inverse Hessian-vector products with a series of Hessian vector products using the conjugate gradient algorithm or Neumann series (Section 3.2). Secondly, adding points one by one might be too costly to generate larger coresets. Lastly, running multiple weight update steps might be prohibitive since the algorithm’s complexity depends linearly on the number of outer iterations. In this section, we address these issues by presenting several variants of our proposed method.

One application of our framework is speeding up model selection and hyperparameter tuning by performing these on the coreset instead of the full data. For this, we expect the coreset to be transferable to multiple models, whereas our formulation (Equation (1)) is tied to a model and a loss function. A simple idea to construct a coreset with better transferability is to ensure that it is a suitable coreset for multiple models. This is straightforward to achieve within our framework—for brevity, we present the idea for two models: consider models $f$ and $g$, and denote their parameters by $\theta_{f}$ and $\theta_{g}$. The problem of generating the joint coreset can be formulated as

For solving this bilevel problem, we can rely on the previously presented techniques. In practice, if the loss magnitudes are of the same order, we can set $\lambda=1$; an additional heuristic for solving the problem with (batch) forward selection is to perform the selection step alternatingly for each model. We verify the validity of this approach in the next section, where we demonstrate the improvement in the transferability of the coreset to deep convolutional networks.

In contrast to the standard supervised setting, where the learning algorithm has access to an i.i.d. data set $\mathcal{D}=\{(x_{i},y_{i})\}_{i=1}^{n}$, continual learning assumes that $\mathcal{D}$ is the union of $T$ disjoint subsets $\mathcal{D}_{1},\dots,\mathcal{D}_{T}$ such that each $\mathcal{D}_{i}$ contains data drawn from a different i.i.d. distribution. The goal is to learn a model based on the data that arrives sequentially from different tasks, such that the model achieves good performance on all tasks. An additional constraint in the setting is that the model cannot revisit all data from the previous tasks $1,\dots,t-1$ when learning on task $t$. The challenge is to avoid catastrophic forgetting (McCloskey and Cohen, 1989; French, 1999), which occurs when the optimization on $\mathcal{D}_{t}$ degrades the model’s performance significantly on some of $\mathcal{D}_{1},\dots,\mathcal{D}_{t-1}$.

Continual learning with neural networks has received increasing interest recently. The approaches for alleviating catastrophic forgetting fall into three main categories: weight regularization to restrict deviations from parameters learned on old tasks (Kirkpatrick et al., 2017; Nguyen et al., 2018); architectural adaptations for different tasks (Rusu et al., 2016); and replay-based approaches, where samples from old tasks are either reproduced via replay memory (Lopez-Paz and Ranzato, 2017) or generative models (Shin et al., 2017).

In this work, we focus on the replay-based approach, which provides strong empirical performance despite its simplicity (Chaudhry et al., 2019). In this setting, coresets are natural candidates for the summaries of the tasks to be stored in the replay memory, and we can readily use our coreset construction for the selection.

For continual learning with replay memory, we employ the following protocol. The learning algorithm receives data $\mathcal{D}_{1},\dots,\mathcal{D}_{T}$ arriving in order from $T$ different tasks. At time $t$, the learner receives $\mathcal{D}_{t}$ but can only access past data through a small number of samples from the replay memory of size $m$. We assume that equal memory is allocated for each task in the buffer, and that the summaries $C_{1},\dots,C_{T}$ are created per task. Thus, the optimization objective at time $t$ is

where $\sum_{\tau=1}^{t-1}|C_{\tau}|\!=\!m$ and $\beta$ is a hyperparameter controlling the regularization strength of the loss on the samples from the replay memory. After performing the optimization, $\mathcal{D}_{t}$ is summarized into $\mathcal{C}_{t}$ and added to the buffer, while previous summaries $\mathcal{C}_{1},\dots,\mathcal{C}_{t-1}$ are shrunk such that $|\mathcal{C}_{\tau}|=\lfloor m/t\rfloor$. The shrinkage is performed by running the summarization algorithms on each $\mathcal{C}_{1},\dots,\mathcal{C}_{t-1}$ again, which for greedy strategies is equivalent to retaining the first $\lfloor m/t\rfloor$ samples from each summary.

We can also apply our coreset construction in the more challenging setting of streaming. In contrast to continual learning, the streaming setting does not define tasks and does not assume i.i.d. data in any portion of the stream. Concretely, in this work, we assume that the learner observes small data batches $\mathcal{D}_{1},...,\mathcal{D}_{T}$ arriving in order, where no i.i.d. and task boundary assumptions are made.

As in the case of continual learning, one approach for alleviating catastrophic forgetting in the streaming setting is the retraining on data from the memory replay buffer. Denoting by $\mathcal{M}_{t}$ the replay memory at time $t$, the optimization objective at time $t$ for learning under streaming with replay memory is

Maintaining a coreset of constant size over datastreams is a cornerstone of training nonconvex models in a streaming setting. We offer a principled way to achieve this, naturally supported by our framework, using the following idea: two coresets can be summarized into a single one by applying our bilevel construction with the outer objective as the loss on the union of the two coresets.

Based on this idea, we use a variant of the merge-reduce framework of Chazelle and Matoušek (1996). For this, we assume that we can store at most $m$ coreset points in a buffer; we split the buffer into $s$ slots of equal size $m_{s}:=m/s$. We associate values $\beta_{i}$ with each of the slots, which will be proportional to the number of points they represent. A new batch is compressed into a new slot with associated default $\beta$, and it is appended to the buffer, which now might contain an extra slot. The reduction to size $m$ happens as follows: select the two consecutive slots $i$ and $i+1$ with smallest $i$ for which $\beta_{i}=\beta_{i+1}$ or, if this does not exist, choose the last two slots; then join the content of the slots (merge) and create the coreset of the merged data (reduce). The new coreset replaces the two original slots with $\beta_{i}+\beta_{i+1}$ associated with it. The pseudocode of the construction is shown in Algorithm 3 in Appendix D together with the illustration of the merge-reduce coreset construction for a buffer with 3 slots and 7 steps in Figure 14. The coreset produced by our construction for a two-layer fully-connected neural network on the imbalanced video stream created from the iCub World 1.0 data set (Fanello et al., 2013) can be seen in Figure 2.

The prominent use cases of our proposed method are scenarios with explicit budget constraints for subset selection. These constraints can be due to computational resource constraints, as in the case of continual learning and streaming with replay memory, or can relate to the cost of involving human interaction. Active learning falls into the latter category and aims to improve the data efficiency of learning algorithms by interleaving training rounds with selective query of the labels for informative unlabeled points from human experts.

The active learning setting assumes that, while unlabeled data is available abundantly, acquiring labels involves the cost of relying on human expertise. In the pool-based setup, each active learning round consists of training the model using the already labeled data and choosing points from the unlabeled pool for label acquisition. The challenge in this setting is to select the most informative samples, i.e., the samples with the highest potential of reducing the model’s generalization error. When the cost of performing a new training round after every single acquired label is considered, active learning becomes computationally unattractive. Batch active learning tackles this issue by acquiring labels for a batch of points in a single round but faces the additional challenge of ensuring diversity between the chosen points.

Active learning and its batch variant have received significant attention (MacKay, 1992; Lewis and Gale, 1994; Balcan et al., 2007; Hoi et al., 2006; Guo and Schuurmans, 2008; Kirsch et al., 2019). Although vastly available unlabeled data is assumed in this setting, most active learning approaches ignore the unlabeled pool while training the model in a supervised manner on the labeled pool only. On the other hand, recent advances in semi-supervised learning (SSL) have shown significant performance improvements of models trained with only a small number of labeled samples. Prominent SSL methods in the image domain include Mean Teacher (Tarvainen and Valpola, 2017), MixMatch (Berthelot et al., 2019) and its improvement, FixMatch (Sohn et al., 2020). These methods achieve the following CIFAR-10 test accuracies: Mean teacher - $78.5\%$ with $1000$ labeled samples; MixMatch - $88.2\%$ with $250$ labeled samples; FixMatch - $95\%$ with $250$ labeled samples.

The success of semi-supervised methods suggests that using the unlabeled data pool in active learning for acquisition only is suboptimal. Based on this observation, early approaches propose to combine active learning with SSL for Gaussian fields (Zhu et al., 2003) and SVMs (Hoi and Lyu, 2005; Leng et al., 2013). In the context of semi-supervised active learning with neural networks, Sener and Savarese (2018) investigate SSL training and selecting points for label acquisition that represent the $k$-centers of the embeddings in the last layer. Song et al. (2019) show that training in a semi-supervised manner with MixMatch and selecting the candidates for label query with standard acquisition functions improves the active learner’s generalization performance compared to uniform sampling. Gao et al. (2019) propose to train in each acquisition round with MixMatch and query the points that produce the most inconsistent predictions when undergoing random data augmentations, as measured by the sum of per-class variances in the predicted class probabilities. We compare our proposed acquisition strategy with these methods empirically.

We propose a simple yet highly effective label acquisition strategy based on bilevel coreset construction that works in the semi-supervised batch active learning setup. The basic idea is the following: in each round of active learning, we train the semi-supervised learner and use its predictions to provide labels for the samples in the unlabeled pool; then, using these “pseudo-labels”, we construct the coreset of the unlabeled pool and query the true labels for the selected points. This strategy naturally accommodates the selection of batches and prohibits redundancy in the selected batch by the design of the objective.

Let us formalize our approach in a single round of batch active learning. Denote the labeled pool by $\mathcal{D}_{\textup{train}}=\{(x_{i},y_{i})\}_{i=1}^{n_{\textup{labeled}}}$ and the unlabeled pool by $\mathcal{D}_{\textup{u}}=\{x^{\prime}_{i}\}_{i=1}^{n_{\textup{unlabeled}}}$. Let $h$ denote the model and $\theta^{*}_{\textup{SSL}}$ denote the parameters that minimize the semi-supervised loss—our strategy is oblivious to the choice of the SSL algorithm, it only assumes that the semi-supervised training outperforms supervised training of the model in terms of the generalization error. Lastly, let $\widehat{\mathcal{D}}_{\textup{u}}=\{(x,h_{\theta^{*}_{\textup{SSL}}}(x)),\;x\in\mathcal{D}_{\textup{u}}\}$ denote the data set of points from $\mathcal{D}_{\textup{u}}$ together with their soft pseudo-labels provided by the semi-supervised learner.

The goal of batch active learning is to select and query the labels of the most informative subset of the unlabeled data pool $\mathcal{M}\subseteq\widehat{\mathcal{D}}_{\textup{u}}$ of size $m=|\mathcal{M}|$ that would result in a maximal reduction of the model’s generalization error. We propose to select $\mathcal{M}$ as follows: $\mathcal{D}_{\textup{train}}\cup\mathcal{M}$ should be the coreset of $\mathcal{D}_{\textup{train}}\cup\widehat{\mathcal{D}}_{\textup{u}}$ for training $h$ in a supervised manner. Formally,

where $\widehat{y}$ denote the pseudo-labels. The motivation for the formulation in Equation (12) is twofold. Firstly, as the coreset of $\widehat{\mathcal{D}}_{\textup{u}}$, $\mathcal{M}$ will contain the most essential points of the unlabeled data pool for supervised training. In case some of these points have been wrongly pseudo-labeled, we expect that querying the correct labels induces a large model change. In the other case, acquiring hard labels benefits the semi-supervised learner in label propagation. Secondly, the coreset selection in Equation (12) naturally supports batch selection while avoiding redundancy among the selected points. We provide empirical support for this hypothesis in the experiments.

In signal compression, a collection of signals (data points) needs to be summarized by a small set of measurements ensuring high-fidelity reconstruction. In this case, instead of selecting data points, we select low-dimensional projections of the data. Despite this difference, due to the generality of our bilevel framework, we can showcase our framework for selecting measurements from a set of dictionary elements in order to improve the compression performance. This problem closely resembles dictionary learning and can be seen as a special case of it, without the individual sparsity constraints (Krause and Cevher, 2010). The classical greedy method, which can obey cardinality constraints on the measurement set and thus control the compression ratio, is computationally very expensive: for each element of the dictionary and at each enlargement, the whole dataset needs to be reconstructed. This increases the computational burden by the size of the dictionary, which can be prohibitively large.

Classically, the compression is addressed by transforming the data (signal) to a basis with a known redundancy such as a Fourier transform, and subsequently applying a set of linear measurements on the data. These are then recovered by imposing a regularization strategy such as the smallest squared squared norm ($L_{2}$). Alternatively, Chen (2005) proposed to use absolute norm regularization ($L_{1}$) referred to as basis pursuit or compressed sensing. In fact, compressed sensing can provably recover $s$-sparse signals with much smaller set of linear measurements than $L_{2}$ regularization, scaling as $\mathcal{O}(s\log(d))$ (Donoho, 2006). The measurement vectors, however, must satisfy specific conditions such as restricted isometry property (RIP) (Candes et al., 2006) for this to be guaranteed. Certifying that a measurement matrix has the RIP is known to be NP-hard (Bandeira et al., 2013). Constructing these matrices randomly is easy, however, the procedure generates them only with a certain probability (Candes et al., 2006).

Given a representative curated data set sufficiently covering all reasonable signals, a natural question is whether one can design a tailored measurement set that improves the compression ratio beyond the randomly generated RIP matrices or other classical measurements. In fact, since the recovery procedure is formulated as an optimization problem, this design question can be captured in the familiar bilevel form:

where $n$ is the size of representative data set, $a_{j}\in\mathbb{R}^{d}$ is one of the $m$ elements of the dictionary we select from, and $R(y)$ is the regularization term corresponding to $R(y)=\left\|y\right\|_{2}^{2}$ or $R(y)=\left\|y\right\|_{1}$. The values of $w_{i}$ are restricted to be binary in this application. While the optimization problems might not always be differentiable, the objective can be reformulated using differentiable relaxation techniques such as the log-sum-exp trick to approximate the supremum, and $L_{1}$ admits a variational reformulation via the so called $\eta$-trick to become differentiable (Bach et al., 2012). In practice, however, using an element of the sub-differential proves to be a viable strategy. We demonstrate the versatility of our framework by applying it to solve Equation (13) in Section 5.6.

Recently, Bora et al. (2017) and Jalal et al. (2021) have demonstrated that the sparsity-inducing regularizers can be substituted by the constraint that the data belongs to the support of a generative model $G(z)$, where $z\in\mathbb{R}^{p}$ is referred to as the latent space. In this case, the regularization term becomes an indicator function $R(y)=\mathbf{1}_{\exists z~{}|~{}y=G(z)}$, which can be reformulated to get a simplified inner problem $\hat{x_{i}}=G(z_{i})$ and $z_{i}=\arg\min_{z}\sum_{j=1}^{m}w_{j}(a_{j}(x_{i}-G(z)))^{2}$. The measurements are assumed to be linear as in classical compressed sensing, and the recovery guarantees satisfy similar conditions on measurement vectors as with sparse signals in previous works (Jalal et al., 2021). Naturally, a more informed measurement selection of $A$ as above can even further reduce the compression ratio.

The basic algorithm (Algorithm 1) for bilevel coresets is impractical except for simple models due to its computational cost—we discuss the runtime complexity in Section 5.7. Hence, we focus on the variants proposed in Section 3.5. Our target model is multiclass logistic regression, where the feature space is the $q=2048$-dimensional Nyström feature space of the Convoluational Neural Tangent Kernel (CNTK) proposed by Arora et al. (2019) with six layers and global average pooling on CIFAR-10. In this case, $\theta\in{\mathbb{R}}^{q\times c}$, and $\ell(\theta^{\top}z(x),y)=-\sum_{j=1}^{c}y_{j}\log\frac{\exp(\theta_{\cdot,j}^{\top}z(x))}{\sum_{j^{\prime}=1}^{c}\exp(\theta_{\cdot,j^{\prime}}^{\top}z(x))}$, where $y$ is the one-hot encoded label vector, $\ell$ is the cross-entropy loss with softmax, and $z(\cdot)$ is the Nyström feature mapping. In each implicit gradient step, we solve the inner optimization problem iteratively up to a tolerance, and approximate the implicit gradient (Pedregosa, 2016) with $100$ conjugate gradient steps. We split CIFAR-10 into a train and validation set, where the validation set is a randomly chosen $10\%$ of the original training set. We instantiate the outer loss as the sum of training and validation losses, whereas the inner optimization problem is defined on the training set. Further details about the experimental setup can be found in Appendix C.

We study unweighted coresets built using one-by-one forward selection, forward selection in batches of 25, exchange, elimination in batches of 200, and exchange with $200$ steps (each step exchanges $1\%$ of the selected points; we found that more steps did not increase the performance). For constructing weighted coresets, we solve the regularized version of the bilevel optimization proposed in Section 5.1. The results are shown in Figure 3. We can observe that forward selection in batches incurs initially a performance penalty but performs similarly to one-by-one forward selection after $25\%$ of the points have been selected. Both forward selection methods produce coresets of sizes between $33\%$ and $90\%$ on which logistic regression achieves lower test error compared to when trained on the full data set. Similarly to Wang et al. (2018), we observe that elimination increases the test accuracy in initial iterations; however, it significantly underperforms compared to uniform sampling for generating coresets smaller than $90\%$. Bilevel coresets via regularization (weighted) of size $8\%$ achieve the same performance as training on the full data set. We note that the higher test performance for the weighted coreset with size $20\%$ compared to $90\%$ is due to the higher number of total outer gradient steps performed.

We compare bilevel coresets to coresets designed for specific models, as well as to other data summarization methods. In all experiments, we observe that other methods do not consistently outperform uniform sampling over all subset sizes in contrast to our method.

We compare our approach to existing replay memory management strategies by conducting an extensive experimental study. We focus continual learning setting where the learning algorithm is a neural network, and we keep the network structure fixed during learning on different tasks. This is known as the “single-head” setup, which is more challenging than instantiating new top layers for different tasks (“multi-head” setup) and does not assume any knowledge of the task descriptor during training and test time. For validating our coreset construction in the continual learning setting, we use the following $10$-class classification data sets:

• •

  PMNIST (Goodfellow et al., 2014): consist of $10$ tasks, where in each task all images’ pixels undergo the same fixed random permutation.

• •

  SMNIST (Zenke et al., 2017): MNIST is split into $5$ tasks, where each task consists of distinguishing between consecutive image classes.

• •

  SCIFAR-10: similar to SMNIST on CIFAR-10.

Following Aljundi et al. (2019b), we keep a subsample of $1000$ points for each task for all data sets while we retain the full test sets. For PMNIST, we use a fully connected net with two hidden layers with $100$ units, ReLU activations, and dropout with probability $0.2$ on the hidden layers. For SMNIST and SCIFAR-10, we use a CNN consisting of two blocks of convolution, dropout, max-pooling, and ReLU activation, where the number of filters are $32$ and $64$ and have size $5\times 5$, followed by two fully connected layers of size $128$ and $10$ with dropout. The dropout probability is $0.5$. We fix the replay memory size $m=100$ for tasks derived from MNIST. For SCIFAR-10, we the set the memory size to $m=200$. We train our networks for $400$ epochs using Adam with step size $5\cdot 10^{-4}$ after each task.

We perform an extensive comparison under the protocol described above of our method to other data selection methods proposed in the continual learning or the coreset literature—the detailed description of the baselines can be found in Appendix D. For each method, we report the test accuracy averaged over tasks on the best buffer regularization strength $\beta$. For a fair comparison to other methods in terms of summary generation time, we restrict our coreset selection method in all of the continual learning experiments to forward selection of unweighted coresets via the Nyström proxy method with $q=512$ (Section 5.1)—we use the Neural Tangent Kernel (Jacot et al., 2018) corresponding to the chosen architecture, without dropout and max-pooling obtained with the library of Novak et al. (2020).