Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature

Abstract

Many statistical learning problems have recently been shown to be amenable to Semi-Definite Programming (SDP), with community detection and clustering in Gaussian mixture models as the most striking instances [javanmard et al., 2016]. Given the growing range of applications of SDP-based techniques to machine learning problems, and the rapid progress in the design of efficient algorithms for solving SDPs, an intriguing question is to understand how the recent advances from empirical process theory can be put to work in order to provide a precise statistical analysis of SDP estimators. In the present paper, we borrow cutting edge techniques and concepts from the learning theory literature, such as fixed point equations and excess risk curvature arguments, which yield general estimation and prediction results for a wide class of SDP estimators. From this perspective, we revisit some classical results in community detection from [guédon et al.,2016] and [chen et al., 2016], and we obtain statistical guarantees for SDP estimators used in signed clustering, group synchronization and MAXCUT.

References in corpus (17)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Quantum state tomography via compressed sensing
• Manopt, a Matlab toolbox for optimization on manifolds
• An overview of low-rank matrix recovery from incomplete observations
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Phase Transitions in Semidefinite Relaxations
• Guaranteed clustering and biclustering via semidefinite programming
• Learning subgaussian classes : Upper and minimax bounds
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• SPONGE: A generalized eigenproblem for clustering signed networks
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
• Statistical learning with Lipschitz and convex loss functions