Statistical Seminar: Every Monday at 2:00 pm.
Time: 2:00 pm – 3:00 pm
Date: November 3rd
Place: 3001

Christophe GIRAUD (Université Paris Saclay) – Computational barriers in learning: high-dimensional phenomenon

 Abstract: 

In many high-dimensional problems, the best polynomial-time estimators fall short of the information-theoretic limits that are provably attainable without computational constraints. The low-degree polynomial framework has emerged as a powerful tool for analyzing the fundamental capabilities of polynomial-time algorithms. Building on our recent advances in the study of low-degree lower bounds, we will explore two notable high-dimensional phenomena:

1. Complex structures– We will show that polynomial-time algorithms may fail to leverage certain low-dimensional yet complex structures.
2. Beyond predictions from statistical physics– We will highlight cases where the computational barriers suggested by tools from statistical physics do not remain valid in specific high-dimensional regimes.

Organizers:

Anna KORBA (CREST), Karim LOUNICI (CMAP) , Jaouad MOURTADA (CREST)

Sponsors:
CREST-CMAP