Random constraint satisfaction problems and high-dimensional estimation
Abstract/Contents
- Abstract
- In this thesis, we consider random constraint satisfaction problems(rCSP's) that exhibit sharp phase transitions. In the first part, we study a rCSP with discrete variables, namely the random regular NAE-SAT model. In a broad class of discrete rCSP's, one-step replica symmetry breaking cavity heuristics from statistical physics predict that there is the condensation threshold before the satisfiability threshold where most of the solutions lie inside a bounded number of solution clusters and the overlap between two independently drawn solutions concentrates precisely at two values. We give the first rigorous confirmation of this prediction for the random regular NAE-SAT problem. The second part of the thesis studies the binary linear classification problem in high dimensions, which can be viewed as a rCSP with continuous variables. We determine the satisfiability threshold for the data to achieve a positive margin assuming the covariates are Gaussian and the labels are drawn from a generalized linear model. Moreover, we characterize the limiting test error of the max-margin estimator.
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 | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Sohn, Youngtak |
|---|---|
| Degree supervisor | Dembo, Amir |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Chatterjee, Sourav |
| Thesis advisor | Montanari, Andrea |
| Degree committee member | Chatterjee, Sourav |
| Degree committee member | Montanari, Andrea |
| Associated with | Stanford University, Department of Statistics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Youngtak Sohn. |
|---|---|
| Note | Submitted to the Department of Statistics. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/jn194fv5657 |
Access conditions
- Copyright
- © 2021 by Youngtak Sohn
- 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...