Cornell University
Discovering Discrete Structures using SDP Relaxation: Hidden Integrality, Statistical Optimality and Semirandom Robustness
Abstract
dc:description.abstractUnderstanding discrete structures of data has been an important and ongoing effort in the communities of machine learning, optimization and statistics. We will introduce the problem under a wide range of generative models, including the well-known Stochastic Block Model and Gaussian Mixture Model. After discussing several popular algorithms, we will present an algorithm based on semidefinite programming (SDP) relaxation. We show that despite being a relaxation, this algorithm achieves an optimal (or nearly optimal) error rate in terms of distance to the target solution, and that this result is enabled by a surprising connection with an Oracle integer program. Moreover, this algorithm is robust under the so-called semirandom model, a property many algorithms lack.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Operations Research and Information Engineering
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Operations Research and Information Engineering
- Grantor
- Cornell University
- Year dc:date.issued
- 2020
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Fei, Yingjie
- Chair dc:contributor.chair
-
- Chen, Yudong
- Committee members dc:contributor.committeemember
-
- Samorodnitsky, Gennady
- Banerjee, Sid
Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 13277778
- Dc Identifier Other
-
ProQuest Submission ID: 12055
ProQuest Publication ID: 28000619