Phase Transitions in Semidefinite Relaxations

1 Introduction

• High-dimensional applications require estimating millions of parameters, while maximum-likelihood methods can require NP-hard combinatorial optimization.Convex relaxations are one approach to this tension.Source: §1 · pp. 2–3
• The statistical behavior of many convex relaxations is poorly understood; this paper develops a statistical-mechanics picture of semidefinite relaxations for three problems.The problems are motivated by clustering and graph synchronization.Source: §1 · p. 3
• In Z2 synchronization, noisy pairwise observations encode unknown ±1 group elements, and the solution can represent a signed-network bipartition.The observations have signal strength λ/n and Gaussian noise; the noise matrix is modeled with GOE entries.Source: §1 · p. 3
• U(1) synchronization estimates unit-modulus complex elements from noisy relative observations and is used to model network clock synchronization.The paper also relates it to phase retrieval and treats it as a prototype for synchronization over compact Lie groups.Source: §1 · pp. 3–4
• The two-block hidden-partition model generates edges at rates a/n within blocks and b/n across blocks, with a > b > 0 and bounded average degree.Its partition can be encoded by a ±1 vector, making the problem analogous to Z2 synchronization with signal strength λ = (a − b)/[2(a + b)].Source: §1 · p. 4

2 Illustrations

• The relaxation replaces an intractable combinatorial estimator with a polynomial-time convex SDP, then extracts a vector estimate from its optimizer’s eigendecomposition.Source: §2 · p. 6
• PCA is efficient but becomes significantly suboptimal at large λ because it ignores the binary constraint x0,i∈{+1,−1}.Source: §2 · p. 6
• For Z2 synchronization, SDP shares Bayes’ threshold λ=1 and, for λ≥1, has exponentially decaying MSE close to Bayes and below PCA.Source: §2 · p. 6
• The Gaussian-noise Z2 prediction captures hidden-partition SDP simulations well even at average degree d=5.Source: Figure 2 · p. 7, §2 · p. 8
• In bounded-average-degree graphs, SDP remains effective where classical spectral methods such as PCA fail to detect the partition.Source: §2 · p. 8
• For hidden partition, the SDP threshold exceeds ideal λ=1, but its excess is at most about 2% across d, making it nearly optimal.Source: §2 · pp. 8–9

3 Analytical results

• The analysis applies non-rigorous mean-field spin-glass techniques to large-N spin models, with partial rigorous evidence for its predictions reported in [MS15].The paper treats Gaussian-noise Z2 and U(1) synchronization before the sparse hidden-partition model.Source: §3 · p. 9

3.1 Gibbs measures, vector spin models

• The SDP relaxation is represented by vector spins on a sphere, with the SDP recovered in the limit of infinite spin dimension.The large-N analysis takes the spin-dimension limit after n tends to infinity; Grothendieck inequality supports this order at the level of objective value.Source: §3.1 · pp. 9–10

3.2 Cavity method: Z2 and U(1) synchronization

• The cavity method yields predictions for synchronization SDP error and overlap through a system of nonlinear equations.The predictions also characterize fixed-size spin marginals in the general finite-dimension, finite-temperature model.Source: §3.2 · p. 11

3.3 Cavity method: Community detection in sparse graphs

• Z2 synchronization appears to approximate the hidden-partition model accurately already at moderate average degree.The sparse-model phase transition is slightly shifted from the dense-case threshold λ = 1.Source: §3.3 · p. 12
• The predicted SDP threshold for sparse community detection is at most 2% sub-optimal and approaches the ideal value λ = 1 as average degree grows.The threshold is characterized by a distributional recursion that can be evaluated numerically.Source: §3.3 · p. 12

4 Final algorithmic considerations

• SDP thresholds are optimal for Z2 and U(1) synchronization and at most 2% sub-optimal for hidden-partition community detection.The paper presents these relaxations as computationally efficient and statistically efficient for the studied problems.Source: §4 · p. 13
• PCA reaches the optimal threshold for synchronization, while spectral algorithms reach the information-theoretically optimal threshold for community detection.These comparisons concern the specific problems studied in the paper.Source: §4 · p. 13

Supplementary Information

• Most derivations are non-rigorous, and rigorously proved results are stated as lemmas, propositions, or similar results.Source: Supplementary Information · p. 19

5.1 General notations

• The general notation distinguishes real and complex settings, defines the unit sphere in either field, and assigns s_G = 1 for Z2 and 2 for U(1).It also specifies conventions for Poisson and Gaussian variables and asymptotic equality.Source: §5.1 · p. 19

