Hardness of Learning Fixed Parities with Neural Networks

Itamar Shoshani; Ohad Shamir

REVIEW 3 major objections 5 minor 1 cited by

Hardness of Learning Fixed Parities with Neural Networks

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper proves that for any fixed parity of size |S|, perturbed gradient descent on a one-hidden-layer ReLU network leaves the loss exponentially close to its trivial value unless the number of iterations is exponential in |S|, even…

desk verdict Solid resolution of the fixed-parity hardness question for a narrow but clean setting; the main theorems hold up, the stress-test's scale factor is a red herring, but the appendix needs a serious copyedit. read the letter →

arxiv 2501.00817 v2 pith:SM4TN3JV submitted 2025-01-01 cs.LG stat.ML

Itamar Shoshani , Ohad Shamir This is my paper · ORCID

classification cs.LGstat.ML MSC 68Q3268T0706E30

keywords parityfunctionsgradientdescenthardnessone-hidden-layerReLUnetworksperturbedFouriercoefficientslinearthresholdBooleanfunctionlearningstatisticalqueries

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 shows that the difficulty of learning a fixed parity function with gradient methods is a real dynamic phenomenon, not merely a worst-case artifact of statistical-query lower bounds. For any subset S of coordinates of size |S| at least logarithmic in the relevant parameters, perturbed gradient descent (PGD) on a one-hidden-layer ReLU network with the linear/correlation loss leaves the objective exponentially close to zero, and for a single ReLU neuron with squared loss leaves the loss exponentially close to the trivial value 1, unless the iteration count is exponential in |S|. This holds even though a small ReLU network represents p_S exactly and a single neuron weakly approximates it. The engine is a new average-case bound: the Fourier coefficient of a Gaussian-weighted linear threshold function on S decays like exp(-$\Omega$(|S|)), which makes the gradient exponentially small almost everywhere.

What carries the argument

The load-bearing object is the Fourier coefficient of a linear threshold (weighted majority) function, f_S(w,b) = E_{x in {±1}^d}[p_S(x) 1{w^T x + b > 0}], which appears in the gradient of the loss with respect to the hidden weights. The paper proves an average-case exponential decay of this coefficient: over Gaussian w, E[$f_S^{2}$] < 6 exp(-|S|/4). The proof expresses E[$f_S^{2}$] as an expected intersection volume of two random hemispheres, expands that volume as a Taylor series in (x^T y)/d, and observes that the first |S|-1 terms vanish by orthogonality of parity characters, leaving a rapidly decaying tail controlled by Stirling and Hoeffding bounds. On the optimization side, a clipped-gradient coupling argument bounds the total variation distance between true PGD and a plain Gaussian random walk, using Markov's inequality on the gradient norm, so the failure follows from the random walk being unable to reduce the loss.

What would settle it

Sample w from a standard d-dimensional Gaussian, estimate E[f_S(w)^2] numerically for several subsets S, and compare the averages to 6 exp(-|S|/4); consistent violation of that bound would refute the Fourier-coefficient engine. A direct PGD experiment on a fixed parity with |S| = 100 should also show every gradient norm staying below exp(-|S|/18) for sub-exponential T, with the linear loss never dropping below exp(-|S|/18); observing a larger gradient or a meaningful loss reduction would refute the theorem's mechanism.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes a general hardness theorem for fixed parities: with d >= 30 and |S| >= 72 * max{ln(6nd $\sigma$), ln(5nd $sigma^{2}$ (T+1))}, after T PGD steps with Gaussian initialization and Gaussian perturbations, with probability at least 1 - (eta $\sqrt$(T)/(2 $\sigma$) + T + 2) exp(-|S|/18) the objective satisfies |F_S(theta_T)| < exp(-|S|/18). Because an exact width-(|S|+1) network exists (Theorem 1), the failure is dynamic, not expressive. For the squared loss and one ReLU neuron, the same phenomenon appears: although parameters achieve squared loss at most 1 - 1/(8|S|^2), PGD outputs loss larger than 1 - (2 + T + eta $\sqrt$(T)/$\sigma$) exp(-|S|/18). The technical root is a Fourier-analysis result (Theorem 3): for w drawn from a spherical Gaussian, the Fourier coefficient f_S(w,0) = E_{x in {±1}^d}[p_S(x) 1{w^T x > 0}] has second moment less than 6 exp(-|S|/4), and a bias-inclusive version (Theorem 6) extends this. This smallness makes PGD updates nearly a plain Gaussian random walk, which cannot reach meaningful solutions.

