{"id":"0315f894-204f-4e80-aa31-12c9afd95e96","arxiv_id":"2411.14288","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For one-hidden-layer equivariant networks, generalization bounds depend only on filter norms and the sample size, while suitable weight sharing can match equivariance and locality adds an extra gain.","lead":"This paper derives mathematical bounds on how much training data a one-hidden-layer equivariant neural network needs to generalize, showing the bounds mainly depend on the size of the learned filters, not the input dimension. It compares equivariant, weight-shared, and local-filter designs to see which architectural choice actually drives sample efficiency.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.4's lower-bound proof drops a sqrt(|G|) factor when taking the supremum over constant filters, so the claimed tightness of the dimension-free bound is not established as written.","rationale":"After reading the upper-bound proofs, I find the main dimension-free upper-bound argument coherent: the peeling step, the contraction lemma application, and the cancellation of |G| are standard, and the general pooling theorem can absorb rho into sigma. The experimental section does not overclaim; it only compares the leading term. My concern is localized to Appendix E. The equality sup_{w in W1+} |sum_k w_(1,k) V_k| = M2 ||V|| ignores the fact that w_(1,k)=a_k 1 gives ||w_(1,k)|| = sqrt(|G|) |a_k|; hence the feasible set for a is the l2 ball of radius M2/sqrt(|G|), not M2. The subsequent use of ||x_i^(k)||_1 >= ||x_i^(k)||_2 is too weak to compensate unless the data are aligned with the all-ones direction. The theorem may be salvageable by choosing a distribution supported on constant signals over G, but that is not what the proof states. This makes the tightness claim unproven as written. Because the upper-bound results are the paper's main quantitative contribution and appear sound, I would accept the paper only conditionally on correcting Theorem 4.4's proof or weakening its statement.","tokens_in":52168,"tokens_out":38938,"duration_ms":324850,"concrete_test":"Recompute the supremum in Appendix E with the explicit constraint |G| sum_k a_k^2 <= M2^2. If the value is (M2/sqrt(|G|)) ||V_+||, then redo the lower-bound derivation for G=C_n, n=2,4,8, using data x_i proportional to the all-ones vector so that 1^T x_i^(k) = sqrt(n) ||x_i^(k)||_2, and check whether the final bound is c M1 M2 B / sqrt(m) independent of n. Alternatively, compute the empirical Rademacher complexity for random positive-orthant data and see whether it decays as 1/sqrt(|G|); if it does, the proof needs a corrected data construction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Appendix E claims the equality sup_{w in W1+} |sum_k w_(1,k) V_k| = M2 ||V||, but with w_(1,k)=a_k 1 the constraint ||w|| <= M2 reads |G| sum_k a_k^2 <= M2^2, so the supremum is (M2/sqrt(|G|)) ||V_+||, not M2 ||V||, and the positivity restriction makes it ||V_+|| rather than ||V||. The proof then lower-bounds ||V|| by B sqrt(m) using only ||x_i^(k)||_1 >= ||x_i^(k)||_2; with the correct factor this yields at best c M1 M2 B / sqrt(m |G|). The claimed data distribution (positive orthant, norm B) does not imply ||V|| is sqrt(|G|) times larger; that requires data aligned with the all-ones direction. Thus the tightness claim is not proven by the given argument, although the upper-bound theorems may still be correct.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the sample complexity of one-hidden-layer group-equivariant networks through Rademacher complexity. It proves norm-based generalization bounds for group-convolution networks with average, max, and a class of general pooling operations, for general equivariant networks parameterized in the frequency domain, for non-equivariant weight-sharing architectures, and for local receptive fields. The headline result is a dimension-free upper bound of order O(||u|| ||w|| / sqrt(m)) for positively homogeneous 1-Lipschitz activations, together with an extension to multilayer networks with a |G|^{(L-1)/2} dependence, a lower bound intended to show tightness, and experiments on rotated MNIST and CIFAR10.","tokens_in":52341,"tokens_out":35214,"duration_ms":324040,"significance":"If the upper-bound theorems are correct, the paper is a useful contribution: it gives clean, dimension-free generalization bounds for a natural class of equivariant one-hidden-layer networks, and it isolates the separate roles of equivariance, weight sharing, and locality. The proofs are based on standard tools, the comparisons with prior work are informative, and the numerical study supports the qualitative scaling of the bound. The main weakness is the lower-bound proof in Appendix E, which contains a concrete error in the norm constraint and therefore does not establish the claimed tightness; the error appears repairable, but the tightness claim is not proven as written.","major_comments":[{"comment":"The lower-bound proof drops a sqrt(|G|) factor in the norm constraint. For w in W_hat^+_1 with w_(1,k) = a_k 1, we have ||w||^2 = |G| sum_k a_k^2, so the constraint ||w|| <= M2 gives sum_k a_k^2 <= M2^2/|G|. Consequently the displayed equality E sup_{w in W_hat^+_1} |sum_i eps_i sum_k w_(1,k) 1^T x_i(k)| = M2 E ||sum_i eps_i (1^T x_i(1), ..., 1^T x_i(c0))|| is missing a factor 1/sqrt(|G|), and it also ignores the nonnegativity restriction on the a_k. With the subsequent bound ||x_i^(k)||_1 >= ||x_i^(k)||_2, the argument as written yields at best c b_x M1 M2 / sqrt(m |G|), not the claimed c b_x M1 M2 / sqrt(m). The theorem can likely be repaired by specializing the data, e.g., c0 = 1 and x_i = (B/sqrt(|G|)) 1 so that 1^T x_i = sqrt(|G|) B, and by handling the positive-part/sign issue carefully, but as written the tightness claim is not established.","section":"Appendix E, Theorem 4.4"},{"comment":"The proofs apply the contraction lemma to squared Rademacher sums, for example after Eq. (21): E sup_w (sum_i eps_i sigma(...))^2 <= E sup_w (sum_i eps_i (linear))^2. Lemma B.4 is stated for convex increasing G, while G(x) = x^2 is not increasing on R. The argument needs the standard two-sided or positive/negative-part version of the contraction inequality, or an explicit justification that the structure of the set T allows applying the lemma to squares. This is a genuine gap in the written proof, although the dimension-free rate is likely preserved after a constant-factor repair.","section":"Appendix C.2, C.5 and Lemma B.4"}],"minor_comments":[{"comment":"The theorem assumes pooling of the form P(z) = phi((1/|G|) 1^T rho(z)) with a non-identity rho, but the proof in C.5 applies phi directly to (1/|G|) 1^T sigma(...) and never uses rho. Since rho and sigma are both 1-Lipschitz positively homogeneous, one can absorb rho into sigma, but the statement and proof should be aligned.","section":"Theorem 4.1 and Appendix C.5"},{"comment":"The confidence term 4 sqrt(2 log(4/delta)/m) implicitly assumes the loss is bounded by 1. The paper states only that the loss is 1-Lipschitz; the boundedness normalization should be stated explicitly.","section":"Theorem B.3 and Section 4"},{"comment":"In the proof of the multi-channel max-pooling covering bound, the set H1 is defined with ||w|| <= M1 in one place and with M2 in the covering-number calculation below it. This appears to be a notational inconsistency, not a mathematical error, but it should be corrected.","section":"Appendix C.4"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound error is the main obstacle to accepting the tightness claims. I would encourage the authors to supply a corrected proof or a revised statement, since the upper-bound theory appears sound and the lower-bound claim is plausibly fixable with a more carefully chosen data distribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nWorth a look: the paper gives genuinely new norm-based Rademacher bounds for one-hidden-layer group-convolution and equivariant networks, with honest comparisons to VSS22 and GRS18. The max-pooling bounds, the weight-sharing norm characterization, the locality factor, and the frequency-domain no-gain remark are the real additions; the average-pooling theorem is, as the authors say, essentially a reworked special case of VSS22. The paper is well written, the appendix proofs are mostly coherent, and limitations (positive homogeneity, pooling representation, no norm nonlinearities) are stated without hand-waving. No code, but that is normal for this line of work.\n\nThe soft spot is in Appendix E, and it is real. Theorem 4.4's lower bound uses constant filters w_(1,k) = a_k 1. The constraint ||w|| <= M2 then reads sqrt(|G|) ||a|| <= M2, so the supremum over a is (M2/sqrt(|G|)) ||V_+||, not M2 ||V_+||. The proof drops that sqrt(|G|). The positive-orthant data assumption does not make ||V|| larger by sqrt(|G|); the final lower bound should scale as c M1 M2 B / sqrt(m |G|), not c M1 M2 B / sqrt(m). So the claimed dimension-free tightness is not proven. The upper-bound theorems may still be correct; the issue is localized to the tightness claim, which is a key selling point in the abstract and introduction. This needs a fix, or the claim should be downgraded to a dimension-dependent lower bound.\n\nOther concerns are minor: the M_max spectral term in the max-pooling bound is data dependent and the authors already note it can be loose for large m; the positive-homogeneity restriction is acknowledged. The citation pattern is fine; self-citation to BCC22 appears only in comparison remarks.\n\nThis paper deserves a serious referee, but the referee should be told to check Appendix E carefully. I would accept it only after the lower-bound factor is corrected or the claim is weakened. For readers focused on the upper bounds, the paper is useful and citable.","headline":"Useful upper-bound paper, but the tightness proof drops a sqrt(|G|) factor in the lower bound and needs repair before the dimension-free claim is credible.","tokens_in":52893,"tokens_out":3685,"would_cite":true,"duration_ms":34390,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes dimension-free sample-complexity bounds for one-hidden-layer group-convolution networks: the generalization error is controlled by the product of filter norms, with a matching lower bound.","keywords":["sample complexity","generalization bounds","equivariant networks","group convolution","Rademacher complexity","weight sharing","local filters","one-hidden-layer networks"],"falsifier":"Run the lower-bound construction of Theorem 4.4 numerically for small $m$: draw inputs supported in the positive orthant with fixed norm $b_x$, train or enumerate the norm-ball group-convolution model with ReLU and average pooling, and compute the empirical Rademacher complexity exactly. If it fails to lie between $c b_x M_1M_2/\\sqrt{m}$ and $b_x M_1M_2/\\sqrt{m}$ up to constants, the claimed tightness is wrong; separately, repeating the PAC experiment many times, the frequency with which $L(h)-\\hat{L}(h)$ exceeds the Theorem 4.1 bound must be at most $\\delta$, otherwise the inequality is violated.","tokens_in":51940,"feed_emoji":"📉","tokens_out":11090,"duration_ms":103535,"temperature":0.7,"pith_summary":"This paper asks which architectural choices — equivariance, weight sharing, local filters — actually reduce how many samples a one-hidden-layer network needs to generalize, and it answers with sharp uniform bounds. For group-convolution networks with average pooling (or any pooling that can be written as a pointwise function of a group average) and activations that are 1-Lipschitz and positively homogeneous, it proves that with high probability $L(h) \\le \\hat{L}(h) + 2 b_x M_1 M_2/\\sqrt{m} + 4\\sqrt{2\\log(4/\\delta)/m}$, with no dependence on input or channel dimensions or on the group size. The argument runs through Rademacher complexity, a standard measure of how well a hypothesis class can fit random labels, and a matching lower bound shows the rate $M_1M_2/\\sqrt{m}$ is tight for ReLU average-pooling networks. The same machinery shows that non-equivariant weight sharing with an orthogonal basis matches the equivariant bound, that locality buys an extra $\\sqrt{O_\\Phi/|G|}$, and that the uncertainty principle forces a trade-off between spatial and frequency locality. If the bounds are right, filter norms rather than parameter counts are the quantity that controls sample efficiency in these shallow equivariant models.","feed_headline":"Sample complexity of equivariant nets depends only on filter norms","feed_subtitle":"Error decays like M1M2/sqrt(m) no matter the group size or channels; experiments match the trend.","key_machinery":"The central object is the norm-constrained hypothesis space $H=\\{h_{u,w}:\\|u\\|\\le M_1,\\ \\|w\\|\\le M_2\\}$, and the mechanism is Rademacher complexity with a peeling argument. The proof first strips off the final linear layer, reducing the Rademacher sum to $\\frac{M_1}{m}\\mathbb{E}_\\epsilon \\sup_w \\|\\sum_i \\epsilon_i P(\\sigma(Wx_i))\\|$, then uses 1-Lipschitzness of the loss and activations via the contraction lemma, and positive homogeneity to normalize each channel's weight vector and collapse the remaining supremum to $b_xM_1M_2/\\sqrt{m}$. For general pooling, the representation $P(z)=\\phi((1/|G|)1^\\top\\rho(z))$ is what lets the group average pass through the pointwise maps and preserve the same chain. Covering-number arguments (Dudley's inequality plus a norm-covering lemma for linear classes) appear only in the max-pooling and multi-channel covering proofs, which is where the mild dimension dependence enters.","core_discovery":"The central claim is that the empirical Rademacher complexity of the hypothesis space $H=\\{h_{u,w}: \\|u\\|\\le M_1,\\ \\|w\\|\\le M_2\\}$ for a multi-channel group-convolution network $h_{u,w}(x)=u^\\top P(\\sigma(Wx))$ is bounded by $b_x M_1 M_2/\\sqrt{m}$ when the pooling functional has the form $P(z)=\\phi((1/|G|)1^\\top \\rho(z))$ with $\\rho,\\phi,\\sigma$ all 1-Lipschitz and positively homogeneous. Theorem 4.1 converts this into a PAC guarantee whose leading term is $2b_x M_1 M_2/\\sqrt{m}$, and Theorem 4.4 shows by a Khintchine-based construction that for average pooling and ReLU there is a data distribution on which the same quantity is at least $c b_x M_1 M_2/\\sqrt{m}$. The same peeling argument applies to general equivariant networks parameterized in Fourier space (Theorem 5.1), while max-pooling and multilayer extensions retain the norm dependence but acquire mild group-size or channel factors. For weight sharing through fixed matrices $B_k$, the bound depends on a shared-norm $\\|w\\|_B$, so orthogonal sharing schemes reproduce the equivariant guarantee without being equivariant (Proposition 6.1). Local filters improve the leading term by $\\sqrt{O_\\Phi/|G|}$ (Proposition 7.1), and band-limited filters trade that gain away through the uncertainty principle (Proposition 7.2).","pith_inferences":["The paper does not pursue it, but the norm-only bound suggests a concrete design rule: regularize $M_1M_2$ (for instance by weight decay on both layers) rather than the number of parameters, if the goal is sample efficiency in shallow equivariant models.","The equivalence between equivariance and orthogonal weight sharing is distribution-free; on data that genuinely has the group symmetry, equivariance should add a further advantage that this bound does not quantify, since the bound never uses the symmetry of the data.","A direct test of the stated conjecture for general Lipschitz activations would be to compute Rademacher complexity of group-convolution networks with sigmoid activations; if dimension-free scaling breaks down, positive homogeneity marks the real boundary of the argument.","Applied to steerable networks, the uncertainty-principle trade-off suggests that band-limiting filters to gain frequency-domain locality costs a factor of order $1/\\sqrt{B}$ in the sample-complexity gain, giving a quantitative knob for choosing filter bandwidth."],"forward_implications":["For a fixed norm budget $M_1M_2$ and input radius $b_x$, increasing the group size $|G|$ or the number of channels does not worsen the leading generalization term in the average-pooling group-convolution network.","Equivariance and a suitably orthogonal weight-sharing scheme yield the same dimension-free bound, so on generic non-symmetric data the two design choices are interchangeable at the level of sample complexity.","Local filters improve the leading term by $\\sqrt{O_\\Phi/|G|}$; the fewer patches a given input coordinate participates in, the better the bound.","Band-limited filters cannot get the full spatial-locality gain: the uncertainty principle forces a spatial support of at least $|G|/B$ for filters with $B$ non-zero frequency entries, leaving a trade-off rather than a free lunch.","A matching lower bound shows the $\\sqrt{m}$ rate and the $M_1M_2$ norm dependence are not artifacts of a loose analysis for ReLU average-pooling networks."],"supporting_citations":[{"why":"Supplies the peeling and size-independent Rademacher technique that the proofs adapt to equivariant architectures.","marker":"[GRS18]"},{"why":"Provides the one-hidden-layer sample-complexity framework for convolutional networks, including average- and max-pooling bounds that this paper extends to group convolution with filter-norm bounds.","marker":"[VSS22]"},{"why":"Gives the representation of permutation-invariant pooling as phi((1/|G|) sum rho(z_i)) that Theorem 4.1 assumes.","marker":"[Zah+17]"},{"why":"Earlier frequency-domain PAC-Bayesian bound for equivariant networks; the paper shows Rademacher analysis yields the same rate without frequency-domain gains.","marker":"[BCC22]"},{"why":"Provides the covering-number bound for linear function classes used with Dudley's inequality in the max-pooling proofs.","marker":"[Zha02]"},{"why":"Supplies norm-based Rademacher and matrix-covering arguments that the max-pooling and channel-covering bounds are compared against.","marker":"[BFT17]"},{"why":"Provides the decoupling and moment inequalities used to bound the Rademacher sums in the pooling proofs.","marker":"[FR13]"}],"fun_headline_variants":["Sample complexity of shallow nets: depends only on filter norms","Equivariance, locality: not the main drivers of sample efficiency","Filter norm alone determines sample complexity of one-layer nets","Locality boosts generalization but caps expressivity","Non-equivariant weight sharing can match equivariant bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole dimension-free result rests on every nonlinear element—activation and pooling—being 1-Lipschitz and positively homogeneous, and on general pooling decomposing as a scalar function of a group average; norm-based activations used in steerable networks fall outside this.","fun_headline_variants_meta":{"raw":{"variants":["Sample complexity of shallow nets: depends only on filter norms","Equivariance, locality: not the main drivers of sample efficiency","Filter norm alone determines sample complexity of one-layer nets","Locality boosts generalization but caps expressivity","Non-equivariant weight sharing can match equivariant bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000222,"raw_usage":{"total_tokens":1518,"prompt_tokens":1071,"completion_tokens":447,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":687,"completion_tokens_details":{"reasoning_tokens":369}},"tokens_in":687,"tokens_out":447,"duration_ms":4829,"temperature":1.0,"reasoning_tokens":369,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:22:04.849819+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the lower-bound construction of Theorem 4.4 numerically for small $m$: draw inputs supported in the positive orthant with fixed norm $b_x$, train or enumerate the norm-ball group-convolution model with ReLU and average pooling, and compute the empirical Rademacher complexity exactly. If it fails to lie between $c b_x M_1M_2/\\sqrt{m}$ and $b_x M_1M_2/\\sqrt{m}$ up to constants, the claimed tightness is wrong; separately, repeating the PAC experiment many times, the frequency with which $L(h)-\\hat{L}(h)$ exceeds the Theorem 4.1 bound must be at most $\\delta$, otherwise the inequality is violated.","supporting_citations":[],"review_version":1}