PaperlayerView exact revision on arXiv

Source-linked AI summary

Polytope Sampling at the Speed of Isoperimetry

Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang

arXiv:2610.23775v1cs.DSmath.OCmath.PR

TL;DR

Uniform sampling from a polytope is a fundamental algorithmic problem, and this paper develops faster samplers using functional stochastic localization. When m = O(n), its final sampler improves on existing runtimes by at least n^(2/3), without requiring a warm start.

  • Problem

    Uniform sampling from polytopes is a fundamental problem with applications across fields, and prior runtimes remain a target for algorithmic improvement.

    Source: §1 · p. 3, §1.1 · p. 4

  • Method

    The paper combines functional stochastic localization with functional cooling to provide the warm starts required by its sampling framework at polylogarithmic overhead.

    Source: §1.1 · p. 5, §4 · p. 31

  • Results

    At m = O(n), the final sampler improves upon all existing runtimes by a factor of at least n^(2/3), with no warmness assumption on the starting point.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The final sampler's iteration count nearly matches the Poincaré constant of the uniform distribution with respect to the log barrier.

    Source: §1.1 · p. 5

    The FSL approach does not directly extend to the commonly used Lee-Sidford barrier, which is not a log-Laplace transform.

    Source: §1.1 · p. 5

Abstract

from arXiv · show

We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \cdot \mathrm{poly}\log(\frac m \delta)$ iterations, each running in time $O(mn^{\omega - 1})$, to return a sample within total variation distance $\delta$ to the uniform distribution. When $m =O(n)$ and $\delta = \mathrm{poly}(\frac 1 n)$, our runtime improves upon all prior works by an $\Omega(n^{2/3})$ factor. Our sampler is based on the recent \emph{functional stochastic localization} framework of [GST26], and achieves an iteration count nearly matching the Poincar\'e constant of the uniform distribution with respect to the logarithmic barrier.

1 Introduction · 2 Preliminaries

This section introduces the problem of uniform sampling from polytopes and develops a geometry-aware sampler based on functional stochastic localization. It also establishes preliminaries on exponential tilting and how convolution relates to log-Laplace transforms.

1.1 Our results

  • For m=O(n), the final sampler improves on all existing runtimes by at least n^2/3, and neither new algorithm requires a warm start.The basic sampler improves runtimes by at least n^1/6 even against a warm-started alternative.Source: §1.1 · p. 4

Functional stochastic localization.

  • The algorithms use functional stochastic localization [GST26], with the polytope log barrier as a log-Laplace transform and an exact forward-oracle implementation.The forward oracle simulates draws from the corresponding conditional distribution.Source: §1.1 · p. 4, Functional stochastic localization · p. 7

1.2 Our techniques

  • For Part I, a backwards oracle tolerates τ=eO(√n) by showing conditional concentration near its mode and using a Gaussian proposal with a high-accuracy sampler.The concentration result applies when τ ≥ √n · polylog(n).Source: Functional stochastic localization · pp. 7–8

Functional stochastic localization.

  • Functional cooling extends [KV24] to provide χ2-warm starts, yielding an eO(m√n)-iteration polytope sampler for Theorem 1.The cooling schedule uses successive distributions that are O(1) warm starts for one another in χ2 divergence.Source: Functional stochastic localization · p. 8

1.2 Our techniques

  • The second backwards oracle tolerates τ=O(log(m/δ)) by combining average-case stable-region bounds with a weak Poincaré analysis.It combines this oracle with the cooling framework to obtain Theorem 2.Source: Functional stochastic localization · pp. 8–9

2.1 General notation

  • Tilting an integrable nonnegative function f by x gives a density proportional to exp(⟨x, ·⟩)f, with normalization exp(−ψ) when ψ = φ♯.The notation T_x f denotes this tilted density.Source: §2.1 · p. 10
  • For densities μ = exp(−φ) and ν = exp(−ξ), the log-Laplace transform of their convolution satisfies χ♯ = φ♯ + ξ♯, where χ = −log(μ ∗ ν) [GST26].Source: §2.1 · p. 10
  • For the potential φ∗τ of a τ-fold convolution, the transform is (φ∗τ)♯ = τφ♯; linear tilts also commute with convolution.Source: §2.1 · p. 10

