PaperlayerView exact revision on arXiv

Source-linked AI summary

A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra

Zhao Song, Lichen Zhang

arXiv:2608.25273v1cs.DSstat.ML

TL;DR

Metropolis-adjusted Dikin walks require controlling both the proposal determinant and reverse quadratic form at random endpoints. The paper keeps the complete logarithmic acceptance ratio intact, obtaining dimension-square mixing bounds for polytopes and leverage-scaled bounds for spectrahedra.

  • Problem

    Metropolis filtering requires controlling the proposal determinant and reverse local quadratic form at the random endpoint, not only local-ellipsoid containment.

    Source: §1 · p. 2

  • Method

    The analysis keeps the complete logarithmic Metropolis ratio intact so uncentered terms cancel, leaving centered fluctuations controlled by second-order tools.

    Source: §1 · p. 2

  • Results

    eO((d^2 + dL^2R^2) log(w/δ)) steps suffice for the polytope walk, while the spectrahedral walk requires eO((ψ*nd + dL^2R^2) log(w/δ)) steps.

    Source: §2.1 · p. 7, §2.2 · p. 7

  • Takeaways & Limitations

    The shared acceptance-to-mixing analysis directly covers Lee–Sidford geometry on polytopes and log-det geometry on spectrahedra.

    Source: §1 · p. 2

    The arrow-spectrum obstruction does not establish a pointwise if-and-only-if statement for all spectrahedra or a mixing-time lower bound.

    Source: §5.7 · p. 47

Abstract

from arXiv · show

We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together. Their leading uncentered terms cancel in the complete logarithmic acceptance ratio, leaving centered fluctuations that can be controlled with second-order tools. For a polytope given by $n$ inequalities and a convex $L$-Lipschitz potential, this yields warm-start mixing in $\widetilde O((d^{2}+dL^{2}R^{2})\log(w/δ))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((ψ^\star nd+dL^{2}R^{2})\log(w/δ))$ steps, where $ψ^\star$ measures matrix leverage. The two analyses share an acceptance-to-mixing reduction. A proposal-comparison argument transfers the polytope bound to an appropriately padded $O(1/d)$-accurate metric computed from high-precision Lewis weights. For spectrahedra, given $\widehatψ\geψ^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $ψ^\star$ replaced by $\widehatψ$ in the mixing bound.

1 Introduction

The paper develops a direct analysis of Metropolis-adjusted Dikin walks by preserving determinant and reverse-quadratic terms so their leading contributions cancel. It obtains dimension-square polytope and leverage-dependent spectrahedral mixing guarantees, transfers them to exact-arithmetic implementations, and identifies acceptance limitations and prior proof gaps.

1 Introduction

  • Keeping the complete logarithmic Metropolis ratio reveals determinant–quadratic cancellation, leaving centered endpoint fluctuations controlled by Gaussian integration by parts and second-order concentration.This supplies a shared acceptance-to-mixing analysis for Lee–Sidford polytopes and log-det spectrahedra.Source: §1 · p. 2

1.1 Our results

  • The main results give warm-start mixing in Õ(d^2 + dL^2R^2) for polytopes and Õ(ψ*nd + dL^2R^2) for spectrahedra.The polytope setting uses exact Lewis weights and the Lee–Sidford metric; the spectrahedral rate depends on matrix leverage through ψ*.Source: §1.1 · pp. 2–3
  • For spectrahedra, κ = 1 can yield exponentially small center acceptance on an arrow spectrahedron when ψ(0) = Θ(d), which is an acceptance obstruction rather than a mixing lower bound.The implementation bounds are arithmetic-operation bounds and exclude finite-bit conditioning, rounded Gaussian sampling, inexact decisions, and warm-start construction.Source: §1.1 · pp. 3–4
  • Exact-arithmetic implementations preserve the corresponding mixing bounds using padded high-precision Lewis weights for polytopes and direct-or-two-seed TensorSRHT sketches for spectrahedra.The proposal-comparison transfer avoids differentiating the approximate metric, while the spectrahedral construction is exactly reversible.Source: §1.1 · p. 3

