Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes

• URL: http://arxiv.org/abs/2505.15496v2
• Date: Mon, 27 Oct 2025 12:22:36 GMT
• Title: Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes
• Abstract summary: We present new fast-rate PAC-Bayesian generalization bounds for multi-task and meta-learning in the unbalanced setting.<n>Our new bounds are numerically computable as well as interpretable.<n>We shed light on the fact that the unbalanced situation allows two meaningful definitions of multi-task risk.
• Score: 21.925083923451595
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present new fast-rate PAC-Bayesian generalization bounds for multi-task and meta-learning in the unbalanced setting, i.e. when the tasks have training sets of different sizes, as is typically the case in real-world scenarios. Previously, only standard-rate bounds were known for this situation, while fast-rate bounds were limited to the setting where all training sets are of equal size. Our new bounds are numerically computable as well as interpretable, and we demonstrate their flexibility in handling a number of cases where they give stronger guarantees than previous bounds. Besides the bounds themselves, we also make conceptual contributions: we demonstrate that the unbalanced multi-task setting has different statistical properties than the balanced situation, specifically that proofs from the balanced situation do not carry over to the unbalanced setting. Additionally, we shed light on the fact that the unbalanced situation allows two meaningful definitions of multi-task risk, depending on whether all tasks should be considered equally important or if sample-rich tasks should receive more weight than sample-poor ones.

Related papers

• A Unified Framework for Quantized and Continuous Strong Lottery Tickets [3.772827533440353]
  We provide an analysis of the Random Subset Sum Problem (RSSP) in the discrete setting, and use it to derive tight SLTH guarantees in the quantized case.<n>Our analysis obtains tight bounds on the failure probability of finding a strong lottery ticket in the quantized regime, providing an exponential improvement over previous results.
  arXiv  Detail & Related papers  (2026-07-04T13:00:39Z)
• Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness and Safety [2.538209532048867]
  We study the multi-task linear regression problem in the presence of contaminated tasks.<n>We introduce a relative balancedness condition, quantified by a balancedness constant, that compares each task's second moment with the average inlier geometry.<n>Our method achieves simultaneous adaptivity to task similarity, robustness to outliers, and safety outside favorable transfer regimes.
  arXiv  Detail & Related papers  (2026-05-16T19:06:54Z)
• In-Context Learning Is Provably Bayesian Inference: A Generalization Theory for Meta-Learning [51.56484100374058]
  We introduce a principled risk decomposition that separates the total ICL risk into two components: Bayes Gap and Posterior Variance.<n>For a uniform-attention Transformer, we derive a non-asymptotic upper bound on this gap, which explicitly clarifies the dependence on the number of pretraining prompts.<n>The Posterior Variance is a model-independent risk representing the intrinsic task uncertainty.
  arXiv  Detail & Related papers  (2025-10-13T03:42:31Z)
• Test-Time Alignment via Hypothesis Reweighting [56.71167047381817]
  Large pretrained models often struggle with underspecified tasks.<n>We propose a novel framework to address the challenge of aligning models to test-time user intent.
  arXiv  Detail & Related papers  (2024-12-11T23:02:26Z)