5 end · 6 Return: xK · 5 Return: y

The section applies functional stochastic localization to polytope sampling with the logarithmic barrier, implements the forward sampling step, and establishes a Poincaré inequality for the uniform measure. The key ingredients are the barrier’s log-Laplace-transform representation and an isoperimetric comparison of metrics.

2.2 Functional stochastic localization

  • Functional stochastic localization, introduced by [GST26] to analyze the non-Euclidean proximal sampler in [GLL+25, Algorithm 1], provides a mixing guarantee when the target satisfies an appropriate functional Poincaré inequality.The paper’s sampler builds on this framework.Source: §2.2 · p. 11
  • The proximal sampler uses Gibbs sampling over a joint density on (x, y) whose x-marginal is the target distribution π.The passage identifies πX as exactly π.Source: §2.2 · p. 11

2.3 Specialization to logarithmic barrier

  • For the log barrier, ∇ψ maps the polytope bijectively to its dual set, and the corresponding strictly convex objective has a unique minimizer.The minimizer satisfies y = τA⊤s(x)−1.Source: §2.3 · p. 12
  • The logarithmic barrier ψ is represented as a log-Laplace transform, enabling its use in the functional stochastic localization framework.The construction defines component measures on rays generated by the constraint vectors and establishes ψ = φ♯.Source: §2.3 · p. 13

5 Return: y

  • O(m(n + τ)) time suffices to sample y = A⊤γ, where γ sums τ independent Exp(s(x)) draws and y has the forward-step distribution.The algorithm computes the slacks, draws the exponential variables, sums them, and applies A⊤.Source: §5 · pp. 13–14

2.4 Isoperimetry

  • The measure π satisfies a 1/(16m)-ψ-Poincaré inequality; for all x,x′∈X, Fact 4 gives mψ(x,x′) ≤ √m·mH(x,x′), while Cheeger’s inequality gives λψ(π) ≥ 1/4 hψ(π)^2.Source: §2.4 · p. 15
  • The Poincaré conclusion also holds for any log-concave measure supported on the polytope, extending the result beyond the uniform measure.This extension is relevant to the paper’s cooling scheme, which multiplies the uniform measure by a log-concave function.Source: §2.4 · p. 15

Polytope Sampling in eO(m√n) Iterations · 3 Backwards Oracle Implementation via Smoothing

This section develops a smoothed backwards-oracle sampler, using slack concentration and Newton-based mode approximation to support a well-conditioned potential with small total variation error.

3 Backwards Oracle Implementation via Smoothing

  • The implementation smooths the backwards-step potential in a high-probability region and combines the section’s components into a backwards-step procedure.The section targets implementation of the backwards step up to small total variation error.Source: §3 · p. 16

3.1 Setup

  • The setup fixes y and τ, defines coordinates relative to w (typically an approximate mode), and reparameterizes the backwards conditional potential.Source: §3.1 · pp. 16–17

3.2 Concentration

  • The backwards conditional concentrates in a constant-width relative-slack box around its mode, using MGF-based slack concentration and score and virial identities to bound expected slacks.Source: §3.2 · p. 18

3.3 Mode finding

  • A χ² warm start followed by the forwards step yields a high-probability ℓ4 bound on relative slacks, which the section uses to analyze Newton’s method.The Newton analysis assumes an initial ℓ4 bound on relative slacks.Source: §3.3 · pp. 23–24
  • Newton’s method yields a high-accuracy approximation to the objective minimizer, with the stated runtime and accuracy guarantee.The proof uses a first step into a Dikin ellipse followed by standard Newton convergence results.Source: §3.3 · pp. 25–26

