# Computational and informational limits in high-dimensional statistical problems

## Abstract/Contents

- Abstract
- This thesis investigates the computational and informational limits in several high-dimensional statistical problems, with a speciﬁc focus on non-convex overparametrized models and their algorithmic aspects. The ﬁrst such non-convex problem we study is negative perceptron, which aims to ﬁnd the max-margin classiﬁer on linearly non-separable data. Since the data are not separable, this problem is equivalent to ﬁnding a linear classiﬁer with the largest possible negative margin κ. Under two natural data assumptions, we study the typical properties of negative perceptron: First, we establish lower and upper bounds on the maximum margin, or equivalently, the interpolation threshold for ﬁxed κ, and show that our bounds match to the leading order as κ → −∞. Second, we propose and analyze a linear programming algorithm for ﬁnding a κ-margin solution, and observe a gap between the interpolation threshold and the threshold for our algorithm. Finally, we prove generalization bounds for all κ-margin classiﬁers and the one produced by our linear programming algorithm. Our second focus is on empirical risk minimization (ERM) with general prediction and loss functions, through the lens of projection pursuit. In many statistical applications, it is the case that the prediction function only depends on a low-dimensional projection of the covariates. Therefore, empirical risk minimization is equivalent to a variational problem over the set of feasible distributions that can be achieved by such projections. We derive tight inner and outer bounds for this "feasibility" set in terms of Wasserstein distance and Kullback-Leibler divergence under proportional asymptotics, and apply our results to a number of interesting supervised learning problems. We then investigate the computational aspects of the same problem by considering the class of incremental approximate message passing (IAMP) algorithms, which is initially proposed and applied in Montanari (2019) to the problem of ﬁnding the ground state energy of the Sherrington-Kirkpatrick (SK) model. Finally, we investigate the evolution of stochastic gradient descent (SGD) for wide two-layer neural networks when applied to the task of learning Gaussian single-index models. Under this setting, we propose a so-called canonical learning order for the learning dynamics, which displays a number of intriguing features: (a) the target function ϕ is learned incrementally, (b) the population risk evolves over time according to a sequence of polynomial approximations of ϕ, and (c) these successive phases of learning take place on well-separated time-scales, which are accurately characterized using the method of matched asymptotic expansions. These behaviors arise naturally because the population gradient ﬂow can be reformulated as a singularly perturbed dynamical system.

## 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 | 2024; ©2024 |

Publication date | 2024; 2024 |

Issuance | monographic |

Language | English |

## Creators/Contributors

Author | Zhou, Kangjie |
---|---|

Degree supervisor | Montanari, Andrea |

Thesis advisor | Montanari, Andrea |

Thesis advisor | Candès, Emmanuel J. (Emmanuel Jean) |

Thesis advisor | Dembo, Amir |

Degree committee member | Candès, Emmanuel J. (Emmanuel Jean) |

Degree committee member | Dembo, Amir |

Associated with | Stanford University, School of Humanities and Sciences |

Associated with | Stanford University, Department of Statistics |

## Subjects

Genre | Theses |
---|---|

Genre | Text |

## Bibliographic information

Statement of responsibility | Kangjie Zhou. |
---|---|

Note | Submitted to the Department of Statistics. |

Thesis | Thesis Ph.D. Stanford University 2024. |

Location | https://purl.stanford.edu/gj401sv2573 |

## Access conditions

- Copyright
- © 2024 by Kangjie Zhou
- 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...