Pith. sign in

REVIEW 1 major objections 4 minor 2 cited by

Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning

T0 review · 1 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper shows that, in a Gaussian single-index model with a truncated quadratic link, full-batch gradient descent achieves weak recovery with n≳d samples and strong recovery after O(log d) steps, while one-pass SGD provably requires n≳d

desk verdict Worth refereeing, with a real fix required: Theorem 4.1 ignores the even-activation symmetry, so strong recovery can only hold up to global sign. read the letter →

arxiv 2602.02431 v2 pith:BO35YIK5 submitted 2026-02-02 stat.ML cs.LG

Filip Kovačević , Hong Chang Ji , Denny Wu , Mahdi Soltanolkotabi , Marco Mondelli This is my paper
classification stat.MLcs.LG
keywords single-indexmodelsfull-batchgradientdescentone-passSGDsamplecomplexityseparationtruncatedquadraticactivationphaseretrievalinformationexponent2strongrecovery
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether reusing the same training data, as full-batch gradient descent does, can beat a single pass through fresh data in a nonlinear, non-convex learning problem. Working in a Gaussian single-index model with a quadratic link function, where online SGD is known to need n≳d log d samples, the authors isolate the mechanism behind the log d gap: the unbounded quadratic activation. They prove that truncating the activation so it becomes bounded lets full-batch spherical gradient flow succeed at n≳d samples, and lets full-batch squared-loss GD from small initialization reach exact recovery in O(log d) steps with n≳d samples. If correct, this removes the logarithmic barrier for plain gradient descent and shows that data reuse can yield a real statistical separation from one-pass updates in feature learning.

What carries the argument

The load-bearing object is the truncated quadratic activation σ(z)=min{z²,M}, together with the empirical matrix A(θ)=(2/n)Σ y_i x_i x_iᵀ φ(⟨x_i,θ⟩²) that appears in the gradient. Boundedness of the activation changes the spectral behavior of this matrix: at n≳d, its top eigenvalue separates from the rest and its top eigenvector aligns with the unknown direction, a sharp spectral phase transition that holds uniformly along the optimization trajectory. For the spherical flow, this lets the dynamics converge to the informative principal eigenvector. For squared-loss GD, small initialization makes the early phase behave like a power iteration on the aligned matrix, while the later phase is cont

What would settle it

Run the Section 4 setup at n=10d with truncation M=8 and initialization uniform on the d^{-15}-sphere, recording the terminal distance to θ* and to −θ* over many seeds. If the theorem's literal statement is correct, almost every run satisfies ∥θ_T−θ*∥²→0; if the sign-symmetry gap is real, roughly half of the runs will instead end near −θ*.

Watch

Extended reading notes

Core claim

The central claim is that with a truncated quadratic activation—a bounded, saturated version of z²—full-batch gradient descent achieves the information-theoretically optimal linear sample complexity n≳d, while one-pass SGD on the same activation provably requires n≳d log d. The paper establishes this in two settings: spherical gradient flow on the correlation loss gives weak recovery at n≳d, and Euclidean GD on the squared loss from uniformly random small initialization gives strong recovery, with the squared error contracting geometrically after at most O(log d) gradient steps. The unbounded quadratic activation is shown to be the obstacle: without truncation, full-batch spherical flow beco

Load-bearing premise

The strong-recovery claim rests on the iterate having entered the basin of θ* with the correct sign; the proof's angle and strong-convexity estimates are only for ⟨θ,θ*⟩>0, and since the loss is even, about half of all random initializations would naturally converge to −θ* instead.

Editorial extensions

If this is right

  • For truncated quadratic single-index models, full-batch GD matches the information-theoretic sample complexity n≳d, closing the log d gap that one-pass SGD provably requires for information-exponent-2 activations.
  • Strong recovery is reachable by plain GD from random initialization: with n≳d samples, O(log d) full-batch steps are enough, and thereafter the squared error contracts geometrically.
  • The unbounded quadratic activation is the reason the log d barrier appears in the spherical/correlation setting: with σ(z)=z², full-batch spherical gradient flow is no better than one-pass SGD.
  • A simple modification of the activation—clipping or saturating it—changes the empirical landscape from one with no finite-n/d signal to one with a uniform spectral gap and aligned top eigenvector.
  • These guarantees extend the known benefit of data reuse beyond linear regression to a canonical non-convex feature-learning problem, with explicit iteration complexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The stated strong-recovery theorem appears, on a close reading, to prove convergence to either θ* or −θ*: the angle used in the proof is absolute-valued, and the one-point strong-convexity lemma is shown only for iterates with positive inner product with θ*. Since the loss is invariant under θ→−θ, an editor would state the exact-recovery guarantee as holding up to global sign unless the initializa
  • The same truncation mechanism may generalize to activations with higher information exponent: saturation creates a low-degree signal that a full-batch spectral first phase can exploit, so full-batch GD might remove or shrink sample-complexity gaps beyond the k=2 case studied here.
  • In practice, the result suggests that clipping the output nonlinearity in phase-retrieval or quadratic-neural-network training could sharply reduce the sample size at which GD begins to learn, at the cost of a controllable saturation bias.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies full-batch gradient descent for learning a d-dimensional Gaussian single-index model y=σ(⟨x,θ*⟩) with quadratic and truncated-quadratic activations. For the quadratic activation, it proves that spherical gradient flow on the correlation loss fails weak recovery when n=o(d log d). For a smooth truncation, it proves n=Θ(d) suffices for weak recovery via uniform BBP-type spectral control and stable-manifold arguments. For the hard-truncated quadratic and squared loss, it claims strong recovery with n≳d and T≳log d steps from small random initialization (Theorem 4.1).

