Elamur Research⌕
☰
home / papers / 2019 / Gradient based sample selection for online continual learning

Gradient based sample selection for online continual learning

Paper · 2019 · Rahaf Aljundi, Min Lin, Baptiste Goujaud et al.

Summary

The paper studies online lifelong learning (continual learning). A model receives a stream of data whose distribution changes over time, and it does not know where one task ends and another begins. To keep the model from forgetting what it learned earlier (catastrophic forgetting), a small buffer of examples is usually stored for rehearsal. Known methods such as GEM and iCaRL fill this buffer using task boundaries and the i.i.d. assumption. The authors propose a different view: learning here is constrained optimization, and choosing examples for the buffer means reducing the number of constraints. The goal is for the reduced feasible region (a cone in gradient space) to differ as little as possible from the full one. The exact problem, stated in terms of the solid angle, is hard to solve, so they replace it with a simpler one: maximize the diversity of gradient directions in the buffer. This leads to two methods: GSS-IQP, based on quadratic programming, and the cheap greedy GSS-Greedy. Neither uses task information, and overall both match the methods that do use it. The advantage is especially clear on imbalanced data streams, where reservoir sampling loses rare tasks.

Key points

  • Example selection is formulated as minimizing the solid angle of the feasible cone. The surrogate is the sum of cosine similarities between gradients, which is equivalent to maximizing the variance of their directions. On random vectors of dimension 200, the authors showed that the surrogate changes monotonically with the solid angle.
  • There are two variants of the method: GSS-IQP and GSS-Greedy. The greedy one costs about as much to compute as reservoir sampling, but stream imbalance does not affect it.
  • Experiments were run on disjoint MNIST, permuted MNIST and disjoint CIFAR-10 (only GSS-Greedy was run on CIFAR-10, because GSS-IQP is too expensive). For MNIST, the buffer held 300 examples.
  • Imbalanced disjoint MNIST: one task has 2000 examples and each of the others has 200; 3 runs. Compared with reservoir sampling, accuracy improved by up to 15%.
  • On permuted MNIST, the method beats GEM and comes close to i.i.d.online. On disjoint CIFAR-10, GSS-Greedy outperforms GEM and iCaRL, and by the end even i.i.d.online. The paper was published at NeurIPS 2019.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓National University of SingaporeSingapore · Singapore207 works · 39,576 citations🔬Canadian Institute for Advanced ResearchToronto · Canada35 works · 19,316 citations🎓KU LeuvenLeuven · Belgium46 works · 7,833 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 works

Cite

Cite as Rahaf Aljundi, Min Lin, Baptiste Goujaud and Yoshua Bengio. 2019. Gradient based sample selection for online continual learning. arXiv:1903.08671.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1903.08671 · arXiv 1903.08671

@misc{aljundi2019gradient,
  title = {{Gradient based sample selection for online continual learning}},
  author = {Rahaf Aljundi, Min Lin, Baptiste Goujaud and Yoshua Bengio},
  year = {2019},
  doi = {10.48550/arxiv.1903.08671},
  eprint = {1903.08671},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1903.08671}
}

References

17 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Rahaf Aljundi, Marcus Rohrbach, and Tinne Tuytelaars. Selfless sequential learning. In ICLR 2019. find
  2. Matthias Beck, Sinai Robins, and Steven V Sam. Positivity theorems for solid-angle polynomials. arXiv preprint arXiv:0906.4031, 2009. (c) Disjoint CIFAR-10 T4 T5 T6 T7 T8 T9 T10 T1 T2 T3 T4 T5 0.6 GSS-IQP GSS-Greedy GEM Single i.i.d.online 0.5 Accuracy 0.4 0.3 0.2 i.i.d.offline iCaRL 0.1 0.0 Number… — [arXiv:0906.4031](https://arxiv.org/abs/0906.4031) find
  3. Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. SIAM Journal on Computing, 33(6):1417–1440, 2004. find
  4. Arslan Chaudhry, Marc’Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny. Efficient lifelong learning with a-gem. arXiv preprint arXiv:1812.00420, 2018. find
  5. Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet K Dokania, Philip HS Torr, and Marc’Aurelio Ranzato. Continual learning with tiny episodic memories. arXiv preprint arXiv:1902.10486, 2019. find
  6. Sebastian Farquhar and Yarin Gal. Towards robust evaluations of continual learning. arXiv preprint arXiv:1805.09733, 2018. find
  7. Robert M French. Dynamically constraining connectionist networks to produce distributed, orthogonal representations to reduce catastrophic interference. network, 1111:00001, 1994. find
  8. David Isele and Akansel Cosgun. Selective experience replay for lifelong learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018. find
  9. Long-Ji Lin. Reinforcement learning for robots using neural networks. Technical report, Carnegie-Mellon Univ Pittsburgh PA School of Computer Science, 1993. find
  10. David Lopez-Paz et al. Gradient episodic memory for continual learning. In Advances in Neural Information Processing Systems, pages 6467–6476, 2017. find
  11. Arun Mallya and Svetlana Lazebnik. Packnet: Adding multiple tasks to a single network by iterative pruning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7765–7773, 2018. find
  12. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013. find
  13. Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner. Variational continual learning. arXiv preprint arXiv:1710.10628, 2017. find
  14. Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proc. CVPR, 2017. find
  15. Jason M Ribando. Measuring solid angles beyond dimension three. Discrete & Computational Geometry, 36(3):479–487, 2006. find
  16. Anthony Robins. Catastrophic forgetting, rehearsal and pseudorehearsal. Connection Science, 7(2):123–146, 1995. find
  17. Jeffrey S Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1):37–57, 1985. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/aljundi-2019-gradient-based-sample-selection-online/