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

The paper addresses the difficulty of controlling endpoint-dependent determinant and reverse-quadratic terms in Metropolis-adjusted Dikin walks. It keeps the complete logarithmic acceptance ratio intact, uses cancellation and second-order tools, and obtains dimension-square polytope mixing together with leverage-dependent spectrahedral mixing. Proposal comparison then extends the results to exact-arithmetic implementations with approximate metrics.

  • Problem

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

  • Method

    The analysis keeps the complete logarithmic Metropolis ratio intact, uses determinant–quadratic cancellation, and controls the centered remainder with Gaussian integration by parts and concentration.

  • Results

    eO((d^2 + dL^2R^2) log(w/δ)) steps suffice for polytopes, while spectrahedra require eO((ψ*nd + dL^2R^2) log(w/δ)) steps.

  • Takeaways & Limitations

    The shared acceptance-to-mixing reduction supports exact-metric analyses and proposal-comparison transfers to implementable approximate-metric walks.

  • Takeaways & Limitations

    The arrow-spectrahedron obstruction shows leverage scaling is needed for uniform acceptance but does not establish a mixing-time lower bound.

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 analyzes Metropolis-adjusted Dikin walks by controlling the complete acceptance ratio, whose determinant and reverse-quadratic terms cancel at leading order. It proves dimension-square polytope mixing, leverage-dependent spectrahedral mixing, and transfers both analyses to implementable approximate metrics.

  • Motivation: Dikin walks adapt Gaussian proposals to local barrier metrics for sampling log-concave densities over convex bodies.For nearly universal barriers, the affine-invariant approach can avoid artificial dependence on the number of constraints.
  • Analytic challenge: The Metropolis filter requires controlling both the proposal determinant and the reverse local quadratic form at the random endpoint.Forward containment in a local ellipsoid alone is insufficient.
  • Core method: Keeping the complete logarithmic Metropolis ratio intact makes the log-determinant linear term cancel the uncentered reverse-quadratic mean.The remaining centered fluctuations are controlled with Gaussian integration by parts and second-order concentration.
  • Implementations: Approximate metrics preserve the corresponding mixing bounds through proposal comparison and exact reversibility.Polytopes use padded O(1/d)-accurate Lewis weights; spectrahedra use direct or two-seed TensorSRHT constructions, with arithmetic-operation rather than bit-complexity guarantees.

2 Technical overview

The technical overview develops parallel polytope and spectrahedral analyses around exact determinant–quadratic cancellation, then transfers their mixing guarantees to implementable approximate metrics.

  • The two proof mechanisms are separated into a Lewis-weight argument for polytopes and a noncommutative log-det argument for spectrahedra.
  • Polytopes: The polytope analysis keeps the complete acceptance ratio intact, where determinant and reverse-quadratic terms cancel before fluctuation bounds are applied.Lewis-weight stability, Gaussian integration by parts, and second-order concentration control the remaining terms.
  • Polytopes: The polytope conductance argument combines local Gaussian overlap, kernel overlap, symmetry, cross-ratio isoperimetry, and Cheeger’s inequality.The resulting warm-start bound is eO((d^2 + dL^2R^2) log(w/δ)) steps.
  • Spectrahedra: The spectrahedral analysis has the same cancellation structure, but its centered fluctuation is a noncommutative trace polynomial controlled through matrix leverage.A leverage-controlled spectral tube and trace contractions yield the acceptance estimate.
  • Spectrahedra: The spectrahedral conductance reduction again uses proposal overlap and local geometry, yielding eO((ψ^*nd + dL^2R^2) log(w/δ)) steps.The arrow spectrahedron shows exponentially small center acceptance when κ = 1 and ψ(0) = Θ(d), motivating leverage scaling for uniform acceptance.
  • Implementable kernels: Approximate positive-definite metrics preserve acceptance and proposal overlap up to universal constants, so the exact mixing bounds transfer without differentiating the approximate metric.The implementation constructs reverse metrics at proposed endpoints and applies the exact Metropolis filter to the constructed metrics.

3 Preliminaries