5.2 Estimation metrics

• The estimation-metrics subsection introduces scaled MSE and overlap for real and complex estimators, then omits n when referring to their high-dimensional limits.The complex overlap replaces sign(z) with z/|z|, defined as zero at z = 0.Source: §5.2 · pp. 19–20

Then we have the identity

• E{σ f(√γ σ + Z; γ)} = E{f(√γ σ + Z; γ)²} for the real observation model with independent signal and Gaussian noise.The proof uses the tower property of conditional expectation.Source: Then we have the identity · p. 20

6.1 Some estimation identities

• Symmetry of the real prior implies f(−y; γ) = −f(y; γ), which is used to obtain identity (31).Source: Then we have the identity · p. 20, §6.1 · p. 20

Then we have the identity

• The section applies the identities to specific real and complex cases, with the complex case using a prior uniform on the unit circle.The complex expectation is over Z ∼ CN(0, 1); the real and complex cases use different priors.Source: Then we have the identity · pp. 20–21

• A small field h breaks O(m) symmetry, with its norm sent to zero after n tends to infinity to select a solution at h = 0.The authors do not explicitly calculate with nonzero h.Source: §7 · p. 21
• After computing an expectation, the procedure forms an empirical covariance and returns its principal eigenvector.The expectation and covariance formulas are not specified in the supplied passages.Source: §7 · p. 22
• The estimator uses c = c(λ), the optimal scaling predicted by the asymptotic theory.Source: §7 · p. 22

• Setting m = 1 and β = λ/2 in the real case or β = λ in the complex case makes the Gibbs measure coincide with the Bayes-optimal estimator’s conditional density.Source: §7.1 · p. 22
• As β→∞, pβ,m concentrates on maximizers of the associated optimization problem.Source: §7.1 · p. 23
• For m ≥ n the limiting optimization recovers the SDP relaxation, whereas m = 1 gives the maximum-likelihood problem.Source: §7.1 · p. 23

7.2.1 General m and β

• The general cavity derivation treats cavity-variable pairs as independent for large n and uses consistency equations to determine the order parameters.The derivation invokes the law of large numbers and central limit theorem.Source: §7.2.1 · pp. 23–24
• For fixed k, the cavity analysis characterizes joint spin marginals under p_{m,β} through Gaussian variables and a uniform rotation, while phase invariance requires selecting a real-valued mean.The replica-symmetric prediction is expected to be asymptotically exact for Bayes-optimal, ML, and SDP estimators, but is only a good approximation in general.Source: §7.2.1 · pp. 24–25

7.2.2 Bayes-optimal: m = 1 and β ∈{λ/2, λ}

• For m = 1, the cavity equations yield asymptotic estimation-error predictions for the Bayes-optimal estimator in both real and complex cases.The real and complex cases use β = λ/2 and β = λ, respectively.Source: §7.2.2 · p. 26

7.2.3 Maximum likelihood: m = 1 and β →∞

• For m = 1 and β→∞, the real and complex maximum-likelihood analyses derive replica-symmetric critical points and asymptotic estimation metrics.The real-case critical point is explicitly described as within the replica-symmetric approximation; the complex-case estimate is also replica-symmetric.Source: §7.2.3 · pp. 27–28

7.2.4 General m and β →∞

• For general bounded m at β→∞, the analysis derives a replica-symmetric critical point λc(m) for the real and complex cases.The authors expect this calculation to be an excellent approximation, not exact, for bounded m.Source: §7.2.4 · pp. 30–31

7.2.5 SDP: m →∞and β →∞

• In the limit m→∞ and β→∞, the SDP prediction has a phase transition at λSDP_c.The section analyzes the transition by expanding the equations near λ = 1.Source: §7.2.5 · pp. 31–32

7.3 Free energy and energy

• The section presents the replica method as an easier route to the free energy and as an independent check of the cavity calculations.The section’s stated goal is to compute asymptotics for the partition function.Source: §7.3 · p. 32, §7.3.1 · p. 32

7.3.1 Replica calculation

• The replica calculation derives partition-function asymptotics by taking moments, introducing Gaussian integrals, and evaluating a saddle point in Q and μ.The resulting free-energy density is given in Eq. (150).Source: §7.3.1 · pp. 32–33, §7.3.2 · p. 33

7.3.2 Non-zero temperature (β < ∞)

• The finite-temperature calculation derives an RS free-energy functional whose saddle-point conditions recover Eqs. (57)–(59).The derivation treats real and complex cases, with the corresponding Gaussian expectation specified in the text.Source: §7.3.2 · pp. 34–35

