PaperlayerView exact revision on arXiv

Source-linked AI summary

Subgaussian Vector Balancing by an Ising Model

Heng Guo, Daniel A. Spielman, Xinyuan Zhang

arXiv:2610.18639v1cs.DSmath.PR

TL;DR

Vector balancing has a sampling formulation with a best-known 1-subgaussian guarantee, and the paper provides a closed-form Ising distribution for achieving it. Its Glauber dynamics mix rapidly when vector norms are inverse-polynomially below 1, with related mixing bounds for other spin systems.

  • Problem

    The sampling formulation of vector balancing calls for a zero-mean signed sum with a subgaussian guarantee, and the Gram-Schmidt Walk achieves the best-possible constant 1.

    Source: §1 · p. 2

  • Method

    The paper constructs a closed-form Ising distribution on sign vectors and analyzes its Glauber dynamics, including under external fields.

    Source: §1 · p. 1, §6.1 · p. 7, §7 · p. 8

  • Results

    The signed sum is 1-subgaussian for vectors of norm less than 1, and Glauber dynamics mix rapidly when their norms are inverse-polynomially below 1.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The approach also provides rapid-mixing bounds for anti-ferromagnetic spin systems on complete graphs with strictly positive interaction-matrix diagonals.

    Source: §1 · p. 2

    Efficient sampling is not established when input vectors have norm 1 or are very close to 1; rescaling gives an at-most (1 + ε)-subgaussian guarantee.

    Source: §1 · p. 2

Abstract

from arXiv · show

We show that the guaranties of the Gram-Schmidt Walk Algorithm of Bansal, Dadush, Garg, and Lovett can be achieved by an Ising model. Given vectors $v_1, \ldots, v_n$ of norm less than 1, we give a closed form for a centrally symmetric distribution on a vector $\sigma \in \{\pm 1 \}^n$ so that the signed sum $\sum_j \sigma(j) v_j$ is $1$-subgaussian. We show that the Glauber dynamics for this model mix rapidly provided that the norms of the input vectors are bounded below 1 by an inverse-polynomial. The proofs employ the theory of Lorentzian polynomials, and we use these techniques to show fast mixing bounds for other spin systems.

1. Introduction

The paper gives a closed-form Ising distribution whose signed vector sum is 1-subgaussian, and proves rapid Glauber mixing when input norms stay inverse-polynomially below 1. It also extends the mixing analysis to other spin systems.

1. Introduction

  • The authors present the distribution as a simple, closed-form alternative to modifying the Gram-Schmidt Walk, and describe it as the first closed-form C-subgaussian sampler to their knowledge.They also identify randomized controlled trials as a potential use for better-understood samplers.Source: §1 · pp. 1–2
  • For vectors of norm less than 1, sampling signs proportional to the Ising weights makes their signed sum 1-subgaussian, matching the best guarantee described for the Gram-Schmidt Walk.The guarantee also holds under external fields after recentering the sum.Source: §1 · pp. 1–2
  • Glauber dynamics mix rapidly when input-vector norms are bounded inverse-polynomially away from 1.The paper gives spectral-gap and mixing-time bounds for this regime.Source: §1 · p. 2
  • The approach yields rapid-mixing bounds for anti-ferromagnetic spin systems on complete graphs with strictly positive interaction-matrix diagonals, and extends the Potts parameter range.The Potts results improve a spectral-gap lower bound from Chen and Wang [CW26].Source: §1 · p. 2
  • For input vectors with inner product 1, the distribution can be interpreted by grouping identical or opposite vectors and constraining each class’s signed sum according to its size.Even-sized classes have sum zero; odd-sized classes have sum equal to one class vector or its opposite.Source: §1 · p. 2
  • The sampling guarantee is not efficiently available when vectors have norm 1 or are very close to 1; rescaling them by 1 + ε yields an at-most (1 + ε)-subgaussian signed sum.The rescaled vectors can be sampled using the theorem’s distribution.Source: §1 · p. 2

2. AI Methodology

The authors describe a process in which interactions with an LLM contributed to proofs of the paper’s subgaussianity and mixing conjectures. They say they later refined the proofs through further reasoning and LLM use.

