# 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):**

Emmanuel Abbe (Ecole Polytechnique Fédérale de Lausanne), 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), Alexandra Carpentier (Otto-von-Guericke-Universität Magdeburg), Moses Charikar (Stanford University), Yuxin Chen (Princeton University), Alex D'Aspremont (INRIA and ENS), Luc Devroye (McGill University), Ilias Diakonikolas (University of Wisconsin-Madison), Vida Dujmovic (University of Ottawa), Uri Feige (Weizmann Institute of Science), David Gamarnik (Massachusetts Institute of Technology), Samuel Hopkins (UC Berkeley), 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), Claire Mathieu (École normale supérieure), 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), Prasad Raghavendra (UC Berkeley), Kavita Ramanan (Brown University), 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), Nike Sun (Massachusetts Institute of Technology), Pragya Sur (Harvard University), Avishay Tal (UC Berkeley), Luca Trevisan (Bocconi University), Martin Wainwright (UC Berkeley), Yuting Wei (Carnegie Mellon University), Alexander Wein (New York University), Mary Wootters (Stanford University), Yihong Wu (Yale University), Jiaming Xu (Duke University), Bin Yu (UC Berkeley), Anru Zhang (University of Wisconsin-Madison)

## 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).