1.2 Prior work and scope

  • The polytope proof repairs the reverse-ellipsoid difficulty without average self-concordance, while explicitly acknowledging prior proof gaps and making no priority claim over the earlier spectrahedral theorem.The spectrahedral theorem is complete and leverage-dependent but is not uniformly stronger when ψ* > 1.Source: §1.2 · p. 4

2 Technical overview

The technical overview separates Lewis-weight and noncommutative log-det proof mechanisms, then explains how approximate metrics yield implementable versions of both walks. Both analyses establish acceptance before transferring local overlap to conductance and warm-start mixing.

2 Technical overview

  • Sections 2.1 and 2.2 develop separate Lewis-weight and noncommutative log-det arguments, while Section 2.3 transfers both analyses to approximate metrics.Source: §2 · pp. 4–5

2.1 Proof overview for Theorem 1.1

  • The polytope proof cancels the determinant’s linear term against the Gaussian mean, controls centered fluctuations through Lewis-weight stability, and yields eO((d^2 + dL^2R^2) log(w/δ)) steps.Leverage-sensitive rowwise contraction prevents dependence on the number of inequalities; overlap, isoperimetry, and Cheeger arguments complete the mixing bound.Source: §2.1 · pp. 5–7

2.2 Proof overview for Theorem 1.2

  • The spectrahedral proof reduces acceptance fluctuations to a centered noncommutative trace polynomial, controls them with leverage-sensitive contractions, and yields eO((ψ*nd + dL^2R^2) log(w/δ)) steps.An arrow-spectrahedron example has ψ(0) = Θ(d) and exponentially small central acceptance without leverage scaling, but makes no mixing lower-bound claim.Source: §2.2 · p. 7

2.3 From exact metrics to implementable kernels

  • Approximate implementations preserve reversibility and transfer acceptance, proposal overlap, conductance, and mixing bounds without differentiating the approximate metric.Polytopes use padded O(1/d)-accurate Lewis weights; spectrahedra use direct or TensorSRHT constructions with fresh endpoint sketches and pointwise success guarantees.Source: §2.3 · p. 9

3 Preliminaries

This section develops the polytope and spectrahedral preliminaries and analytic tools used later. It establishes notation, Lewis-weight and leverage calculus, metric-comparison and exact-metric log-det inputs, and the isoperimetric and Cheeger tools for mixing guarantees.

3.1 Notation

  • Notation defines the matrix spaces, norms, diagonal and Hadamard operations, and asymptotic conventions used throughout.Source: §3.1 · p. 9

3.2 Polytope, slacks, and Lewis weights

  • The polytope is K = {z ∈ R^d : Az ≥ b}, with positive interior slacks, bounded full-dimensional geometry, and uniquely defined ℓ_p-Lewis weights.Lewis weights exist uniquely for p ≥ 2; their smooth row-rescaling behavior is imported from,, and [LS19].Source: §3.2 · p. 10

3.3 First-derivative Lewis calculus

  • The first-derivative Lewis calculus provides smooth weight derivatives and operator bounds, including ∥R_z∥op ≤ p/2 and 0 ⪯ N_z ⪯ pI.The derivative formula is Lemma 3.1 from [LS19], with the spatial specialization fixing the sign and factor two.Source: §3.3 · p. 11

3.4 Analytic, metric, and geometric inputs

  • The analytic and geometric inputs combine Gaussian concentration, strong self-concordance of the scaled Lee–Sidford metric, cross-ratio isoperimetry, and Cheeger’s conductance-to-gap inequality.Cross-ratio isoperimetry applies to e^−f 1_K for convex f, while Cheeger’s inequality applies to the lazy reversible chain.Source: §3.4 · pp. 11–13

