Smoothing Without Densifying: Structure-Preserving Noise for Burer–Monteiro SDPs

Semidefinite programs are convex optimization problems over matrices that must stay positive semidefinite. They power Max-Cut approximation, phase retrieval, synchronization, and neural-network certification, but the matrix variable needs $n^2$ numbers of storage. The usual escape is the Burer–Monteiro method: write the matrix as $X = YY^\top$ with a thin factor $Y$ of size $n \times p$ and run gradient descent on $Y$. Memory falls to $np$, but the problem is no longer convex, so local search could stall at bad local minima. In practice it almost never does. The standard theoretical explanation is smoothed analysis, which studies worst-case inputs after a small random perturbation. It shows that adding a small random matrix to the cost removes the bad minima. The catch is that every such result perturbs the cost with a dense Gaussian matrix. That turns a sparse graph with five million edges into a matrix with $10^{12}$ nonzeros, and it erases the memory and speed advantage that made the method attractive.

This proposal asks whether the smoothing noise can respect the structure of the instance. The two candidates are noise placed only on the graph's existing edges, and noise of low rank. The question is whether such noise still dismantles the known traps while keeping per-iteration cost linear in the problem size. Our claim is that it can, under a checkable degree-of-freedom condition. A side effect of sparse noise is that it shifts the optimum far less than dense noise does. We will prove this where possible, measure it everywhere, and identify where structured noise provably fails.

Core Claim

Existing smoothed guarantees for Burer–Monteiro all perturb the cost $C$ with a dense Wigner matrix (a symmetric matrix with independent Gaussian entries). This holds for the landscape result on approximate stationary points in Smoothed analysis of the low-rank approach for smooth semidefinite programs, the penalty-form result in Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form, and the end-to-end polynomial-time result in Polynomial time guarantees for the Burer-Monteiro method. The only structured-noise result in the file, Smoothed analysis of the condition number under low-rank perturbations, shows that a rank-$k$ Gaussian term $UV^\top$ regularizes a matrix's condition number as well as dense noise does, at $O(nk)$ cost. That paper treats a linear-algebra quantity, not a non-convex landscape, and it notes that structured noise breaks standard anti-concentration tools.

We propose to replace the dense perturbation with a Gaussian $G$ drawn from a linear subspace $L$ of symmetric matrices. We study two cases. In the first, $L_E$ is supported on the edge set $E$ of the input graph. In the second, $L_k = \{UU^\top\}$ is generated by a random $n \times k$ Gaussian $U$. The new content is a transversality condition that decides whether a subspace is rich enough. For the Max-Cut SDP, a factor $Y$ is a critical point when $(C - \mathrm{diag}(\mu))Y = 0$ with $\mu_i = (CYY^\top)_{ii}$. A spurious critical point survives the perturbation only if the noise cannot move this $n \times p$ equation in enough directions.

A dimension count gives sharp, falsifiable predictions. Edge-supported noise has $|E|$ free parameters acting on an $np$-dimensional condition, so it should suffice roughly when the average degree is at least on the order of $2p$. Rank-$k$ noise should need $k$ comparable to $p$.

Diagonal noise should do nothing at all, because the constraints $X_{ii}=1$ make $\langle \mathrm{diag}(d), X\rangle$ constant. It is therefore a built-in negative control.

The payoff of sparse noise is a smaller distortion of the problem. A dense Wigner matrix with entry scale $\sigma$ has operator norm about $2\sigma\sqrt{n}$. Edge-supported noise has operator norm of order $\sigma\sqrt{d_{\max}}$ up to logarithms, by standard bounds for sparse random matrices. Since $|\langle G, X\rangle| \le \|G\|_{op}\,\mathrm{tr}(X) = n\|G\|_{op}$ for Max-Cut, the relative objective bias from smoothing drops from about $\sigma\sqrt{n}/\bar d$ to about $\sigma\sqrt{d_{\max}}/\bar d$, where $\bar d$ is the average degree and the objective is of order $n\bar d$.

Research Program

Theory. The first strand adapts the tube-volume method of Cifuentes and Moitra to noise restricted to $L$. Their method bounds how much Gaussian probability mass lies near the algebraic set of cost matrices that admit spurious critical points. If the affine slice $C + L$ is not contained in that bad set, the intersection is a lower-dimensional variety inside $L$, and tube-volume bounds apply within $L$.

The work is to show non-containment under the transversality condition above. That means showing the linear map $G \mapsto GY - \mathrm{diag}((GYY^\top)_{ii})Y$, restricted to $L$, has full rank onto the relevant normal directions at every candidate spurious $Y$. The target statement mirrors Smoothed analysis of the low-rank approach for smooth semidefinite programs: with high probability, every approximate second-order stationary point has optimality gap bounded by the stationarity tolerances and $\sigma$. Here the dependence on $\sigma$ would run through $\dim L$ rather than $n^2$.

We expect the exponents to be loose, as they are for the dense case, and we treat the empirical phase diagrams below as the sharper evidence. We also expect a negative theorem. For edge-supported noise on graphs with a large automorphism group, a construction in the style of The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound may produce traps that survive any noise on the edges, while rank-$k$ noise still breaks them. That paper builds traps from symmetric "axial" vector configurations and nearly positive-definite cost matrices.

Algorithm. The second strand is a drop-in solver: factored gradient descent from Factored Gradient Descent, run on the Riemannian product of spheres, applied to $C+G$. The edge-supported variant stores one extra weight per edge. The low-rank variant stores $U$ and adds $O(nkp)$ work per gradient.

At the end, the solver re-evaluates the factor on the original $C$ and attaches an optimality certificate, which costs $O(n)$ memory. It forms the dual slack $S = C - \mathrm{diag}(\mu)$ and computes $\lambda_{\min}(S)$ by Lanczos iteration using only matrix-vector products. This yields a computable duality gap on every instance.

