New paper: a general recipe for anytime-valid error bounds for iterative algorithms
_onionesque · x · 2026-10-20
A new arXiv paper by Soham Bonnerjee and Aaditya Ramdas gives a general recipe for data-adaptive anytime-valid error bounds for a broad class of stochastic iterative algorithms.
- Problem: most convergence guarantees hold only at fixed iteration counts; existing anytime-valid envelopes are either too conservative or derived case-by-case.
- Key idea: many algorithms' performance measures satisfy a one-step recursion, reducing error analysis to time-uniform concentration of predictably weighted noise sums (a strongly adapted sub-ψ condition).
- Tools: off-the-shelf boundaries via continuous/discrete mixtures, stitching, and product betting martingales.
- Coverage: SGD, temporal-difference learning, Bures-Wasserstein SGD; for SGD it recovers or significantly sharpens every known envelope.
More from Research
- RFD4-Proteina's 'underrated' docs detail partial diffusion for protein redesign — AllThingsApx · 2026-10-23
- MPI-Sec PhD Thesis on Vulnerability Detection Benchmarks Includes Pre-LLM Classic "Top Score on the Wrong Exam" — mboehme_ · 2026-10-23
- LiveNerf's 29-day data finds no nerfing of Claude Opus 5.5 — TheOnlyVibemaster · 2026-10-23
- New paper makes 9 falsifiable predictions toward a major AI-enabled terror attack by 2027-2028 — StephenLCasper · 2026-10-23
- HumanoidPose recovers humanoid robots' full-body joint states from RGB video alone — cholz · 2026-10-23
- Sophont's Holon-S1 predicts genes and biomarkers from routine pathology slides — iScienceLuvr · 2026-10-23