3.5 Setting and the walk

  • The spectrahedral setting assumes bounded full-dimensional geometry and Slater feasibility, then defines the exact-metric log-det walk with Gaussian proposals and exact Metropolis–Hastings acceptance.The target is π ∝ e^−f 1_K for convex L-Lipschitz f, and proposals outside K are rejected.Source: §3.5 · p. 13

3.6 The matrix leverage operator

  • The matrix leverage operator is frame-independent, has trace d, satisfies d/n ≤ ψ(x) ≤ d, and reduces to diagonal leverage scores with ψ ≤ 1 for polytopes.Source: §3.6 · p. 14

3.7 Toolbox

  • The toolbox collects PSD trace inequalities, a twice-integrated Gaussian Stein identity, dimension-free cutoffs, McShane extensions, and scalar and matrix Gaussian concentration black boxes.The matrix concentration input is [Tro15, Theorem 4.1.1], and all subsequent applications bound the deterministic variance operator in Loewner order.Source: §3.7 · pp. 14–15
  • A differential metric inequality yields (1 −∆)^2M(x) ⪯ M(z) ⪯ (1 −∆)^−2M(x) for segment distance ∆ < 1.The proof bounds the evolving norm by ∆/(1 −t∆), controls quadratic forms, and exponentiates the resulting logarithmic change.Source: §3.7 · p. 16
  • Cross-ratio isoperimetry gives π(S3) ≥ ciso min{σ0, 1}π(S1)π(S2) when convexity and log-concavity support the localization theorem.Its role is to convert chord cross-ratio separation between two sets into stationary mass in the intervening set.Source: §3.7 · p. 16
  • For the 1/2-lazy reversible Metropolis–Hastings chain, conductance Φ implies a spectral gap of at least cChΦ^2, with laziness removing negative-spectrum issues.The paper relates its conductance convention to the cited theorem’s convention using reversibility and applies the result to the exact kernel.Source: §3.7 · p. 16

4 Proof of Theorem 1.1

This part proves the polytope mixing theorem by establishing uniform local stability and a lower tail for the complete Metropolis acceptance ratio through determinant remainders, Lewis-Hessian contraction, Stein’s method, and localization. It then converts these acceptance estimates into the stated warm-start mixing bound via kernel overlap, isoperimetry, and Cheeger’s inequality.

4.1 The metric, the walk, and the main theorem

  • eO((d^2 + dL^2R^2) log(w/δ)) steps suffice for warm-start mixing of the lazy exact Lewis-weight Metropolis walk on bounded polytopes.The theorem assumes a full-dimensional K ⊆ B2(0,R), convex L-Lipschitz f, exact acceptance, and the regularized Lee–Sidford metric; the conductance-to-mixing reduction yields the bound.Source: §1.1 · p. 3, §4.1 · p. 17

4.2 The complete proposal ratio and the exact cancellation

  • The complete Gaussian proposal log-ratio cancels the uncentered determinant and quadratic terms, leaving centered fluctuations plus a finite determinant remainder.The cancellation avoids separately controlling the difficult term w̄^T b, which would require stronger Lewis-weight inputs than available at second order.Source: §4.2 · pp. 19–20

4.3 Uniform local stability

  • A high-probability convex Gaussian tube keeps endpoint weights, slacks, and metrics uniformly comparable, reducing the ledger identity to the centered fluctuation with controlled finite errors.The tube is obtained from Gaussian concentration and a Dini bootstrap; the scaled quantity ητ1 controls slack ratios and keeps the constants dimension-free.Source: §4.3 · pp. 20, 22
  • A finite quadratic remainder controls every order of the determinant without expanding log det beyond second order or using convexity of log det G.The stability argument bounds the eigenvalues of the normalized perturbation and applies the fundamental theorem of calculus.Source: §4.3 · p. 23

4.4 A row-dependent contraction of Lewis Hessians

  • The row-dependent Lewis-Hessian contraction improves the relevant bound to C_p d, versus the naive C_p n d or C_p d^3/2.It applies when each direction r_i has norm at most μ√w_i; these are exactly the directions produced by the Stein identity.Source: §4.4 · pp. 24, 25, 27

