PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Orthogonal Multi-Index Models Beyond Small Initialization: Incremental Learning, Competitive Dynamics and Symmetry

Mo Zhou, Weihang Xu, Simon S. Du, Maryam Fazel

arXiv:2609.10879v1cs.LGstat.ML

TL;DR

Existing analyses leave feature-learning dynamics under standard initialization unresolved because neuron interactions are substantially stronger. This paper uses symmetry-based finite-width analysis to show that incremental learning persists, with competitive parameter-mass reallocation driving recovery of target directions.

  • Problem

    Prior analyses leave the technically challenging standard-initialization regime unresolved, where non-negligible network outputs induce collective neuron interactions.

    Source: §1 · p. 2

  • Method

    The analysis compares the network directly with a finite symmetrized counterpart, exploiting target and dynamical symmetries instead of an infinite-width limit.

    Source: §4 · p. 6, §7 · p. 11

  • Results

    Under standard initialization, modified gradient flow learns orthogonal multi-index targets with polynomial samples, while loss decreases in Hermite order and parameter mass reallocates competitively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Competitive mass reallocation is an additional feature-learning mechanism beyond small initialization, and symmetry-based finite-width approximation may generalize to other symmetric problems.

    Source: §1 · p. 2, §7 · p. 11

    The analysis does not directly cover vanilla gradient flow, non-isotropic or near-orthogonal targets, or optimal sample-complexity rates.

    Source: §7 · p. 11

Abstract

from arXiv · show

Recent work has identified incremental learning in shallow networks trained on single-index and multi-index models. However, existing analyses often rely on simplifying settings, such as small initialization, correlation loss, or layer-wise training. These choices reduce neuron interactions and leave some feature learning dynamics under standard initialization unexplored. We study training dynamics for polynomial-width two-layer networks learning orthogonal multi-index targets under standard initialization using polynomially many samples. We first prove that incremental learning still occurs: the loss decreases sequentially according to the Hermite expansion of the target, with lower-order components learned before higher-order components recover the individual target directions. In this standard initialization regime, training also shows a competitive reallocation of parameter mass: after the total mass fits the target mean and stabilizes, mass shifts into the target subspace and then concentrates on aligned neurons. Our theoretical analysis uses slightly modified gradient flow, while vanilla gradient descent empirically exhibits the same qualitative dynamics. Technically, we introduce a symmetry-based finite-width approximation via symmetrized networks, rather than comparing directly with an infinite-width limit. This yields better control of approximation errors and may be of independent interest.

1 Introduction

The paper shows that incremental learning persists for orthogonal multi-index targets under standard initialization, despite interacting neurons and non-negligible network output. It identifies competitive parameter-mass reallocation as the mechanism and develops a symmetry-based finite-width analysis to control these dynamics.

1.1 Related works, key challenges and our contributions

  • Unlike prior analyses relying on small initialization, correlation loss, layer-wise training, or infinite-width limits, this work studies interacting finite-width square-loss dynamics without layer-wise training.It characterizes both incremental loss reduction and competitive mass reallocation for orthogonal multi-index targets.Source: §1 · p. 1, §1.1 · pp. 3–4
  • Standard initialization creates interacting dynamics because the network output is non-negligible, unlike the approximately decoupled target-driven dynamics produced by small initialization.These interactions make standard-initialization analysis technically more challenging.Source: §1 · p. 2, §1.1 · pp. 2–3

1 Introduction

  • Under standard initialization, the population loss decreases in Hermite order: the network fits the mean, recovers the target subspace, then identifies individual target directions.The analyzed modified gradient flow learns orthogonal multi-index targets to small population loss with polynomial width and samples.Source: §1 · p. 2
  • After fitting the mean, parameter mass is competitively reallocated from irrelevant directions into the target subspace and then from diffuse neurons to target-aligned neurons.This mechanism differs from independent amplification of weakly aligned neurons and yields competitive feature learning under standard initialization.Source: §1 · p. 2, §1.1 · p. 3

1.1 Related works, key challenges and our contributions

  • The effective competitive dynamics have a Lotka–Volterra-type structure, with mass constrained after zeroth-order fitting and redistributed during second- and higher-order learning.Second-order learning moves mass into the target subspace, while higher-order learning favors neurons aligned with individual target directions.Source: §1.1 · p. 3
  • A symmetry-based finite symmetrized network preserves tractable population invariances while maintaining finite-particle correspondence, enabling polynomial-width coupling guarantees.The approach avoids projecting neurons onto the sphere and controls the actual finite-width empirical trajectory under standard initialization.Source: §1.1 · p. 3

2 Preliminaries and problem setup

The paper studies two-layer networks learning orthogonal multi-index targets from Gaussian data, using standard initialization and even activations under a mean-field scaling. Training uses empirical square loss with gradient flow and weight decay, while Hermite and tensor decompositions organize the population loss by degree.

