{"id":"arxiv/2610.18154","url":"https://arxiv.org/abs/2610.18154","tags":["cs.LG","math.GR","stat.ML"],"score":0,"title":"Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension","domain":"cs.LG","source":"arxiv","authors":["Xiaoyu Li"],"reviews":0,"subject":"cs.LG","summary":"We study learning an unknown element $g$ of a group acting with finite orbits on a countable set, from examples $(x,gx)$. After a sample on $A$, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of $A$, and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}