Fetching the paper…
Reading the bibliography…
We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise.
“The landscape of the planted clique problem: Dense subgraphs and the overlap gap property”, 2019
David Gamarnik and Ilias Zadik · 1904
Earlier work this paper cites.
Dmitriy Kunisky, Alexander. Wein and Afonso. Bandeira · 1907
Earlier work this paper cites.
David Gamarnik, Eren. Kızıldağ and Ilias Zadik · 1910
Earlier work this paper cites.
“Generalized Linear Models”
J.. Nelder and R… Wedderburn · 1972
Earlier work this paper cites.
“Phase retrieval algorithms: a comparison”
James Fienup · 1982
Earlier work this paper cites.
“Factoring polynomials with rational coefficients”
Arjen Lenstra, Hendrik Lenstra and László Lovász · 1982
Earlier work this paper cites.
“A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem”
Adi Shamir · 1982
Earlier work this paper cites.
“Improved Algorithms for Integer Programming and Related Lattice Problems”
Ravi Kannan · 1983
Earlier work this paper cites.
“Knapsack public key cryptosystems and diophantine approximation”
Jeffrey Lagarias · 1984
Earlier work this paper cites.
“Solving Low-Density Subset Sum Problems”
J.. Lagarias and A.. Odlyzko · 1985
Earlier work this paper cites.
“On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem”
Alan. Frieze · 1986
Earlier work this paper cites.
“A hierarchy of polynomial time lattice basis reduction algorithms”
Claus-Peter Schnorr · 1987
Earlier work this paper cites.
“Condition numbers of random matrices”
Stanislaw Szarek · 1991
Earlier work this paper cites.
“Large cliques elude the Metropolis process”
Mark Jerrum · 1992
Earlier work this paper cites.
“Cryptographic Hardness of Distribution-Specific Learning”
Michael Kharitonov · 1993
Earlier work this paper cites.
“Weakly learning DNF and characterizing statistical query learning using Fourier analysis”
Avrim Blum et al · 1994
Earlier work this paper cites.
“Lattices and Codes: A Course Partially Based on Lectures by F. Hirzebruch”
Wolfgang Ebeling and Friedrich Hirzebruch · 1994
Earlier work this paper cites.
“Cryptographic Limitations on Learning Boolean Formulae and Finite Automata”
Michael Kearns and Leslie Valiant · 1994
Earlier work this paper cites.
“Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems”
C.. Schnorr and M. Euchner · 1994
Earlier work this paper cites.
“Finding a large hidden clique in a random graph”
Noga Alon, Michael Krivelevich and Benny Sudakov · 1998
Earlier work this paper cites.
“Efficient noise-tolerant learning from statistical queries”
Michael Kearns · 1998
Earlier work this paper cites.
“Generalized Linear Models”
Marlene Müller · 2000
Earlier work this paper cites.
“Poly-time universality and limitations of deep learning”, 2020
Emmanuel Abbe and Colin Sandon · 2001
Earlier work this paper cites.
“Distributional and L-q norm inequalities for polynomials over convex bodies in R-n”
A. Carbery and James Wright · 2001
Earlier work this paper cites.
“Foundations of Cryptography”
Oded Goldreich · 2001
Earlier work this paper cites.
“The concentration of measure phenomenon”
Michel Ledoux · 2001
Earlier work this paper cites.
“Complexity of Lattice Problems: A Cryptographic Perspective”, The Springer International Series in Engineering and Computer Science
Daniele Micciancio and Shafi Goldwasser · 2002
Earlier work this paper cites.
“Online stochastic gradient descent on non-convex losses from high-dimensional inference”, 2021
Gerard Arous, Reza Gheissari and Aukosh Jagannath · 2003
Earlier work this paper cites.
“The coarea formula for Sobolev mappings”
Jan Malý, David Swanson and William Ziemer · 2003
Earlier work this paper cites.
“Lattice problems in NP ∩ \cap CoNP”
Dorit Aharonov and Oded Regev · 2005
Earlier work this paper cites.
“On signal reconstruction without phase”
Radu Balan, Pete Casazza and Dan Edidin · 2005
Cited alongside, same era.
“The zero set of a polynomial”
Richard Caron and Tim Traynor · 2005
Cited alongside, same era.
“Agnostic learning of a single neuron with gradient descent”, 2020
Spencer Frei, Yuan Cao and Quanquan Gu · 2005
Cited alongside, same era.
“Hardness of Approximating the Shortest Vector Problem in Lattices”
Subhash Khot · 2005
Cited alongside, same era.
“On lattices, learning with errors, random linear codes, and cryptography”
Oded Regev · 2005
Cited alongside, same era.
“Phase retrieval in high dimensions: Statistical and computational phase transitions”, 2020
“Learning one-hidden-layer neural networks with landscape design”, 2017
Rong Ge, Jason Lee and Tengyu Ma · 2017
Later among the works it cites.
“High dimensional linear regression with binary coefficients: Mean squared error and a phase transition”
David Gamarnik and Ilias Zadik · 2017
Later among the works it cites.
“Learning relus via gradient descent”, 2017
Mahdi Soltanolkotabi · 2017
Later among the works it cites.
“On the Complexity of Learning Neural Networks”
Le Song, Santosh Vempala, John Wilmes and Bo Xie · 2017
Later among the works it cites.
“Failures of gradient-based deep learning”
Shai Shalev-Shwartz, Ohad Shamir and Shaked Shammah · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Antoine Maillard, Bruno Loureiro, Florent Krzakala and Lenka Zdeborová · 2006
Cited alongside, same era.
“Complex dynamics in simple neural networks: Understanding gradient flow in phase retrieval”, 2020
Stefano Mannelli et al · 2006
Cited alongside, same era.
Stefano Mannelli, Eric Vanden-Eijnden and Lenka Zdeborová · 2006
Cited alongside, same era.
“Tensor-Based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors”
Ishay Haviv and Oded Regev · 2007
Cited alongside, same era.
“Finding Short Lattice Vectors within Mordell’s Inequality”
Nicolas Gama and Phong. Nguyen · 2008
Cited alongside, same era.
“Message-passing algorithms for compressed sensing”
David. Donoho, Arian Maleki and Andrea Montanari · 2009
Cited alongside, same era.
“Cryptographic hardness for learning intersections of halfspaces”
Adam Klivans and Alexander Sherstov · 2009
Cited alongside, same era.
Noah Stephens-Davidowitz · 2017
Later among the works it cites.
“Recovery guarantees for one-hidden-layer neural networks”, 2017
Kai Zhong et al · 2017
Later among the works it cites.
“Learning and generalization in overparameterized neural networks, going beyond two layers”, 2018
Zeyuan Allen-Zhu, Yuanzhi Li and Yingyu Liang · 2018
Later among the works it cites.
“Notes on computational-to-statistical gaps: predictions using statistical physics”, 2018
Afonso. Bandeira, Amelia Perry and Alexander. Wein · 2018
Later among the works it cites.
“Phasemax: Convex phase retrieval via basis pursuit”
Tom Goldstein and Christoph Studer · 2018
Later among the works it cites.
“Fundamental limits of weak recovery with applications to phase retrieval”
Marco Mondelli and Andrea Montanari · 2018
Later among the works it cites.
“Distribution-Specific Hardness of Learning Neural Networks”
Ohad Shamir · 2018
Later among the works it cites.
“High-dimensional probability: an introduction with applications in data science”, Cambridge Series in Statistical and Probabilistic Mathematics
Roman Vershynin · 2018
Later among the works it cites.
“High Dimensional Linear Regression using Lattice Basis Reduction”
Ilias Zadik and David Gamarnik · 2018
Later among the works it cites.
“The committee machine: Computational to statistical gaps in learning a two-layers neural network”
Benjamin Aubin et al · 2019
Later among the works it cites.
“Optimal errors and phase transitions in high-dimensional generalized linear models”
Jean Barbier et al · 2019
Later among the works it cites.
“Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval”
Yuxin Chen, Yuejie Chi, Jianqing Fan and Cong Ma · 2019
Later among the works it cites.
“Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals”
Surbhi Goel, Sushrut Karmalkar and Adam Klivans · 2019
Later among the works it cites.
“Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm”, 2019
David Gamarnik and Ilias Zadik · 2019
Later among the works it cites.
“All-or-Nothing Phenomena: From Single-Letter to High Dimensions”
Galen Reeves, Jiaming Xu and Ilias Zadik · 2019
Later among the works it cites.
“High-Dimensional Statistics: A Non-Asymptotic Viewpoint”, Cambridge Series in Statistical and Probabilistic Mathematics
Martin. Wainwright · 2019
Later among the works it cites.
“Slide Reduction, Revisited—Filling the Gaps in SVP Approximation”
Divesh Aggarwal, Jianwei Li, Phong. Nguyen and Noah Stephens-Davidowitz · 2020
Later among the works it cites.
“Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process”, 2020
Gorjan Alagic et al · 2020
Later among the works it cites.
“Approximation schemes for relu regression”
Ilias Diakonikolas et al · 2020
Later among the works it cites.
“Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks”
Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis and Nikos Zarifis · 2020
Later among the works it cites.
“Superpolynomial lower bounds for learning one-layer neural networks using gradient descent”
Surbhi Goel et al · 2020
Later among the works it cites.
“Marvels and Pitfalls of the Langevin Algorithm in Noisy High-Dimensional Inference”
Stefano Sarao et al · 2020
Later among the works it cites.
“Continuous LWE”
Joan Bruna, Oded Regev, Min Song and Yi Tang · 2021
Closest in time.
“From Local Pseudorandom Generators to Hardness of Learning”, 2021
Amit Daniely and Gal Vardi · 2021
Closest in time.
“Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem”
Francesca Mignacco, Pierfrancesco Urbani and Lenka Zdeborova · 2021
Closest in time.