SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics

1 Introduction

• Vanilla staircases and degree-four monomials have similar low-dimensional statistical complexity but different CSQ dimensions, Θ(d) versus Θ(d^4), motivating hierarchy-sensitive SGD complexity.The staircase is leap-1, whereas the monomial is leap-4; aligning with k coordinates simultaneously requires ˜O(d^(k−1)) steps, matching CSQ lower bounds up to logarithmic factors.Source: §1 · p. 4

1.1 The leap complexity

• Leap complexity orders nonzero basis elements so that each added monomial introduces at most k new support coordinates, generalizing merged-staircase functions to leap-k targets.For Gaussian data, newly added coordinates are counted with multiplicity; for Boolean data, the measure reduces to the cardinality of the support difference.Source: §1.1 · p. 5

1 Introduction

• For low-latent-dimensional targets under isotropic Gaussian or Boolean inputs, the conjectured risk-learning time is ˜Ω(d^(Leap(h∗)−1∨1))poly(1/ε), with total complexity ˜Ω(d^(Leap(h∗)∨2))poly(1/ε).The target has the form f∗(x)=h∗(Mx) with P=O_d(1), so ambient dimension is large while dependence is restricted to finitely many unknown latent coordinates.Source: §1 · p. 3, §1.2 · p. 6

1.2 Summary of our contributions

• SGD sequentially learns target supports through saddle-to-saddle phases, spending ˜Θ(d^max(L−1,1)) steps to identify each new coordinate set of size at most the leap L, yielding ˜Θ(d^max(Leap(h∗),2)) total time.The formal result uses smooth two-layer networks, layer-wise projected SGD, Gaussian isotropic data, and a representative function subclass; the general conjecture concerns fully connected networks with poly(d) edges and rotationally invariant initialization.Source: §1.2 · pp. 6–7

1.3 Related works

• Compared with prior single-index or one-step analyses [BBSS22] [BEG+22], this work controls multiple sequential learning phases and the full neural-network SGD trajectory.The leap controls the entire trajectory rather than only initialization correlations, while the proof avoids infinite-width and continuous-time approximations.Source: §1.2 · p. 6, §1.3 · p. 8

Linear-method lower bounds

• Any linear method requires c_h* d^D samples to learn a degree-D polynomial composed with an unknown permutation or rotation, extending the Boolean result to Gaussian inputs.The error must remain below a positive ε_h* threshold.Source: §2 · p. 9

CSQ lower bounds

• CSQ learning requires at least c_h* d^Leap(h*) queries in the Boolean case and c_h* d^(Leap(h*)/2) in the Gaussian case.These bounds apply to learning below ε_h* error in the setting of Proposition 1.Source: §2 · p. 9
• The Boolean CSQ lower bound matches the conjectured total-time scaling, whereas the Gaussian result proves only half the exponent and conjectures the Boolean scaling.The Gaussian conjecture is deferred to Appendix F.Source: §2 · p. 9

Limitations and SGD correspondence

• The lower bounds concern CSQ or noisy population-GD models rather than online-SGD, and the correspondence may fail beyond finite P or when fitting large-support functions is costly.For large P, SGD may need to express a high-degree monomial after identifying the support, while CSQ can require zero additional queries when the relevant function is known.Source: §2 · p. 9

3.1 Algorithm

• The algorithm trains first-layer weights with projected online-SGD, then second-layer weights with standard SGD and ridge regularization, while freezing biases.Projection controls first-layer coordinate growth caused by layerwise training, which leaves the target incompletely fitted during the first phase.Source: §3.1 · pp. 10–11

3.2 Learning a single monomial

• For a single monomial, first-layer weights align with its support only near the end of training, after T1 = C0d^(D−1) log(d)^C0 steps.The result holds with probability at least 1 − Md^−C∗ under the stated activation, projection, initialization, and learning-rate conditions; early stopping prevents fitting.Source: §3.2 · pp. 11–13

3.3 Learning multiple monomials

• For nested multiple monomials, support coordinates align sequentially, requiring between d^(D^2−1)C log(d)^C steps per stage under the theorem’s largest-leap parameter D.The analysis obtains d^(Dl−1) scaling for smaller leaps by varying the step size, while constant-step-size practice appears to achieve this scaling empirically.Source: §3.3 · p. 13
• For nested sums of monomials, SGD achieves risk R(Θ_T1+T2) ≤ ε with high probability after T1 = ˜Θ(d^Leap(h∗)−1) and T2 = poly(1/ϵ).This informal corollary applies to a poly(1/ϵ)-width two-layer network with a suitable activation function and hyperparameters.Source: §3.3 · p. 14

