- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies why compression favors generalizable rule-based solutions over memorizing solutions in finite-group operation tasks, and introduces Effective Gate Complexity (EGC) to measure the minimum structural complexity required to realize a complete prediction map. Theoretically, the authors first derive uniform generalization bounds from low EGC and show that the true group law has substantially lower EGC than poorly generalizing fits, thereby establishing a nonempty compression window. They further prove that, for specified group families and fixed-depth ReLU networks, every parameter vector sufficiently close to the global optimum of a quadratically regularized objective has a complete prediction map admitting a low-EGC realization, and hence generalizes. Experiments on modular addition over show that lower regularized objective values are associated with higher held-out accuracy and smaller verified EGC upper bounds, providing qualitative support for the proposed compression mechanism.
Critical strengths
-
The paper presents an interesting perspective on the relationship between compression and generalization. Rather than treating compression only as a generic complexity control, it identifies a task-dependent structural notion that can separate the true group law from poorly generalizing fits, which gives the framework a clear theoretical interpretation.
-
The experimental section is handled with considerable care. The authors verify exact agreement of complete prediction maps over the full input domain and explicitly distinguish certified EGC upper bounds from true EGC, which makes the empirical evidence more reliable despite its limited scope.
Critical weaknesses
-
The theoretical guarantees are interesting but rely on a fairly specific set of assumptions, and the scope of some of the broader claims could be delineated more clearly. The strongest results depend on particular group families, representations, architectures, width and finite-size conditions, and quantitative near-global optimality, so the generality of the conclusions is narrower than the title and some of the surrounding discussion may suggest.
-
The empirical results provide only indirect support for the main theoretical mechanism. The experiments do not verify the near-optimality condition required by the main theorem, and the reconstruction procedure certifies only EGC upper bounds. Thus, the results are best interpreted as qualitative evidence rather than a direct validation of the theoretical guarantees.
Questions for authors
-
Can the authors provide any quantitative evidence that the experimental checkpoints are close to the near-optimal region required by Theorem 4.1? In particular, is there any computable lower bound, relaxation, or certificate for that allows one to estimate ? This would materially affect how strongly the experiments support the main theoretical mechanism.
-
Can the authors clarify the finite- regime in which Theorem 4.1/4.2 becomes non-vacuous? In particular, for the experimental setting , which finite-size conditions are satisfied or violated, and what are the main conditions determining the asymptotic threshold? This would help assess the quantitative scope of the theoretical guarantees.
A clear response to these questions would help strengthen my confidence in the paper and may lead to a higher rating.