4.5 A Stein bound for the centered fluctuation, and the acceptance lower tail

  • Stein’s method combines the C_p d contraction, a dimension-free Lipschitz bound, and cutoff-extension arguments to control centered fluctuations and assemble a uniform lower tail for the complete Metropolis ratio.The analysis works on the stability tube, uses a cutoff to obtain compactly supported W 2,∞ functions, and extends the fluctuation globally without increasing its Lipschitz constant.Source: §4.5 · pp. 27–29
  • At every interior x, the complete ratio satisfies Pr_Y~q_x[Y ∈ K and log R_x(Y) ≥ −C] ≥ 1 − ϵ, with universal constants independent of x, n, d, L, R, and regularizer orientation.The argument controls proposal and target-ratio terms on intersected tube, concentration, and Gaussian-norm events.Source: §4.5 · p. 30
  • The acceptance lower-tail lemma is affine-invariant and requires no boundary-layer or s-conductance argument, because it holds at every interior point and uses only C ⪰ 0 for the regularizer.This removes dependence on distance to the boundary in the subsequent conductance analysis.Source: §4.5 · p. 30

4.6 From acceptance to mixing

  • The proof converts acceptance into mixing by combining local Gaussian overlap, kernel overlap, symmetry, cross-ratio isoperimetry, and Cheeger’s inequality directly for the complete kernel.This avoids reintroducing forward/reverse asymmetry at the coupling stage.Source: §4.6 · pp. 31, 32, 34
  • The regularized metric G = κH + L2I inherits the needed self-concordance-type control and symmetry, while cross-ratio separation yields a uniform conductance lower bound for the walk.Proposal overlap and accepted-kernel overlap hold for nearby states, and the resulting separation is combined with log-concave cross-ratio isoperimetry.Source: §4.6 · pp. 31, 33, 34

5 Proof of Theorem 1.2

This section proves the spectrahedral log-det walk mixing theorem by controlling acceptance through endpoint identities, spectral-tube stability, determinant remainders, and centered fluctuations, then converting acceptance into mixing via local overlap and cross-ratio conductance. It also identifies a family-specific obstruction for the arrow spectrahedron, showing that the unscaled walk requires a proposal radius of order at most d^-1/2 for constant acceptance.

5.1 Main theorem

  • Under bounded strict feasibility, convex L-Lipschitz f, and κ = eO(ψ*), the exact-metric lazy Metropolis walk mixes in O~((ψ*nd + dL^2R^2) log(w/δ)) steps.The result holds from a w-warm start and reaches total-variation distance δ.Source: §5.1 · pp. 34–35

5.2 Normalization, endpoint formulas, and the ledger

  • Normalization preserves the Metropolis ratio and yields an exact proposal ledger in which the uncentered coupling tr[Q Ē] cancels, leaving determinant and centered-fluctuation remainders.The normalized regularized metric is written G(x) = κ(I + C), with C ⪰ 0 and 0 ⪯ Q = (I + C)^−1 ⪯ I.Source: §5.2 · pp. 35–36

5.3 The spectral tube, stability, and the determinant remainder

  • The spectral tube has high Gaussian probability, while collar stability keeps ∥Δ∥op ≤ 1/64 and controls the determinant remainder through eigenvalue bounds for I + E.The tube probability follows from Gaussian norm and matrix-series concentration, and stability makes endpoint quantities uniformly comparable to their base values.Source: §5.3 · pp. 37–38

5.4 The Stein mean bound

  • A paired four-trace estimate bounds the Stein second-derivative contributions by 13/12 ψd, yielding the mean-control mechanism for the centered fluctuation Z.The contraction uses the six four-letter words from the endpoint second-derivative formula and bounds their aggregate contribution after the η^2 prefactor.Source: §5.4 · pp. 38–39
  • The Stein mean bound controls the main and collar contributions so their total is at most ϵ0 under the chosen parameters.The collar terms are controlled using their small probability and uniform bounds, while the main term follows from Lemma 5.9.Source: §5.4 · p. 40

