PaperlayerView exact revision on arXiv

Source-linked AI summary

Coresets via Bilevel Optimization for Continual Learning and Streaming

Zalán Borsos, Mojmír Mutný, Andreas Krause

arXiv:2006.03875v2cs.LGstat.ML

TL;DR

Accurate continual-learning and streaming models must summarize past data despite non-iid arrivals and catastrophic forgetting, while existing coresets are limited for complex models. The paper uses cardinality-constrained bilevel optimization with matching-pursuit selection and proxy models to construct neural-network coresets. It reports effective summaries in continual learning and streaming, while noting computational overhead above 500 points and heuristic guarantees for neural networks.

  • Problem

    Non-iid continual-learning and streaming data can cause catastrophic forgetting, while existing coreset constructions are poorly suited to neural networks.

  • Method

    The paper formulates coreset selection as cardinality-constrained bilevel optimization, solves it with greedy matching pursuit, and uses proxy models for neural networks.

  • Results

    The coreset construction performs among the best summarization strategies in continual learning and streaming deep learning.

  • Takeaways & Limitations

    The framework provides representative data summaries for neural networks and is applied to alleviate catastrophic forgetting in continual learning and streaming.

  • Takeaways & Limitations

    Summaries larger than 500 incur significant computational overhead, and neural-network coreset selection remains heuristic because the cardinality-constrained bilevel problem is hard.

Abstract

from arXiv · show

Coresets are small data summaries that are sufficient for model training. They can be maintained online, enabling efficient handling of large data streams under resource constraints. However, existing constructions are limited to simple models such as k-means and logistic regression. In this work, we propose a novel coreset construction via cardinality-constrained bilevel optimization. We show how our framework can efficiently generate coresets for deep neural networks, and demonstrate its empirical benefits in continual learning and in streaming settings.

1 Introduction

Online continual-learning and streaming systems must maintain accurate models from non-iid data without revisiting the past. The paper proposes coresets as an efficient replay-memory summary and develops a bilevel framework for selecting them for neural networks.

  • Non-iid task sequences and streams can cause model performance to degrade arbitrarily, especially through catastrophic forgetting in deep learning.
  • Coresets are small, weighted data subsets whose trained models can perform almost as well as models trained on the full dataset.
  • Coresets can be maintained over data streams, providing an efficient way to handle massive datasets and streaming data.
  • The paper formulates coreset selection as cardinality-constrained bilevel optimization and solves it with greedy forward selection via matching pursuit.
  • A proxy-model reformulation makes the framework especially suited to replay-based continual learning and streaming with neural networks.

2 Related Work

Prior work addresses continual learning mainly through regularization, architectural changes, or replay, while coreset constructions have largely targeted simpler models. The paper positions bilevel optimization as a route to data summarization for neural-network replay and streaming.

  • Continual Learning and Streaming: Continual-learning methods commonly use weight regularization, task-specific architectural adaptations, or replay through stored samples or generative models.
  • Figure 1 contrasts five-class stream composition, reservoir sampling, and the paper’s selection method on an imbalanced iCub World image stream.
  • Continual Learning and Streaming: The paper focuses on replay-based continual learning because it offers strong empirical performance despite its simplicity.
  • Continual Learning and Streaming: Replay-based streaming with neural networks has received little attention, with only a small set of prior methods identified for experimental comparison.
  • Coresets: Uniform-approximation coreset definitions work for models such as k-means, Gaussian mixture models, and logistic regression but can produce large coresets for neural networks.
  • Coresets: In continual-learning research, “coreset” is often used loosely for replay-memory samples, commonly selected by uniform sampling or clustering in feature space.
  • Bilevel optimization: Bilevel optimization has applications in meta-learning, hyperparameter optimization, neural architecture search, sample reweighting, and sensor selection.

3 Coresets via Bilevel Optimization

