Sharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data

• URL: http://arxiv.org/abs/2502.18167v3
• Date: Wed, 21 May 2025 01:15:38 GMT
• Title: Sharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data
• Abstract summary: Existing generalization analyses yield a emphsub-optimal risk bound of $O(frac1sqrtn)$, where $n$ is the number of training samples of each task.<n>This paper proposes a new Bennett-type inequality, enabling the derivation of a sharper risk bound of $O(fraclog nn)$.
• Score: 5.42833955464548
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In multi-task learning (MTL) with each task involving graph-dependent data, existing generalization analyses yield a \emph{sub-optimal} risk bound of $O(\frac{1}{\sqrt{n}})$, where $n$ is the number of training samples of each task. However, to improve the risk bound is technically challenging, which is attributed to the lack of a foundational sharper concentration inequality for multi-graph dependent random variables. To fill up this gap, this paper proposes a new Bennett-type inequality, enabling the derivation of a sharper risk bound of $O(\frac{\log n}{n})$. Technically, building on the proposed Bennett-type inequality, we propose a new Talagrand-type inequality for the empirical process, and further develop a new analytical framework of the local fractional Rademacher complexity to enhance generalization analyses in MTL with multi-graph dependent data. Finally, we apply the theoretical advancements to applications such as Macro-AUC optimization, illustrating the superiority of our theoretical results over prior work, which is also verified by experimental results.

Related papers

• Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms [5.54992643082602]
  We study a contaminated multi-task empirical risk minimization framework.<n>Our goal is to estimate both the global minimizer of the average risk and the clean task-specific minimizers.<n>We propose a computationally efficient filtering-based robust multi-task gradient descent method.
  arXiv  Detail & Related papers  (2026-07-02T18:23:41Z)
• A Refined Generalization Analysis for Extreme Multi-class Supervised Contrastive Representation Learning [15.903047134800453]
  We prove a bound with a sample complexity of the same order as the number of classes $R$, regardless of the distribution over classes.<n>We also formulate a different estimator that captures the concentration of the risk textitacross classes.
  arXiv  Detail & Related papers  (2026-05-08T11:12:43Z)
• 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)
• On the sample complexity of semi-supervised multi-objective learning [17.947890912560162]
  In multi-objective learning, several possibly competing prediction tasks must be solved jointly by a single model.<n>For objectives defined with Bregman losses, we prove that the complexity of $mathcalG$ may come into play only in terms of unlabeled data.<n>These rates are achieved by a simple, semi-supervised algorithm via pseudo-labeling.
  arXiv  Detail & Related papers  (2025-08-23T22:15:36Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Simple Semi-supervised Knowledge Distillation from Vision-Language Models via $\mathbf{\ exttt{D}}$ual-$\mathbf{\ exttt{H}}$ead $\mathbf{\ exttt{O}}$ptimization [49.2338910653152]
  Vision-constrained models (VLMs) have achieved remarkable success across diverse tasks by leveraging rich textual information with minimal labeled data.<n> Knowledge distillation (KD) offers a well-established solution to this problem; however, recent KD approaches from VLMs often involve multi-stage training or additional tuning.<n>We propose $mathbftextttDHO$ -- a simple yet effective KD framework that transfers knowledge from VLMs to compact, task-specific models in semi-language settings.
  arXiv  Detail & Related papers  (2025-05-12T15:39:51Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning [85.75164588939185]
  We study the discriminative probabilistic modeling on a continuous domain for the data prediction task of (multimodal) self-supervised representation learning.<n>We conduct generalization error analysis to reveal the limitation of current InfoNCE-based contrastive loss for self-supervised representation learning.<n>We propose a novel non-parametric method for approximating the sum of conditional probability densities required by MIS.
  arXiv  Detail & Related papers  (2024-10-11T18:02:46Z)
• DCILP: A Distributed Approach for Large-Scale Causal Structure Learning [4.551283926017506]
  Causal learning tackles the computationally demanding task of estimating causal graphs.<n>This paper introduces a new divide-and-conquer approach for causal graph learning, called DCILP.
  arXiv  Detail & Related papers  (2024-06-15T03:17:48Z)
• FAIRM: Learning invariant representations for algorithmic fairness and domain generalization with minimax optimality [15.71499916304475]
  We propose a training environment-based oracle, FAIRM, which has desirable fairness and domain generalization properties under a diversity-type condition. We develop efficient algorithms to realize FAIRM in linear models and demonstrate the nonasymptotic performance with minimax optimality.
  arXiv  Detail & Related papers  (2024-04-02T03:06:25Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data [4.971690889257356]
  We introduce an adaptation of the alternating minimization-descent scheme proposed by Collins and Nayer and Vaswani. We show that vanilla alternating-minimization descent fails catastrophically even for iid, but mildly non-isotropic data. Our analysis unifies and generalizes prior work, and provides a flexible framework for a wider range of applications.
  arXiv  Detail & Related papers  (2023-08-08T17:56:20Z)
• Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity [41.772562538698395]
  Multitask learning methods improve efficiency by leveraging commonalities across datasets.<n>We study multitask linear regression and contextual bandits under sparse heterogeneity.<n>We show that our methods are minimax optimal by providing a number of lower bounds.
  arXiv  Detail & Related papers  (2023-06-09T22:48:13Z)
• On the Stability and Generalization of Triplet Learning [55.75784102837832]
  Triplet learning, i.e. learning from triplet data, has attracted much attention in computer vision tasks. This paper investigates the generalization guarantees of triplet learning by leveraging the stability analysis.
  arXiv  Detail & Related papers  (2023-02-20T07:32:50Z)
• On the Generalization for Transfer Learning: An Information-Theoretic Analysis [8.102199960821165]
  We give an information-theoretic analysis of the generalization error and excess risk of transfer learning algorithms. Our results suggest, perhaps as expected, that the Kullback-Leibler divergenceD(mu|mu')$ plays an important role in the characterizations. We then generalize the mutual information bound with other divergences such as $phi$-divergence and Wasserstein distance.
  arXiv  Detail & Related papers  (2022-07-12T08:20:41Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms. We develop a general framework from the perspective of Bregman minimization divergence. We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
  arXiv  Detail & Related papers  (2021-12-07T01:23:20Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Applications [25.410110072480187]
  Wasserstein distances are sensitive to outliers in the considered distributions. We propose a new outlier-robust Wasserstein distance $mathsfW_pvarepsilon$ which allows for $varepsilon$ outlier mass to be removed from each contaminated distribution.
  arXiv  Detail & Related papers  (2021-11-02T04:05:45Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
  This paper establishes a precise high-dimensional theory for boosting on separable data. Under a class of statistical models, we provide an exact analysis of the universality error of boosting. We also explicitly pin down the relation between the boosting test error and the optimal Bayes error.
  arXiv  Detail & Related papers  (2020-02-05T00:24:53Z)

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.