The Power of Random Features and the Limits of Distribution-Free Gradient Descent

Ari Karchmer; Eran Malach

REVIEW 3 major objections 4 minor 30 references

The Power of Random Features and the Limits of Distribution-Free Gradient Descent

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read If a parametric model is distribution-free bSGD-learnable, random features approximate it with polynomially many terms.

desk verdict 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. read the letter →

arxiv 2505.10423 v1 pith:TRZLVNS3 submitted 2025-05-15 cs.LG

Ari Karchmer , Eran Malach This is my paper · ORCID

classification cs.LG MSC 68Q3268Q17

keywords distribution-freelearningmini-batchstochasticgradientdescentrandomfeaturesstatisticalquerydimensionaverageprobabilisticcomplexitycommunicationboosting

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

But 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.

There'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.

These 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.

Who 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[Appendix A.3 and Definition 3.2] 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.
[Appendix A.3, eq. (10)] 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 A.2 and Theorem D.6] 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.

minor comments (4)

[Definition 3.2] 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,ϕ⟩).
[Lemma A.4 proof] 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.
[Appendix A.3] 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.
[Introduction, Section 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a chain of independent external reductions (bSGD to SQ, SQ dimension, discrepancy, random features, boosting), and no load-bearing claim reduces to its own input by construction.

full rationale

The claimed derivation chain is Theorem 3.3 -> Theorem 3.4 (Abbe et al. 2021, bSGD simulated by SQ) + Theorem 3.6 (Blum et al. 1994, SQ-dimension lower bound) -> Theorem 4.1 (adc bounded by O(sq(F)^{24.01})) -> Theorem A.1/Lemma A.3 (Sherstov discrepancy theorem) -> Lemma A.4 (Random Feature lemma) -> Theorem A.6 (AdaBoost). Each step is either proved in the appendix from explicit constructions or imported from published parameter-free theorems whose assumptions do not include the target result. The new definition adc is not assumed in the proof of its own bound; the proof constructs weak random-feature predictors from correlation with 2-bit protocols and then boosts them, which is a genuine reduction rather than a renaming or a fitted-input prediction. The self-citations to Abbe et al. (2021), which includes coauthor Malach, and to Karchmer (2024a,b) are to published independent results; under the review rules these are real evidence and do not raise the circularity score. There is a serious quantifier concern in Appendix A.3: the embedding distribution E is defined through AdaBoost distributions rho_i that appear to depend on the target f, so the single distribution E required by the adc definition may not be established. That is a correctness gap in the proof, not an equivalence-by-construction or a parameter fit, and therefore it does not make the paper circular on the definition used here.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The central claim rests on several external theorems and on two unproven distributional assumptions inside the proof; there are no fitted numeric parameters.

assumptions (5)

standard math Abbe et al. (2021) Theorem 1c: any bSGD(T,c,b,p) method can be simulated by an SQ(Tp,c/8) method.
External theorem used as the first bridge in the main proof; stated as Theorem 3.4. It is peer-reviewed and not derived in this paper.
standard math Blum et al. (1994) SQ dimension lower bound: a SQ(k,τ) method accurate to 1/2-τ requires k > d τ^2 - 1/2.
Used to bound SQ dimension by Tp/c^2 in Theorem 3.3; external known result.
standard math Sherstov (2008b) Theorem 7.1: SQ dimension controls the reciprocal of product-distribution discrepancy.
Used to relate SQ dimension to discrepancy in Lemma A.3.
ad hoc to paper Theorem D.6 (2-party norm bound) holds for the arbitrary product distribution (μ,ρ), not only for uniform inputs.
The paper applies the uniform-distribution bound to a non-uniform product distribution in Lemma A.4 without proof or citation of a distributional variant.
ad hoc to paper The boosting process can reveal a final embedding distribution E that is independent of the target f, even though the queried distributions ρ_i are chosen adaptively based on f.
This is the quantifier-order assumption in the proof of Theorem 4.1; not justified in the text.

invented entities (1)

Average probabilistic dimension complexity (adc_{ε,δ}(µ))
purpose: A complexity measure for the number of random features needed to approximate most functions in a class under a prior.
A new definition introduced in Section 3.1; it has no falsifiable handle outside the paper, but it is a mathematical definition rather than a physical entity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Power of Random Features and the Limits of Distribution-Free Gradient Descent." pith.science (2026). https://pith.science/paper/TRZLVNS3

@misc{pith2026250510423,
  author       = {Pith},
  title        = {Pith review of: The Power of Random Features and the Limits of Distribution-Free Gradient Descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TRZLVNS3}},
  note         = {Machine review of arXiv:2505.10423}
}