The paper defines a coreset through weighted empirical-risk minimization and selects its support by solving a cardinality-constrained bilevel problem. Matching pursuit incrementally adds points using outer-objective information, with influence-function connections and convex-case guarantees.

  • Coresets via Bilevel Optimization: A coreset is a weighted subset represented by a sparse weight vector, where zero-weight points are excluded from the summary.
  • Coresets via Bilevel Optimization: The bilevel objective minimizes full-data loss at parameters obtained by minimizing weighted coreset loss, subject to coreset size m ≤ n.
  • Background: Bilevel Optimization: The general bilevel problem is NP-hard, while first-order relaxation uses stationarity of the inner objective and is tight when that objective is strictly convex.
  • Warm-up: Least Squares Regression, and Connections to Experimental Design: For least-squares regression, the inner problem has a closed-form solution and connects the summarization objective to Bayesian V-experimental design.
  • Warm-up: Least Squares Regression, and Connections to Experimental Design: After relaxing integrality, the Bayesian V-experimental-design objective is smooth and convex in the weights, supporting first-order optimization in this special case.
  • Incremental Subset Selection: Norm-based sparsity regularization is ineffective because jointly rescaling weights and the regularizer leaves the inner solution unchanged.
  • Incremental Subset Selection: Greedy selection is impractical for general losses because each candidate point would require solving a bilevel optimization problem for its marginal gain.
  • Incremental Subset Selection: Matching pursuit grows the active atom set incrementally and stops when the desired coreset size m is reached.

4 Coresets for Neural Networks

The framework adapts cardinality-constrained bilevel coreset selection to deep neural networks through a proxy-model reformulation that makes small summaries computationally tractable. It uses kernel representations to reduce inner-level dimensionality, while remaining heuristic and costly beyond 500 points.

  • Neural-network coreset construction: The bilevel framework applies to twice differentiable models and is demonstrated on deep neural networks.The neural-network setting is challenging because direct bilevel optimization requires repeated Hessian-related computations.
  • Proxy reformulation: A proxy model provides a large speedup for coreset sizes of at most 500 points.The proxies are reproducing-kernel Hilbert-space functions using a positive-definite kernel and the same convex loss as the neural network.
  • Proxy reformulation: The representer theorem reduces the inner-level parameters to at most the coreset size m.This enables fast inner solvers and supports approximate inverse Hessian-vector products computed with conjugate gradients.
  • Proxy reformulation: For neural networks, the proposed proxy is the corresponding Neural Tangent Kernel, while alternative kernels are left for future investigation.The Neural Tangent Kernel characterizes gradient-descent training in the infinite-width limit.
  • Computational cost: The standard formulation is impractical for weighted coreset selection because 30 conjugate-gradient steps require one minute for a ResNet-18 on a GPU.The proxy reformulation reduces the number of parameters to O(m), addressing this computational bottleneck for small coresets.
  • Limitations: Generating summaries larger than 500 points incurs significant computational overhead, and cardinality-constrained bilevel optimization makes neural-network selection heuristic.The paper suggests batched greedy selection or greedy elimination as possible remedies for larger summaries.

5 Applications in Continual Learning and Streaming Deep Learning

The paper evaluates coreset-based replay memories for continual learning and task-agnostic streaming, including a merge-reduce procedure for maintaining bounded memory. Its experiments cover neural-network summaries on MNIST and CIFAR-10, while the streaming protocol handles batches without task boundaries.

  • Applications: The applications compare coreset summaries with other replay-memory strategies while keeping the network structure fixed in a single-head setup.The goal is to manage representative past samples for continual learning and streaming with neural networks.
  • Continual learning: In continual learning, each task receives an equal share of replay memory, and summaries are created per task with unit weights.At time t, the learner receives tasks in order and accesses past data only through the replay memory.
  • Continual learning: After adding the current task summary, previous summaries are shrunk to floor(m/t) points each.For greedy strategies, shrinkage retains the first floor(m/t) samples from each summary.
  • Streaming: Streaming differs because batches arrive sequentially without task-boundary information, and tasks may not be defined.The replay memory at time t supports learning from this task-agnostic sequence.
  • Streaming coresets via merge-reduce: A merge-reduce example runs for 7 steps with a buffer containing 3 slots; grey nodes show the final buffer and corner numbers show coreset construction times.The figure caption specifies the buffer state after the seven steps.
  • Streaming coresets via merge-reduce: Merge-reduce combines two coresets by summarizing their union with the bilevel construction.This provides a principled way to maintain streaming replay memory.
  • Empirical evaluation: Figure 3 reports CNN results on MNIST, KRR results on CIFAR-10, and ResNet-18 results on CIFAR-10 using binary-weight coresets.The KRR experiment obtains almost 50% test accuracy on CIFAR-10 using only 400 points.
  • Streaming coresets via merge-reduce: The streaming buffer is divided into equally sized slots, and consecutive slots are merged and reduced when the buffer exceeds size m.Each resulting slot receives a regularizer proportional to the number of points it represents.

