Timezone: »
Poster
Smoothed analysis of the low-rank approach for smooth semidefinite programs
Thomas Pumir · Samy Jelassi · Nicolas Boumal
We consider semidefinite programs (SDPs) of size $n$ with equality constraints. In order to overcome scalability issues, Burer and Monteiro proposed a factorized approach based on optimizing over a matrix $Y$ of size $n\times k$ such that $X=YY^*$ is the SDP variable. The advantages of such formulation are twofold: the dimension of the optimization variable is reduced, and positive semidefiniteness is naturally enforced. However, optimization in $Y$ is non-convex. In prior work, it has been shown that, when the constraints on the factorized variable regularly define a smooth manifold, provided $k$ is large enough, for almost all cost matrices, all second-order stationary points (SOSPs) are optimal. Importantly, in practice, one can only compute points which approximately satisfy necessary optimality conditions, leading to the question: are such points also approximately optimal? To answer it, under similar assumptions, we use smoothed analysis to show that approximate SOSPs for a randomly perturbed objective function are approximate global optima, with $k$ scaling like the square root of the number of constraints (up to log factors). Moreover, we bound the optimality gap at the approximate solution of the perturbed problem with respect to the original problem. We particularize our results to an SDP relaxation of phase retrieval.
Author Information
Thomas Pumir (Princeton University)
Samy Jelassi (Princeton University)
Nicolas Boumal (Princeton)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Oral: Smoothed analysis of the low-rank approach for smooth semidefinite programs »
Thu. Dec 6th 09:25 -- 09:40 PM Room Room 517 CD
More from the Same Authors
-
2022 Poster: Vision Transformers provably learn spatial structure »
Samy Jelassi · Michael Sander · Yuanzhi Li -
2020 Poster: A mean-field analysis of two-player zero-sum games »
Carles Domingo-Enrich · Samy Jelassi · Arthur Mensch · Grant Rotskoff · Joan Bruna -
2019 Poster: Towards closing the gap between the theory and practice of SVRG »
Othmane Sebbouh · Nidham Gazagnadou · Samy Jelassi · Francis Bach · Robert Gower -
2018 : Poster Session (All Posters) »
Stephen Macke · Hongzi Mao · Caroline Lemieux · Saim Salman · Rishikesh Jha · Hanrui Wang · Shoumik P Palkar · Tianqi Chen · Thomas Pumir · Vaishnav Janardhan · adit bhardwaj · Ed Chi