Abstract
The recent explosion in the amount and dimensionality of data has exacerbated the need of trading off computational and statistical efficiency carefully, so that inference is both tractable and meaningful. We propose a framework that provides an explicit opportunity for practitioners to specify how much statistical risk they are willing to accept for a given computational cost, and leads to a theoretical risk-computation frontier for any given inference problem. We illustrate the tradeoff between risk and computation and illustrate the frontier in three distinct settings. First, we derive analytic forms for the risk of estimating parameters in the classical setting of estimating the mean and variance for normally distributed data and for the more general setting of parameters of an exponential family. The second example concentrates on computationally constrained Hodges-Lehmann estimators. We conclude with an evaluation of risk associated with early termination of iterative matrix inversion algorithms in the context of linear regression.
Introduction
In the era of "Big Data," researchers often face a surplus of information but a deficit of time or memory. Traditionally, statistical theory has focused on maximizing accuracy (minimizing "risk") under the assumption of infinite computational resources. Conversely, computer science has focused on algorithmic complexity (Big-O notation), often without regard for the specific statistical quality of the output.
This paper bridges the gap by introducing a formal framework for navigating the "risk-computation frontier." This frontier represents the optimal balance between statistical accuracy and the time required to run an algorithm. By treating computational cost as a constrained resource, we can identify estimation procedures that provide the best possible results within a specific time budget.
The Risk-Computation Frontier
The proposed framework pairs every estimator $\hat{\theta}$ with an algorithm having a measurable computational cost $C(\hat{\theta})$. The risk-computation frontier is defined as the set of estimators that achieve the minimum statistical risk for any given computational budget.
As shown in the figure above, the frontier (dashed line) represents the Pareto-optimal set of estimators. Estimators like point C are "dominated"—they sit above and to the right of the frontier, meaning they are both computationally more expensive and statistically riskier than points on the curve (like D). In practice, such estimators should be discarded in favor of those on the frontier.
Methodology and Case Studies
The paper explores this tradeoff through three primary lenses:
- Sufficient Statistics Partitioning: For exponential families (e.g., the Normal distribution), the framework analyzes "looks" at data. If a practitioner has a budget of $n$ operations, the framework helps decide whether to use all $n$ points to estimate a single parameter (like the mean) or split the budget to estimate multiple parameters (mean and variance).
- Robust Estimation: The authors examine the Hodges-Lehmann (HL) estimator, which is highly robust but computationally expensive ($O(n^2)$). By applying sub-sampling and sequential processing, they map how much robustness is sacrificed when speed is prioritized.
- Iterative Algorithms: In the context of matrix inversion for linear regression, the number of iterations is treated as the "cost." The framework compares how different methods, such as Newton-Raphson versus Power methods, approach the true solution over time.
Key Insights
- Optimal Resource Allocation: The "optimal" way to spend a compute budget depends heavily on the data's signal-to-noise ratio. For instance, in low-signal environments, it is often more beneficial to spend more budget estimating variance rather than the mean.
- Data Splitting vs. Subsampling: In streaming contexts with limited memory, it is often superior to use different subsets of data for different parts of a statistic (e.g., one subset for the first moment, another for the second) rather than using a small global subsample for everything.
- Early Stopping as an Estimator: In iterative methods, every iteration can be viewed as a distinct estimator with its own position on the risk-computation frontier. While some methods (like Newton-Raphson) converge faster, they may be highly unstable initially, making slower but more reliable methods (like Power methods) preferable if early termination is likely.
Conclusion and Future Work
While this framework provides a rigorous way to choose estimators, several challenges remain. Modern hardware costs are more complex than the "cost of one look" model used here, involving cache misses and parallelization. Furthermore, choosing the optimal estimator often requires prior knowledge of the parameters being estimated. Future work may involve two-stage approaches where a small portion of the budget is used to estimate parameters to inform the final estimator choice. Additionally, scaling these calculations to high-dimensional graphical models remains a significant computational challenge.
Summary updated