arXiv preprint ·
Subgaussian Vector Balancing by an Ising Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $σ\in \{\pm 1 \}^n$ so that the signed sum $\sum_j σ(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Sampling from the Sherrington-Kirkpatrick Model up to Criticality
From Global to Tail Convergence: Dynamics of $α$-Stable Score-Based Generative Models
The Singularity Has a Distribution: Exact Timing Laws and Detection Limits for a Stochastic Intelligence Explosion
Interior smoothness and zero-variance geometry for finite-maturity Heston American puts
$q_x$-Bass Martingales: Optimality, Existence and Convergence
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.