3.4 Smoothing

  • The smoothed potential has global regularity, induces a measure within δ total variation distance of the true backwards conditional, and has a gradient evaluable in O(mn) time.The section motivates smoothing by its well-conditioning and Lipschitz Hessian, which make high-accuracy sampling methods applicable.Source: §3.4 · p. 26
  • The measure ν̄ assigns substantial mass to the pushforward of B(w, 1/4); for the chosen τ, a union bound gives ∥r(Z) − E[r(Z)]∥∞ ≤ 1/8 with probability ≥ 1−δ.Source: §3.4 · p. 29

3.5 Putting things together

  • The backwards oracle applies the sampler of [ZAC26] to the smoothed measure from Lemma 14.The section states a high-probability output guarantee and an implementation-time bound for Algorithm 3.Source: §3.5 · p. 30

5 end

The proof establishes the sampler’s total-variation accuracy by combining two δ/2 approximations, and bounds the cost of key computations by O(mn^(ω−1)).

5 end

  • The output is within total variation distance δ of ν_w, combining two δ/2 approximations and undoing the transformation in Line 8.The argument conditions on Lemma 12 succeeding and uses Proposition 3 to sample from the approximating distribution.Source: §5 · p. 31
  • When Δ=O(1), computing V(w) and h(w) costs O(mn^(ω−1)); the remaining cost includes an O(mn)-time implementation of ∇¯F.The runtime discussion combines Proposition 3 with the gradient implementation from Lemma 14.Source: §5 · p. 31

4 Functional Cooling

The section develops functional cooling to provide χ2 warm starts at polylogarithmic overhead. It builds on [KV24] and couples its cooling strategy with an FSL-based implementation.

4 Functional Cooling

  • Cooling uses a sequence of distributions ending at the target, with each stage serving as a warm start for the next while keeping total sampling cost near direct target sampling.Prior schemes multiply the target distribution by Gaussian factors; early stages can be cheaper because large Gaussian components improve isoperimetry.Source: §4 · p. 31
  • Coupling the [KV24] cooling strategy with an FSL-based implementation yields only polylogarithmic overhead in the overall iteration complexity.The framework builds on [KV24], which extended Gaussian cooling to self-concordant barriers compatible with the polytope log barrier.Source: §4 · pp. 31–32

4.1 χ2-to-TV oracle implementation

  • A (3, δ)-χ2-to-TV oracle samples each cooled measure π_t from a starting point with χ2 divergence at most 3, returning a sample within TV distance δ.The oracle is implemented in Algorithm 4, which follows FSL but uses an approximate backwards step.Source: §4.1 · p. 33

6 end · 7 Return: xK

Algorithm 4 provides a χ2-to-TV oracle for πt, with its correctness established by controlling the error from approximate backward steps. Algorithm 5 uses this oracle in a four-phase cooling framework, beginning with a Gaussian draw and then calling the oracle at different inverse temperatures.

7 Return: xK

  • If two Markov kernels agree on a high-probability event under μ, applying the approximate kernel instead of the exact one incurs small total variation error.In the application, the kernels are the exact and approximate backward steps, and the event is supplied by Corollary 2.Source: §7 · p. 33
  • (3, δ)-χ2-to-TV oracle: Algorithm 4 returns an oracle for πt, with runtime established from Propositions 2 and 4 and its iteration count.The stated runtime expression is not fully visible in the supplied passage.Source: §7 · p. 34
  • The forward step is implemented exactly, while the ideal and implemented backward steps define the kernels compared in the correctness argument.The analysis uses joint randomness of the forward-step input (x, y).Source: §7 · p. 34
  • δ/(4K) bounds the failure probability for each analyzed step, and iterating the resulting bound gives TV(μ̃K, μK) ≤ δ/2.The per-step event is obtained by applying Corollary 2, followed by the kernel comparison in Lemma 19.Source: §7 · pp. 34–35
  • The ideal LLTProx kernel P leaves πt stationary, and πt satisfies an αt-ψ-PI with αt := max{t, 1/(16m)}.The two terms in the maximum follow respectively from Fact 2 and Lemma 3 via Remark 2.Source: §7 · pp. 34–35