Setup

  • The setup uses Gaussian inputs and an orthogonal multi-index target whose directions are rotated without loss of generality to coordinate vectors.The target directions are orthonormal, and Gaussian rotational invariance permits setting w∗_j = e_j for all j ≤ r.Source: §2 · p. 4
  • The learner is a mean-field-scaled two-layer network with a 2-homogeneous parametrization of neuron weights.The scaling factor is 1/m, with parameters W = (w_1, …, w_m)^⊤ and normalized directions w_i = w_i/∥w_i∥_2.Source: §2 · p. 4

Activation assumption

  • The activation is even, allowing either absolute value or a smooth bounded-derivative activation with only even Hermite coefficients, including symmetrized ReLU-type activations.ReLU becomes |x|, while GeLU and Swish yield smooth even activations after symmetrization.Source: §2 · p. 4

Training dynamics

  • Training minimizes empirical square loss with gradient flow, weight decay, and standard random initialization whose neuron norms are approximately one.The default choice is λ_t = λ with λ = rλ_0 for sufficiently small λ_0 and γ_t,i = 1, aside from a short technical modification interval.Source: §2 · p. 4

Hermite and tensor decomposition

  • Hermite orthogonality decomposes the population loss into degree-wise tensor terms, so fitting degree k means matching the network tensor T_k to the target tensor T∗_k.The decomposition uses Gaussian correlations of Hermite features and defines projections onto degree-k and higher Hermite subspaces.Source: §2 · p. 5

3 Main Results

Under standard initialization, a polynomial-width two-layer network learns orthogonal multi-index targets from polynomially many samples, with population loss decreasing in Hermite order. The result also characterizes target recovery and distinguishes this loss-based incremental learning from small-initialization analyses.

Incremental learning

  • The population loss decreases sequentially according to the target’s Hermite expansion, reducing each component after its transition while leaving later components present beforehand.Thus the theorem specifies both final recovery and the order in which target components are learned.Source: §3 · p. 5

Main theorem

  • Theorem 3.1 guarantees target recovery under standard initialization using polynomial width and samples, with high probability and suitable weight decay and stepsize schedules.The theorem applies under Assumption 1 and permits target error ε > e−log2 r.Source: §3 · p. 5

Quantitative scope

  • The polynomial width and sample requirements are non-optimal because they arise from finite-width coupling arguments.Further quantitative discussion appears in Appendix A.2.Source: §3 · p. 6

Relation to prior analyses

  • The result establishes incremental learning through true square-loss decrease, unlike small-initialization analyses that often use support or subspace recovery instead [AAM23] [DKL+24].It is closer in spirit to [BBPV23] [RNWL25], while addressing a different setting and technical challenges.Source: §3 · p. 6

Proof strategy

  • The proof constructs a finite symmetrized network, analyzes its population dynamics, and couples those dynamics to the actual empirical network.This strategy is developed across Sections 4–6 and captures both incremental and competitive dynamics.Source: §3 · p. 6

4 Symmetry in Dynamics

The proof exploits invariance of the target and population dynamics under coordinate sign flips and irrelevant-coordinate permutations, enforcing this symmetry directly with a finite symmetrized network rather than an infinite-width limit.

Symmetry in population dynamics

  • The finite group P independently flips coordinate signs and permutes irrelevant coordinates, leaving the target invariant because it depends only on the first r coordinates.The Gaussian distribution, target, and population loss are P-invariant, making the population gradient field equivariant.Source: §4 · p. 6
  • If the particle measure is P-invariant at time T, population gradient flow preserves that invariance for all t ≥ T, and the induced network remains P-invariant.This is Claim 1’s symmetry-preservation result.Source: §4 · p. 6
  • Conditional sign symmetry eliminates odd Hermite-gradient monomials and forces second-moment matrices to be diagonal, with only tensor entries having even coordinate multiplicities surviving.These cancellations simplify the population dynamics’ tensor structure.Source: §4 · pp. 6–7

Symmetrized networks

  • The method enforces target and population-dynamics symmetry at finite width through symmetrization, showing that the simplification comes from symmetry rather than infinite width and may extend to other groups.This contrasts with related infinite-width analyses.Source: §4 · p. 7
  • Symmetrizing a finite network copies every neuron along its P-transform, producing exactly P-invariant networks with m|P| neurons.Because each transformation is orthogonal, this is equivalent to replacing each neuron wi by ρ^-1(wi).Source: §4 · p. 7
  • The analysis first controls the symmetrized component, then proves the original finite-width network stays close to it, avoiding comparison with an infinite-width object.The decomposition’s cross term vanishes because the symmetrized residual is invariant while the difference has zero group average.Source: §4 · p. 7

5 Training dynamics of symmetrized network under population loss

The symmetrized network exhibits incremental learning through recurring competitive dynamics: parameter mass is first allocated to the mean, then the target subspace, and finally aligned target directions. Weight decay accelerates competitive mass transfer, while higher-order terms complete directional and norm fitting.

