acceptodds
Under review as a conference paper at ICLR 2027

Provable Data Scaling Law for Meta Learning via Complexity Minimization

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.

Primary area:
learning theory
Keywords:
pre-training, meta-learning, representation learning, scaling law, sample complexity, model complexity, adaptive model selection

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_kp5wOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the data expansion rules in pre-training/meta-learning, that is, why with the increase of meta-training data size, downstream tasks can achieve faster error convergence with fewer samples. The authors propose a complexity minimization framework, no longer directly using the adapted prediction error as the meta-learning objective, but learning a representation that minimizes the optimal downstream model complexity required by different source domains under this representation; specifically, through Lepski's method, the best model complexity of each domain is adaptively estimated from a limited sample set, and then the meta-learner minimizes the worst-case complexity across source domains. The authors further establish an end-to-end theoretical analysis from meta-training to downstream regression, proving that as the meta-training sample size m increases, the downstream convergence index of the learned representation gradually approaches the ideal index, thereby formally obtaining the data scaling law.

Critical strengths
  1. The paper presents a significant new theoretical perspective: understanding the quality of representations through downstream model complexity rather than merely downstream loss. The author rephrases meta-representation learning as finding the representation that minimizes the worst-case optimal downstream model complexity across domains, and directly links this complexity to the downstream convergence rate. This aspect is crucial for my overall assessment as it not only presents a new algorithmic detail but also provides a different statistical mechanism for understanding why more pre-training data improves the few-shot sample efficiency. It has the potential to inspire subsequent research on representation complexity and scaling laws.

  2. The paper presents a relatively complete end-to-end theoretical chain, rather than merely proposing a sufficient condition or a local bound. The main theorem explicitly links the meta-training data size to the downstream convergence exponent, and further constructs a complete proof through the complexity estimator, meta-learning guarantee, and downstream learner guarantee.

Critical weaknesses
  1. The representation-class assumption relied upon by the main theorem has not received any meaningful specific instances to support it. Assumption 2 requires Phi to simultaneously satisfy specific metric-entropy conditions, but the authors explicitly admit that constructing a specific Phi that meets these conditions remains an open problem. This defect has a significant impact on the overall evaluation, as the paper claims to explain the data scaling law in representation learning, but it is currently unclear whether the core theorem is applicable to linear representations, networks subject to norm constraints, or other practical representation classes used in practice.

  2. The experiment did not truly validate the complexity-minimization algorithm proposed in the paper, and there is a significant gap in the mechanism between the theory and the experiment. The theoretical method requires using Lepski's method to estimate the domain-wise best complexity and minimizing its worst-case value by the meta-learner; however, the experiment merely added spectral-norm and other elements to the existing meta-learning method. The intuition that "complexity regularization may improve sample efficiency" cannot directly prove that the complexity minimization in the theory is the mechanism causing the observed scaling behavior. This weakens the closed loop between theory and empirical evidence.

Questions for authors
  1. Assumption 2 is of crucial importance to the main theorem of this paper. Could the author provide at least one non-trivial and interpretable representation family Phi (such as a certain type of linear representation, a finite-dimensional parameterized model, or a neural network class subject to norm constraints) that satisfies this assumption, or at least clearly state in which actual related model classes this assumption can be verified?

  2. The current experiment employs spectral/L1-norm regularization instead of the Lepski-based complexity-minimization algorithm mentioned in the text. Could the authors establish a clearer theoretical or empirical correspondence between the two, for instance, directly estimating the downstream convergence exponent under different pre-training sizes m, or implementing an approximation version that is closer to domain-wise complexity minimization?

Reviewer_To9VOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies whether increasing meta-training data can provably improve the downstream learning rate. It proposes complexity minimization: each domain-specific base learner estimates, via Lepski's method over nested head classes, the model complexity best suited to that domain, and the meta learner selects a representation minimizing the worst estimated complexity across observed domains. Under polynomial approximation, entropy, domain-coverage, and sub-Gaussian noise assumptions, the paper proves a downstream regression bound whose exponent approaches the ideal exponent as the per-domain meta-training sample size grows.

Critical strengths

The paper targets an important and under-explained question: how the amount of source data can change the downstream convergence rate, rather than merely a constant in a fixed-rate bound. The attempt to connect representation quality to an adaptive model-complexity selector is conceptually interesting and could be valuable if instantiated.

Critical weaknesses
  • The theory and experiments evaluate different methods and different notions of complexity. The proposed algorithm estimates a discrete complexity level with Lepski's method over nested function classes, minimizes the worst estimated level across domains, and uses another Lepski selector downstream. None of these components is implemented. The experiments merely add spectral-norm or L1 penalties to MAML, ProtoNet, and R2-D2. The paper gives no theorem or empirical calibration showing that these parameter norms correspond to the paper's J, approximation exponent, or Minkowski-Bouligand dimension. Consequently, the experiments can show that ordinary norm regularization helps, but they do not validate complexity minimization.
  • The theoretical result is too abstract to support the practical claims made around modern meta-learning. Assumption 2 requires simultaneous entropy control of the representation class, yet the paper explicitly leaves constructing any concrete class satisfying it as an open problem. The theorem is for regression with exact empirical risk minimization over nested head classes and an abstract argmin over representations, whereas the experiments use classification, finite neural networks, stochastic optimization, and full-backbone fine-tuning.