Contributions

• The paper conjectures that neural-network learning complexity is governed by leap complexity, generalizing the Leap(h∗) = 1 result of.For classical linear methods, complexity instead depends on target-function degree.Source: §4 · p. 14
• Theoretical evidence includes d^Ω(Leap(h∗)) CSQ lower bounds and d^O(Leap(h∗)) modified-SGD samples and runtime for learning leap-staircase functions and fitting multilinear leap-staircase functions.The SGD guarantee applies to relevant-index learning for functions of form (11) and function fitting for functions of form (12).Source: §4 · p. 14

Future work

• Future work includes removing layerwise training and projection from SGD, analyzing general functions beyond form (11), and extending leap complexity beyond isotropic input distributions.Source: §4 · p. 14

A Additional numerical simulations

• Saddle-to-saddle dynamics repeatedly appear as SGD sequentially aligns network weights with hierarchical target supports across Boolean, Gaussian, ResNet, and non-polynomial settings.For the Gaussian leap-3 example, SGD first aligns with x1,x2, then slowly picks up x3,x4,x5 before fitting the remaining function.Source: A Additional numerical simulations · p. 20, Figure 3 · p. 21, Figure 5 · p. 23
• As ambient dimension increases, escaping saddles increasingly dominates SGD trajectories, and higher-leap tasks can plateau at saddles while leap-1 tasks avoid them.For d=50,100,200,400, the leap-3 Boolean task exhibits increasingly salient saddle-to-saddle evolution; with Gaussian data at d=500, He3(z1) stalls whereas He1(z1)+He3(z1) does not.Source: Figure 3 · p. 21, Figure 4 · p. 22
• For leap-1 targets, weights align quickly without saddles, but deeper networks fit different monomials faster than two-layer networks, a depth effect distinct from depth separation [SL22].The simulations report alignment in fewer than 5000 steps for a Boolean leap-1 target and improved fitting with a deeper ReLU ResNet on Gaussian data.Source: Figure 6 · p. 24, Figure 7 · p. 25

B.1 Additional references

• Sparse Fourier methods can learn classes with concentrated known Fourier support in polynomial time, whereas SGD-trained neural networks do not necessarily treat degree-k and degree-(d−k) monomials equivalently.The cited framework gives sample complexity O((1/ϵ)|S| log(|S|/δ)) when the relevant basis set S is known, covering juntas and related classes [Man94, O’D14].Source: §B.1 · p. 26
• Prior lower bounds relate weak initial alignment to large leap complexity and require Ω(d^Lτ^2) noisy-GD steps for leap-L functions, unlike the paper’s online-SGD setting [AB22].The appendix contrasts these results with generic SGD on regular neural networks and notes the different computational model.Source: §B.1 · p. 26
• Generic SGD estimates low-dimensional multi-index supports without prior target information and can nearly match the best CSQ complexity, although specialized methods can do better.The appendix situates this result alongside phase retrieval, intersections of halfspaces, and subspace juntas, where support estimation breaks the curse of dimensionality [VX11].Source: §B.1 · p. 26

B.2 Discussion on the definition of the leap complexity

• Degenerate leap-1 functions can require more than Θ(d) SGD steps because permutation symmetry prevents support-coordinate separation, motivating isotropic leap as the basis-aware complexity measure.For h*(z)=z1+z2+z1z2, a rotation yields isoLeap(h*)=2, ruling out Θ(d) mean-field SGD learning; the canonical-basis treatment is justified almost surely only under the stated smoothed-complexity assumption [ABM22].Source: §B.2 · p. 27

B.3 Intuition for the proof of Theorem 1

• Drift dominates martingale fluctuations, yielding the theorem’s scaling for support alignment, while spherical projection contributes only negligibly to the dynamics.The analysis chooses step-size and initialization scaling to control martingale noise, and introduces projection to prevent statistically amplified coordinates from continuing to grow.Source: §B.3 · pp. 28–30

B.4 Going beyond sparsity