Load-bearing premise

The whole argument rests on the parameters' probability distribution staying nearly spherically symmetric while training runs; the Gaussian perturbations and the linear loss enforce that, and if the noise or the loss changes, the proof does not go through.

Editorial extensions

If this is right

For |S| = omega(log d), reaching any meaningful reduction of the linear loss requires a number of iterations super-polynomial in d; the full parity function S = {1,...,d} is covered, which prior parity-hardness results did not cover.
The failure mechanism is small gradients under spherically symmetric parameter distributions, so the theorem transfers to any one-hidden-layer ReLU network and linear loss with spherically symmetric perturbations and appropriately bounded step sizes.
The single-neuron squared-loss result shows the obstruction is not an artifact of the unusual linear loss: weak learnability exists, yet PGD cannot exploit it in sub-exponential time.
The Fourier-coefficient bound stands on its own as a statement about the Boolean spectrum of weighted majority functions, beyond the well-studied plain majority case.
The results delimit what gradient-based methods can do for parity learning: any success requires either a contrived architecture or an algorithmic noise structure that breaks near-spherical symmetry.

Reading between the lines

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

If the mechanism is as generic as the proof suggests, the empirical failure of ordinary SGD on parities may share the same cause: gradients are exponentially small as long as the iterates' distribution stays nearly spherically symmetric, and SGD's example-dependent noise is the main barrier to making this rigorous.
A testable extension would be to run PGD on small parities while tracking the empirical distribution of weight directions; the proof predicts the marginal remains nearly spherical and gradients stay below the exponential threshold, whereas an anisotropic initialization or noise should quickly produce larger gradients.
A deterministic version of the Fourier-decay bound for weights far from majority-like structured vectors would imply hardness for more general training dynamics, including those whose iterates concentrate on non-spherical directions.
The deliberately contrived architectures that implement Gaussian elimination stand as the known exception, so the result should not be read as proving parities are unlearnable by all differentiable models.

Share X Bluesky LinkedIn Reddit HN

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

Worth a careful read. The paper proves something genuinely new: for any fixed parity of size above logarithmic, perturbed GD on a one-hidden-layer ReLU network with the expected linear loss fails to reduce the loss below exp(-Ω(|S|)), and there is a single-neuron analogue for squared loss. This resolves the Abbe-Boix-Adsera open problem for the full parity and all large subsets, not just |S|≈d/2. The Fourier result behind it—average-case exponential decay of the |S|-th Fourier coefficient of weighted majority functions under a spherically symmetric weight distribution—is clean and likely to be used independently. The proof structure is sound: a TV coupling of PGD to a clipped process, then a bound on the chance that the clipped process's Gaussian walk ever visits a large-gradient point, then a small-loss bound for a plain random walk.

I checked the stress-test note's alleged missing √(j+2) factor in Theorem 2's union bound. It does not land. For the linear loss, F_S is homogeneous of degree 1 in the parameters, so the gradient is scale-invariant, ∇F_S(cθ)=∇F_S(θ), not scale-linear. Therefore the partial sums ∑_{t=-1}^j ξ_t have the same gradient norm distribution as a single σ-scale Gaussian draw, and Lemma 2 applies without strengthening the |S| condition. The displayed justification in the paper is telegraphic, but the step is correct. The reader's other flagged issues are real: Lemma 2's display misstates the expectation (it is E|E_x[...]|, not |E_x[...]|), and there is a sign/index slip in the Theorem 5 appendix and a constants-line slip in the Theorem 3 appendix. None of these appears to break the argument.

