Abstract
In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances. The methods we describe here are based on mature, albeit non-rigorous, tools from statistical physics.
Original language | English (US) |
---|---|
Pages (from-to) | 159-186 |
Number of pages | 28 |
Journal | Portugaliae Mathematica |
Volume | 75 |
Issue number | 2 |
DOIs | |
State | Published - 2018 |
Keywords
- Approximate message passing
- Cavity method
- Computational-to-statistical gaps
- Phase transitions
- Replica method
ASJC Scopus subject areas
- Mathematics(all)