Significance. The weak-recovery separation is a meaningful contribution: it gives a concrete setting in which data reuse by full-batch GD overcomes the d log d sample barrier of one-pass SGD for information-exponent-2 activations, matching the information-theoretic linear-in-d rate. The proof machinery—uniform spectral bounds, VC-type uniform concentration, and center-stable manifold arguments—is substantial and largely machine-checkable in structure. However, the strong-recovery claim as stated is false because of the θ*↔−θ* symmetry, making the central advertised result incorrect without a sign-conditioning repair.

major comments (1)
  1. [Theorem 4.1 / Proposition D.26] Theorem 4.1 cannot hold as stated. The activation (4.4) is even, so the squared loss (4.1) and GD iteration (4.2) are invariant under θ↦−θ; both θ* and −θ* are global minimizers. For uniform initialization on the sphere of radius r0, the event ⟨θ0,θ*⟩<0 has probability 1/2, and the corresponding trajectory converges to −θ*, giving ∥θ_t−θ*∥²→4, contradicting (4.5). The proof fails precisely at the sign step: Proposition D.1 and D.15 define ∠ via arccos(|⟨θ,θ*⟩|/(∥θ∥∥θ*∥)), so they certify alignment only up to sign. Proposition D.26's event B in eq. (D.96) requires g1∈[1/8,1/4] and a>0, which holds only when ⟨θ,θ*⟩>0; for θ near −θ* the true angle is π−φ, the event B is empty, and the lower bound (D.96) is not valid. Consequently the one-point strong convexity (D.91) is not established for the negative-overlap basin, and the probability claim 1−2/d² is impossible. A repair is to state conv
minor comments (4)
  1. [Section 3.2, proof sketch, Eq. (3.10)] The displayed inequality '|⟨v1(A⋆), θ⋆⟩| ≤ CM√(d/n)' has the wrong direction: it should be '1−|⟨v1(A⋆), θ⋆⟩| ≤ CM√(d/n)' (or equivalently '|⟨v1(A⋆), θ⋆⟩| ≥ 1−CM√(d/n)') to agree with the preceding sentence and with Theorem B.3.
  2. [Propositions D.1, D.15] The angle φ_t is defined through arccos of the absolute overlap. After the sign repair, the authors should either explicitly state that all angle bounds are up to global sign, or introduce a sign-aware angle in the refinement phase, so that Proposition D.26's positive-overlap requirement is transparent.
  3. [References] Several references are unpublished or listed as 'in preparation' or 'submitted' (Braun et al. 2026, Montanari and Wang 2026, Xie et al. 2026). For an archival journal version, please clarify availability or cite published/preprint versions.
  4. [Appendix D.2, proof of Lemma D.8] The notation for the symmetric-difference event, e.g. '1{Eθ∆Eθ}', is typeset ambiguously with mismatched braces in several places. Please fix for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sample-complexity separation is derived from concentration, spectral, and dynamical-system arguments rather than fit; self-citations are not load-bearing.

full rationale