Questions for authors
  • Can the authors implement the actual algorithms defined in Sections 4.1-4.3, including the Lepski-based base learner, worst-domain meta objective, and downstream selector, and compare them with both the unregularized baselines and the norm-regularized proxy?
  • What formal result connects spectral or L1 parameter norms to J, the approximation exponent alpha, or the Minkowski-Bouligand complexity used in the proof? If no such result is available, can the authors measure whether the norm penalties actually reduce the estimated theoretical complexity and mediate the observed downstream gains?
Reviewer_qc8ZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a complexity minimization framework for meta-representation learning to theoretically explain how increasing pre-training data improves downstream sample efficiency. The framework learns representations by minimizing the worst-case downstream model complexity across source domains. Using Lepski's method for adaptive complexity estimation, the authors establish an end-to-end convergence bound in which the downstream learning exponent approaches an optimal value as the amount of meta-training data increases. Experiments on several meta-learning algorithms suggest that complexity regularization can improve downstream sample efficiency.

Critical strengths

The paper addresses an interesting and important theoretical question: how the amount of pre-training data influences downstream learning rates. Connecting representation learning with downstream model complexity is a potentially useful perspective. The attempt to provide an end-to-end theoretical analysis, rather than assuming a pre-trained representation with desirable properties, is also valuable.

Critical weaknesses

1. Strong and insufficiently justified theoretical assumptions.

The main theoretical result relies heavily on Assumptions 1 and 2, whose applicability to meaningful learning problems is unclear.

Assumption 1 requires the approximation error to exhibit an exact polynomial decay rate, AJ≍J−2αA_J \asymp J^{-2\alpha}, uniformly over all candidate representations and distributions in P∗\mathcal{P}^*. This is considerably stronger than a standard approximation upper bound and excludes natural settings, such as exactly representable target functions or representations that discard predictive information. The paper provides insufficient justification for imposing such a restrictive condition.

Assumption 2 introduces two metric entropy conditions on the representation class, including one defined directly in terms of the downstream convergence exponent. These conditions are difficult to verify, and the paper does not establish that any meaningful representation family satisfies them. The authors explicitly acknowledge that constructing such a family remains an open problem. Without concrete examples satisfying these assumptions, the practical relevance and nontrivial applicability of the main theorem remain questionable.

2. Limited connection between theoretical results and experiments.

The experiments employ norm-based regularization in existing meta-learning algorithms rather than the complexity minimization algorithm analyzed theoretically. Moreover, the experiments do not verify the theoretical assumptions or directly demonstrate the predicted improvement in downstream convergence exponents. Consequently, the empirical findings provide only indirect support for the theoretical claims.

Questions for authors
  1. Can the authors provide a nontrivial example of a representation family and task distribution satisfying Assumptions 1 and 2 simultaneously? In particular, can these conditions be verified for a standard neural network representation class?

  2. Why is the two-sided polynomial approximation condition in Assumption 1 necessary? Could the analysis be extended to more general approximation classes, including exactly representable target functions?

  3. Can the authors provide experimental evidence that increasing the meta-training sample size improves the downstream convergence exponent, rather than merely reducing the downstream error at fixed sample sizes?

Comments on the paper

1 comment

We thank all reviewers for their careful reading and insightful comments. The reviews share the following concerns, which we answer below; the revised paper gives the details.

1. A concrete class satisfying Assumption 2 (qc8Z, To9V, kp5w)

We would like to highlight that Assumption 2 is not vacuous. The revised paper gives a non-trivial and interpretable representation class, in which the representation decides how the head complexity is shared among the input coordinates, and proves both conditions of Assumption 2 for every task allowed by Assumption 1, without assuming a smoothness class. In this class, the exponent genuinely depends on the representation, and the best representation improves it. Hence, the main theorem applies to a setting where pre-training improves the downstream exponent, which is the phenomenon the paper aims to explain.

For standard neural network classes, the first condition of Assumption 2 holds when the extractor and the heads are Lipschitz in finitely many parameters. The second condition, which controls how the exponent varies over the representation class, remains open: verifying it requires the approximation exponent of each regression function under each network extractor, which is not available for ReLU networks.

2. The analysed algorithm and the exponent (qc8Z, To9V, kp5w)

We implemented the analysed algorithm itself, with the Lepski base-learner, the worst-domain meta-learner and the downstream Lepski selector, on tasks whose exponents are known. The estimated complexity tracks the population one, the meta-learner finds the representation with the ideal exponent, and the estimated exponent of the downstream error improves with mm towards the ideal one. This confirms the claim of the main theorem, an improvement of the exponent, and not only a lower error at a fixed nn.

The norm penalties in the neural network experiments are heuristic proxies for JJ. There is no formal link between the spectral or ℓ1\ell_1 norm and JJ, and we do not claim one.

3. Assumption 1 and exactly representable targets (qc8Z)

We thank Reviewer qc8Z for pointing out the exactly representable case. We extended the analysis to exactly representable targets with the main theorem unchanged.

4. Gap between the theoretical setting and practice (To9V)

The theorem is for regression with exact sieved ERM over nested head classes. It establishes a provable mechanism by which pre-training improves the downstream exponent, not a model of classification with SGD and full fine-tuning. Extending complexity minimization to gradient-based optimization and fine-tuning is an important direction for future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.