{"id":"f3a3a151-dc7b-4710-9290-f44ddd925d5a","arxiv_id":"2508.21022","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For linear least squares, SNGD and SPRING are proved equivalent to accelerated regularized Kaczmarz methods, yielding the first fast rates and first SPRING guarantee; the general quadratic analysis holds under strong idealized assumptions.","lead":"This paper proves convergence rates for subsampled natural gradient descent (SNGD) and its momentum variant SPRING on quadratic model problems, by showing they are equivalent to randomized Kaczmarz solvers. A generalist may care because these rates are the first for SPRING and help explain why curvature-aware subsampling works in physics-informed and neural wavefunction training.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"LLQ rate rests on an eigenbasis alignment the paper admits is unrealistic, and Theorem 4's proof silently uses λ=0.","rationale":"The LLS half is solid: the mapping to regularized Kaczmarz is a direct algebra identity and the rates follow from known Kaczmarz bounds. I found no error there. The paper's broader reach depends on the LLQ theorem. The reader's weakest assumption already identifies the eigenbasis alignment; I agree and add that the proof silently sets λ=0. Since the paper itself admits the alignment will not hold in practice and Proposition 3 provides a divergence mechanism, the LLQ contribution is conditional, not established. This does not undermine the LLS equivalence, so conditional acceptance remains the right verdict.","tokens_in":20792,"tokens_out":24201,"duration_ms":231120,"concrete_test":"Re-derive Theorem 4 keeping λ>0: replace J^+ in eq. (38) with J^+(λ)=(J^TJ+λI)^-1J^T and attempt to obtain a Q^-1-norm contraction of the form (20). If the contraction fails for λ>0—e.g. because the cross terms no longer collapse to -2ηJ^THJ—Theorem 4 must be restated as a λ=0 result, and the 'first explanation outside LLS' does not cover the regularized algorithm used in practice.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The second headline contribution—'first explanation for SNGD outside least-squares'—is Theorem 4. It requires, in addition to Assumption 2, that the expected regularized projector P be simultaneously diagonalizable with J^TJ (Section 4.2). The paper itself says this 'is not expected to hold in practice.' When it fails, Proposition 3 shows the expected iteration matrix M=PJ^+HJ can have an eigenvalue with negative real part, so SNGD diverges for every step size at small λ. The proof of Theorem 4 also has an unstated λ=0 restriction: P(S) is the λ-regularized block projector, but in Appendix B eqs. (38)-(39) J^+(λ) is replaced by the unregularized (J^TJ)^-1J^T, and Q is defined as P(S)(J^TJ)^-1. For λ>0, θ_{t+1}-θ* = (I-ηP(S)J^+(λ)HJ)(θ-θ*) does not equal (I-ηP(S)(J^TJ)^-1J^THJ)(θ-θ*), so the contraction in the Q^-1 norm (20) is not algebraically justified. The LLQ rate is therefore supported only under an alignment assumption the authors disavow and at λ=0, the regime Proposition 3 identifies as fragile.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes subsampled natural gradient descent (SNGD) and its momentum variant SPRING on two quadratic model problems: linear least-squares (LLS) and linear least-quadratics (LLQ). For consistent LLS, it proves that SNGD with unit step size is exactly the regularized Kaczmarz method of Goldshlager et al. (2025) and that SPRING is equivalent to the accelerated regularized Kaczmarz (ARK) method of Dereziński et al. (2025), leading to the stated geometric convergence rates. For LLQ, under a strong consistency condition plus an added assumption that the expected regularized projector commutes with JᵀJ, the paper proves a convergence rate for SNGD, and it shows that without the commutation assumption SNGD can diverge for all step sizes when the regularization is small. SPRING for LLQ is left as a conjecture with supporting numerics. The paper frames these results as the first convergence guarantees for SNGD and SPRING and the first rigorous explanation of SPRING's acceleration.","tokens_in":21106,"tokens_out":16281,"duration_ms":155693,"significance":"If the LLS results are correct, they provide a clean and useful bridge between subsampled natural gradient methods and randomized linear algebra: the equivalence proofs are explicit, the rates follow from established Kaczmarz theory, and the single-batch coupling is handled naturally rather than by decoupling gradient and preconditioner samples. The SPRING-ARK equivalence is a genuine new structural insight and gives the first convergence statement for SPRING. The LLQ analysis is more conditional: the main theorem requires an eigenbasis alignment assumption that the authors themselves state is not expected to hold in practice, and Proposition 3 shows that without such an assumption divergence is possible. Nevertheless, the paper is transparent about this limitation and provides concrete special cases (DPP sampling and Gaussian limits) where the alignment holds. Overall, the LLS contribution is solid, while the LLQ contribution is a plausible starting point rather than a general explanation.","major_comments":[{"comment":"The claimed 'first explanation for SNGD outside least-squares' rests on the assumption that the expected regularized projector P shares an eigenbasis with JᵀJ. The paper explicitly says this assumption 'is not expected to hold in practice,' and Proposition 3 shows that when it fails, SNGD can diverge for every step size at small λ. Thus Theorem 4 establishes convergence only under an idealized alignment condition (or in the DPP/Gaussian special cases of Proposition 9), not for the motivating NNW/PINN settings. The contribution should be reframed accordingly, or the authors should provide evidence or a relaxed condition under which approximate alignment holds in the motivating applications.","section":"Section 4.2, Theorem 4"},{"comment":"The SPRING rate is stated as holding 'for appropriate choices of η and μ,' but the paper never specifies admissible values or ranges for these hyperparameters, nor the corresponding constraints on the ARK step-size transformation \\\tilde η = 1-(1-η)/μ given in Appendix A. Since one of the main contributions is the first convergence guarantee for SPRING, the guarantee is not actionable without explicit hyperparameter conditions. Please include the concrete ARK assumptions (e.g., from Dereziński et al. 2025) under which eq. (16) holds, or state a fully self-contained theorem.","section":"Theorem 1, eq. (16)"}],"minor_comments":[{"comment":"The symbol J⁺ is used for both the regularized pseudoinverse J⁺(λ) and the unregularized pseudoinverse; for example, eq. (18) introduces J⁺ without a definition. Please define J⁺ = (JᵀJ)⁻¹Jᵀ explicitly.","section":"Notation, Sections 2-4"},{"comment":"The proof uses Q for both the deterministic matrix in Theorem 4 and the random matrix P(S)(JᵀJ)⁻¹. This makes equations (38)-(40) hard to read. Use notation such as \\bar Q for the deterministic expectation and Q_S for the random quantity. Also note: the apparent replacement of a regularized pseudoinverse by an unregularized one in eqs. (38)-(39) is not an error, because J⁺ there is the full pseudoinverse from eq. (18) and the regularization enters only through P(S); clarifying this would prevent confusion.","section":"Appendix B, proof of Theorem 4"},{"comment":"The asymptotic statements contain typographical issues: 'α = Ω(kβκ−2_dem(J)' is missing a closing parenthesis, and 'γ = Ω(κ2(J))' should presumably be 'γ = Ω(κ⁻²(J))' to be consistent with the rate in eq. (21). Please correct.","section":"Corollary 5"},{"comment":"After deriving \\tilde η = 1-(1-η)/μ, the paper does not discuss the admissible sign or magnitude of \\tilde η. Since ARK requires certain step-size constraints, state the conditions on η and μ that make \\tilde η admissible.","section":"Appendix A, ARK transformation"}],"recommendation":"major_revision","confidential_remarks":"The LLS equivalences and rates are the strongest part of the paper and are, in my reading, sound. The main risk is overclaiming the LLQ contribution: Theorem 4 depends on an alignment assumption that the authors disavow for practice, and the SPRING guarantee in Theorem 1 lacks explicit hyperparameter conditions. Both issues are fixable within the scope of the manuscript. I also checked the stress-test concern about a hidden λ=0 substitution in Theorem 4's proof; it does not land, because J⁺ in eq. (38) is the unregularized full pseudoinverse and the regularization is carried by P(S). The paper would be strengthened by an explicit discussion of this point."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The least-squares half is clean and worth taking seriously: the proof that SNGD is exactly regularized Kaczmarz and SPRING is exactly ARK under a change of variables is explicit, checkable, and yields the first convergence guarantee for SPRING and the first proof that momentum accelerates SNGD. The LLQ half is genuinely new but sits on strong assumptions the paper itself disavows for practice. Also, the stress-test's specific allegation—that the proof of Theorem 4 silently sets λ=0—does not survive contact with the paper.\n\nThe claimed λ-slip in Appendix B is wrong. In eq. (18) the derivation correctly factors the sampled block-regularized inverse into P(S) times the unregularized full pseudoinverse J^+; the regularization parameter enters only through P(S). Equation (38) writes I − ηP(S)J^+HJ with the unregularized J^+, which is exactly what the algebra gives. The contraction in the Q^{-1} norm is justified as far as λ is concerned.\n\nWhat is new and good. The SNGD-to-regularized-Kaczmarz equivalence is a one-liner but it is the right lens, and the SPRING-to-ARK equivalence with the iterate transformation ϕ̃_t = −µϕ_t, θ̃_t = θ_t − µϕ_t is a real insight that explains the otherwise ad hoc momentum structure. For LLQ, rewriting the update as P(S) times the deterministic natural gradient under range(HJ) ⊆ range(J) is a clean conceptual step, and Proposition 3's divergence condition explains why λ is needed beyond invertibility. The paper is unusually honest about the LLQ rate's limitation: it states plainly that the eigenbasis alignment is not expected to hold in practice.\n\nSoft spots, in order. (1) Theorem 4's rate is conditional on that alignment assumption plus Gaussian/DPP idealizations, so the \"first explanation outside least-squares\" is heavily idealized. (2) The SPRING rate in Theorem 1 is imported from prior ARK analysis with \"appropriate choices\" of η and µ left unspecified; the equivalence is exact but the hyperparameter regime is not made constructive. (3) The SNGD LLS rate is effectively the same group's regularized Kaczmarz theorem after the equivalence; legitimate, but the new contribution is the identification, not the bound. (4) Minor QC: the abstract on the arXiv record describes a squared-volume-sampling proxy that appears nowhere in the paper; the paper's own abstract is different.\n\nThe reader's conditional verdict is about right. Who this is for: optimization theorists and the sketch-and-project community; the NNW/PINN narrative is motivation, not evidence. I would take the LLS half as near-verbatim and ask the authors to frame the LLQ theorem explicitly as an idealized proof of concept. It deserves a serious referee.","headline":"The LLS equivalences and first SPRING guarantee are solid; the LLQ rate is new but rests on an alignment assumption the authors admit is unrealistic, and the stress-test's alleged λ=0 slip is wrong on reading.","tokens_in":21565,"tokens_out":14124,"would_cite":true,"duration_ms":125712,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","68W20","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Subsampled natural gradient descent is, on linear least-squares problems, exactly regularized Kaczmarz; its momentum variant SPRING is accelerated Kaczmarz — yielding the first fast convergence rates for both.","keywords":["subsampled natural gradient descent","Kaczmarz method","sketch-and-project","SPRING momentum","convergence rate","linear least-squares","scientific machine learning","randomized linear algebra"],"falsifier":"Compute the spectrum of M = P J^+ H J for a realistic model Jacobian at a chosen regularization λ: if min Re(eig M) < 0, Proposition 3 predicts SNGD diverges for every step size, a prediction testable by running SNGD from a random initial point. Independently, test whether the expected projector P commutes with J^T J on a real neural-network Jacobian from a PINN or wavefunction model; if it does not, Theorem 4's conditions fail and its predicted rate (1 − κ⁻¹(H̃)αγ)^t should be checked empirically to see whether fast convergence persists outside the assumption.","tokens_in":20659,"feed_emoji":"🧮","tokens_out":15358,"duration_ms":132167,"temperature":0.7,"pith_summary":"Subsampled natural gradient descent (SNGD) and its momentum variant SPRING are behind recent successes in scientific machine learning — finding ground states of quantum systems and solving PDEs with neural networks — yet until now no analysis explained how they converge in the small-mini-batch regime that makes them practical. This paper closes that gap by proving that, for linear least-squares problems, SNGD is exactly a regularized Kaczmarz method and SPRING is exactly its Nesterov-accelerated counterpart, so existing randomized linear algebra theory applies directly. From that identification the paper obtains global convergence rates that hold for any batch size, the first convergence guarantee for SPRING in any setting, and the first proof that SPRING accelerates SNGD, by up to a square-root improvement in the error contraction rate. It also explains why SNGD beats SGD: the rate improves with the rate of spectral decay of the model Jacobian, which SGD cannot exploit. For the more general quadratic losses that model energy-based neural-network training, the paper proves a fast rate under a strong consistency condition, and shows that with too little regularization SNGD can diverge for every step size.","feed_headline":"Subsampled natural gradient is a Kaczmarz method in disguise","feed_subtitle":"First fast convergence proofs for SNGD and SPRING follow from this equivalence, explaining why they beat SGD.","key_machinery":"The central object is the random regularized projector P(S) = J_S^+ J_S, which maps vectors onto the row space of the sampled Jacobian rows. Bundling all stochasticity into P(S) — instead of separating the random gradient from the random preconditioner as earlier analyses did — turns the SNGD update into (I − ηP(S)) acting on the error, a contraction in expectation since P(S)² ⪯ P(S). This lets the paper import two ready-made analyses: regularized Kaczmarz for SNGD, and its accelerated version (ARK) for SPRING. For the LLQ extension, the new identity J_S^+ H J = P(S) J^+ H J, valid when range(HJ) ⊆ range(J), expresses the update as a random projector applied to a deterministic natural-gradie","core_discovery":"On consistent linear least-squares problems (Jθ* = b), SNGD is identical to regularized Kaczmarz iteration, and its momentum variant SPRING is identical to the accelerated regularized Kaczmarz (ARK) method. Using the same mini-batch for gradient and preconditioner bundles all randomness into one regularized projector P(S) = J_S^+ J_S, so the expected error shrinks as (1 − α)^t for SNGD and O((1 − √(α/β))^t) for SPRING — a square-root speed-up. These give the first fast rates for SNGD, the first convergence guarantee for SPRING, and the first proof SPRING accelerates SNGD. SNGD beats SGD by turning Jacobian spectral decay into acceleration. For the general LLQ loss, a similar rate holds only","pith_inferences":["Editorial inference: because the SNGD–Kaczmarz identity is algebraic, the transfer is not limited to convergence rates — improvements from the Kaczmarz literature, such as non-uniform row sampling or tail averaging, could be ported into SNGD/SPRING implementations; the paper itself only analyzes uniform sampling.","Editorial inference: the LLQ theorem's eigen-alignment condition is the point where theory and practice could diverge; checking whether P and J^T J share an eigenbasis on a real network Jacobian from a PINN or wavefunction model would reveal how wide that gap is. The paper's numerical experiments use Gaussian Jacobians, where the alignment holds only asymptotically, so they do not probe it.","Editorial inference: the central coupling insight — one mini-batch shared by gradient and curvature estimate collapsing into a single random projector — should carry over to subsampled Newton and Gauss-Newton methods, where the identical two-estimator coupling problem arises and a parallel contraction argument may be constructible.","Editorial inference: Proposition 3 yields a practical diagnostic: compute ξ(λ) = min Re eig(P J^+ H J) on a small surrogate model; its sign predicts guaranteed divergence (negative) versus guaranteed convergence (positive) for SNGD, giving a principled rule for choosing λ in energy-based training."],"forward_implications":["First fast convergence rates for SNGD on linear least-squares: expected squared error decays as (1 − α)^t for any batch size, not only asymptotically large ones.","First convergence guarantee for SPRING in any setting, plus the first proof that SPRING accelerates SNGD, by up to a square-root improvement in the rate.","Explains the empirical advantage of SNGD over SGD: the rate improves with the spectral decay exponent β of the Jacobian (k^β versus k), which matters for problems like PINNs whose Jacobians have rapidly decaying singular values.","Explains why using a single mini-batch for both the stochastic gradient and the stochastic preconditioner is beneficial, and why SPRING's gains are largest for small batch sizes.","For the LLQ losses that model energy-based wavefunction training, SNGD can diverge for every step size if the regularization λ is too small; a sufficiently large λ guarantees convergence, giving a new reason why λ > 0 is essential in practice."],"supporting_citations":[{"why":"Defines the regularized Kaczmarz method that SNGD is shown to be equivalent to, and supplies the (1−α)^t rate and the α-versus-SGD comparison used in Theorem 1.","marker":"Goldshlager et al. (2025)"},{"why":"Defines the accelerated regularized Kaczmarz (ARK) method that SPRING is shown to be equivalent to; its analysis yields the SPRING rate O((1−√(α/β))^t).","marker":"Dereziński et al. (2025)"},{"why":"Presents the ARK convergence bound in the form the paper applies, and supplies the Gaussian-sketch eigenbasis lemma used in Corollary 5.","marker":"Dereziński et al. (2024)"},{"why":"Foundational randomized block Kaczmarz analysis that licenses treating the regularized projector P(S) as the object whose expectation contracts.","marker":"Needell & Tropp (2014)"},{"why":"Companion analysis of randomized iterative methods cited for the expected-projector contraction argument.","marker":"Gower & Richtárik (2015)"},{"why":"Introduced SPRING, whose update equations the paper re-derives from ARK; its DPP expectation formula supports the eigenbasis condition in Proposition 9.","marker":"Goldshlager et al. (2024)"},{"why":"Supplies the weighted-sampling SGD analysis used to bound the SGD baseline rate that SNGD is compared against in Corollary 5.","marker":"Needell et al. (2014)"},{"why":"Establishes that mini-batch SGD rates scale at most linearly in batch size k, the comparison point in Corollary 5.","marker":"Jain et al. (2018)"}],"fun_headline_variants":["SNGD is Kaczmarz in disguise: first fast proofs","Subsampled natural gradient is regularized Kaczmarz","SPRING accelerates SNGD via Kaczmarz equivalence","Natural gradient equals Kaczmarz: new convergence rates","Hidden Kaczmarz structure gives SNGD and SPRING rates"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The linear least-squares results assume the system is consistent (an exact solution exists), and the extension to general quadratic losses additionally assumes the subsampled projector and the model's Gram matrix can be diagonalized using the same eigenvectors — a condition the paper itself says is not expected to hold in practice.","fun_headline_variants_meta":{"raw":{"variants":["SNGD is Kaczmarz in disguise: first fast proofs","Subsampled natural gradient is regularized Kaczmarz","SPRING accelerates SNGD via Kaczmarz equivalence","Natural gradient equals Kaczmarz: new convergence rates","Hidden Kaczmarz structure gives SNGD and SPRING rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000408,"raw_usage":{"total_tokens":1973,"prompt_tokens":779,"completion_tokens":1194,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":1119}},"tokens_in":523,"tokens_out":1194,"duration_ms":8425,"temperature":1.0,"reasoning_tokens":1119,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:37:03.839450+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the spectrum of M = P J^+ H J for a realistic model Jacobian at a chosen regularization λ: if min Re(eig M) < 0, Proposition 3 predicts SNGD diverges for every step size, a prediction testable by running SNGD from a random initial point. Independently, test whether the expected projector P commutes with J^T J on a real neural-network Jacobian from a PINN or wavefunction model; if it does not, Theorem 4's conditions fail and its predicted rate (1 − κ⁻¹(H̃)αγ)^t should be checked empirically to see whether fast convergence persists outside the assumption.","supporting_citations":[{"cited_title":"Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification","cited_arxiv_id":null,"evidence_quote":"Establishes that mini-batch SGD rates scale at most linearly in batch size k, the comparison point in Corollary 5."}],"review_version":1}