Program
s
Fall 2021

Computational Complexity of Statistical Inference

Aug. 18Dec. 17, 2021

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 (MIT; chair), Adam Klivans (University of Texas, 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)

Long-Term Participants (including Organizers):

Jean Barbier (International Center for Theoretical Physics), Peter Bartlett (UC Berkeley), Gérard Ben Arous (New York University), Andrej Bogdanov (The Chinese University of Hong Kong), Guy Bresler (MIT; chair), Flori Bunea (Cornell University), Moses Charikar (Stanford University), Yuxin Chen (Princeton University), Alex d'Aspremont (École normale supérieure), Luc Devroye (McGill University), Ilias Diakonikolas (University of Wisconsin-Madison), Uri Feige (Weizmann Institute of Science), David Gamarnik (Massachusetts Institute of Technology), Sanjam Garg (UC Berkeley), Shafi Goldwasser (UC Berkeley), Nika Haghtalab (UC Berkeley), Zaid Harchaoui (University of Washington), Moritz Hardt (UC Berkeley), Prahladh Harsha (Tata Institute of Fundamental Research), Justin Holmgren (NTT Research), Jiantao Jiao (UC Berkeley), Michael Jordan (UC Berkeley), Adam Klivans (University of Texas, Austin), Pravesh Kothari (Carnegie Mellon University), Florent Krzakala (École Polytechnique Fédérale de Lausanne), Jerry Li (Microsoft Research), Po-Ling Loh (University of Wisconsin, Madison), Gábor Lugosi (Pompeu Fabra University), Song Mei (UC Berkeley), Raghu Meka (UC Los Angeles), Andrea Montanari (Stanford University), Shay Moran (Technion - Israel Institute for Technology), Vidyut Naware (PayPal), Jelani Nelson (UC Berkeley), Jon Niles-Weed (New York University), Ayfer Özgür (Stanford University), Ashwin Pananjady (Georgia Institute of Technology), Aaron Potechin (University of Chicago), Prasad Raghavendra (UC Berkeley), Benjamin Recht (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), Jacob Steinhardt (UC Berkeley), Pragya Sur (Harvard University), Avishay Tal (UC Berkeley), Luca Trevisan (Bocconi University), Martin Wainwright (UC Berkeley), Jiangping Wang (PayPal), Yuting Wei (University of Pennsylvania), Mary Wootters (Stanford University), Yihong Wu (Yale University), Jiaming Xu (Duke University), Bin Yu (UC Berkeley), Ilias Zadik (Massachusetts Institute of Technology), Lenka Zdeborová (École polytechnique fédérale de Lausanne), Anru Zhang (University of Wisconsin-Madison)

Research Fellows:

Sitan Chen (UC Berkeley), Yanjun Han (UC Berkeley), Sam Hopkins (UC Berkeley; Microsoft Research Fellow), Frederic Koehler (UC Berkeley), Holden Lee (Duke University), Cindy Rush (Columbia University), Fiona Skerman (Uppsala University), Alex Wein (New York University), Dana Yang (Duke University)

Visiting Graduate Students and Postdocs:

Vilhelm Agdur (Uppsala University), Taejoo Ahn (UC Berkeley), Dylan Altschuler (New York University), Zoe Bell (UC Berkeley), Hadley Black (UC Los Angeles), Enric Boix (Massachusetts Institute of Technology), Michael Celentano (UC Berkeley), Yeshwanth Cherapanamjeri (UC Berkeley), Ofer Grossman (Massachusetts Institute of Technology), Tim Hsieh (Carnegie Mellon University), Wei Hu (UC Berkeley), Brice Huang (Massachusetts Institute of Technology), Sushrut Karmalkar (University of Wisconsin-Madison), Koulik Khamaru (UC Berkeley), Michael Kim (UC Berkeley), Eren Can Kizildag (Massachusetts Institute of Technology), Jasper Lee (University of Wisconsin-Madison), Tianjiao Li (Georgia Institute of Technology), Yue Li (Carnegie Mellon University), Andrea Lincoln (UC Berkeley), Mengqi Lou (Georgia Institute of Technology), Yuetian Luo (University of Wisconsin-Madison), Jay Mardia (Stanford University), Sidhanth Mohanty (UC Berkeley), Dheeraj Nagaraj (Massachusetts Institute of Technology), Ankit Pensia (University of Wisconsin - Madison), Aram-Alexandre Pooladian (New York University), Gautam Prakriya Venkata (Chinese University of Hong Kong), Manuel Saenz (International Center for Theoretical Physics), Mark Sellke (Stanford), Abhishek Shetty (UC Berkeley), Jan van den Brand (UC Berkeley), Tanay Wakhare (Massachusetts Institute of Technology), Jingyan Wang (Georgia Institute of Technology), Yixin Wang (Simons Institute, UC Berkeley), Manxi Wu (UC Berkeley), Manxi Wu (UC Berkeley), Jeff Xu (Carnegie Mellon University), Yuling Yan (Princeton University), Sophie Yu (Duke University), Angela Zhou (UC Berkeley)