5.1 A recurring competitive ODE

  • A competitive ODE reallocates mass from a competing component q to a favored component p while their shared growth term controls total scale.As long as p < 1, q/p decreases; weight decay yields exponential competitor decay, whereas λ = 0 gives polynomial decay q(t) = Θ(1/t).Source: §5.1 · pp. 7–8

5.2 Training dynamics in stages

  • Stage 1.1 rapidly fits the 0th-order mean by growing total parameter mass from order one to r − λ/(2bσ2_0) in time e O(1/r).During this stage, neuron directions and relative norms remain essentially fixed, producing the first loss drop.Source: §5.2 · p. 8
  • Stage 1.2 transfers mass from irrelevant coordinates into the target subspace, taking O(log d) time and producing the second loss drop.The target-subspace mass has an additional competitive advantage, and neurons become almost entirely supported there while retaining their initial within-subspace directions.Source: §5.2 · p. 8
  • Stage 2.1 amplifies a small initial advantage, with best initial coordinate about 2 log(m)/r, and discovers all individual target directions in time O(r/log m).The potential-neuron sets Spot,i are disjoint with high probability, while remaining neurons stay small and spread out within the target subspace.Source: §5.2 · p. 9
  • Stages 2.2–2.3 transfer mass from dense non-aligned neurons to aligned neurons through another competitive ODE, fitting the target up to weight-decay bias and then reaching loss at most ε.Stage 2.2 takes O(log(1/ε_norm)) time, while Stage 2.3 sets λ = 0 to remove the residual bias.Source: §5.2 · p. 9

6 Coupling the symmetrized network and finite-width network

The section couples the actual finite-width empirical dynamics directly to a finite symmetrized network, rather than to an infinite-width limit. This yields a polynomial-width coupling that transfers the symmetrized network’s incremental and competitive dynamics to the finite network.

Coupling construction

  • The analysis couples the finite empirical network directly to a finite symmetrized network, avoiding comparison with an infinite-width limit [GWB25].This symmetry-based reference system is designed to preserve the finite-width structure while enabling transfer of the population analysis.Source: §6 · p. 9

Error decomposition

  • The function-space discrepancy splits into particle-coupling error and finite-width P-sampling error.The decomposition f − f̃ = (f − f̌) + (f̌ − f̃) separates differences between empirical particles and symmetrized representatives from sampling one transform per particle versus averaging all P transforms.Source: §6 · p. 10

Coupling result

  • Finite-width coupling transfers the symmetrized network’s incremental and competitive dynamics to the actual empirical network.Under Theorem 3.1, the normalized maximum particle discrepancy satisfies Δmax(t) ≤ ε^1/6 for all t ≤ T^2.Source: §6 · p. 10

Proof strategy

  • A stage-wise Gronwall argument controls stability, function-space discrepancy, and finite-sample error despite the dynamics being noncontractive.The stability term is tied to particle-norm growth, while the other terms are controlled by function-space and sample-size bounds, yielding Lemma 6.1 similar to.Source: §6 · p. 10

Width control

  • The stage-wise symmetrized analysis handles time ω(log d) with polynomial width, whereas a crude e^T stability bound would require super-polynomial width [GWB25].This provides the key width-control advantage of the symmetry-adapted coupling.Source: §6 · p. 10

Broader contribution

  • More generally, useful target and population symmetries can motivate finite symmetrized reference systems coupled to actual finite-width dynamics.The perspective may also combine with recent propagation-of-chaos techniques [GWB25].Source: §6 · pp. 10–11

7 Conclusion · A Omitted results and proofs in Sections 2 to 4 · A.1 Omitted results and proofs in Section 2

The paper shows that incremental learning and competitive parameter-mass reallocation persist beyond small initialization, using a symmetry-based finite-width approximation. The appendices provide omitted formulas and proofs, including conditional-symmetry dynamics and the main theorem, while identifying open analytical and sample-complexity questions.

7 Conclusion

  • Incremental learning persists beyond small initialization, alongside competitive reallocation of parameter mass, for overparameterized two-layer networks learning orthogonal multi-index targets.The analysis exploits target and dynamical symmetry rather than comparing directly with an infinite-width limit.Source: §7 · p. 11
  • A symmetry-based finite-width approximation compares the network with a finite symmetrized counterpart and may extend to other feature-learning problems with exploitable symmetries.Source: §7 · p. 11
  • Open questions include removing the technical gradient-flow modification, treating non-isotropic or near-orthogonal settings [OSSW24] [RNWL25], and obtaining optimal sample-complexity rates.Current bounds separate feature learning from fixed-kernel methods but do not match rates suggested by information-exponent analyses [AGJ21] [RL24].Source: §7 · p. 11

A Omitted results and proofs in Sections 2 to 4

