Research map / Learning theory and algorithms / Kernels and regression theory
Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives the first fast-rate (kl-style and Catoni-style) PAC-Bayesian generalization bounds for unbalanced multi-task and meta-learning, in both task-centric and sample-centric risk definitions.
Problem
Existing fast-rate PAC-Bayesian multi-task and meta-learning bounds only hold when all tasks have equal training set sizes; unbalanced settings have only standard-rate bounds, and naive fast-rate proofs depend on the minimum task sample size.
Approach
Replaces the balanced proof technique (single MGF over pooled Bernoulli variables) with per-task change-of-measure terms that yield per-task kl or Catoni terms weighted by sample sizes, and introduces task-centric versus sample-centric multi-task risks, extended to meta-learning.
Key results
- On split-CIFAR10 task-centric, the kl-style fast-rate bound gives 0.2717 versus 0.3068 for the standard-rate bound; the joint-constraint bound gives 0.2705.
- On split-CIFAR10 sample-centric, the Catoni-style fast-rate bound gives 0.2621 versus 0.3002 for the standard-rate bound.
- The naive fast-rate bound with m_min (0.3467 on CIFAR10 task-centric) is looser than the standard-rate bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the task-centric kl-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR10 | generalization bound: 0.3068328072912082 -> 0.27165681352782367 | Helped |
| use the task-centric kl-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR100 | generalization bound: 0.5947962787187728 -> 0.5912170334604309 | Helped |
| use the task-centric Catoni-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR10 | generalization bound: 0.3068328072912082 -> 0.2709879892608734 | Helped |
| use the task-centric Catoni-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR100 | generalization bound: 0.5947962787187728 -> 0.591102036611135 | Helped |
| combine the task-centric kl-style and Catoni-style bounds with a joint constraint | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR10 | generalization bound: 0.27165681352782367 / 0.2709879892608734 -> 0.27047403890096644 | Helped |
| combine the task-centric kl-style and Catoni-style bounds with a joint constraint | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR100 | generalization bound: 0.5912170334604309 / 0.591102036611135 -> 0.590689756198559 | Helped |
| use the sample-centric kl-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR10 | generalization bound: 0.30019207851214524 -> 0.2648635057681427 | Helped |
| use the sample-centric kl-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR100 | generalization bound: 0.5947181124725951 -> 0.5928530544615933 | Helped |
| use the sample-centric Catoni-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR10 | generalization bound: 0.30019207851214524 -> 0.2621240871614677 | Helped |
| use the sample-centric Catoni-style fast-rate bound instead of the standard-rate bound | unbalanced MTL with a low-rank Vision Transformer · split-CIFAR100 | generalization bound: 0.5947181124725951 -> 0.5897834383676699 | Helped |
| use the naive fast-rate bound determined by m_min instead of the standard-rate bound | task-centric unbalanced MTL with a low-rank Vision Transformer · split-CIFAR10 | generalization bound: 0.3068328072912082 -> 0.3467360063173952 | Hurt |
| use the naive fast-rate bound determined by m_min instead of the standard-rate bound | task-centric unbalanced MTL with a low-rank Vision Transformer · split-CIFAR100 | generalization bound: 0.5947962787187728 -> 0.6161623959107059 | Hurt |
Surprising findings
- Existing balanced fast-rate proof techniques do not carry over to the unbalanced setting; the MGF of the inverse-size-weighted kl is infinite for lambda above m_min.
- The naive fast-rate bound with m_min is always looser than even the standard-rate bound in the experiments.
Limitations
- Resulting bounds are less interpretable than explicit standard-rate bounds and require numerical optimization.
- Fast-rate advantage diminishes when empirical error is large (e.g., split-CIFAR100).
- Lambda values are chosen from a finite candidate set via union bound, so optimization is not free of cost.
Experimental setup
Datasets: MDPR split-CIFAR10 split-CIFAR100 ImageNet
Benchmarks: MDPR split-CIFAR10 split-CIFAR100
Metrics: generalization bound value on risk (task-centric and sample-
Baselines: standard-rate PAC-Bayesian multi-task bound naive fast-rate bound with m_min single-task kl bound
Builds on: PAC-Bayesian multi-task learning bounds kl-style fast-rate PAC-Bayes bounds Catoni bound PAC-Bayes meta-learning (Pentina & Lampert style)
Closest papers by meaning
- Fast-Rate PAC-Bayesian Generalization Bounds for Meta-Learning (ICML 2022 · similarity 0.91)
- Bayesian Uncertainty for Gradient Aggregation in Multi-Task Learning (ICML 2024 · similarity 0.88)
- More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithms (ICML 2024 · similarity 0.87)
- On the Stability and Generalization of Meta-Learning (NeurIPS 2024 · similarity 0.87)
- Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks (ICML 2025 · similarity 0.86)
- Theoretical Investigations and Practical Enhancements on Tail Task Risk Minimization in Meta Learning (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.