Summary
arXiv:2511.23152v5 Announce Type: replace-cross Abstract: Discovering discrete algebraic structures from data is a fundamental challenge in machine learning. We ask how continuous learning objectives can favor functional compression---representing data through shared algebraic composition rather than low-rank representations. We analyze the global optima of a canonical factorization model for algebraic completion (recovering finite binary operations) that demonstrated a preference for group operations. We measure algebraic complexity by the infimum of parameter sensitivity under exact reconstruction. We establish a universal complexity floor, whose attainment forces geometric alignment and unitarity of the latent representations. At the floor, input representations compose into the corresponding output representations; their reuse across the operation table propagates these local identities to enforce a globally shared algebraic structure. If the floor is not attained, a positive gap s…
Original text(via arXiv stat.ML)
Computer Science > Machine Learning
Title:Functional Compression as Occam's Razor: Algebraic Complexity from Sensitivity Minimization
Abstract:Discovering discrete algebraic structures from data is a fundamental challenge in machine learning. We ask how continuous learning objectives can favor functional compression---representing data through shared algebraic composition rather than low-rank representations. We analyze the global optima of a canonical factorization model for algebraic completion (recovering finite binary operations) that demonstrated a preference for group operations. We measure algebraic complexity by the infimum of parameter sensitivity under exact reconstruction. We establish a universal complexity floor, whose attainment forces geometric alignment and unitarity of the latent representations. At the floor, input representations compose into the corresponding output representations; their reuse across the operation table propagates these local identities to enforce a globally shared algebraic structure. If the floor is not attained, a positive gap separates it from the feasible infimum. For cancellative operations, floor attainment forces the model's latent representation to be an injective homomorphism, equivalent to the target being isotopic to a group. In this case, every global minimizer is equivalent to the underlying group's unitary left-regular representation, up to isotopy and unitary gauge, resolving the central conjecture of Huh (2025). For non-cancellative operations, floor attainment forces exact structural redundancies (identical rows or columns) and is equivalent to a unitary factorization of the target's row- and column-reduced table with orthonormal output matrices, yielding the fewest distinct input matrices compatible with exact reconstruction. The resulting cancellative table then embeds in a group-isotope table. This analysis reveals a structural bias toward functional compression: at the sensitivity floor, algebraic composition of latent representations implements the target operation.
| Comments: | 28 pages, 3 figures. Version 5: major revision, adding results for arbitrary binary operations, positive-gap theorems, and Lean 4 formalizations of the main theoretical results |
|---|
| Subjects: | Machine Learning (cs.LG) ; Disordered Systems and Neural Networks (cond-mat.dis-nn); Optimization and Control (math.OC); Representation Theory (math.RT); Machine Learning (stat.ML) |
| Cite as: | arXiv:2511.23152 [cs.LG] |
| (or arXiv:2511.23152v5 [cs.LG] for this version) |
| https://doi.org/10.48550/arXiv.2511.23152 arXiv-issued DOI via DataCite |
Submission history
The text above was extracted automatically from the source page and may miss images, tables or code blocks. The original is authoritative.
Published by arXiv stat.ML
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