5.5 Fluctuation bound, parameter choice, and the acceptance theorem

  • The fluctuation analysis establishes a uniform lower tail for the complete acceptance ratio with universal constants independent of x, n, d, L, R, and regularizer orientation.The proof combines tube, Gaussian-deviation, and norm events; feasibility, proposal, and target ratios are then bounded separately.Source: §5.5 · p. 42

5.6 From acceptance to mixing

  • The acceptance-to-mixing argument combines Gaussian proposal overlap, kernel overlap, cross-ratio geometry, and conductance to obtain mixing control.The acceptance guarantee is boundary-independent and affine-invariant, while self-concordance relates the local metric to cross-ratio separation used in the conductance proof.Source: §5.5 · p. 42, §5.6 · pp. 44–45

5.7 A worst-case acceptance obstruction: the arrow spectrahedron

  • For a fixed universal proposal radius, the arrow spectrahedron shows that uniform constant acceptance can require κ = Ω(ψ(x)), with ψ(0) = Θ(ψ+∗) up to polylogarithmic factors.The construction uses n = d + 1 and an arrow-shaped spectrahedron whose relevant restriction has eigenvalues 1 ± ∥x∥/2.Source: §5.7 · p. 45
  • On the arrow instance with f ≡ 0 and unit scale, accepted proposals have probability bounded away from one for sufficiently small r and large d.The result applies at the center x = 0, where H(0) = I.Source: §5.7 · p. 46
  • Constant acceptance requires r ≲ d^-1/2 ≍ ψ(0)^-1/2, making the ψ-scaling necessary up to logarithmic factors on this family.With center metric scaled from I to κI, the same calculation forces κ = Ω(d) = Ω(ψ(0)) at fixed universal r.Source: §5.7 · pp. 46–47
  • The obstruction is family-specific and proves neither a pointwise if-and-only-if characterization for all spectrahedra nor a mixing-time lower bound.For polytopes and incoherent instances, the theorem gives eO(nd), while the general barrier-scaling bound is eO(d^2n).Source: §5.7 · p. 47

A Approximate metrics and exact-arithmetic complexity

The appendix shows that exact metrics can serve as reference chains while implementations use approximate metrics. One-sided padding and O(1/d) relative error preserve proposal overlap and conductance, with high-precision Lewis weights for polytopes and TensorSRHT plus two-seed filtering for spectrahedra.

Implementation guarantees

  • Exact walks remain reference chains because exact Lewis-map derivatives and log-det Hessians enable the analysis’s cancellation and endpoint identities.Approximate-metric proposals are compared against these exact chains without changing the ledger arguments.Source: A Approximate metrics and… · p. 48

Approximate metrics

  • One-sided metric padding and O(1/d) relative error keep approximate Gaussian proposals within a constant factor on the established acceptance event, preserving overlap and conductance.The resulting universal constants may differ from those for exact proposals.Source: A Approximate metrics and… · p. 48
  • High-precision Lewis weights implement the polytope approximation, while spectrahedra use TensorSRHT log-det Hessian sketches and a two-seed Metropolis filter.The spectrahedral construction follows Gu et al. [GKM+24, Lemma G.12].Source: A Approximate metrics and… · p. 48

A.1 High-precision Lewis weights

High-precision Lewis weights provide a deterministic, coordinatewise approximation to the exact weights. Inflating the resulting metric by the worst downward error yields the one-sided comparison needed to transfer the exact walk’s guarantees.

