acceptodds
Under review as a conference paper at ICLR 2027

Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models

Abstract

We establish a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning. We study growing-rank multi-index models with high-dimensional Gaussian covariates in and teacher directions forming a cyclic symmetry orbit, where . We compare three ways of exploiting this structure: architectural weight sharing, data augmentation over the full symmetry group, and learning without access to the symmetry. In particular, we analyze a symmetry-tied convolutional network, an untied network, and the same untied network trained with full-group data augmentation, using spherical online SGD with correlation loss. For a class of polynomial links with information exponent , we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in samples, whereas the symmetry-agnostic learner requires . For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities and , respectively. Thus, full-group data augmentation matches the sample efficiency of architectural weight sharing, and both provide a polynomial advantage over training without symmetry. For , the proof reveals a two-stage mechanism: fluctuations at initialization select one direction in the teacher orbit, after which localized growth amplifies its overlap to the weak recovery scale while competing overlaps remain near their initialization scale.

Primary area:
learning theory
Keywords:
multi-index models, feature learning, stochastic gradient descent, learning theory, symmetric deep learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TVo5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies online spherical SGD with correlation loss on the Gaussian target f(x)=r−1/2∑k<rσ(⟨Πkw,x⟩)f(x)=r^{-1/2}\sum_{k<r}\sigma(\langle\Pi^k w,x\rangle). Here Π\Pi is the cyclic shift by d/rd/r coordinates, r=dδr=d^\delta with δ<1/2\delta<1/2, and w∗w^* is uniform on the sphere. Three procedures are compared, each with a prescribed step size (Eq. 6): a tied student (T), an untied student of width ss (U), and the same untied student trained on the full-group-averaged loss (A).

  • p≥3p\ge3 (Thm 3.2). For polynomial links with information exponent p≥3p\ge3, weak directional recovery takes Θ~(dp−1)\tilde\Theta(d^{p-1}) samples for T and A and Θ~(rdp−1)\tilde\Theta(rd^{p-1}) for U. With s≥(1+ε)rlog⁡rs\ge(1+\varepsilon)r\log r, U and A cover the whole orbit at the same scales (Cor. 3.5).
  • σ=h2\sigma=h_2 (Thm 3.7). Weak subspace recovery takes Θ~(d)\tilde\Theta(d) samples for T and A, against Θ~(rd)\tilde\Theta(rd) for U.

The upper bounds rest on a two-phase argument: the largest initial correlation is selected, then grows. The lower bounds are non-escape estimates (Thm B.4). One experiment (h4h_4, r=dr=\sqrt d, d≤576d\le576) illustrates the scalings.

Critical strengths
  • For each procedure, at the prescribed step sizes, upper and lower bounds match up to polylogarithmic factors. The lower bound holds uniformly over polynomially many weights.
  • The analysis handles a number of interacting teacher directions that grows with dd. Interaction terms are controlled through the near-orthogonality rμ∗=o((log⁡d)−2)r\mu^*=o((\log d)^{-2}) (Lemma C.1) and an initial relative gap of order (log⁡d)−2(\log d)^{-2} (Lemma C.3). This makes rigorous the mechanism by which the initial leader remains the leader, and extends greedy-selection arguments (Ben Arous et al., 2026) to growing rank.
Critical weaknesses
  • The separation is between three algorithms at prescribed step sizes. Thm B.4 is proved for ηd=d−p/2(log⁡d)−A\eta_d=d^{-p/2}(\log d)^{-A} with the rescaling (9), and App. A (l. 873–875) states that the lower bounds hold "for the specified spherical SGD updates and learning rates". Neither the abstract ("a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning") nor Thm 3.2 mentions this restriction. The lower bound for U does not exclude a shorter hitting time under another step size or schedule. Moreover, the dp−1d^{p-1} rate is itself specific to vanilla online SGD: loss smoothing (Damian et al., 2023) and batch reuse (Dandi et al., 2024b) change it, and the paper does not discuss whether the factor rr persists under them.
  • Interpretation of the factor rr. Per fresh sample, an augmented weight takes the average of the rr untied single-weight gradients at the transformed copies (Πkxt,yt)(\Pi^kx_t,y_t), with a step rr times larger than in U (Eqs. 65–66). This is U on a minibatch of the rr copies, with the step scaled linearly in the batch size. Since the orbit is nearly orthogonal, these copies act on the correlations mkm_k almost as rr independent samples. The factor rr then equals the number of processed examples per fresh sample, and also the per-iteration overhead of A (l. 228–229): counted in gradient evaluations, A and U both cost Θ~(rdp−1)\tilde\Theta(rd^{p-1}). This reading determines what "symmetry-aware" buys and should be discussed.
  • The setting is narrow. The group enters the proofs only through the near-orthogonality of a random orbit (Lemma C.1) and through the tied identity. The condition δ<1/2\delta<1/2 excludes r≍dr\asymp d (stride-one convolution) and local filters with overlapping patches, which are the cases behind the convolutional interpretation. The correlation loss decouples the student neurons (l. 441–444), so U and A are ss independent single-neuron runs on shared data. The second layer is not trained.