7.3.3 Zero temperature (β →∞)

• At zero temperature, the measure concentrates around the maximizer σM(ξ, C), and the equations recover Eqs. (101)–(104).The maximizer is determined using a Lagrange multiplier enforcing the unit-norm constraint.Source: §7.3.3 · pp. 35–36

7.4 On the maximum likelihood phase transition

• For U(1), the replica-symmetric calculation gives λML_c = 2/√π, but the text says this apparent worse-than-Bayes threshold is an artifact of the approximation.The supplied passage does not state the replacement threshold.Source: §7.4 · pp. 36–37
• The heuristic identifies positive overlap when m = 0 becomes a local minimum, at λ > −F′′(0).For λ < −F′′(0), m = 0 is a local maximum under the stated differentiability assumption.Source: §7.4 · p. 37
• For Z2, the maximum-likelihood critical point is λML_c = 1, using F′′(0) = −1 together with the no-overlap bound below λ = 1.The argument relates the onset of positive overlap to the change in whether m = 0 is a local maximum or minimum.Source: §7.4 · p. 37

8 Analysis of PCA estimator for synchronization problem

• The leading eigenvalue λ1(Y) is 2 when λ ≤ 1 and λ + 1/λ when λ > 1.The PCA estimator is defined using the leading eigenvector of Y.Source: §8 · p. 38
• MSE( x̂PCA; c) = max(1 − λ^−2, 0), so the reported error is zero for λ ≤ 1 and positive for λ > 1.The text notes that the estimator can be expressed using λ1(Y), so knowledge of λ is not required.Source: §8 · p. 39

9 Analytical results for community detection

• Replica-symmetric cavity equations relate a node’s marginal to those of its descendant subtrees, and the analysis uses a log-linear vectorial ansatz that is not exact but can be systematically improved.The authors report that the ansatz yields very accurate results and expect its symmetric-phase approximation to be accurate for d large and d close to one.Source: §9 · p. 40, §9.1 · p. 41

9.1 Symmetric phase

• For d ≤ 1, the symmetric-phase recursion has only the zero solution; for d > 1, it has exactly two solutions, including a maximal solution c* that is positive with positive probability.The other solution is c0 = 0 almost surely.Source: §9.1 · p. 42

9.2 Linear stability of the symmetric phase and critical point

• The stability recursion admits the symmetric fixed point (c*, √c*Z), which does not break the +1 ↔ −1 symmetry.Here Z is standard normal and independent of c*; rescaling the perturbation does not change the recursion’s properties.Source: §9.2 · pp. 45–46
• The critical point is the smallest λ for which the symmetry-breaking perturbation’s exponential growth rate is positive; the prediction appears insensitive to the moment parameter α.The analysis uses the second moment, α = 2.Source: §9.2 · p. 46

9.3 Numerical solution of the distributional recursions

• Above a critical point, the estimated G2(d, λ) becomes positive and is essentially linear near the transition; for large fixed d, G2(d, λ) is logarithmic in λ.The critical point is estimated from population dynamics using a local linear fit where G2(d, λ) is significantly above zero.Source: §9.3 · pp. 48–49, Figure 5 · p. 49

9.4 The recovery phase (broken O(m) symmetry)

• For λ > λSDP_c(d), the cavity-equation analysis uses an ansatz breaking O(m) symmetry to O(m−1), in a regime where the SDP estimator has positive correlation as n → ∞.The analysis approximates the cavity equations within this broken-symmetry ansatz.Source: §9.4 · pp. 49–50
• In the d → ∞ limit, the recovery equations are shown to coincide with those for the Z2 synchronization problem derived using the replica method.The derivation verifies this limit by matching the corresponding equations and parameters.Source: §9.4 · pp. 52–54

9.5 Limitations of the vectorial ansatz

• The vectorial ansatz is approximate because its expansion assumes small inner products even though the ansatz permits alignment; it is expected to be accurate for large d or d close to 1.The authors suggest systematic improvement using quadratic terms depending on two-dimensional projections.Source: §9.5 · p. 54

10.1 Optimization algorithms

• The rank-constrained vector-spin formulation differs in value from the SDP by relative error O(1/m), uniformly in n, and simulations scale to n = 64,000 versus only hundreds for standard SDP solvers.Empirically, optimizers appear essentially independent of m around 40–100 for n ≲ 10^4, and typical instances do not appear stuck in local minima.Source: §10.1 · pp. 55–56