2. AI Methodology

  • The authors report using black-box optimization and then an LLM to investigate their conjectures about subgaussianity and rapid mixing.Their initial prompt was modeled on one used for the Cycle Double-Cover Conjecture.Source: §2 · p. 2
  • The first LLM interaction affirmed the 1-subgaussian conjecture using Alexandrov-Fenchel and established an n^O(1/α0) mixing-time bound via a local-to-global argument [AL20].The authors then asked the LLM to improve the mixing bound, leading to Theorem 2.Source: §2 · p. 2
  • After recognizing that Theorem 2 also gives mixing criteria for settings in Section 8, the authors substantially refined the proofs through reasoning and LLM use.Source: §2 · p. 3

3. Preliminaries

The preliminaries define subgaussian random vectors and the Markov-chain quantities used to analyze Glauber dynamics. They also specify the single-coordinate update rule for that dynamics.

3. Preliminaries

  • A random vector is C-subgaussian when its moment-generating function satisfies the stated bound for every vector θ.Source: §3 · p. 3
  • For a reversible finite Markov chain, the spectral gap is one minus its second-largest eigenvalue, and mixing time measures convergence to stationarity in total variation.The passage defines mixing time for a specified error ε.Source: §3 · p. 3
  • Glauber dynamics selects a coordinate uniformly and resamples it according to its conditional distribution given the other coordinates.This chain is reversible with respect to the target distribution.Source: §3 · p. 3

4. Motivating the distribution

The authors motivate their distribution through small computational experiments and several desired behaviors. These include favorable covariance for two unit vectors, Gaussian-like behavior in one dimension, and limited interaction between orthogonal vectors.

4. Motivating the distribution

  • The authors enumerated candidate distributions with desired properties and used small experiments to eliminate candidates that failed to produce 1-subgaussian sums.They say this process preceded useful LLMs.Source: §4 · p. 3
  • For two unit input vectors, the distribution minimizes the operator norm of the resulting covariance matrix, a behavior the authors sought to preserve.Source: §4 · p. 3
  • With many identical small one-dimensional vectors, the induced distribution approaches a discrete Gaussian as n grows.The probability of sum kε is approximately proportional to exp(−(kε)^2/2) for k equivalent to n modulo 2.Source: §4 · p. 3
  • The authors sought a distribution in which entirely orthogonal vector sets do not interact and orthogonal pairs do not interact directly.Source: §4 · p. 3

5. A discrete Alexandrov-Fenchel inequality and Lorentzian Polynomials

The section develops a discrete Alexandrov–Fenchel inequality through Lorentzian matrices and polynomials, a tool used in the paper’s later analysis. It defines the relevant matrix condition and applies the inequality to the Lorentz matrix of the input vectors.

5. A discrete Alexandrov-Fenchel inequality and Lorentzian Polynomials

  • The authors identify the use of Lee, Oh, and Seo’s discrete Alexandrov–Fenchel inequality [LOS25] via Lorentzian polynomials as a novel part of their proof.Lorentzian polynomials had already been used to analyze Markov-chain mixing rates.Source: §5 · p. 3
  • A symmetric matrix is Lorentzian when its entries are non-negative and it has at most one positive eigenvalue.The paper defines the Lorentz matrix by A(c, c′) = 1 − ⟨v_c, v_c′⟩.Source: §5 · pp. 3–4
  • Theorem 3 gives a multiplicative inequality for the polarized function V_A, relating evaluations at x_1, x_2 to evaluations with repeated arguments.Its proof route uses the polarization of a Lorentzian polynomial and results of Brändén and Huh.Source: §5 · p. 4
  • If every vector has norm at most one, its Lorentz matrix is Lorentzian.The proof uses non-negativity of the entries and the fact that the associated quadratic form is non-positive on vectors orthogonal to the all-ones vector.Source: §5 · p. 4

6. Subgaussian concentration

The authors use Lorentzian inequalities to control the signed sum under the Ising distribution, including distributions tilted by external fields. For input vectors of norm less than one, the resulting signed sum is 1-subgaussian.

