Sharp Computational-Statistical Phase Transitions via Oracle Computational Model

• Activity Number: 656
• Type: Contributed
• Date/Time: Thursday, August 4, 2016 : 8:30 AM to 10:20 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Zhaoran Wang* and Quanquan Gu and Han Liu
• Companies: Princeton and University of Virginia and Princeton
• Keywords: Computational-Statistical Tradeoff ; Minimax Lower Bound ; Le Cam's Method ; Algorithmic Complexity ; Hypothesis Testing

Abstract

We study the fundamental tradeoffs between computational tractability and statistical accuracy for a general family of hypothesis testing problems with combinatorial structures. Based upon an oracle model of computation, which captures the interactions between algorithms and data, we establish a general lower bound that explicitly connects the minimum testing risk under computational budget constraints with the intrinsic probabilistic and combinatorial structures of statistical problems. This lower bound mirrors the classical statistical lower bound by Le Cam (1986) and allows us to quantify the optimal statistical performance achievable given limited computational budgets in a systematic fashion. Under this unified framework, we sharply characterize the statistical-computational phase transition for a broad range of problems. In particular, for these problems we identify significant gaps between the optimal statistical accuracy that is achievable under computational tractability constraints and the classical statistical lower bounds. Our result provides an intuitive and concrete interpretation for the intrinsic computational intractability of high-dimensional statistical problems.