2024/10/08 by Yuzhou Gu, Gu, Yuzhou, Nikki Lijing Kuang +7 · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2410.05700
openalex publication_date 2024/10/08 · openalex created_date 2024/10/12 · openalex updated_date 2026/07/28
We consider the problem of sampling from a d-dimensional log-concave distribution π(θ) ∝ exp(-f(θ)) for L-Lipschitz f, constrained to a convex body with an efficiently computable self-concordant barrier function, contained in a ball of radius R with a w-warm start. We propose a robust sampling framework that computes spectral approximations to the Hessian of the barrier functions in each iteration. We prove that for polytopes that are described by n hyperplanes, sampling with the Lee-Sidford barrier function mixes within \widetilde O((d2+dL2R2)log(w/δ)) steps with a per step cost of \widetilde O(ndω-1), where ω≈ 2.37 is the fast matrix multiplication exponent. Compared to the prior work of Mangoubi and Vishnoi, our approach gives faster mixing time as we are able to design a generalized soft-threshold Dikin walk beyond log-barrier. We further extend our result to show how to sample from a d-dimensional spectrahedron, the constrained set of a semidefinite program, specified by the set \x∈ ℝd: ∑i=1d xi Ai \succeq C \ where A1,…,Ad, C are n× n real symmetric matrices. We design a walk that mixes in \widetilde O((nd+dL2R2)log(w/δ)) steps with a per iteration cost of \widetilde O(nω+n2d3ω-5). We improve the mixing time bound of prior best Dikin walk due to Narayanan and Rakhlin that mixes in \widetilde O((n2d3+n2dL2R2)log(w/δ)) steps.