read the original abstract

We study the relationship between gradient-based optimization of parametric models (e.g., neural networks) and optimization of linear combinations of random features. Our main result shows that if a parametric model can be learned using mini-batch stochastic gradient descent (bSGD) without making assumptions about the data distribution, then with high probability, the target function can also be approximated using a polynomial-sized combination of random features. The size of this combination depends on the number of gradient steps and numerical precision used in the bSGD process. This finding reveals fundamental limitations of distribution-free learning in neural networks trained by gradient descent, highlighting why making assumptions about data distributions is often crucial in practice. Along the way, we also introduce a new theoretical framework called average probabilistic dimension complexity (adc), which extends the probabilistic dimension complexity developed by Kamath et al. (2020). We prove that adc has a polynomial relationship with statistical query dimension, and use this relationship to demonstrate an infinite separation between adc and standard dimension complexity.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 23 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

On the power of differentiable learning versus pac and sq learning

Abbe, E., Kamath, P., Malach, E., Sandon, C., and Srebro, N. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34: 0 24340--24351, 2021

work page 2021
[3]

Learning and generalization in overparameterized neural networks, going beyond two layers

Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019

work page 2019
[4]

and Williams, R

Alman, J. and Williams, R. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 641--652, 2017

work page 2017
[5]

Learning polynomials with neural networks

Andoni, A., Panigrahy, R., Valiant, G., and Zhang, L. Learning polynomials with neural networks. In International conference on machine learning, pp.\ 1908--1916. PMLR, 2014

work page 1908
[6]

and Barak, B

Arora, S. and Barak, B. Computational complexity: a modern approach. Cambridge University Press, 2009

work page 2009
[7]

Hidden progress in deep learning: Sgd learns parities near the computational limit

Barak, B., Edelman, B., Goel, S., Kakade, S., Malach, E., and Zhang, C. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35: 0 21750--21764, 2022

2022
[8]

Ben-David, S., Eiron, N., and Simon, H. U. Limitations of learning via embeddings in euclidean half spaces. Journal of Machine Learning Research, 3 0 (Nov): 0 441--461, 2002

work page 2002

Show all 30 references

[9]

Weakly learning dnf and characterizing statistical query learning using fourier analysis

Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., and Rudich, S. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp.\ 253--262, 1994

1994
[10]

On lazy training in differentiable programming

Chizat, L., Oyallon, E., and Bach, F. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019

2019
[11]

Chung, F. R. and Tetali, P. Communication complexity and quasi randomness. SIAM Journal on Discrete Mathematics, 6 0 (1): 0 110--123, 1993

1993
[12]

Sgd learns the conjugate kernel class of the network

Daniely, A. Sgd learns the conjugate kernel class of the network. Advances in neural information processing systems, 30, 2017

2017
[13]

Madaboost: A modification of adaboost

Domingo, C., Watanabe, O., et al. Madaboost: A modification of adaboost. In COLT, pp.\ 180--189, 2000

2000
[14]

Gradient descent finds global minima of deep neural networks

Du, S., Lee, J., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp.\ 1675--1685. PMLR, 2019

2019
[15]

S., Zhai, X., Poczos, B., and Singh, A

Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018

2018 arXiv
[16]

L., Goel, S., Kakade, S., Malach, E., and Zhang, C

