Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error

Jonah Brown-Cohen

Abstract

In modern statistical estimation, data collection often involves biased or correlated processes, such as snowball sampling or selective prediction. Traditional i.i.d. assumptions fail in these settings. This paper builds upon the framework of minimizing "worst-case expected error," where the data collection process is known but data values are assumed to be chosen by an adversary. We present significantly faster algorithms for computing optimal semilinear estimators using Online Convex Optimization (OCO). For $\ell_\infty$-normalized data, we provide a $\pi/2$-approximation algorithm that iteratively solves simplified Semidefinite Programs (SDPs). For $\ell_2$-normalized data, we demonstrate that the problem reduces to iterative eigenvector computations, offering massive speedups without loss of accuracy. Finally, we establish a combinatorial condition—$\alpha$-non-expansion—that identifies when low-error estimation is fundamentally impossible.

Introduction

Standard statistical methods typically rely on the assumption that data points are independent and identically distributed (i.i.d.). However, real-world data collection is frequently non-random. For instance, in social network surveys, participants often recruit their acquaintances, leading to "snowball sampling" where the sample is inherently biased by the network's structure.

Chen, Valiant, and Valiant (2020) introduced a framework to address this by minimizing the worst-case expected error. In this model, the researcher knows the randomized sampling process but assumes the underlying data values are adversarial. While they proved that "semilinear estimators" (where weights depend on the sampling process) can be effective, their solution required solving complex, high-dimensional SDPs with no explicit runtime guarantees. This paper addresses the computational bottleneck, providing efficient, scalable algorithms and new theoretical lower bounds.

Algorithmic Framework: Estimation as a Min-Max Game

The problem of finding an optimal estimator is framed as a min-max game: the estimator seeks to choose weights to minimize error, while an adversary chooses data values to maximize it. The core innovation of this work is the application of Online Gradient Descent (OGD) to this objective. By treating the complex concave objective function as a series of simpler convex costs, we transform a heavy "one-shot" optimization into a light "multi-shot" iterative process.

$\ell_\infty$-Normalized Data

When data values are bounded (e.g., between -1 and 1), the algorithm iteratively solves a sequence of standard SDPs. While this still utilizes SDP solvers, the individual problems are more constrained and simpler than the original CVV formulation. This approach maintains a $\pi/2$ approximation factor relative to the optimal semilinear estimator, a limit imposed by the Grothendieck inequality used in the SDP relaxation.

$\ell_2$-Normalized Data

The most significant practical contribution occurs in the $\ell_2$-normalized setting (where the second moment of the data is bounded). Here, the adversary’s optimal strategy is always a rank-1 matrix. This observation allows the algorithm to bypass SDP solvers entirely, reducing the problem to iteratively computing the top eigenvector of a matrix using the power method. This reduction enables the use of standard, highly scalable machine learning libraries.

Combinatorial Lower Bounds

Beyond algorithmic improvements, the paper introduces a combinatorial condition called $\alpha$-non-expansion. This condition describes distributions where the sampled set and the target population are so disconnected that no estimator—regardless of its complexity—can achieve low worst-case error. This provides a fundamental limit on when statistical estimation is possible given a specific data collection regime.

Experimental Results

The proposed algorithms were evaluated on three synthetic datasets designed to simulate difficult sampling environments:

  1. Importance Sampling: Sampling probabilities vary across groups, with data values correlated to those probabilities.
  2. Snowball Sampling: Sampling propagates through a 2D spatial network where data values are spatially clustered.
  3. Selective Prediction: A temporal model where past samples are used to predict the average of future time steps.

Performance and Speed

The OGD-based approach demonstrated dramatic improvements in computational efficiency. In the snowball sampling experiment, the new algorithm reached a solution in approximately 3 seconds on a standard laptop. In contrast, the previous SDP-based approach took 130 seconds, with 100 of those seconds spent merely compiling the problem description. Despite the speedup, the $\ell_2$-normalized algorithm matched the accuracy of the original $\ell_\infty$ approach, proving that the efficiency gains do not come at the cost of estimator quality.

Conclusion

This work moves the framework of worst-case expected error from a theoretical curiosity to a practical tool. By leveraging Online Convex Optimization and identifying the rank-1 nature of the $\ell_2$ adversary, we provide the first explicit runtime bounds for these robust estimators: $O(\rho^2 \log \rho / \epsilon^2)$ iterations. Future work remains to bridge the $\pi/2$ approximation gap in the $\ell_\infty$ case and to validate these algorithms on large-scale, real-world social network and polling data.

Summary updated

Abstract

The study of statistical estimation without distributional assumptions on data values, but with knowledge of data collection methods was recently introduced by Chen, Valiant and Valiant (NeurIPS 2020). In this framework, the goal is to design estimators that minimize the worst-case expected error. Here the expectation is over a known, randomized data collection process from some population, and the data values corresponding to each element of the population are assumed to be worst-case. Chen, Valiant and Valiant show that, when data values are $\ell_{\infty}$-normalized, there is a polynomial time algorithm to compute an estimator for the mean with worst-case expected error that is within a factor $\frac{\pi}{2}$ of the optimum within the natural class of semilinear estimators. However, their algorithm is based on optimizing a somewhat complex concave objective function over a constrained set of positive semidefinite matrices, and thus does not come with explicit runtime guarantees beyond being polynomial time in the input. In this paper we design provably efficient algorithms for approximating the optimal semilinear estimator based on online convex optimization. In the setting where data values are $\ell_{\infty}$-normalized, our algorithm achieves a $\frac{\pi}{2}$-approximation by iteratively solving a sequence of standard SDPs. When data values are $\ell_2$-normalized, our algorithm iteratively computes the top eigenvector of a sequence of matrices, and does not lose any multiplicative approximation factor. We complement these positive results by stating a simple combinatorial condition which, if satisfied by a data collection process, implies that any (not necessarily semilinear) estimator for the mean has constant worst-case expected error.
BibTeX
@inproceedings{browncohen2021faster,
  author = {Jonah Brown-Cohen},
  title = {{Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=qViS_JPyzR3},
}
Figure