betaFeedback

WorksComputer Science

The Multiscale Single-Index Model: An MSE Analysis of Online SGD Dynamics

Abstract

We consider the Multiscale Single-Index Model (MSIM), first introduced by Oymak and Soltanolkotabi (2021), as a stylized model for hierarchical feature learning with scale separation. Each layer extracts a shared single-index feature at one physical scale and passes it to the next, giving a tractable setting in which to study how deep architectures learn local multiscale representations. Under non-degeneracy and delocalization assumptions on the link function and planted features respectively, for the two hidden-layer case (K=2K=2), we analyze joint online spherical SGD under MSE loss, which is a canonical regression objective, in discrete time and show that it achieves weak recovery from random initialization in O(dlog⁡2d)O(d\log^2 d) samples, followed by strong recovery to accuracy ε\varepsilon in O(dlog⁡(1/ε))O(d\log(1/\varepsilon)) additional samples. The main technical challenge arises from the non-Gaussian learned features observed by the second layer. We address this challenge through a quantitative Gaussian comparison using delocalization, combined with sharp trajectory-level control of the coupled SGD dynamics. This work is a companion to Bruna (2026, arXiv:2607.03347), which studies recovery under a correlation objective for general KK.

Introduction

Feature learning, informally defined as the ability to extract informative low-dimensional representations out of high-dimensional data, is the defining characteristic of Neural Networks trained with gradient descent —and the basis for the modern AI paradigm of pretraining then fine-tuning. Over the recent years, a feature learning theory has emerged, focusing on a stylized model for high-dimensional learning based on multi-index models [2, 16, 12, 13, 14, 3, 11]; see [6] for a recent survey, demonstrating the ability of shallow neural networks to perform efficient feature learning, and even identifying sharp phase transitions [25].

A natural shortcoming for such theory is that shallow NNs are limited idealizations of modern NNs, where depth is a critical component. Towards addressing this gap, several works [1, 26, 28, 15, 31] have studied feature learning in deeper architectures, raising novel questions such as (i) elucidating the hierarchy between features at different layers, or (ii) how to adapt gradient methods to facilitate learning across all layers.

In this work, motivated by applications in data domains such as images or text, we consider a stylized model for deep feature learning based on the principle of scale separation, where each layer of the network can be associated with a different physical scale. In the context of computer vision, the model becomes a Convolutional Neural Network (CNN) with disjoint receptive fields, as originally introduced in [27]; the first hidden-layer extracts local features at each patch, and subsequent layers capture local information at the next scale, progressively coarse-graining the domain [7, 22].

We instantiate each feature learning stage using a single-index model. Specifically, we consider a setting with Gaussian inputs X∈(Rd)⊗KX \in(\mathbb{R}^{d})^{\otimes K}, capturing a multiscale structure with KK scales and ‘patches’ of size dd, and a target obtained by a KK-layer network, whereby each layer k∈[K]k \in[K] coarse-grains the feature map Z(k−1)∈(Rd)⊗K−k+1Z^{(k-1)} \in(\mathbb{R}^{d})^{\otimes K-k+1} as Z(k)=ϕ(Z(k−1)θk∗)∈(Rd)⊗K−kZ^{(k)} = \phi(Z^{(k-1)}\theta_k^*) \in(\mathbb{R}^{d})^{\otimes K-k}; see Figure 1. The model X↦fθ∗(X):=Z(K)∈RX \mapsto f_{\theta^*}(X) := Z^{(K)} \in\mathbb{R} is thus parametrized by hidden directions or features θ1∗,…,θK∗∈Sd−1\theta_1^*,\ldots,\theta_K^* \in\mathbb{S}^{d-1}, and a non-linear activation function ϕ:R→R\phi:\mathbb{R}\to\mathbb{R}.

Schema of the Multiscale SIM model