Edelman, B. L., Goel, S., Kakade, S., Malach, E., and Zhang, C. Pareto frontiers in neural feature learning: Data, compute, width, and luck. arXiv preprint arXiv:2309.03800, 2023

2023 arXiv
[17]

and Schapire, R

Freund, Y. and Schapire, R. E. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55 0 (1): 0 119--139, 1997

1997
[18]

Neural tangent kernel: Convergence and generalization in neural networks

Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018

2018
[19]

Approximate is good enough: Probabilistic variants of dimensional and margin complexity

Kamath, P., Montasser, O., and Srebro, N. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Learning Theory, pp.\ 2236--2262. PMLR, 2020

2020
[20]

and Larsen, K

Karbasi, A. and Larsen, K. G. The impossibility of parallelizing boosting. In International Conference on Algorithmic Learning Theory, pp.\ 635--653. PMLR, 2024

2024
[21]

Agnostic membership query learning with nontrivial savings: New results and techniques

Karchmer, A. Agnostic membership query learning with nontrivial savings: New results and techniques. In International Conference on Algorithmic Learning Theory, pp.\ 654--682. PMLR, 2024 a

2024
[22]

Distributional pac-learning from nisan’s natural proofs

Karchmer, A. Distributional pac-learning from nisan’s natural proofs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2024 b

2024
[23]

and Nisan, N

Kushilevitz, E. and Nisan, N. Communication complexity, 1996

1996
[24]

and Liang, Y

Li, Y. and Liang, Y. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in neural information processing systems, 31, 2018

2018
[25]

Auto-regressive next-token predictors are universal learners

Malach, E. Auto-regressive next-token predictors are universal learners. arXiv preprint arXiv:2309.06979, 2023

2023 arXiv
[26]

and Shalev-Shwartz, S

Malach, E. and Shalev-Shwartz, S. Learning boolean circuits with neural networks. arXiv preprint arXiv:1910.11923, 2019

1910 arXiv
[27]

The bns-chung criterion for multi-party communication complexity

Raz, R. The bns-chung criterion for multi-party communication complexity. Computational Complexity, 9 0 (2): 0 113--122, 2000

2000
[28]

Sherstov, A. A. Communication complexity under product and nonproduct distributions. In 2008 23rd Annual IEEE Conference on Computational Complexity, pp.\ 64--70. IEEE, 2008 a

2008
[29]

Sherstov, A. A. Halfspace matrices. Computational Complexity, 17: 0 149--178, 2008 b

2008
[30]

and Wigderson, A

Viola, E. and Wigderson, A. Norms, xor lemmas, and lower bounds for gf (2) polynomials and multiparty protocols. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pp.\ 141--154. IEEE, 2007

2007

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

On the power of differentiable learning versus pac and sq learning

Abbe, E., Kamath, P., Malach, E., Sandon, C., and Srebro, N. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34: 0 24340--24351, 2021

work page 2021

[3] [3]

Learning and generalization in overparameterized neural networks, going beyond two layers

Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019

work page 2019

[4] [4]

and Williams, R

Alman, J. and Williams, R. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 641--652, 2017

work page 2017

[5] [5]

Learning polynomials with neural networks

Andoni, A., Panigrahy, R., Valiant, G., and Zhang, L. Learning polynomials with neural networks. In International conference on machine learning, pp.\ 1908--1916. PMLR, 2014

work page 1908

[6] [6]

and Barak, B

Arora, S. and Barak, B. Computational complexity: a modern approach. Cambridge University Press, 2009

work page 2009

[7] [7]

Hidden progress in deep learning: Sgd learns parities near the computational limit

Barak, B., Edelman, B., Goel, S., Kakade, S., Malach, E., and Zhang, C. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35: 0 21750--21764, 2022

2022

[8] [8]

Ben-David, S., Eiron, N., and Simon, H. U. Limitations of learning via embeddings in euclidean half spaces. Journal of Machine Learning Research, 3 0 (Nov): 0 441--461, 2002

work page 2002