acceptodds
Under review as a conference paper at ICLR 2027

Exact Group Recovery from Subquadratic Observations

Abstract

Recovering a finite group operation table from partial observations presents a fundamentally unusual completion task. Unlike classical matrix completion, which relies on a low-rank prior and geometric incoherence to interpolate missing entries, completing a group table requires enforcing an associativity prior and exploiting the discrete Latin-square property, which guarantees uniform marginals without structural incoherence assumptions. We resolve this by analyzing a canonical operator-valued factorization model under gradient-sensitivity regularization. This objective forces the model's latent matrix embeddings to become unitary and satisfy the exact multiplication laws of the observed pairs once a basic coverage threshold of observations is reached (coupon collector). By identifying the structural observation patterns required to propagate these localized relations into exact global recovery, we establish sub-quadratic sample complexity bounds under two regimes. Under active query selection, a presentation-dependent scaffold deterministically recovers the complete table in at most queries, where counts the pairs needed to close the relator cycles, by tracing a Cayley spanning tree and the group's defining relators to algebraically synchronize the representations. Under passive Bernoulli sampling, expected observations guarantee exact table recovery with high probability, as overlapping observations form connected graphs that globally propagate the associativity prior. In both regimes, evaluating all negative candidate outputs for just one observed input pair provides the necessary anchor to eliminate degenerate solutions and select the regular representation. These bounds establish the first closed theory of partial-observation learning for general finite groups, verified formally in Lean 4 and empirically across 32 group families.

Primary area:
learning theory
Keywords:
Sample Complexity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_RuxLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3(+1)
Soundness
1
Read review
Paper summary

This paper studies the exact recovery of finite-group multiplication tables from partial observations using the HyperCube model with gradient-sensitivity regularization. The authors establish conditions under which every global minimizer recovers the complete multiplication table. For active sampling, they derive a deterministic bound of $3n-2+|R_{\mathrm{indep}}|$observations based on group presentations. For passive Bernoulli sampling, they establish a sample complexity of $O(n^{3/2}\sqrt{\log n})$using connectivity of comparison graphs. The theoretical results are supported by Lean 4 formalization and numerical experiments on 32 finite groups.

Critical strengths

The paper establishes nontrivial subquadratic sample complexity guarantees for exact recovery of general finite groups, including non-Abelian groups. The relative-comparison graph approach provides an interesting technique for propagating local algebraic relations into global recovery guarantees without assuming shared embeddings.

Critical weaknesses

These theoretical guarantees are limited to exact global minima and do not address the convergence or stability of the optimization process. Furthermore, there is a significant gap between theoretical bounds and empirical recovery thresholds. Moreover, using test accuracy as a criterion for early stopping in experiments may introduce evaluation bias, while active sampling methods require prior knowledge of the target population's structure.

Questions for authors

Q1: Can the theoretical guarantees be extended to approximate global minimizers? Is there any evidence that gradient-based optimization can reliably reach solutions satisfying these guarantees? Q2:The theoretical sample complexity bounds are substantially larger than the empirical recovery thresholds. Could the authors explain the main sources of this gap and whether the bounds can be improved?

4 comments

Thank you for highlighting the comparison-graph technique and for the questions about stability, the empirical gap, and active sampling.

W1 / Q1: Can the guarantees extend to approximate global minimizers? Is there evidence that gradient-based optimization reliably reaches them?

A: For approximate global minimizers, yes. Joint Response 1 states qualitative stability for unrestricted complex factors and the finite-budget training results. Appendix O proves that near-minimizing sequences are bounded, without assuming a bounded parameter domain, then uses a convergent subsequence and continuity to establish stability. This does not establish which initializations or iteration budgets reach the required objective gap.

W2 / Q2: What causes the gap between the theoretical bound and empirical thresholds, and can the bound be improved?

A: Each comparison edge requires two observations, giving probability p2p^2; controlling dependencies between comparison edges and bounding the probability of disconnected comparison graphs yields the sufficient condition. Sharper connectivity estimates or weaker sufficient conditions could improve it. The necessary Bernoulli coverage floor is only Ω(nlog⁡n)\Omega(n\log n), so the optimal passive rate remains open. Joint Response 2 gives the numerical comparison and empirical qualifications.

W3: Does stopping based on test accuracy bias the evaluation?

