Computational limits in statistical estimation : hidden clique and related problems
Abstract/Contents
- Abstract
- Characterizing computational costs of statistical estimation and inference is a fundamental challenge. In many modern applications a confluence of both large-scale and high-resolution data has highlighted the computational challenges in extracting information and performing inference. For a number of reasons, the hidden clique problem from theoretical computer science has emerged as a prototypical example of the impact computational considerations can have on statistical estimation problems. In particular, the computational phenomena observed in the hidden clique problem are intimately related to analogous phenomena in other problems like sparse principal components analysis and learning communities in graphs. In this thesis, we study algorithm-based computational limits for the hidden clique problem and related problems. We use the popular approaches of the belief propagation heuristic, and convex programming relaxations for two aims: 1. We propose new algorithms that provably improve over the prior state-of-the-art methods for the hidden clique problem and sparse principal components analysis (PCA). 2. We provide hardness evidence for the hidden clique problem based on local algorithms, which generalize the belief propagation heuristic, and the powerful Sum-of-Squares hierarchy of convex programming relaxations.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2016 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Deshpande, Yash |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering. |
| Primary advisor | Montanari, Andrea |
| Thesis advisor | Montanari, Andrea |
| Thesis advisor | Boyd, Stephen A |
| Thesis advisor | Candès, Emmanuel J. (Emmanuel Jean) |
| Advisor | Boyd, Stephen A |
| Advisor | Candès, Emmanuel J. (Emmanuel Jean) |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Yash Deshpande. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2016. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2016 by Yash Kiran Deshpande
- 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...