When we train a machine learning model to solve a single task, its sample complexity—the amount of data required to achieve a target generalization error—is governed by the complexity of the hypothesis space. If we want the model to learn $r$ different tasks, a naive baseline approach is to train $r$ independent models. Under standard statistical learning theory, the total sample complexity of this independent approach scales linearly with the number of tasks. This is known as the linear scaling baseline, a direct consequence of the union bound.
However, empirical evidence consistently demonstrates that joint training allows models to achieve high accuracy with significantly less data per task than single-task baselines. This gap between independent linear scaling and joint efficiency introduces a fundamental question in learning theory: Can the total sample complexity of learning multiple tasks simultaneously be strictly less than the sum of their individual complexities?
This question is formalized as the "direct sum" problem in learning theory, and a growing body of research seeks to map the exact mathematical boundaries that allow joint optimization to break the linear scaling baseline.
The Direct Sum Problem
In classical computational complexity, a direct sum property implies that the resources needed to solve $r$ independent problems scale as the sum of the resources required for each problem individually. In Open problem: Direct Sums in Learning Theory, Shay Moran, Steve Hanneke, and Tom Waknine formalize whether this baseline holds true for sample complexity across various learning paradigms, such as PAC and agnostic learning.
If tasks are completely independent and share no underlying structure, standard uniform convergence models dictate that parallel learning offers no statistical shortcuts. As explored by the authors in List Sample Compression and Uniform Convergence, proving sub-linear scaling for entirely unrelated concepts remains an elusive theoretical challenge. To break the direct sum baseline, a learning system must exploit some form of shared structural constraint.
Amortizing Complexity via Shared Representations
The primary mechanism for beating the linear scaling baseline is the mathematical restriction of the joint hypothesis space. Instead of allowing each task to choose any arbitrary function, multi-task learning forces tasks to share an underlying representation layer.
Independent Learning (Linear Scaling):
Task 1: Data ──> [ High-Dim Feature Space 1 ] ──> Predictor 1
Task 2: Data ──> [ High-Dim Feature Space 2 ] ──> Predictor 2
Joint Learning (Sub-linear Scaling):
Task 1: Data ──┐
├──> [ Shared Low-Dim Subspace ] ──┬──> Predictor 1
Task 2: Data ──┘ └──> Predictor 2
In a foundational analysis, Andreas Maurer demonstrated in Bounds for Linear Multi-Task Learning that forcing tasks to share a common linear preprocessor yields dimension-free generalization bounds. When multiple tasks pass through the same low-dimensional bottleneck, the data from Task $A$ implicitly restricts the search space for Task $B$. This concept was extended to unsupervised dictionary learning by Maurer et al. in Sparse coding for multitask and transfer learning, proving that the generalization error of a shared sparse code shrinks as the number of tasks increases, effectively accelerating the overall learning rate.
In deep neural networks, this phenomenon can be quantified through the lens of dimensionality reduction. Hossein Zakerinia et al. introduced the concept of Amortized Intrinsic Dimensionality (AID) in From Low Intrinsic Dimensionality to Non-Vacuous Generalization Bounds in Deep Multi-Task Learning. They proved that deep multi-task networks parameterize multiple functions within a shared subspace whose intrinsic dimensionality is significantly lower than the combined dimensions required to learn each task in isolation. This compression provides the mathematical justification for non-vacuous generalization guarantees in deep architectures.
Quantifying the Currency of Task Relatedness
To guarantee that joint learning reduces sample complexity, we must replace vague notions of "similar tasks" with rigorous mathematical metrics.
Early frameworks, such as the one proposed by Reba Schuller et al. in Exploiting Task Relatedness for Mulitple Task Learning, shifted the definition of relatedness away from functional similarity and toward shared data-generating mechanisms. By proving that tasks originating from a common environmental mixture share structural invariants, the authors derived bounds showing a clear sample complexity advantage over independent learning.
This structural overlap directly dictates the speed limits of model convergence. In Learning Rates for Multi-task Regularization Networks, Haizhang Zhang utilized vector-valued reproducing kernel Hilbert spaces (RKHS) to derive explicit learning rates, showing how the volume of data and the number of tasks interact to dictate accuracy.
Depending on the domain, this similarity can be measured in distinct ways:
- Metric Learning: Boyu Wang et al. established a formal link between task similarity and convergence rates in Multitask Metric Learning: Theory and Algorithm, demonstrating that pooling distance metrics across tasks prevents overfitting when data is scarce—a challenge previously highlighted by Kaizhu Huang et al. in A review on multi-task metric learning.
- Control Theory: In Policy Gradient Bounds in Multitask LQR, Charis J. Stamouli et al. introduced a bisimulation-based measure of task similarity for Linear Quadratic Regulation (LQR), bypassing overly conservative classical bounds to prove tighter convergence guarantees for joint policy gradient methods.
The Optimization Reality
While statistical bounds prove what is possible, optimization dynamics dictate what is achievable. Joint training does not always guarantee efficiency; the success of breaking the direct sum baseline depends heavily on how the tasks interact during gradient descent.
When tasks are loosely related, distribution divergence can actively harm performance. Axel Kerinec et al. demonstrated in When does deep multi-task learning work for loosely related document classification tasks? that the Jensen-Shannon Divergence between task data distributions serves as a strong negative predictor of multi-task success. If the distributions diverge too sharply, the shared representation becomes conflicted, destroying any sample complexity advantage.
Conversely, when tasks align well, the optimization benefits extend beyond simple data pooling. Joachim Bingel et al. discovered in Identifying beneficial task relations for multi-task learning in deep neural networks that multi-task learning often succeeds because an auxiliary task fundamentally alters the loss landscape. Specifically, if a main task is prone to getting stuck in local minima, an auxiliary task with a different learning speed can act as an optimization regularizer, guiding gradient descent toward better global solutions.
This interplay explains why empirical frameworks—whether applied systematically across natural language processing pipelines as evaluated by Jianquan Li et al. in Empirical evaluation of multi-task learning in deep neural networks for natural language processing, or mapped to evolutionary hierarchies in computational biology by Christian Widmer et al. in Multitask Learning in Computational Biology—can bypass the pessimistic constraints of independent learning. By compressing the effective dimensionality of the hypothesis space and smoothing the optimization path, joint learning transforms the direct sum from a strict linear barrier into a sub-linear curve of scalable efficiency.
Key Foundational Work
Exploiting Task Relatedness for Mulitple Task Learning (2003) — contributed 2 concept elements to this direction.
Bounds for Linear Multi-Task Learning (2006) — contributed 2 concept elements to this direction.