Vovk note yields concentration theorem for complexity–fit tradeoff
_onionesque · x · 2026-11-22
Discussing a short note by Vladimir Vovk whose substantive result is a concentration theorem for the tradeoff between model complexity (à la Kolmogorov complexity) and goodness of fit.
- The author finds it broadly reminiscent of the "regularity philosophy" descending from Szemerédi's regularity lemma.
- Key difference: in the regularity-lemma setting the pseudorandom component can co-exist with algorithmic compressibility, but not in Vovk's framework.
Relevant to learning theory and the intersection of algorithmic information theory and statistical modeling.
Related event: Vovk's New Paper: Universal Measure of Nonrandom Objects Vanishes(2 posts)→
More from Research
- One photo, 8 VLAs, only 3 correct: ERQA embodied-reasoning benchmark questioned — giffmana · 2026-11-22
- Fleuret: treat AI as oracles, not explainers — human-comprehensible math will be negligible — francoisfleuret · 2026-11-22
- Vovk paper shows probabilistically nonrandom objects have vanishing universal measure — _onionesque · 2026-11-22
- AI generates a Riemann proof, AI generates the rebuttal—and it scores 100% AI — zetalyrae · 2026-11-22
- François Fleuret asks: is the gradient Japanese? It never refuses to give you a direction — francoisfleuret · 2026-11-22
- Hat Matrix Explained: How Much Leverage Does Each Data Point Have in Least Squares? — RobertTLange · 2026-11-22