Search papers, labs, and topics across Lattice.
We demonstrate a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning for growing-rank multi-index models with cyclic symmetry. By analyzing symmetry-tied convolutional networks, untied networks, and untied networks with full-group data augmentation using spherical online SGD, we show that tied and augmented learners achieve weak directional recovery in $\widetilde{\Theta}(d^{p-1})$ samples for polynomial links with $p\ge3$, while symmetry-agnostic learners require $\widetilde{\Theta}(rd^{p-1})$. This separation also holds for weak recovery of the teacher subspace in the pure quadratic Hermite link, with complexities $\widetilde{\Theta}(d)$ and $\widetilde{\Theta}(rd)$ respectively, indicating that full-group data augmentation matches the sample efficiency of architectural weight sharing.
Exploiting cyclic symmetries in multi-index models offers a polynomial sample complexity advantage, with data augmentation proving as sample-efficient as architectural weight sharing.
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 $\mathbb{R}^d$ and $r=\Theta(d^\delta)$ teacher directions forming a cyclic symmetry orbit, where $0<\delta<1/2$. 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 $p\ge3$, we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in $\widetilde{\Theta}(d^{p-1})$ samples, whereas the symmetry-agnostic learner requires $\widetilde{\Theta}(rd^{p-1})$. For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities $\widetilde{\Theta}(d)$ and $\widetilde{\Theta}(rd)$, 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 $p\ge3$, 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.
