Online Program Home
My Program

Abstract Details

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
Abstract #320247
Title: Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
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

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.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2016 program

Copyright © American Statistical Association