Loss-Complexity Landscape and Model Structure Functions
This provides a theoretical foundation for understanding model complexity and generalization in machine learning, though it appears incremental in applying existing mathematical frameworks to ML contexts.
The paper developed a framework to dualize the Kolmogorov structure function using computable complexity proxies, establishing an analogy between information theory and statistical mechanics with explicit proofs of Legendre-Fenchel duality. Experiments with linear and tree-based regression models verified theoretical predictions about loss-complexity trade-offs, showing phase transitions where complexity variance peaks at overfitting thresholds.
We develop a framework for dualizing the Kolmogorov structure function $h_x(α)$, 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.