A: No change to the recovery conclusions was found in our runs. Training is highly stable: test loss decreases monotonically rather than deteriorating after a favorable intermediate checkpoint. We report accuracy at termination, not a selected peak-accuracy checkpoint. In our runs, internal algebraic alignment and unobserved accuracy improve on similar timescales, consistent with the grokking transition. Accordingly, stopping based on local algebraic alignment, without consulting unobserved labels, gives the same convergence outcomes. Joint Response 3 explains the compute-saving stopping rules.

W4: Active sampling requires prior knowledge of the target structure.

A: Yes, constructing the teaching set requires prior knowledge of the target structure. The revised text explains why we consider both regimes: target-aware teaching exposes the generalization mechanism by identifying which observations suffice for full-table reconstruction and enabling controlled relation ablations (Section 4.2; Table 1). The learner receives only labeled pairs and minimizes the same objective in both regimes. Passive Bernoulli sampling requires no target-structure knowledge.

AuthorsOpenReview ↗

Clarification of Soundness Concerns

Dear Reviewer RuxL,

Following our responses above, we would appreciate clarification of any remaining soundness concerns. Appendix O extends recovery to sufficiently near-global minimizers on each fixed covered recovering observation set, over unrestricted complex factors. The main recovery results are formally verified in Lean, with the scope and audit documented in Appendix M. Our rebuttal also addresses the empirical accuracy criteria and label-dependent stopping protocol.

Our theoretical contribution is an objective-level recovery guarantee, including its extension to sufficiently small objective gaps. Proving convergence of a particular optimizer is not required to establish these guarantees; it would be an additional algorithmic result about computational attainability, outside the scope of this paper, rather than a missing step in the recovery theory.

Could you clarify whether these responses resolve your soundness concerns, or identify any remaining specific issue in the mathematical claims, proofs, or experimental conclusions?

I appreciate the authors’ response and their careful answers to my questions. I have increased the presentation scores. However, I still believe my initial overall rating reflects my assessment of the paper, and therefore I would like to keep it.

Thank you for considering our response and updating the presentation assessment. We understand that your overall assessment may remain unchanged. Could you clarify which specific concerns continue to motivate your soundness assessment? In particular, is there a mathematical claim, proof step, or experimental conclusion that you consider incorrect or insufficiently supported after our responses? Identifying the unresolved issue would help us address it directly.

Reviewer_f6xWOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies Exact Group Recovery (Caley Table Recovery) under the HyperCube Reconstruction model, which penalizes a Jacobian-based objective function. This paper follows up on the paper by Huh, Horesh, Jeong which studied “complete observation” of the table and where they concluded that the best solution in this case is the group’s regular representation. The current paper takes the next logical step of looking at “partial observation” of the table under the same model, and studying how many such observations are required to fill the whole table correctly (with high probability).

The paper essentially shows that (these are my digestion from the paper; see Cons Point 2 and 3 below):

  1. If the random sample is just large enough that every symbol shows up at least once as a left input, as a right input, and as an output (about nlog⁡(3n/δ)n \log(3n/\delta) samples, by a coupon-collector argument), then every best solution has all of its matrices unitary, up to one common scaling factor, and full rank. This doesn’t yet say anything about the unobserved entries. It only says that the model’s matrices are forced into the “right shape”, which is the starting point for everything else.
  2. Now if we are allowed to choose what to show the model, then about 3n entries suffice (there is an additional term that depends on the presentation of the group) to teach the model the correct representation (the regular representation).
  3. On the other hand, if the model is shown only uniformly chosen random entries, then O(n3/2log⁡(n2/δ))O(n^{3/2}\sqrt{\log(n^{2}/\delta)}) expected samples suffice for every best solution to fill in the whole table correctly with probability at least 1-\delta.

A key ingredient that the paper introduces is the anchored program: pick a single observed input pair, and besides asking the model to give the correct output a score of 11, also ask it to give each of the n−1n−1 wrong outputs a score of 00. Without any “wrong answer” constraints, there is a trivial solution (all matrices equal to the same multiple of the identity) that fits every observed entry but doesn’t encode the group at all. This one row of n−1n-1 zero constraints is enough to rule that out and force the regular representation (Theorem 7). Alongside this, the paper introduces two more concepts: the teacher-chosen scaffold (Section 4.2) and the comparison-graph argument for random samples (Section 4.5), and does a lot of algebraic and analytic analysis to get to its desired results.

