{"id":"0bce5dbf-7518-4c76-b583-01a9b5306eb5","arxiv_id":"2502.09106","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For power-law data and target decays, SGD on the quadratically parameterized model provably beats linear SGD when the target opposes the spectrum, with rates T^{-(2β-2)/(α+β)} versus T^{-(β-1)/α}.","lead":"This paper proves convergence-rate bounds for stochastic gradient descent on a quadratically parameterized linear regression model, showing that an effective dimension emerges from the data spectrum and ground-truth decay. It reports that this toy feature-learning model can beat plain linear SGD when the ground truth opposes the covariance spectrum, and claims to match the information-theoretic limit when the two align.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Quoted minimax lower bound T^{-1/β} conflicts with the paper's own upper rate T^{-(β-1)/β} for β>2 in the α≤β regime, undermining the optimality claim.","rationale":"The reader's formal 'weakest_assumption' was Assumption 3.1's independent Gaussian covariates, but the reader's rationale also flagged 'the internal exponent conflict between the stated information-theoretic lower bound and the paper's own upper rate.' I identify this exponent conflict as the single most load-bearing concern because it directly threatens the paper's headline optimality result and the correctness of the main upper bound, rather than only the transferability to correlated or non-Gaussian data. If the quoted lower bound T^{−1/β} is correct, then for β > 2 the upper bound T^{−(β−1)/β} is mathematically impossible for a minimax-optimal algorithm, so the proof of Theorem 4.1 must contain a gap—likely in the Phase II approximation or the choice of effective dimension D. If the lower bound is misquoted and should be T^{−(β−1)/β}, then the optimality claim is restored but the manuscript requires a correction. Either way, the contradiction must be resolved before the central claim can be accepted. The Gaussian-independence concern remains valid as a limitation, but it is secondary to an internal logical inconsistency in the stated rates. Therefore I recommend CONDITIONAL acceptance: the authors must provide a correct statement of the minimax lower bound, or identify and fix the error in Theorem 4.1, before the scaling law and separation results can be considered established.","tokens_in":47938,"tokens_out":7064,"duration_ms":69065,"concrete_test":"Independently re-derive the minimax lower bound for the class of ground truths satisfying Assumption 3.3, i.e., λ_i ≍ i^{−α} and λ_i(v*_i)^4 ≍ i^{−β}, using Fano's or Assouad's method. If the correct minimax exponent is (β−1)/β (which a standard bias-variance truncation would predict), then Remark 4.4's T^{−1/β} is a typo and the paper's upper bound can be compatible. If the correct minimax exponent is 1/β, then Theorem 4.1's rate at, say, β=3, α=2 is T^{−2/3}, which is faster than the lower bound T^{−1/3}, proving the proof of Theorem 4.1 cannot be correct. Resolving this exponent directly determines whether the central claim survives.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central optimality claim is internally inconsistent. Theorem 4.1 (Eq. 4) and Corollary 4.2 give, for β ≥ α, excess risk ≲ (σ²+1)/T^{1−1/β} = (σ²+1)/T^{(β−1)/β}, assuming the approximation term 1/M^{β−1} is negligible. Remark 4.4 states that the information-theoretic lower bound is Ω(T^{−1/β}) and is agnostic to parametrization and algorithm. For every β > 2, (β−1)/β > 1/β, so the upper bound is strictly faster than the quoted minimax rate. Since the lower bound is claimed to apply to all algorithms, the two displayed statements cannot both be true for β > 2. This is not a matter of differing constants or polylogarithmic factors: the polynomial exponents contradict. Consequently, either the proof of Theorem 4.1 (specifically the Phase II linear approximation leading to the bias term D/T + 1/D^{β−1}) contains an error, or the lower bound quoted in Remark 4.4 is misstated or misapplied. The paper's headline result—that SGD with the quadratic parameterization 'hits the information-theoretic lower bound' in the α≤β regime—therefore rests on an unresolved internal contradiction that must be fixed before the rates can be trusted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies SGD for a quadratically parameterized linear regression model f(x)=<x,v^{\\odot 2}> under infinite-dimensional Gaussian covariates whose covariance eigenvalues decay as \\lambda_i\\asymp i^{-\\alpha} and whose ground truth satisfies \\lambda_i(v^*_i)^4\\asymp i^{-\\beta}. It proposes a two-phase analysis of SGD with a warm-up plus tail-geometric step-size schedule, proving an upper bound on the last-iterate excess risk in Theorem 4.1 with an effective dimension D, and deriving Corollaries 4.2 and 4.3 for the large- and small-model regimes. The paper claims that when \\alpha\\le\\beta the quadratic model achieves the information-theoretic rate and that when \\alpha>\\beta it strictly outperforms the linear-SGD rate quoted from prior work. An algorithmic lower bound matching the upper bound is stated in Appendix B, and simulations are provided in Appendix D.","tokens_in":48207,"tokens_out":14866,"duration_ms":153990,"significance":"If the proof is correct, the result is valuable: it gives a nontrivial two-phase convergence analysis for a simple feature-learning model with anisotropic spectra, and it provides a concrete rate separation between linear and quadratically parameterized SGD. The appendix contains explicit coupling constructions, submartingale/supermartingale arguments, and a matching algorithmic lower bound, which are substantive technical contributions. However, the central optimality claim is currently undermined by an internal contradiction between the paper's own upper bound and the information-theoretic lower bound quoted in Remark 4.4, so the rates cannot be accepted as stated without revision.","major_comments":[{"comment":"There is a direct internal contradiction in the claimed optimality. For \\beta\\ge\\alpha, Corollary 4.2 and Theorem 4.1 give excess risk \\tilde{O}((\\sigma^2+1)/T^{(\\beta-1)/\\beta}), while Remark 4.4 quotes the information-theoretic lower bound as T^{-1/\\beta} for any algorithm. For every \\beta>2, (\\beta-1)/\\beta>1/\\beta, so the upper bound is polynomially faster than the quoted lower bound; this cannot be reconciled by constants or logarithmic factors. Since the same remark concludes that SGD 'hits the lower bound' in the \\alpha\\le\\beta regime, either the proof of Theorem 4.1 contains an error in the Phase II bias/variance decomposition or the lower bound quoted in Remark 4.4 is misstated or misapplied. The authors must correct one of these statements and then re-derive the optimality and separation conclusions.","section":"§4, Remark 4.4 and Corollary 4.2"},{"comment":"The algorithmic lower bound in Theorem B.1 has the same polynomial shape as the upper bound, namely 1/M^{\\beta-1}+\\bar{\\sigma}^2D/T+D^{-(\\beta-1)}\\mathbf{1}_{M>D}. When D\\asymp T^{1/\\beta}, this yields \\Omega(T^{-(\\beta-1)/\\beta}), which is the exponent of the paper's own upper bound, not the T^{-1/\\beta} quoted in Remark 4.4. Therefore this appendix cannot validate the claim that the upper bound hits the information-theoretic lower bound. The manuscript needs to distinguish clearly between the algorithmic lower bound, which matches the SGD trajectory analysis, and the minimax/information-theoretic lower bound, and it needs to identify which evidence supports the optimality assertion in the \\alpha\\le\\beta regime.","section":"Appendix B, Theorem B.1"},{"comment":"The entire probabilistic engine relies on Assumption 3.1 [A1]: the covariates are independent Gaussian coordinates. Lemmas C.3, C.4, C.9 and the b-capped and neighbor coupling constructions in Appendix A use Gaussian fourth moments and coordinate-wise independence. No result is proved for correlated or non-Gaussian covariates, despite the broad framing in the Introduction and Abstract about 'feature learning' and 'scaling law'. This is not by itself an error, because the theorem states the assumption explicitly, but the scope limitation should be stated as prominently as the rate results, and Remark 3.2 should not imply that the extension is routine.","section":"§3.3 and Appendix C"}],"minor_comments":[{"comment":"The algorithm's initialization v_0=\\Omega(\\min\\{1,M^{-(\\beta-\\alpha)/4}\\})\\mathbf{1}_M and the step size \\eta\\asymp D^{\\min\\{0,(\\alpha-\\beta)/4\\}} depend on the unknown exponents \\alpha,\\beta and on D. The text should qualify statements such as 'automatically adapt' and 'without explicitly selecting D' so that readers understand the adaptation is along the trajectory, not parameter-free.","section":"Algorithm 1 and Theorem 4.1"},{"comment":"The displayed condition 'h>\\lceil(T-h)/\\log(T-h)\\rceil' in Theorem B.1 is inconsistent with the earlier definitions h=\\lceil T/\\log T\\rceil and T_1=\\lfloor(T-h)/\\log(T-h)\\rfloor; please correct this typo and state the exact relation between h and T_1 used in the lower bound proof.","section":"Appendix B, Theorem B.1"},{"comment":"The simulation figures are visually consistent with the claimed rates, but the text reports no fitted exponents or error bars. Adding fitted slopes with confidence intervals for the quadratic and linear curves would make the empirical support for the scaling-law exponents quantitative.","section":"Appendix D, Simulations"}],"recommendation":"major_revision","confidential_remarks":"The main unresolved issue is the contradiction between Corollary 4.2/Theorem 4.1 and the quoted minimax lower bound in Remark 4.4. If the correct information-theoretic rate is actually T^{-(\\beta-1)/\\beta}, then the upper bound and the algorithmic lower bound are consistent and the paper's contribution survives, but the optimality/superiority discussion must be rewritten. If the correct rate is T^{-1/\\beta}, then the upper bound proof is wrong and the paper cannot be accepted. I recommend that the editor ask the authors to resolve this discrepancy before further review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is a serious theory contribution: it gives the first explicit piecewise scaling-law rates for SGD on a quadratically parameterized linear regression with power-law covariance and decaying ground truth. The two-phase decomposition (adaptation, then estimation) is a real technical step forward over the isotropic quadratic analyses in HaoChen et al. and Woodworth et al. The claimed separation against linear SGD in the α > β regime is concrete, and the algorithmic lower bound in Appendix B is a genuine attempt to show the upper bound is tight for the algorithm. I believe the proof machinery, while dense, is honestly built from the stated assumptions rather than fitted to simulations.\n\nThat said, the main soft spot is the one the stress-test flags. Remark 4.4 quotes an information-theoretic lower bound of T^{-1/β} for all algorithms, while Corollary 4.2 claims an upper bound of T^{-(β-1)/β} when β ≥ α. For β > 2, (β-1)/β > 1/β, so the upper bound is strictly faster than the quoted minimax rate. Both cannot be true. Either the lower bound is misapplied (possibly it refers to a different parameterization, or the prior work's β has a different meaning), or the Phase II bias calculation contains an error. The paper's own algorithmic lower bound matches the upper bound, so the internal consistency is fine, but the contradiction with the external lower bound is unresolved. A referee must ask for a corrected statement.\n\nA secondary limitation is Assumption 3.1: independent Gaussian coordinates. The concentration lemmas (C.3, C.4, C.9) rely on coordinate-wise independence and Gaussian fourth moments; the paper says it may be extendable to low-correlation data but doesn't prove it. For a scaling-law paper, that's a meaningful gap, but not fatal if presented as a starting point.\n\nWho is this for? Learning theorists interested in implicit regularization and feature learning in a tractable non-convex model. It deserves a serious referee: the result is novel, the proofs are detailed, and the conflict with the lower bound is a fixable (but essential) issue, not a fundamental flaw in the overall approach. I would engage with it.\n\nRecommendation: send to peer review, with the expectation of major revision on the exponent conflict.","headline":"Substantial new rates for feature-learning-style SGD, but the quoted minimax bound and the paper's own upper rate contradict in the α≤β regime – that conflict needs to be resolved before the optimality claim stands.","tokens_in":48783,"tokens_out":5149,"would_cite":true,"duration_ms":48856,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","62J05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Quadratic parameterization of linear regression changes SGD's scaling law, yielding strictly faster excess-risk decay than linear SGD when the ground truth opposes the covariance spectrum.","keywords":["scaling law","stochastic gradient descent","quadratic parameterization","feature learning","implicit regularization","spectral decay","excess risk","effective dimension"],"falsifier":"Generate data with the same power-law spectra but with correlated Gaussian covariates (for example, a fixed Toeplitz coupling) or heavy-tailed coordinates, run Algorithm 1, and measure the excess-risk exponent: a rate significantly worse than $\\tilde{O}(T^{-(2\\beta-2)/(\\alpha+\\beta)})$ in the $\\alpha > \\beta$ regime would show the scaling law depends on coordinate-wise independence.","tokens_in":47717,"feed_emoji":"📈","tokens_out":9628,"duration_ms":79295,"temperature":0.7,"pith_summary":"This paper derives a scaling law for stochastic gradient descent on a quadratically parameterized linear regression, where the predictor is $\\langle x, v^{\\odot 2}\\rangle$ and both the covariance spectrum and the ground truth decay as power laws. It establishes an upper bound on the excess risk that is piecewise in the effective dimension $D = \\min\\{T^{1/\\max\\{\\beta,(\\alpha+\\beta)/2\\}}, M\\}$, with approximation, variance, and bias terms. The central finding is a separation: when the ground truth opposes the covariance spectrum ($\\alpha > \\beta$), the quadratic model achieves $\\tilde{O}(T^{-(2\\beta-2)/(\\alpha+\\beta)})$, strictly faster than the best linear SGD rate $\\tilde{O}(T^{-(\\beta-1)/\\alpha})$; when $\\alpha \\le \\beta$, it matches the optimal rate $\\tilde{O}(T^{-(\\beta-1)/\\beta})$. The paper argues the speedup comes from feature learning: coordinates with strong signal are adapted in an initial phase, after which estimation behaves like linear SGD on re-scaled features.","feed_headline":"Quadratic parameterization makes SGD beat linear-model rates","feed_subtitle":"When ground truth opposes the data spectrum, quadratic SGD achieves Õ(T^{-(2β-2)/(α+β)}) excess risk.","key_machinery":"The proof decomposes SGD into two phases. In Phase I (adaptation), the dynamics select an effective dimension $D$ without explicit thresholding: coordinates $1,\\ldots,D$ climb to within a constant factor of $v^*$, while coordinates beyond $D$ stay bounded by a constant multiple of $v^*$. This is shown through a b-capped coupling sequence and coordinate-wise sub-Gaussian supermartingales. In Phase II (estimation), iterates remain confined near $v^*$, and the update is approximated as linear SGD on reparameterized features $\\Pi_M x \\odot v^*_{1:M}$, whose per-coordinate rescaling by $v^*$ accelerates bias decay. The geometrically decaying step size and an auxiliary truncated sequence carry the linear-regression analysis through the nonlinear phase.","core_discovery":"The paper's central claim is that the quadratic parameterization itself acts as an implicit regularizer that adapts per-coordinate learning rates, and this adaptation changes the SGD scaling law. Concretely, with eigenvalues $\\lambda_i \\asymp i^{-\\alpha}$ and ground-truth alignment $\\lambda_i (v^*_i)^4 \\asymp i^{-\\beta}$, the last-iterate excess risk of SGD with a warm-up constant step size followed by geometric decay is at most $$R_M(v_T) - \\mathbb{E}[\\$xi^{2}$] \\lesssim $M^{{-(\\beta-1)}}$ + \\frac{\\$sigma^{2}$ D}{T} + \\frac{D}{T} + $D^{{-(\\beta-1)}}$ \\mathbf{1}_{D<M},$$ with $D = \\min\\{T^{1/\\max\\{\\beta,(\\alpha+\\beta)/2\\}}, M\\}$. In the large-model regime this yields $\\tilde{O}(T^{-(\\beta-1)/\\beta})$ when $\\beta \\ge \\alpha$ and $\\tilde{O}(T^{-(2\\beta-2)/(\\alpha+\\beta)})$ when $\\alpha > \\beta$. The $\\alpha > \\beta$ rate is strictly faster than the best rate the paper quotes for linear SGD, $\\tilde{O}(T^{-(\\beta-1)/\\alpha})$. The paper also proves a matching algorithmic lower bound for this SGD algorithm, showing the rate is intrinsic to the method, and notes that both quadratic and linear SGD miss the information-theoretic bound when $\\alpha > \\beta$.","pith_inferences":["Extension — If the two-phase mechanism is generic, other positive-homogeneous parameterizations (for example cubing or matrix factorization) should show a similar acceleration with exponents set by the degree of the parameterization; this is directly testable in the paper's synthetic setup.","Extension — The effective dimension $D$ emerges from the dynamics rather than from an explicit threshold, suggesting a principled early-stopping proxy: stop once the learned coordinates have plateaued near their $v^*$-neighborhoods; the paper does not explore this.","Extension — The algorithmic lower bound's slow-ascent argument implies the gap to the information-theoretic bound in the $\\alpha > \\beta$ regime is an optimization artifact, so preconditioned or momentum variants of SGD might close part of that gap.","Extension — The compute-optimal allocation implies that in opposed-spectrum problems data, not model size, is the bottleneck; practitioners should favor more samples over wider models in such regimes."],"forward_implications":["In the aligned regime $\\beta \\ge \\alpha$, quadratic SGD reaches the same optimal rate as linear SGD, so feature learning does not degrade worst-case scaling.","In the opposed regime $\\alpha > \\beta$, the quadratic model's rate $\\tilde{O}(T^{-(2\\beta-2)/(\\alpha+\\beta)})$ is strictly faster than the linear rate $\\tilde{O}(T^{-(\\beta-1)/\\alpha})$, yielding an explicit separation between models with and without feature learning.","The excess risk is governed by $D = \\min\\{T^{1/\\max\\{\\beta,(\\alpha+\\beta)/2\\}}, M\\}$: for fixed $T$, adding parameters helps only until $D$ saturates, after which the approximation term $M^{-(\\beta-1)}$ dominates.","For a compute budget $B=MT$, the optimal allocation follows $M \\asymp B^{1/(1+\\beta)}$, $T \\asymp B^{\\beta/(1+\\beta)}$ when $\\beta \\ge \\alpha$, and $M \\asymp B^{1/(1+(\\alpha+\\beta)/2)}$, $T \\asymp B^{(\\alpha+\\beta)/2/(1+(\\alpha+\\beta)/2)}$ when $\\alpha > \\beta$.","The matching algorithmic lower bound implies the quoted rates are intrinsic to this SGD algorithm, and in the $\\alpha > \\beta$ regime the algorithm remains above the information-theoretic bound."],"supporting_citations":[{"why":"Supplies the last-iterate risk bounds for linear SGD with decaying step sizes and the geometric decay schedule that Algorithm 1 adopts.","marker":"Wu et al. (2022)"},{"why":"Provides the optimal linear-SGD rate and the information-theoretic lower bound that the quadratic model is compared against.","marker":"Zhang, Liu, et al. (2024)"},{"why":"Prior analysis of the quadratic model under isotropic data; this paper extends the setting to anisotropic covariance and decaying ground truth.","marker":"HaoChen et al. (2021)"},{"why":"Establishes the near-optimality of geometrically decaying step-size schedules for least squares, motivating the two-stage schedule.","marker":"Ge et al. (2019)"},{"why":"Linear-regression scaling laws with sketched covariates and power-law spectra, the direct baseline for the model-size and data-size comparison.","marker":"L. Lin et al. (2024)"},{"why":"Motivates the power-law spectral and source-condition assumptions from empirical neural scaling laws.","marker":"Bahri et al. (2024)"},{"why":"Identifies rich versus kernel regimes and the implicit bias of quadratic parameterization.","marker":"Woodworth et al. (2020)"},{"why":"Shows quadratic parameterization enables sparse recovery, a prior example of its implicit regularization.","marker":"Vaskevicius et al. (2019)"}],"fun_headline_variants":["Quadratic features let SGD outpace linear-model scaling law","Implicit regularization from quadratic parameterization speeds SGD","SGD learns features automatically in quadratically parameterized regression","Quadratic parameterization improves SGD scaling law beyond linear rates","Last-iterate SGD error beats linear-model bound via quadratic features"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the infinitely many covariates are independent Gaussians with variances $\\lambda_i$; if covariates are correlated or non-Gaussian, the concentration estimates and the two-phase decomposition in the proof no longer go through.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic features let SGD outpace linear-model scaling law","Implicit regularization from quadratic parameterization speeds SGD","SGD learns features automatically in quadratically parameterized regression","Quadratic parameterization improves SGD scaling law beyond linear rates","Last-iterate SGD error beats linear-model bound via quadratic features"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000913,"raw_usage":{"total_tokens":3987,"prompt_tokens":1075,"completion_tokens":2912,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":691,"completion_tokens_details":{"reasoning_tokens":2831}},"tokens_in":691,"tokens_out":2912,"duration_ms":20056,"temperature":1.0,"reasoning_tokens":2831,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T22:37:18.186709+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate data with the same power-law spectra but with correlated Gaussian covariates (for example, a fixed Toeplitz coupling) or heavy-tailed coordinates, run Algorithm 1, and measure the excess-risk exponent: a rate significantly worse than $\\tilde{O}(T^{-(2\\beta-2)/(\\alpha+\\beta)})$ in the $\\alpha > \\beta$ regime would show the scaling law depends on coordinate-wise independence.","supporting_citations":[{"cited_title":"Z., Wei, C., Lee, J., & Ma, T","cited_arxiv_id":null,"evidence_quote":"Prior analysis of the quadratic model under isotropic data; this paper extends the setting to anisotropic covariance and decaying ground truth."},{"cited_title":"M., Bartlett, P., & Lee, J","cited_arxiv_id":null,"evidence_quote":"Linear-regression scaling laws with sketched covariates and power-law spectra, the direct baseline for the model-size and data-size comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates the power-law spectral and source-condition assumptions from empirical neural scaling laws."},{"cited_title":"D., Moroshko, E., Savarese, P., Golan, I.,","cited_arxiv_id":null,"evidence_quote":"Identifies rich versus kernel regimes and the implicit bias of quadratic parameterization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows quadratic parameterization enables sparse recovery, a prior example of its implicit regularization."}],"review_version":1}