{"id":"4142a5f0-0307-4e14-b56b-7db6b2b0b7a7","arxiv_id":"2506.16283","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Under source conditions with smoothness r>0 and capacity 2r+b>1, random features achieve minimax-optimal rates for any spectral regularization method with qualification at least r∨1.","lead":"This paper proves that random features preserve optimal learning rates for a broad family of kernel algorithms, not just kernel ridge regression. It matters because it gives theoretical cover for using random features and neural tangent kernels in large-scale learning and for analyzing neural operators.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem is sound within its stated easy-regime assumptions, but the conclusion overstates scope by claiming 'arbitrary r>0' when the proof requires 2r+b>1 and the theorem statement omits boundary values r=1/2 and r=1.","rationale":"I read the main theorem as conditional on Assumptions 3.1-3.4. The proof is a standard bias-variance decomposition with concentration arguments from Tropp and Caponnetto-De Vito, and the algebra in Propositions A.2 and A.16 is coherent in the easy regime. The hard-regime failure is not an internal inconsistency: the paper explicitly leaves 2r+b≤1 open. It is, however, the load-bearing limit of the advertised generality, because the theorem's rate and M scaling are not proven there. The reader's weakest assumption identifies exactly this condition, and I agree it is the least secure part of the central claim, though I do not regard it as a fatal flaw. The omitted boundary values r=1/2 and r=1 are also genuine statement-level gaps; the surrounding proof suggests they can be covered, but Theorem 3.5 as written does not apply at those points. These considerations support keeping the reader's CONDITIONAL verdict without changing it.","tokens_in":31737,"tokens_out":22841,"duration_ms":239212,"concrete_test":"Analytic check: in the proof of Theorem 3.5, substitute λ = C n^{-1/(2r+b)} log^3(2/δ) into the lower-bound condition n ≥ c(log(λ^{-1})/λ + λ^{-(2r+b)}) and show that the inequality is unsatisfiable for large n when 2r+b≤1; this settles the scope limit. Separately, rerun Proposition A.16 at r=1/2 and r=1, recording the required M exponent in each case, and amend Theorem 3.5 to cover the boundary values if the closed-interval proof is valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3.5 closes only when the lower bound n ≥ c(log(λ^{-1})/λ + λ^{-(2r+b)}) from Proposition A.2 is compatible with λ = C n^{-1/(2r+b)} log^3(2/δ). Substituting λ forces n ≥ c n^{1/(2r+b)} log^3(2/δ), which cannot hold as n→∞ when 2r+b≤1; the strict form n ≥ n0 with n0 = e^{(2r+b)/(2r+b-1)} requires 2r+b>1. Thus the bias-variance balance of Propositions A.1-A.3 is established only in the easy-learning regime. This is explicitly stated in Assumption 3.4, so it is not a hidden invalidity, but the conclusion's phrase 'minimax-optimal rates for arbitrary smoothness r > 0' is too strong without the qualifier 2r+b>1: for any b<1 there are values r≤(1-b)/2 that are excluded. In addition, Theorem 3.5's piecewise M condition is silent at r=1/2 and r=1; the proof cases in Proposition A.16 cover the closed intervals, so the statement should either include these boundaries or explicitly defer them to a corollary. These are scope and boundary issues rather than errors in the main argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies random feature (RF) approximation for a broad class of spectral regularization methods in vector-valued kernel regression. Under a source condition gρ = L∞^r h, an effective-dimension bound N(λ) ≤ cb λ^{-b}, and the easy-learning restriction 2r+b>1, the main theorem (Theorem 3.5) shows that with λ = C n^{-1/(2r+b)} log^3(2/δ) and M of order log(n) times a piecewise power of n, the excess risk satisfies O(n^{-r/(2r+b)} polylog(1/δ)) for any spectral method with qualification ν ≥ r∨1. The framework covers Tikhonov regularization, gradient descent, Heavy-Ball, and Nesterov acceleration, and the authors apply it to neural networks and neural operators via the neural tangent kernel. The appendix supplies a detailed bias-variance proof with operator concentration inequalities, and numerical experiments on NTK random features illustrate the predicted M = O(√n) regime.","tokens_in":32019,"tokens_out":7382,"duration_ms":79128,"significance":"If the main result is correct, it is a useful extension of random-feature theory: previous sharp guarantees were largely limited to kernel ridge regression, whereas this paper covers general spectral filtering methods and vector-valued kernels, including NTK-type kernels. The proof strategy is standard but self-contained, with explicit constants and a clean bias-variance decomposition; the statement that M = O(√n log n) suffices to preserve the underlying spectral method's optimal rate is concrete and testable. The main caveat is that the result is restricted to the easy-learning regime 2r+b>1, which is explicit in Assumption 3.4 but is not always reflected in the paper's broader claims. The boundary values r=1/2 and r=1 are omitted from the theorem statement despite being covered by the proof.","major_comments":[{"comment":"The piecewise condition on M uses the open intervals r ∈ (0,1/2), r ∈ (1/2,1), and r ∈ (1,∞), thereby omitting r=1/2 and r=1. This is not purely cosmetic: Proposition A.16 proves closed-interval cases (\"CASE (r ≤ 1/2)\", \"CASE (r ∈ [1/2,1])\", \"CASE (r ≥ 1)\"), and at r=1 the second branch gives M of order n^{(1+b)/(2+b)} while the third branch gives n^{2/(2+b)}, which are different unless b=1. The theorem statement should therefore use closed or half-open intervals, e.g., r ∈ (0,1/2], r ∈ (1/2,1], and r ∈ (1,∞), or explicitly defer the boundary cases to a corollary. Since the appendix proof already covers these values, this is a statement-completeness issue rather than a flaw in the derivation.","section":"Theorem 3.5 (Section 3.1)"},{"comment":"The conclusion states that the framework \"yields minimax-optimal rates for arbitrary smoothness r > 0\", but Assumption 3.4 requires 2r+b>1. For any b<1 there are values r ≤ (1-b)/2 that are excluded, so the qualifier \"with 2r+b>1\" must appear in every summary claim, including the abstract's statement about \"optimal learning rates over regularity classes\". The proof explicitly relies on this condition to make the lower bound n ≥ n0 = exp((2r+b)/(2r+b-1)) consistent with λ = C n^{-1/(2r+b)} log^3(2/δ); the condition is not an artifact. I recommend replacing \"arbitrary smoothness r > 0\" with \"arbitrary r > 0 satisfying 2r+b>1\".","section":"Assumption 3.4 and Conclusion (Section 3.1, Section 6)"}],"minor_comments":[{"comment":"The sentence \"The case b = 1 is refereed as the capacity independent case\" contains a typo: \"refereed\" should be \"referred\".","section":"Section 3.1"},{"comment":"\"Mercers theorem\" should be \"Mercer's theorem\".","section":"Appendix A.2, Propositions A.2 and A.3"},{"comment":"The theorem heading \"Theorem 4.2 (Nguyen and Mücke (2024) (Theorem 3.5.))\" has mismatched parentheses and a stray period; please clean up the citation formatting.","section":"Theorem 4.2 (Section 4.3)"},{"comment":"The norms such as ∥GθT − gρ∥L2ρu are written without parentheses around the measure; writing L2(ρu) and L2(µx) consistently would improve readability.","section":"Section 4.3"},{"comment":"The notation φ(i)(x, ωm) is used in the display but the random variables ωm are defined only in surrounding text; consider explicitly writing φ(i)_m(x) = φ(i)(x, ω_m) before Eq. (2.6) to avoid ambiguity with the sum index i.","section":"Section 2.1, Eq. (2.6)"}],"recommendation":"minor_revision","confidential_remarks":"The paper's reliance on the authors' earlier neural-operator theorem (Nguyen and Mücke 2024) is an application, not circular reasoning, so I see no novelty-disclosure concern. The main caveat is purely the scope wording and the boundary-value omission in Theorem 3.5; both are locally fixable and do not undermine the central derivation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers what it says on the box: it proves that random feature approximation does not degrade the minimax rate of a broad class of spectral regularization methods, including gradient descent, Heavy-Ball, and Nesterov, for vector-valued kernels. The machinery is standard—bias-variance decomposition plus operator concentration—but the extension is real. Previous work was pinned to KRR; this unifies it and covers source conditions r<1/2 in the easy regime. The proofs in the appendix are detailed and I didn't find a fatal gap.\n\nThe main theorem is sound within Assumptions 3.1–3.4. The bias-variance balance is established only when 2r+b>1, and the paper says so in Assumption 3.4 and in the discussion. What's less careful is the abstract and conclusion saying 'optimal rates for arbitrary smoothness r>0' without the qualifier. For b<1 there are positive r values excluded. That's a framing issue, not a hidden flaw.\n\nTwo smaller things. First, the piecewise M condition in Theorem 3.5 uses open intervals that omit r=1/2 and r=1, while the proof's Proposition A.16 covers the closed intervals; the statement should include the boundaries or defer them to a corollary. Second, the neural operator application leans on the authors' companion paper for the Taylor error and parameter bounds, which is fine, but it is not self-contained. The numerical experiment is illustrative: no code, no error bars, no data release. Minor.\n\nOverall: a solid, carefully written paper. People working on random features, spectral filtering, or NTK-based operator learning will get value from it. I'd send it out. The core result stands; the boundary and framing fixes are easy.","headline":"Sound generalization of random-feature rates to spectral methods, with an overbroad 'arbitrary r>0' claim and minor boundary omissions.","tokens_in":32568,"tokens_out":1485,"would_cite":true,"duration_ms":14588,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","62G08","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random feature approximation does not degrade the minimax learning rate of any spectral regularization method.","keywords":["random feature approximation","spectral regularization methods","kernel ridge regression","learning rates","effective dimension","neural tangent kernel","neural operators","gradient descent"],"falsifier":"Take a kernel whose eigenvalues decay like $\\mu_i\\sim i^{-1/b}$ with $b=1/2$ (so $N_{L_\\infty}(\\lambda)\\sim \\lambda^{-1/2}$) and a target $g_\\rho=L_\\infty^r h$ with $r=0.3$, giving $2r+b=1.1$. Choose $\\lambda\\sim n^{-1/1.1}$ and $M=\\sqrt{n}\\log n$ as in Theorem 3.5; if, for large $n$, the excess risk $\\|g_\\rho-S_M f^M_\\lambda\\|_{L^2(\\rho_x)}$ fails to decay like $n^{-0.3/1.1}$ with high probability, the theorem's bound is violated.","tokens_in":31534,"feed_emoji":"🎲","tokens_out":11920,"duration_ms":118594,"temperature":0.7,"pith_summary":"Random feature approximations replace an expensive kernel by a finite random sum, and this paper asks whether that substitution costs anything in statistical accuracy. The answer, under a smoothness condition and a kernel-capacity bound, is no: for any spectral regularization method, the random-feature estimator reaches the same minimax-optimal rate $n^{-r/(2r+b)}$ as the exact kernel method, with high probability. The price is only the number of random features, which in the well-specified case scales as $O(\\sqrt{n}\\log n)$. This matters because it certifies that cheap large-scale kernel algorithms, including neural tangent kernel models and neural operators, can retain optimal accuracy while using random features.","feed_headline":"Random features keep the optimal learning rate for kernel methods","feed_subtitle":"One theorem covers kernel ridge, gradient descent, Heavy-Ball and Nesterov with O(√n log n) random features.","key_machinery":"The load-bearing object is the spectral-filter estimator $$f^M_\\$\\lambda$=\\phi_\\$\\lambda$(\\hat\\Sigma_M)\\hat S^*_M y,$$ where $\\phi_\\lambda$ is a regularization function acting on the empirical covariance operator $\\hat\\Sigma_M$ of the random-feature kernel $K_M$, and $\\hat S^*_M$ is the empirical sampling operator. The proof splits the excess risk into a bias term, controlled by the qualification $\\nu$ of $\\phi_\\lambda$ together with the source condition $g_\\rho=L_\\infty^r h$, and a variance term, controlled by operator concentration: $\\hat\\Sigma_M$ concentrates around $\\Sigma_M$ in the random-feature Hilbert space, and the random-feature kernel operator $L_M$ concentrates around $L_\\infty$ in the ambient space. The effective dimension $N_{L_\\infty}(\\lambda)=\\operatorname{tr}(L_\\infty(L_\\infty+\\lambda I)^{-1})\\le c_b\\lambda^{-b}$ is what converts these concentration bounds into the stated feature-count thresholds $M$.","core_discovery":"The paper's central claim is Theorem 3.5. Suppose the kernel admits an integral representation $$K_\\infty(x,\\tilde x)=\\sum_{i=1}^p\\int_\\$\\Omega$ \\$varphi^{{(i)}}$(x,\\omega)\\otimes \\$varphi^{{(i)}}$(\\tilde x,\\omega)\\,d\\pi(\\omega),$$ the regression function satisfies the source condition $g_\\rho=L_\\infty^r h$ with $\\|h\\|_{L^2(\\rho_x)}\\le R$, and the kernel integral operator satisfies the effective-dimension bound $N_{L_\\infty}(\\lambda)\\le c_b\\lambda^{-b}$ with $2r+b>1$. Then, for any spectral regularization method with qualification $\\nu\\ge r\\vee 1$, choosing $$\\$\\lambda$=C $n^{{-1/(2r+b)}}$\\$log^{3}$(2/\\delta)$$ and $M\\ge \\tilde C\\log(n)$ times $n^{1/(2r+b)}$ for $r<1/2$, $n^{[1+b(2r-1)]/(2r+b)}$ for $1/2<r<1$, and $n^{2r/(2r+b)}$ for $r>1$, yields $$\\|g_\\rho-S_M f^M_\\$\\lambda$\\|_{$L^{2}$(\\rho_x)}\\le \\bar C\\, $n^{{-r/(2r+b)}}$\\$log^{{3r+1}}$(1/\\delta)$$ with probability at least $1-\\delta$. In words, random features do not degrade the minimax-optimal rate of the underlying spectral algorithm; they only set a feature-count threshold that must be crossed.","pith_inferences":["Beyond the paper, a plausible next step is that the logarithmic factor in the feature count is removable, as it was for kernel ridge regression, so $M=O(\\sqrt{n})$ would suffice for all spectral methods; the paper does not prove this.","Since Assumptions 3.3 and 3.4 exclude the hard-problem regime $2r+b\\le 1$, a concrete test is whether lowering $r$ or $b$ forces a larger feature count, for instance $M\\asymp n^{1/(2r+b)}$, to keep any optimal rate; the paper only establishes the easy-regime balance.","The same operator-concentration argument could be re-run for data-dependent sketches or Nyström approximations, suggesting that the $O(\\sqrt{n}\\log n)$ threshold may be a general property of kernel approximations rather than a special fact about random features."],"forward_implications":["Kernel ridge regression, gradient descent, Heavy-Ball, and Nesterov all attain the minimax rate with only $M=O(\\sqrt{n}\\log n)$ random features in the well-specified case, so no method in this class loses statistical efficiency to random features.","Smoothness classes with $r<1/2$ that lie outside the reproducing kernel Hilbert space are covered whenever $2r+b>1$, removing the saturation limitation that blocked earlier random-feature analyses of kernel ridge regression.","For smoother targets, the optimal rate needs fewer iterations but more random features: $T=O(n^{1/(2r+b)})$ and $M=O(n^{2r/(2r+b)}\\log n)$ for $r\\ge 1$.","Because the framework accepts finite sums of integral kernels, it covers neural tangent kernels and yields optimal $n_U^{-r/(2r+b)}$ rates for two-layer neural operators trained by gradient descent, provided the network width and the second-stage sample count are large enough.","The result unifies and extends the previously KRR-only random-feature guarantees to the whole class of spectral methods, closing the algorithmic gap between theory and practice for random-feature kernel models."],"supporting_citations":[{"why":"Supplies the random-feature concentration machinery and the earlier KRR feature-count benchmark $O(\\sqrt{n}\\log n)$ that this paper generalizes.","marker":"Rudi and Rosasco (2016)"},{"why":"Gives vector-valued random feature bounds with $M=O(\\sqrt{n})$, the sharp comparison point for whether the logarithmic factor is removable.","marker":"Lanthaler and Nelsen (2023)"},{"why":"Provides the spectral regularization framework and qualification conditions that define the method class analyzed here.","marker":"Blanchard and Mücke (2017)"},{"why":"Introduces the source-condition and effective-dimension setup underlying Assumptions 3.3 and 3.4, plus the minimax benchmark.","marker":"Caponnetto and De Vito (2007)"},{"why":"Shows that Heavy-Ball and Nesterov iterations are spectral filtering methods with explicit qualification, enabling their inclusion.","marker":"Pagliana and Rosasco (2019)"},{"why":"Provides operator concentration inequalities for sums of random operators used to control the covariance and feature errors.","marker":"Lin and Cevher (2018)"},{"why":"Supplies the matrix tail bounds underlying the concentration events in Appendix A.3.","marker":"Tropp (2011)"},{"why":"Establishes the neural-operator NTK construction and the approximation-error estimates used in the neural operator application.","marker":"Nguyen and Mücke (2024)"}],"fun_headline_variants":["Random features don't hurt optimal rates for spectral methods","Optimal rates preserved with random features for many kernel methods","Random features match exact kernel rates for broad spectral class","Random features keep minimax rates for gradient descent and more","Feature approximation preserves optimal learning for spectral algorithms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the 'easy learning' assumption that the smoothness parameter $r$ and the kernel-capacity parameter $b$ satisfy $2r+b>1$; when $2r+b\\le 1$, the bias-variance balance that produces the rate $n^{-r/(2r+b)}$ is not proved, so the theorem's feature count and rate are unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Random features don't hurt optimal rates for spectral methods","Optimal rates preserved with random features for many kernel methods","Random features match exact kernel rates for broad spectral class","Random features keep minimax rates for gradient descent and more","Feature approximation preserves optimal learning for spectral algorithms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00045,"raw_usage":{"total_tokens":2299,"prompt_tokens":1008,"completion_tokens":1291,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":624,"completion_tokens_details":{"reasoning_tokens":1215}},"tokens_in":624,"tokens_out":1291,"duration_ms":9863,"temperature":1.0,"reasoning_tokens":1215,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T23:45:45.715361+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a kernel whose eigenvalues decay like $\\mu_i\\sim i^{-1/b}$ with $b=1/2$ (so $N_{L_\\infty}(\\lambda)\\sim \\lambda^{-1/2}$) and a target $g_\\rho=L_\\infty^r h$ with $r=0.3$, giving $2r+b=1.1$. Choose $\\lambda\\sim n^{-1/1.1}$ and $M=\\sqrt{n}\\log n$ as in Theorem 3.5; if, for large $n$, the excess risk $\\|g_\\rho-S_M f^M_\\lambda\\|_{L^2(\\rho_x)}$ fails to decay like $n^{-0.3/1.1}$ with high probability, the theorem's bound is violated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives vector-valued random feature bounds with $M=O(\\sqrt{n})$, the sharp comparison point for whether the logarithmic factor is removable."},{"cited_title":"Optimal rates for regularization of statistical inverse learning problems","cited_arxiv_id":null,"evidence_quote":"Provides the spectral regularization framework and qualification conditions that define the method class analyzed here."},{"cited_title":"Implicit regularization of accelerated methods in hilbert spaces","cited_arxiv_id":null,"evidence_quote":"Shows that Heavy-Ball and Nesterov iterations are spectral filtering methods with explicit qualification, enabling their inclusion."},{"cited_title":"Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms","cited_arxiv_id":"1801.07226","evidence_quote":"Provides operator concentration inequalities for sums of random operators used to control the covariance and feature errors."}],"review_version":1}