Variance-adaptive Chernoff bounds: nonasymptotically valid, asymptotically sharp confidence sets for unbounded means
Ramdas and Martinez-Taboada
It closes a long-standing gap in concentration: under martingale dependence and a sub-Gaussian proxy \(s\), it gives closed-form intervals valid at every \(n\) whose half-width matches \(\sigma z_{1-\alpha/2}/\sqrt{n}\) to first order, and confidence sequences of width \(\sigma\sqrt{2\log\log n/n}\), with extensions to heavy tails given any moment above two.
- Prerequisites
- Martingales and Ville’s inequality, sub-Gaussian moment generating functions, empirical-Bernstein bounds, the law of the iterated logarithm.
- Focus on
- Sections 1.1 to 1.3, 2.1 to 2.4 and 3.1 to 3.3; Section 5 for the heavy-tailed case.
- Reading time
- About 4 hours
arXiv:2610.42058
Verifier-Guided Self-Consistency: Test-Time Reasoning with Imperfect Generators and Verifiers
Fadeeva et al.
It gives a probabilistic reading of how majority voting and verifier-guided search combine: the decoder is approximate sampling from a trajectory distribution tilted by the verifier, while several trajectories are kept for a final vote.
- Prerequisites
- Self-consistency and majority voting, process and outcome reward models, importance sampling and accept-reject schemes.
- Focus on
- Section 3, especially 3.1 to 3.4, and the proofs in Appendix C.
- Reading time
- About 2 hours
arXiv:2611.06606