Questions for authors
  • Does the lower bound of Thm B.4 for U extend to all step sizes, constant or time-varying? If not, can Fig. 1 be complemented by a step-size sweep for each procedure?
  • Under the square loss, Eq. (66) no longer holds. Do A and T still have the same sample complexity, and does the factor rr persist?
  • For δ≥1/2\delta\ge1/2 (the conjecture in Sec. 5), which step fails: the initialization gap (Lemma C.3) or the control of the interaction terms? Is the agreement of Fig. 1 at δ=1/2\delta=1/2 evidence for the conjecture?
Reviewer_6RXHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper asks how much it helps in feature learning when symmetry is known. Can a model learn from fewer samples? It compares a model that reuses one weight across all rr shifts (named T), an untied model with separate weights and an ordinary loss on each sample (named U), and that previous untied model trained by loss averaged over all shifted versions of each sample (named A).

For a very specific online SGD method used in the paper the authors prove that T and A need about rr times less samples than U to weakly recover a teacher feature (up to log factors). Because rr grows with the dimension, this gap is polynomial in dd. T and A also match the single feature sample rate. They find a similar gap for recovering the teacher subspace in the quadratic link case.

A small synthetic experiment shows recovery times that are consistent with what they predict.

Critical strengths

Matching upper and lower bounds.\textbf{Matching upper and lower bounds.} The paper proves matching upper and lower bounds, up to log factors, for the specified SGD procedures. T and A need about rr times fewer samples than U, and rr grows with the dimension. This polynomial gap is in my opinion the main strength of this work.

Proof intuition.\textbf{Proof intuition.} The proof provides intutition as to how this gap occurs. It shows how one teacher direction starts slightly in front due to random initialization and keeps growing while the other directions stay small, even as their number increases with dimension. Compared to T and A, it shows that U follows the same selection and then growth process, but each update (under the chose learning rate) pushes the correlation with the teacher rr times less while noise is just r\sqrt{r} times smaller and thus it takes about rr times more samples.

Critical weaknesses

Scope.\textbf{Scope.} The lower bound for U applies to the particular spherical online SGD procedure and learning rates chosen in the paper. It leaves open if U with some other learning rate or another untied algorithm could do better. The gap is thus established only for the procedures analyzed here and not for symmetry-aware and symmetry-agnostic learning in general.

Simplified setting.\textbf{Simplified setting.} Under the correlation loss, each untied weight’s gradient depends only on that weight, so U and A can be analyzed one weight at a time. The analysis also assumes a known link and studies weak recovery. These choices make the result easier to analyze but they leave open whether the gap holds under L2 loss or unknown link.

Questions for authors
  1. The lower bound for U uses the learning rate you mention in the theorem. What happens if its learning rate is different? More specifically, can you provide some intuition as to whether U could reduce (or could not reduce) the polynomial gap through a different choice?

  2. The correlation loss lets you analyze each untied weight separately. Which parts of the separation rely on this decoupling? Do you have evidence that a similar gap occus with L2 loss?

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

This paper provides a sample complexity improvement in symmetry-aware feature learning in growing-rank multi-index models with symmetric features. The authors compared weight sharing, full-group data augmentation, and a standard untied learner under spherical online SGD, and proved a complexity improvement by the order of the group for the symmetry-aware learners in feature recovery.

Critical strengths
  1. The paper provides a clean theoretical comparison between different learners, with matching sample complexity bounds up to logarithmic factors.
  2. The theoretical analysis is detailed and the paper is well organized.
Critical weaknesses
  1. The proposed theoretical mechanism seems not very new. Feature selection and amplification in single/multi-index learning have been extensively studied [1–3], and the sample complexity benefit of exploiting symmetry has also been established in previous work [4].
  2. The theoretical contribution also seems incremental. Most proof techniques appear to be closely related to existing analyses of single-index models or multi-index models with growing ranks; while the equivalence between data augmentation and weight sharing follows directly from the correlation loss. It is unclear what substantially new technical difficulty is addressed here.
Questions for authors

Questions:

  1. Can authors better clarify the technical novelty and positioning relative to previous feature-learning analyses [1–3] and symmetry-aware learning results [4]? In particular, which parts of the proof do authors think that are technically novel and significant compared to existing results? Or do authors think it is a new theoretical justification towards some unjustified algorithmic practice?
  2. The lower bound for the untied learner seems quite restrictive to the prescribed learning-rate scaling. Could different learning rates or gradient manipulations (group transform, label transforms, or other noisy gradient exploration) improve its SNR and achieve a matching sample complexity?
  3. Both symmetry-aware learners are given the correct transformation group, which seems to be strong prior information about the teacher. If the group is known, an untied learner can also exploit it through gradient averaging without changing its architecture. What does the separation tell us beyond the benefit of this structural prior? Could the results be extended to a more general setting, say, when we only know partial or approximately known symmetry?

References:

[1] Oko et al. (2024). Learning Sum of Diverse Features: Computational Hardness and Efficient Gradient-Based Training for Ridge Combinations. COLT.

[2] Ren et al. (2025). Emergence and Scaling Laws in SGD Learning of Shallow Neural Networks. NeurIPS.

[3] Şimşek et al. (2025). Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence. AISTATS.

[4] Mei, Misiakiewicz & Montanari (2021). Learning with Invariances in Random Features and Kernel Models. COLT.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.