Subpolynomial query complexity for well-conditioned log-concave sampling
For every fixed ε > 0, we give a sampling algorithm using at most $C_\varepsilon d^\varepsilon$ exact first-order queries on every execution for C 2 potentials on ℝ d with a known minimizer and Hessian between I d and $2I_d$. The output has total-variation distance at most 1/10 from the target Gibbs law. Computation between queries is unrestricted. We also prove an $\Omega(\log d)$ query lower bound for arbitrary randomized adaptive algorithms, determining the optimal dimension exponent to be zero.
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling
curl -X POST /api/v1/records/openai-math/Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'