A.1 High-precision Lewis weights

  • (1−εw)wx,i ≤ ewx,i ≤ (1+εw)wx,i for every coordinate, with the prescribed initialization and iteration count making the output a deterministic Borel function of x.The guarantee follows from Gribling–Sidford–Zhang’s high-precision result and the fixed computation schedule.Source: §A.1 · p. 49
  • Inflating the approximate metric by (1−εw)^−cp converts the two-sided weight estimate into the required one-sided metric comparison.For εw ≤ 1/2, the associated distortion parameter satisfies 0 ≤ θw ≤ 4εw.Source: §A.1 · pp. 49–50
  • The perturbation argument compares the inflated approximate metric with the exact metric pointwise, then transfers the exact walk’s acceptance and overlap bounds without differentiating the approximate weights.The resulting approximate-metric LS walk is defined using the inflated metric and remains 2-lazy.Source: §A.1 · pp. 49–50

A.2 From metric approximation to mixing

The section shows that O(1/d)-accurate metric approximations preserve proposal overlap, endpoint density control, acceptance, and the dimension-square mixing guarantee. For randomized spectrahedral metrics, independent endpoint seeds restore reversibility and kernel overlap under pointwise good-seed conditions.

Deterministic metric approximation

  • The 1/d accuracy scale controls Gaussian determinant fluctuations across d directions, yielding centered proposal closeness and endpoint density comparisons.The sandwich simultaneously gives total-variation closeness of centered proposals and control of Gaussian densities at both endpoints of accepted steps.Source: §A.2 · pp. 50–51
  • If ε_w ≤ c_app/d, approximate acceptance remains uniformly bounded below and the approximate kernels retain a fixed positive local overlap.The argument combines the two-endpoint reference event with Gaussian proposal perturbation and an overlap margin inherited from the exact analysis.Source: §A.2 · pp. 51–52
  • Theorem A.7 gives exactly reversible mixing in eO((d^2 + dL^2R^2) log(w/δ)) steps when the deterministic Lewis-weight metric error satisfies ε_w ≤ c_app/d.The proof transfers exact-walk conductance through approximate proposal overlap, endpoint acceptance control, and warm-start mixing.Source: §A.2 · p. 52

Randomized metric approximation

  • For randomized metrics, independent seeds at both endpoints make the marginal kernel exactly reversible and preserve common mass when good seeds and conditional acceptance bounds hold pointwise.This two-seed device follows Gu et al. [GKM+24, Lemma D.12] and requires no event to hold simultaneously over the mixing horizon.Source: §A.2 · pp. 52–53

A.3 Arithmetic complexity for polytopes

The polytope walk admits an exact-arithmetic implementation whose cached metric requires at most one new Lewis-weight computation per feasible proposal and one new potential evaluation per Markov step. The resulting arithmetic-operation guarantee excludes finite-bit precision effects and is therefore not a bit-complexity bound.

Implementation and cost

  • At most one new Lewis-weight computation is needed per feasible proposal, while caching limits the walk to one new evaluation of f per Markov step.The initial metric and target-value cache is built once; subsequent accepted proposals update it for the next step.Source: §A.3 · pp. 53–54

Arithmetic complexity

  • With εw = capp/d, Corollary A.9 gives an exact-arithmetic implementation and a warm-start total-cost bound, with the displayed operation counts supplied by the corollary.The result also bounds the number of evaluations of f by eO((d2 + dL2R2) log(ew/δ)).Source: §A.3 · pp. 53–54

Lewis-weight computation

  • One ApproxLewisεw call costs eO(ndω−1) arithmetic operations, where ω is the square-matrix multiplication exponent.The estimator uses polylogarithmically many iterations in n and d, each computing a full leverage-score vector.Source: §A.3 · p. 54

Exact-arithmetic model

  • The bound is stated in an exact-arithmetic model that assigns unit cost to field operations, comparisons, scalar functions, and exact random variates.It includes Lewis iterations, slack and membership checks, metric factorization, Gaussian quadratic forms, and one new target evaluation at feasible proposals.Source: §A.3 · p. 54

Limitations

  • The corollary is an arithmetic-operation bound rather than a bit-complexity result because it does not control finite-bit conditioning, approximate Gaussian generation, or inexact Metropolis decisions.A bit-complexity analysis would additionally require precision control for ill-conditioned diagonal scalings.Source: §A.3 · p. 54

