Summary of Semidefinite Programming Relaxations and Debiasing For Maxcut-based Clustering, by Shuheng Zhou
Semidefinite programming relaxations and debiasing for MAXCUT-based clustering
by Shuheng Zhou
First submitted to arxiv on: 16 Jan 2024
Categories
- Main: Machine Learning (stat.ML)
- Secondary: Machine Learning (cs.LG); Statistics Theory (math.ST)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper explores the problem of partitioning a small dataset from a mixture of two sub-Gaussian distributions in high-dimensional space (R^p). The authors propose three computationally efficient algorithms: SDP1, BalancedSDP, and Spectral clustering. These methods leverage semidefinite programming relaxations of an integer quadratic program to find the maximum cut on a graph, where edge weights represent dissimilarity scores between nodes based on their p features. The goal is to allow for partial recovery (success rate < 100%) when the signal-to-noise ratio (s^2) is lower bounded by a constant. The paper proves that the misclassification error decays exponentially with respect to s^2 for SDP1 and designs an estimator (BalancedSDP) with debiasing properties, removing an assumption on bounding the trace difference between population covariance matrices. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This research is about finding patterns in a small group of data points that come from two different groups. The authors want to use as few features (characteristics) as possible to correctly group the data. They propose three methods to do this: SDP1, BalancedSDP, and Spectral clustering. These methods work by looking at how similar or dissimilar each data point is compared to others based on their characteristics. The goal is to be able to identify patterns even when there’s a lot of noise in the data. The authors show that one of these methods (SDP1) works really well and is better than the others. |
Keywords
* Artificial intelligence * Spectral clustering
