Antoine Maillard (FIM (Institute for Mathematical Research) and the department of mathematics at ETH Zurich)
| When |
Nov 22, 2023
from 01:00 to 02:00 |
|---|---|
| Where | M7 101 |
| Attendees |
Antoine Maillard |
| Add event to calendar |
vCal
iCal
|
Speaker: Antoine Maillard
Title: Fitting ellipsoids to random points
Abstract: We consider the problem of exactly fitting an ellipsoid (centered at 0) to n standard Gaussian random vectors in dimension d, for very large n and d. This problem has connections to questions in statistical learning and theoretical computer science, and is conjectured to undergo a sharp transition: with high probability, it has a solution if n < d2/4, while it is not satisfiable if n > d2/4. In this talk we will discuss the origin of this conjecture, and highlight some recent progress, in three different directions:
- A proof that the problem is feasible for n < d2 / C, for some (large) constant C, significantly improving over previously-known bounds.
- A non-rigorous characterization of the conjecture, as well as significant generalizations, using analytical methods of statistical physics.
- A rigorous proof of a satisfiability transition exactly at n = d2 / 4 in a slightly relaxed version of the problem, the first rigorous result characterizing the expected phase transition in ellipsoid fitting. The proof is inspired by the non-rigorous characterization discussed above.
This talk is based on the three manuscripts: arXiv:2307.01181, arXiv:2310.01169, arXiv:2310.05787, which are joint works with Afonso Bandeira, Tim Kunisky, Shahar Mendelson and Elliot Paquette.
In Room M7 101