The limitations are genuine but acknowledged. The spherical-symmetry machinery requires zero-mean Gaussian perturbations and the population loss; SGD and multi-neuron squared loss are left open, exactly as Section 5 states. The theorem needs |S| ≥ 72 ln(...) so very small parities are not covered, which is fine—those are learnable by other means. Theorem 1 and Theorem 4 do the necessary work, so the failure is dynamical, not representational.

Who is this for: anyone working on gradient-based learning of parities, Boolean function Fourier analysis, or implicit bias/hardness of neural optimization. I would send it to a serious theory venue after a copyedit pass; the typos are fixable and the core is in good shape.

Referee Report

3 major / 5 minor

Summary. The paper studies hardness of learning fixed parity functions p_S by perturbed gradient descent (PGD) on one-hidden-layer ReLU networks. After showing (Theorem 1) that such networks can express p_S exactly with O(|S|) neurons and polynomially bounded weights, the main result (Theorem 2) states that for |S| at least logarithmic in the problem parameters, PGD with Gaussian initialization and zero-mean Gaussian perturbations leaves the expected correlation loss exponentially close to zero unless the number of iterations is exponential in |S|. A parallel result (Theorem 5) is proved for the squared loss with a single ReLU neuron, complementing a weak-learnability construction (Theorem 4). The key new analytic ingredient is Theorem 3 (and its biased variant Theorem 6): the Fourier coefficient of a linear threshold function corresponding to S decays exponentially in |S| in expectation over spherically symmetric weights. The proofs couple the PGD process to a clipped process whose updates are pure Gaussian steps, and use the smallness of gradients almost everywhere to show that the coupling is close in total variation.

Significance. If the technical gaps identified below are repaired, the paper would make a solid and appropriately scoped contribution. Its main value is conceptual: it replaces a worst-case-over-parities SQ statement with a fixed-parity hardness statement in a concrete, standard model (PGD, ReLU networks, population loss), and it covers the full parity function, which was explicitly left open by Abbe and Boix-Adsera. The Fourier-coefficient theorem (Theorem 3/6) is an independent contribution with explicit constants. The paper also carefully proves expressibility and weak learnability (Theorems 1 and 4), so the hardness is not due to lack of capacity. The limitations—population loss, PGD rather than SGD, and reliance on spherical symmetry—are stated honestly in Section 5.

major comments (3)

[Section 3.3, Eq. (6) and following paragraph] The union bound over j applies Lemma 2 to S_j = \sum_{t=-1}^j \xi_t, invoking only that S_j ~ N(0,(j+2)\sigma^2 I). Lemma 2 is proved for \theta ~ N(0,\sigma^2 I), and because the gradient is positively homogeneous in the full parameter vector, the correct bound is P(||\nabla F_S(S_j)|| \ge \varepsilon) \le \sqrt{j+2}\,e^{-|S|/18}, not \varepsilon. Hence the displayed '(T+1)\varepsilon' should be \Theta(T^{3/2})\varepsilon, and the theorem's stated failure probability (\eta\sqrt{T}/(2\sigma)+T+2)e^{-|S|/18} is not established as written. The qualitative exponential-hardness claim survives after replacing the probability bound by a polynomial-in-T factor or strengthening the minimal-size condition by an extra log T term, but the proof needs this correction.
[Section 4, Eq. (34)] The chain P(||\nabla F_lin(v_t)|| \ge \varepsilon) = P(||\nabla F_lin(v_t)||^2 \ge \varepsilon^2) \le E||\nabla F_lin(v_t)||^2/\varepsilon^2 \le \varepsilon is invalid, since the second-moment bound E||\nabla F_lin(v_t)||^2 \le \varepsilon (established a few lines later) yields E/\varepsilon^2 = 1/\varepsilon after Markov, not \varepsilon. A correct proof would need a first-moment bound such as E||\nabla F_lin(v_t)|| \le C\sqrt{d}\,e^{-|S|/8} (obtainable from Theorem 6 and Jensen) and then a Markov step giving e^{-5|S|/72} per term, which requires a stronger |S| condition than the one stated, or a different arrangement of constants. The displayed derivation does not go through.
[Section 4, Theorem 5 statement and proof] The theorem asserts that with probability at least 1-\varepsilon, F_S(\theta_T) > 1-C\varepsilon, where C=2+T+\eta\sqrt{T}/\sigma. The proof instead concludes P(F_S(\theta_T) \le 1-\varepsilon) \le C\varepsilon. These statements are incomparable as written: the latter gives a weaker probability for a stronger threshold and does not imply the former. The theorem should either be restated in the same format as Theorem 2 (failure probability C\varepsilon, threshold \varepsilon) or the proof must establish the stated probability with the weaker threshold.

