{"id":"6f14033b-7279-4f70-97f8-4e30421b3876","arxiv_id":"2505.10423","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Distribution-free learnability by bounded-precision mini-batch SGD implies approximability by a polynomial number of random features, up to a new complexity measure called average probabilistic dimension complexity.","lead":"This paper claims that any function class learnable by distribution-free mini-batch gradient descent can also be approximated by a polynomial-sized combination of random features, a limitation result for distribution-free learning. It also introduces a new complexity measure, average probabilistic dimension complexity, and claims an infinite separation from standard dimension complexity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 4.1 constructs the embedding distribution E after conditioning on the target f, so it establishes only ∀f∃E_f, not the ∃E required by adc; the main theorem's quantifier order is unsupported.","rationale":"The reader's weakest_assumption identifies the same load-bearing flaw: the proof of Theorem 4.1 produces an embedding distribution that depends on the target function, while the adc definition requires a single distribution before sampling the target. I reconstructed the quantifier chain from Lemma A.4 through the boosting argument in Appendix A.3 and confirmed that the ρ_i used to define E are chosen adaptively by AdaBoost based on the target's labels. Thus the proof establishes the weaker statement 'for most f, there exists E_f', not the required 'there exists E such that for most f'. This is not a stylistic quantifier preference; it breaks the distribution-free interpretation of the main theorem, because using E_f would require knowing f. I also note the second issue raised by the reader: Theorem D.6 is a uniform-distribution bound, but Lemma A.3 needs correlation under an arbitrary product distribution (μ,ρ); no distributional analogue is stated or proved. Both issues independently undermine the formal proof. The paper's conceptual message may survive in a weakened per-function or per-distribution form, and the adc definition and separation results are valuable enough to warrant a revised version, but as written the central formal claim is unsupported. Since the reader's REJECT verdict already reflects this, no adjustment is needed.","tokens_in":20145,"tokens_out":8166,"duration_ms":84585,"concrete_test":"Analytic check: take F={f_1,f_2} with μ uniform and write out the AdaBoost query distributions ρ_1,ρ_2,... in the proof of Theorem 4.1 when the target is f_1 versus f_2. Since AdaBoost reweights examples by the weak learners' errors on the target, the two sequences (and hence the embedding distributions E_{f_1} and E_{f_2}) will in general differ. Then verify whether any single E can be defined without conditioning on the target: attempt to sample from E using only μ and ρ, not the labels of the hidden f. If every admissible definition of E in Appendix A.3 requires oracle access to f to choose the ρ_i, the ∃E quantifier is unproven and the theorem needs a uniform version of Lemma A.4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main theorem (Theorem 3.3) concludes adc_{ε,δ}(μ) ≤ poly(Tp/c^2), i.e. there exists a single distribution E over embeddings such that Pr_{h∼μ}[∀ρ: E_{φ∼E}[inf_w L_01] ≤ ε] ≥ 1−δ. The proof goes through Theorem 4.1, whose proof appears in Appendix A. The Random Feature lemma (Lemma A.4) has the quantifier order: with probability ≥1−δ over f∼μ, for every ρ there exists μ_feat_ρ such that a sample from μ_feat_ρ is a γ-weak approximator for that particular f under ρ. It does not assert a single μ_feat_ρ that is good for all f in the high-probability set. In Appendix A.3, the embedding distribution E is then defined as: sample f'_1,...,f'_d from μ_feat_{ρ_1},...,μ_feat_{ρ_d} for the successive distributions ρ_i chosen by AdaBoost. Those ρ_i are the reweighted example distributions produced by boosting a weak learner for the unknown target f; they depend on f through the weak learners' error pattern on f. Hence the resulting E is actually E_f, a distribution that depends on the target. The proof establishes 'for most f, ∃E_f such that ...', which is the reverse quantifier order from adc. The gap is load-bearing because without a single E independent of h, the reduction to random-feature linear learning is not distribution-free: the embedding distribution would need to know which target is being learned. A secondary independent gap is that Theorem D.6's 2-party-norm bound is stated for the uniform distribution, while Lemma A.3's correlation is with respect to an arbitrary product distribution (μ,ρ); no distributional version is stated or cited.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims that if a parametric model class is learnable by clipped mini-batch SGD in a distribution-free manner, then for any prior over target functions, most targets can be approximated by a polynomial-sized linear combination of random features. The authors introduce average probabilistic dimension complexity (adc), prove an upper bound on adc in terms of statistical query dimension, and derive an infinite separation between adc and standard dimension complexity. The proof proceeds by converting bSGD to SQ learning, relating SQ dimension to discrepancy and communication complexity, deriving a random-feature weak-approximation lemma, and then using AdaBoost to combine weak random-feature predictors into a strong predictor.","tokens_in":20532,"tokens_out":10571,"duration_ms":108092,"significance":"If the main theorem were established, it would be a conceptually significant result connecting distribution-free gradient-based learning to the limits of random-feature representations, and the adc framework would give a clean average-case complexity measure with an appealing separation corollary. The modular proof strategy is attractive and the introduction of adc is a useful contribution in its own right. However, the proof of the central theorem contains a load-bearing quantifier error and a distributional gap in the use of a communication-complexity bound. These issues mean that the main advertised claim, distribution-free collapse to random features, is not established by the manuscript as written.","major_comments":[{"comment":"The proof of Theorem 4.1 constructs the embedding distribution E after conditioning on the target f. Specifically, the proof samples features from distributions μ_feat_{ρ_1},...,μ_feat_{ρ_d}, where ρ_1,...,ρ_d are the successive example distributions generated by AdaBoost for the target f. These ρ_i depend on f through the weak learners' error patterns, so the construction yields a per-target distribution E_f. The proof therefore establishes, for most f, the existence of a distribution E_f with the stated properties, whereas Definition 3.2 and Theorem 3.3 require a single distribution E such that for most f and every ρ the random-feature linear loss is small. This quantifier shift is load-bearing: without a single E that is independent of the target, the collapse to random-feature learning is not distribution-free.","section":"Appendix A.3 and Definition 3.2"},{"comment":"Even for a fixed good target f, the proof does not establish the universal quantification over ρ that appears in adc. AdaBoost, as used in Theorem A.6, is run for one target distribution ρ and produces a sequence of distributions ρ_1,...,ρ_Z; the random features are then drawn from μ_feat at those distributions. To satisfy the condition 'for all ρ' in Definition 3.2, one would need a single finite feature vector that works for every possible ρ, or an argument that the same features contain weak approximators for the AdaBoost sequences of all ρ simultaneously. The 'pool of Z example distributions' calculation in Appendix A.3 only accounts for the Z distributions of a single run and does not quantify over the infinite set of possible ρ. Consequently, eq. (10) as proven is not the same as the theorem's conclusion.","section":"Appendix A.3, eq. (10)"},{"comment":"Lemma A.4 applies Theorem D.6 to the correlation E_{(f,x)∼(μ,ρ)}[π(f,x)A(f;x)] and concludes that R_2(Eval) is large. However, Theorem D.6 is stated only for x uniformly distributed over {0,1}×{0,1}; no distributional analogue for arbitrary product distributions (μ,ρ) is stated or cited. Since μ and ρ are arbitrary, the bound Cor(f,Π_c) ≤ 2^c R_2(f)^{1/4} does not apply in the way it is used, and this gap also affects the derivation of the Random Feature lemma.","section":"Section A.2 and Theorem D.6"}],"minor_comments":[{"comment":"The notation L_{D_{h,ρ}}(h,⟨w,ϕ⟩) in Definition 3.2 is inconsistent with the notation used elsewhere and should read L_{D_{h,ρ}}(⟨w,ϕ⟩).","section":"Definition 3.2"},{"comment":"The step where 'sampling a string of random bits r and then hard-coding it into Predict_ρ induces a distribution over functions' is under-specified; as written it is easy to read the resulting distribution μ_feat^ρ as depending on the target f, which would make the quantifier issue even more direct.","section":"Lemma A.4 proof"},{"comment":"The symbol D is used both as a random variable for the number of sampled features and as the dimension d in adc, which makes the final Markov step confusing; distinct notation would improve readability.","section":"Appendix A.3"},{"comment":"The statement that 'random parities are well known to be computationally hard to learn using linear combinations of random features' would benefit from a specific citation, since this hardness is used to interpret the main result.","section":"Introduction, Section 1"}],"recommendation":"reject","confidential_remarks":"The core theorem's proof has a quantifier error that appears to be structural rather than a local typo: the constructed embedding distribution depends on the target f, so the claimed distribution-free collapse is not proven. The adc notion and the separation corollary may be salvageable as independent contributions, but the main advertised claim would need to be substantially revised, likely to a weaker per-target statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on 2505.10423. The paper's pitch is attractive: if distribution-free mini-batch SGD learns a class, then most functions in the class can be approximated by polynomially many random features. The new adc measure is a natural relaxation of probabilistic dimension complexity, and the proof route—bSGD to SQ via Abbe et al., SQ dimension to communication, then boosting—is imaginative. The authors also honestly flag the gradient-precision limitation. I want this to be true.\n\nBut I don't think the proof of Theorem 4.1 delivers what the theorem states. The Random Feature lemma (A.4) gives, for each target f and each example distribution ρ, a distribution over features µ_feat_ρ that weakly approximates that f under that ρ. The high-probability set over f can depend on ρ, and µ_feat_ρ depends on both. In Appendix A.3, the embedding distribution E is constructed by sampling from µ_feat_{ρ_i}, where the ρ_i are the successive reweighted distributions chosen by AdaBoost. Those ρ_i depend on the unknown target f through the weak learner's errors on f. So the construction yields, for most f, an E_f that works for all ρ—not a single E that works for most f and all ρ. The adc definition requires the latter. The proof appears to prove the reverse quantifier order: ∀f∃E_f instead of ∃E∀most f. That is exactly the difference between random features chosen after seeing the target and a distribution-free reduction.\n\nThere's a second gap. The argument applies Theorem D.6, the 2-party-norm bound, which is stated for the uniform distribution over inputs, to the non-uniform product distribution (µ,ρ) used in Lemma A.3. No distributional version is provided or cited. This may be fixable, but it's not in the paper.\n\nThese are load-bearing, not cosmetic. Without a single E, the slogan 'distribution-free bSGD collapses to random features' is unsupported. The informal claim might survive in a weaker per-function form, and perhaps the quantifier can be repaired with more work, but the manuscript as written does not establish the main theorem. The separation corollary (Section 3.4) depends on Theorem 4.1, so it is open too.\n\nWho should read this? Learning theorists interested in SQ dimension, random features, and gradient-based learning will find the adc definition and the proof strategy worth engaging with. It deserves a serious referee—the ideas are good enough that the gaps are worth pinning down. But my recommendation to the editor would be: send to review, and expect the referees to push back on the quantifier step; if it can't be fixed, the paper should be rejected, possibly with an invitation to resubmit a corrected version.","headline":"A clever, well-written paper with a genuine new complexity measure, but the proof of the main theorem has a quantifier gap that is load-bearing; the central claim stands on shaky ground.","tokens_in":21050,"tokens_out":5684,"would_cite":false,"duration_ms":53601,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"If a parametric model is distribution-free bSGD-learnable, random features approximate it with polynomially many terms.","keywords":["distribution-free learning","mini-batch stochastic gradient descent","random features","statistical query dimension","average probabilistic dimension complexity","dimension complexity","communication complexity","boosting"],"falsifier":"Find a function class $F$ and a prior $\\mu$ for which a $\\mathrm{bSGD}(T,c,b,p)$ method achieves distribution-free squared loss $1/10$ but, for some $\\rho$, every distribution over $d=\\mathrm{poly}(Tp/c^2)$ random embeddings fails to $0/1$-approximate a $1-\\delta$ mass of $F$; that would refute Theorem 3.3 directly.","tokens_in":19879,"feed_emoji":"🧠","tokens_out":9706,"duration_ms":85816,"temperature":0.7,"pith_summary":"The paper proves that distribution-free mini-batch stochastic gradient descent has a hidden ceiling: if a parametric model class can be learned by bSGD to squared loss $1/10$ for every source distribution formed from any target in $F$ and any example distribution, then for any prior over $F$, most targets can be approximated by a linear combination of polynomially many random features, with the polynomial depending on the number of gradient steps, parameter count, and inverse gradient precision. This is a collapse result: distribution-free SGD learnability implies random-feature approximability. The paper introduces average probabilistic dimension complexity (adc) to state the collapse precisely, and proves adc is polynomially related to statistical query dimension. It then derives an infinite separation between adc and standard dimension complexity, and reads the whole picture as evidence that distributional assumptions are not optional for gradient-based learning.","feed_headline":"Distribution-free SGD collapses to random features","feed_subtitle":"If bSGD learns every distribution, polynomially many random features suffice for most targets—why parity stays hard.","key_machinery":"The machinery is the average probabilistic dimension complexity (adc), the smallest $d$ such that a single distribution over random embeddings lets a linear model reach $0/1$ loss at most $\\varepsilon$ for a $1-\\delta$ fraction of the target class, uniformly over input distributions. The proof is carried by a four-step chain. First, clipped mini-batch SGD with batch size satisfying $bc^2 \\geq \\Omega(\\log Tp/\\delta)$ is simulated by a statistical-query algorithm with $Tp$ queries of tolerance $c/8$. Second, the statistical-query dimension of the sign matrix of $F$ controls the reciprocal of its discrepancy under product distributions, giving a 2-bit communication protocol with correlation $\\Omega(1/\\mathrm{sq}(F)^2)$. Third, a 2-party norm bound converts that correlation into a distribution over weak random-feature predictors that are correct with advantage $\\Omega(1/\\mathrm{sq}(F)^8)$. Fourth, a weak-to-strong boosting algorithm combines $O(\\mathrm{sq}(F)^{16})$ weak predictors into a single linear combination of features, yielding $d \\leq O(\\mathrm{sq}(F)^{24.01})$, which becomes $\\mathrm{poly}(Tp/c^2)$ after the statistical-query dimension bound.","core_discovery":"The central claim, Theorem 3.3, is a collapse theorem. Suppose a $p$-parameter differentiable model is distribution-free bSGD-learnable: there is an algorithm running $T$ clipped mini-batch gradient steps with batch size $b$ and gradient precision $c$ that, for every $f \\in F$ and every example distribution $\\rho$, achieves squared-loss error at most $1/10$. Then for any prior $\\mu$ over $F$ and any small $\\varepsilon,\\delta>0$, there is a distribution over embeddings $\\varphi: X \\to \\mathbb{R}^d$ with $d \\leq \\mathrm{poly}(Tp/c^2)$ such that, with probability at least $1-\\delta$ over $f \\sim \\mu$, and for every $\\rho$, the optimal linear combination of the random features achieves $0/1$ loss at most $\\varepsilon$. In the paper's own measure, this is $\\mathrm{adc}_{\\varepsilon,\\delta}(\\mu) \\leq \\mathrm{poly}(Tp/c^2)$. The proof chain is bSGD to statistical queries, a statistical-query dimension bound, a communication-complexity lemma turning that dimension into weak random-feature predictors, and boosting those weak predictors into a single linear combination.","pith_inferences":["If the uniform-to-product distribution gap can be closed, the same argument likely extends to other stochastic-gradient variants and loss functions, because only the bSGD-to-SQ simulation and the discrepancy/2-party-norm link are used.","The theorem's dependence on gradient precision suggests a phase transition: with very fine gradients, bSGD can simulate PAC learning and the collapse fails, so the 'power of random features' is really a statement about coarse, noisy gradients.","A constructive version of the boosting step would convert a trained distribution-free network into an explicit random-feature model of polynomial size; testing this conversion empirically on finite Boolean classes would expose whether the hidden constants are practically meaningful.","The adc measure itself may be useful beyond this paper: polynomial equivalence to statistical query dimension gives a new way to reason about average-case learnability of linear feature models."],"forward_implications":["For any prior over a target class, distribution-free bSGD learnability forces the class to have small average probabilistic dimension complexity, so the class is random-feature friendly in the average case.","Learning problems that are hard for random features—random parities being the canonical example—cannot be solved by distribution-free gradient descent with coarse gradient precision; this explains why distributional assumptions such as biased product distributions are needed for parity learning.","The number of features needed is polynomial in $Tp/c^2$, so the collapse is quantitative: bounded compute and bounded gradient precision keep the random-feature representation small.","The infinite separation between adc and standard dimension complexity means worst-case lower bounds on feature representations can be misleading: average-case random-feature learning can be much easier than the worst function in the class suggests."],"supporting_citations":[{"why":"Proves the bSGD-to-SQ simulation (their Theorem 1c, restated as the paper's Theorem 3.4), the first reduction of the main proof.","marker":"Abbe et al. (2021)"},{"why":"Gives the SQ-dimension lower bound on statistical-query learning (Theorem 3.6), which turns the SQ query count $Tp$ into a bound on $\\mathrm{sq}(F)$.","marker":"Blum et al. (1994)"},{"why":"Supplies Theorem A.1 relating statistical query dimension to reciprocal discrepancy, the bridge to communication complexity.","marker":"Sherstov (2008b)"},{"why":"One of the sources for the 2-party norm bound (Theorem D.6) used to convert correlation into weak random-feature predictors.","marker":"Viola & Wigderson (2007)"},{"why":"Provides the AdaBoost weak-to-strong boosting theorem (Theorem A.6) that assembles weak features into a linear combination.","marker":"Freund & Schapire (1997)"},{"why":"Defines probabilistic dimension complexity and poses the infinite-separation open problem that motivates the adc relaxation.","marker":"Kamath et al. (2020)"},{"why":"Gives the Zarankiewicz-matrix construction (Theorem C.5) used for the infinite separation between adc and standard dimension complexity.","marker":"Sherstov (2008a)"},{"why":"Supplies the averaging argument (Lemma A.5) used inside the Random Feature lemma.","marker":"Arora & Barak (2009)"}],"fun_headline_variants":["SGD without data assumptions reduces to random features","Distribution-free SGD? Random features suffice","Random features: the fate of distribution-free SGD","SGD's power shrinks to random features sans distribution","When SGD assumes nothing, random features take over"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the 2-party norm bound, proved for uniformly distributed inputs, continues to hold when the function rows and the example columns are drawn from an arbitrary product distribution; if that step fails, the random-feature lemma and the collapse theorem do not go through.","fun_headline_variants_meta":{"raw":{"variants":["SGD without data assumptions reduces to random features","Distribution-free SGD? Random features suffice","Random features: the fate of distribution-free SGD","SGD's power shrinks to random features sans distribution","When SGD assumes nothing, random features take over"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000822,"raw_usage":{"total_tokens":3611,"prompt_tokens":976,"completion_tokens":2635,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":2564}},"tokens_in":592,"tokens_out":2635,"duration_ms":19238,"temperature":1.0,"reasoning_tokens":2564,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:12:43.634157+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a function class $F$ and a prior $\\mu$ for which a $\\mathrm{bSGD}(T,c,b,p)$ method achieves distribution-free squared loss $1/10$ but, for some $\\rho$, every distribution over $d=\\mathrm{poly}(Tp/c^2)$ random embeddings fails to $0/1$-approximate a $1-\\delta$ mass of $F$; that would refute Theorem 3.3 directly.","supporting_citations":[{"cited_title":"On the power of differentiable learning versus pac and sq learning","cited_arxiv_id":null,"evidence_quote":"Proves the bSGD-to-SQ simulation (their Theorem 1c, restated as the paper's Theorem 3.4), the first reduction of the main proof."},{"cited_title":"Weakly learning dnf and characterizing statistical query learning using fourier analysis","cited_arxiv_id":null,"evidence_quote":"Gives the SQ-dimension lower bound on statistical-query learning (Theorem 3.6), which turns the SQ query count $Tp$ into a bound on $\\mathrm{sq}(F)$."},{"cited_title":"and Wigderson, A","cited_arxiv_id":null,"evidence_quote":"One of the sources for the 2-party norm bound (Theorem D.6) used to convert correlation into weak random-feature predictors."},{"cited_title":"Approximate is good enough: Probabilistic variants of dimensional and margin complexity","cited_arxiv_id":null,"evidence_quote":"Defines probabilistic dimension complexity and poses the infinite-separation open problem that motivates the adc relaxation."},{"cited_title":"and Barak, B","cited_arxiv_id":null,"evidence_quote":"Supplies the averaging argument (Lemma A.5) used inside the Random Feature lemma."}],"review_version":1}