The main claims are not circular. Theorem 3.1 derives the negative result from the spectrum of A* = (2/n) sum y_i x_i x_i^T, using the rank-one perturbation formula in (A.6) and a lower bound on lambda_1(P), which are random-matrix calculations rather than assumed conclusions. Theorem 3.2 introduces the truncated activation in (3.6), proves spectral concentration of A(theta) in Propositions B.1-B.3, and then uses Lyapunov and stable-manifold arguments in Propositions B.4-B.5; the BBP-phase-transition result is shown, not assumed. Theorem 4.1 is a two-phase trajectory proof: Proposition D.1 bounds the power-method angle reduction at t* = 3 log d / log(1+1.99 eta), Proposition D.14 controls norm growth to O(log d / eta) steps, and Proposition D.26 establishes one-point strong convexity via the uniform Gram-matrix concentration in Proposition D.20 and a population lower bound. The constants alpha and C are not fitted to the claimed conclusion, and the one-pass SGD lower bound is the external Ben Arous et al. (2021) theorem. The self-citations, such as Mondelli-Montanari (2018) and Stoeger-Soltanolkotabi (2021), are used as technique references or optional relaxations, not as the load-bearing proof of the claimed separation; removing them would not collapse the derivation. I therefore find no circular step. Separately, there is a sign-symmetry correctness concern that is not a circularity: the angle in Proposition D.1 is defined with |<theta, theta*>|, while Theorem 4.1 claims signed convergence to theta*, and Proposition D.26's event B in (D.96) assumes positive overlap; for the negative-overlap basin the one-point strong convexity inequality is not established. This is a gap in the theorem as stated, not a prediction-by-fit or self-citation-based circularity.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central claim rests on Gaussian design, an external one-pass SGD lower bound, random matrix spectral results, and the stable-manifold theorem. No physically new entities are introduced. The algorithmic hyperparameters M and r0 are not fitted to data; they are chosen to make the proofs work. The paper's main contribution is the proof itself, not a new postulated mechanism.

free parameters (2)
  • M (truncation threshold) = Large constant; M=8 in experiments
    The truncated activation is defined with a threshold M. The theorems require M large enough, and error bounds scale as e^{-M/2} plus polynomial terms in M/δ. It is an algorithmic hyperparameter, not fitted to data, but the positive results depend on it being sufficiently large.
  • r0 (initialization radius) = d^{-15}
    Theorem 4.1 uses initialization uniformly on a sphere of radius r0=d^{-15}. This is chosen by hand to keep the early phase below the truncation and enable power-iteration analysis. The paper notes it could be relaxed to a lower power of 1/d at the cost of a more involved argument.
assumptions (6)
  • domain assumption Gaussian i.i.d. design and single-index model (1.1)
    The entire analysis assumes x_i ~ N(0,I_d), y_i=σ(<x_i,θ*>), ∥θ*∥=1. All matrix concentration, spectral, and trajectory results are specific to this data-generating model.
  • domain assumption One-pass SGD lower bound for information-exponent-2 activations (Ben Arous et al. 2021, Theorem 1.4)
    The claimed separation relies on this external theorem to assert that one-pass SGD requires n≳d log d for the same truncated activation. The paper does not reprove or verify this bound; it is a benchmark taken from prior literature.
  • standard math Random matrix BBP/spectral characterization (Lu and Li 2020; Mondelli and Montanari 2018)
    The proof of Theorem 3.1 and spectral properties of A* use precise asymptotics for the principal eigenvector and eigenvalues of random matrices of the form Σ y_i x_i x_i^T. These results are imported as external mathematical facts.
  • standard math Center-stable manifold theorem (Panageas and Piliouras 2017; Shub 1987)
    Proposition B.5 uses the center-stable manifold theorem to show that non-principal stationary points of the spherical flow have basins of measure zero. The theorem is invoked as a standard result in dynamical systems.
  • standard math Concentration inequalities and VC dimension bounds
    The uniform spectral control over the sphere relies on sub-Gaussian concentration, Bernstein-type inequalities, Sauer–Shelah, and VC dimension bounds for unions of halfspaces. These are standard tools applied to slab indicators.
  • domain assumption Smooth truncation and C∞ regularity of the flow
    For the spherical flow, the activation is smoothed to be C∞ so that the ODE has a unique global solution and a smooth flow map. This is a technical regularity assumption on the link function, not justified by the original problem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning." pith.science (2026). https://pith.science/paper/BO35YIK5

@misc{pith2026260202431,
  author       = {Pith},
  title        = {Pith review of: Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BO35YIK5}},
  note         = {Machine review of arXiv:2602.02431}
}
abstract

It is folklore that reusing training data more than once can improve the statistical efficiency of gradient-based learning. While this phenomenon has been extensively studied in linear regression, the benefit of multi-pass gradient descent (GD, which reuses all the data) over one-pass stochastic gradient descent (online SGD, which uses each data point only once) is not well-understood in nonlinear and non-convex settings, except for a loss modification mechanism achieved by the first two passes on the data. In this work, we consider learning a $d$-dimensional single-index model with a quadratic activation, for which it is known that one-pass SGD requires $n\gtrsim d\log d$ samples to achieve weak recovery. We first show that this $\log d$ factor in the sample complexity persists for full-batch spherical GD on the correlation loss; however, by simply truncating the activation, full-batch GD exhibits a favorable optimization landscape at $n \simeq d$ samples, thereby outperforming one-pass SGD (with the same activation) in statistical efficiency. We complement this result with a trajectory analysis of full-batch GD on the squared loss from small initialization, showing that $n \gtrsim d$ samples and $T \gtrsim\log d$ gradient steps suffice to achieve strong (exact) recovery.

