Worst-Case Analysis for Randomly Collected Data

Justin Y. Chen, Gregory Valiant, Paul ValiantNeurIPS 2020 · OpenReview

Introduction: The Problem with i.i.d. Assumptions

Most of classical statistics and machine learning relies on a fundamental assumption: data is "well-behaved," typically meaning it is Independent and Identically Distributed (i.i.d.). However, in the real world, data collection is often messy and heavily biased. Consider "snowball sampling" (where survey respondents recruit their friends) or "selective prediction" (where past chronological data is used to predict the future). In these scenarios, the sample is highly correlated.

If your data does not follow a predictable distribution like a Gaussian, standard estimators—such as the simple sample mean—can fail spectacularly. This paper asks a provocative question: If we know how the data was collected, but we make zero assumptions about the data values themselves, can we still design optimal estimators?

A New Paradigm: Worst-Case Analysis via Sampling

The authors introduce a novel framework for statistical estimation that works even when you know absolutely nothing about your data's distribution. Instead of assuming the data values are drawn from a random distribution, they shift the "randomness" entirely to the sampling process.

By treating the data values as adversarial (worst-case) and leveraging knowledge of the sampling pipeline, the authors provide an efficient algorithm that finds estimators with near-optimal performance. You do not need to assume the world is stationary or that data is "nice" as long as you understand the "noise" in your collection pipeline.

Methodology: Semilinear Estimators and the Grothendieck Connection

The paper focuses on semilinear estimators. In this setup, the estimate is a weighted sum of the observed sample values. Crucially, the weights can depend on the sampling process and the identities of the elements, but not the data values themselves.

The core technical contribution of the paper is uncovering a deep connection to the Grothendieck problem, a famous problem in functional analysis and computer science:

  1. Evaluating an Estimator: Calculating the exact worst-case error for a fixed estimator is NP-hard. However, the authors use a Semidefinite Programming (SDP) relaxation to approximate this error within a constant factor of $\pi/2$.
  2. Finding the Best Estimator: They provide an efficient algorithm that solves a concave maximization problem to find the optimal weights for a given sampling distribution.
  3. Generalization: While the primary focus is on estimating the mean, the framework is successfully extended to handle $d$-dimensional linear regression.

The SDP algorithm naturally "regularizes" the estimator. It prevents the model from over-relying on a small number of samples that might have high variance or high leverage, effectively balancing the bias-variance tradeoff based purely on the known sampling geometry.

Experimental Results

The proposed algorithm is theoretically guaranteed to be within a factor of $\pi/2 \approx 1.57$ of the best possible semilinear estimator. The authors evaluated the algorithm using three synthetic experimental setups designed to mimic real-world non-i.i.d. scenarios:

  • Snowball/Chain Sampling: In a spatial setup where samples "recruit" nearest neighbors, the SDP-based algorithm outperformed the standard sample mean by 4–7x in worst-case scenarios and 2–4x even on spatially correlated (non-adversarial) data.
  • Selective Prediction: In a chronological setting aimed at predicting a future window of data based on past samples, the algorithm achieved a 2–3x reduction in error compared to existing state-of-the-art estimators specifically designed for chronological prediction.
  • Importance Sampling: The framework successfully handled populations where different groups had significantly different probabilities of being sampled.

Limitations and Future Directions

While the results are highly promising, the paper outlines a few limitations and areas for future research:

  • The Semilinear Gap: The framework restricts itself to semilinear estimators. The authors conjecture that the performance gap between semilinear and arbitrary (non-linear) estimators is extremely small (perhaps a factor of 1.004), but proving this remains an open theoretical question.
  • Scalability: The current algorithm's runtime depends on the population size $n$. For massive datasets or infinite populations, new algorithmic approaches are needed to decouple the runtime from $n$.
  • Value Constraints: The theoretical guarantees assume data values are bounded within an $\ell_\infty$ ball. Future work could explore how optimal estimators change if data is constrained by other norms, such as $\ell_1$ or $\ell_2$.

Summary updated

Abstract

We introduce a framework for statistical estimation that leverages knowledge of how samples are collected but makes no distributional assumptions on the data values. Specifically, we consider a population of elements [n]={1,...,n} with corresponding data values x<em>1,...,x</em>n. We observe the values for a "sample" set A \subset [n] and wish to estimate some statistic of the values for a "target" set B \subset [n] where B could be the entire set. Crucially, we assume that the sets A and B are drawn according to some known distribution P over pairs of subsets of [n]. A given estimation algorithm is evaluated based on its "worst-case, expected error" where the expectation is with respect to the distribution P from which the sample A and target sets B are drawn, and the worst-case is with respect to the data values x<em>1,...,x</em>n. Within this framework, we give an efficient algorithm for estimating the target mean that returns a weighted combination of the sample values–-where the weights are functions of the distribution P and the sample and target sets A, B--and show that the worst-case expected error achieved by this algorithm is at most a multiplicative pi/2 factor worse than the optimal of such algorithms. The algorithm and proof leverage a surprising connection to the Grothendieck problem. We also extend these results to the linear regression setting where each datapoint is not a scalar but a labeled vector (x<em>i,y</em>i). This framework, which makes no distributional assumptions on the data values but rather relies on knowledge of the data collection process via the distribution P, is a significant departure from the typical statistical estimation framework and introduces a uniform analysis for the many natural settings where membership in a sample may be correlated with data values, such as when individuals are recruited into a sample through their social networks as in "snowball/chain" sampling or when samples have chronological structure as in "selective prediction".
BibTeX
@inproceedings{chen2020worst,
  author = {Justin Y. Chen and Gregory Valiant and Paul Valiant},
  title = {{Worst-Case Analysis for Randomly Collected Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=HjadENkWwB},
}

Loading related content...

Figure