10.1.1 Projected gradient ascent

• Projected gradient ascent alternates a step along the objective gradient with projection onto the convex hull of the spin manifold.The supplied passages describe the projection subroutine through a Lagrangian and iterative computation of its multiplier.Source: §10.1.1 · pp. 57–58

10.1.2 Block coordinate ascent

• Block-coordinate ascent updates spins sequentially in random order by aligning each with its local field, providing an independent numerical check and appearing faster than projected gradient ascent.The method maximizes the objective over each spin in turn.Source: §10.1.2 · pp. 58–59

10.2 Numerical experiments with the projected gradient ascent

• In Figure 7, the SDP estimator’s overlap agrees well with the large-d cavity prediction even at average degrees d = 5 and 10; the phase-transition location seems indistinguishable, on this scale, from (a − b)/2(a + b) = 1.The plotted SDP performance is averaged over 500 realizations.Source: §10.2 · p. 60, Figure 7 · p. 61

10.2.1 Dependence on m

• For m ≥ 40, changes in average overlap are comparable to their standard deviations, motivating m = 40 for the section’s numerical experiments.This trend is reported for experiments at d = 5 and d = 10.Source: §10.2.1 · p. 60, Table 2 · p. 60, Table 3 · p. 62

10.2.2 Robustness and comparison with spectral methods

• At perturbation α = 0.025, SDP substantially outperforms Bethe Hessian, whose overlap degrades severely, while both methods perform nearly equivalently without perturbation.The perturbation adds triangles by connecting the neighbors of randomly selected vertices; results use n = 16,000 and d = 10.Source: §10.2.2 · pp. 62–63, Figure 8 · p. 63

10.3 Numerical experiments with block coordinate ascent

• Block-coordinate ascent simulations investigate η and tol3, dependence on spin dimension, convergence time, and the phase-transition location against analytical predictions.The section uses this algorithm for large-statistics simulations and high-precision determinations of the critical point.Source: §10.2 · p. 59, §10.3 · p. 63

10.3.1 Selection of the algorithm parameters

• With m = 100, the block-coordinate experiments track global magnetization over iterations; its asymptotic value is small and decreases as 1/η and 1/√n.Each iteration comprises n spin updates; the reported runs use d = 5 and λ = 1.1.Source: §10.3.1 · p. 63, Figure 9 · p. 64
• At small t, ∥M(σt)∥2=Θ(√n), then decays as t^-a with a≈1.1 at intermediate times, a regime seen only when η is large enough.Source: §10.3.1 · p. 64
• At large t, ∥M(σt)∥2 plateaus at Θ(1/√n), proportional to 1/η; its small, n-decreasing value supports approximate X1=0 and the choice η=1.Source: §10.3.1 · p. 64
• Convergence is roughly η-independent for η≲1 and somewhat slower for η≳1; iteration counts grow with n as a power law with b≈1.75, while tol3=10^-3 approximates the t→∞ behavior.Source: §10.3.1 · p. 65, Figure 10 · p. 65, Figure 11 · p. 66

10.3.2 Selection of m and scaling of convergence times

• For m=100, log(tconv) histograms concentrate around their median, unlike the broadening m=20 histograms; intermediate m show a crossover, supporting m=100 for n≲10^5.The authors interpret concentration as evidence of convergence to a well-defined global minimum and broadening as a signature of local minima.Source: §10.3.2 · p. 66, Figure 12 · p. 67
• The typical block-coordinate-ascent time complexity is empirically O(m n^1.22), with each iteration comprising n updates.For m=100, the mean and variance of log(tconv) were fitted across graph sizes.Source: Figure 13 · p. 67, §10.3.2 · p. 68

10.3.3 Determination of the phase transition location

• Binder-cumulant curves cross at roughly n-independent values; the largest-size crossings give nominal λ#(d) estimates broadly consistent with analytics, with a larger discrepancy at d=2.The comparison uses n=32,000 and 64,000 for d=2, and n=16,000 and 32,000 for d=5 and 10; the discrepancy may reflect finite graph sizes or inaccuracy in the vectorial ansatz.Source: §10.3.3 · p. 69, Figure 15 · p. 70

10.4 Improving numerical results by restricting to the 2-core

• Reducing each graph to its 2-core preserves whether the SDP estimator achieves positive overlap asymptotically, and therefore does not change the phase-transition location.The removed portion consists with high probability of trees of size O(1); the authors also report numerical confirmation of the invariance.Source: §10.4 · p. 71