Critical strengths

The results are very interesting (although not surprising in hindsight) given the push towards understanding what neural networks and other large language models really learn about groups when trained on partially observed tables.

But I am afraid this is where the pros stop. See below.

Critical weaknesses

The paper is not well written. And I think I will talk more about that.

  1. I should start at the introduction then. Section 1 does leave a lot to desire, because this is where HyperCube, the paper’s main model under scrutiny, is first introduced and the reader can’t be expected to know what it is (and even if they have read the Huh, Horesh, Jeong paper, a quick refresher here is warranted). But in any case, let us now assume one gets across Section 1 unimpeded and has reached Section 1.1.
  2. Section 1.1 is in my opinion the worst offender. This is where readers get to see what the paper is all about, what the paper is claiming to show. But I couldn’t even understand what it was saying, even informally, unless I read the rest of the paper several times and revisited this part. More precisely, the reader runs into “metric locking”, “three-slot coupon-collector threshold”, “scaled-unitary slices”, “identity cross”, “Cayley spanning tree”, “presentation relators”, “R_indep” and “output fiber”, all in a few lines. None of these has been explained at that point and most aren’t standard terms. If I have to point things out: “Three-slot coverage” is only defined on page 4 (line 196), even though the abstract, introduction, summary and related work have already used it. The identity cross, scaffolds and spanning tree are defined on page 5 (Definition 5). “Output fiber” is never properly defined, it just appears in Theorem 7 on page 6. So in practice the first two pages can only be understood by going back after reading pages 4 to 6, with again, Section 1.1 being the hardest to read even though it's the first place where a paper gets to keep its reader.
  3. Continuing with Section 1.1, the paper does not really say in simple words what it found. I looked for one simple sentence of the main result and couldn’t find it. The above digestion is something I had to come up with on my own, and that’s not expected from a paper at a top-tier conference.
  4. Related work is fine, nothing much to talk about here.
  5. Problem setting, Section 3. It can be followed more-or-less with some amount of non-trivial effort from the reader (considering myself a representative) but the main issue here is that there are four optimization problems floating around and no real guide on how to follow them. One under exact-fit constraints, one defined as the positive program, one as the anchored program, and one with the regularized objective. Now, where one gets lost is that Theorem 3 uses one, Theorem 4 another, Theorem 9 a third, and Corollary 11 “transfers” to the fourth. This is quite fixable though. A small table (program, constraints, which theorem uses it, what it guarantees) would fix much of the confusion. A forward reference to this table, with a short plain-language explanation, should be enough.
  6. Section 3 (Section 3.2 really) also brings in bolded phrases like “metric locking and algebraic homomorphism ” and “character orthogonality and faithfulness”, but at this point, I am not sure what they are doing here (they retroactively makes sense after one has read the paper, but that’s not how a reader encounters them).
  7. The rest of the main paper is doing the analysis, which at a cursory glance looks sound to me, so I don't have much to say about that here. As I said, the results are very interesting to me, but I am not sure what to take away from this paper other than the results. I would have loved to deeply understand the mechanisms behind the results, but it's all very opaque.
  8. One thing did pique my interest: the proof of Lemma L.14, specifically the statement “Union-bound their failure events; independence between different slot-label classes is neither true in general nor needed. ”. Union bound never requires independence, so this remark is unnecessary and suggests the proofs were not carefully edited. There are similar remarks elsewhere (last line of proof of Theorem 9 “These are deterministic consequences of the same good-mask event, so no union bound over matrices, minimizers, or choices of anchor is required.”, etc).
Questions for authors

I have no questions really, other than asking the authors to make the presentation and exposition better.

2 comments

Thank you for the detailed reading and for explaining where the exposition obscures the results and their mechanisms.

W1: The introduction does not adequately explain the model or state the main result in accessible terms.

A: We have rewritten the introduction to explain the model before presenting the main results and to foreground the recovery mechanism. Section 2 provides the formal definitions and training objective. The Common Rebuttal summarizes the presentation changes.

W2: Section 1.1 accumulates unexplained technical terms and lacks a simple statement of the main result; the reader must return after reading the later definitions.

A: We have rewritten the former Section 1.1 summary as Section 1.2 to state the main result and recovery mechanism before introducing technical constructions. Specialized terms are defined where they enter the argument.

