Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
From MaRDI portal
Publication:5868965
DOI10.1287/moor.2021.1216OpenAlexW3201865094WikidataQ114058151 ScholiaQ114058151MaRDI QIDQ5868965
Publication date: 26 September 2022
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1803.06510
SDP relaxationmixture modelsexponential ratesstochastic ball modelhidden integralitysemirandom robustness
Cites Work
- Unnamed Item
- Statistical guarantees for the EM algorithm: from population to sample-based analysis
- A local search approximation algorithm for \(k\)-means clustering
- A spectral algorithm for learning mixture models
- Community detection in sparse networks via Grothendieck's inequality
- Recovery guarantees for exemplar-based clustering
- NP-hardness of Euclidean sum-of-squares clustering
- Heuristics for semirandom graph problems
- Probably certifiably correct \(k\)-means clustering
- On semidefinite relaxations for the block model
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Approximating $k$-Median via Pseudo-Approximation
- A constant-factor approximation algorithm for the k -median problem (extended abstract)
- Efficiently learning mixtures of two Gaussians
- Exact Recovery in the Stochastic Block Model
- Improved Graph Clustering
- Relax, No Need to Round
- Improved Spectral-Norm Bounds for Clustering
- A new greedy approach for facility location problems
- The Planar k-Means Problem is NP-Hard
- Community Detection and Stochastic Block Models
- Clustering subgaussian mixtures by semidefinite programming
- Exponential Error Rates of SDP for Block Models: Beyond Grothendieck’s Inequality
- Least squares quantization in PCM
- Mixture models, robustness, and sum of squares proofs
- Semirandom Models as Benchmarks for Coloring Algorithms
- Semidefinite programs on sparse random graphs and their application to community detection
- How robust are reconstruction thresholds for community detection?
- Approximation algorithms for semi-random partitioning problems
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Probability and Computing
- Automata, Languages and Programming
- Learning Theory
- METHOD OF MOMENTS AND METHOD OF MAXIMUM LIKELIHOOD