• Beyond coordinate sparsity, leap may depend on basis choice, initialization, architecture, and the potentially nontrivial cost of fitting functions after their support is learned.Full parity illustrates that Gaussian initialization may not permit polynomial-time learning even when special Rademacher initialization and ReLU can suffice; fitting an arbitrary function on a detected support can add complexity.Source: §B.4 · pp. 30–31

B.5 Lower-bounds: beyond noisy GD

• The SGD result matches CSQ lower-bound scaling despite model differences, raising whether regular network architectures impose constraints comparable to CSQ limitations.The paper proves population-gradient drift dominates over the considered horizon, whereas CSQ adds noise to query outputs; irregular networks can surpass CSQ/SQ barriers, leaving the regularity question open.Source: §B.5 · p. 31

C Proof of Theorem 1: alignment with a single monomial

• The formal proof tracks all P support coordinates of each neuron while controlling the remaining d−P coordinates through a drift–martingale decomposition.Unlike the single-index analysis in [TV19], the proof must maintain trajectory-wide control of the nonsupport parameters.Source: C Proof of Theorem 1: alignment with a… · p. 32

C.1 Preliminaries

• The preliminaries reduce first-layer training to independent correlation dynamics under small second-layer initialization, bounded biases, and projection constraints enforced through stopping times.A union bound extends the per-neuron event to the full network, while the stopping-time analysis shows the relevant stopping times exceed T1 with high probability.Source: §C.1 · pp. 32–34
• The preliminary estimates show that coordinates outside the active support remain small after the relevant stopping time.For i > P and t ≥ τ_r + 1, the cited bound gives |a_i| ≤ |a_0|κ̃ when S_t ∩ [P] = ∅.Source: §C.1 · p. 35

C.2 Bounding the different contributions to the dynamics

• The projection analysis bounds norm changes when the support is unchanged or changes, using η_1 ≤ 1/d and sufficiently large d.When the support is unchanged, the squared update contribution is bounded by 1/4; when it changes, at most P coordinates are removed and the new norm is bounded by 4Pr^2 + ||S_{t}(w_{t+1})||_2^2.Source: §C.2 · p. 36
• The dynamics decompose into a population-gradient drift and a martingale difference between stochastic and population gradients.Inductive estimates control the projected weight and martingale components before the stopping times τ_0, τ_+, and τ_−.Source: §C.2 · p. 37
• Under the stated bounds on η_1 and T, the trajectory remains close to its controlled regime, with projected norms between 1 − Cr^2 − C/log(d) and 1 + Cr^2 + C/log(d).The trajectory bounds apply for t < T ∧ τ_+ ∧ τ_− ∧ τ_0 and separately track coordinates i ≥ P + 1 or i ∈ [P] before τ_r.Source: §C.2 · pp. 37–38
• The martingale contribution is bounded uniformly over time by truncation, maximal inequalities, and a union bound under the lemma’s assumptions.Lemma 4 fixes T ≤ d^D and chooses the step size so that the resulting maximal martingale control holds with constants depending only on D, K, and C*.Source: §C.2 · pp. 38–39

C.3 Proof of Theorem 1

• With probability at least 1 − d^-C*, the dynamics satisfy the required bounds up to the stopping time τ, under conditions on T and η1.The proof then chooses T and η1 so T < τ and Theorem 1(a), (b), and (c) follow.Source: §C.3 · p. 39
• The proof controls active coordinates by bounding their growth and shows the relevant stopping times occur within explicit scales involving log(d), η1, a0, and μD(σ).In particular, the bounds include τr ∧ τ ≤ C log(d)/(η1 a0 μD(σ)), τΔ − τr ≤ C/(η1 a0 μD(σ)), and τΔ ∧ τ ≤ C d^(D/2−1)/(η1 a0 μD(σ)).Source: §C.3 · pp. 40–41
• For coordinates outside the target support, the proof bounds their dynamics and chooses r sufficiently small so the positive and negative stopping times exceed the reference stopping time.This control is used to establish the theorem’s conclusions for the non-support coordinates.Source: §C.3 · pp. 41–42
• Choosing T1 := T and η1 to satisfy the stated conditions yields τ0 > τ+ ∧ τ− ∧ T with probability at least 1 − C d^-C*, proving Theorem 1(b) and (c).Theorem 1(a) is completed separately for all neurons, including those whose initialization does not satisfy the main condition, by controlling their drift and coordinates.Source: §C.3 · pp. 42–43