Workshops

Aug. 23Aug. 27, 2021

Organizers:

Guy Bresler (MIT; chair), Adam Klivans (University of Texas, 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)
Sep. 13Sep. 17, 2021

Organizers:

Sam Hopkins (UC Berkeley; Microsoft Research Fellow; co-chair), Lenka Zdeborová (École polytechnique fédérale de Lausanne; co-chair), Afonso Bandeira (ETH Zürich)
Oct. 11Oct. 15, 2021

Organizers:

Laurent Massoulie (Microsoft Research-INRIA Joint Centre; chair), Po-Ling Loh (University of Wisconsin, Madison), Jiaming Xu (Duke University)
Nov. 2Nov. 5, 2021

Organizers:

Adam Klivans (University of Texas, Austin), Jerry Li (Microsoft Research), Tselil Schramm (Stanford University)
Nov. 8Nov. 10, 2021

Organizers:

Luca Trevisan (Bocconi University; chair), Boaz Barak (Harvard University), Amit Daniely (Google Research), Tselil Schramm (Stanford University), Rocco Servedio (Columbia University), Vinod Vaikuntanathan (Massachusetts Institute of Technology)

If you are interested in joining this program, please see the Participate page.

 Subscribe to the program calendar.

Internal Program Activities

Next event (Weekly): Monday, December 6th 10:00 am – 11:00 am 
Next event (Weekly): Monday, November 29th 1:30 pm – 3:30 pm 
Tuesday, November 30th 11:00 am – 12:00 pm 
Dylan Altschuler (New York University)
Next event (Weekly): Tuesday, November 30th 2:00 pm – 3:00 pm 
Next event (Weekly): Wednesday, December 1st 3:00 pm – 5:00 pm 
Next event (Weekly): Thursday, December 2nd 9:30 am – 11:00 am 
Monday, December 6th 11:00 am – 12:00 pm 

Past Internal Program Activities

Wednesday, November 24th 3:00 pm5:00 pm
Tuesday, November 23rd 2:00 pm3:00 pm
Monday, November 22nd 1:30 pm3:30 pm
Monday, November 22nd 11:00 am12:00 pm
Monday, November 22nd 10:00 am11:00 am
Thursday, November 18th 9:30 am11:00 am
Wednesday, November 17th 3:00 pm5:00 pm
Tuesday, November 16th 2:00 pm3:00 pm
Monday, November 15th 1:30 pm3:30 pm
Monday, November 15th 10:00 am11:00 am
Thursday, November 4th 9:30 am11:00 am
Wednesday, November 3rd 3:00 pm5:00 pm
Tuesday, November 2nd 2:00 pm3:00 pm
Monday, November 1st 1:30 pm3:30 pm
Monday, November 1st 10:00 am11:00 am
Thursday, October 28th 9:30 am11:00 am
Wednesday, October 27th 3:00 pm5:00 pm
Tuesday, October 26th 2:00 pm3:00 pm
Monday, October 25th 1:30 pm3:30 pm
Monday, October 25th 11:00 am12:00 pm
Andrej Bogdanov (The Chinese University of Hong Kong)
Monday, October 25th 10:00 am11:00 am
Thursday, October 21st 9:30 am11:00 am
Wednesday, October 20th 3:00 pm5:00 pm
Tuesday, October 19th 2:00 pm3:00 pm
Monday, October 18th 1:30 pm3:30 pm
Monday, October 18th 10:00 am11:00 am
Thursday, October 7th 9:30 am11:00 am
Wednesday, October 6th 3:00 pm5:00 pm
Tuesday, October 5th 2:00 pm3:00 pm
Monday, October 4th 1:30 pm3:30 pm
Monday, October 4th 10:00 am11:00 am
Thursday, September 30th 9:30 am11:00 am
Wednesday, September 29th 3:00 pm5:00 pm
Tuesday, September 28th 2:00 pm3:00 pm
Monday, September 27th 1:30 pm3:30 pm
Monday, September 27th 11:00 am12:00 pm
Pragya Sur (Harvard)  
Monday, September 27th 10:00 am11:00 am
Thursday, September 23rd 9:30 am11:00 am
Wednesday, September 22nd 3:00 pm5:00 pm
Tuesday, September 21st 2:00 pm3:00 pm
Monday, September 20th 1:30 pm3:30 pm
Monday, September 20th 11:00 am12:30 pm
Sitan Chen (UC Berkeley)
Monday, September 20th 10:00 am11:00 am
Thursday, September 9th 10:00 am4:30 pm
Wednesday, September 8th 10:00 am5:30 pm
Wednesday, September 8thThursday, September 9th
Tuesday, September 7th 11:00 am12:00 pm
David Gamarnik (Massachusetts Institute of Technology)
Friday, September 3rd 11:00 am12:00 pm
Monday, August 30th 1:00 pm2:00 pm
Friday, August 20th 1:00 pm3:00 pm