Groupe d’études et de recherche en analyse des décisions

The statistical price for computational efficiency

Philippe Rigollet MIT, États-Unis

With the explosion of the size of data, computation has become an integral part of statistics. Ad hoc remedies such as employing convex relaxations, or manipulating sufficient statistics, have been successful to derive efficient procedures with provably optimal statistical guarantees. Unfortunately, computational efficiency sometimes comes at an inevitable statistical cost. Therefore, one needs to redefine optimality among computationally efficient procedures. Using tools from information theory and computational complexity, we quantify this cost in the context of two models: (i) the multi-armed bandit problem, and (ii) sparse principal component analysis [Based on joint work with Q. Berthet, S. Chassang, V. Perchet and E. Snowberg]