High-dimensional problems in probability, optimization, and learning
Abstract/Contents
- Abstract
- This thesis concerns several problems in probability, optimization, and machine learning. In the first part we study mixing and sampling. We first revisit the riffle shuffle, generalizing the classic ``seven shuffles suffice'' result of Bayer and Diaconis to shuffles with asymmetric cuts. We then study our first spin glass model, aiming to sample from the Sherrington-Kirkpatrick Gibbs measure in the high-temperature phase. We develop a new approach based not on a Markov Chain, but instead on Eldan's stochastic localization. Moreover we prove a hardness result for stable algorithms using Chatterjee's disorder chaos. In the second part we turn to optimization, aiming to find approximate ground states in spin glass models. This problem is intimately related to their low temperature behavior, and the limiting ground state energy is given by the Parisi formula at zero temperature. We determine an exact algorithmic threshold for a natural class of stable algorithms, which is achieved by approximate message passing algorithms. Our hardness results stem from a refined landscape property that we christen the branching overlap gap property. The third part concerns two problems in high-dimensional machine learning. We first study the problem of chasing convex bodies, in which one aims to perform stable convex optimization to obtain robust performance guarantees in changing environments. The solution involves a generalization of the classical Steiner point in convex geometry and its connections to Lipschitz selection. Finally we establish the law of robustness, showing that a natural robustness memorization task in high dimension requires extremely overparametrized machine learning models to solve.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Sellke, Mark |
|---|---|
| Degree supervisor | Bubeck, Sebastien |
| Degree supervisor | Montanari, Andrea |
| Thesis advisor | Bubeck, Sebastien |
| Thesis advisor | Montanari, Andrea |
| Thesis advisor | Diaconis, Persi |
| Degree committee member | Diaconis, Persi |
| Associated with | Stanford University, Department of Mathematics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Mark Sellke. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/cd294tv9439 |
Access conditions
- Copyright
- © 2022 by Mark Sellke
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...