6. Subgaussian concentration

  • To apply the Lorentzian inequality, the proof indexes each input vector and its opposite and constructs selection vectors for the signed-sum distribution.It introduces additional coordinates for the zero vector and a scaled test vector before applying the inequality.Source: §6 · pp. 4–5
  • An external field h∈R^n tilts the distribution, yielding weights w_h used to analyze the signed sum.The proof expresses the normalizing partition function through the Lorentzian-polynomial framework.Source: §6 · pp. 4–5

6.1. Subgaussian.

  • The proof bounds the covariance of the signed sum for every external field, then integrates along a path of external fields to establish subgaussian concentration.The distribution tilted by h is normalized by its partition function Z(h), and F(h) is defined as ln Z(h).Source: §6 · p. 5, §6.1 · p. 6
  • For input vectors of norm less than one, the signed sum under the distribution proportional to w_h(σ) is 1-subgaussian for every external field h.The theorem strengthens the zero-field result; at h = 0, E_0σ = 0.Source: §6.1 · p. 7

7. Glauber dynamics

The section analyzes Glauber dynamics for the Ising distribution through a Poincaré inequality derived from the Lorentzian inequality. Its spectral-gap bound depends on how far the input-vector norms lie below one.

7. Glauber dynamics

  • Glauber dynamics resamples one coordinate from its conditional distribution while keeping the other coordinates fixed.The coordinate-resampling operators are used in the variance analysis.Source: §7 · p. 8
  • The proof reduces variance control to functions represented using vectors of norm at most √α0, then applies the Lorentzian-based inequality.The argument augments vectors to transfer a bound for inner products with σ to the augmented-vector setting.Source: §7 · p. 9
  • The proof first employs a sum over S = {0, ±1}^n and gives coefficients, then shows it can be replaced by a sum over S = {0, ±δ}^n for any δ > 0.For Lemma 8, it sets δ = α0/√n and S = {0, ±δ}^n.Source: §7 · pp. 11, 13
  • The Glauber dynamics has spectral gap at least α0/n when every input vector has squared norm at most 1 − α0.The paper identifies approximate tensorization of variance as equivalent to the Poincaré inequality used for the gap bound.Source: §7 · pp. 8, 13

8. General rapid mixing results

The section extends Lorentzian-polynomial techniques to obtain Glauber-dynamics spectral-gap bounds for complete-graph and general-graph spin systems. The bounds cover anti-ferromagnetic Potts models and, on line graphs, apply to arbitrary numbers of spins without bounded-degree or external-field restrictions.

Complete-graph spin systems

  • The generalization begins with uniform interactions on a complete graph and then applies the resulting machinery to more general spin systems.The proof of the complete-graph result follows the strategy of Theorem 2 and uses an analogue of Lemma 10.Source: §8 · p. 14
  • When every diagonal entry of A is positive, the complete-graph Glauber dynamics has spectral gap Ω_A(1/n).Theorem 14 establishes the bound when c_A > 0; positive diagonal entries ensure this condition.Source: §8 · p. 14

General graphs

  • For general graphs, c_G,A > 0 gives a spectral-gap bound in terms of the interaction matrix and adjacency-matrix eigenvalues.The bound uses λ_max for the ferromagnetic part and λ_min for the anti-ferromagnetic part; the graph model is reduced to a complete-graph setting by enlarging the spin set and choosing external fields.Source: §8 · pp. 17–18
  • For the general-graph reduction, the auxiliary complete-graph model preserves configuration weights while restricting each vertex to its original spins.The enlarged interaction matrix is chosen to satisfy Theorem 14’s hypotheses.Source: §8 · pp. 17–18
  • On line graphs, the condition c_A > 1/2 yields an Ω(1/n) gap bound, covering any q ≥ 2 without bounded degree and allowing arbitrary external fields.Earlier results cited for comparison cover anti-ferromagnetic 2-spin systems on bounded-degree line graphs [DHJM21].Source: §8 · p. 18

Potts model

  • For the anti-ferromagnetic q-state Potts model, the derived bound extends the parameter range and improves the spectral-gap lower bound of Chen and Wang [CW26, Corollary 6.7].The result holds whenever the stated expression is positive.Source: §8 · p. 18
Loading 2610.18639v1…