Department seminar by Alex WeinExport this event to calendar

Wednesday, December 15, 2021 — 12:00 PM EST

Please Note: This seminar will be given online.

Department seminar

Alex Wein
University of California, Berkeley

Link to join seminar: Hosted on Zoom

Understanding Statistical-vs-Computational Tradeoffs via Low-Degree Polynomials

Many high-dimensional statistical tasks---including sparse PCA (principal component analysis), community detection, gaussian clustering, tensor PCA, and more---exhibit a striking gap between what can be achieved statistically (by a brute force algorithm) and what can be achieved with the best known polynomial-time algorithms. An emerging framework to understand these gaps is based on analyzing the class of "low-degree polynomial algorithms". This is a powerful class of algorithms (which includes, for instance, spectral methods and approximate message passing), and so provable failure of this class of algorithms is a form of concrete evidence for inherent computational hardness of statistical problems.

While low-degree algorithms were initially studied in the context of hypothesis testing problems, I will present some new general-purpose techniques for determining the precise limitations of low-degree algorithms for other types of statistical tasks, including estimation and optimization. I will focus primarily on two problems: recovering a planted submatrix of elevated mean in a gaussian matrix, and finding a large independent set in a sparse random graph. This line of work illustrates that low-degree polynomials provide a unifying framework for studying the computational complexity of a wide variety of statistical tasks.

Based primarily on joint works with David Gamarnik, Aukosh Jagannath, and Tselil Schramm.

Event tags 

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2022 (26)
    1. August (1)
    2. April (1)
    3. March (1)
    4. February (4)
    5. January (19)
  2. 2021 (89)
    1. December (12)
    2. November (12)
    3. October (8)
    4. September (5)
    5. July (4)
    6. June (3)
    7. May (6)
    8. April (8)
    9. March (13)
    10. February (7)
    11. January (12)
  3. 2020 (71)
  4. 2019 (65)
  5. 2018 (44)
  6. 2017 (55)
  7. 2016 (44)
  8. 2015 (37)
  9. 2014 (44)
  10. 2013 (46)
  11. 2012 (44)