Figures

Figures reproduced from arXiv: 2602.02431 by the authors.

Figure 1
Figure 1. Overlap achieved by minimizing the empirical correlation loss on the sphere as a function of δ = n/d. We run spherical gradient descent with learning rate η = 0.1 for T = 1000 log2 d steps; experiments are averaged across 128 random seeds. Left: for the unbounded quadratic activation, increasing d yields a larger threshold δ for weak recovery; we include a spline fit (solid lines) to smooth out the fluctuations. Mid… view at source ↗
Figure 2
Figure 2. Overlap and parameter norm vs. number of GD steps. We use the truncated quadratic activation (4.4) with M = 8, run Euclidean gradient descent with learning rate η = 0.1/M2 and initialization scale 1/d2 , and fix δ = n/d = 10; experiments are averaged across 1024 random seeds. Left, Middle: Observe that the time required for non-trivial overlap and norm growth increases with d. Right: number of GD steps required to a… view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Approximate Message Passing with Random Initialization for Phase Retrieval

    math.ST 2026-08 conditional novelty 7.0 of 10

    Randomly initialized Bayes-optimal AMP provably achieves the weak-recovery threshold δ=1/2 and arbitrarily accurate recovery for δ>1.13 in proportional-regime noiseless phase retrieval.

  2. Statistical Inference on Gradient Flows

    math.ST 2026-05 unverdicted novelty 7.0 of 10

    Proves uniform CLT for gradient flows in ERM and constructs an algorithm-aware, inversion-free covariance estimator for asymptotically valid time-uniform confidence intervals.

Reference graph

Works this paper leans on

4 extracted references · cited by 2 Pith papers

  1. [1]

    4 cosφ− √ 3 s 2 R√ M e− M 2R2 + 2e− M 2 !# · tanφ 1 + tanφ ∥θ∥ ≤

    Thus, we can assumen≥2. Let An−1 := 2 n n−1X i=1 yixix⊤ i ,so thatA ⋆ =A n−1 + 2 n ynxnx⊤ n . We writeu n :=x n p 2yn/n, soA ⋆ =A n−1 +u nu⊤ n . LetA∈R d×d be symmetric and letE:= ker(A−λ 1(A)I) be its top eigenspace. Ifu̸⊥E, we claim that the largest eigenvalue ofB:=A+uu ⊤ is simple. 18 Proof of the claim.Choose a unit vectorv∈Ewithu ⊤v̸= 0. Then v⊤Bv=v ...

    1993

  2. [2]

    67 Furthermore, we have ⟨gS, a⟩=rcosθ,⟨g S, b⟩=rcos(θ−α), which implies that D(a, b) ={cosθ·cos(θ−α)<0}

    In particular, E[r2] = 2,E[r 4] = 8. 67 Furthermore, we have ⟨gS, a⟩=rcosθ,⟨g S, b⟩=rcos(θ−α), which implies that D(a, b) ={cosθ·cos(θ−α)<0}. Note thatD(a, b) depends onθand not onr. On the circle this set consists of two disjoint angular intervals, each of lengthα, hence P(g∈D(a, b)) = 2α 2π = α π .(D.90) Using thatYis independent of (X,1{D(a, b)}) andE[...

  3. [4]

    Therefore, we have E[(a−b) 21{B}] =E[(⟨x, u⟩)21{B}]≥E[(u 1g1 +u 2g2)21{B}]

    is independent of (g 1, g2) and hence independent ofB. Therefore, we have E[(a−b) 21{B}] =E[(⟨x, u⟩)21{B}]≥E[(u 1g1 +u 2g2)21{B}]. SinceBis symmetric ing 2,E[g 1g21{B}] = 0, and hence E[(u1g1 +u 2g2)21{B}] =u 2 1 E[g2 11{B}] +u 2 2 E[g2 21{B}]. We now lower bound the two expectations. Because the standard normal densityfis decreasing on [0,∞), P(g1 ∈[1/8,...

  4. [1262]

    Alex Damian, Jason D Lee, and Joan Bruna

    PMLR, 2024. Alex Damian, Jason D Lee, and Joan Bruna. The generative leap: Tight sample complexity for efficiently learning gaussian multi-index models. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, on...

    arXiv 2024

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.