The preliminaries establish the polytope and spectrahedral settings, define Lewis and leverage weights, and collect smoothness, concentration, isoperimetry, and conductance tools for mixing analysis.

  • Geometric setting: The polytope is a bounded, full-dimensional set K = {z ∈ R^d : Az ≥ b} contained in a radius-R Euclidean ball, with interior defined by strict slacks.Feasible points satisfy Az − b > 0.
  • Lewis-weight calculus: Lewis weights are uniquely defined positive fixed-point weights for the slack-rescaled constraint matrix, and their spatial derivatives are governed by a row-rescaling Jacobian.The associated leverage-score matrix is a rank-d orthogonal projection.
  • Concentration: Gaussian Lipschitz concentration and centered Gaussian tails provide the probabilistic control used for proposal fluctuations.The concentration theorem is treated as the only non-elementary concentration black box in the polytope proof.
  • Metric regularity: The scaled Lee–Sidford metric 2(1 + p^2)H is strongly self-concordant, with resolvent and derivative bounds controlling metric variation.The eigenvalue bounds imply ∥R_z∥op ≤ p/2 and 0 ⪯ N_z ⪯ pI.
  • Mixing tools: Cross-ratio isoperimetry converts separation between sets into stationary mass in an intervening set, while Cheeger’s inequality converts conductance into a spectral gap.Exact Metropolis detailed balance supplies reversibility, and laziness places the spectrum in [0, 1].
  • Spectrahedral setup: For the exact-metric log-det walk, proposals are Gaussian with covariance proportional to G(x)^−1 and are accepted using the exact Metropolis–Hastings ratio.The chain is reversible with respect to π ∝ e^−f 1_K, and w-warmness bounds the initial density relative to π.
  • Spectrahedral setup: The matrix leverage parameter Ψ has trace d and satisfies d/n ≤ ψ(x) ≤ d; in the polytope case, ψ ≤ 1.For diagonal blocks, Ψ reduces to the diagonal leverage-score matrix of the slack-rescaled constraints.

4 Proof of Theorem 1.1

The proof analyzes the complete Metropolis proposal ratio through exact endpoint identities and determinant–quadratic cancellation, then controls the remaining fluctuations to obtain dimension-square mixing for polytopes.

  • 4.1 The metric, the walk, and the main theorem: The regularized Lee–Sidford walk uses a 1/2-lazy exact-metric Gaussian proposal and the exact Metropolis–Hastings acceptance ratio.Proposals outside K are rejected, and the resulting chain is reversible with respect to π ∝ e^−f 1_K.
  • 4.1 The metric, the walk, and the main theorem: Theorem 4.2 gives warm-start mixing in eO((d^2 + dL^2R^2) log(w/δ)) steps for bounded polytopes with n inequalities.The bound applies to convex L-Lipschitz potentials and exact Lewis weights.
  • 4.2 The complete proposal ratio and the exact cancellation: After affine normalization, the regularizer is constant across the proposal, so endpoint changes are expressed through the Lee–Sidford metric alone.The Gaussian proposal is represented as y = x + ηh with h ∼ N(0, Q) and Q ⪯ I.
  • 4.2 The complete proposal ratio and the exact cancellation: Exact endpoint identities express the proposal determinant and reverse quadratic form without Taylor-expanding the endpoint metric.The endpoint rescaling sign is explicit, and the resulting quadratic identity is exact.
  • 4.2 The complete proposal ratio and the exact cancellation: The complete Gaussian log-ratio cancels the uncentered determinant term against the mean of the reverse quadratic term, leaving centered fluctuations and finite second-order remainders.Separately bounding determinant and quadratic terms would require stronger Lewis-weight inputs than the second-order analysis provides.
  • 4.3 Lewis-weight stability and acceptance: A high-probability convex tube keeps endpoint slacks, Lewis weights, and metrics uniformly comparable to their base-point values.The scaled quantity ητ1 controls slack ratios and makes the constants in the tube dimension-free.
  • 4.5 Acceptance and mixing: A uniform lower-tail bound gives Pr[Y ∈ K and log R_x(Y) ≥ −C] ≥ 1 − ε uniformly over every interior point.The constants are independent of x, n, d, L, R, and the regularizer orientation, with no boundary-distance dependence.

5 Proof of Theorem 1.2

