Session: Semidefinite Relaxations in Inference Problems
Chair: Yong Sheng Soh
Cluster: Conic and Semidefinite Optimization
Talk 1: Local geometry determines global landscape in low-rank factorization for synchronization
Speaker: Shuyang Ling
Abstract: The orthogonal group synchronization problem, which focuses on recovering orthogonal group elements from their corrupted pairwise measurements, encompasses examples such as high-dimensional Kuramoto model on general signed networks, $\mathbb{Z}_2$-synchronization, community detection under stochastic block models, and orthogonal Procrustes problem. The semidefinite relaxation (SDR) has proven its power in solving this problem; however, its expensive computational costs impede its widespread practical applications. We consider the Burer-Monteiro factorization approach to the orthogonal group synchronization, an effective and scalable low-rank factorization to solve large scale SDPs. Despite the significant empirical successes of this factorization approach, it is still a challenging task to understand when the nonconvex optimization landscape is benign, i.e., the optimization landscape possesses only one local minimizer, which is also global. In this work, we demonstrate that if the degree of freedom within the factorization exceeds the condition number of the ``Laplacian" (certificate matrix) at the global minimizer, the optimization landscape is absent of spurious local minima. Our main theorem is purely algebraic and versatile, and it seamlessly applies to all the aforementioned examples: the nonconvex landscape remains benign under almost identical condition that enables the success of the SDR. Finally, we will discuss the statistical sides of group synchronization by quantifying the uncertainty of both MLE and spectral estimators.
Talk 2: Exactness Conditions for Semidefinite Relaxations of the Quadratic Assignment Problem
Speaker: Junyu Chen
Abstract: The Quadratic Assignment Problem (QAP) is an important discrete optimization instance that encompasses many well-known combinatorial optimization problems, and has applications in a wide range of areas such as logistics and computer vision. The QAP, unfortunately, is NP-hard to solve. To address this difficulty, a number of semidefinite relaxations of the QAP have been developed. These techniques are known to be powerful in that they compute globally optimal solutions in many instances, and are often deployed as sub-routines within enumerative procedures for solving QAPs. In this paper, we investigate the strength of these semidefinite relaxations. Our main result is a deterministic set of conditions on the input matrices -- specified via linear inequalities -- under which these semidefinite relaxations are exact. Our result is simple to state, in the hope that it serves as a foundation for subsequent studies on semidefinite relaxations of the QAP as well as other related combinatorial optimization problems. As a corollary, we show that the semidefinite relaxation is exact under a perturbation model whereby the input matrices differ by a suitably small perturbation term. One technical difficulty we encounter is that the set of dual feasible solutions is not closed. To circumvent these difficulties, our analysis constructs a sequence of dual feasible solutions whose objective value approaches the primal objective, but never attains it.
Talk 3: Inference of planted subgraphs in random graphs
Speaker: Cheng Mao
Abstract: Suppose that we are given a graph G obtained from randomly planting a template graph in an Erdős–Rényi graph. Can we detect the presence and recover the location of the planted subgraph in G? This problem is well understood in the case where the template graph is a clique or a dense subgraph but has received less attention otherwise. We consider several settings where the planted subgraph is the power of a Hamiltonian cycle or a random geometric graph which arises in multiple applications. The difficulty of the detention or recovery problem primarily lies in the combinatorial nature of the associated optimization problem. To tackle the problem, we study computationally efficient methods such that subgraph counting and spectral methods which leverage the higher triangle density of the planted subgraph.
