How bad is worst-case data if you know where it comes from?

Justin Y. Chen, Gregory Valiant, Paul ValiantarXiv 2019 · arXiv · OpenReview

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,\ldots,n}$ with corresponding data values $x_1,\ldots,x_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]$. 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$, and the worst-case is with respect to the data values $x_1,\ldots,x_n$. Within this framework, we give an efficient algorithm for estimating the target mean that returns a weighted combination of the sample values and show that the worst-case expected error achieved by this algorithm is at most a multiplicative $\pi/2$ factor worse than the optimal. The algorithm leverages a connection to the Grothendieck problem, providing a uniform algorithmic analysis for settings like importance sampling, snowball sampling, and selective prediction.

Introduction

Standard statistical tools typically rely on the assumption that data is "well-behaved"—often meaning it is independent and identically distributed (i.i.d.) or follows a specific distribution like a Gaussian. However, in real-world scenarios, data collection is often inherently biased or structured. For instance, "snowball sampling" is used to find hidden populations via social networks, and "selective prediction" uses historical data to forecast future windows. In these cases, the sample is often highly correlated with the values we aim to estimate.

When data fails to meet traditional distributional assumptions, standard estimators can fail spectacularly. This research addresses a fundamental question: If we know exactly how our sampling process is biased, can we still provide accurate estimates even if the data itself is adversarial? By shifting the focus from modeling the data values to modeling the collection process, we can derive robust estimators that do not rely on stationarity or independence.

The Framework: Estimation via Process Knowledge

We define a population of $n$ elements, each with an associated value $x_i$. We observe a sample $A$ and aim to estimate a statistic (such as the mean) of a target set $B$. The pair $(A, B)$ is drawn from a known distribution $P$.

Our goal is to find an estimator that minimizes the worst-case expected error. The expectation is taken over the randomness of the sampling process $P$, while the "worst-case" refers to the data values $x_1, \dots, x_n$, which are treated as adversarial. This approach ensures that the estimator remains reliable regardless of the underlying data distribution, provided the sampling mechanism is understood.

Semilinear Estimators

The study focuses on semilinear estimators, which compute a weighted sum of observed sample values: $$\hat{\mu} = \sum_{i \in A} w_i(A, B) x_i$$ Crucially, the weights $w_i$ can depend on the identities of the elements in the sample and the known distribution $P$, but they cannot depend on the data values $x_i$ themselves.

Algorithmic Approach and the Grothendieck Connection

Finding the optimal weights for these estimators is computationally difficult (NP-hard). To overcome this, we identify a connection between evaluating the worst-case error and the positive semidefinite Grothendieck problem, a classic problem in functional analysis.

By applying a Semidefinite Programming (SDP) relaxation, we can efficiently find near-optimal weights. We provide two primary algorithms:

  1. Algorithm 1: Designed for scenarios where the sampling distribution $P$ is fully known.
  2. Algorithm 2: A sample-efficient version that works when only black-box sampling access to the collection process is available.

The $\pi/2$ Guarantee

A key theoretical result of this work is the proof that the SDP-based estimator is at most a factor of $\pi/2 \approx 1.57$ worse than the theoretical optimum semilinear estimator. This constant is a fundamental limit tied to the Grothendieck constant, providing a tight bound on the performance of our convex relaxation.

Experimental Evaluation

We evaluated the framework across three synthetic but representative sampling scenarios:

  • Importance Sampling: In a population where certain groups were five times more likely to be sampled, the SDP algorithm achieved a 2-fold improvement in worst-case expected error compared to standard unbiased estimators like inverse proportional reweighting.
  • Snowball/Chain Sampling: Simulating social network recruitment in a 2D space, the SDP algorithm outperformed the standard sample mean by 2–4x for correlated data and 4–7x in strictly worst-case scenarios. The algorithm naturally "regularizes" weights to avoid over-reliance on high-variance clusters.
  • Selective Prediction: In chronological settings where the future may differ significantly from the past, the framework successfully estimated future means, demonstrating that stationarity is not a requirement for accurate estimation if the timing of the prediction is accounted for in $P$.

Extensions and Future Work

Beyond mean estimation, we successfully extended this framework to $d$-dimensional linear regression, providing bounds on the error of recovered coefficients under adversarial data values.

While the current work focuses on semilinear estimators, future research may explore whether non-linear estimators offer significant advantages. Additionally, as the current SDP approach scales with the population size $n$, developing algorithms for infinite domains or more interpretable sampling properties remains a priority. This framework represents a significant departure from typical estimation, offering a unified tool for any setting where membership in a sample is correlated with the data values themselves.

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,\ldots,n}$ with corresponding data values $x_1,\ldots,x_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_1,\ldots,x_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. This framework, which makes no distributional assumptions on the data values but rather relies on knowledge of the data collection process, is a significant departure from typical estimation and introduces a uniform algorithmic analysis for the many natural settings where membership in a sample may be correlated with data values, such as when sampling probabilities vary as in "importance sampling", when individuals are recruited into a sample via a social network as in "snowball sampling", or when samples have chronological structure as in "selective prediction".
BibTeX
@misc{chen2019how,
  author = {Justin Y. Chen and Gregory Valiant and Paul Valiant},
  title = {{How bad is worst-case data if you know where it comes from?}},
  year = {2019},
  eprint = {1911.03605},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.03605},
}
Figure