Abstract
This paper introduces a formal framework for analyzing the relationship between computational runtime and statistical sample complexity. Traditionally, these two resources have been studied in isolation. However, in the era of Big Data, an abundance of samples can often be traded for reduced computational effort. By utilizing convex relaxation as a mechanism for "algorithm weakening," the authors demonstrate that a constant-factor increase in data can lead to super-polynomial reductions in computation time without sacrificing statistical accuracy.
Introduction
In modern data science, we encounter a fundamental tension between statistical power and computational feasibility. Statisticians view more data as a path to simplicity via the law of large numbers, while computer scientists often view it as a source of increased complexity. Venkat Chandrasekaran and Michael I. Jordan bridge these perspectives in their seminal work, asking whether we can intentionally use faster, "weaker" algorithms when data is plentiful.
Historically, the gap between statistically optimal but intractable estimators and fast but unreliable heuristics has been wide. This paper formalizes this gap through the Time-Data Complexity Class $TD(t(p), n(p), \epsilon(p))$, which maps the relationship between runtime ($t$), sample size ($n$), and error ($\epsilon$) for a problem of dimension $p$.
Methodology: Convex Relaxation as a Tuning Knob
The core technical contribution is the use of convex relaxation to systematically weaken algorithms. The authors focus on denoising problems where a signal $x^*$ must be recovered from noisy observations.
- The Hierarchy of Relaxations: Complex, non-convex sets (e.g., permutations or rank-one matrices) are approximated by a sequence of increasingly "loose" but "easier-to-compute" convex sets. A "tight" relaxation (like the cut polytope) provides high accuracy with minimal data but is computationally expensive. A "weak" relaxation (like an $\ell_1$ or nuclear norm ball) is computationally efficient but requires more data to achieve the same error.
- Gaussian Squared-Complexity: To quantify this tradeoff, the authors employ Gaussian squared-complexity, a geometric measure of the "width" of the cone of feasible directions at the signal. They prove that increasing the sample size effectively narrows this cone, allowing even weak relaxations to succeed.
Key Results and the Tradeoff Profile
The paper provides concrete "time-data profiles" for several high-dimensional problems, such as denoising signed matrices and sparse PCA. A critical finding is that increasing the dataset size by only a constant factor can allow a transition from super-polynomial time algorithms to polynomial-time ones.
As shown in the figure above, there is a clear frontier between the minimax risk lower bound (the minimum data required regardless of computation) and the computational lower bound (the minimum time required to process the data). Points A through H represent different levels of relaxation. For example, in the Denoising Signed Matrices problem:
- Point A (Intractable): Requires $n \approx \sqrt{p}$ samples but takes super-polynomial time.
- Point E (Efficient): Requires slightly more samples ($c \sqrt{p}$) but runs in $O(p^{1.5})$ time.
Discussion and Future Work
The most profound insight of this work is that data acts as a computational lubricant. When data is abundant, sophisticated algorithms are less necessary; simpler, faster methods can achieve the same results. However, there is a "floor" to this benefit: once the cost of reading or aggregating data exceeds the time saved by weakening the algorithm, additional data becomes a liability rather than an asset.
Future research directions include extending these principles to general M-estimation with complex loss functions and developing adaptive algorithms that can "back off" to simpler logic in real-time as data stream rates increase.
Summary updated