A.1 Omitted results and proofs in Section 2

  • For σ(x) = |x|, the Hermite coefficients satisfy |bσk| = Θ(k−5/4) and vanish for odd k, supporting the appendix’s loss and gradient derivations.The appendix uses the Hermite expansion to state the exact loss and dynamics.Source: §A.1 · p. 16
  • Conditional symmetry makes the coordinate dynamics tractable: odd polynomials vanish, relevant expressions become sums of even polynomials, and the resulting terms are non-negative.The appendix defines conditional symmetry as invariance under coordinate sign flips.Source: §A.1 · pp. 16–17
  • Each coordinate evolves multiplicatively, with velocity proportional to the coordinate itself, helping control initially small coordinates; conditional symmetry is preserved by the symmetric network dynamics.Source: §A.1 · p. 17
  • The appendix notes that the gradient formula in appears inconsistent with its tensor form, with discrepancies as large as kO(k), while its results should remain valid after proof modifications.The discrepancy is illustrated using a fourth-order term.Source: §A.1 · p. 17

A.2 Omitted results and proofs for Section 3 · A.3 Omitted results and proofs in Section 4

The appendices specify sufficient parameter regimes and prove Theorem 3.1 via a symmetrized trajectory before transferring guarantees to the finite-width network. They also formalize a symmetry-based loss decomposition and explain why controlling the resulting variance term is nontrivial during training.

A.2 Omitted results and proofs for Section 3

  • The analysis assumes log_2 d < r/log_2 r < r log_2 r < log_3 d, width d^3 ≤ m ≤ poly(d), and sample size n ≥ d^(3+c).Exact degree conditions on d are needed only for the coupling section, while the dynamic analysis requires m = poly(d).Source: §A.2 · p. 18
  • Related analyses obtain sharper sample-complexity bounds by recovering the target subspace from degree 2 and individual directions from higher-order components, but use spherical SGD with correlation loss and separate second-layer fitting.For orthogonal multi-index models, different Hermite orders reveal different target structure, so a single information exponent is insufficient.Source: §A.2 · p. 18
  • Theorem 3.1 uses sufficient, non-optimal conditions m ≥ d^3 and n = Θ(d^(3+c)) to control the finite-width training trajectory rather than establish sharp learnability thresholds.The quantitative requirements arise largely from the finite-width coupling framework, while sharper bounds are left for future refinement.Source: §A.2 · p. 18
  • The symmetrized trajectory reaches the target regime within time T_2 ≲ r/log m, with stage-wise bounds producing the order-by-order loss profile across transition times.The proof combines initialization guarantees with stage-wise dynamics lemmas before transferring the result to the actual finite-width empirical trajectory.Source: §A.2 · p. 18
  • The proof obtains L(W(T_2)) ≤ e^(-log_2 r) ≤ ε, while absolute-value activation admits an additional local-convergence phase to arbitrary target accuracy ε.The post-T_2 phase has the stated sample-complexity and time guarantees.Source: §A.2 · p. 18

A.3 Omitted results and proofs in Section 4

  • Symmetrization decomposes twice the square loss into the symmetrized-network loss plus the discrepancy loss: 2E_x[(f_θ(x) − f*(x))^2] = E_x[(f̃_θ(x) − f*(x))^2] + E_x[(f_θ(x) − f̃_θ(x))^2].The cross term vanishes because the target and symmetrized model are invariant under the symmetry group.Source: §A.3 · p. 19
  • The decomposition can be interpreted as a function-space bias–variance split, with the symmetrized loss as bias and the discrepancy from symmetrization as variance.Although the variance is expected to be small at large width under random initialization, it may grow during training as the model scale increases, requiring explicit bounds.Source: §A.3 · p. 19

B Initialization · B.1 Concentration · C Stage 1: learn mean and subspace (0-th and 2nd order term)

Under sufficient overparameterization, initialization satisfies high-probability regularity properties that control individual neurons and the scarcity and separation of potential neurons. Stage 1 then sequentially fits the mean before reallocating norm toward the target subspace through the second-order component.

B Initialization

  • With sufficient overparameterization, the analysis conditions on high-probability initialization events providing neuron-level and distributional regularity.These events include individual-neuron bounds and regularity for the neuron population.Source: B Initialization · pp. 19–20
  • Potential neurons are scarce at initialization, with at most m^o(1) such neurons under the stated scaling.The bound follows from a tail estimate and a Chernoff argument.Source: B Initialization · pp. 20–21
  • Potential neurons have a coordinate gap, while no neuron is simultaneously bad for two distinct target directions with high probability.The reported failure probability for the no-bad-neuron event is at most m^-0.95.Source: B Initialization · pp. 20, 22

B.1 Concentration

  • The spherical-coordinate concentration lemma controls squared coordinates of uniform spherical vectors when r is sufficiently larger than log^2 n.Its tail estimates yield failure probability at most δ under the stated parameter conditions.Source: §B.1 · p. 22

