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

arXiv: https://arxiv.org/abs/2502.18167 · HTML: https://mlsanity.com/paper/2502.18167/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 25 Feb 2025.

## Builds on (most cited first, 19 of 19)

- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [Multi-Task Deep Neural Networks for Natural Language Understanding](https://mlsanity.com/paper/1901.11504/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Multi-Task Learning in Natural Language Processing: An Overview](https://mlsanity.com/paper/2109.09138/) (2021)
- [Learning with Multiclass AUC: Theory and Algorithms](https://mlsanity.com/paper/2107.13171/) (2021)
- [Learning Internal Representations (COLT 1995)](https://mlsanity.com/paper/1911.05781/) (2019)
- [Generalization bounds for neural ordinary differential equations and deep residual networks](https://mlsanity.com/paper/2305.06648/) (2023)
- [Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning](https://mlsanity.com/paper/1602.05916/) (2016)
- [McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds](https://mlsanity.com/paper/1909.02330/) (2019)
- [Generalization Bounds for Neural Networks via Approximate Description Length](https://mlsanity.com/paper/1910.05697/) (2019)
- [An extension of McDiarmid's inequality](https://mlsanity.com/paper/1511.05240/) (2015)
- [LocalDrop: A Hybrid Regularization for Deep Neural Networks](https://mlsanity.com/paper/2103.00719/) (2021)
- [Multi-task and Lifelong Learning of Kernels](https://mlsanity.com/paper/1602.06531/) (2016)
- [MultiMatch: Multi-task Learning for Semi-supervised Domain Generalization](https://mlsanity.com/paper/2208.05853/) (2022)
- [Fast GraspNeXt: A Fast Self-Attention Neural Network Architecture for Multi-task Learning in Computer Vision Tasks for Robotic Grasping on the Edge](https://mlsanity.com/paper/2304.11196/) (2023)
- [Generalization bounds for learning under graph-dependence: A survey](https://mlsanity.com/paper/2203.13534/) (2022)
- [Semi-supervised Vector-valued Learning: Improved Bounds and Algorithms](https://mlsanity.com/paper/1909.04883/) (2019)
- [An Empirical Study on Regularization of Deep Neural Networks by Local Rademacher Complexity](https://mlsanity.com/paper/1902.00873/) (2019)

## Abstract (arXiv)

In multi-task learning (MTL) with each task involving graph-dependent data, existing generalization analyses yield a sub-optimal risk bound of O(frac1√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(fraclog nn). 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.