The spectrahedral proof combines exact endpoint identities with centered fluctuation bounds to establish acceptance, conductance, and warm-start mixing for the log-det walk.

  • Assumptions: Theorem 5.1 analyzes bounded, strictly feasible spectrahedra with n × n blocks, a convex L-Lipschitz potential, and a log-det metric governed by ψ⋆.The scale κ is chosen exponentially in ψ⋆ up to the paper’s stated asymptotic notation.
  • Endpoint identities: The exact endpoint identities express the transformed metric and its derivatives through resolvents R and trace products along feasible Gaussian steps.The condition ∥∆(g)∥op < 1 ensures the entire proposal segment remains interior.
  • Acceptance analysis: The complete proposal log-ratio cancels the uncentered coupling tr[QĒ], leaving a determinant remainder and centered fluctuation controlled by second-order estimates.This cancellation occurs before tail bounds are applied.
  • Stability and concentration: The tube and collar lemmas provide high-probability feasibility and uniform resolvent stability, with R bounded between 64/65 I and 64/63 I.Gaussian norm and spectral concentration establish the tube event.
  • Mixing reduction: The acceptance, proposal-overlap, kernel-overlap, symmetry, and conductance lemmas feed the Cheeger and warm-start spectral argument for total-variation mixing.The proof uses the nonnegative spectrum of the lazy reversible chain.
  • Acceptance obstruction: On the arrow family, constant acceptance for the unscaled walk requires r ≲ ψ(0)^−1/2, while the result is not a general mixing lower bound.The obstruction matches the sufficient leverage scale up to logarithmic factors on that family.

A Approximate metrics and exact-arithmetic complexity

The implementation appendix compares approximate-metric proposals with exact reference walks, preserving mixing under sufficiently accurate metric approximations.

  • Reference chains: The exact walks serve as reference chains because their analyses rely on exact Lewis maps or exact log-det Hessians.The implementation argument avoids differentiating the approximate metric.
  • Proposal comparison: A one-sided padded metric together with O(1/d) relative error keeps approximate Gaussian proposals within a constant factor on the established acceptance event.The determinant contribution across d directions explains the accuracy scale.

A.1 High-precision Lewis weights

High-precision Lewis-weight estimates produce deterministic approximate metrics, whose padding supports an exactly reversible approximate Lee–Sidford walk.

  • Weight computation: The weight approximation satisfies (1 − εw)wx,i ≤ ewx,i ≤ (1 + εw)wx,i coordinatewise.The prescribed fixed-schedule iteration and all-ones initialization make the output a deterministic measurable function of x.
  • Metric construction: Inflating the approximate metric by its worst downward error yields ¯H(x) = (1 − εw)^−cp eH(x) and ¯G(x) = κ¯H(x) + L²I.The padding converts a two-sided weight guarantee into the one-sided comparison required by the perturbation argument.
  • Walk implementation: The approximate walk uses lazy Gaussian proposals, rejects infeasible steps, evaluates the acceptance ratio, and caches metric-related quantities.Its state-dependent proposal and acceptance operations are specified algorithmically.
  • Perturbation strategy: The perturbation argument compares approximate and exact metrics pointwise rather than differentiating approximate Lewis weights.This transfers acceptance and overlap properties from the exact walk.

A.2 From metric approximation to mixing

Approximate proposals inherit exact-walk mixing through Gaussian density comparisons, acceptance preservation, and overlap arguments, including a two-seed treatment for randomized metrics.

  • Density comparison: Because Gaussian log densities aggregate determinant errors over d directions, metric relative accuracy must be O(1/d) to preserve constant-factor proposal comparisons.The relevant comparison is made on the exact walk’s acceptance event.
  • Acceptance preservation: If εw ≤ capp/d, approximate acceptance retains a uniform lower bound, with the perturbation contributing only a bounded dθw term.The bound follows from θw ≤ 4εw and the two-endpoint reference event.
  • Overlap: Approximate proposal overlap remains sufficient after accounting for total-variation perturbations, provided the approximation constant is chosen small enough.The proof preserves a fixed positive overlap margin.
  • Polytope guarantee: The padded approximate-metric LS walk is exactly reversible and mixes in eO((d² + dL²R²) log(w/δ)) steps from any w-warm start.The result is obtained by reusing the exact walk’s conductance and warm-start argument.
  • Randomized metrics: For randomized spectrahedral metrics, independent endpoint seeds and a pointwise good-seed guarantee preserve reversibility and common proposal mass.No event must hold simultaneously over the entire mixing horizon.

A.3 Arithmetic complexity for polytopes

