Sharpening Occam's Razor
<|reference_start|>Sharpening Occam's Razor: We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to:   (i) Obtain better sample complexity than both length-based and VC-based versions of Occam's razor theorem, in many applications.   (ii) Achieve a sharper reverse of Occam's razor theorem than previous work.   Specifically, we weaken the assumptions made in an earlier publication, and extend the reverse to superpolynomial running times.<|reference_end|>
@article{li2002sharpening,
    title={Sharpening Occam's Razor},
    author={Ming Li (Univ. Waterloo), John Tromp (CWI), and Paul Vitanyi (CWI and
  University of Amsterdam)},
    journal={arXiv preprint arXiv:cs/0201005},
    year={2002},
    number={CWI Manuscript 1994},
    archivePrefix={arXiv},
    eprint={cs/0201005},
    primaryClass={cs.LG cond-mat.dis-nn cs.AI cs.CC math.PR physics.data-an}
}