W3: The four optimization programs and their theorem dependencies are difficult to follow.

A: The revised main text focuses on the sensitivity-regularized squared-error objective used in training. The auxiliary constrained programs are defined and analyzed in the appendix. The positive program isolates local structure; the anchored program identifies the regular representation; the exact-fit program supports rigidity and minimum-count analysis. Following your suggestion, Table 2 in Appendix A lists each program's objective, constraints, and theorem roles, with a forward reference from Section 2.2.

W4: The roles of "metric locking and algebraic homomorphism" and "character orthogonality and faithfulness" are unclear when introduced. The results are interesting, but the mechanisms behind them remain opaque.

A: We have substantially rewritten Section 3 to explain what each ingredient contributes to unseen prediction, using descriptive headings for local alignment, propagation through shared operators, and output identification. Each step is motivated before the sample bounds are derived. The Core Message summarizes the mechanism.

W5: Remarks about independence and union bounds in the proofs are unnecessary and suggest insufficient editing.

A: We removed the two cited redundant qualifications from the coverage proof and the proof of constrained passive recovery (Corollary L.15). The probability argument is unchanged.

AuthorsOpenReview ↗

Clarification of Soundness Concerns

Dear Reviewer f6xW, We would appreciate clarification of one additional point regarding the soundness assessment. Your review states that the analysis “looks sound to me,” while the soundness rating indicates significant concerns. Could you clarify whether there is a specific concern about the correctness of a claim, assumption, or proof? The main recovery results are formally verified in Lean, with the scope, theorem correspondence, and axiom audit documented in Appendix M. We have also substantially revised the exposition to clarify the model, proof mechanism, and theorem dependencies. We would appreciate identifying any remaining technical issue so we can address it directly.

Reviewer_pkvyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper presents a theoretical analysis showing that a regularized matrix-factorization model can exactly recover finite group multiplication tables from subquadratically many observations, requiring O~(n1.5)\tilde{O}(n^{1.5}) random observations or approximately O(n)O(n) strategically selected observations for groups with sufficiently compact presentations.

The central theoretical result establishes that gradient-sensitivity regularization forces exact global minimizers to satisfy the underlying group representation structure, allowing observed multiplication relationships to determine unobserved entries. The authors establish sufficient recovery conditions using algebraic arguments and random graph connectivity, and provide formal verification of several results in Lean 4.

The results are empirically evaluated across 32 finite groups, with experiments showing that the model can achieve high prediction accuracy from a relatively small fraction of observed multiplication-table entries.

Critical strengths

The main strength of this paper is that it establishes a mathematically nontrivial sample-complexity guarantee for exact recovery of finite group multiplication tables. As far as I can verify, the central proof appears correct, and I appreciate that the authors provide a relatively complete theoretical analysis, including formal verification in Lean 4.

I also find the connection between gradient-sensitivity regularization and the recovery of algebraic structure somewhat interesting. In particular, the authors show how the regularization objective can force learned matrix representations to satisfy the underlying group multiplication laws, and how local relationships can propagate to unobserved entries. This is a potentially useful illustration of how structural inductive biases can enable generalization from incomplete observations.

Critical weaknesses

My biggest concern is that I struggle to understand the broader significance of this paper for machine learning, or why this particular result constitutes a substantive contribution to ICLR. While the mathematical analysis appears sound, this is fundamentally a specialized theoretical paper on recovering finite algebraic structures. I do not think the authors sufficiently explain what general insight we gain about representation learning, generalization, or the behavior of practical learning algorithms.

First, the central conclusion that finite group multiplication tables can be recovered from subquadratically many observations is somewhat expected, given the strong algebraic structure of finite groups. Indeed, the authors' own information-theoretic discussion demonstrates that group tables contain substantially less information than arbitrary multiplication tables. The interesting question is therefore what the proposed analysis teaches us beyond the fact that algebraic structure can reduce sample complexity. Unfortunately, I do not think the paper provides a particularly compelling answer. The results are specific to a carefully constructed matrix-factorization architecture with regularization designed to encourage group representations, and it is unclear how the insights would extend to more general machine learning problems.

Second, there is a significant gap between the theoretical guarantees and the actual learning process. The results characterize exact global minimizers of a highly nonconvex objective, but provide no guarantee that gradient-based training can find these solutions. This distinction is particularly important given the paper's connection to the literature on grokking, where the central question concerns how neural networks discover underlying structure during training. The paper establishes that the desired algebraic representation exists at the global optimum, but tells us relatively little about whether, when, or why practical learning algorithms discover it.