The polytope implementation combines cached deterministic Lewis-weight metrics with exact-arithmetic Metropolis steps, yielding stated arithmetic and function-evaluation bounds for warm-start mixing.

  • Metric construction: εw = capp/d sets the Lewis-weight accuracy used by Algorithm 1.The fixed-schedule estimator computes coordinatewise Lewis-weight estimates to the required relative accuracy.
  • Mixing and cost: eO((d2 + dL2R2) log(ew/δ)) evaluations of f suffice for warm-start mixing to total-variation error δ.The walk starts from an exact w-warm draw and uses at most one new evaluation of f per Markov step.
  • Metric construction: eO(ndω−1) arithmetic operations bound one ApproxLewisεw call through exact leverage-score computation.The cost comes from forming and factoring the weighted Gram matrix and evaluating all row quadratic forms.
  • Per-step implementation: Each nonlazy iteration computes at most one new feasible-endpoint metric and one new target value because the current metric and target are cached.Proposal factorization, determinant evaluation, and both quadratic forms are included in the per-step accounting.
  • Model scope: The exact-arithmetic model counts field operations, exact random variates, metric work, and target evaluations, but not finite-bit conditioning or rounded sampling.It is therefore an arithmetic-operation bound rather than a bit-complexity result.

A.4 A sketched log-det metric

The sketched log-det walk pads TensorSRHT metric approximations to remain positive definite, uses fresh endpoint seeds, and preserves exact reversibility with a controlled mixing bound.

  • Implementation: TensorSRHT compresses the Gram factor before forming the d×d metric, with sketch size s = eO(d3) at εs = Θ(1/d) and constant failure probability.The direct construction is used when n < s, while the sketched construction is used when n ≥ s.
  • Metric construction: One-sided padding defines positive-definite sketched metrics on every seed while restricting the approximation claim to the sketch-success event.The padded metric is combined with L2I in the implemented geometry.
  • Two-seed implementation: Fresh independent seeds are used at the current point and proposal so the reverse sketch does not depend on chain history.Reusing the reverse seed would require a different lifted-state analysis.
  • Mixing guarantee: bψ ≥ ψ+∗ and εs ≤ cs/d yield exact reversibility and warm-start mixing in eO((bψnd + dL2R2) log(w/δ)) steps.The guarantee applies to the two-seed sketched log-det walk under the hypotheses of Theorem 5.1.
  • Mixing guarantee: bψ = d is always valid because ψ+∗ ≤ d, giving the unconditional order eO((nd2 + dL2R2) log(w/δ)).This substitutes nd2 for the leverage-dependent term.
  • Proof strategy: The seed-interchange argument makes the marginal accepted flow symmetric, while common-mass and conductance arguments transfer mixing from the exact reference walk.The pointwise sketch guarantee does not require a union bound over the mixing horizon.

A.5 Arithmetic complexity for spectrahedra

The spectrahedral implementation selects direct or sketched metric construction by block dimension and gives exact-arithmetic per-step, total, and function-evaluation bounds.

  • Sketched branch: A complete fresh sketched-metric build costs Csk(n, d, s) := O(dn2 + nω + dTmat(n, n, s) + Tmat(d, s, d) + dω).The terms account for slack formation and factorization, TensorSRHT construction, Gram formation, and d×d metric testing and factorization.
  • Branch selection: n < s uses the direct exact build, while n ≥ s uses the sketched build with s = eO(d3).This regime rule charges each transition to the cheaper metric construction for its dimension range.
  • Total complexity: eO((bψnd + dL2R2) log(ew/δ)) evaluations of f suffice for warm-start spectrahedral mixing.With bψ = d, the leverage term becomes nd2 in the total bound.
  • Per-step cost: A nonlazy feasible sketched transition uses one fresh forward build and one fresh reverse build, with the factor of two treated as constant.Slack factors and the current target value may be cached, but random metrics are not reused.
  • Model scope: The exact-arithmetic count includes TensorSRHT application, metric factorization, both conditional Gaussian densities, and the two-seed Metropolis decision.The input supplies an exact warm draw and parameters L, R, w, and bψ.
  • Model scope: The spectrahedral bounds count arithmetic operations rather than bit complexity and exclude finite-bit conditioning, rounded Gaussian sampling, inexact decisions, and warm-start construction.These exclusions apply to the stated implementation complexity result.
Loading 2608.25273v1…