• Quantifying Prediction Consistency Under Fine-Tuning Multiplicity in Tabular LLMs [10.494477811252034]
  Fine-tuning multiplicity can arise in Tabular LLMs on classification tasks.<n>Our work formalizes this unique challenge of fine-tuning multiplicity in Tabular LLMs.<n>We propose a novel measure to quantify consistency of individual predictions without expensive model retraining.
  arXiv  Detail & Related papers  (2024-07-04T22:22:09Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Robust Multi-Task Learning with Excess Risks [24.695243608197835]
  Multi-task learning (MTL) considers learning a joint model for multiple tasks by optimizing a convex combination of all task losses. Existing methods use an adaptive weight updating scheme, where task weights are dynamically adjusted based on their respective losses to prioritize difficult tasks. We propose Multi-Task Learning with Excess Risks (ExcessMTL), an excess risk-based task balancing method that updates the task weights by their distances to convergence.
  arXiv  Detail & Related papers  (2024-02-03T03:46:14Z)
• Byzantine-Tolerant Methods for Distributed Variational Inequalities [12.340793486560658]
  Byzantine robustness is a necessity for various distributed training scenarios. Our work makes a further step in this direction by providing severalprovably Byzantine-robust methods for distributed variational inequality.
  arXiv  Detail & Related papers  (2023-11-08T11:18:17Z)
• Fair Few-shot Learning with Auxiliary Sets [53.30014767684218]
  In many machine learning (ML) tasks, only very few labeled data samples can be collected, which can lead to inferior fairness performance. In this paper, we define the fairness-aware learning task with limited training samples as the emphfair few-shot learning problem. We devise a novel framework that accumulates fairness-aware knowledge across different meta-training tasks and then generalizes the learned knowledge to meta-test tasks.
  arXiv  Detail & Related papers  (2023-08-28T06:31:37Z)
• Continual Learning in Linear Classification on Separable Data [34.78569443156924]
  We show that learning with weak regularization reduces to solving a sequential max-margin problem. We then develop upper bounds on the forgetting and other quantities of interest under various settings. We discuss several practical implications to popular training practices like regularization scheduling and weighting.
  arXiv  Detail & Related papers  (2023-06-06T09:34:11Z)
• Towards Practical Few-Shot Query Sets: Transductive Minimum Description Length Inference [0.0]
  We introduce a PrimAl Dual Minimum Description LEngth (PADDLE) formulation, which balances data-fitting accuracy and model complexity for a given few-shot task. Our constrained MDL-like objective promotes competition among a large set of possible classes, preserving only effective classes that befit better the data of a few-shot task.
  arXiv  Detail & Related papers  (2022-10-26T08:06:57Z)
• On Steering Multi-Annotations per Sample for Multi-Task Learning [79.98259057711044]
  The study of multi-task learning has drawn great attention from the community. Despite the remarkable progress, the challenge of optimally learning different tasks simultaneously remains to be explored. Previous works attempt to modify the gradients from different tasks. Yet these methods give a subjective assumption of the relationship between tasks, and the modified gradient may be less accurate. In this paper, we introduce Task Allocation(STA), a mechanism that addresses this issue by a task allocation approach, in which each sample is randomly allocated a subset of tasks. For further progress, we propose Interleaved Task Allocation(ISTA) to iteratively allocate all
  arXiv  Detail & Related papers  (2022-03-06T11:57:18Z)
• Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound [18.92870267111897]
  We provide the first PAC-Bayes bound capable of providing rich information by bounding the Kullback-Leibler divergence.<n>Our bound is especially useful in cases where the severity of different mis-classifications may change over time.
  arXiv  Detail & Related papers  (2022-02-11T11:35:21Z)
• In Defense of the Unitary Scalarization for Deep Multi-Task Learning [121.76421174107463]
  We present a theoretical analysis suggesting that many specialized multi-tasks can be interpreted as forms of regularization. We show that, when coupled with standard regularization and stabilization techniques, unitary scalarization matches or improves upon the performance of complex multitasks.
  arXiv  Detail & Related papers  (2022-01-11T18:44:17Z)
• New Tight Relaxations of Rank Minimization for Multi-Task Learning [161.23314844751556]
  We propose two novel multi-task learning formulations based on two regularization terms. We show that our methods can correctly recover the low-rank structure shared across tasks, and outperform related multi-task learning methods.
  arXiv  Detail & Related papers  (2021-12-09T07:29:57Z)
• Few-Shot Learning with Class Imbalance [13.60699610822265]
  Few-shot learning aims to train models on a limited number of labeled samples given in a support set in order to generalize to unseen samples from a query set. In the standard setup, the support set contains an equal amount of data points for each class. We present a detailed study of few-shot class-imbalance along three axes: meta-dataset vs. task imbalance, effect of different imbalance distributions (linear, step, random), and effect of rebalancing techniques.
  arXiv  Detail & Related papers  (2021-01-07T12:54:32Z)
• Low Resource Multi-Task Sequence Tagging -- Revisiting Dynamic Conditional Random Fields [67.51177964010967]
  We compare different models for low resource multi-task sequence tagging that leverage dependencies between label sequences for different tasks. We find that explicit modeling of inter-dependencies between task predictions outperforms single-task as well as standard multi-task models.
  arXiv  Detail & Related papers  (2020-05-01T07:11:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.