Learning Group Elements from Group Actions: Natarajan Dimension and the Abel-Ruffini Threshold

Group theory and statistical learning theory may seem to lie at opposite ends of the mathematical spectrum, but a new paper reveals a surprisingly deep correspondence between the two. The research addresses a core question: when a group $g$ is known to act on a countable set with finite orbits, how can the unknown group element be learned from samples $(x, gx)$? The answer unexpectedly weaves together Galois theory, empirical risk minimization, and combinatorial dimension theory.

From Samples to the Galois Correspondence

The paper's central insight rests on an elegant correspondence. Given a sample set $A$, all hypotheses consistent with the sample form precisely a coset—specifically, the restriction of some coset of the pointwise stabilizer of $A$. This means the sample effectively "forces" all labels of the points fixed by the stabilizer.

For the special case of Galois groups, this correspondence takes on a more concrete mathematical form: the set of consistent hypotheses forms exactly the field generated by the data. This finding endows the combinatorial dimensions in learning theory with group-theoretic meaning—they become complete invariants of the group.

Pointwise stabilizer is a fundamental construction in group action theory. Given a group $G$ acting on a set $X$, for a subset $A \subseteq X$, its pointwise stabilizer is defined as $\mathrm{Stab}(A) = {g \in G : gx = x, \forall x \in A}$, i.e., the subgroup consisting of group elements that fix every point in $A$. Unlike pointwise fixing, the setwise stabilizer only requires that $A$ be preserved as a whole. In Galois theory, $A$ corresponds to a set of algebraic elements adjoined to the base field, and the pointwise stabilizer is precisely the subgroup of automorphisms fixing the subfield generated by these elements—this is the manifestation of the reverse inclusion between fields and groups in the Galois correspondence. The paper uses this structure to show that the sample $A$ compresses all consistent hypotheses into a coset of $\mathrm{Stab}(A)$; the sample therefore uniquely determines all labels of the points fixed by the stabilizer, and the learning problem is thereby transformed into a coset identification problem.

Combinatorial Dimensions as Group Invariants

Through this Galois correspondence, the paper derives several exact equivalences between multiclass dimensions and group-theoretic quantities. The DS dimension (Daniely-Shalev-Shwartz dimension) and the graph dimension both equal the height of the group; the Littlestone dimension corresponds to the length of the longest redundancy-free sequence; and the teaching dimension is equivalent to the minimal base size.

These equivalences are not merely formal analogies; they reveal the structural role that symmetry plays in the learning process. The algebraic properties of the group directly determine the intrinsic complexity of the learning problem, and vice versa.

Symmetry Makes ERM Optimal

The paper proves a powerful result within the framework of deterministic learners: symmetry makes empirical risk minimization (ERM) an optimal strategy. Specifically, on non-degenerate classes, every consistent learner—regardless of how it breaks ties—achieves the optimal realizable sample complexity, up to a constant factor. For online learning, every consistent online learner likewise achieves the optimal regret bound.

In the agnostic learning setting, the results are equally satisfying: the gap between the sample complexity of every ERM and the known lower bound is at most the ratio of the DS dimension to the Natarajan dimension, multiplied by a constant. This means that for group classes with comparable dimensions, ERM is nearly the optimal universal strategy.

Natarajan Dimension and the Abel-Ruffini Threshold

One of the paper's deepest findings concerns the exact computation of the Natarajan dimension. For finite Galois extensions over countable fields, the Natarajan dimension equals a group invariant—the coset-cube number—whose value is at least the number of complement factors in any chief series of any subgroup.

This result leads to a beautiful dichotomy: for every solvable Galois group, the DS dimension and the Natarajan dimension coincide exactly. But for the Galois groups $A_5$ and $S_5$ of the quintic equation, the two dimensions exhibit gaps of $2<3$ and $3<4$ respectively, and $A_5$ is the smallest group exhibiting such a gap.

Even more striking is the connection to classical algebraic results: for the Galois group $S_n$ of the general degree-$n$ equation, the two dimensions coincide if and only if $n\le 4$—which, in characteristic zero, is precisely equivalent to the equation being solvable by radicals. This is the echo of the Abel-Ruffini theorem in learning theory. The paper also notes that this implication is one-directional: the simple group $\mathrm{PSL}(2,8)$, though non-solvable, does not produce a dimension gap.

