{"id":"0ac8ac58-b42a-4a53-af3f-6a6ad61a9db2","arxiv_id":"2411.17567","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Repeating forward gradient descent updates on each sample ℓ times improves the linear-model error rate from d²/n to d²/(ℓ∧d)n, matching SGD when ℓ≈d.","lead":"Forward gradient descent is a biologically plausible learning rule that replaces backpropagation with random projections. This paper proves that reusing each training sample up to d times with fresh random projections closes the statistical gap to stochastic gradient descent in linear regression.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The theorem is internally sound, but the advertised rates are conditional on oracle knowledge of the population spectrum and norm bound b; without an adaptive step-size rule, the minimax d/k claim is not an implementable guarantee.","rationale":"I read Theorem 3.1 and its proof appendix in detail. The induction through Proposition A.5 is explicit, and the Loewner-order steps in Lemma A.4 are valid: the coefficient reduction 1 - 2y + 4y^2 <= 1 - y uses y = alpha X^T X <= 1/4, and the additional 3y^2 term from the prediction-error term is absorbed into that coefficient before the inequality is applied. The final product bound in Theorem 3.1 is correct when the integral approximation is taken from k1 to k2+1. Thus the central mathematical claim is internally consistent. The weakest premise is exactly the one the reader flagged: the step-size constants require oracle knowledge of the population spectrum and the norm bound b, and no adaptive procedure is supplied. The simulations appear to operate in the oracle setting, though the code would need inspection to confirm. A secondary caveat, present in the text but absent from the abstract, is that with the stated constants the d/k regime only starts at k of order d^2 because c1 c2 = Omega(d) makes the bias term ((1+c1 c2)/(k+1+c1 c2))^2 MSPE(theta_0) of order d^3/k^2 when Sigma = I_d. This weakens the practical reading of 'minimax optimality' but does not invalidate the rate result. I therefore agree with the reader's verdict and see no reason to change it.","tokens_in":25521,"tokens_out":27765,"duration_ms":240620,"concrete_test":"Inspect the released GitHub code (github.com/NiklasDexheimer/FGDsimulations) to determine whether the learning-rate constants c1, c2 and the repetition count ell are chosen using the true population Sigma and b. If they are, re-run the main simulations with c1 and c2 estimated from a preliminary sample (for example, the first half of the data) and check whether the d/k scaling in Figures 4.1-4.2 is preserved; if the performance degrades substantially, the oracle-tuning premise is essential to the paper's empirical claims.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1 establishes the convergence rate only for learning rates alpha_i = c1/(ell(c1 c2 + i)) with c1 >= 2/lambda_min_ne0(Sigma) and c2 >= (3b/lambda_min_ne0(Sigma))(2 lambda_max(Sigma) + tr(Sigma)/ell). These constants depend on population-level quantities — the smallest nonzero and largest eigenvalues of Sigma, the trace of Sigma, and the almost-sure bound b on ||X_1||^2 — that are not available to a user. The paper provides no data-dependent procedure for choosing c1 and c2, and the simulation section does not state that the experiments avoid this oracle. The abstract's wording that FGD(ell) 'achieves' the rate d^2/((ell wedge d) k) is therefore a conditional existence statement: if one knew the spectrum of Sigma and b, the stated bound follows. I checked the induction via Proposition A.5 and found no circular step; the proof is coherent. The oracle assumption is the least secure premise on which the advertised rates rest, though it is a standard limitation in optimization theory and does not by itself make the theorem false.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces FGD(ell), a repeated-sampling variant of forward gradient descent for the linear model, in which each training sample is used for ell consecutive updates with independent Gaussian random projections. The main result (Theorem 3.1) provides a nonasymptotic bound on the mean squared prediction error under the step-size schedule alpha_i = c1/(ell(c1 c2 + i)), with constants c1 and c2 that depend on the population spectral quantities of the input covariance matrix Sigma and an almost-sure bound b on the squared norm of the inputs. The bound implies that for ell >= tr(Sigma) the error decays at the rate b/k up to a transient, and that for rank-s input distributions the algorithm attains the rate s/k. The proof controls the stochastic dependencies induced by repeated sampling through conditional Gaussian fourth-moment identities and recursive Loewner-order inequalities. An analogous result is proved for an adjusted version aFGD(ell), and a simulation study is included.","tokens_in":25741,"tokens_out":16686,"duration_ms":139135,"significance":"The result is significant because it closes the gap between forward gradient descent and stochastic gradient descent in the linear model: with ell approximately d forward passes per sample, the prediction error rate improves from the known d^2/k rate to the minimax d/k rate. The main mathematical contribution is the careful tracking of the dependence between the iterate and the repeated random projections, which is the core difficulty of repeated sampling. The paper gives explicit nonasymptotic constants, demonstrates adaptation to low-dimensional structure, and makes the simulation code available. The primary limitation is that the step-size constants in Theorem 3.1 are oracle-dependent, so the rate guarantee is conditional on knowledge of the spectrum of Sigma and the norm bound b; this is a common feature in optimization theory but should be stated explicitly in the abstract.","major_comments":[],"minor_comments":[{"comment":"The step-size constants c1 and c2 in Theorem 3.1 depend on lambda_min_neq0(Sigma), lambda_max(Sigma), tr(Sigma), and the almost-sure norm bound b. The abstract states that FGD(ell) 'achieves' the rate d^2/((ell wedge d)k) without mentioning that the guarantee requires knowledge of these population quantities. Please add an explicit caveat that the rate is conditional on such oracle information and that no data-dependent procedure for choosing c1 and c2 is provided.","section":"Section 3, Theorem 3.1"},{"comment":"The inequality labelled (A.1) is written with exponents r-1 and ell-1, while the lemma statement concerns the exponent r. This appears to be a typographical error, since the bound 1-(1-y)^r <= 2 r y follows directly for y in [0,3/4]; please correct the displayed inequality to match the lemma statement.","section":"Lemma A.2, equation (A.1)"},{"comment":"In the proof of Theorem B.2, the conditional expectation E[eps_k omega_{k,r} | X_k] is stated without a detailed derivation; adding a short derivation analogous to Lemma A.2 would improve readability.","section":"Appendix B, proof of Theorem B.2"},{"comment":"The simulation section does not report how the learning-rate constants were selected for FGD(ell) and aFGD(ell). If the oracle values from Theorem 3.1 were used, this should be stated; if a heuristic was used, the authors should explain the choice, since the theoretical guarantee does not apply to arbitrary constants.","section":"Section 4, simulation study"},{"comment":"The notation 'lambda_min_neq0(Sigma)' is used in the introduction without a definition; it is defined in the notation subsection, but consider defining it at first use in the introduction as well.","section":"Section 1, notation"}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound and the oracle step-size issue is the only substantive concern; I do not think it invalidates the theorem, but the authors should temper the abstract and explicitly discuss the limitation. The paper fits the scope of the journal and the simulation code is a nice addition."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper actually proves what it claims. FGD(d) achieves the minimax d/k rate in the linear model, closing the d-factor gap shown for FGD(1). The main technical work is controlling the dependence when the same sample is used ell times, and the proof handles that via a contraction recursion (Proposition A.5) that I checked. No circular steps, no fitted constants. This is a genuine new result, not a repackaging.\n\nWhat is good: the d^2/((ell wedge d) k) bound is explicit, the low-dimensional subspace adaptation (s/k with ell=s) is a nice bonus, and the bias-variance decomposition in Theorem 2.1 gives intuition for why repeated sampling helps. The simulations are consistent with the rates, including the empirical flattening of the error for ell beyond the effective rank.\n\nSoft spots: the step-size schedule requires knowing population quantities — lambda_min nonzero, lambda_max, tr(Sigma), and the almost-sure bound b. The theorem is a conditional guarantee: if you know those, this rate holds. There is no adaptive scheme offered, so a user cannot implement the schedule from data alone. That is a standard limitation in optimization theory, but the abstract's 'achieves' should be read as 'achieves given oracle knowledge of the spectrum.' Also, the d/k rate only kicks in for k ≳ d^2; for smaller k the bias term dominates. That is not hidden, but it is easy to miss. The Github code has no commit hash, so reproducibility is slightly weaker than it should be.\n\nBottom line: a solid, clearly written paper for people working on forward gradients, zeroth-order methods, or biologically plausible learning. It deserves a serious referee; my main request would be a discussion of how the constants could be estimated or avoided, and a note on the k ≳ d^2 regime. I would send it out. Would I cite it? Yes, if I were working on forward gradient methods.","headline":"Repeated-sampling FGD provably reaches the SGD minimax rate in the linear model; the proof is sound and the oracle step-size caveat is standard, not fatal.","tokens_in":26282,"tokens_out":2511,"would_cite":true,"duration_ms":25156,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62J05","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Repeated sampling makes forward gradient descent minimax-optimal in the linear model.","keywords":["forward gradient descent","repeated sampling","linear regression","mean squared prediction error","minimax rates","zeroth-order optimization","Gaussian random projections","stochastic approximation"],"falsifier":"Run FGD(d) and SGD on the same Gaussian-design linear model with $d=100$, $n=5\\times 10^4$, and oracle step sizes; if the mean squared prediction error of FGD(d) is not within a constant factor of SGD's $d/n$ curve, Theorem 3.1's rate is contradicted.","tokens_in":25314,"feed_emoji":"📈","tokens_out":6768,"duration_ms":59346,"temperature":0.7,"pith_summary":"Forward gradient descent (FGD) estimates a gradient by multiplying the loss gradient with a random Gaussian projection vector, avoiding the backward pass but paying a d-fold penalty in the linear-model prediction error compared with SGD. This paper introduces FGD(ℓ), which draws ℓ fresh projection vectors and updates ℓ times on each training sample, and proves that the penalty shrinks from d to d/(ℓ∧d). In particular, taking ℓ=d recovers the minimax-optimal d/k rate, so a biologically plausible forward-only update rule matches SGD statistically. The paper also shows the method adapts to low-dimensional input structure: if the covariates live in an s-dimensional subspace, FGD(s) achieves s/k, and simulations match the predicted d/(ℓ∧d) dependence.","feed_headline":"Forward gradient descent matches SGD with d repeats per sample","feed_subtitle":"Repeated sampling cuts the d-fold slowdown to d/(ℓ∧d), recovering the minimax d/k rate at ℓ=d.","key_machinery":"The working object is the FGD(ℓ) update $\\theta_{k,r} = \\theta_{k,r-1} + \\alpha_k (Y_k - X_k^\\top \\theta_{k,r-1}) X_k^\\top \\xi_{k,r} \\xi_{k,r}$, where fresh independent standard normal vectors $\\xi_{k,r}$ are drawn for each of the ℓ repeats. The analysis rests on a Gaussian fourth-moment identity (Lemma A.1): for $Z \\sim N(0,\\Gamma)$ independent of an $\\mathcal{F}$-measurable vector $U$, $\\mathbb{E}[(U^\\top Z)^2 Z Z^\\top | \\mathcal{F}] = 2\\Gamma U U^\\top \\Gamma + U^\\top \\Gamma U \\Gamma$. This identity lets the authors take conditional expectations inside a sample despite the correlation built up by the repeated updates, yielding a one-step contraction inequality for the MSPE in which the contraction coefficient is $1 - 2\\alpha_k \\ell \\lambda_{\\min\\neq 0}(\\Sigma) + O(\\alpha_k^2)$ and the added variance is $O(\\alpha_k^2 \\ell (\\ell \\lambda_{\\max}(\\Sigma) + \\mathrm{tr}(\\Sigma)))$. Iterating that recursion with the decaying step schedule gives the stated rate.","core_discovery":"At its core, the paper proves Theorem 3.1: for the linear model with $\\|X_1\\|^2 \\le b$ and step sizes $\\alpha_i = c_1/(\\ell(c_1 c_2 + i))$ chosen with $c_1 \\ge 2/\\lambda_{\\min\\neq 0}(\\Sigma)$ and $c_2 \\ge (3b/\\lambda_{\\min\\neq 0}(\\Sigma))(2\\lambda_{\\max}(\\Sigma)+\\mathrm{tr}(\\Sigma)/\\ell)$, the mean squared prediction error after $k$ samples satisfies $\\mathrm{MSPE}(\\theta_{k,\\ell}) \\le ((1+c_1 c_2)/(k+1+c_1 c_2))^2 \\mathrm{MSPE}(\\theta_0) + 16 b c_1^2 (\\lambda_{\\max}(\\Sigma)+\\mathrm{tr}(\\Sigma)/\\ell) k/(k+1+c_1 c_2)^2$. Reading the bound with $b = d m^2$ shows the rate $d^2/((\\ell \\wedge d) k)$, and for $\\ell = d$ this is the minimax $d/k$ rate. If the inputs are supported on an $s$-dimensional subspace, FGD($s$) is shown to achieve $s/k$ up to constants. The proof handles the stochastic dependence between the $\\ell$ updates on one sample, which is the obstacle that had kept repeated sampling out of earlier analyses.","pith_inferences":["The oracle requirement on step sizes is the paper's main practical gap; a data-dependent choice of $c_1$ and $c_2$ from empirical covariance estimates would make the rate adaptive, but such a procedure is not proven here.","Because the proof only uses the Gaussian fourth-moment structure of the projections, the same contraction argument should carry over to other isotropic or sub-Gaussian projection distributions, with constants changed; the $d/(\\ell \\wedge d)$ trade-off is likely not special to normality.","For a near-low-rank covariance with slowly decaying eigenvalues, Theorem 3.1 suggests the effective repetition count is the effective rank $\\mathrm{tr}(\\Sigma)/\\lambda_{\\max}(\\Sigma)$; testing FGD(ℓ) with ℓ equal to this quantity on such designs would be a direct numerical check of the trade-off.","The variance-reduction mechanism suggests a broader recipe: any zeroth-order or projection-based optimizer that doubles its forward evaluations can buy back a polynomial factor in dimension; whether this extends to nonlinear models near initialization is open."],"forward_implications":["FGD(d) matches SGD's minimax prediction-error rate $d/k$ in the linear model, so a forward-only update rule can be statistically as efficient as backpropagation-based SGD.","Repeating a sample more than $d$ times, or more than the effective rank $\\mathrm{tr}(\\Sigma)/\\lambda_{\\max}(\\Sigma)$, does not improve the leading-order MSPE bound; the useful repetition count is governed by the input dimension or intrinsic dimension.","When the covariates concentrate on an $s$-dimensional subspace, only $s$ repeats per sample are needed to obtain the $s/k$ rate, so the method automatically benefits from low-dimensional structure.","The bias of FGD(ℓ) is essentially the bias of FGD with learning rate scaled by $1/\\ell$, while the variance is reduced; this locates the $d$-factor suboptimality of plain FGD in the variance of the random projection step."],"supporting_citations":[{"why":"Introduces forward gradient descent and conjectures that repeated sampling per training sample should improve its performance.","marker":"[4]"},{"why":"Provides the prior FGD analysis in the linear model with a $d^2 \\log(d)/n$ rate, and supplies the Lemma 4.1 identity and autoregressive representation the current proof builds on.","marker":"[7]"},{"why":"Gives a minimax lower bound of $d^2/n$ for estimators querying each sample at most twice, explaining why ℓ repeats per sample are needed to reach the $d/n$ rate.","marker":"[27]"},{"why":"Supplies the standard inequality involving $\\exp(-x)$ used in Lemma A.2 to control the contraction factors in the recursion.","marker":"[1]"}],"fun_headline_variants":["Repeated sampling closes FGD's d-fold gap to SGD","One sample, ℓ updates: FGD hits SGD rate at ℓ=d","Forward gradient descent catches SGD with ℓ repeats per sample","ℓ-step FGD per sample recovers minimax rate","Repeated sampling in FGD: from d² slow to d/k optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The step-size schedule requires knowing or tightly bounding the population covariance's nonzero eigenvalues, its trace, and an almost-sure norm bound $b$ on the inputs; without that oracle information the stated rate is not shown and no adaptive choice is supplied.","fun_headline_variants_meta":{"raw":{"variants":["Repeated sampling closes FGD's d-fold gap to SGD","One sample, ℓ updates: FGD hits SGD rate at ℓ=d","Forward gradient descent catches SGD with ℓ repeats per sample","ℓ-step FGD per sample recovers minimax rate","Repeated sampling in FGD: from d² slow to d/k optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000699,"raw_usage":{"total_tokens":3176,"prompt_tokens":986,"completion_tokens":2190,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":2099}},"tokens_in":602,"tokens_out":2190,"duration_ms":15247,"temperature":1.0,"reasoning_tokens":2099,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:59:39.189032+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run FGD(d) and SGD on the same Gaussian-design linear model with $d=100$, $n=5\\times 10^4$, and oracle step sizes; if the mean squared prediction error of FGD(d) is not within a constant factor of SGD's $d/n$ curve, Theorem 3.1's rate is contradicted.","supporting_citations":[{"cited_title":"Convergence guarantees for forward gradient descent in the linear regression model","cited_arxiv_id":null,"evidence_quote":"Provides the prior FGD analysis in the linear model with a $d^2 \\log(d)/n$ rate, and supplies the Lemma 4.1 identity and autoregressive representation the current proof builds on."},{"cited_title":"Hebbian learning inspired estimation of the linear regression parameters from queries","cited_arxiv_id":"2311.03483","evidence_quote":"Gives a minimax lower bound of $d^2/n$ for estimators querying each sample at most twice, explaining why ℓ repeats per sample are needed to reach the $d/n$ rate."},{"cited_title":"Abramowitz and I","cited_arxiv_id":null,"evidence_quote":"Supplies the standard inequality involving $\\exp(-x)$ used in Lemma A.2 to control the contraction factors in the recursion."}],"review_version":1}