Query Labels Are the Scarce Resource in Episodic Meta-Learning

Meta-learning trains a model on many small tasks so that it can adapt quickly to a new one. Each training task is split in two. A small "support" set is used to adapt the model, and a "query" set scores how well that adaptation worked. The query score is then used to update the shared starting point that all tasks adapt from. Theory and practice both count data along two axes: how many tasks you have, and how many examples each task has. This note argues that the count that actually limits overfitting is a third one: how many distinct query labels the outer loop has seen, and how many times it has reused them. When a finite pool of tasks is cycled for thousands of outer steps, the query sets behave like a validation set that is tuned against over and over. The shared starting point can then fit query-label noise, much as hyperparameter search overfits a reused validation split.

We propose to make this precise and test it. The theory side is a generalization bound in which support data and query data enter separately. Query data enters through the number of outer steps divided by the number of distinct query samples, borrowing the stability analysis of hyperparameter tuning. The empirical side is a set of fixed-budget experiments on standard few-shot benchmarks. They test the predictions this bound makes and ordinary two-axis accounts do not. The practical payoff is an allocation rule: given a labeling budget, how to split it among tasks, support examples, and query examples. A second payoff is an explanation of a puzzling empirical result: fixing support sets during meta-training helps rather than hurts.

Core Claim

Existing sample-complexity results for meta-learning treat each task's data as one pool of size $n$. Fallah et al. show MAML can reach $O(1/mn)$ rates when the $m$ tasks and $n$ samples per task are pooled (Alireza Fallah et al. (2021)). Uniform meta-stability gives $O(1/m+1/n)$ for proximal methods (On the Stability and Generalization of Meta-Learning). Cioba et al. show the best per-task size converges to a constant as the budget grows (How to Distribute Data across Tasks for Meta-Learning?). None of these separates support from query. None charges for the number of outer iterations.

Separately, Bao et al. prove that gradient-based hyperparameter tuning has a generalization gap of order $T^\kappa/m_{\text{val}}$, where $T$ is the number of outer steps and $m_{\text{val}}$ the validation size (Stability and Generalization of Bilevel Programming in Hyperparameter Optimization). Their result covers a single task, not the episodic structure.

Our claim combines the two. For episodic gradient-based meta-learning with $m$ training tasks, $n_S$ support and $n_Q$ query samples per task, $K$ inner steps and $T$ outer steps, the meta-generalization gap behaves like

$$ \text{gap} \;\lesssim\; \frac{T^{\kappa}}{m\,n_Q} \;+\; \beta_{\text{adapt}}(n_S, K) \;+\; \frac{c}{m}, $$

where:

  • the first term is outer-loop leakage of query noise, from Bao-style stability, since swapping one query sample perturbs each outer gradient by $O(1/(m n_Q))$ and these perturbations accumulate over $T$ steps;
  • $\beta_{\text{adapt}}$ is the stability of few-step adaptation used in PAC-BUS (Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability), which shrinks with $n_S$ and grows with $K$;
  • $c/m$ is the usual cost of seeing only finitely many environments.

The new content is not the individual terms. It is the predictions that follow when they are combined:

  1. At a fixed labeling budget $B = m(n_S+n_Q)$, the best query fraction should grow with training length $T$ and with model capacity.
  2. Reusing support sets should be nearly free.
  3. Reusing query sets should be expensive.

Research Program

Theory. We first prove the bound under Bao et al.'s smoothness assumptions, using Softplus as they do, with weight decay on both levels. We do this for unrolled MAML and FOMAML, then specialize it to mixed linear regression. In that setting Cioba et al. already characterize the two-axis optimum, so we can compute the three-way optimum $(m^*, n_S^*, n_Q^*)$ in closed form and check that it reduces to their result as $T$ grows slowly.

Episodic overtuning measure. We adapt the overtuning measure of Overtuning in Hyperparameter Optimization to episodes. It is the test error of the meta-checkpoint selected by meta-validation, minus the best test error among all checkpoints seen so far. This turns query-reuse damage into a single number per run.

Reuse ablation. The decisive mechanism test crosses support reuse with query reuse. Both are either fixed per task or freshly resampled from a held-in pool. This yields four conditions at equal compute.

Is Support Set Diversity Necessary for Meta-Learning? reports that fixing supports while randomizing queries (FIX-ML) improves accuracy. That paper offers no bound explaining why. Our account predicts the gain comes from fresh queries, not fixed supports, and should vanish once queries are also fixed.

Relation to prior work. - Understanding Train-Validation Split in Meta-Learning with Neural Networks motivates this work. It shows the support-query split is what stops noise memorization, but it treats query evaluations as exact. We ask how small and how reused they can be. - Bilevel Programming for Hyperparameter Optimization and Meta-Learning flags validation-size effects as open. We address that question directly. - Metalearning with Very Few Samples Per Task constrains the design. Its identifiability floor of $k+2$ samples per task means $n_S + n_Q$ cannot shrink arbitrarily, whatever the query allocation. We keep $n_S$ above such floors in the synthetic experiments. - The benign-overfitting analysis of Understanding Benign Overfitting in Nested Meta Learning suggests some query fitting may be harmless in overparameterized linear models. We treat this as a competing hypothesis for the wide-model regime.