6 Experiments

Experiments evaluate the coreset construction for neural-network dataset summarization, continual learning, streaming, imbalanced streams, and runtime. The method generally performs strongly, while its advantage depends on the setting and smaller coreset sizes are computationally preferable.

  • Dataset summarization: The method summarizes MNIST with a CNN and evaluates test accuracy as a function of summary size over five random seeds.The CNN uses convolutional, dropout, max-pooling, ReLU, and fully connected layers, and is trained with Adam at learning rate 5 · 10^-4.
  • Dataset summarization: On CIFAR-10, CNTK-based selection reaches almost 50% test accuracy with only 400 samples, while binary unweighted subsets also improve representative selection for ResNet-18.The experiments use kernelized ridge regression and a ResNet-18 variant without batch normalization.
  • Continual Learning: In continual learning, the coreset construction performs among the best across datasets under replay-memory budgets of 100 for MNIST and 200 for CIFAR-10.The comparison averages test accuracy over tasks and restricts the method to binary coreset weights for fair summary-generation-time comparisons.
  • Continual Learning: The method also benefits VCL, with results suggesting that representative coresets outperform simple selection rules when using 20 summary points per task.The VCL experiment uses a single-headed two-layer network with 256 units per layer and ReLU activations.
  • Streaming: In balanced streaming, the method outperforms competing selection strategies across most SplitMNIST tasks, but does not outperform reservoir sampling on CIFAR-10.The streaming experiments use merge-reduce buffers; the SplitMNIST comparison examines final per-task test accuracy.
  • Streaming: For imbalanced streams, the method is competitive with strategies designed specifically for imbalance, while runtime grows nonlinearly with coreset size and is most practical for smaller summaries.The imbalanced setup retains 200 samples from each of the first four tasks and 2000 from the last task; runtime is measured from batches of 1000 points.

7 Conclusion

The paper presents a cardinality-constrained bilevel framework for generating neural-network coresets and evaluates it in continual learning and streaming. The construction produces representative summaries and performs among the best summarization strategies in these settings.

  • The framework generates coresets through bilevel optimization with cardinality constraints.
  • The method yields representative data summaries for neural networks.
  • Experiments illustrate advantages in alleviating catastrophic forgetting in continual learning and streaming deep learning.
  • The coreset construction performs among the best summarization strategies in the evaluated settings.

Broader Impact

Coresets can reduce the computational and storage demands of handling large datasets. The paper also identifies privacy and bias-related implications as possible benefits or future directions.

  • Coresets can reduce computational costs when handling large datasets under computational constraints.
  • Reducing retained data may also provide possible energy-consumption and privacy benefits.
  • Explicitly optimizing representativeness beyond accuracy, including to counteract data bias, is proposed as future work.

A Connections to Experimental Design