C Stage 1: learn mean and subspace (0-th and 2nd order term)

  • Stage 1 is divided into learning the 0th-order component and learning the 2nd-order component to recover the target subspace.The section assumes each normalized neuron direction has squared norm 1 − o(1).Source: C Stage 1: learn mean and subspace… · pp. 22–23
  • In Stage 1.1, neuron directions remain essentially unchanged while neuron norms grow to fit the mean, namely the 0th-order component.This separates norm growth from directional learning during mean fitting.Source: C Stage 1: learn mean and subspace… · p. 23
  • In Stage 1.2, directions inside and outside the target subspace remain essentially fixed while target-subspace norm grows and irrelevant-subspace norm decreases.This reallocates parameter norm toward the target subspace while learning the 2nd-order component.Source: C Stage 1: learn mean and subspace… · p. 23

C.1 Stage 1.1: learn 0-th order · C.1.1 Omitted proofs for Stage 1.1

Stage 1.1 learns the target’s 0-th-order term within a controlled time while neuron directions and norms remain stable. The omitted proofs establish this through induction hypotheses, simplified dynamics, and convergence of the scalar parameter.

C.1 Stage 1.1: learn 0-th order

  • Stage 1.1 ends by time T11 = O(...), with the dynamics dominated by the 0-th-order term and the loss bounded by cbσ2.The supplied statement truncates the full expression for the time bound.Source: §C.1 · pp. 23–24
  • At the stage endpoint, each neuron’s direction remains essentially unchanged, while the relevant norm and regularity bounds continue to hold.The endpoint properties are summarized across the main lemma and induction hypothesis.Source: §C.1 · pp. 23–24
  • The induction hypothesis tracks stable neuron directions, norms, and regularity, and Stage 1.1 ends before any of these conditions fails.This provides the self-consistency argument needed to maintain the stage assumptions.Source: §C.1 · pp. 23–24
  • Under the induction hypothesis, random-initialization bounds transfer to the evolving neurons, enabling the stage’s simplified dynamics.The transfer uses the fact that neuron directions move little during this stage.Source: §C.1 · p. 24

C.1.1 Omitted proofs for Stage 1.1

  • The scalar parameter α̃ converges to its target value up to error 1/r^10 within the stage’s prescribed time.The convergence proof solves the differential equation obtained from the simplified dynamics.Source: §C.1 · p. 24, §C.1.1 · p. 27
  • The omitted proofs close the induction by contradiction: direction, norm, and regularity stopping times cannot occur before T11.Each possible premature stopping event contradicts the bounds derived from the simplified dynamics.Source: §C.1.1 · pp. 25–26
  • The simplified dynamics make higher-order gradient terms error contributions, so the 0-th-order component controls the evolution during Stage 1.1.The proof bounds higher-order terms using the induction hypothesis and auxiliary initialization estimates.Source: §C.1 · p. 24, §C.1.1 · pp. 26–27

C.2 Stage 1.2: learn target subspace (2nd-order term)

Stage 1.2 suppresses the second-order term while learning the target subspace: ||v_≤r||2/||v||2 rises from Θ(r/d) to 1−o(1). Within O(log d) time, target-subspace learning proceeds without changing neuron directions inside or outside that subspace.

C.2 Stage 1.2: learn target subspace (2nd-order term)

  • The target-subspace mass ratio increases from Θ(r/d) to 1−o(1), while the second-order term becomes small.Source: §C.2 · p. 28
  • Stage 1.2 ends within T12−T11 ≲ log d, with neuron directions remaining unchanged within the target and irrelevant subspaces.Source: §C.2 · p. 28
  • Incremental learning persists: the loss remains near its pre-stage level until late Stage 1.2, then reaches the second-order target level at T12.Source: §C.2 · p. 28
  • The second-order dynamics converge within O(log d), then receive an additional O(log log d) refinement to improve the terminal bound.Source: §C.2 · pp. 30–31
  • The convergence analysis tracks coupled target and non-target second-order coefficients, with β1 approaching its target while β2 remains on the scale r/d.Source: §C.2 · pp. 31–32

C.2.1 Omitted proofs for Stage 1.2

The omitted proofs establish the Stage 1.2 induction hypothesis and derive its key time, norm, coordinate, and convergence controls. In particular, the stage completes within O(log d), while the convergence analysis characterizes both the final and intermediate-time behavior.

C.2.1 Omitted proofs for Stage 1.2

  • Stage 1.2 ends at T12 = eT12 ≤ ˆT12 ≲ log d, by ruling out earlier termination at the direction, norm, or regularity stopping times.The proof identifies eT12 with T12 and shows T12 ≤ min{Tdir,12, Tnorm,12, Treg,12} as well as T12 ≤ ˆT12 = O(log d).Source: §C.2.1 · pp. 32–33
  • The argument uses invariance under permutations of the last d − r coordinates, together with the exact gradient formula and high-order-term error treatment under IH.Source: §C.2.1 · p. 34
  • The neuron dynamics are obtained from the exact gradient formula, while higher-order terms are bounded as errors under the induction hypothesis to derive population-term dynamics.The argument separately bounds the higher-order gradient contributions and sums them using Claim A.1 before deriving the evolution of the relevant norms and population quantities.Source: §C.2.1 · pp. 34–35
  • The convergence proof shows Tconv = O(log d), with q(Tconv) = r^-1 and the associated bounds obtained at convergence.The proof controls the scaled ratio q through differential inequalities and then translates its decay into bounds on β1 and β2.Source: §C.2.1 · pp. 36–37
  • At tδ = (1 − δ)Tconv, q(tδ) tends to infinity when δ log d ≫ log r, while β1 remains O(1/r^3) and β2 changes only by a constant factor.The intermediate-time argument uses log q(tδ) ≫ log r and translates this through y(t) into the stated β1 and β2 behavior.Source: §C.2.1 · pp. 37–38