C.4 Technical lemmas

• The technical lemmas provide conditional tail and moment bounds for functions of Gaussians when the weight norm is bounded, using hypercontractivity, bounded activations, and subgaussian noise.The constants depend only on the polynomial degree D and noise or activation bounds K.Source: §C.4 · p. 43
• Lemma 6 bounds sequences obeying geometric evolution inequalities from above and below, serving as a discrete analogue of the Bihari–LaSalle inequality.The bounds cover both k = 2, yielding exponential growth, and k > 2, yielding the corresponding nonlinear estimates.Source: §C.4 · p. 44

• The proof splits the dynamics into L sequential phases, each corresponding to alignment with one of the L monomials.The argument follows the same general strategy as the single-monomial case.Source: D Proof of Theorem 2: sequential… · p. 46
• The analysis uses generic constants C, c > 0 depending only on D and K, with values allowed to change from line to line.The remaining constants satisfy P_l, D_j, D_l ≤ D.Source: D Proof of Theorem 2: sequential… · p. 46

D.1 Proof of Theorem 2: alignment to the full support

• The proof tracks newly introduced coordinate blocks [P_l] \ [P_{l−1}] across successive phases using stopping times that separate alignment, growth, and sign-control events.The analysis reduces the dynamics to one neuron and introduces phase-dependent stopping times before applying population-gradient bounds.Source: §D.1 · pp. 46–47
• Theorem 2 holds with probability at least 1 − d^−C* under the stated conditions on T and η1, which control the dynamics up to the stopping time τ.The proof assumes conditions (32), (34), and (37), with martingale terms satisfying bounds (38).Source: §D.1 · p. 47
• Each new coordinate block remains controlled through the preceding phases, yielding τ_i^∆ > τ^{r,l′} + 1 and, by induction, alignment across all relevant coordinates.The intermediate bounds first show τ^{+,l} > τ^{r,l′} + 1, then transfer this to the coordinate-specific stopping times.Source: §D.1 · pp. 47–48
• After alignment, the proof bounds the growth of newly activated coordinates while controlling previously activated coordinates, using the condition D_l > 2 and Lemma 6.These estimates establish lower bounds for new coordinates and corresponding bounds for coordinates in earlier blocks.Source: §D.1 · p. 48
• The phase-wise estimates also provide corresponding bounds on τ^{∆,l}, completing the control needed for the final theorem statement.The stopping-time bounds are obtained by the same argument used for the earlier phase analysis.Source: §D.1 · p. 48
• Theorem 2(a) follows from the growth estimates with η1 and T1 := T satisfying the prescribed conditions, while Theorem 2(b) follows by the corresponding final-phase argument.Both conclusions require the growth conditions established in Step 2 and the assumptions referenced in the proof.Source: §D.1 · p. 48

D.2.1 Adaptive step-size

• With increasing leaps, constant-step-size SGD exhibits saddle-to-saddle plateaus, requiring O(d^D_l−1) steps to escape each saddle.For early phases, the required steps d^((D_l+D)/2−1) are much smaller than d^(D−1), allowing larger step sizes while keeping martingale contributions negligible.Source: §D.2.1 · pp. 48–49
• The tight constant-step-size scaling for every plateau remains unproved because it would require jointly analyzing both network layers, beyond the current techniques.The adaptive theorem instead supplies the per-phase scaling under a learning-rate schedule.Source: §D.2.1 · p. 49
• eΘ(d^D_l−1) steps suffice to align each successive monomial under a phase-specific learning-rate schedule.The schedule uses T_l proportional to d^D_l−1 log(d)^C0 and η_l proportional to 1/(κd^(D_l/2)log(d)^C1), under the theorem’s stated assumptions.Source: §D.2.1 · p. 49
• The adaptive theorem aligns all neurons sequentially, recovering exactly the support [P_l] and no additional coordinates at the end of each phase.Consequently, the network cannot fit the remaining L−l monomials through second-layer weights at that time.Source: §D.2.1 · p. 49
• The adaptive schedule preserves the phase separation by keeping martingale terms and drift from later monomials negligible throughout each phase.T_l and η_l are selected to maintain these controls during the complete training dynamics.Source: §D.2.1 · p. 49

D.2.2 Non-nested monomials

• Leap complexity does not require nested or compositional monomials: the construction allows new coordinates in successive monomials with D_1<⋯<D_L and D=max_l D_l.Here D is identified with the leap complexity of h*; compositionality is presented as a proof convenience rather than a necessary structure.Source: §D.2.2 · p. 50
• For non-compositional targets, the proof retains the martingale and dynamical bounds but must use modified population-gradient formulas.The authors outline this modification for Theorem 2 and defer proving the full conjecture for general leap functions to future work.Source: §D.2.2 · p. 50

E.1 Proof of Corollary 1: fitting one monomial

• The proof treats h*(z)=z_1⋯z_P first, proving the upper and converse bounds separately before extending the argument to h*(z)=He_D(z_1).The product case identifies P=D and assumes zero biases in the second-layer-fitting analysis.Source: §E.1 · p. 51, §E.1.1 · p. 51

E.1.1 Second-layer fitting

• Training the first layer aligns relevant coordinates with signed increments while leaving irrelevant coordinates close to initialization, enabling construction of features indexed by sign vectors.The feature construction combines trained neurons to approximate E_G[σ(Δ⟨δ,z⟩+G)] for each δ∈{±1}^P.Source: §E.1.1 · p. 51
• A certificate combines these features to represent the product monomial, and second-layer SGD then converges through ridge-regularized least-squares regression with the first layer fixed.The certificate retains the trained first-layer weights and uses suitable second-layer coefficients; the resulting analysis proves the low-loss fitting direction.Source: §E.1.1 · pp. 52–54

E.1.2 Converse if early stopping

• With early stopping, the first-layer features remain close enough to their initial configuration that the network cannot obtain the target correlation required by Corollary 1.The converse follows the proof strategy of [GMMM21, Theorem 1] and uses concentration and rotational invariance to control feature correlations.Source: §E.1.2 · pp. 54–56
• The early-stopping converse is established by bounding the feature Gram structure and showing that individual neuron features have insufficient correlation with the product target.The argument uses Taylor expansion, concentration, and integration by parts under the high-probability initialization event.Source: §E.1.2 · pp. 55–56

E.1.3 Proof for a single-index Hermite monomial

• For h*(z)=He_D(z_1), randomized biases over [−Δ,Δ] provide enough nearby neurons to construct approximate good features for every required bias interval.The neuron count is chosen sufficiently large but remains independent of d, while Δ is selected as in Theorem 1.Source: §E.1.3 · p. 56
• A signed measure over biases cancels unwanted Taylor components and yields a certificate for He_D(z_1), after which the same least-squares analysis proves low test error.The construction uses linear independence of the auxiliary polynomials and a signed measure with controlled second moment.Source: §E.1.3 · pp. 56–57
• The Hermite early-stopping lower bound follows by applying the same converse argument used for the product monomial.The section explicitly reduces the lower-bound proof to the argument in Section E.1.2.Source: §E.1.3 · p. 57

Formal guarantee

• The corollary provides SGD parameters under which the monomial-sum target is learned with probability at least 1 − d^−C∗−ε for sufficiently large d.The width, initialization, regularization, step-size, and runtime scales are specified as functions of d, ε, D, K, and C∗.Source: §E.2 · p. 57

Activation construction

• The proof requires a sufficiently diverse activation whose bias-shifted Hermite coefficients realize all required sign patterns across monomial degrees.The constructed activation depends on P but not h∗; simulations indicate standard ReLUs also learn these functions.Source: §E.2 · pp. 57–58
• Choosing a sufficiently large truncation parameter makes the coefficient system invertible because diagonal terms remain bounded below while off-diagonal terms become small.This guarantees coefficients γs,k satisfying the required Hermite-sign conditions.Source: §E.2 · p. 58

Certificate

• Biases compensate for the unavailable individual sign directions, allowing trained neurons to approximate shifted Gaussian expectations and estimate each monomial feature to O(∆) error.The certificate uses first-layer weights near ∆δ, biases near b(s), and bias measures with controlled second moments.Source: §E.2 · p. 59
• A linear combination of these estimated monomial features approximates h∗, and a bounded-norm certificate then yields the generalization guarantee.The target is h∗(z) = z1 · · · zP1 + z1 · · · zP2 + · · · + z1 · · · zPL.Source: §E.2 · p. 59

E.3 Technical result: last iterate convergence of SGD on linear models

