Reducing Isotropy to KLS, A Faster Sampling Algorithm
summary
Claims a sampling algorithm that uses roughly n^{3.5} oracle calls for any convex body and, if the KLS conjecture holds, improves to n^{3}. It builds an iterative routine that maintains an inner ball, runs the ball-walk to gather r^2 samples per phase, computes empirical covariance, rescales directions with eigenvalues > n, and repeats for O(log n) phases. Proofs use matrix Chernoff bounds to control large eigenvalues; the procedure is proved to work and matches the stated runtimes.
AI-written summary · about