D Stage 2: learn target directions (high-order term) · D.1 Induction Hypothesis and Dynamics of Stage 2 · D.1.1 Dynamics

This section analyzes Stage 2 dynamics for learning the ground-truth target directions, organizing the process into direction recovery, aligned-neuron mass growth, and final target recovery. It develops an induction framework and simplified dynamical equations for the relevant neuron populations and target-direction coefficients.

D Stage 2: learn target directions (high-order term)

  • Within T2−T1 ≲ r/log m, Stage 2 learns every ground-truth direction and reduces the loss to ε1/2.Stage 2.1 recovers each direction in O(r/log m), Stage 2.2 grows aligned-neuron mass to â*, and Stage 2.3 removes weight decay for full target recovery.Source: D Stage 2: learn target directions… · pp. 38–39

D.1 Induction Hypothesis and Dynamics of Stage 2

  • The induction hypothesis keeps small-and-dense neurons nearly stationary and balanced, bounds potential-neuron behavior, and preserves alignment for neurons that have learned target directions.The stage ends before any of these induction conditions breaks, with dense-neuron norms bounded by 2ω√r.Source: §D.1 · pp. 39–40

D.1.1 Dynamics

  • The dynamics lemmas simplify small-and-dense, potential, and population evolution by retaining leading low-order gradient terms and controlling higher-order contributions.The population 0th- and 2nd-order dynamics are summarized explicitly for Stage 2, using the neuron-level bounds.Source: §D.1.1 · pp. 41, 43, 46
  • The analysis simplifies the Stage 2 dynamics by invoking Lemmas B.1, D.2(c), and G.2.These lemmas are used to reduce the preceding expressions to more tractable forms.Source: §D.1.1 · pp. 47–48
  • It derives an evolution equation for the spot-related quantity ˜ESpot,k[w2_i] using Lemma D.2(e).The supplied passage identifies this as a distinct dynamical component but does not provide the resulting equation’s full form.Source: §D.1.1 · p. 47
  • The subsection separately derives the dynamics of ˆa_i and ˆa_k from Lemma D.5 and subsequent simplification.The passage states that the final expression gives the dynamics of ˆa_k, while the preceding derivation concerns ˆa_i.Source: §D.1.1 · p. 48

D.2 Stage 2.1 … D.3.1 Dynamics and convergence

This section analyzes the dynamics through alignment and norm adjustment stages: target directions are learned within a small hitting-time gap, after which aligned-neuron norms are fitted while the induction hypothesis is preserved. It concludes convergence by establishing balanced aligned masses, decaying dense mass, and proximity to the target scale.

D.2 Stage 2.1

  • Within Θ(r/log m) time, Stage 2.1 learns every target direction, although the total mass of aligned neurons remains small.The stage also preserves the stated induction-hypothesis conditions and ends before any such condition breaks.Source: §D.2 · pp. 48–49

D.2.2 Convergence

  • Within O(r/log m) time, each ground-truth direction has a nearly perfectly correlated neuron, while all other coordinates of potential neurons remain at most ω/r.The proof uses tensor-power-type dynamics: the largest coordinate grows rapidly, whereas competing coordinates remain nearly unchanged.Source: §D.2.2 · p. 52

D.2.1 Dynamics

  • Balanced second-order population terms make target directions evolve almost independently, while non-target coordinates decay exponentially and remain at most 1/d^2.The simplified dynamics cover small-and-dense neurons, potential neurons, and population 0th- and 2nd-order terms throughout Stage 2.1.Source: §D.2.1 · pp. 51–52, §D.2.2 · p. 52

D.2.2 Convergence

  • All r target directions are learned with hitting times differing by o(log m), and the aligned coordinates remain balanced for later stages.The analysis also establishes that the relevant neuron masses are balanced after convergence.Source: §D.2.2 · p. 55

D.3 Stage 2.2

  • Stage 2.2 grows ground-truth-aligned neurons to fit the target norm, suppresses the remaining neurons, and finishes within polylog(r) time while maintaining Lemma D.2.At its endpoint, the residual norm error is ε_norm = e^−polylog(r), and all conditions of Lemma D.2 hold.Source: §D.3 · p. 57