minor comments (5)

[Section 4, Theorem 5 statement] The statement uses F_S(w_t,b_t) but the bound refers to the final iterate; replace t by T, or write \theta_T.
[Appendix A.2.1, Lemma 1 proof] The expression \theta_{t-1}+\Delta_{t-1} appears in the KL computation, but with the convention \theta_{t+1}=\theta_t-\Delta_t in Eq. (3) it should be \theta_{t-1}-\Delta_{t-1}. The subsequent Gaussian means use the correct sign, so this is a typographical issue.
[Appendix A.2.2, Lemma 2 proof] The constants imported from Theorem 6 are not fully consistent: the bound for E(\partial_{b_j}F)^2 uses 4e^{-|S|/4}, while Theorem 6 states a constant smaller than 8e^{-|S|/4}; later lines use 6e^{2.55}\sqrt{2\pi}/\sqrt{\pi}. The inequalities are loose enough, but the constants should be reconciled for a clean proof.
[Section 4, Eq. (28)] The notation [z]_\varepsilon = z\cdot 1\{z>\varepsilon\} is used for vectors as well as scalars; clarify that the clipping is applied to the norm, as in the definition used for Theorem 2.
[Section 3.2, proof of Theorem 3] The Taylor expansion of arccos is evaluated at x^Ty/d values that can equal \pm 1; since the coefficients satisfy \alpha_j = O(j^{-3/2}), the endpoint convergence is absolute and easily justified, but this should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hardness result follows from an independently derived Fourier-coefficient theorem and an explicit construction, not from fitted inputs or load-bearing self-citation.

full rationale

The paper's central claim, Theorem 2, is not derived from the conclusion it asserts. The expressiveness result (Theorem 1) is proved by an explicit ReLU-network construction for parity functions, with a concrete norm bound, and is used only to rule out trivial failure by lack of expressiveness. The key analytical input, Theorem 3 and its biased variant Theorem 6, proves exponential-in-|S| decay of the Fourier coefficients of linear threshold functions in an average-case sense; the proof proceeds from spherical geometry (the volume of intersecting hemispheres), the Taylor expansion of arccos, and a Hoeffding tail bound. Its assumptions do not include the PGD failure it later implies. Lemma 2 and Lemma 3 apply that Fourier result to bound gradient norms and objective values along Gaussian iterates, and Theorem 2 combines these with a total-variation comparison between the true PGD process and a Gaussian random walk. There are no fitted parameters, no normalization calibrated on the target parity, and no prediction that is equivalent by construction to an input. Citations to prior work, such as O'Donnell for standard facts about majority Fourier coefficients, are external and contextual rather than load-bearing self-citation; the cited works by Abbe et al. frame the open problem but do not supply the paper's central derivation. The paper's own Section 5 limitations—squared loss for multi-neuron networks and SGD—are honest scope restrictions, not evidence of circularity. A potential technical issue raised by a careful reader, concerning the variance scaling of partial sums in the union bound of Lemma 2's application, would be a proof gap if real, but a proof gap is not definitional circularity: the theorem's conclusion is not equivalent to its assumptions by construction.

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

