Multi-Observation Regression

Rafael M. Frongillo, Nishant A. Mehta, Tom Morgan, Bo Waggoner

Executive Summary

Traditional regression learns from single data-label pairs, but many important statistics—like variance or financial risk measures—are much easier to learn using multiple observations at once. This paper introduces "multi-observation regression," providing the first practical algorithms and theoretical guarantees for training models on standard datasets where only one label is available per input.

Introduction: The Elicitation Complexity Gap

In standard machine learning, Empirical Risk Minimization (ERM) is used to find a hypothesis that minimizes a loss function $\ell(f(x), y)$. This works well for predicting the mean (using squared loss) or the median (using absolute loss). However, some properties of a distribution, such as its variance, are "impossible" to learn directly from a single observation—a concept known as elicitation complexity.

While researchers recently proposed "multi-observation losses" of the form $\ell(f(x), y_1, \dots, y_m)$, these assume a luxury rarely found in real-world data: having multiple labels for the exact same input $x$. In most regression datasets, every $x$ is unique. This paper addresses the fundamental gap: how to utilize multi-observation losses when only one label per point is available.

Methodology: Constructing Metasamples

The authors propose a strategy of constructing metasamples. By "clumping" together nearby data points, they create synthetic training instances that look like $(x, y_1, \dots, y_m)$. They introduce four primary algorithms to achieve this:

  1. Naïve Sampling: For each base point, it finds the $m$ nearest neighbors to form a metasample.
  2. Improved Sampling: A more sophisticated version using global matching to ensure resulting samples are independent and identically distributed (i.i.d.), which is crucial for theoretical guarantees.
Algorithms 1 and 2: Naïve and Improved Sampling strategies for metasample construction.
  1. Sliding Window: Sorts data by $x$ and creates metasamples from every overlapping group of $m$ adjacent points.
  2. $\epsilon$-Nearby: Constructs metasamples from all possible $m$-tuples of points whose $x$-values fall within a small distance $\epsilon$.
Algorithms 3 and 4: Sliding Window and $\epsilon$-Nearby approaches for efficient data reuse.

The paper provides a rigorous theoretical analysis, proving "excess risk bounds." They demonstrate that even if labels in a clump come from slightly different $x$ values, the error remains bounded as long as the underlying distribution changes smoothly (a Lipschitz assumption).

Experimental Evaluation

Because this is a foundational theoretical paper, the authors use synthetic datasets to evaluate their algorithms. Synthetic data is necessary because, unlike standard regression, ground truth for higher-order statistics (like true conditional variance) is required to measure performance.

  • Variance Regression: Data generated from sine waves and linear functions with Gaussian noise.
  • Risk Measures (UCB & MINVAR): Data generated from Gamma and Exponential distributions to test the ability to learn complex financial and engineering risk metrics.

Theoretical and Practical Insights

  • Direct vs. Indirect Learning: Traditionally, to find variance, one fits two models: one for $\mathbb{E}[Y|X]$ and one for $\mathbb{E}[Y^2|X]$, then subtracts them. If the mean is complex but variance is simple, errors from the mean model degrade the variance estimate. Multi-observation regression allows fitting the simple variance model directly, bypassing the complexity of the mean.
  • The Power of Two: For many statistics, moving from one observation to two drops the "elicitation complexity" from infinity to one.
  • The Curse of Proximity: The theory relies on finding points that are "close enough." In high-dimensional spaces, points are sparse. The authors prove a lower bound showing that any algorithm for variance regression must have a sample complexity scaling exponentially with the number of dimensions $d$.

Experimental Results

  • Empirical Superiority: In simulations, the "Sliding Window" and "$\epsilon$-Nearby" algorithms consistently outperformed traditional "two-moment" baselines, particularly when the underlying distribution's mean was non-linear.
  • Faster Convergence: For 1D problems, the authors proved a convergence rate of $O(1/n)$, significantly faster than the $O(n^{-2/3})$ rate typically seen in traditional non-parametric approaches for these statistics.
  • Practicality: The biased algorithms (Sliding Window and $\epsilon$-Nearby) performed better in practice than the unbiased ones, likely due to more efficient data reuse.

Conclusion and Future Directions

While promising, the "Information-Theoretic Barrier" in high dimensions remains a challenge. Without further assumptions, such as data living on a low-dimensional manifold, these techniques struggle as feature counts increase. Future work may involve "active learning" to intentionally collect "clumps" of data or discovering multi-observation loss functions for statistics like the Upper Confidence Bound that require fewer assumptions about noise distribution.

Summary updated

Abstract

Recent work introduced loss functions which measure the error of a prediction based on multiple simultaneous observations or outcomes. In this paper, we explore the theoretical and practical questions that arise when using such multi-observation losses for regression on data sets of $(x,y)$ pairs. When a loss depends on only one observation, the average empirical loss decomposes by applying the loss to each pair, but for the multi-observation case, empirical loss is not even well-defined, and the possibility of statistical guarantees is unclear without several $(x,y)$ pairs with exactly the same $x$ value. We propose four algorithms formalizing the concept of empirical risk minimization for this problem, two of which have statistical guarantees in settings allowing both slow and fast convergence rates, but which are out-performed empirically by the other two. Empirical results demonstrate practicality of these algorithms in low-dimensional settings, while lower bounds demonstrate intrinsic difficulty in higher dimensions. Finally, we demonstrate the potential benefit of the algorithms over natural baselines that use traditional single-observation losses via both lower bounds and simulations.
BibTeX
@inproceedings{frongillo2019multi,
  author = {Rafael M. Frongillo and Nishant A. Mehta and Tom Morgan and Bo Waggoner},
  title = {{Multi-Observation Regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=trWINjgXcQz},
}
Figure