Figure 1. Schema of the Multiscale SIM model. Each patch within the same layer kk shares the same local feature, parametrized by a SIM of direction θk\theta_k.

By considering the Wiener chaos expansion of the target f(X)f(X), this model can be viewed as a non-linear analogue of Tensor PCA [24], where the planted directions θ1∗,…,θK∗\theta_1^*,\ldots,\theta_K^* may be estimated from a spike in the associated chaos decomposition. This naturally leads to the study of two different algorithmic frameworks: (i) a spectral method, motivated by its efficiency in related problems, eg single- and multi-index models [23, 13, 20], spiked tensor PCA, and tensor-decomposition methods for non-overlapping CNNs [27]; and (ii) stochastic gradient-descent, inspired by the practical connection with deep learning. The latter setting is not addressed by these tensor-decomposition analyses and therefore is the main focus of our work.

Our analysis makes two key structural assumptions: we consider the setting where ϕ\phi is non-degenerate, in the sense that EG∼N(0,1)[ϕ′(G)]:=κ≠0\mathbb{E}_{G\sim\mathcal{N}(0,1)}[\phi'(G)] := \kappa\ne01, and further assume that the planted directions are delocalized, unaligned with the basis on which the non-linear activations act. Exploiting these two assumptions, we analyze online SGD in the case (K=2)(K=2), the immediate multiscale extension of the single-index setting, we establish a sample complexity of n=O(d(log⁡(d)2+log⁡ϵ−1))n = O(d(\log(d)^2 + \log\epsilon^{-1})) to achieve error ϵ\epsilon, nearly matching the spectral estimator up to logarithmic factor. It is important to emphasize that the machinery of Ben Arous et al. [2] does not directly apply in this setting, due to the non-Gaussian features seen by the second hidden layer activations.

Related Works. Understanding the benefits of depth in Neural Networks is a longstanding question in the field, with initial progress centered on approximation questions [30, 17]. The efforts then moved towards incorporating optimization aspects, with early notable works such as [29, 21], and later developed in [32, 26, 1]. One aspect shared by all these works is the fact that the input high-dimensional distribution is rotation-invariant, ie with no particular physical structure. Early works that also exploited tensor representations of data to capture scale separation are [10], which focused on expressivity.

The closest works to ours are [15] and [28], which we discuss briefly. Dandi et al. [15] study Single/Multi-Index Gaussian Hierarchical Targets f∗(x)=g∗(a∗⊤Pk(W∗x)/de1)f^*(x) = g^*(a^{*\top}P_k(W^*x)/\sqrt{d^{e_1}}) with W∗∈Rde1×dW^* \in\mathbb{R}^{d^{e_1}\times d}, where the hierarchy is one of dimensions d→de1→1d \to d^{e_1} \to1. They train a three-layer MLP layer-wise and propagate Hermite decompositions across layers via the asymptotic Gaussianity of the inner statistic h∗h^*, which holds because E(Pk)=2\mathbb{E}(P_k)=2. Our setup differs in three essentials: (1) the hierarchy is one of physical scales (within- versus cross-patch), with both layers acting in the same dimension dd on single-index teachers β∗,θ∗∈Sd−1\beta^*,\theta^* \in\mathbb{S}^{d-1}; (2) both layers are trained jointly by online SGD on the same timescale, so the second-layer student sees a moving, non-Gaussian feature map throughout; and (3) at E(ϕ)=1\mathbb{E}(\phi)=1 the inner statistic is not asymptotically Gaussian, so we replace the CLT by a quantitative Stein/Lindeberg comparison driven by the delocalization. Ren et al. [28] prove that LL-layer convolutional networks trained layer-wise learn LL-level Random Hierarchy Models with O(m1+o(1)L)O(m^{1+o(1)}L) samples, via a problem-independent “shallow-to-deep chaining” reduction: layer-wise training succeeds whenever the target correlates with lower-level latents, the signal to lower layers is clean, and the lower-level features are weakly identifiable. Their setting is complementary to ours: The data are discrete tokens drawn from a probabilistic context-free grammar rather than continuous Gaussian patches, and the targets are categorical class labels rather than scalar regressions, so the relevant geometry is a tree of synonym classes rather than the product sphere. Our companion work [5] shows that under correlation loss between teacher model and student model E[fθ(X)fθ∗(X)]\mathbb{E}[f_{\theta}(X)f_{\theta^*}(X)] when initialized in a favorable basin of constant-in-dd probability, online SGD achieves achieves weak recovery in O~(dK−1)\widetilde{O}(d^{K-1}) samples, and continues to 1−αd(1)1-\alpha_d(1) overlap after a lower-order continuation phase, for any fixed depth KK. Yet it remains unclear how the online SGD behaves under standard loss such as Mean Square Error (MSE) loss, which is the main focus of this work.

Notation: All expectations EX\mathbb{E}_X are with respect to XX, with the directions held fixed, unless explicitly stated otherwise. For unit vectors u,vu,v, define the sign-invariant distance dist⁡±(u,v):=min⁡{∥u−v∥2,∥u+v∥2}\operatorname{dist}_{\pm}(u,v) := \min\{\lVert u-v\rVert_2,\lVert u+v\rVert_2\}.

The Multiscale Single-Index Model

Let K≥1K \ge1 be fixed. We model the input as a KK-th order Gaussian tensor of dimension dd, ie X∈(Rd)⊗KX \in(\mathbb{R}^d)^{\otimes K} have independent N(0,1)N(0,1) entries. Given unit vectors θ1,…,θK∈Sd−1\theta_1,\ldots,\theta_K \in S^{d-1}, define Z(0)=XZ^{(0)} = X, and recursively

Yir+1,…,iK(r)=∑j=1dθr(j)Zj,ir+1,…,iK(r−1),1≤r≤K,(1)Y^{(r)}_{i_{r+1},\ldots,i_K} = \sum_{j=1}^{d} \theta_r(j) Z^{(r-1)}_{j,i_{r+1},\ldots,i_K}, \qquad1 \le r \le K, \tag*{(1)}
Z(r)=ϕ(Y(r))entrywise.Z^{(r)} = \phi(Y^{(r)}) \quad\text{entrywise}.

At the final layer Z(K)∈RZ^{(K)} \in\mathbb{R}, and we write fθ(X):=Z(K)f_\theta(X) := Z^{(K)}. As illustrated in Figure 1, this is a stylized model of a NN with physical structure: each layer computes local and translation-invariant features at a fixed spatial scale. In the case where K=2K = 2, for instance, the first layer extracts a single shared ‘local’ feature θ1∗\theta_1^* capturing internal correlations within each patch, while the second layer extracts a coarse feature θ2∗\theta_2^* capturing correlations across patches.

Our algorithmic approaches will be based on two main assumptions:

Assumption 2.1 (Non-degeneracy and regularity, informal). Let G∼N(0,1)G \sim N(0,1). We assume

Eϕ(G)=0,Eϕ(G)2=1,κ:=Eϕ′(G)≠0.(2)\mathbb{E}\phi(G) = 0,\qquad\mathbb{E}\phi(G)^2 = 1,\qquad\kappa:= \mathbb{E}\phi'(G) \ne0. \tag*{(2)}

Further, ϕ\phi satisfies certain standard regularity assumptions, which differ slightly on each setting (discussed in each section).

In the language of Ben Arous et al. [2], non-degeneracy corresponds to the case where the information exponent of ϕ\phi is 1. In the shallow setting K=1K = 1, this assumption greatly simplifies the geometry of the model, ensuring a descent direction from random initializations. In our setting K>1K > 1, the non-degeneracy is instrumental for gradient methods to escape the mediocrity, as will be shown in later sections.

Assumption 2.2 (Incoherence, informal). The planted directions are delocalized, in the sense that ∥θk∥∞≪1\lVert\theta_k\rVert_\infty\ll1.

Incoherence corresponds to the notion that no patch exerts an dominant influence on the output, and enables a mean-field approximation, or equivalently a Gaussian universality in our SGD analysis, similarly as in [18].

Main Result

We now turn to verify that, indeed, K=2K = 2 is a tractable setting for SGD dynamics to achieve strong recovery under the natural MSE loss rather than linear correlation in our companion paper [5]. For ease of presentation, we name θ1∗=θ∗\theta_1^* = \theta^* and θ2∗=β∗\theta_2^* = \beta^* in the remainder of this section.

Setup

Given the teacher direction (θ∗,β∗)∈Sd−1×Sd−1(\theta^*, \beta^*) \in\mathbb{S}^{d-1} \times\mathbb{S}^{d-1} we want to study the ability of online stochastic gradient descent (online SGD) to minimize the population loss

L(βt,θt):=∥fβt,θt−fβ∗,θ∗∥2=Ex∼γD[fβt,θt(x)−fβ∗,θ∗(x)]2,(3)\mathcal{L}(\beta_t, \theta_t) := \lVert f_{\beta_t,\theta_t} - f_{\beta^*,\theta^*} \rVert^2 = \mathbb{E}_{x \sim\gamma_D}[f_{\beta_t,\theta_t}(x) - f_{\beta^*,\theta^*}(x)]^2, \tag*{(3)}

where the label is generated by zi:=ϕ(Xi⋅β∗)z_i := \phi(X_i \cdot\beta^*), fβ∗,θ∗(X):=ψ(z⋅θ∗)f_{\beta^*,\theta^*}(X) := \psi(z \cdot\theta^*), i∈[d]i \in[d]. To recover the teacher, we run online SGD on Sd−1×Sd−1\mathbb{S}^{d-1} \times\mathbb{S}^{d-1}:

References

  1. [1]Z. Allen-Zhu and Y. Li. What Can ResNet Learn Efficiently, Going Beyond Kernels? In Advances in Neural Information Processing Systems, 2019.
  2. [2]G. B. Arous, R. Gheissari, and A. Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference, 2021.
  3. [3]J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12):5451–5460, 2019.DOI
  4. [4]A. Bietti, J. Bruna, and L. Pillaud-Vivien. On learning gaussian multi-index models with gradient flow. arXiv preprint arXiv:2310.19793, 2023.arxiv.org/abs/2310.19793
  5. [5]J. Bruna. The multiscale single-index model: A stylized model for hierarchical feature learning, 2026.arxiv.org/abs/2607.03347
  6. [6]J. Bruna and D. Hsu. Survey on algorithms for multi-index models, 2025.arxiv.org/abs/2504.05426
  7. [7]J. Bruna and S. Mallat. Invariant scattering convolution networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1872–1886, 2013.
  8. [8]J. Bruna, L. Pillaud-Vivien, and A. Zweig. On single index models beyond gaussian data, 2023.arxiv.org/abs/2307.15804
  9. [9]R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud. Neural ordinary differential equations, 2019.arxiv.org/abs/1806.07366
  10. [10]N. Cohen, O. Sharir, and A. Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on learning theory, pages 698–728. PMLR, 2016.arxiv.org/abs/1509.05009
  11. [11]H. Cui, L. Pesce, Y. Dandi, F. Krzakala, Y. M. Lu, L. Zdeborová, and B. Loureiro. Asymptotics of feature learning in two-layer networks after one gradient-step. arXiv preprint arXiv:2402.04980, 2024.arxiv.org/abs/2402.04980
  12. [12]A. Damian, J. Lee, and M. Soltanolkotabi. Neural Networks can Learn Representations with Gradient Descent. In Proceedings of the Thirty Fifth Conference on Learning Theory, 2022.arxiv.org/abs/2206.15144
  13. [13]A. Damian, L. Pillaud-Vivien, J. D. Lee, and J. Bruna. Computational-statistical gaps in gaussian single-index models. arXiv preprint arXiv:2403.05529, 2024.arxiv.org/abs/2403.05529
  14. [14]Y. Dandi, F. Krzakala, B. Loureiro, L. Pesce, and L. Stephan. Learning two-layer neural networks, one (giant) step at a time. arXiv preprint arXiv:2305.18270, 2023.arxiv.org/abs/2305.18270
  15. [15]Y. Dandi, L. Pesce, L. Zdeborová, and F. Krzakala. The computational advantage of depth: Learning high-dimensional hierarchical functions with gradient descent, 2025.DOI
  16. [16]R. Dudeja and D. Hsu. Learning single-index models in gaussian space. In Conference On Learning Theory, pages 1887–1930. PMLR, 2018.
  17. [17]R. Eldan and O. Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907–940. PMLR, 2016.
  18. [18]R. Gheissari and A. Jagannath. Universality of high-dimensional scaling limits of stochastic gradient descent. arXiv preprint arXiv:2512.13634, 2025.arxiv.org/abs/2512.13634
  19. [19]K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition, 2015.arxiv.org/abs/1512.03385
  20. [20]N. Joshi, T. Misiakiewicz, and N. Srebro. On the complexity of learning sparse functions with statistical and gradient queries. arXiv preprint arXiv:2407.05622, 2024.arxiv.org/abs/2407.05622
  21. [21]E. Malach, G. Yehudai, S. Shalev-Schwartz, and O. Shamir. The connection between approximation, depth separation and learnability in neural networks. In Conference on Learning Theory, pages 3265–3295. PMLR, 2021.arxiv.org/abs/2102.00434
  22. [22]S. Mallat. Understanding deep convolutional networks. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 374(2065):20150203, 2016.DOI
  23. [23]M. Mondelli and A. Montanari. Fundamental limits of weak recovery with applications to phase retrieval. In Conference On Learning Theory, pages 1445–1450. PMLR, 2018.arxiv.org/abs/1708.05932
  24. [24]A. Montanari and E. Richard. A statistical model for tensor pca. Advances in neural information processing systems, 27, 2014.arxiv.org/abs/1411.1076
  25. [25]A. Montanari and Z. Wang. Phase transitions for feature learning in neural networks, 2026.arxiv.org/abs/2602.01434
  26. [26]E. Nichani, A. Damian, and J. D. Lee. Provable guarantees for nonlinear feature learning in three-layer neural networks. Advances in Neural Information Processing Systems, 36, 2023.arxiv.org/abs/2305.06986
  27. [27]S. Oymak and M. Soltanolkotabi. Learning a deep convolutional neural network via tensor decomposition. Information and Inference: A Journal of the IMA, 10(3):1031–1071, 2021.DOI
  28. [28]Y. Ren, Y. Dandi, F. Krzakala, and J. D. Lee. Provable learning of random hierarchy models and hierarchical shallow-to-deep chaining, 2026.arxiv.org/abs/2601.19756
  29. [29]I. Safran and J. Lee. Optimization-based separations for neural networks. In P.-L. Loh and M. Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3–64. PMLR, 02–05 Jul 2022.arxiv.org/abs/2112.02393
  30. [30]M. Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pages 1517–1539. PMLR, 2016.arxiv.org/abs/1602.04485
  31. [31]Z. Wang, E. Nichani, and J. D. Lee. Learning hierarchical polynomials with three-layer neural networks. arXiv preprint arXiv:2311.13774, 2023.arxiv.org/abs/2311.13774
  32. [32]Z. Wang, E. Nichani, and J. D. Lee. Learning hierarchical polynomials with three-layer neural networks, 2023.arxiv.org/abs/2311.13774

Paper details

vlnc:W_gectpphv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents