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:
- Importance Sampling: Sampling probabilities vary across groups, with data values correlated to those probabilities.
- Snowball Sampling: Sampling propagates through a 2D spatial network where data values are spatially clustered.
- 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