Chapter 9 · Book pp. 233–248 · August 9, 2026 edition
Lower Bounds for Sampling
Identify which dimension, smoothness, condition-number, and accuracy dependences are unavoidable.
Begin with 9.1 Open this chapter in the canonical August 9 source ↗Chapter route
This chapter develops minimax risk, packing, testing reduction, oracle lower bound. Its main destination is to connect the definitions below to the results that later chapters consume.
Core definitions
- Query complexity counts oracle evaluations rather than bit-level computation.
- A hard family is a collection of target potentials that agree on much of the oracle transcript.
- A testing reduction turns an accurate sampler into an estimator of the hidden hard-instance index.
Main results
- One-dimensional constructions yield nontrivial smooth log-concave sampling lower bounds.
- Constant-dimensional packings show additional accuracy and query barriers.
- Gaussian families isolate dimension-dependent lower bounds in a tractable subclass.
- The lower bounds calibrate which upper-bound dependences are algorithmic losses and which are intrinsic.
Contents
Why is this chapter route valid?
Analytic contracts
- The oracle transcript and algorithmic randomization must be represented explicitly.
- Pairwise divergence bounds need the exact observation law.
- The hard family must remain inside the stated target class.
Open boundaries
- Oracle-transcript framework
- Packing and testing reductions
- Book-specific hard instances
View Lean formalization
These mappings are evidence links, not a claim that the entire chapter is formalized.
No declaration-level source block is mapped for this chapter yet.