Source-linked AI summary
The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints
Po-Wei Wang, Wei-Cheng Chang, J. Zico Kolter
TL;DR
Large SDPs can be costly because their matrix variables grow quadratically, while existing low-rank approaches lack general global-convergence guarantees for this setting. The paper introduces low-rank coordinate descent for diagonal-constrained SDPs and reports faster MAXCUT solving alongside convergence guarantees under stated conditions.
Problem
Generic SDP solvers face a quadratic number of matrix variables, and existing low-rank methods lack a general proof of global convergence without strong assumptions.
Source: §1 · p. 2Method
Results
The method is several times faster than existing state-of-the-art solvers on the MAXCUT relaxation, and with a step size it converges globally almost surely under random initialization.
Source: §1 · pp. 2–3Takeaways & Limitations
For sparse adjacency matrices, a round of MAXCUT updates takes O(k · #edges) time.
Source: §4.1 · p. 13The convergence proof for the method without step size requires an additional non-degeneracy assumption on its normalization.
Source: §3.1 · p. 6
Abstract
from arXiv · showhide
In this paper, we propose a low-rank coordinate descent approach to structured semidefinite programming with diagonal constraints. The approach, which we call the Mixing method, is extremely simple to implement, has no free parameters, and typically attains an order of magnitude or better improvement in optimization performance over the current state of the art. We show that the method is strictly decreasing, converges to a critical point, and further that for sufficient rank all non-optimal critical points are unstable. Moreover, we prove that with a step size, the Mixing method converges to the global optimum of the semidefinite program almost surely in a locally linear rate under random initialization. This is the first low-rank semidefinite programming method that has been shown to achieve a global optimum on the spherical manifold without assumption. We apply our algorithm to two related domains: solving the maximum cut semidefinite relaxation, and solving a maximum satisfiability relaxation (we also briefly consider additional applications such as learning word embeddings). In all settings, we demonstrate substantial improvement over the existing state of the art along various dimensions, and in total, this work expands the scope and scale of problems that can be solved using semidefinite programming methods.
1. Introduction
The introduction motivates low-rank optimization for structured SDPs and presents the Mixing method for diagonal constraints. It highlights applications to MAXCUT and MAXSAT, along with convergence guarantees and reported speed and scale gains.
1. Introduction
- Low-rank formulations represent X as V^T V, avoiding explicit semidefiniteness constraints, but prior methods for optimizing V can converge slowly or require difficult step-size choices.Optimal solutions can be low-rank, motivating non-convex formulations despite these practical challenges.Source: §1 · p. 2
- The Mixing method is a low-rank coordinate descent approach for SDPs constrained only on matrix diagonal entries, including unit-diagonal constraints.The paper says the method extends easily from unit diagonal constraints to arbitrary positive diagonal values.Source: §1 · p. 2
- The diagonal-constrained SDP setting is a special case of general SDPs that includes the MAXCUT relaxation and motivates the paper's primary application.The paper also proposes a relaxation of general MAXSAT, extending the MAX-2SAT relaxation.Source: §1 · pp. 2–3
- With sufficient rank k > 2n, the method converges to the original SDP's global optimum with local linear convergence, although the proof uses a step-size version.The unmodified method is strictly decreasing and converges to a first-order critical point; its non-optimal critical points are unstable, while the step-size version converges globally almost surely under random initialization.Source: §1 · p. 3
- 10-100x faster than other state-of-the-art solvers, the Mixing method also scales to millions of variables on the MAXCUT SDP relaxation.For MAXSAT, the proposed formulation is solvable in linear time in the number of literals, with better approximation ratios than other approximation algorithms and results comparable to the best partial MAXSAT solvers in some instances.Source: §1 · p. 3
2. Background and related work
Prior work uses low-rank factorizations and manifold-based optimization to reduce the cost of solving SDPs. Existing convergence results leave a gap for global guarantees in the spherical, diagonally constrained setting considered here.
2. Background and related work
- An SDP with p constraints admits a solution of rank k = ⌈√2p⌉, enabling a factorization X = V^T V with fewer variables and no explicit semidefinite constraint.Burer and Monteiro first used this structure in SDPLR, applying L-BFGS to an extended Lagrangian problem.Source: §2 · pp. 3–4
- Prior low-rank methods are observed to reach global optima in practice, but the cited work lacks a general proof without strong assumptions.Existing results include convergence to critical points or local-minimizer guarantees under specific conditions, rather than a general global convergence result for this setting.Source: §2 · p. 4
- Existing global-convergence results address unconstrained or convex-feasible formulations, while cited random-initialization results do not apply to the spherical manifold.The cited results in Lee et al. (2016, 2017) fail there because of a Jacobian singularity, even with step size.Source: §2 · p. 4
- Certifying global optimality in low-rank SDP methods typically uses an outer loop that checks a dual certificate and increases rank when needed.Computing the dual solution can require an eigenvalue problem as large as the original matrix, so this check is often avoided in practice.Source: §2 · p. 4
- The Goemans-Williamson SDP relaxation gives a 0.878 approximation guarantee for MAXCUT and MAX-2SAT; MAXSAT experiments report tighter SDP bounds than classical LP relaxation.The paper frames its approach as a way to obtain better results than linear programming in less time.Source: §2 · p. 5
3. The Mixing method
This section presents the Mixing method’s cyclic closed-form coordinate updates on a low-rank SDP factorization and analyzes its convergence and critical points. It characterizes optimal critical solutions through a positive-semidefiniteness condition and establishes instability of non-optimal critical points.
3. The Mixing method
- Each cyclic update replaces a unit vector with the normalized negative weighted sum of the others; for sparse C, one full pass costs O(k·m).If the weighted sum has zero norm, the vector is not updated.Source: §3 · p. 5
3.1 Convergence properties of the Mixing methods
- The method strictly decreases its objective and converges to first-order critical points; it converges linearly near the global optimum with a step size, or without one under Assumption 3.2.The no-step-size results require non-degenerate normalization.Source: §3.1 · pp. 6–7
- For k > 2n, almost all C yield only unstable non-optimal first-order critical points, from which the Mixing method tends to diverge locally.The theorem identifies these points as unstable fixed points.Source: §3.1 · p. 7
3.2 Proof of Theorem 3.4: The instability of non-optimal criticals points
- The instability proof compares the Mixing method’s Jacobian with the Gauss–Seidel Jacobian, using their shared eigenvalue structure to establish local instability around non-optimal critical points.The proof uses a spectral-radius argument and results on eigenvalues of Kronecker products.Source: §3.1 · p. 7
3.1 Convergence properties of the Mixing methods
- For k > 2n and 0 < θ < 1/max_i ||c_i||_1, the step-size variant converges almost surely to a global optimum for almost every C under random initialization.The result applies without additional assumptions.Source: §3.1 · pp. 6, 8
Proof of technical lemmas.
- The technical lemmas show that the Mixing Jacobian inherits eigenvalues from the Gauss–Seidel Jacobian, whose spectral radius exceeds one when S = C + Dy is not positive semidefinite.This provides the spectral basis for the instability result.Source: Proof of technical lemmas · p. 11
- A critical solution V is optimal if and only if S = C + diag(y) is positive semidefinite, where y_i = ||V c_i||.At an optimum, y_i is positive unless c_i = 0.Source: Proof of technical lemmas · p. 11
- The dual optimum y* is unique, and every optimal feasible U satisfies ||U c_i|| = ||V* c_i|| for all i.The passage derives this equality from f(U) − f* = tr(U S* U^T) = 0.Source: Proof of technical lemmas · p. 11
- For almost every C, every non-optimal first-order critical point is unstable under the Mixing method.The argument uses that critical points have rank below k and that the method’s Jacobian has spectral radius greater than one at non-optimal points.Source: Proof of technical lemmas · p. 12
4. Applications
The applications adapt Mixing to the MAXCUT relaxation and introduce a general MAXSAT relaxation. The paper reports that the MAXSAT relaxation achieves substantially better approximation results than existing relaxations.
4.1 Maximum cut problem
- For MAXCUT, Mixing applies directly to the unit-diagonal SDP and runs a round of updates in O(k · #edges) time for sparse adjacency matrices.Source: §4.1 · p. 13
4.2 Maximum satisfiability problem
- The proposed MAXSAT relaxation achieves substantially better approximation results than existing relaxations.Source: §4.2 · p. 13
- The MAXSAT relaxation generalizes the Goemans-Williamson MAX-2SAT idea; its formula matches their MAX-2SAT approximation.Source: §4.2 · p. 13
- MAXSAT uses an auxiliary truth variable to avoid a bias term, maintains each clause vector zj, and runs in O(k · m) time; rounding compares each variable with v0.Source: §4.2 · pp. 13–14
- For binary assignments, the MAXSAT clause term upper-bounds the exact solution; relaxing variables to unit vectors yields the SDP, with weights wj = 1/(4|sj|).Source: §4.2 · p. 13
5. Experimental results
The Mixing method achieves strong MAXSAT approximation quality and substantially faster MAXCUT optimization than competing approaches. Experiments also find that very low rank can suffice for both SDP optimization and randomized rounding.
Running time comparison for MAXCUT
- 10–100x faster than competing approaches at modest accuracy on MAXCUT, and about 10x or more faster than Manopt throughout the largest runs.Figure 1 plots objective difference against training time; some SDPLR, DSDP, and RBR curves are absent because those solvers crashed or produced no solution within an hour.Source: §5 · pp. 14–15, Figure 1 · p. 15
Effectiveness of the Mixing method on approximating MAXSAT problems
- 0.978 average approximation ratio across 525 MAXSAT complete-track problems, with solutions usually found within seconds or less.The method sometimes finds perfect solutions faster than the best partial solvers.Source: §5 · p. 15
- The Mixing method gives better and faster MAXSAT solutions than LP approximations, and is sometimes faster than the best partial and complete competition solvers.Figure 2 compares approximation ratio over log running time; the complete solvers’ results are verified, whereas partial solvers’ results are not.Source: §5 · pp. 15–16, Figure 2 · p. 16
The sufficient rank for optimization and randomized rounding
- Rank ≤5 suffices for nearly optimal optimization and randomized-rounding performance in the tested MAXSAT instances; increasing rank beyond 2n does not improve performance.The experiments measure relative objective error and randomized-rounding approximation error.Source: §5 · p. 16, Figure 3 · p. 17
6. Conclusion
The paper presents the Mixing method for diagonally constrained SDPs and establishes convergence properties alongside positive results across application domains.
6. Conclusion
- The Mixing method is a simple, parameter-free low-rank coordinate descent approach for diagonally constrained semidefinite programs.The paper reports first-order critical-point convergence, instability of non-optimal critical points at sufficient rank, and almost-sure global convergence with a proper step size.Source: §6 · p. 17
- Experiments report faster optimization for MAXCUT and word embeddings, and high-quality application solutions for a MAXSAT relaxation.The paper concludes that its results expand the applications feasibly addressed with SDP methods and advance structured low-rank optimization.Source: §6 · p. 17
Appendix A. Proof of Theorem 3.1: Convergence to critical points
The appendix establishes that Mixing updates decrease the objective and uses this decrease to show that limit points are critical points.
Appendix A. Proof of Theorem 3.1: Convergence to critical points
- Each coordinate update yields an objective decrease, and summing the per-coordinate decreases gives the full-iteration result.The proof considers the objective as a function of v_i while holding the other coordinates fixed.Source: Appendix A · p. 21
Proof of Theorem 3.1
- Under Assumption 3.2, the objective values decrease to a limit, and every limit point is a fixed point with zero Riemannian gradient.The proof uses compactness, bounded coordinate normalizers, and the vanishing function decrease; the same argument applies to the step-sized version.Source: Proof of Theorem 3.1 · pp. 21–22
Appendix B. Proof of Theorem 3.3: Local Linear convergence
The proof develops a local error bound for the Mixing method using expansions around a critical point and properties of its coordinate updates.
Appendix B. Proof of Theorem 3.3: Local Linear convergence
- The asymptotic analysis uses a generalized Rayleigh quotient to identify an inherent problem while removing an assumption.The proof relates the quadratic terms in ∥V Ŝ∥² and f(V) − f̄.Source: Appendix B · pp. 22–23
- ∥VS∥² serves as a local error bound near the critical point.The proof establishes this bound using a geodesic perturbation and a generalized Rayleigh quotient analysis.Source: Appendix B · p. 22
- A unit tangent perturbation on the sphere gives v_i = v̄_i + t u_i + O(t²) and V S̄_i = t U S̄_i + O(t²).The derivation starts from the geodesic formula and expands around the critical point.Source: Appendix B · p. 22
- Choosing ŷ_i = −v_i^T V c_i ensures ∥V S∥² ≥ ∥V Ŝ∥² for S = C + Dy.The proof also expresses the Mixing update difference as V S(L^T + Dy)^−1.Source: Appendix B · p. 23
Proof of Theorem 3.3
The proof turns a local bound on the update into linear convergence near a critical point, for both the standard and step-size Mixing methods.
Proof of Theorem 3.3
- The Mixing method converges R-linearly to the nearest critical point in its neighborhood.The proof uses a local bound on the update norm in terms of the objective gap.Source: Proof of Theorem 3.3 · p. 24
- The step-size Mixing method has the same local linear convergence, for θ ∈ (0, 1/max_i ∥c_i∥).The proof invokes Lemma D.3 and Lemma B.4.Source: Proof of Theorem 3.3 · p. 24
- The solution converges to a critical point Q-linearly.Source: Proof of Theorem 3.3 · p. 24
Appendix C. Proof of Lemma 3.10: Divergence of Gauss-Seidel methods
The proof shows that Gauss-Seidel diverges when its quadratic objective is not positive semidefinite, by ruling out convergence to a negative-valued limit.
Appendix C. Proof of Lemma 3.10: Divergence of Gauss-Seidel methods
- When S is not positive semidefinite, a negative-curvature eigenvector yields an initial point with negative objective value.The proof considers Gauss-Seidel iterates initialized at that eigenvector.Source: Appendix C · p. 24
- The Gauss-Seidel updates decrease the objective monotonically, leaving convergence below zero or divergence to negative infinity as the two cases.Source: Appendix C · p. 24
- Convergence below zero is impossible: a convergent sequence would reach a fixed point with Sx̄ = 0 and objective zero.This contradicts the monotone decrease from a negative initial value.Source: Appendix C · pp. 24–25
- The remaining case is exponential divergence to negative infinity, and the Gauss-Seidel iteration matrix has spectral radius greater than one.Source: Appendix C · pp. 24, 26
Appendix D. Proof of Theorem 3.5: Global convergence with a step size
The step-size proof prevents degenerate updates and establishes that the method is a diffeomorphism by analyzing its coordinate maps.
Appendix D. Proof of Theorem 3.5: Global convergence with a step size
- For θ ∈ (0, 1/max_i ∥c_i∥₁), the update remains nondegenerate: ∥θV c_i∥ ≤ 1 − δ and ∥v_i − θV c_i∥ ≥ δ.Source: Appendix D · p. 28
- With the same step-size range, the Mixing method Mθ is a diffeomorphism.The proof reduces this to showing that each coordinate update is a diffeomorphism.Source: Appendix D · p. 28
- The coordinate-map argument uses a projective mapping and its inverse, with the square root justified by the nondegeneracy bound.Source: Appendix D · p. 28
Proof of Theorem 3.5
The step-size Mixing map has a Jacobian whose spectral radius at critical points is bounded below by that of coordinate gradient descent. This supports the result that non-optimal critical points are unstable and that random initialization leads almost surely to a global optimum.
Proof of Theorem 3.5
- At critical points, the step-size Mixing Jacobian’s spectral radius is lower bounded by that of coordinate gradient descent (CGD).The comparison uses the CGD Jacobian on the linear system S = C + Dy.Source: Proof of Theorem 3.5 · p. 29
- Because CGD has spectral radius above 1 when S is not positive semidefinite, non-optimal critical points are unstable fixed points of the step-size Mixing map.The proof applies the center-stable manifold theorem to show that random initialization almost surely escapes these points and converges to a global optimum.Source: Proof of Theorem 3.5 · p. 29
- The critical points are non-isolated because they are invariant to rotations in R^k.The proof notes that the cited center-stable manifold result still suffices despite this non-isolation.Source: Proof of Theorem 3.5 · p. 29
Appendix E. Proof of Lemma 3.11: Rank Deficiency in Critical Points
The appendices establish a generic rank-deficiency result for critical points and apply Mixing to the GloVe objective. On wiki8 and enwiki, Mixing converges substantially faster than SGD and reaches a lower function value.
Appendix E. Proof of Lemma 3.11: Rank Deficiency in Critical Points
- The rank argument uses a right-hand side independent of V to bound critical-point rank, then bounds the dimension of the resulting matrix sets.It represents C as M − Dν, with M = C + Dν and nullity ℓ, and considers ℓ ≥ k.Source: Appendix E · p. 30
- A dimension argument establishes that, for almost all C, critical points have rank at most k − 1 when the stated rank condition holds.The argument bounds the set of matrices admitting rank-k critical points; the excerpt gives the condition as k(k+1)/2 + n < n(n+1)/2.Source: Appendix E · p. 30
Appendix F. Application: Word embedding problem
- The application uses a slightly modified GloVe objective based on word co-occurrence counts and excludes self-loop terms.Its weighting factor suppresses high-frequency words.Source: Appendix F · p. 31
- Updating one word vector yields an unconstrained quadratic subproblem, approximated with conjugate gradients and applied cyclically across vectors.A full pass costs O(k · m · (# CG iterations)); the reported settings typically use fewer than 10 CG iterations.Source: Appendix F · pp. 31–32
- The word-embedding experiment demonstrates that Mixing can extend to a nonlinear objective function.The figure caption identifies SGD as the comparison method.Source: Figure 4 · p. 32
- On both wiki8 and enwiki, Mixing converges substantially faster and reaches a lower function value than SGD.Figure 4 compares objective gap against training time; the corpora were preprocessed and words occurring fewer than 1000 times were excluded.Source: Appendix F · p. 32, Figure 4 · p. 32