Technical Summary: Separating Geometric and Algorithmic Compression via Cayley-Table Completion

1. Problem Statement

The paper identifies a fundamental theoretical divide in Statistical Learning Theory (SLT) between Geometric Compression and Algorithmic Compression.

• Geometric Compression: Modern deep learning relies on continuous capacity control mechanisms (e.g., norm-based regularization, margin maximization, low-rank bias). These methods assume parsimonious concepts lie on smooth manifolds or low-dimensional linear subspaces. While successful for continuous data, this paradigm fails to extrapolate exact algorithmic or discrete algebraic rules.
• Algorithmic Compression: Classical learning theory (PAC Learning, Occam's Razor, MDL) framed learning as the recovery of exact, minimal logical rules. However, optimizing discrete algorithmic complexity is generally NP-hard, leading modern SLT to largely abandon it.
• The Gap: Deep learning lacks an inductive bias toward algorithmic complexity minimization. Consequently, neural networks struggle with tasks requiring exact discrete algebraic structures (e.g., length generalization on algorithmic tasks, discovering exact symmetries), often resorting to brittle memorization rather than rule abstraction.

The paper proposes Cayley-table completion as the canonical testbed to address this missing bias. This task involves recovering a discrete binary operation (a group or quasigroup structure) from partial observations, serving as the discrete algebraic counterpart to matrix completion.

2. Methodology and Theoretical Framework

The Canonical Task: Cayley-Table Completion

Unlike Matrix Completion, which seeks low linear rank (where rows are linearly dependent), Cayley tables of groups are Latin squares where rows are permutations of one another. This structure inherently precludes linear redundancy. The true parsimony of algebraic groups stems from the associativity axiom, which constrains the global structure to minimize structural description length.

Operator-Valued Tensor Factorization

To solve this without intractable combinatorial search, the paper utilizes a continuous, differentiable approach based on recent work by Huh (2025):

1. Tensor Representation: The binary operation $\circ$ on a finite set $Q$ of size $n$ is represented by a structure tensor $\delta \in \{0, 1\}^{n \times n \times n}$, where $\delta_{abc} = 1$ if $a \circ b = c$.
2. Factorization Model: The tensor is modeled via an operator-valued factorization:
   $$T_{abc}(\Theta) := \frac{1}{n} \text{Tr}(A_a B_b C_c)$$
   where $\Theta = (A, B, C)$ and $A_a, B_b, C_c$ are $n \times n$ matrix slices (linear operators).
3. Flatness Prior: The optimization objective includes a flatness prior that penalizes the trace of the Hessian of the empirical reconstruction loss:
   $$H(\Theta) := \text{Tr}\left(\nabla^2 \sum_{(a,b,c) \in \Omega} (T_{abc}(\Theta) - \delta_{abc})^2\right)$$

Variational Characterization

The objective function $H(\Theta)$ decomposes into two critical components that induce discrete properties:

• Geometric Alignment (Collinearity): Enforces the associativity axiom.
• Inverse $\ell_2$ Penalty: Acts as an exact inverse rank penalty within the collinear manifold.

Crucially, this mechanism drives parameters toward full-rank unitarity, diametrically opposing the low-rank bias of standard geometric compression.

3. Key Results and Proofs

The paper presents the following theoretical findings based on the proposed framework:

• Exact Recovery Bound: In the fully-observed limit, the geometric infimum $H_{\inf}(\delta) := \inf_{T(\Theta)=\delta} H(\Theta)$ is proven to be an exact, differentiable measure of algebraic complexity.
• Lower Bound: The objective establishes an absolute lower bound $H_{\inf}(\delta) \ge 3|\delta|$ (where $|\delta| = n^2$).
• Characterization of Minimizers: This bound is attained if and only if the target operation is isotopic to a group. In this case, the global minimizer uniquely characterizes the regular representation of the underlying group (up to unitary gauge).
• Proof of Concept: This provides a formal proof that continuous gradient-based optimization can natively discover discrete algebraic axioms (specifically associativity) without resorting to combinatorial search.

4. Open Problems Posed

The paper challenges the community to formalize the separation between geometric and algorithmic compression through two specific open problems:

1. Open Problem 1 (Formal Separation): Establish a strict separation theorem between geometric capacity control (e.g., Rademacher complexity, margin bounds) and algorithmic compression. The goal is to characterize hypothesis classes (e.g., discrete algebraic rules) where purely geometric generalization bounds are provably vacuous (requiring exponential sample complexity), while differentiable algorithmic complexity measures yield tight, polynomial guarantees.
2. Open Problem 2 (Sample Complexity of Cayley-Table Completion): Formally establish an exact recovery guarantee for the flatness-regularized tensor factorization. Specifically, can it be proven that the global minimizer perfectly completes the group table with high probability given only $O(n \log n)$ uniformly sampled entries? This would contrast with standard matrix completion theory, which yields vacuous bounds exceeding $O(n^2)$ for full-rank structures.

5. Significance and Limitations

Significance

The paper argues that formalizing and solving the Cayley-table completion problem would:

• Provide a rigorous mathematical bridge between the classical logic-driven era and the modern geometry-driven era of SLT.
• Offer a proof-of-concept that carefully designed, purely continuous priors can compel gradient descent to optimize exact combinatorial properties natively.
• Address the critical missing foundation in SLT regarding the territories where geometric surrogates fail and algorithmic compression succeeds.

Limitations and Current State

• Partial Results: The paper acknowledges that while existence proofs and landscape analyses exist (Huh, 2025), the foundational question of the exact theoretical boundary remains open.
• Neurosymbolic Limitations: Current neurosymbolic approaches are critiqued for either relaxing logic into approximate probabilities (failing to recover rigid structures) or relying on external symbolic engines to handle logical constraints (failing to achieve native algorithmic discovery).
• Scope: The paper focuses on establishing the theoretical framework and posing the open problems. It does not claim to have solved the sample complexity bounds (Open Problem 2) or the general separation theorem (Open Problem 1) within this text, but rather positions them as the necessary next steps for the field.