This is an announcement of the first two papers in a series on Computational Algorithmic Statistics (CAS).
Algorithmic statistics goes back to Kolmogorov, who in 1974 proposed a reformulation of statistics that does not rely on probabilistic assumptions. A model for an individual string is a finite set containing it, and a good model is simple with a typical element of it. The best models are uncomputable, so any practical method has to choose from a restricted class of candidate models. The CAS series studies the class given by symmetry.
The goal of the series is an algorithm, based on reinforcement learning, that searches for strong models: models computed from the data by a total program. The problem is therefore a form of program search. The first two papers lay the mathematical foundations for this search.
CAS I: A Geometric Coding Theorem treats symmetries as programs. A string is described by a symmetry that has it as its unique fixed point. For fix-retractable groups the resulting symmetry prior satisfies a coding theorem, .
CAS II: Orbits as Models treats symmetries as hypotheses. A group's orbits sort all strings into classes, and the orbit containing is the model. The paper introduces the -structure function and -sophistication, which measure which part of the regularity of is symmetric. It also gives the space of strong models coordinates, a moduli space with explicit moves, in which a search agent can move. The maximal gap theorem sets the limits: any space of symmetry hypotheses small enough to search is small enough to miss simple structure.
Later papers in the series move towards learned search, first with reinforcement learning and then guided by LLMs. Comments and pointers to related work are welcome.
This is an announcement of the first two papers in a series on Computational Algorithmic Statistics (CAS).
Algorithmic statistics goes back to Kolmogorov, who in 1974 proposed a reformulation of statistics that does not rely on probabilistic assumptions. A model for an individual string
The goal of the series is an algorithm, based on reinforcement learning, that searches for strong models: models computed from the data by a total program. The problem is therefore a form of program search. The first two papers lay the mathematical foundations for this search.
Later papers in the series move towards learned search, first with reinforcement learning and then guided by LLMs. Comments and pointers to related work are welcome.
Links