4.2 Cooling framework

  • Algorithm 5 has four phases: it initializes with an appropriate Gaussian draw, then iteratively calls the Lemma 20 oracle at different inverse temperatures t.The framework builds on the χ2-to-TV oracle implementation in Lemma 20.Source: §4.2 · p. 35

7 end … 18 Return: x

Algorithm 5’s successive oracle calls maintain χ2 warmness and yield a sample within total variation distance δ of π; the proof also bounds its runtime under the stated initialization conditions.

18 Return: x

  • The analytic-center initialization uses Newton steps costing O(mn^(ω−1)) each, with O(log log 1/∆) additional steps to reach decrement ∆.The argument first uses short-step path following, then applies Newton’s method.Source: §18 · p. 36
  • Corollary 3 combines the bounds for Phases 2–4 to give their total runtime and limits the number of LLTProxHMC calls.The supplied passage does not show the runtime expression or call-count value.Source: §18 · p. 38
  • The terminal cooling distribution satisfies χ2(π_t∥π) ≤ 3.The proof establishes H(t) ≤ mt log 4 ≤ log 4 to obtain this bound.Source: §18 · p. 41
  • TV(Law(x), π) ≤ δ for Algorithm 5’s output x.The proof obtains this by propagating warm starts along the cooling path and bounding the total accumulated error by δ.Source: §18 · pp. 41–42
  • The Phase 1 output admits a measure µ with χ2(µ∥π_t1) ≤ 3, providing the warm start used to begin the cooling path.The proof also bounds the initial output’s total variation distance from µ by δ/2.Source: §18 · p. 42

4.3 Proof of Theorem 1

  • Algorithm 5 using Algorithm 4 as O returns x with TV(Law(x), π) ≤ δ when given the stated feasible-point and ball-containment inputs.For known 0 < r < R and B2(x0, r) ⊂ X ⊂ B2(x0, R), the theorem also gives a runtime bound, though its expression is not visible in the supplied passage.Source: §4.3 · p. 42

Polytope Sampling in eO(m) Iterations · 5 Backwards Oracle Implementation via Dual Conditioning

A backwards oracle based on dual conditioning uses a simple whitened Metropolized random walk and controls its contraction defect through an average concentration bound, rather than a uniform bound over backwards conditional distributions.

Polytope Sampling in eO(m) Iterations

  • The dual-conditioning approach implements a (3, δ)-χ2-to-TV oracle at step size τ = O(log(m/δ)).It replaces the earlier oracle implementation described as Lemma 20.Source: §5 · p. 43

5 Backwards Oracle Implementation via Dual Conditioning

  • Instead of bounding all backwards conditional distributions uniformly, the method allows a weak χ2 contraction with a defect proportional to the dual-unstable region’s size.The region’s size varies across backwards conditionals but is small on average, which suffices for the final TV guarantee.Source: §5 · p. 43
  • The section’s concentration result, instancewise random-walk guarantee, and approximate oracle implementation culminate in a proof of Theorem 2.The described progression uses Lemma 30 to control the average defect.Source: §5 · p. 43

5.1 Setup

  • A backwards-conditional draw falls in Bτ(γ, 1/4) with high probability on average over γ ∼ πΓ_t,τ.This concentration fact (Lemma 30) supports control of the average defect.Source: §5.1 · p. 44

5.2 Metropolized random walk

  • The approximate backwards oracle has an instancewise guarantee depending on the forwards draw γ, with its defect governed by the backwards measure of Bτ(γ, 1/4).The guarantee is used to compare the defective contraction with the ideal outer-loop proximal-sampler iteration.Source: §5.2 · p. 44
  • The backwards step uses a simple Metropolized random walk in coordinates whitened with respect to Hγ.Algorithm 6 is 1/2-lazy: from any x ∈ X, its Markov kernel assigns at least half its mass to x.Source: §5.2 · p. 44

9 end · 10 Return: xN

The section establishes an instancewise defective χ²-convergence guarantee and runtime bound for Algorithm 6, then uses that analysis in an improved χ²-to-TV oracle that works at τ = O(log(m/δ)).