The results depend only on standard probabilistic and analytic tools plus an explicit algorithmic model (Gaussian-perturbed GD on population loss). There are no fitted constants and no new postulated entities.

assumptions (5)

standard math Hoeffding's inequality for Rademacher sums
Used in the proofs of Theorems 3 and 6 to bound the tail probability of |x^T y|.
standard math Stirling's approximation for factorials
Used to bound the Taylor coefficients α_j of arccos and binomial coefficients in Theorems 3, 4, and 6.
domain assumption The PGD algorithm with zero-mean Gaussian initialization and perturbations
Defines the algorithm in Section 2; the proofs rely on spherical symmetry of the perturbation distribution to keep parameter marginals nearly spherical.
domain assumption Population expected loss (full distribution over {±1}^d) rather than empirical loss
The theorems concern the expected correlation and squared losses; extending to finite samples/SGD is left open in Section 5.
domain assumption ReLU derivative convention 1{z>0}, including 0 at z=0
Stated in Section 2 as without much loss of generality; the proofs use this convention for gradient computations.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hardness of Learning Fixed Parities with Neural Networks." pith.science (2026). https://pith.science/paper/SM4TN3JV

@misc{pith2026250100817,
  author       = {Pith},
  title        = {Pith review of: Hardness of Learning Fixed Parities with Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SM4TN3JV}},
  note         = {Machine review of arXiv:2501.00817}
}

read the original abstract

Learning parity functions is a canonical problem in learning theory, which although computationally tractable, is not amenable to standard learning algorithms such as gradient-based methods. This hardness is usually explained via statistical query lower bounds [Kearns, 1998]. However, these bounds only imply that for any given algorithm, there is some worst-case parity function that will be hard to learn. Thus, they do not explain why fixed parities - say, the full parity function over all coordinates - are difficult to learn in practice, at least with standard predictors and gradient-based methods [Abbe and Boix-Adsera, 2022]. In this paper, we address this open problem, by showing that for any fixed parity of some minimal size, using it as a target function to train one-hidden-layer ReLU networks with perturbed gradient descent will fail to produce anything meaningful. To establish this, we prove a new result about the decay of the Fourier coefficients of linear threshold (or weighted majority) functions, which may be of independent interest.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Limitations of SGD for Multi-Index Models Beyond Statistical Queries
cs.LG 2026-02 conditional novelty 7.0 of 10

Vanilla SGD provably fails to learn periodic and low-information-exponent single/multi-index targets unless the input dimension is small or the number of iterations is large.

Reference graph

Works this paper leans on

20 extracted references · 15 canonical work pages · cited by 1 Pith paper

[1]

On the non-universality of deep learning: quantifying the cost of symmetry

Emmanuel Abbe and Enric Boix-Adsera. On the non-universality of deep learning: quantifying the cost of symmetry. Advances in Neural Information Processing Systems, 35: 0 17188--17201, 2022

work page 2022
[2]

Poly-time universality and limitations of deep learning

Emmanuel Abbe and Colin Sandon. Poly-time universality and limitations of deep learning. arXiv preprint arXiv:2001.02992, 2020 a

arXiv 2001
[3]

On the universality of deep learning

Emmanuel Abbe and Colin Sandon. On the universality of deep learning. Advances in Neural Information Processing Systems, 33: 0 20061--20072, 2020 b

work page 2020
[4]

On the power of differentiable learning versus pac and sq learning

Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. 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
[5]

Noise-tolerant learning, the parity problem, and the statistical query model

Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50 0 (4): 0 506--519, 2003

