# Computational Complexity of Statistical Inference

The two basic lines of inquiry in statistical inference have long been: (i) to determine fundamental statistical (i.e., information-theoretic) limits; and (ii) to find efficient algorithms achieving these limits. However, for many structured inference problems, it is not clear if statistical optimality is compatible with efficient computation. Statistically optimal estimators often entail an infeasible exhaustive search. Conversely, for many settings the computationally efficient algorithms we know are statistically suboptimal, requiring higher signal strength or more data than is information-theoretically necessary. This phenomenon is both fascinating and unsettling. It suggests that the information-theoretic limit on the signal-to-noise ratio (or the amount of data) for these problems, as studied since the beginning of mathematical statistics, is not the practically relevant benchmark for modem high-dimensional settings. Instead, the practically relevant benchmark is the fundamental statistical limit for *computationally efficient *algorithms.

By now dozens of fundamental high-dimensional statistical estimation problems are conjectured to have different computational and statistical limits. These problems (for example, sparse linear regression or sparse phase retrieval) are ubiquitous in practice and well-studied theoretically, yet the central mysteries remain: What are the fundamental data limits for computationally efficient algorithms? How do we find optimal efficient algorithms? At a more basic level, are these statistical-computational gaps in various problems appearing for a common reason? Is there hope of building a widely applicable theory describing and explaining statistical-computational trade-offs?

The objective of the program is to advance the methodology for reasoning about the computational complexity of statistical estimation. Over the last decade several disparate communities and lines of work have begun to make progress on these questions. This program aims to stimulate work towards developing a deeper understanding and building a coherent theory by forming new collaborations between researchers in complexity theory, algorithms, statistics, learning theory, probability, and information theory.

sympa [at] lists.simons.berkeley.edu (body: subscribe%20si2021announcements%40lists.simons.berkeley.edu) (Click here to subscribe to our announcements email list for this program).

**Organizers:**

Guy Bresler (Massachusetts Institute of Technology; chair), Adam Klivans (University of Texas at Austin), Gábor Lugosi (Pompeu Fabra University), Ankur Moitra (Massachusetts Institute of Technology), Prasad Raghavendra (UC Berkeley), Tselil Schramm (Stanford University), Yihong Wu (Yale University)

**List of participants (tentative list, including ****organizers):**

Jean Barbier (International Center for Theoretical Physics), Peter Bartlett (UC Berkeley), Andrej Bogdanov (The Chinese University of Hong Kong), Guy Bresler (Massachusetts Institute of Technology), Florentina Bunea (Cornell University), Moses Charikar (Stanford University), Yuxin Chen (Princeton University), Alex D'Aspremont (INRIA and ENS), Luc Devroye (McGill University), Ilias Diakonikolas (University of Wisconsin-Madison), Uri Feige (Weizmann Institute of Science), David Gamarnik (Massachusetts Institute of Technology), Nika Haghtalab (UC Berkeley), Zaid Harchaoui (University of Washington), Prahladh Harsha (Tata Institute of Fundamental Research), Jiantao Jiao (UC Berkeley), Michael Jordan (UC Berkeley), Pravesh Kothari (Carnegie Mellon University), Jerry Li (Microsoft Research), Andrea Lincoln (UC Berkeley), Po-Ling Loh (University of Cambridge), Gábor Lugosi (Pompeu Fabra University), Raghu Meka (UC Los Angeles), Ankur Moitra (Massachusetts Institute of Technology), Andrea Montanari (Stanford University), Shay Moran (Technion - Israel Institute for Technology), Jelani Nelson (UC Berkeley), Jon Niles-Weed (New York University), Ashwin Pananjady (Georgia Institute of Technology), Prasad Raghavendra (UC Berkeley), Andrej Risteski (Carnegie Mellon University), Sujay Sanghavi (UT Austin and Amazon), Tselil Schramm (Stanford University), Subhabrata Sen (Harvard University), Nati Srebro (Toyota Technological Institute at Chicago), Pragya Sur (Harvard University), Avishay Tal (UC Berkeley), Luca Trevisan (Bocconi University), Martin Wainwright (UC Berkeley), Yuting Wei (Carnegie Mellon University), Mary Wootters (Stanford University), Yihong Wu (Yale University), Jiaming Xu (Duke University), Bin Yu (UC Berkeley), Anru Zhang (University of Wisconsin-Madison)

## Research Fellows:

Sitan Chen (UC Berkeley), Yanjun Han (Stanford University), Sam Hopkins (UC Berkeley), Frederic Koehler (Massachusetts Institute of Technology), Holden Lee (Duke University), Cynthia Rush (Columbia University), Fiona Anne Skerman (Uppsala University), Alex Wein (New York University), Dana Yang (Duke University)

## Visiting Graduate Students and Postdocs:

Vilhelm Agdur (Uppsala University), Dylan Altschuler (New York University), Hadley Black (UC Los Angeles), Enric Boix (Massachusetts Institute of Technology), Michael Celentano (UC Berkeley), Rungang Han (University of Wisconsin-Madison), Tim Hsieh (Carnegie Mellon University), Brice Huang (Massachusetts Institute of Technology), Sushrut Karmalkar (University of Wisconsin-Madison), Eren Can Kizildag (Massachusetts Institute of Technology), Jasper Lee (University of Wisconsin-Madison), Yue Li (Carnegie Mellon University), Tianjiao Li (Georgia Institute of Technology), Mengqi Lou (Georgia Institute of Technology), Yuetian Luo (University of Wisconsin-Madison), Jay Mardia (Stanford University), Dheeraj Nagaraj (Massachusetts Institute of Technology), Ankit Pensia (University of Wisconsin - Madison), Gautam Prakriya (Chinese University of Hong Kong), Manuel Saenz (International Center for Theoretical Physics), Anna Thomas (Stanford University), Tanay Wakhare (Massachusetts Institute of Technology), Jingyan Wang (Georgia Institute of Technology), Jeff Xu (Carnegie Mellon University), Yuling Yan (Princeton University), Sophie Yu (Duke University)

## Workshops

## Organizers:

## Organizers:

## Organizers:

## Organizers:

Those interested in participating in this program should send an email to the organizers at this si2021 [at] lists.simons.berkeley.edu (at this address).