Vi studerar den statistiska prestanda semidefinite programmering (SDP) avkopplingar för klustering under slumpmässiga graf modeller. Under Z 2 Synkronisering modell, Censored Block Model och Stochastic Block Model, visar vi att SDP uppnår en felfrekvens av formen Heren är en lämplig multipel av antalet noder och I * är ett informations-teoretiskt mått på signal-till-brus förhållandet. Vi erbjuder matchande lägre gränser på Bayes fel för varje modell och visar därför att SDP-metoden är Bayes optimal. Som en följd av detta innebär våra resultat att SDP uppnår den optimala exakta återvinningströskeln för varje modell. Dessutom visar vi att SDP är robust: ovanstående bundna förblir giltiga under semirandom versioner av modellerna där den observerade grafen modifieras av en monoton motståndare. Vårt bevis bygger på en ny primal-dual analys av SDP inom en enhetlig ram för alla tre modellerna, och analysen visar att SDP tillnärmar ett omröstningsförfarande med gemensam majoritet.
För detta problem visar REF att lösningen (5) matchar minimax lägre gräns på den optimala Bayes felfrekvensen för ursprungliga problem (4).
Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}