Multi-Observation Regression

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

Authors and Affiliations

Abstract

Given a data set of $(x,y)$ pairs, a common learning task is to fit a model predicting $y$ (a label or dependent variable) conditioned on $x$. This paper considers the similar but much less-understood task of predicting a property of the distribution of $y$ given $x$, such as its variance or its 2-norm. We introduce a framework for Multi-Observation Regression, which "clumps" nearby data points into metasamples to enable Empirical Risk Minimization (ERM) for complex statistics that were previously thought to be "un-elicitable" with standard loss functions.

Introduction

Standard regression is highly effective for predicting conditional means. However, fields like finance (risk measures), ecology (biodiversity), and engineering (robust design) often require higher-order statistics of the distribution $D_x$, such as variance or the "Conditional Value at Risk."

The fundamental challenge is elicitation. Theory suggests that for many higher-order statistics, no standard loss function $\ell(f(x), y)$ exists that is minimized by the true statistic when observing single $(x, y)$ pairs. While researchers often use surrogate models (e.g., estimating the first and second moments separately to calculate variance), this can be inefficient and prone to compounding errors.

Methodology: Multi-Observation Losses

The authors propose using multi-observation losses: functions of the form $\ell(f(x), y_1, \dots, y_m)$ that take $m$ independent samples of $y$ for the same $x$. Since real datasets rarely provide multiple $y$ values for the exact same $x$, the authors develop algorithms to construct metasamples by grouping points with nearby $x$ values.

Proposed Algorithms

  1. Naïve Sampling: A baseline that draws a base sample and searches for $m$ neighbors for each point.
  2. Improved Sampling: Uses a maximum matching approach to group points within a distance $\epsilon$, providing robust theoretical guarantees.
  3. Sliding Window: A heuristic for 1D data that creates metasamples from every group of $m$ adjacent points.
  4. $\epsilon$-Nearby: A heuristic that constructs metasamples from all $m$-tuples of data points within a diameter $\epsilon$.

Theoretical Framework

The core contribution is an analysis of ERM with "corrupted" samples. By assuming the underlying distribution $D_x$ is Lipschitz (nearby $x$ have similar $y$ distributions), the authors prove that metasample-based approaches converge to the true statistic. The "Improved Sampling" algorithm provides the first excess risk bounds for multi-observation ERM, showing convergence rates of $O(1/\sqrt{n})$ generally and $O(1/n)$ under strong convexity.

Empirical Evaluation

The approach was tested on synthetic datasets where the true conditional statistics are known, allowing for objective accuracy measurement. These included variance estimation (sine and linear functions), biodiversity (2-norm), and Upper Confidence Bound (UCB) estimation using Gamma distributions.

Mean squared error comparison across four estimation tasks. The $\epsilon$-nearby and sliding window algorithms consistently outperform standard surrogate moment-based approaches (2mom linear/quad).

As shown in the results above, the $\epsilon$-Nearby and Sliding Window algorithms consistently outperformed standard "two-estimator" approaches. This demonstrates that targeting the statistic directly with a multi-observation loss is often superior to fitting surrogate models, especially when the surrogate properties are more complex than the target statistic itself.

Insights and Limitations

  • Direct vs. Surrogate: Direct estimation via multi-observation loss is more robust than modeling multiple moments separately.
  • The Curse of Dimensionality: Sample complexity for estimating variance scales exponentially with the dimension $d$. This remains a significant hurdle for high-dimensional applications.
  • Future Directions: Potential solutions to dimensionality include active learning or assuming "low intrinsic dimension." Additionally, designing multi-observation losses for statistics like UCB that work across all distribution classes remains an open problem.

Summary updated

Abstract

Given a data set of $(x,y)$ pairs, a common learning task is to fit a model predicting $y$ (a label or dependent variable) conditioned on $x$. This paper considers the similar but much less-underst...
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