Spring 2020

Statistical and Computational Tradeoffs


Over the last decade, the statistical and computational aspects of massive data processing have become increasingly intertwined. In particular, we are now well aware that the gold standard of designing methods that are both statistically optimal and computationally efficient may not be achievable. Instead, it is often desirable to achieve a compromise where statistical accuracy is traded off for computational efficiency. These tradeoffs are further nuanced by purely computational resource tradeoffs: time vs. space vs. communication, and purely statistical ones: bias vs. variance, all of which interact in a nontrivial fashion. This last point is exemplified by the recent trend in optimization that consists exploiting the specific structure of the computational problem at hand and that has accompanied the fantastic impact of first-order optimization methods in machine learning . Even more recently, seemingly minor adjustments in models have led to significant computational benefits. Understanding the Pareto-optimal tradeoffs in this complex space is a fundamental question of modern data science.