The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning

• URL: http://arxiv.org/abs/2607.03347v1
• Date: Fri, 03 Jul 2026 14:02:42 GMT
• Title: The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning
• Abstract summary: We consider the Multiscale Single-Index Model (MSIM) as a stylized model for hierarchical learning with emphscale separation.<n>We perform a fine-grained analysis of the chaos using Wiener Edgeworth expansions.<n>We prove that online SGD on the correlation objective, where all layers evolve in the same timescale, $1 - o_d(1)$ recovery with $n = widetildeO( dK-1)$ samples, recovering the same sample complexity as in the linear counterpart.
• Score: 33.59654714700262
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the Multiscale Single-Index Model (MSIM), first introduced in \cite{oymak2021learning}, as a stylized model for hierarchical learning with \emph{scale separation}. Each layer extracts a shared single-index feature at one physical scale and passes it to the next, thus defining a tractable setting in which to study how deep architectures learn multiscale representations. Under non-degeneracy and delocalization assumptions on the link function and planted features respectively, for fixed depth $K$ and local scale $d$, the first Wiener chaos of the target behaves as a perturbed spiked tensor, where the perturbation of order $d^{-1/2}$ comes from the non-linearity -- revealing the MSIM as a natural non-linear analogue of the Tensor PCA model \cite{montanari2014statistical}. While this perturbative picture is sufficient to enable efficient spectral recovery based on Tensor unfolding (as already observed in \cite{oymak2021learning}), it is not precise enough for the analysis of backpropagation gradient-based methods. In this work, we address this limitation by performing a fine-grained analysis of the Wiener chaos using Edgeworth expansions. In the first chaos, this gives a finite-rank hierarchy at scales $d^{-q/2}$. In higher chaoses, balanced flattenings exhibit staircase singular-value plateaus of size $d^{-ρ/2}$ and multiplicity $d^ρ$ under a natural higher-chaos non-cancellation condition. Using this higher-chaos structure, and under an additional slow Hermite-energy tail condition, we first establish shallow-network approximation lower bounds, quantifying the benefit of depth in this model. Next, and most importantly, we prove that online SGD on the correlation objective, where all layers evolve in the same timescale, achieves $1 - o_d(1)$ recovery with $n = \widetilde{O}( d^{K-1})$ samples, recovering the same sample complexity as in the linear counterpart.

Related papers

• Extra-Merge: Tracing the Rank-1 Subspace of Model Merging in Language Model Pre-Training [56.323119575322146]
  Extra-Merge consistently outperforms standard merging baselines in experiments across GPT-2 and LLaMA families.<n>It yields consistent zero-shot accuracy gains on Pythia-12B downstream tasks and generalizes effectively to the Muon citepjordan2024muon.
  arXiv  Detail & Related papers  (2026-05-26T02:48:34Z)
• How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
  We study the feedback in a Gaussian single-index model with $r*(x) = *(langle *, xrangle)$ and $x sim N(0, I_d)$.<n>We analyze a two-stage neural reward model that first learns the hidden direction $*$ from reward-weighted samples and then fits the readout layer by weighted ridge regression.
  arXiv  Detail & Related papers  (2026-05-23T22:00:38Z)
• Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noise [12.977441534320041]
  We show that a scale-invariant first-order method with spectral norm requires $(minm, n-frac3p-2p-1) calls.<n>We prove that a batched method achieves the matching bound of $(minm, n-frac5p2p-2p-2)$ when the norm is spectral and the Hessian is Lipschitz.
  arXiv  Detail & Related papers  (2026-05-18T15:13:18Z)
• How to Scale Mixture-of-Experts: From muP to the Maximally Scale-Stable Parameterization [45.69980208532521]
  We take a principled step toward resolving this gap by analyzing three different scaling regimes.<n>For each regime, we develop a novel Dynamical Mean Field Theory (DMFT) description of the limiting training dynamics of MoEs.<n>We show that the resulting $$P prescription does not reliably induce monotonic improvement with scale or robust learning-rate transfer.
  arXiv  Detail & Related papers  (2026-05-13T23:32:00Z)
• Minimax Rates for Hyperbolic Hierarchical Learning [3.3192479135000426]
  We prove an exponential separation in sample complexity between Euclidean and hyperbolic representations for learning on hierarchical data.<n>We also show a geometry-independent bottleneck: any rank-$k$ prediction space captures only $O(k)$ canonical hierarchical contrasts.
  arXiv  Detail & Related papers  (2026-01-27T20:50:24Z)
• Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limit [66.20349460098275]
  We study the gradient descent learning of a general Gaussian Multi-index model $f(boldsymbolx)=g(boldsymbolUboldsymbolx)$ with hidden subspace $boldsymbolUin mathbbRrtimes d$.<n>We prove that under generic non-degenerate assumptions on the link function, a standard two-layer neural network trained via layer-wise gradient descent can agnostically learn the target with $o_d(1)$ test error.
  arXiv  Detail & Related papers  (2025-11-19T04:46:47Z)
• A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond [25.592330047318274]
  We focus on the structure discovery aspect and study it under weaker assumptions.<n>At the core of our approach is a key $textitderandomization$ lemma.<n>This lemma directly explains structure discovery and has immediate applications in other domains.
  arXiv  Detail & Related papers  (2025-10-22T08:55:00Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
  arXiv  Detail & Related papers  (2025-06-05T18:34:56Z)
• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
  This work introduces a hybrid non-Euclidean optimization method which generalizes norm clipping by combining steepest descent and conditional gradient approaches.<n>We discuss how to instantiate the algorithms for deep learning and demonstrate their properties on image classification and language modeling.
  arXiv  Detail & Related papers  (2025-06-02T17:34:29Z)
• Minimum $\ell_{1}$-norm interpolators: Precise asymptotics and multiple descent [19.781475554462553]
  This paper pursues theoretical understanding for an important type of interpolators: the minimum $ell_1$-norm interpolator. We observe, and provide rigorous theoretical justification for, a curious multi-descent phenomenon. Our finding is built upon an exact characterization of the risk behavior, which is governed by a system of two non-linear equations with two unknowns.
  arXiv  Detail & Related papers  (2021-10-18T17:51:14Z)
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
  We propose a new framework of variance-reduced Hamiltonian Monte Carlo (HMC) methods for sampling from an $L$-smooth and $m$-strongly log-concave distribution. We show that the unbiased gradient estimators, including SAGA and SVRG, based HMC methods achieve highest gradient efficiency with small batch size. Experimental results on both synthetic and real-world benchmark data show that our new framework significantly outperforms the full gradient and gradient HMC approaches.
  arXiv  Detail & Related papers  (2021-02-09T02:44:24Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.