Positioning. The deterministic certificate of Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs rules out bad minima whenever $\lambda_n(L)/\lambda_2(L) < p$. Here $L$ is the graph Laplacian, a different object from the noise subspace $L$ above. We compute this ratio on every benchmark graph to separate instances already covered by deterministic theory from those where smoothing is doing real work.

Baselines

The naive reference point is unperturbed Burer–Monteiro gradient descent at the same rank $p$, with the same random initialization, step-size schedule, and iteration budget. It answers whether smoothing is needed at all on a given family.

The strongest landscape competitor is dense Wigner smoothing as in Polynomial time guarantees for the Burer-Monteiro method. The file reports that adding noise at $\sigma = 0.2$ raised success on difficult synthetic instances from roughly 50% to nearly 90%. We run it two ways. Explicitly where memory allows ($n \le 3000$). Implicitly via a seeded generator at larger $n$, which costs $O(n^2)$ time per matrix-vector product but no extra memory. We match $\sigma$ by equal objective bias rather than equal entry scale, because matching entry scale would favour sparse noise unfairly. Structured noise beats it if it reaches the same certified success rate at equal or lower relative bias, while keeping per-iteration time linear in $|E| + np$.

The strongest memory-constrained competitors are SketchyCGAL from Scalable Semidefinite Programming and the smooth Frank–Wolfe method of A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP. The file reports their scale: SketchyCGAL solved a Max-Cut instance with 23 million vertices (549 trillion implicit entries) on a laptop-equivalent machine, and the Frank–Wolfe method solved $10^6$ nodes and $5\times 10^6$ edges in $O(n)$ storage. For Gset it reports no per-instance numbers ("no reported result found on Lacuna for SketchyCGAL or Frank–Wolfe relative error on individual Gset graphs"), so we will rerun both with their released settings. We use equal wall-clock and memory budgets on the same machine and report certified duality gap against time. Structured-noise Burer–Monteiro wins if it reaches a given certified gap faster at matched memory. Tying is acceptable if it also returns the explicit factor for rounding, which sketching must reconstruct.

The ablation that isolates the key ingredient is diagonal-only noise at matched norm. Theory says it cannot change the Max-Cut landscape, so any gain it shows would expose a confound. A second control places sparse noise on a random support unrelated to the graph, which tests whether alignment with the edges matters beyond sparsity alone.

Why not just…?

Why not just use random restarts or noisy gradient steps instead of perturbing the data? Noise in the iterates helps escape saddle points but leaves the landscape unchanged. A genuine spurious local minimum, like the degenerate ones in The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound, is still there afterward. Restarts can still work if the bad basin is small. We include restarts at an equal total gradient budget on the trap instances. If restarts match structured smoothing there, the landscape-level contribution is moot for practice, and we will say so.

Why not just apply dense Gaussian noise implicitly from a random seed, so it costs no memory? Memory is indeed not the obstacle in that case; time is. Every matrix-vector product becomes $O(n^2)$, which at $n=10^6$ is about $10^{12}$ operations per step, against about $10^7$ for the sparse graph. Dense noise also carries the larger $\sigma\sqrt{n}$ bias computed above. The bias-matched comparison in the experiments quantifies both costs directly.

Why not just raise the rank $p$? Traps survive up to $p=n/2$ in the worst case, per O'Carroll et al. Rank inflation also gives back the memory savings when the number of constraints is large, as discussed around The non-convex Burer-Monteiro approach works on smooth semidefinite programs. Still, this is a real threat on benign instances. The phase diagram over $p$ shows the smallest rank at which unperturbed and smoothed runs succeed. Structured noise matters only if it lowers that rank.

Why not just use convex sketching and avoid non-convexity altogether? SketchyCGAL has no landscape problem. Its proved rate, however, is $O(t^{-1/2})$, it depends on repeated Lanczos calls, and it must reconstruct $X$ from a sketch. Whether that adds up to a practical loss is an empirical question, which the time-to-certified-gap comparison settles in either direction.

Proposed Experiments

Trap instances. First, we build the axial-position trap instances of O'Carroll et al. for $n$ from 100 to 2000 and ranks up to $n/2$. On each, we compare no noise, dense, edge-supported, rank-$k$, diagonal, and random-support noise. The metric is the fraction of 100 seeds certified globally optimal by the Lanczos dual check.

The decisive check is the predicted dimension-count boundary. Edge-supported noise should succeed when the average degree exceeds a constant times $p$ and fail below it. Rank-$k$ noise should switch on near $k \approx p$. Diagonal noise should equal no noise. If the boundaries fall where the counting predicts, the transversality condition earns its place. If edge noise works at every degree, the condition is too conservative. If it fails broadly, the sparse route is ruled out and the low-rank route carries the proposal.

Realistic graphs. Second, on Gset and on $d$-regular random graphs up to $n=10^6$, we compute $\lambda_n/\lambda_2$ of the graph Laplacian to flag instances already covered by Rakoto Endor and Waldspurger. On the uncovered instances, we measure certified success, relative objective bias on the original $C$, and wall-clock time to a fixed duality gap, against SketchyCGAL and Frank–Wolfe under matched budgets. The bias prediction is that relative bias falls by roughly a factor of $\sqrt{n/d_{\max}}$ versus bias-matched dense noise. It is directly checkable from these runs.

Transfer. Third, we test whether the edge-versus-low-rank distinction carries over to the PhaseCut phase-retrieval SDP at $n$ up to $10^6$, where the measurement structure is low-rank rather than graph-sparse. This is the setting in which Smoothed analysis of the low-rank approach for smooth semidefinite programs reported Burer–Monteiro about 40 times faster than an interior-point solver at $n=3000$.