Transfer bounds for linear feature learning

Andreas MaurerMachine Learning 2009 · OpenReview

Abstract

If regression tasks are sampled from a distribution, then the expected error for a future task can be estimated by the average empirical errors on the data of a finite sample of tasks, uniformly over a class of regularizing or pre-processing transformations. The bound is dimension free, justifies optimization of the pre-processing feature-map and explains the circumstances under which learning-to-learn is preferable to single task learning.

Introduction

In standard machine learning, the objective is typically to find a predictor that generalizes to new data from the same distribution as the training set. However, in many real-world scenarios, we encounter a sequence of related but distinct tasks. This paper addresses the problem of Learning-to-Learn (LTL), also known as transfer learning, where an agent seeks to leverage experience from $n$ previous tasks to improve performance on a brand-new $(n+1)$-th task.

Consider an "agency" that builds predictors for various clients. While each client has a unique problem, these problems often share an underlying structure. The central question is: how can the agency use its historical data to select a "feature map"—a pre-processing transformation—that makes learning significantly easier for future clients, even when those clients provide very few training examples?

The Challenge of Dimensionality

A significant gap in previous transfer learning theories was the dependence on the dimensionality of the input space. Traditional bounds often grew with the number of features, rendering them ineffective for high-dimensional data or infinite-dimensional kernel methods. This work provides dimension-free bounds, ensuring that the theoretical guarantees remain robust regardless of the complexity of the input space.

Methodology

The paper establishes a formal framework where tasks are sampled from a common "environment" (a distribution over distributions). The agency uses a fixed base algorithm, such as Regularized Least Squares (RLS), but modifies it using a linear operator $D$. This operator acts as a pre-processor that extracts the most relevant features from the raw data.

To derive these bounds, the author introduces several key technical components:

  • Kernel Stability: An algorithm is defined as kernel-stable if small perturbations in the Gram matrix (the matrix of inner products between data points) result in only minor changes to the empirical loss.
  • Gaussian Complexities and Slepian’s Lemma: To maintain dimension-free results, the paper avoids simple counting arguments like VC-dimension. Instead, it employs Gaussian complexities and Slepian’s Lemma—a tool for comparing Gaussian processes—to bound the complexity of the class of possible feature maps.
  • Transfer Risk: The ultimate goal is to minimize the "transfer risk," defined as the expected loss on a new task drawn from the environment, averaged over all possible training sets for that task.

Key Insights

Dimension-Free Generalization

By utilizing Schatten norms and covariance operators instead of raw dimensions, the results remain valid in infinite-dimensional Hilbert spaces. This makes the theory directly applicable to Support Vector Machines (SVMs) and other sophisticated kernel methods.

The Utility of Subspaces

The paper provides a mathematical justification for learning a $d$-dimensional subspace (a form of dimensionality reduction) across tasks. It demonstrates that the error on a new task depends on the ratio of the "useful" dimension $d$ to the number of samples $m$, rather than the total dimension of the entire space.

Multi-Task Learning vs. Learning-to-Learn

A critical distinction is made between Multi-Task Learning (MTL) and LTL. While MTL focuses on performing well on a fixed, known set of tasks, LTL requires generalizing from those tasks to the underlying environment itself to prepare for an unknown future task. LTL is inherently more challenging as it requires an additional layer of generalization.

Main Results

The primary contribution is a general bound on transfer risk. For the specific application of Regularized Least Squares, the bound is expressed as:

$$ \text{Transfer Risk} \leq \text{Average Past Empirical Error} + O\left(\frac{\sqrt{d}}{\lambda \sqrt{m}}\right) + O\left(\frac{\sqrt{d}}{\lambda \sqrt{n}}\right) $$

In this expression:

  • $d$ represents the dimension of the chosen feature subspace.
  • $m$ is the number of samples available per task.
  • $n$ is the number of tasks previously encountered.
  • $\lambda$ is the regularization parameter.

This result explicitly shows that as the number of tasks ($n$) increases, the agency's estimate of the optimal feature map becomes more accurate. This effectively "shares" the burden of learning across the entire history of tasks, allowing for successful learning on new tasks even when the per-task sample size ($m$) is small.

Limitations and Future Directions

While providing a rigorous foundation, the study notes several constraints:

  1. Linearity: The results are restricted to linear feature maps. While this encompasses kernel methods, it does not directly extend to the non-linear feature learning characteristic of deep neural networks.
  2. I.I.D. Environment: The theory assumes tasks are sampled independently and identically from a static environment, not accounting for potential "concept drift" where the environment might evolve.
  3. Computational Complexity: The focus is on the existence of generalization bounds rather than the optimization process. Finding the optimal operator $D$ remains a computationally intensive task, though the author suggests that existing practical algorithms can be analyzed through this lens.

Conclusion

This work justifies the practice of optimizing pre-processing transformations in transfer learning. By proving that the expected error on future tasks can be controlled by the average empirical error of past tasks, it provides a theoretical guarantee for the efficacy of "learning-to-learn" in high-dimensional settings.

Summary updated

Abstract

If regression tasks are sampled from a distribution, then the expected error for a future task can be estimated by the average empirical errors on the data of a finite sample of tasks, uniformly over a class of regularizing or pre-processing transformations. The bound is dimension free, justifies optimization of the pre-processing feature-map and explains the circumstances under which learning-to-learn is preferable to single task learning.
BibTeX
@article{maurer2009transfer,
  author = {Andreas Maurer},
  title = {{Transfer bounds for linear feature learning}},
  journal = {Machine Learning},
  year = {2009},
  url = {https://openreview.net/forum?id=lpMe28knwc6},
}
Figure