Multi-Task Learning and Algorithmic Stability

Yu ZhangAAAI 2015 · DOI

Abstract

Multi-Task Learning (MTL) has emerged as a robust paradigm for improving model performance by learning multiple related tasks simultaneously. However, theoretical guarantees for the generalization of regularized MTL models have remained elusive. This paper introduces a novel theoretical framework based on algorithmic stability. By defining Multi-Task Uniform Stability and proving a Generalized McDiarmid’s Inequality, we provide the first formal generalization bounds for several popular MTL models, including those utilizing task covariance and trace-norm regularization. Our results highlight the critical role of $\ell_2$ regularization as a mathematical stabilizer in ensuring reliable generalization.

1. Introduction

Multi-Task Learning (MTL) leverages the shared information between related tasks to improve the predictive performance of each individual task. While empirically successful, the theoretical justification for why these models generalize well to unseen data has often been restricted to specific settings. Traditional tools for analyzing generalization, such as VC dimension or Rademacher complexity, are frequently difficult to apply to the "regularized" objective functions common in MTL, such as those involving Lasso or Ridge-style penalties.

Algorithmic stability—a measure of how much a model's output changes in response to small perturbations in the training data—offers a more natural framework for analyzing regularized models. However, standard stability definitions were designed for single-task learning. This paper bridges this gap by extending stability theory to the multi-task setting, providing a rigorous foundation for understanding the generalization properties of complex MTL algorithms.

2. Theoretical Framework

2.1 Multi-Task Uniform Stability

The primary challenge in applying stability to MTL is the interconnected nature of the tasks. In single-task learning, stability is typically measured by removing one data point. In this work, we define Multi-Task Uniform Stability. This new definition considers the impact of removing exactly one data point from every task simultaneously. This approach captures the global sensitivity of the MTL model to changes across its entire training set, reflecting how information is shared across task boundaries.

2.2 Generalized McDiarmid’s Inequality

To translate stability into a generalization bound (a mathematical guarantee on performance on unseen data), a concentration inequality is required. The standard McDiarmid’s inequality is limited to functions where only one input changes at a time. To accommodate the multi-task setting where multiple data points (one per task) are modified, we prove a Generalized McDiarmid’s Inequality. This theorem allows us to bound the deviation between empirical error and true error even when multiple inputs change simultaneously, provided the algorithm remains stable.

3. Generalization Bounds for MTL Models

Using the developed framework, we analyze three major classes of MTL algorithms:

  1. Learning with Task Covariance: Models that explicitly estimate the relationship matrix ($\Omega$) between tasks.
  2. Trace Norm Regularization: Models that assume task parameters share a low-dimensional subspace.
  3. Composite Sparse Norms: Models that decompose parameters into low-rank and sparse components.

3.1 Key Results

The paper provides concrete upper bounds for the generalization error ($R$) of these algorithms. For an algorithm $\mathcal{A}$ with stability $\tau$ and $n_0$ samples per task, the generalization error is bounded by:

$$R(\mathcal{A}, \mathcal{S}) \leq R_{emp}(\mathcal{A}, \mathcal{S}) + 2\tau + \text{confidence terms}$$

For models learning task relations, the stability $\tau$ is shown to be proportional to $\frac{\lambda_1(\Omega)m}{n_0}$, where $\lambda_1$ is the largest eigenvalue of the covariance matrix and $m$ is the number of tasks. This formally demonstrates that as the number of samples per task ($n_0$) increases, the model's stability improves, leading to tighter generalization guarantees.

3.2 The Role of the Stabilizer

A significant insight from this analysis is the "Sparse Norm Trap." We demonstrate that models using only sparse regularizers (like pure trace norm) may lack the necessary stability to guarantee generalization. The addition of a squared Frobenius norm (an $\ell_2$ penalty) acts as a mathematical stabilizer. For trace-norm models with an $\ell_2$ penalty ($\beta$), the stability is bounded by:

$$\tau \leq \frac{2\kappa^2\sigma^2m}{\beta n_0}$$

This result highlights that the $\beta$ term is not merely a heuristic but a theoretical necessity to prevent the stability coefficient from exploding, thereby ensuring the model generalizes reliably.

4. Discussion and Limitations

While this framework provides a powerful new lens for MTL, several areas remain for future exploration:

  • Sample Distribution: The current proofs assume a uniform sample size across all tasks ($n_i = n_0$). Future work should address scenarios where tasks have highly imbalanced data distributions.
  • Stability Definitions: This paper focuses on uniform stability, the strongest form of stability. Extending these bounds to weaker forms, such as leave-one-out stability, could yield even tighter bounds for certain classes of algorithms.
  • Model Complexity: The specific applications discussed focus on linear models. Extending this stability framework to non-linear architectures, such as deep multi-task neural networks, remains a significant open challenge.

5. Conclusion

By introducing Multi-Task Uniform Stability and the Generalized McDiarmid’s Inequality, this work provides a rigorous theoretical foundation for Multi-Task Learning. We show that MTL can be more stable than individual task learning when tasks are highly related, and we identify the crucial role of $\ell_2$ regularization in stabilizing sparse MTL models. These insights provide both a justification for current MTL practices and a roadmap for developing more robust multi-task algorithms.

Summary updated

BibTeX
@inproceedings{zhang2015multi,
  author = {Yu Zhang},
  title = {{Multi-Task Learning and Algorithmic Stability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9558},
}
Figure