Designing Statistical Estimators That Balance Sample Size, Risk, and Computational Cost

Abstract

This paper proposes a tradeoff between computational time, sample complexity, and statistical accuracy that applies to statistical estimators based on convex optimization. When we have a large amount of data, we can exploit excess samples to decrease statistical risk, to decrease computational cost, or to trade off between the two. We propose to achieve this tradeoff by varying the amount of smoothing applied to the optimization problem. This work uses regularized linear regression as a case study to argue for the existence of this tradeoff both theoretically and experimentally. We also apply our method to describe a tradeoff in an image interpolation problem.

Additional Information

© 2015 IEEE. Manuscript received August 07, 2014; revised November 18, 2014; accepted January 13, 2015. Date of publication February 05, 2015; date of current version May 12, 2015. The work of J. J. Bruer and J. A. Tropp was supported under Office of Naval Research award N00014-11-1002, Air Force Office of Scientific Research award FA9550-09-1-0643, and a Sloan Research Fellowship. The work of V. Cevher was supported in part by the European Commission under the Grants MIRG-268398 and ERC Future Proof, and by the Swiss Science Foundation under the Grants SNF 200021-132548, SNF 200021-146750, and SNF CRSII2-147633. The guest editor coordinating the review of this manuscript and approving it for publication was Dr. Georgios Giannakis.

Additional details