Back to search

Cornell University

Discovering Discrete Structures using SDP Relaxation: Hidden Integrality, Statistical Optimality and Semirandom Robustness

Abstract

dc:description.abstract

Understanding 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

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Fei, Yingjie. Discovering Discrete Structures using SDP Relaxation: Hidden Integrality, Statistical Optimality and Semirandom Robustness. Doctor of Philosophy thesis, Cornell University, 2020. https://hdl.handle.net/1813/103079