work page 2003
[6]

Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent

Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent. In Conference on Learning Theory, pages 678--689. PMLR, 2017

work page 2017
[7]

Gradient descent can take exponential time to escape saddle points

Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances in neural information processing systems, 30, 2017

work page 2017
[8]

Nonasymptotic convergence analysis for the unadjusted langevin algorithm

Alain Durmus and \'E ric Moulines. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. The Annals of Applied Probability, 27 0 (3): 0 1551, 2017

work page 2017

Show all 20 references

[9]

Statistical algorithms and a lower bound for detecting planted cliques

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64 0 (2): 0 1--37, 2017

2017
[10]

How to escape saddle points efficiently

Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International conference on machine learning, pages 1724--1732. PMLR, 2017

2017
[11]

Efficient noise-tolerant learning from statistical queries

Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45 0 (6): 0 983--1006, 1998

1998
[12]

An introduction to computational learning theory

Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994

1994
[13]

On symmetry and initialization for neural networks

Ido Nachum and Amir Yehudayoff. On symmetry and initialization for neural networks. In LATIN 2020: Theoretical Informatics: 14th Latin American Symposium, S \ a o Paulo, Brazil, January 5-8, 2021, Proceedings 14 , pages 401--412. Springer, 2020

2020
[14]

Analysis of boolean functions, 2021

Ryan O'Donnell. Analysis of boolean functions, 2021. URL https://arxiv.org/abs/2105.10386

2021 arXiv
[15]

Fast learning requires good memory: A time-space lower bound for parity learning

Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. Journal of the ACM (JACM), 66 0 (1): 0 1--18, 2018

2018
[16]

Statistical queries and statistical algorithms: Foundations and applications

Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00557, 2020

2004 arXiv
[17]

Failures of gradient-based deep learning

Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning, pages 3067--3075. PMLR, 2017

2017
[18]

Global convergence of langevin dynamics based algorithms for nonconvex optimization

Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018

2018
[19]

New lower bounds for statistical query learning

Ke Yang. New lower bounds for statistical query learning. Journal of Computer and System Sciences, 70 0 (4): 0 485--509, 2005

2005
[20]

Escape saddle points by a simple gradient-descent based algorithm

Chenyi Zhang and Tongyang Li. Escape saddle points by a simple gradient-descent based algorithm. Advances in Neural Information Processing Systems, 34: 0 8545--8556, 2021

2021

Pith tools

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

[1] [1]

On the non-universality of deep learning: quantifying the cost of symmetry

Emmanuel Abbe and Enric Boix-Adsera. On the non-universality of deep learning: quantifying the cost of symmetry. Advances in Neural Information Processing Systems, 35: 0 17188--17201, 2022

work page 2022

[2] [2]

Poly-time universality and limitations of deep learning

Emmanuel Abbe and Colin Sandon. Poly-time universality and limitations of deep learning. arXiv preprint arXiv:2001.02992, 2020 a

arXiv 2001

[3] [3]

On the universality of deep learning

Emmanuel Abbe and Colin Sandon. On the universality of deep learning. Advances in Neural Information Processing Systems, 33: 0 20061--20072, 2020 b

work page 2020

[4] [4]

On the power of differentiable learning versus pac and sq learning

Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. 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

[5] [5]

Noise-tolerant learning, the parity problem, and the statistical query model

Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50 0 (4): 0 506--519, 2003

work page 2003

[6] [6]

Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent

Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent. In Conference on Learning Theory, pages 678--689. PMLR, 2017

work page 2017

[7] [7]

Gradient descent can take exponential time to escape saddle points

Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances in neural information processing systems, 30, 2017

work page 2017

[8] [8]

Nonasymptotic convergence analysis for the unadjusted langevin algorithm

Alain Durmus and \'E ric Moulines. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. The Annals of Applied Probability, 27 0 (3): 0 1551, 2017

work page 2017