D.3.1 Dynamics and convergence

  • A transient larger stepsize accelerates norm fitting after direction recovery, increasing aligned mass and decreasing non-aligned mass while preserving the induction hypothesis.The modification addresses fluctuations from the second-order residual in the standard-initialization setting; it only fast-forwards a short adjustment phase.Source: §D.3.1 · p. 58
  • The modified dynamics preserve qualitative behavior: aligned-neuron masses follow a logistic-type convergence, directions stabilize, and vanilla gradient descent exhibits the same behavior empirically.Removing the stepsize simplification remains an open direction, although the paper reports matching qualitative dynamics under vanilla gradient descent.Source: §D.3.1 · pp. 58–59
  • Pairwise logarithmic spread is almost nonincreasing, with accumulated error controlled while err · t < 1.The proof bounds the upper Dini derivative of M_ij by err in every sign quadrant.Source: §D.3.1 · pp. 60–61
  • Within O(λ_0^-1 log(r/ε_norm)) time, dense mass satisfies b̂_i ≤ ε_norm/r for every i and remains so thereafter.The ratio b̂_i/â_i continues decreasing after reaching the bound.Source: §D.3.1 · p. 62
  • After dense mass becomes negligible, aligned masses balance to â_i = ā ± O(ε_norm), with this balance preserved.The argument uses the logarithmic spread U(t) and reaches U = O(ε_norm) within an additional O(log(1/ε_norm)) time.Source: §D.3.1 · p. 62
  • The common aligned scale contracts toward â*, yielding |â_i − â*| = O(ε_norm) and the stated final bounds for every i.The scale converges within an additional O(r^-1 log(1/ε_norm)) time; replacing ε_norm by a sufficiently small constant multiple gives |â_i − â*| ≤ ε_norm and b̂_i ≤ ε_norm.Source: §D.3.1 · p. 62

D.3.2 Proof of Induction Hypothesis Lemma D.2 in Stage 2.2 … Define the hitting times

The appendix proves Stage 2.2’s induction hypothesis by controlling direction, norm, potential, stability, and regularity hitting times, then analyzes later-stage alignment and hitting-time gaps. It also establishes technical bounds supporting the Stage 2 dynamics and shows that aligned neurons reach the target threshold earlier under small perturbations.

D.3.2 Proof of Induction Hypothesis Lemma D.2 in Stage 2.2

  • Stage 2.2 concludes when the relevant direction, norm, potential, stability, and regularity conditions persist through T21+c22 log(1/εnorm), so eT22=T22.The proof checks each stopping time against eT2 and uses earlier lemmas to maintain the induction conditions.Source: §D.3.2 · pp. 62, 64

D.4 Stage 2.3: achieve small loss without weight decay

  • With weight decay removed at Stage 2.3, aligned coefficients grow toward 1 while orthogonal coefficients remain small, yielding small loss within T23−T22≲log(1/εnorm).The stage starts from the Stage 2.2 state, where aligned coefficients are near their target and orthogonal mass is O(εnorm).Source: §D.4 · pp. 64–65

D.5 Technical lemmas for Stage 2

  • The Stage 2 technical lemma bounds higher-coordinate dynamics by partitioning neurons into small-and-dense and potential classes, with separate estimates across ranges of j.Potential neurons are either aligned with a ground-truth direction or have bounded norm, while small-and-dense contributions use auxiliary lemmas.Source: §D.5 · pp. 65–67

D.5.1 Technical lemma for Stage 2.1

  • The Stage 2.1 technical lemma compares the largest and smallest potential-neuron trajectories and aims to show that their times to reach 1−ε differ by little.It formalizes the effect of small perturbations on the trajectories’ threshold-crossing times.Source: §D.5.1 · p. 68

Define the hitting times

  • For ODE trajectories x and y reaching 1−ε at Tx and Ty, positivity makes both trajectories increasing, and separation of variables yields explicit bounds on Ty−Tx.The derived bound is 2aSδy^2+b/(8aS^2δy^2+baS^2ε)≤Ty−Tx≤2(δx−δy).Source: Define the hitting times · pp. 68–70

E (Optional) Stage 3: local convergence · F Coupling the dynamics of symmetrized network with finite-width network · F.1 Proof of Lemma F.1

Stage 3 extends Stage 2 to arbitrary target error through local convergence, while Sections F–F.1 rigorously couple symmetrized, intermediate, and finite-width dynamics using concentration and Lipschitz control.

E (Optional) Stage 3: local convergence

  • The Stage 3 sample complexity improves on [ZGJ21] by reducing its dimension dependence from d2 to d, while the analysis uses absolute-value activation.The paper conjectures a tight 1/t3 convergence rate rather than 1/t and leaves extensions to more general activations for future work.Source: E (Optional) Stage 3: local convergence · p. 71
  • The local argument applies [ZGJ21, Theorem 4] after verifying orthogonality, unit norms, width m ≥ r, local loss, zero λt, and the rescaling w′ = w/√m.Under this mapping, √m∇wL = ∇w′L and the loss is preserved.Source: E (Optional) Stage 3: local convergence · p. 71
  • After Stage 2 establishes L ≤ e−log2 r, Stage 3 reaches arbitrary error ε from threshold ε0 = 1/poly(r), achieving ε loss within time O(r/ε).The local convergence result requires no symmetrized network; it only requires initial loss L(W) ≤ ε0.Source: E (Optional) Stage 3: local convergence · pp. 70–71