• The analysis differs from [JKK+17] and by treating one-sample online gradient descent with a small learning rate rather than online minibatches.This choice is made to match the theorem’s SGD setting.Source: §E.3 · p. 59
• Compared with, the result concerns final-iterate bounds with exponentially high probability rather than bounds stated only in expectation.The comparison is specifically about the probability mode of the final-risk guarantee.Source: §E.3 · p. 59
• The analysis studies online-SGD for a linear predictor on embedded data with a ridge-regularized square loss.The dynamics use one sample per iteration and a small learning rate.Source: §E.3 · p. 59
• The main convergence lemma assumes bounded features and responses, positive ridge regularization, and a bounded second moment of the labels.Under these conditions, the proof controls the last iterate’s excess loss relative to the unique regularized optimum.Source: §E.3 · pp. 60–61
• The proof decomposes the iterate error into bias and variance terms, then bounds the variance through an auxiliary process with controlled increments.The auxiliary process dominates the variance norm and enables concentration of the stochastic recursion.Source: §E.3 · pp. 60–61
• A martingale high-probability bound is applied to the variance process to obtain the last-iterate control for every δ in (0,1/2).The argument uses conditional mean-zero noise, a stopping-time truncation, and bounded differences.Source: §E.3 · pp. 61–62

Overview

• Linear methods must use at least Ω(d^D) samples and feature width dim(H) ≥ d^D to learn degree-D functions with unknown support on isotropic data.The section’s general takeaway is stated for functions with small support when the support is not known.Source: §F.1 · p. 63

Hypercube

• On the Boolean hypercube, Proposition 3 establishes this limitation for functions obtained by permuting the coordinates of a degree-D target, extending the result of.The class consists of targets depending on an unknown subset of coordinates, and the proposition applies to any linear method, including with possibly noisy samples.Source: §F.1 · p. 63

Gaussian data

• For Gaussian isotropic data, Proposition 4 gives a new degree-dependent lower bound for linear methods learning targets supported on an unknown subspace.The bound applies to a uniformly random semi-orthogonal subspace embedding M and possibly noisy samples.Source: §F.1 · pp. 63–64
• The Gaussian proof represents a degree-D monomial as a linear combination of at most 2^D rotated copies of the target, with coefficients controlled by the target function.This construction uses semiorthogonal matrices and coefficients bounded by a constant depending only on h∗.Source: §F.1 · p. 64
• The resulting lower bound follows because a linear predictor lies in the span of the observed feature vectors, leaving an orthogonal-projection error against randomly rotated coordinate products.The argument invokes the hypercube lower bound from after random rotation and permutation.Source: §F.1 · pp. 64–65

CSQ setup

• A CSQ algorithm queries ϕ(x)∈[-1,1] and receives an approximation to E_x[ϕ(x)f*(x)], then outputs an estimate of f*; noisy population gradient descent is one example [BIK95, BF02, Rey20, AB22].With independent zero-mean label noise, the response differs from the correlation by at most the query tolerance τ.Source: §F.2 · p. 65

Hypercube lower bound

• Unlike [AB22], which analyzes noisy population gradient descent, the hypercube argument applies to general CSQ algorithms, although [AB22] gives tighter exponent constants.The proof uses the leap definition to identify a coordinate subset after which every nonzero Fourier component has sufficiently large residual support, making the first queries uninformative under random permutations.Source: §F.2 · pp. 65–66
• For hypercube targets formed by permuting a leap-structured h*, Proposition 5 bounds the success probability of any n-query CSQ learner in terms of n, d, Leap(h*), and tolerance τ.The result concerns a random choice of the coordinate permutation and applies even when the learner is given the relevant initial coordinates.Source: §F.2 · p. 65

Gaussian lower bound

• For Gaussian data, Proposition 6 gives an analogous CSQ limitation for finite-degree polynomial targets h* applied to a randomly chosen coordinate subspace, governed by isotropic leap.The result is stated for arbitrary n-query CSQ algorithms with tolerance ±τ and holds with high probability over the random subspace.Source: §F.2 · p. 66
• The Gaussian proof reduces to a basis maximizing the leap and controls correlations under Haar-random rotations using Hermite expansions and combinatorial bounds on compatible multi-indices.Knowing the first r rows of the embedding can only help the learner; the remaining random rows are handled by the same indistinguishability strategy as in the hypercube case.Source: §F.2 · pp. 66–67