Many semidefinite programs (SDPs) are too large to store. An SDP is an optimization over a positive semidefinite $n \times n$ matrix, and at a million variables that matrix has $10^{12}$ entries. Current linear-memory solvers never form it. They grow a compressed picture of it one eigenvector at a time. We propose a different route. Keep only the small dual vector. Represent the primal matrix implicitly as the covariance of a simulated physical system: a harmonic oscillator whose stiffness matrix is the dual "slack" matrix, held at a fixed temperature by a colored-noise thermostat. A thermostat is the random-kick-plus-friction term in molecular dynamics that keeps a system at a set temperature. "Colored" means the kicks are correlated in time, so friction can be tuned separately at each vibrational frequency.
Under a log-barrier, the ideal primal matrix is exactly proportional to the inverse slack matrix. That inverse is exactly the position covariance of the thermostatted oscillator. The simulation therefore gives three things at once. Averages of $q_i^2$ supply the dual gradient. Signs of the positions $q(t)$ are ready-made Goemans–Williamson rounding samples. And whenever the oscillator stays stable, the dual objective is a certified upper bound. Memory is a handful of length-$n$ vectors.
The colored noise has a specific job. Plain white-noise dynamics mixes at a rate set by the stiffest-to-softest frequency ratio, and that ratio blows up along the barrier path. A frequency-shaped thermostat can damp every mode near its fastest-decorrelation (critically damped) rate simultaneously.
Core Claim
For the Max-Cut SDP the dual variable is $y \in \mathbb{R}^n$ and the slack matrix is $S(y) = \mathrm{Diag}(y) - L/4$, where $L$ is the graph Laplacian. The barrier dual problem is
$$\min_{y} \; \mathbf{1}^T y - \mu \log\det S(y), \qquad \nabla = \mathbf{1} - \mu\,\mathrm{diag}\big(S(y)^{-1}\big),$$
where $\mu > 0$ is the barrier weight. The primal iterate on the central path is $X(y) = \mu S(y)^{-1}$, and the duality gap on that path is $n\mu$.
Now evolve positions $q$ under the potential $\tfrac12 q^T S(y) q$ with a thermostat at temperature $\mu$. The stationary distribution of $q$ is exactly Gaussian $\mathcal{N}(0, \mu S(y)^{-1}) = \mathcal{N}(0, X(y))$, because the dynamics are linear and the fluctuation–dissipation relation holds.
We claim that a two-timescale scheme closes the loop in $O(n_s n + |E|)$ memory, where $n_s$ is the number of auxiliary thermostat variables per coordinate. The fast process runs the thermostatted oscillator. The slow process takes stochastic gradient steps on $y$ using running averages of $q_i^2$, and shrinks $\mu$ along the way. The scheme costs one sparse matrix–vector product per integration step and needs no eigen-solver in the inner loop. The inner-loop Lanczos is the arithmetic bottleneck that Scalable Semidefinite Programming names as its main open problem.
The ingredient that makes this practical rather than merely correct is frequency-uniform damping. The spectrum of $S(y)$ widens as $\mu \to 0$. A matrix-based generalized Langevin thermostat of the kind Efficient stochastic thermostatting of path integral molecular dynamics uses to sample efficiently "across widely separated relaxation times" should keep the fast process's correlation time roughly flat across that spectrum. White-noise Langevin cannot do that.
Relation to Prior Work
The mechanism comes from Evaluating functions of positive-definite matrices using colored-noise thermostats. That paper maps a fixed positive-definite matrix to the stiffness of a fictitious oscillator and reads off matrix functions from trajectory averages using only matrix–vector products. It beats Cholesky beyond $N \approx 10^5$ on sparse lattices. It evaluates a static matrix, however, and names two weaknesses: sharp target functions need many auxiliary variables, and indefinite matrices make the dynamics diverge.
Our proposal turns the static evaluator into the inner loop of an optimizer, and it sidesteps both weaknesses. The target function $f(\lambda) = \mu/\lambda$ is rational, so no hard spectral fit is needed; the thermostat only has to be tuned for sampling efficiency. Positive definiteness of $S(y)$ is exactly dual feasibility, and the barrier maintains it. Divergence of the oscillator then becomes a useful infeasibility alarm: we backtrack $y$ when energy blows up.
The optimization side is constrained by three linear-memory solvers.
- Scalable Semidefinite Programming (SketchyCGAL) combines conditional-gradient steps with a Nyström sketch. It needs one Lanczos eigenvector per iteration and proves an $O(k^{-1/2})$ rate.
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching (USBS) bundles several eigenvectors and drops rigid step schedules so it can warm-start.
- A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP keeps strictly $O(n)$ memory. It maintains Gaussian samples whose covariance tracks the iterate, so rounding never materializes $X$.
That last paper is the closest in spirit: it also represents $X$ through Gaussian samples. Its samples, though, are built from Frank–Wolfe eigenvector steps, while ours are the thermostat's own trajectory, driven by a dual interior-point path. All three are eigenvector-driven primal methods. Ours is an eigen-solver-free dual method.
Riemannian Langevin Algorithm for Solving Semidefinite Programs is the other point of contact. It injects white noise on the low-rank factor manifold to escape saddles, with iteration bounds of order $\epsilon^{-4.5}$. There the noise is an exploration device on a non-convex problem. Here the noise is a representation of a convex dual path, and the relevant physics is mixing speed rather than saddle escape.
Research Program
We will build the method in three pieces and analyze the coupling between them.
The fast sampler. The fast sampler integrates the extended Markovian form of the generalized Langevin equation, following Nuclear Quantum Effects in Solids Using a Colored-Noise Thermostat. Each coordinate carries a position, a momentum and $n_s$ auxiliary variables, all driven by a shared small drift matrix and diffusion matrix. We fit those matrices so that the position autocorrelation time is near-minimal over a target frequency band. The band is $[\omega_{\min}, \omega_{\max}]$, estimated cheaply from the current $S(y)$ with a few power iterations. Integration uses the standard exact-Ornstein–Uhlenbeck splitting. We pick the timestep from $\omega_{\max}$ and stabilize the stiffest modes the way Efficient multiple time scale molecular dynamics: Using colored noise thermostats to stabilize resonances damps resonances. Because the equilibrium covariance is exactly $\mu S^{-1}$ for any valid drift/diffusion pair that satisfies fluctuation–dissipation, the thermostat design affects only variance and mixing, never the correctness of the stationary law.
The slow dual update. The slow update takes stochastic gradient steps on $y$ using exponentially weighted averages of $q_i^2/\mu$. We also try a diagonal Newton-like step that uses the same averages. The barrier weight $\mu$ follows a geometric schedule that is triggered when the estimated gradient norm falls below a threshold. We want a two-timescale analysis. The bias from tracking a moving target should scale as (dual step size) × (thermostat correlation time). The variance should scale as $\tau/T$, where $\tau$ is the correlation time and $T$ is the averaging window; this is where the $O(1/\sqrt{t})$ central-limit behavior noted by Nava et al. enters. Together these give a rule tying step size to $\tau$. That rule is exactly where a flat-in-frequency $\tau$ pays off.
A safeguard for noisy gradients. Following Linear scaling electronic structure calculations and accurate statistical mechanics sampling with noisy forces, we monitor equipartition, meaning the measured kinetic temperature versus the target $\mu$. Violations indicate that $S(y)$ drifted faster than the sampler can follow, or is nearly singular. Either triggers a step-size cut.
Outputs. From the trajectory we read three quantities. The primal objective estimate is the average of $q^T L q/4$. Rounded cuts are the signs of decorrelated snapshots $q(t)$. A dual upper bound is $\mathbf{1}^T y$; we certify it post hoc with a single Lanczos check that $\lambda_{\min}(S(y)) > 0$.
Warm-starting. Warm-starting is natural: the state $(y, q, p, s)$ simply continues when the problem changes. We treat it as a secondary test, not the headline.
Baselines
Naive reference: exact interior point. The do-nothing reference is an exact interior-point solve on small Gset graphs, $n \le 3000$, where it fits in memory. It provides ground-truth SDP values against which we measure relative gap. On large instances the naive reference is simply "no answer."
SketchyCGAL. SketchyCGAL from Scalable Semidefinite Programming is the canonical linear-memory solver and the one whose Lanczos bottleneck we target. It has solved Max-Cut with 23 million vertices on laptop-class hardware.
USBS. USBS from Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching is the strongest existing competitor. It reports accurate solutions on all 10 MaxCut instances up to 3.7M nodes within 28 hours, where CGAL failed to reach target accuracy on 7 of 10 within 72 hours. It also reports a 10–25× GPU speedup in JAX and 20–100× warm-start speedups on SCAD-zbMATH.
Frank–Wolfe Max-Cut solver. The $O(n)$ Frank–Wolfe Max-Cut solver from A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP solved 1,000,000-node, 5,000,000-edge instances. It is the fairest memory-matched competitor because it also rounds from Gaussian samples. Per-instance Gset gap numbers for these methods were not in the file ("no reported result found on Lacuna" for specific Gset relative-gap values), so we will rerun all three ourselves.
Fair-comparison protocol. All methods run in the same JAX codebase on the same GPU. Each gets equal wall-clock and equal counts of sparse matrix–vector products, and the same hyperparameter-search budget of 20 configurations per method on G1 before freezing settings. We report time to reach a relative duality gap of $10^{-2}$ and $10^{-3}$, plus the rounded cut value. Beating USBS means reaching $10^{-2}$ relative gap in less wall-clock and fewer matrix–vector products on the large instances, with no worse rounded cuts. Matching it at $10^{-3}$ would already be notable given that we use no eigen-solver.
Ablations. The key ablation replaces the colored thermostat with white-noise Langevin at the same temperature, which has the identical stationary covariance, with friction tuned optimally for the band center. This isolates frequency-uniform damping as the sole difference. A second ablation replaces the thermostat with a deterministic estimator, described next.
Why not just…?
Why not just estimate $\mathrm{diag}(S^{-1})$ with Hutchinson probes and conjugate gradients? This is the real threat. Random probe vectors $z$ with $z \odot S^{-1}z$ averaged give an unbiased diagonal estimate. Conjugate gradients solves each $S^{-1}z$ in memory proportional to $n$, converging in $\sqrt{\kappa}$ products, where $\kappa$ is the condition number. Samples for rounding could then come from Krylov approximations of $S^{-1/2}g$. Nothing in the file shows the thermostat beats this.
The thermostat's argument is amortization. Each conjugate-gradient solve starts from scratch at every dual step and must converge. The thermostat instead carries its state across slowly changing $S(y)$, spending one product per step while continuously tracking the moving covariance. Its well-damped modes decorrelate within a few oscillation periods of the softest mode, which is $\sqrt{\kappa}$-like as well. We will run exactly this baseline, with warm-started conjugate gradients so it too reuses state, at matched product counts.
If it matches the thermostat end to end, we will report that the contribution is the barrier-dual-with-sampled-rounding formulation, not the physics. That outcome is still useful.
Why not just use white-noise Langevin, since the stationary covariance is identical? Correct: colored noise is not needed for correctness here. Its only claimed benefit is mixing speed on a wide spectrum. White noise with a single friction value over-damps soft modes or under-damps stiff ones, so its correlation time grows with the frequency ratio, which diverges as $\mu \to 0$. The colored-noise literature reports frequency-uniform efficient sampling Efficient stochastic thermostatting of path integral molecular dynamics, but only for physical spectra. Our first experiment measures correlation time versus $\kappa$ for both thermostats directly. If the gap is under 2× at realistic $\kappa$, we drop the generalized Langevin machinery and say so.
Why not just run a low-rank factorization with a quasi-Newton solver, or the Riemannian Langevin method? Factored methods are memory-light but non-convex and sensitive to rank choice, and Riemannian Langevin Algorithm for Solving Semidefinite Programs needs conservative steps with $\epsilon^{-4.5}$-type complexity. They also give no dual certificate, whereas our $\mathbf{1}^T y$ is a valid upper bound. We will include a Riemannian-trust-region low-rank factorization baseline on Gset for cut quality and time, since it may win on raw speed. Our claim is certified bounds in linear memory, not only good cuts.
Proposed Experiments
Step 1: mixing on a fixed matrix (go/no-go). We freeze $S(y)$ at several points along the central path for G1, G40 and random 3-regular graphs, with $\kappa$ from $10^2$ to $10^6$. We then measure the integrated autocorrelation time of the diagonal estimator for colored versus white thermostats, and the product count per effective sample against conjugate-gradient Hutchinson. This single plot decides whether the project continues.
Step 2: end-to-end on Gset. We run end to end on Gset ($n$ = 800–3000) against interior-point ground truth, SketchyCGAL, USBS, Frank–Wolfe and the low-rank factorization. We report relative gap, certified bound, and rounded cut versus products and wall-clock. We also check that the empirical gap tracks $n\mu$, which tests whether sampling bias is under control.
Step 3: scale. We move to DIMACS10 graphs and random regular graphs up to $10^6$–$10^7$ nodes, recording peak memory alongside time. The target is to stay within a small constant of the Frank–Wolfe solver's $O(n)$ footprint while beating USBS's time to $10^{-2}$ gap.
Step 4: warm start. We perturb edge weights of a solved Gset instance and compare the continued thermostat state against USBS warm starts.
The decisive checks are two.
- Step 1 must show at least a severalfold correlation-time advantage for colored noise at $\kappa \ge 10^4$.
- Step 3 must show fewer total matrix–vector products than both USBS and warm-started conjugate-gradient Hutchinson at equal certified gap.
Failing the first removes the thermostat. Failing the second removes the method.
References
- Scalable Semidefinite Programming
- Efficient stochastic thermostatting of path integral molecular dynamics
- Evaluating functions of positive-definite matrices using colored-noise thermostats
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching
- A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP
- Riemannian Langevin Algorithm for Solving Semidefinite Programs
- Nuclear Quantum Effects in Solids Using a Colored-Noise Thermostat
- Efficient multiple time scale molecular dynamics: Using colored noise thermostats to stabilize resonances
- Linear scaling electronic structure calculations and accurate statistical mechanics sampling with noisy forces