The bilevel coreset framework connects data summarization to frequentist and Bayesian experimental design under linear regression. Its objectives inherit favorable optimization properties, including approximate submodularity that supports greedy selection.

  • Coreset formulation: Binary coreset selection is equivalent to selecting rows of X through either a subset S or diagonal matrix D(w).Here w ∈ {0, 1}^n indicates selected points.
  • Frequentist Experimental Design: Under linear regression, different outer objectives in the bilevel framework recover corresponding frequentist experimental-design objectives.The framework uses an inner regression objective and varies the outer objective to obtain different design criteria.
  • Infinite data limit: In the infinite-data limit, the summarization objective and V-experimental design converge to selections with the same quality, without implying identical algorithmic steps.This equivalence concerns optimal-solution quality rather than execution trajectories.
  • Bayesian Experimental Design: Under Bayesian linear regression, integrating over the parameter prior yields a corresponding Bayesian V-experimental-design objective.The true parameter is modeled as θ ∼ N(0, λ^-1 I), and the prior enters the outer expectation.
  • Weak-submodularity: Bayesian V-experimental design is non-negative, monotone, and γ-weakly submodular, so greedy selection is expected to perform well.The associated cardinality-constrained greedy maximization has a 1 − e^-γ approximation guarantee for weakly submodular objectives.
  • Influence functions: With twice-differentiable, strictly convex inner loss, maximizing a point’s influence matches the framework’s incremental selection rule.This establishes a formal link between greedy bilevel selection and influence-function-based subset selection.

D Continual Learning and Streaming Experiments

The experiments evaluate coreset replay against sampling, clustering, uncertainty, and prior replay-memory strategies in continual learning and streaming settings. The method consistently outperforms uniform sampling across datasets and selects diverse, difficulty-sensitive MNIST examples.

  • Experimental comparisons: The study compares replay without memory, uniform sampling, per-task coresets, clustering methods, uncertainty-based selection, and prior replay strategies.Clustering is evaluated in feature, embedding, and gradient spaces.
  • Continual learning results: Our coreset construction is the only method consistently outperforming uniform sampling on all datasets.Several alternatives outperform uniform sampling on individual datasets, but not across the full evaluation.
  • Memory-size study: The method offers bigger improvements with smaller replay-memory sizes on SplitMNIST.This conclusion is reported in the replay-memory size study.
  • Proxy study: An RBF kernel is a good proxy on MNIST-derived datasets but fails on harder datasets such as CIFAR-10.The RBF experiments use k(x, y) = exp(−γ ∥x − y∥^2) with γ = 5 · 10^-4.
  • Coreset inspection: For a coreset of size 40 on MNIST, selected samples are diverse within classes and harder classes receive more samples.The method initially selects examples from different classes, then diversifies within classes; it selects twice as many 8s as 1s.

E Speedups, Data Preprocessing, Architectures and Hyperparameters

The implementation uses quasi-Newton optimization for inner problems, Adam for outer optimization, and warm starts, with additional simplifications for continual learning and streaming. Experiments standardize inputs and specify training, tuning, and hardware settings.

  • Optimization: Inner bilevel problems use L-BFGS, while outer-level optimization uses Adam.The inner solver uses specified iteration and tolerance settings, and outer optimization uses task-dependent learning rates and iteration counts.
  • Speedups: Reusing the previous inner solution and using binary weights provide additional speedups for streaming and continual learning.Binary weights also avoid outer iterations because those settings use unweighted samples.
  • Data preprocessing: All datasets are standardized per channel, while CIFAR-10 streaming additionally uses random cropping and horizontal flipping.Preprocessing is performed separately for each dataset.
  • Training: Continual-learning networks train for 400 epochs after each task, whereas streaming networks train for 40 gradient-descent steps after each batch.Both use Adam with step size 5 · 10^-4; continual learning uses minibatches of size 256.
  • Hyperparameters: Replay-memory regularization strength β is tuned separately for each method from six candidate values, with the best test-set result reported.The candidate set is {0.01, 0.1, 1, 10, 100, 1000}.
  • Computational resources: Neural networks and kernels run on a single GeForce GTX 1080 Ti, while coreset generation uses one CPU thread.The same GPU is used to calculate (C)NTK kernels.
Loading 2006.03875v2…