A.4 A sketched log-det metric

The section constructs a two-seed TensorSRHT approximation to the log-det metric, with padding and fallback ensuring well-defined positive-definite proposals. It proves exact reversibility and warm-start mixing with complexity controlled by an upper bound on matrix leverage.

Metric approximation

  • With probability at least 1 − βs for each fixed state, the TensorSRHT sketch supplies the metric approximation needed for the sketched proposal.The construction forms the sketched Gram factor, applies one-sided padding, and avoids fallback on the sketch-success event.Source: §A.4 · p. 55

Construction

  • Padding the pencil to the next Hadamard size leaves the feasible body, log-det Hessian, and ψ* unchanged while altering bounds by at most a universal constant.The padded size satisfies n′ < 2n, and the leverage operator becomes Ψ(x) ⊕ 0.Source: §A.4 · p. 55
  • The sketched log-det walk uses independent fresh TensorSRHT seeds at the proposal endpoints and evaluates both conditional densities exactly, preserving exact reversibility.The fallback defines the conditional proposal for every seed, while the approximation guarantee applies on the sketch-success event.Source: §A.4 · pp. 55–56

Mixing guarantee

  • If εs ≤ cs/d and βs ≤ β̄s, the walk is exactly reversible and mixes from a w-warm start in eO((ψ̂nd + dL^2R^2) log(w/δ)) steps.Here ψ̂ ≥ ψ*; choosing ψ̂ = d is always valid because ψ* ≤ d, yielding eO((nd^2 + dL^2R^2) log(w/δ)).Source: §A.4 · p. 56

Proof mechanism

  • The proof transfers the exact reference walk through constant conditional acceptance and common mass, then applies the existing conductance and warm-start arguments without a horizon-wide union bound.Failed seeds are incorporated into the transition kernel, while seed interchange makes the accepted flow symmetric.Source: §A.4 · pp. 56–57

A.5 Arithmetic complexity for spectrahedra

The implementation selects an exact direct metric build for n < s and a TensorSRHT sketched build for n ≥ s, charging each transition to the cheaper regime. Corollary A.16 gives arithmetic and evaluation bounds in an exact-arithmetic model, while excluding finite-bit and rounded-sampling costs.

Metric construction

  • A fresh sketched-metric build costs O(dn^2 + n^ω + dTmat(n,n,s) + Tmat(d,s,d) + d^ω).The terms form and factor the slack, construct the TensorSRHT, form its Gram matrix, and factor the d × d metric.Source: §A.5 · p. 57

Implementation

  • The implementation uses the direct exact-metric walk when n < s and the sketched walk when n ≥ s, with s = eO(d^3).The threshold rule charges each transition to the cheaper metric construction in its dimension regime.Source: §A.5 · p. 57

Complexity guarantee

  • Corollary A.16 bounds total function evaluations by eO((bψnd + dL^2R^2) log(ew/δ)), or by eO((nd^2 + dL^2R^2) log(ew/δ)) when bψ = d.The result applies from an exact w-warm draw and permits at most one new evaluation of f per Markov step.Source: §A.5 · p. 58

Arithmetic model

  • The arithmetic count includes exact field operations, metric construction and factorization, conditional Gaussian densities, and the two-seed Metropolis decision.The model assigns unit cost to exact Gaussian, uniform, and Rademacher variates and assumes an exact warm draw and supplied parameters.Source: §A.5 · p. 58

Scope and limitations

  • The bounds count arithmetic operations rather than bit complexity, excluding finite-bit conditioning, rounded Gaussian sampling, inexact Metropolis decisions, and warm-start construction.The implementation uses fresh independent endpoint seeds for spectrahedra, and actual conditional proposal densities in the Metropolis ratio.Source: §A.5 · p. 58

Related papers

Loading 2608.25273v1…