Provable Data Scaling Law for Meta Learning via Complexity Minimization

Kazuto Fukuchi, Ryuichiro Hataya, Kota MatsuiarXiv 2026 · arXiv

TL;DR

This paper introduces complexity minimization, a new meta-learning framework that selects representations by minimizing the worst-case model complexity across source domains. It provides the first end-to-end theoretical proof that downstream error rates decay faster as the amount of pre-training data increases, finally aligning meta-learning theory with the empirical "scaling laws" observed in foundation models.

What Problem Does This Paper Address?

We know empirically that "scaling laws" exist: as you increase the size of pre-training datasets, downstream tasks require fewer samples to reach high accuracy. However, existing theoretical frameworks for meta-learning often fail to capture this. Most current bounds for downstream error are independent of the pre-training data size ($m$), suggesting that pre-training helps, but not explaining why more of it is better.

The authors identify a missing link: an end-to-end analysis that connects the pre-training strategy directly to the downstream convergence rate. They aim to design a pre-training algorithm that provably achieves these scaling behaviors.

Methods

The authors propose a hierarchical framework called Complexity Minimization. Unlike standard meta-learning that might minimize average regression error, this approach focuses on the "best model complexity" as a proxy for downstream efficiency.

  1. Base-Learners (Domain-Specific): Each base-learner evaluates a feature extractor ($\phi$) by estimating the "best model complexity" ($J^\dagger$) for its specific domain. To do this without knowing the data's underlying parameters, they use Lepski’s method—a principled statistical technique for adaptive model selection that finds the optimal balance between approximation error and variance.
  2. Meta-Learner: The meta-learner collects these complexity estimates and selects a representation $\phi$ that minimizes the worst-case complexity across all observed source domains.
Conceptual diagram of complexity minimization. The meta-learner selects a representation that minimizes the maximum complexity reported by base-learners across different domains.

By minimizing this complexity, the framework ensures that the resulting representation makes downstream tasks "simpler" to learn, requiring fewer samples ($n$) to achieve low error.

Datasets

The authors validated their theory using standard meta-learning benchmarks and cross-domain transfer tasks:

  • Omniglot: Used for 5-way and 20-way 1-shot meta-training, then evaluated on transfer to SVHN.
  • Mini-ImageNet: Used for 5-way 1-shot meta-training, then evaluated on transfer to CIFAR-10 and CIFAR-100.

Key Insights and Ideas

  • Complexity as the Target: The core "aha" moment is shifting the optimization target from error to complexity. If a representation allows a downstream task to be solved with a "simpler" model (e.g., a sparser one), that task will naturally converge faster.
  • Bridging Theory and Practice: The paper provides an end-to-end analysis. They prove that the downstream excess error achieves a rate of $(n/\ln n)^{-\beta^* + O(\ln^{-\gamma} m)}$. Crucially, as the meta-training size $m$ grows, the exponent approaches the ideal convergence rate $\beta^*$.
  • Algorithm Agnostic: The principle of complexity minimization can be "plugged into" existing algorithms. By simply adding a norm-based complexity regularizer (like spectral norm) to the meta-loss, standard methods start exhibiting better scaling behavior.

Key Results

  • Provable Scaling: The authors mathematically demonstrate that the downstream error rate improves as the meta-training sample size $m$ grows, providing a theoretical foundation for the data scaling law.
  • Empirical Gains: Adding spectral norm regularization consistently improved downstream sample efficiency across four major meta-learning algorithms: MAML (First-Order and Second-Order), Prototypical Networks, and R2-D2.
  • Sample Efficiency: As shown in the experiments, models regularized for complexity reached lower test error rates on CIFAR-10 compared to baselines, especially when the downstream fine-tuning size ($n$) was small.
Test error rate on CIFAR-10 vs. fine-tuning size. Regularizing model complexity (spectral norms) consistently improves performance across different meta-learning algorithms and pre-training scales.

Limitations and Future Work

  • Theoretical Assumptions: The proof relies on "Assumption 2" regarding the metric entropy of the feature extractor class. The authors note that constructing a concrete family of neural networks that satisfies this assumption remains an open challenge.
  • Task Scope: The current theoretical analysis is focused on regression tasks. Extending this provable scaling law to classification and more complex structured prediction tasks is a key direction for future research.
  • Computational Overhead: While complexity regularization is simple to implement, the theoretical "complexity minimization" framework requires estimating optimal complexity levels, which could be computationally intensive at massive scales.

Summary updated

Abstract

Pre-training has become a fundamental paradigm in modern machine learning, with one of its key empirical benefits being reduced downstream sample complexity as the scale of pre-training data increases. However, existing theoretical frameworks for pre-training do not fully explain this phenomenon. In this paper, we introduce complexity minimization, a novel meta-representation learning framework designed to enable theoretical analysis of this scaling behavior, which learns representations by evaluating the downstream model complexity best suited to each domain and minimizing the worst-case such complexity across source domains. Our end-to-end theoretical analysis, spanning pre-training through downstream regression, shows that this framework provably captures this scaling behavior; in particular, we show that the error rate of few-shot adaptation improves as the amount of meta-training data grows. Empirically, we demonstrate that incorporating complexity regularization into existing meta-learning methods consistently improves downstream sample efficiency.
BibTeX
@misc{fukuchi2026provable,
  author = {Kazuto Fukuchi and Ryuichiro Hataya and Kota Matsui},
  title = {{Provable Data Scaling Law for Meta Learning via Complexity Minimization}},
  year = {2026},
  eprint = {2606.02008},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.02008},
}

Loading related content...

Figure