Skip to Main content Skip to Navigation
Theses

Fundamental limits of inference: A statistical physics approach.

Léo Miolane 1, 2, 3
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : We study classical statistical problems such as as community detection on graphs, Principal Component Analysis (PCA), sparse PCA, Gaussian mixture clustering, linear and generalized linear models, in a Bayesian framework. We compute the best estimation performance (often denoted as ``Bayes Risk'') achievable by any statistical method in the high dimensional regime. This allows to observe surprising phenomena: for many problems, there exists a critical noise level above which it is impossible to estimate better than random guessing. Below this threshold, we compare the performance of existing polynomial-time algorithms to the optimal one and observe a gap in many situations: even if non-trivial estimation is theoretically possible, computationally efficient methods do not manage to achieve optimality. From a statistical physics point of view that we adopt throughout this manuscript, these phenomena can be explained by phase transitions. The tools and methods of this thesis are therefore mainly issued from statistical physics, more precisely from the mathematical study of spin glasses.
Complete list of metadatas

Cited literature [231 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/tel-02446988
Contributor : Léo Miolane <>
Submitted on : Tuesday, January 21, 2020 - 12:03:21 PM
Last modification on : Saturday, September 19, 2020 - 4:38:51 AM
Long-term archiving on: : Wednesday, April 22, 2020 - 5:42:49 PM

File

these2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-02446988, version 1

Collections

Citation

Léo Miolane. Fundamental limits of inference: A statistical physics approach.. Probability [math.PR]. Ecole normale supérieure - ENS PARIS; Inria Paris, 2019. English. ⟨tel-02446988⟩

Share

Metrics

Record views

428

Files downloads

343