Adaptive Smoothed Online Multi-Task Learning

Keerthiram Murugesan, Hanxiao Liu, Jaime G. Carbonell, Yiming YangNeurIPS 2016 · OpenReview

TL;DR

This paper introduces an efficient framework for Online Multi-Task Learning that simultaneously learns individual task models and the underlying relationships between tasks. By using a "smoothed" attention mechanism and KL-divergence regularization, the authors derive closed-form, exponential update rules that achieve state-of-the-art accuracy with significantly lower computational overhead than previous methods.

What Problem Does This Paper Address?

Multi-task learning (MTL) is powerful because it allows "information-rich" tasks to help "information-poor" ones. However, most MTL methods assume that task relationships are either known beforehand or can be learned in a "batch" setting where all data is available at once.

In the online setting, data arrives in a stream. The challenge is twofold:

  1. Adaptivity: Task relationships might change over time.
  2. Efficiency: Updating a $K \times K$ relationship matrix (where $K$ is the number of tasks) at every time step is often computationally ruinous, involving expensive operations like Singular Value Decomposition (SVD) or Semi-Definite Programming (SDP).

The authors aim to bridge this gap by creating an algorithm that learns these relationships on-the-fly without sacrificing real-time performance.

Methods

The core of the paper is a new way to parameterize the task relationship matrix $\eta$: $$\eta = \alpha I + (1 - \alpha) P$$ * $\alpha$ (Concentration Factor): Determines how much a learner focuses on its own task vs. others. * $P$ (Smoothed Attention Matrix): A row-stochastic matrix where each row represents how much a specific task "attends" to all other tasks.

Key Innovations:

  • Probabilistic Regularization: In the batch setting, they use Max-Entropy regularization to encourage a uniform initial distribution of attention. In the online setting, they use Kullback–Leibler (KL) divergence to ensure that the attention matrix $P$ evolves smoothly from one time step to the next.
  • Closed-Form Updates: Unlike previous methods that require complex optimization, this formulation leads to an exponential update rule (similar to Mirror Descent). This means updating the relationship matrix is essentially just a few element-wise multiplications and a normalization step.
  • Error-Driven Updates: The model only updates when a task makes a prediction error, saving further computation.

The resulting online algorithm, OSMTL-e, utilizes these efficient update mechanisms as detailed below:

Algorithm 2: Online Algorithm (OSMTL-e)

Datasets

The authors evaluated their approach on three standard MTL benchmarks:

  1. Landmine Detection: 19 tasks (different geographical areas) to detect landmines from satellite images.
  2. Spam Detection: 15 tasks, where each task is an individual user's email inbox. The goal is to build personalized spam filters.
  3. Sentiment Analysis: 24 tasks consisting of product reviews from different Amazon domains (e.g., Books, Electronics).

Key Insights and Ideas

  • Asymmetric Sharing is Key: Unlike many models that assume task relationships are symmetric (if A relates to B, B relates to A), this model allows for directed sharing. For example, a general "Electronics" sentiment model might help a "Cell Phones" model, but the reverse might be less true.
  • The "Aha" Moment on Complexity: By shifting the problem from learning a covariance matrix (which requires SVD) to learning a row-stochastic attention matrix (which requires KL-regularization), the authors turned a "heavy" optimization problem into a "light" exponential update.
  • Theoretical Rigor: The paper proves a sub-linear regret bound. This mathematically guarantees that as the learner sees more data, its performance converges toward the best possible linear predictor that could have been chosen with the benefit of hindsight.

Key Results

The proposed algorithm, OSMTL-e (Online Smoothed Multi-Task Learning with exponential updates), showed dominant performance across the board.

AUC Performance and Task Relationship Heatmaps
  • Accuracy: It consistently outperformed baselines like PA-ITL (Independent Task Learning) and OMTRL (a previous state-of-the-art relationship learner) in terms of Area Under the Curve (AUC), as seen in the performance curves.
  • Speed: The computational gains were massive. On the Sentiment Analysis dataset, OSMTL-e took roughly 2.16 seconds, while the SVD-based OMTRL took 128 seconds—a ~60x speedup.
  • Sparsity and Clustering: The model naturally identifies clusters of related tasks. As visualized in the heatmaps above, in datasets like Landmine detection, it successfully recovered distinct terrain types without being explicitly told they existed.

Limitations and Future Work

  • Hyperparameter Sensitivity: The performance depends on the choice of $\alpha$ and the learning rate $C$. While the authors provide a principled way to set these based on the time horizon $T$, in true "infinite" streaming scenarios, these might need more complex scheduling.
  • Task Synchronization: The current formulation assumes the learner receives observations from all $K$ tasks at every round $t$. In many real-world scenarios, tasks might provide data asynchronously.
  • Binary Focus: While the authors state the method generalizes to multi-class and regression, the experimental validation is strictly focused on binary classification. Testing the "smoothing" effect on high-dimensional regression tasks remains an open area.

Summary updated

Abstract

This paper addresses the challenge of jointly learning both the per-task model parameters and the inter-task relationships in a multi-task online learning setting. The proposed algorithm features probabilistic interpretation, efficient updating rules and flexible modulation on whether learners focus on their specific task or on jointly address all tasks. The paper also proves a sub-linear regret bound as compared to the best linear predictor in hindsight. Experiments over three multi-task learning benchmark datasets show advantageous performance of the proposed approach over several state-of-the-art online multi-task learning baselines.
BibTeX
@inproceedings{murugesan2016adaptive,
  author = {Keerthiram Murugesan and Hanxiao Liu and Jaime G. Carbonell and Yiming Yang},
  title = {{Adaptive Smoothed Online Multi-Task Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=HkExD_bOWS},
}
Figure