Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion
This is an open problem for the machine learning community, aiming to bridge the gap between continuous generalization and discrete algorithmic reasoning.
The paper identifies that deep learning lacks inductive bias for algorithmic complexity minimization, failing to extrapolate discrete algebraic rules. It proposes Cayley-table completion as a testbed and challenges the community to establish exact recovery bounds and generalize flatness priors to discover discrete algorithmic axioms.
Modern statistical learning theory and deep learning characterize generalization primarily in terms of continuous capacity control (e.g., norm-based regularization, margin maximization, low-rank bias). While highly successful in continuous domains, deep learning consistently fails to extrapolate exact algorithmic or discrete algebraic rules, reflecting a missing inductive bias toward algorithmic complexity minimization. We propose the Cayley-table completion as the canonical testbed for this missing bias, serving as the discrete algebraic counterpart to matrix completion. Just as matrix factorization combined with weight decay yields an implicit geometric bias toward low linear rank, recent results demonstrate that operator-valued tensor factorizations paired with a flatness prior yield an implicit algorithmic bias toward exact discrete associativity. We pose the open problem of establishing formal exact recovery bounds for Cayley-table completion, and challenge the community to generalize continuous flatness priors to autonomously discover broader discrete algorithmic axioms without combinatorial search.