F Coupling the dynamics of symmetrized network with finite-width network

  • Section F decomposes the coupling as symmetrized network ≈ intermediate network ≈ finite-width network, controlling neuronwise distances and average coupling error Δ.The resulting bounds require sufficiently large width and small average coupling error.Source: F Coupling the dynamics of symmetrized… · p. 72
  • For sufficiently large width, the intermediate network concentrates around the symmetrized network because its independently transformed neurons average over the symmetry group.The proof uses identical dynamics for corresponding particles, norm preservation under group actions, and Bernstein-type concentration.Source: F Coupling the dynamics of symmetrized… · p. 72
  • Lemma F.2 establishes the finite-width coupling under sample size n > d3+c and width m ≥ d2+c, with subsequent bounds using the Stage 1–2 norm controls.The analysis separately treats neurons not aligned with ground truth and aligned neurons, with εnorm = e−polylog(r) ≫ εdir = m−Θ(1).Source: F Coupling the dynamics of symmetrized… · p. 72

F.1 Proof of Lemma F.1

  • F.1 proves the symmetrized-versus-intermediate bound by representing Gaussian initializations as independent uniform group elements acting on canonical orbit representatives.Conditioned on the representatives, the intermediate network is an average of independent Hilbert-space-valued random elements with mean equal to the symmetrized network.Source: §F.1 · pp. 73–74
  • F.1 upgrades fixed-time concentration to uniform-in-time coupling through Lipschitz bounds, a polynomial h-net, and a union bound; the additive m−40 term is negligible.The argument applies Lemma F.3 across the net and extends the bound to all times up to the Stage 1–2 runtime.Source: §F.1 · pp. 75–76

F.2 Bound ∆max and ∆ … G Technical lemma

This section develops technical bounds for the training analysis, controlling errors, finite-width and finite-sample terms, Jacobian and gradient expansions, and alignment-related quantities. It establishes these results through symmetry-based estimates, Hermite-based formulas, stopping-time arguments, and norm and initialization controls.

F.2 Bound ∆max and ∆

  • Under n > d^(3+c), m ≥ d^(2+c), and t ≤ T2, Lemma F.5 bounds both ∆ and ∆max by combining At, Bt, and Ct estimates with a Gronwall-type argument.The proof proceeds stage by stage, first controlling the average error ∆ and then the individual error ∆max, and closes the stopping-time argument at T2.Source: §F.2 · pp. 76, 80

F.3 Bound of At

  • The At analysis uses symmetry-based Jacobian expansions: all odd-order Jacobian terms vanish, while stage-specific even-order bounds control small-and-dense and potential neurons.The argument is given for ReLU and extends to smooth activations; aligned neurons receive an improved Jacobian bound after T21.Source: §F.3 · pp. 81, 84, 85

F.4 Bound of Bt and E[Bt]

  • For ∆ < 1, Lemma F.10 bounds Bt through a decomposition into two contributions and gives an improved empirical expectation E[Bt] over neuron pairs during the later stages.For T21 ≤ t ≤ T2, the analysis tracks the aligned set G = ∪k Gk and the associated quantity â.Source: §F.4 · p. 86
  • F.4 bounds E[B_t] by combining Taylor-remainder estimates with stage-dependent parameter bounds, including distinct rates for smooth and ReLU-like activations.For smooth activations, the remainder scales quadratically in ∥v−ˇv∥; for ReLU, LeakyReLU, and Absolute activations, it scales as ∥ˇv∥^1/2∥v−ˇv∥^3/2.Source: §F.4 · pp. 87–88

F.5 Bound on Ct

  • Lemma F.12 bounds C_t for all t ≤ T2 when n > d log3 d and Δ < 1, using empirical-process concentration for a piecewise-polynomial VC-subgraph class with sub-exponential envelope.Source: §F.5 · pp. 89, 91

F.6 Technical lemma

  • Lemma F.14 gives Hermite expansions for G, g, and ∇g, including an explicit J_k formula, and the analysis establishes that the resulting Jacobian J is bounded and Lipschitz.Source: §F.6 · pp. 91, 93
  • F.6 establishes a ReLU Jacobian expansion whose series converges uniformly, with Lipschitz control along nonvanishing interpolating paths.The argument uses ReLU Hermite-coefficient decay and assumes ∥v_t∥≥r0>0; it also bounds higher-order Jacobian terms by C M^k.Source: §F.6 · pp. 96–97

G Technical lemma

  • G derives bounds for gradient terms using sign-flip symmetry, Gaussian moment concentration, and coordinate decompositions, with improved bounds in the small-tail regime.The lemmas also show that unit vectors with u_1^2≥1−ε have controlled even-power alignment with a signed coordinate direction.Source: G Technical lemma · pp. 99–101

Related papers

Loading 2609.10879v1…