Loss-Complexity Landscape and Model Structure Functions

Abstract:We develop a framework for dualizing the Kolmogorov structure function $h_x(\alpha)$, which then allows using computable complexity proxies. We establish a mathematical analogy between information-theoretic constructs and statistical mechanics, introducing a suitable partition function and free energy functional. We explicitly prove the Legendre-Fenchel duality between the structure function and free energy, showing detailed balance of the Metropolis kernel, and interpret acceptance probabilities as information-theoretic scattering amplitudes. A susceptibility-like variance of model complexity is shown to peak precisely at loss-complexity trade-offs interpreted as phase transitions. Practical experiments with linear and tree-based regression models verify these theoretical predictions, explicitly demonstrating the interplay between the model complexity, generalization, and overfitting threshold.

Information Theory (cs.IT); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Mathematical Physics (math-ph)

arXiv:2507.13543 [cs.IT]

(or arXiv:2507.13543v5 [cs.IT] for this version)

2026 J. Phys. A: Math. Theor. 59 145204

https://doi.org/10.1088/1751-8121/ae58d5 DOI(s) linking to related resources