{"id":"67231c0e-635a-4ca4-8ee5-d046a8192be1","arxiv_id":"2509.17251","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Early-stopped gradient descent dominates ridge regression for all well-specified linear regression problems, and it dominates stochastic gradient descent whenever the covariance spectrum decays fast and continuously.","lead":"This paper proves that for linear regression, plain gradient descent with early stopping is never more than a constant factor worse than explicitly regularized ridge regression, and can be polynomially better. It also shows gradient descent and stochastic gradient descent are incomparable in general, but gradient descent wins on problems with fast decaying covariance spectra.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"GD-dominates-ridge is formally proven only for the Bayesian-symmetry class L'_b; the claimed extension to all well-specified (non-Bayesian) problems compares a high-probability upper bound with an expectation lower bound, which is not a valid step.","rationale":"The paper's headline contribution is the universal one-sided dominance of GD over ridge. The proof of Theorem 3.2 is legitimate for the Bayesian-symmetry class L'_b, and the rate computations for power-law classes appear sound given the stated bounds. However, the abstract and title assert dominance for 'any well-specified linear regression problem', and the only connection to the non-Bayesian class L_b is an informal paragraph that compares a high-probability upper bound with an expectation lower bound. That comparison is not a proof: an expectation lower bound can be dominated by rare design matrices and does not imply the required conditional high-probability lower bound. The additional issue that the L'_b proof averages over w* reinforces the same conclusion: the formal theorem is about a Bayesian-averaged risk, not a per-instance fixed-w* guarantee. These are correctness risks in the central claim, not merely presentation. The reader's weakest_assumption identified exactly this gap, and the appropriate action is to keep the CONDITIONAL verdict until the extension to L_b is either proven with a high-probability lower bound under Assumption 2C or explicitly removed from the stated scope of the main theorem.","tokens_in":46900,"tokens_out":11148,"duration_ms":107494,"concrete_test":"Re-derive the ridge lower bound in Proposition 2.1 under Assumption 2C without 2C', tracking the off-diagonal bias terms (the quantities that vanish only in expectation via x ~ -x, as in Zou et al. 2021). If these terms cannot be bounded pointwise with high probability, the Section 3 comparison for L_b is invalid. Then run a finite-dimensional Gaussian check with fixed anisotropic w* (e.g., Sigma = diag(i^{-2}), w* = e_1 + e_d, n=200): compute exactly E[E(hat w_gd)|X] and E[E(hat w_ridge)|X] for the matching stopping time, and estimate whether P(E[E_gd|X] <= c E[E_ridge|X]) >= 1-exp(-n/c0). If this high-probability inequality fails while the prior-averaged comparison holds, Theorem 3.2 must be restricted to the Bayesian-symmetry class L'_b.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 3.2, whose proof uses Proposition 2.1's ridge lower bound under Assumption 2C'. The text then asserts that 2C' can be replaced by 2C if one accepts comparing Theorem 3.1's high-probability upper bound with Proposition 2.1's expectation lower bound. This comparison is not justified: the theorem's conclusion is a high-probability inequality conditional on X, while the expectation lower bound only controls E[E(hat w_ridge)] averaged over X. On the high-probability event where the GD upper bound holds, the ridge conditional expectation could be far below its average, with the average inflated by rare X. Moreover, the L'_b proof averages over the prior on w* ('take an additional expectation over w*' in the proof of Theorem 3.2), yielding an averaged-over-prior bound rather than a guarantee for each fixed w*. Thus the formal result is a dominance statement for a Bayesian-averaged problem, not for the abstract's 'any well-specified linear regression problem' with fixed w*. This is load-bearing because the universal one-sided dominance is the headline contribution; restricting to L'_b, or proving a genuine high-probability ridge lower bound under 2C, changes the scope of the main theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies finite-sample excess-risk comparisons among gradient descent (GD), ridge regression, and online SGD in well-specified linear regression. It contributes two new upper bounds for GD (a ridge-type bound in Theorem 3.1 and an SGD-type bound in Theorem 4.3) and a new lower bound for GD (Theorem 4.1). Combining these with existing tight bounds for ridge and SGD, the paper claims (i) GD dominates ridge regression for all well-specified problems, (ii) GD and SGD are incomparable, and (iii) GD dominates SGD for problems with fast, continuously decaying covariance spectra. It also derives exact rates for the (a,r)-power-law class, recovering known minimax rates for GD and the suboptimality regions for ridge and SGD.","tokens_in":1644,"tokens_out":1974,"duration_ms":104721,"significance":"If the results hold as stated, this would be a valuable instance-wise complement to the classical worst-case minimax theory, identifying explicit cases where implicit regularization is provably at least as good as explicit regularization. The new finite-sample bounds for GD, especially the SGD-type bound in Theorem 4.3 and the lower bound in Theorem 4.1, are potentially reusable technical tools. The appendix proofs are detailed and, as far as I checked, internally coherent. However, the headline claim of universal dominance of GD over ridge is currently not supported by the formal statements, because the only proved theorem for that claim uses a Bayesian prior over the target parameter and a comparison of high-probability and expectation bounds that is not justified as written. This limits the significance of the paper's central conceptual message, although the individual bounds and rate computations remain of interest.","major_comments":[{"comment":"The theorem is stated for the Bayesian class L'_b, and the proof explicitly says 'we take an additional expectation over w*' before combining Theorem 3.1 with Proposition 2.1. This yields a bound that is averaged over the prior on w*, not a guarantee for each fixed w* in the class. The subsequent claim that 'if one accepts comparing the high probability upper bound in Theorem 3.1 with the expectation lower bound in Proposition 2.1, then Assumption 2C' can be replaced by Assumption 2C' is not a valid step: Theorem 3.1 gives a high-probability upper bound on E[E_GD|X], whereas the third bullet of Proposition 2.1 is an unconditional expectation lower bound on E[E_ridge]. On the high-probability event on which the GD upper bound holds, the conditional expectation E[E_ridge|X] may be far below its unconditional average, so the claimed inequality E[E_GD|X] ≤ c E[E_ridge|X] does not follow. Because the abstract and Table 1 advertise 'all well-specified linear regression problems' and the formal L_b class is meant to be the non-Bayesian version, this is a load-bearing gap in the central dominance claim. The authors should either prove a genuine high-probability ridge lower bound under Assumption 2C for fixed w*, or reformulate the dominance result as a Bayesian-averaged statement and adjust the abstract and table accordingly.","section":"Section 3, Theorem 3.2 and its proof (pp.8-9)"},{"comment":"The abstract states the first finding for 'any well-specified linear regression problem', but the formal class L_b in Eq. (1) requires Assumption 1A (independent sigma_x^2-subgaussian entries of Sigma^{-1/2}x), Assumption 2B, Assumption 2C (symmetric x), and the signal-to-noise bound ||w*||_Sigma^2 ≤ b sigma^2. These are substantial restrictions that exclude, for example, designs with dependent whitened coordinates or strongly skewed x distributions. The dominance claim is also never proved for the full non-Bayesian L_b, as noted above. The authors should either prove the result under weaker assumptions or explicitly qualify the headline claim so that the abstract's 'any well-specified linear regression problem' is replaced by the formal class actually covered.","section":"Abstract and Section 1 vs. Eq. (1)"}],"minor_comments":[{"comment":"The phrase 'we take an additional expectation over w*' needs a precise probability-space statement: the high-probability event in Theorem 3.1 is over X for fixed w*, and averaging over w* can change the probability measure with respect to which the inequality holds. Please clarify whether the theorem's 'with probability' is over (X,w*) jointly or over X for the prior-averaged risk.","section":"Section 3, proof of Theorem 3.2"},{"comment":"The definition of f ≲ g says 'for every x, f(x) ≤ c g(x)', but x is overloaded with the covariate; it would be clearer to say 'for all arguments' or to use a different placeholder.","section":"Notation, Section 2"},{"comment":"The effective variance error is stated twice in the same display ('EffectiveVariance≤ ...' followed by 'where EffectiveVariance≤ ...'), and the brace-heavy decomposition of the bound is difficult to parse. Restating the bound with named components (e.g., B_var, B_eff) would improve readability.","section":"Theorem 4.3 (p.11)"},{"comment":"Typo: 'varaince' should be 'variance'.","section":"Appendix A, p.21"},{"comment":"Minor typos: 'subGussian' should be 'subgaussian'; 'diagnoal' should be 'diagonal'; 'becasue' should be 'because'; 'defintion' should be 'definition'.","section":"Appendix B, Lemma B.4 proof; Appendix C; Appendix E"},{"comment":"The claim that 'the best of ridge regression and SGD is (nearly) optimal for all power law classes' relies on Corollary 5.3 whose lower bound is eOmega(n^{-2r}), i.e., up to log factors; the statement and the figure should make the logarithmic factor explicit.","section":"Section 5 and Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The central technical issue is that Theorem 3.2's dominance statement is proved only for the Bayesian-averaged class L'_b and the non-Bayesian extension rests on comparing a high-probability upper bound with an expectation lower bound, which is not valid without additional argument. This is the kind of issue that can be fixed by either proving a suitable high-probability ridge lower bound or by honestly restricting the claims to L'_b; either way the abstract and the main theorem need to be brought into agreement. The rest of the paper, including the GD-vs-SGD incomparability and the rate computations, appears more solid and should be preserved. I recommend major revision rather than rejection because the core derivations are sound and the gap is localized."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing about this paper. It is a technically substantial contribution: the new GD bounds are real, and the \"GD can be polynomially worse than SGD\" construction is the most interesting thing in it. But the headline claim — GD dominates ridge for every well-specified problem — is formally proven only for a Bayesian-averaged subclass, and the paper's own text concedes the step that would extend it.\n\nWhat is genuinely new: Theorem 3.1 is a ridge-type upper bound for GD that works for a general anisotropic w*, which is a real generalization of Ali et al. (2019), who needed an isotropic prior. Theorem 4.1 (a GD lower bound) and Theorem 4.3 (an SGD-type GD upper bound) are new, and the Section 5 power-law rate calculations are clean. Theorem 4.2, where GD is polynomially worse than SGD via a benign-overfitting-style construction, is novel and surprising. The citation pattern is honest: the external ridge and SGD bounds they lean on are published tight results, and the self-citations are to the relevant prior analyses.\n\nThe weak point is Theorem 3.2. The proof takes an additional expectation over w* under Assumption 2C', so what is shown is a bound on the prior-averaged risk, not a bound for each fixed w*; that is a weaker statement than \"for every mu in L'_b\" as written. Then the text offers that Assumption 2C' can be replaced by 2C \"if one accepts comparing\" the high-probability GD upper bound with the expectation ridge lower bound. I don't accept that comparison, and neither should a referee: the GD bound holds on a high-probability event conditional on X, while the ridge expectation lower bound only controls the average over X, and the conditional ridge risk on the good event can sit well below that average. The authors flag this in the same paragraph, which is honest but does not make it valid. This matters because the one-sided dominance is the paper's main selling point.\n\nOther issues are minor. Assumption 1A (independent subgaussian entries of Sigma^{-1/2}x) is restrictive and is acknowledged as such. Constants are deliberately untracked, which is fine for the stated purpose.\n\nWho this is for: the implicit-regularization and statistical-learning-theory crowd. It deserves a serious referee — the new bounds are substantive and the gap is exactly what referees are for. I would send it out with a clear instruction: either prove a genuine high-probability ridge lower bound under Assumption 2C, or restate the theorem for L'_b and align the abstract with the formal result.","headline":"Substantial new bounds for GD plus a surprising GD-loses-to-SGD construction, but the headline GD-dominates-ridge claim is formally proven only for a Bayesian-averaged class, and the paper's own extension step beyond that class is not valid.","tokens_in":47710,"tokens_out":7507,"would_cite":true,"duration_ms":65935,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62J05","62J07","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that early-stopped gradient descent dominates ridge regression for all well-specified linear regression problems, while remaining incomparable with SGD overall.","keywords":["gradient descent","ridge regression","stochastic gradient descent","implicit regularization","excess risk","linear regression","early stopping","benign overfitting"],"falsifier":"Exhibit a well-specified linear regression problem satisfying Assumptions 1 and 2 where, for some fixed ridge penalty $\\lambda\\ge 0$, every GD stopping time $t$ gives expected excess risk larger than a constant times the ridge expected excess risk; a simulated Gaussian spike-covariance problem whose tail spectrum is slow is the natural place to look. Such an instance would directly contradict Theorem 3.2.","tokens_in":46687,"feed_emoji":"📉","tokens_out":6314,"duration_ms":53874,"temperature":0.7,"pith_summary":"This paper compares the finite-sample excess risks of three estimators on every well-specified linear regression problem: gradient descent with early stopping, ridge regression, and online SGD. Its central claim is that GD's implicit regularization dominates explicit ridge regularization: with comparable regularization (stopping time inversely proportional to the ridge penalty), GD's excess risk is always within a constant factor of ridge's, and for natural problems ridge can be polynomially worse even after optimal tuning. Against SGD, the picture is mixed: GD is incomparable overall, being polynomially better on some problems and polynomially worse on specially constructed ones, but GD dominates SGD on problems whose covariance spectra decay fast and continuously. If true, this means a simple unregularized early-stopped algorithm is a statistically safe, often superior substitute for a tuned regularized estimator.","feed_headline":"Early-stopped gradient descent dominates ridge regression","feed_subtitle":"Compared instance by instance, implicit regularization is never worse up to constants—and can win polynomially.","key_machinery":"The argument runs through a scalar-parameter family of bounds indexed by an effective regularization strength: for GD this is $1/(\\eta t)$ plus a tail quantity, exactly matching ridge's $\\lambda$ at the critical index $k^*$ where bias and variance balance. The load-bearing object is the GD shrinkage matrix $\\tilde A = (I - (I - \\eta XX^\\top/n)^t)^{-1} XX^\\top$, which the paper proves is comparable to ridge's shrinkage matrix $XX^\\top + n\\lambda I$; this reduction yields a new ridge-type upper bound for GD (Theorem 3.1), a new SGD-type upper bound (Theorem 4.3) that decomposes risk into bias, variance, and an effective-variance term controlled by the order-1 effective dimension $D_1$, and a new lower bound for GD (Theorem 4.1). Assumption 3, that the covariance spectrum decays fast and continuously, brings $D_1$ within a constant factor of the effective dimension $D$, which is exactly what lets GD match SGD's bias decay in that subclass.","core_discovery":"For the class of well-specified linear regression problems satisfying the paper's conditions, the paper proves (Theorem 3.2) that for every ridge penalty $\\lambda \\ge 0$ there is a GD stopping time $t$ such that, with high probability, $E[E_\\mu(\\hat w^{\\mathrm{GD}}_t)|X] \\le c\\, E[E_\\mu(\\hat w^{\\mathrm{ridge}}_\\lambda)|X]$, where $c$ depends only on the subgaussian constant and the signal-to-noise ratio, not on the problem or sample size. It also proves that the reverse inequality can fail polynomially: in $(a,r)$-power-law classes with source condition $r>1$, ridge's optimally tuned excess risk is $\\Omega(n^{-2a/(1+2a)})$, while GD attains the minimax rate $n^{-2ar/(1+2ar)}$. The paper further shows GD and SGD are incomparable by constructing a spike-covariance family where GD's risk is $\\Omega(n^{-0.2})$ while SGD achieves $O(\\log n / n)$, and it shows GD dominates SGD under Assumption 3, a fast continuously decaying spectrum condition that every power-law spectrum satisfies.","pith_inferences":["A natural empirical extension would be to test whether data-driven stopping-time selection, such as validation, preserves the dominance over tuned ridge in finite samples; the paper's fixed-proportional stopping proof does not cover that selection rule.","The paper notes that multi-epoch SGD is no worse than either GD or SGD, which suggests the dominance results may extend to multi-epoch procedures, but that extension is not established here.","Because the hard GD-versus-SGD examples are built from benign-overfitting spike spectra, the paper can be read as delineating when early stopping should be preferred to online averaging; a practical rule of thumb might pick between them based on the empirical eigenvalue decay rate.","The comparison framework could be tested on kernel regression with nontrivial spectra, though all bounds here rely on analytic formulas special to linear regression."],"forward_implications":["For any well-specified linear regression problem, a user can switch from tuned ridge regression to early-stopped GD and never pay more than a constant factor in excess risk, while sometimes gaining polynomially in sample size.","In power-law classes with smooth source conditions ($r>1$), ridge regression and SGD are polynomially suboptimal, whereas GD is minimax optimal for all $r\\ge 0$, so early stopping alone achieves the best possible rate.","GD and SGD occupy incomparable regimes: benign-overfitting-style spike problems favor SGD by a polynomial gap, while fast-decay-spectrum problems favor GD, so the batch versus online choice must depend on the covariance structure.","Within the fast continuously decaying subclass, which contains all standard capacity-condition models, GD is at least as good as SGD up to constants, making early-stopped GD a robust default there."],"supporting_citations":[{"why":"Supplies the tight ridge upper and lower bounds in Proposition 2.1 that the GD-versus-ridge dominance argument compares against.","marker":"Tsigler and Bartlett, 2023"},{"why":"Provides the benign-overfitting variance bounds and the critical-index machinery used in the ridge bounds and in the GD lower bound.","marker":"Bartlett et al., 2020"},{"why":"Provides the expectation lower bound for ridge regression under symmetry and the prior comparison of SGD versus ridge that motivates the GD-SGD analysis.","marker":"Zou et al., 2021"},{"why":"Supplies the tight SGD upper and lower bounds in Proposition 2.2 used to compare GD with SGD.","marker":"Wu et al., 2022b"},{"why":"Develops the operator method underlying the SGD bounds and the exponential-decay bias analysis for SGD.","marker":"Zou et al., 2023"},{"why":"Contributes the shrinkage-matrix comparison lemma (Lemma B.2) that lets the paper bound the GD variance and bias by ridge-style quantities.","marker":"Zou et al., 2022"},{"why":"Defines the capacity and source conditions and the minimax rates for the power-law classes used in Section 5.","marker":"Caponnetto and De Vito, 2007"},{"why":"Provides the earlier GD-versus-ridge comparison under an isotropic prior, which Theorem 3.2 generalizes to anisotropic priors.","marker":"Ali et al., 2019"}],"fun_headline_variants":["Implicit regularization beats explicit in linear regression","Early-stopped gradient descent beats ridge regression","GD wins over ridge, but loses to SGD on some problems","Ridge regression loses to early-stopped gradient descent","Implicit beats explicit, but SGD can beat implicit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that GD dominates ridge needs a symmetry condition on the optimal parameter's prior (Assumption 2C') or, without it, a comparison between a high-probability GD upper bound and an expectation ridge lower bound; all upper bounds also require the whitened covariates to have independent, subgaussian entries, and if those fail the dominance statements are unproven.","fun_headline_variants_meta":{"raw":{"variants":["Implicit regularization beats explicit in linear regression","Early-stopped gradient descent beats ridge regression","GD wins over ridge, but loses to SGD on some problems","Ridge regression loses to early-stopped gradient descent","Implicit beats explicit, but SGD can beat implicit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000413,"raw_usage":{"total_tokens":2156,"prompt_tokens":984,"completion_tokens":1172,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":1096}},"tokens_in":600,"tokens_out":1172,"duration_ms":10913,"temperature":1.0,"reasoning_tokens":1096,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:47:34.257385+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a well-specified linear regression problem satisfying Assumptions 1 and 2 where, for some fixed ridge penalty $\\lambda\\ge 0$, every GD stopping time $t$ gives expected excess risk larger than a constant times the ridge expected excess risk; a simulated Gaussian spike-covariance problem whose tail spectrum is slow is the natural place to look. Such an instance would directly contradict Theorem 3.2.","supporting_citations":[{"cited_title":"Benign overfitting in ridge regression","cited_arxiv_id":null,"evidence_quote":"Supplies the tight ridge upper and lower bounds in Proposition 2.1 that the GD-versus-ridge dominance argument compares against."},{"cited_title":"The benefits of implicit regularization from sgd in least squares problems","cited_arxiv_id":null,"evidence_quote":"Provides the expectation lower bound for ridge regression under symmetry and the prior comparison of SGD versus ridge that motivates the GD-SGD analysis."},{"cited_title":"Benign overfitting of constant-stepsize sgd for linear regression","cited_arxiv_id":null,"evidence_quote":"Develops the operator method underlying the SGD bounds and the exponential-decay bias analysis for SGD."},{"cited_title":"A continuous-time view of early stopping for least squares regression","cited_arxiv_id":null,"evidence_quote":"Provides the earlier GD-versus-ridge comparison under an isotropic prior, which Theorem 3.2 generalizes to anisotropic priors."}],"review_version":2}