10 Return: xN

  • For symmetric proposals, Proposition 6 bounds Metropolized-kernel TV distance by proposal TV distance plus one minus the smaller acceptance probability.The bound is TV(M(z, ·), M(w, ·)) ≤ TV(P(z, ·), P(w, ·)) + 1 − min{A(z), A(w)}.Source: §10 · p. 45
  • Proposition 7 [DCWY19] uses local TV overlap to lower-bound conductance when the conditional target on a convex set is strongly log-concave.Its condition requires overlap for pairs of points within distance Δ.Source: §10 · pp. 45–46
  • Lemma 31 combines weak-Poincaré ingredients from to bound variance by an energy term and a defect term proportional to δ times oscillation squared.The displayed bound is Var_µ[f] ≤ 2/((1 − ε)^2 b^2) E_Kε(f, f) + 2δ osc(f)^2.Source: §10 · p. 46
  • Combining three helper results yields a defective χ²-convergence guarantee for Algorithm 6 under its stated inputs.The proof applies the weak-Poincaré result after deriving local overlap and conductance bounds for the algorithm’s kernel.Source: §10 · pp. 47, 49
  • The potential is well-conditioned on a large region; for ∆:=1/(64√n) and ∥z−w∥₂≤∆, the argument combines preceding inequalities with Proposition 6.The passage also invokes Pinsker’s inequality and the KL divergence between identity-covariance Gaussians with different means.Source: §10 · pp. 47–48
  • Batching n iterations allows Algorithm 6’s loop work to be implemented in O(mn^(ω−1)) time after precomputation, with O(m) work per iteration.The batch precomputation takes O(mn^(ω−1)) time, and the n loop iterations then take O(mn) total.Source: §10 · p. 49

5.3 Comparison to the ideal proximal sampler

  • Algorithm 7 is an improved χ²-to-TV oracle that uses Algorithm 6 for O(nτ) steps as its approximate backwards oracle; its analysis compares it with ideal Algorithm 1.Its analysis combines Lemma 32’s instancewise defectiveness guarantee for Algorithm 6 with Lemma 30’s result that defectiveness is small on average.Source: §5.3 · p. 49

7 end · 8 Return: xK · AI Disclosure

The closing proof establishes total-variation guarantees for the sampler and its oracle, while the AI disclosure describes AI’s role in developing ideas and the authors’ responsibility for the manuscript.

8 Return: xK

  • The inexact proximal sampler’s overall Markov operator is eP = F eB, using the inexact backward step in place of the exact one.The passage identifies F as the exact forward-step operator and eB as the inexact backward-step operator.Source: §8 · p. 50
  • Algorithm 7 is a (3, δ)-χ2-to-TV oracle for πt and has a stated runtime.The runtime expression is missing from the supplied text.Source: §8 · p. 51

5.4 Proof of Theorem 2

  • The sampler outputs x with TV(Law(x), π) ≤ δ when supplied a point with known inner and outer ball bounds.The passage also states that the algorithm runs in time, but the runtime expression is missing from the supplied text.Source: §5.4 · p. 52

AI Disclosure

  • The authors identify the logarithmic barrier as an LLT for [GST26], mode-centered backward oracles motivated by [FYC23], and functional cooling based on [KV24].ChatGPT 5.6 Pro explored backward-oracle implementation strategies and materially affected Sections 3.2 and 3.4, including mean-relative-slack proofs and globally smoothed-measure analysis.Source: AI Disclosure · p. 53
  • GPT 6 Pro produced essentially the Part II ideas after observing compatibility between analyses and the backward oracle’s properties.The authors primarily streamlined the presentation and unified it with Part I, splitting the paper to reflect the two backward-oracle implementations and idea provenance.Source: AI Disclosure · p. 53
  • The authors wrote the manuscript solely and take full responsibility for the organization and presentation of all results.Source: AI Disclosure · p. 53

Related papers

Loading 2610.23775v1…