The Natarajan dimension is a combinatorial measure of the complexity of a hypothesis class, introduced by Natarajan in 1989, commonly used to analyze sample complexity in multiclass classification and agnostic learning. Its definition is based on the number of "projection" patterns that the hypothesis class induces on sample points: for every sample set of size $m$, if the hypothesis class can induce at least $m^d$ distinct label assignments on it, then the dimension is at least $d$. Unlike the VC dimension, which allows arbitrary binary patterns, the Natarajan dimension concerns the upper bound on the diversity of multiclass labels. In the paper's Galois setting, this dimension corresponds precisely to a group-theoretic quantity—the coset-cube number—namely the maximum independence number of triple coset combinations of the form $gH_1 \times gH_2 \times gH_3$. It measures the degree to which group elements remain "free" under sample constraints; thus solvable groups, being structurally restricted, have lower dimensions that coincide with the DS dimension, while non-solvable groups exhibit dimension gaps.

A chief series is a normal series used in group theory to decompose group structure, requiring that adjacent quotient factors all be minimal normal subgroups. For a finite group $G$, a chief series takes the form $1 = G_0 \triangleleft G_1 \triangleleft \cdots \triangleleft G_k = G$, where each layer $G_{i+1}/G_i$ is a characteristically simple group. The "number of complement factors" mentioned in the paper refers to the number of complementary subgroups of $G_i$ in $G_{i+1}$ in the group extension $1 \to G_i \to G_{i+1} \to Q \to 1$, reflecting the degree to which the group extension is non-split. This quantity appears in the lower bound for the Natarajan dimension, indicating that even when the group itself is solvable, the richness of complement factors between layers in its chief series can raise the Natarajan dimension—thus explaining why certain non-solvable groups (such as $\mathrm{PSL}(2,8)$) exhibit no dimension gap, yet the existence of dimension gaps remains highly correlated with solvability.

Dimension Analysis for Further Group Classes

The paper also extends the analysis to classical group classes. For linear, orthogonal, and unitary maps over $\mathbb{R}^d$ or $\mathbb{C}^d$, both dimensions equal $d$—the dimension is entirely determined by the dimension of the ambient space. Furthermore, the paper proves that a two-fibered pseudo-cube is a union of disjoint Natarajan cubes if and only if its monodromy group is abelian.

Together, these results paint a picture: the structural properties of groups—solvability, abelianness—are precisely reflected in the complexity of learning problems through the presence or absence of dimension gaps.

A two-fibered pseudo-cube is a model in combinatorial and geometric group theory describing certain finite covering spaces or poset structures, in which each vertex fiber contains at most two elements. The paper proves that such a structure is a union of disjoint Natarajan cubes if and only if its monodromy group is abelian. The monodromy group is a central concept in covering space theory or fiber bundle theory, referring to the group generated by the permutations experienced by points in a fiber as one moves along closed paths. It characterizes the global symmetry of the fibration structure. This theorem shows that the desirable property of a pseudo-cube being decomposable into independent Natarajan components—a favorable property in terms of learning complexity—is exactly equivalent to the abelianness of the monodromy group, once again confirming the paper's thesis: the structural properties of groups leave precise fingerprints in learning theory through dimension decomposition behavior.

Why This Matters

This work is valuable on multiple levels. Theoretically, it establishes a rigorous bridge between Galois theory and statistical learning theory, allowing mature classification tools from group theory to be used to analyze the complexity of learning problems. Practically, the ERM optimality results provide theoretical guarantees for practitioners using ERM—at least for problems with rich symmetry, they need not worry about the existence of significantly better learning strategies.

The appearance of the Abel-Ruffini threshold hints at a deeper space for conjecture: there may exist broader connections between solvability, long studied in classical algebra, and the dimensional relationships of modern learning theory than the known results suggest.

One-line Summary

New research reveals a deep correspondence between learning group actions and Galois theory, with dimension gaps precisely characterizing solvability.

Paragraph Summary

This article introduces a new study that deeply connects group theory with statistical learning theory. When a group is known to act with finite orbits on a countable set, the problem of learning group elements from samples $(x, gx)$ is shown to have a precise correspondence with Galois theory: consistent hypotheses with the sample form a coset of the pointwise stabilizer, and for Galois groups, they form the field generated by the data. This correspondence makes the DS dimension, Littlestone dimension, and teaching dimension equal to the group's height, longest redundancy-free sequence length, and minimal base size, respectively. The paper further proves that symmetry makes ERM an optimal strategy, and exactly computes the Natarajan dimension as the coset-cube number. Most strikingly, the Abel-Ruffini threshold reappears: for $S_n$, the DS dimension and Natarajan dimension coincide if and only if $n \le 4$, corresponding to solvability by radicals, while $A_5$ is the smallest group exhibiting a dimension gap.