One-shot learning and big data with n=2

Lee H. Dicker, Dean P. FosterNeurIPS 2013

This paper, "One-shot learning and big data with $n=2$," by Lee H. Dicker and Dean P. Foster, explores a fascinating intersection of high-dimensional statistics and machine learning. It challenges the conventional wisdom of "big data" by showing that when you have a massive number of features, you can actually learn effectively from an incredibly small number of examples.

The Challenge: High-Dimension, Low-Sample Size

Most modern machine learning algorithms are notoriously "data-hungry," requiring thousands or even millions of examples to generalize well. However, humans can often learn a new concept from just one or two instances—a capability known as one-shot learning.

In statistical terms, this scenario is a "high-dimension, low-sample size" (HDLSS) problem. Usually, when the number of features ($d$) is much larger than the number of observations ($n$), models are highly prone to overfitting. The standard statistical remedy is to use "shrinkage" methods (like Lasso or Ridge regression) to pull parameter estimates toward zero, reducing variance at the cost of some bias.

The authors ask a provocative question: Can we turn the "curse of dimensionality" into a "blessing"? They investigate whether having a very large $d$ provides enough "contextual information" to make prediction easier, even when $n$ is tiny (e.g., $n=2$).

Methodology: Expanding Instead of Shrinking

To tackle this, the authors propose a latent factor model. They assume there is a hidden variable ($h$) that links the outcome ($y$) we want to predict with the high-dimensional context vector ($x$).

  1. Standard PCR: Traditionally, Principal Component Regression (PCR) finds the directions (principal components) in the $x$-data that explain the most variance and uses them to predict $y$.
  2. The Inconsistency Discovery: The authors prove mathematically that in the one-shot regime (where $n$ is fixed and $d \to \infty$), the classical PCR estimator is inconsistent. It consistently underestimates the true relationship because the sample eigenvalues in such extreme dimensions are heavily biased.
  3. Bias-Corrected PCR (The "Expansion" Method): To fix this inconsistency, they introduce a bias-corrected estimator. Unlike standard regularization techniques that shrink coefficients (multiplying by a factor $c < 1$), their method actually expands the estimator by multiplying it by a factor $c > 1$. Specifically, they use the ratio of the largest eigenvalue to the difference between the largest and smallest eigenvalues: $\frac{l_1}{l_1 - l_n}$.
Theoretical prediction error formulas for standard PCR, bias-corrected PCR, and the oracle estimator.

Experimental Setup

The paper relies on rigorously designed simulated datasets to test their mathematical theories, focusing on establishing the fundamental statistical properties of the "expansion" phenomenon rather than benchmarking on real-world datasets like ImageNet.

  • Parameters: They varied the number of features $d$ (up to 5,000) and the number of training examples $n$ (from 2 to 20).
  • Setup: They simulated 1,000 independent datasets for each configuration to compare the empirical prediction error against their theoretical risk approximations.

Key Insights and Results

The findings challenge traditional statistical intuition in several ways:

  • More Context is Better: Counter-intuitively, as the number of features $d$ increases, the prediction problem actually becomes easier. The high dimensionality provides a clearer "signal" for the underlying latent factor.
  • Expansion > Shrinkage: In high-dimensional settings with tiny samples, the noise in the sample covariance matrix causes standard estimators to be too small. Expanding the estimator corrects this bias.
  • Consistency at $n=2$: They prove that their bias-corrected method is "weakly consistent." This means that as you add more features ($d \to \infty$), the prediction error approaches zero, even if you only ever have two training points.

In the simulations, the bias-corrected PCR consistently outperformed standard PCR. Remarkably, the bias-corrected version achieved lower error with just 9 examples than standard PCR did with 20 examples. Furthermore, the bias-corrected estimator performed nearly as well as an "oracle" estimator—a theoretical model that already knows the true underlying structure of the data.

Empirical and theoretical prediction errors comparing PCR, Bias-corrected PCR, and Oracle estimators.

Limitations and Future Work

While groundbreaking, the paper outlines several areas for future exploration:

  • Single Latent Factor: The primary analysis assumes a single latent factor connects $x$ and $y$. While they discuss multi-factor extensions, the mathematics become significantly more complex.
  • Gaussian Assumptions: The proofs rely on the data being normally distributed (Gaussian). It remains to be seen how robust these results are under "heavy-tailed" or non-normal real-world data distributions.
  • Semi-Supervised Potential: The authors suggest their work could be naturally extended to semi-supervised learning, where a model uses a few labeled examples alongside a vast amount of unlabeled data to better identify the principal components.
  • Classification: While this paper focuses on continuous outcomes (regression), the authors note that these expansion concepts could be adapted for one-shot classification problems in the future.

Summary updated

BibTeX
@inproceedings{dicker2013one,
  author = {Lee H. Dicker and Dean P. Foster},
  title = {{One-shot learning and big data with n=2}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
}
Figure