Baselines

Naive reference. Standard episodic training with the conventional per-task split: 1 or 5 support shots and 15 queries per class. Tasks are drawn from the full training pool, and the checkpoint is chosen by meta-validation accuracy. Every allocation and every reuse condition is run with the same backbone, the same total number of labeled training examples, the same outer-step count, and the same tuning budget for learning rates. The comparison is therefore about where labels go, not how many there are.

Two-axis allocation optimum. The strongest existing allocation baseline is the rule from How to Distribute Data across Tasks for Meta-Learning?. It fixes per-class data at its reported plateau, roughly 10 per class on miniImageNet and roughly 7 on CIFAR-FS, and spends the remaining budget on more tasks, with the standard support-query split inside each task. Beating it means a statistically significant test-accuracy gain at equal $B$ from re-splitting the same per-task data between support and query, across at least two benchmarks and two values of $T$.

Strongest empirical method on this question. FIX-ML, which reports 78.19% 5-way 5-shot miniImageNet accuracy with ResNet-12 (Is Support Set Diversity Necessary for Meta-Learning?). We reimplement it rather than copy the number, under our matched budget. Beating it is not the main goal. The goal is to show its gain is reproduced by "fresh queries" alone and destroyed by "fixed queries."

Regularization baselines. Two regularization baselines, each with its own tuned strength:

  • Bilevel weight decay as in Bao et al. For Omniglot, Bao et al. report validation loss falling while test loss rises at $K=256$; no reported result found on Lacuna for their final Omniglot accuracy.
  • The PAC-BUS regularizer. Its reported 87.9% versus MAML's 23.4% on non-mutually-exclusive Omniglot is the strongest memorization-control number in the file.

Ablation isolating the key ingredient. Holding $m$, $n_S$, and $T$ fixed, vary only the number of distinct query samples, through $n_Q$ and the size of the query pool. The bound predicts the gap tracks $T^\kappa/(m n_Q)$. Varying $n_S$ alone should move only the adaptation term.

Why not just…?

Why not just use the two-axis allocation of Cioba et al.? It is the right answer if the support-query split doesn't matter, and that is exactly what our ablation tests. Their analysis has no outer-step count. It therefore cannot predict that the optimum shifts as training runs longer. If our fixed-budget sweeps show the best query fraction flat in $T$, our claim fails and their rule suffices.

Why not just add weight decay to both levels? Bao et al. show this restores stability, so it is a real threat. Weight decay could absorb most of the leakage term. However, Optimizing Millions of Hyperparameters by Implicit Differentiation shows a high-capacity outer loop can memorize validation labels outright. That makes it plausible the query-reuse effect persists for backbone-sized meta-parameters. We run every allocation with and without tuned two-level weight decay. If regularization erases the allocation effect, we report that as the result. Even then, the allocation rule matters for budgets where regularization strength cannot itself be tuned without another validation set.

Why not just early-stop on meta-validation tasks? This is already standard and is our naive baseline. But Amplified Early Stopping Bias: Overestimated Performance with Deep Learning shows that selecting by validation metrics overestimates performance. The overtuning study finds roughly 10% of hyperparameter-search runs end worse than their default. Our episodic overtuning measure quantifies how much early stopping actually recovers.

Why not just use FIX-ML or distillation and skip theory? These help empirically, but they say nothing about how to allocate a labeling budget. Our reuse ablation would also reveal whether FIX-ML's benefit is about supports at all.

Proposed Experiments

Synthetic validation of the rates. - Sine-wave regression with tasks of the form $y=\alpha\sin(x+\beta)$, where On the Stability and Generalization of Meta-Learning verified $O(1/m+1/n)$ gaps. - Cioba et al.'s mixed linear regression. - In both, sweep $m$, $n_S$, $n_Q$, and $T$ on a log grid. Fit the gap's exponents and check that query count and $T$ enter as predicted, while support count does not interact with $T$.

Benchmark tests. - Datasets: miniImageNet, CIFAR-FS and tieredImageNet. - Learners: Conv-4 and ResNet-12 backbones with MAML, FOMAML and Prototypical Networks. - Measurements: meta-test accuracy, the support-query generalization gap, and episodic overtuning, over five seeds. - Reference points: - miniImageNet 1-shot FOMAML, where the train-validation split paper reports roughly 46.2% with a split versus 25.9% without. - miniImageNet 1-shot, where Franceschi et al. report 50.54% (MAML 48.70%, Prototypical Networks 49.42%). - Non-mutually-exclusive Omniglot serves as a stress test where query memorization is easy.

Decisive checks. Three results would support the proposal:

  1. The best query fraction at fixed budget rises with $T$ and with backbone width.
  2. In the reuse ablation, fixed queries hurt markedly more than fixed supports, and FIX-ML's advantage disappears when its queries are frozen.
  3. The three-way allocation beats the two-axis allocation of Cioba et al. at equal labels, with and without two-level weight decay.

If the first two fail, the leakage term is not real for these models.