Third, I find the relationship between the theoretical and empirical results somewhat unsatisfactory. The theoretical recovery bound is extremely conservative over the range of group sizes studied. For example, for a group of order 128 and a 95% confidence guarantee, the sufficient condition requires observing approximately 83% of the table, while the empirical experiments report high accuracy from approximately 9.4% of the entries. While this is not a contradiction, since the theorem provides a sufficient condition, it raises the question of what the theoretical bound actually explains about the observed learning behavior. Moreover, the theoretical results establish exact recovery, whereas the principal empirical threshold is based on 95% prediction accuracy. The empirical scaling curve is also partially fitted to the observed data, limiting its value as independent validation of the theoretical characterization.

Relatedly, the experimental protocol uses early stopping criteria that depend on accuracy over unobserved entries. This would not be available in a genuine recovery setting, and further limits the interpretation of the experiments as demonstrating a practical learning procedure.

Finally, I found the paper somewhat poorly written. The presentation is unnecessarily complicated, and the extensive notation and technical exposition make it difficult to identify the main insight and understand why the results matter. There are also apparent signs of insufficient editorial attention, including duplicated text and placeholder material in the manuscript. I strongly believe that, particularly in this day and age of AI, how much effort authors put into communicating their results is just as important as the results themselves. If a reader has to read the paper three times or resort to AI assistance simply to understand its main contribution, then the paper is failing at a fundamental aspect of scientific communication.

Overall, I recognize the mathematical effort behind this work, and I do not have substantive objections to the correctness of the central theorem. However, I remain unconvinced that the result advances our understanding of machine learning sufficiently to warrant acceptance at ICLR. The paper establishes a technically interesting property of a specialized algebraic reconstruction model, but its broader scientific implications remain unclear.

Questions for authors

My main question is about the broader significance of the theoretical result. Beyond establishing that finite group multiplication tables can be recovered from subquadratically many observations, what fundamental insight does this paper provide about machine learning? In particular, how does the analysis advance our understanding of generalization or representation learning beyond this specific algebraic reconstruction problem?

Relatedly, can the authors clarify what their theory tells us about practical learning algorithms? The results apply to exact global minimizers, but the paper does not characterize whether gradient-based optimization reaches these solutions. Given the motivation from grokking and neural network generalization, I would be interested in understanding what conclusions can actually be drawn about the learning process.

Finally, how should we interpret the substantial gap between the theoretical sample-complexity bound and the empirical recovery thresholds? For the experimentally relevant group sizes, the theoretical sufficient condition requires substantially more observations than are needed in practice. Does the proposed analysis provide any meaningful prediction of practical recovery thresholds, or is its contribution primarily to establish the existence of an asymptotic subquadratic guarantee?

2 comments

Thank you for recognizing the mathematical analysis and for pressing us to clarify its machine-learning significance and limitations.

W1 / Q1: Beyond the low information content of group tables, what insight does the result provide about representation learning and generalization? Why this specialized model, and what are the broader implications?

A: Our analysis reveals the latent compositional regularities underlying algebraic data and shows how gradient-based learning can discover and generalize from them through a generic sensitivity objective. This provides a novel mechanism for learning discrete compositional structure. Remarkably, this establishes systematic generalization: recovery is independent of the training distribution (Corollary 5). This is an unusually strong generalization guarantee: under the recovery conditions, prediction is correct under every test distribution over the same symbols and operation, even when training and test supports do not overlap.

Such algebraic regularities also govern natural data through symmetries and compositions of transformations. For example, symmetries are described in the language of groups. An inductive bias toward groups could therefore enable deep learning models to discover latent symmetry structure in data, even when its action is not explicit in the observed coordinates. This contrasts with standard CNN/equivariant architectures, which require the symmetry action they enforce to be prescribed. Understanding this mechanism can help deep learning models discover symbolic and algebraic structures more efficiently and achieve systematic generalization.

W2 / Q2: What does the theory say about practical optimization and grokking, given that the objective is nonconvex?

A: Our theory characterizes recovery at global minima and sufficiently small objective gaps, not optimizer convergence or learning dynamics. Appendix O establishes the near-minimizer extension for fixed covered recovering observation sets. The 32-group benchmark demonstrates empirical convergence to the analytically known global minimum, within numerical precision. A theoretical account of convergence and grokking times remains open. Joint Response 1 summarizes the result and its scope.

W3 / Q3: Why is the sufficient bound so much larger than the empirical threshold? What does the fitted scaling curve validate, and are exact recovery and 95% accuracy comparable?

A: The main quantitative advance is the subquadratic sufficient rate O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}), rather than an optimized finite-size constant. Joint Response 2 explains the conservative bound, empirical support for the exponent over the tested range, and historical precedents for subsequent refinements. We deliberately use 95% mean unobserved accuracy to locate the empirical recovery transition, rather than choose a count comfortably inside the full-recovery regime. For all 14 benchmark instances with n≥36n\ge36, the smallest tested observation count reaching 95% mean accuracy also achieves 100% accuracy in every run (Appendix I).

W4: Early stopping uses unobserved accuracy, which is unavailable in a genuine recovery task.

A: The stopping rules save computation and time rather than select a favorable checkpoint. In our runs, internal algebraic alignment develops on a similar timescale to the improvement in unobserved accuracy, consistent with the grokking transition. Accordingly, stopping based on local algebraic alignment, without consulting unobserved labels, gives the same convergence outcomes. Joint Response 3 explains this relationship and the stopping protocol.

W5: The presentation is difficult to follow, with duplicated text and placeholder material.

A: We have substantially revised the manuscript to improve readability and make the main insight explicit, including rewriting the introduction and consolidating repeated material. The Common Rebuttal summarizes these revisions.

AuthorsOpenReview ↗

Clarification of the Recovery Guarantee and Scope

Dear Reviewer pkvy,

We would like to clarify one point in your description of the theoretical contribution. The result establishes recovery at every global minimizer, not merely the existence of the desired representation at a global optimum. It identifies when partial observations force the objective to determine all unseen products through shared algebraic composition. This characterizes the objective’s generalization bias beyond the fact that group tables admit compact descriptions. Appendix O also extends recovery to sufficiently small objective gaps.

Proving that a particular optimizer reaches the required gap would be an additional algorithmic result about computational attainability, outside this paper’s scope, rather than a missing step in establishing these recovery guarantees.

We would appreciate your assessment of whether this clarification addresses the distinction between the objective-level generalization mechanism established here and the separate question of optimization dynamics.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Common Rebuttal

We thank the reviewers for recognizing the general-group recovery guarantees and comparison-graph technique, and for identifying where the exposition needed improvement.

Core Message

Huh et al. (2025) established that sensitivity minimization under exact fitting of full operation tables favors group operations through shared algebraic composition. We show when this bias yields systematic generalization from partial observations, independently of the training distribution.

Under the stated observation conditions, the generalization mechanism has three steps:

  1. Sensitivity regularization enforces local composition. At every global minimum, the symbol matrices are scaled-unitary, and each observed product forces an algebraic identity among them.
  2. Shared operators extend these rules to unseen combinations. Sufficient overlaps, or observations encoding the defining relations, force the shared full-rank operators into one consistent composition across the whole table.
  3. Reconstruction loss on observed data distinguishes the output labels. Once global composition is established, the output scores at one observed pair rule out representations that collapse distinct outputs and determine all unseen scores.

For any observation-selection procedure, once the observed pairs satisfy the structural recovery conditions, every global minimizer recovers the complete operation (Corollary 5). Correct decoding therefore holds under every test distribution on the same symbols and operation, without matching training and test frequencies. This achieves functional compression through shared algebraic composition, rather than low-rank interpolation through linear dependencies.

We first establish recovery on a fixed observation set. Sample requirements follow by analyzing propagation through random overlaps and constructing target-aware observations that enforce the defining relations (Theorems 6 and 8). At fixed confidence, O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}) expected Bernoulli observations suffice for every finite group of order nn. Presentation scaffolds suffice with 3n−2+k3n-2+k pairs, where kk counts additional pairs enforcing generator relations; 3n−23n-2 pairs are necessary for recovery (Theorem 9).

Summary of Manuscript Revisions

In response to the reviews, we have substantially revised the exposition, strengthened the theoretical analysis, and extended the Lean 4 formalization:

  • Exposition: Reorganized the introduction and main argument to explain the model and recovery mechanism before the sample bounds, and clarified the roles of the four optimization programs.
  • Theory and formalization: Added recovery guarantees for approximate global minimizers and extended the Lean 4 development to cover the additional results.
  • Empirical interpretation: Clarified the accuracy criteria, limitations of finite-range scaling fits, and label-dependent termination protocol.

Terminology: In the main exposition, we replaced ambiguous names and labels with more descriptive wording:

  • "Active sampling" →\to "target-aware teaching".
  • "Gradient sensitivity objective" →\to "sensitivity-objective/regularization".
  • "Metric locking" →\to "local alignment".
  • "Character anchor" →\to "regular-representation identification".
  • "Minimal presentation scaffold" →\to "presentation scaffold"
AuthorsOpenReview ↗

Joint Responses

Joint Responses

1. Approximate minimizers and optimization (pkvy W2; RuxL W1).

Theorems 6 and 8 guarantee recovery at every global minimizer, not merely the existence of a correct representation. For each fixed covered observation set that forces exact scaled-tensor recovery, Proposition O.2 and Corollary O.3 show that sufficiently small objective gaps guarantee uniformly accurate predictions of the scaled target sλ3δs_\lambda^3\delta and correct decoding. The result holds for unrestricted complex factors. For passive sampling, it applies on the same good-mask event. The result is qualitative: the objective-gap tolerance may depend on the group, observation set, regularization coefficient, and requested accuracy. Experiments across 32 group instances test the breadth and sample efficiency of finite-budget Adam training; guarantees that training reaches the required objective gap remain open.

2. Theoretical bound and empirical thresholds (pkvy W3; RuxL W2).

The principal sample-complexity result is the subquadratic sufficient rate O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}), rather than an optimized finite-size constant. Relative comparisons require two observations, giving comparison edges with probability p2p^2; the connectivity condition np2≳log⁡nnp^2\gtrsim\log n yields the stated sampling scale. The explicit prefactor is conservative, arising from controlling dependencies between comparison edges and bounding disconnected cuts. At order 128, the 95%-confidence bound requires observing approximately 83% of the table, compared with the measured threshold of 9.4%. Appendix I verifies that the same 1,543-pair threshold achieves at least 95% mean unobserved accuracy and at least 99.9% accuracy in each of five runs. Meeting these empirical criteria does not establish exact recovery or a 95% recovery probability.

Measured passive thresholds support this dependence over the tested range. Across the 18 benchmark instances with 24≤n≤12824\le n\le128, fitting a free polynomial exponent after accounting for the proposed log⁡n\sqrt{\log n} correction gives approximately 1.5071.507. The single fitted coefficient 0.4760.476 in the hybrid curve adjusts its scale, not its polynomial exponent. The tested range also admits other logarithmically modified power laws and does not uniquely determine the asymptotic law. Target-aware recovery near 3n3n agrees also with the predicted leading constant.

Establishing recovery and sharpening its sample requirement are distinct theoretical advances. Initial nuclear-norm matrix-completion guarantees contained extra polynomial dimension factors; subsequent results achieved near-linear dimensional dependence with logarithmic overhead under their respective assumptions. Likewise, improving PhaseLift's sample requirement from O(nlog⁡n)O(n\log n) to O(n)O(n) required substantial further theoretical work. Appendix N.2 gives these historical comparisons. Our result establishes objective-dependent recovery from partial observations; improving its sufficient exponent, logarithmic factor, or numerical prefactor remains an important continuation.

The relation ablations in Table 1 test the mechanism directly: nearly unitary geometry can coexist with poor unseen prediction, whereas adding relation-enforcing observations enables recovery.

3. Label-dependent termination (pkvy W4; RuxL W3).

These stopping rules save computation and time rather than select a favorable checkpoint. In our checks, the stopping condition did not change the convergence result. One continues training for a substantial period after crossing a recovery threshold; the other terminates at an eligible near-chance evaluation. Training is highly stable: test loss decreases monotonically rather than deteriorating after a favorable intermediate checkpoint. We report accuracy at termination rather than peak accuracy. In our runs, internal algebraic alignment develops on a similar timescale to improving unobserved accuracy, consistent with the grokking transition. Accordingly, stopping based on local algebraic alignment, without consulting unobserved labels, gives the same convergence outcomes. Appendix K documents the stopping rules and configuration provenance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.