- 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
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.
Thank you for highlighting the comparison-graph technique and for the questions about stability, the empirical gap, and active sampling.
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.
A: Each comparison edge requires two observations, giving probability p2; 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 Ω(nlogn), so the optimal passive rate remains open. Joint Response 2 gives the numerical comparison and empirical qualifications.
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.
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.