Lune

Abstract

In this paper, we introduce a discrete variant of the meta-learning framework. Meta-learning aims at exploiting prior experience and data to improve performance on future tasks. By now, there exist numerous formulations for meta-learning in the continuous domain. Notably, the Model-Agnostic Meta-Learning (MAML) formulation views each task as a continuous optimization problem and based on prior data learns a suitable initialization that can be adapted to new, unseen tasks after a few simple gradient updates. Motivated by this terminology, we propose a novel meta-learning framework in the discrete domain where each task is equivalent to maximizing a set function under a cardinality constraint. Our approach aims at using prior data, i.e., previously visited tasks, to train a proper initial solution set that can be quickly adapted to a new task at a relatively low computational cost. This approach leads to (i) a personalized solution for each individual task, and (ii) significantly reduced computational cost at test time compared to the case where the solution is fully optimized once the new task is revealed. The training procedure is performed by solving a challenging discrete optimization problem for which we present deterministic and randomized algorithms. In the case where the tasks are monotone and submodular, we show strong theoretical guarantees for our proposed methods even though the training objective may not be submodular. We also demonstrate the effectiveness of our framework on two real-world problem instances where we observe that our methods lead to a significant reduction in computational complexity in solving the new tasks while incurring a small performance loss compared to when the tasks are fully optimized.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. ES-MAML: Simple Hessian-Free Meta LearningXingyou Song, Wenbo Gao, Yuxiang Yang, Krzysztof Choromanski et al.ICLR 2020 · 128 citations

Related papers

  1. Task-Robust Model-Agnostic Meta-LearningLiam Collins, Aryan Mokhtari, Sanjay ShakkottaiNeurIPS 2020 · 66 citations
  2. Online Fast Adaptation and Knowledge Accumulation (OSAKA): a New Approach to Continual LearningMassimo Caccia, Pau Rodríguez, Oleksiy Ostapenko, Fabrice Normandin et al.NeurIPS 2020 · 83 citations
  3. Meta-Learning with Task-Adaptive Loss Function for Few-Shot LearningSungyong Baik, Janghoon Choi, Heewon Kim, Dohee Cho et al.ICCV 2021 · 146 citations
  4. Structured Prediction for Conditional Meta-LearningRuohan Wang, Yiannis Demiris, Carlo CilibertoNeurIPS 2020 · 19 citations
  5. PLATINUM: Semi-Supervised Model Agnostic Meta-Learning using Submodular Mutual InformationChangbin Li, Suraj Kothawade, Feng Chen, Rishabh K. IyerICML 2022 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines