Fetching the paper…
Reading the bibliography…
We give superpolynomial statistical query (SQ) lower bounds for learning two-hidden-layer ReLU networks with respect to Gaussian inputs in the standard (noise-free) model.
Factoring polynomials with rational coefficients
Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász · 1982
Earlier work this paper cites.
A theory of the learnable
Leslie G Valiant · 1984
Earlier work this paper cites.
Training a 3-node neural network is np-complete
Avrim Blum and Ronald L Rivest · 1989
Earlier work this paper cites.
On small depth threshold circuits
Alexander A Razborov · 1992
Earlier work this paper cites.
Threshold circuits of bounded depth
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán · 1993
Earlier work this paper cites.
Weakly learning dnf and characterizing statistical query learning using fourier analysis
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
When won’t membership queries help?
Dana Angluin and Michael Kharitonov · 1995
Earlier work this paper cites.
Cryptographic lower bounds for learnability of boolean functions on the uniform distribution
Michael Kharitonov · 1995
Earlier work this paper cites.
Number-theoretic constructions of efficient pseudo-random functions
Moni Naor and Omer Reingold · 1997
Earlier work this paper cites.
Natural proofs
Alexander A Razborov and Steven Rudich · 1997
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Pseudorandom functions in in tc0 and cryptographic limitations to proving lower bounds
Matthias Krause and Stefan Lucks · 2001
Earlier work this paper cites.
On the infeasibility of training neural networks with small mean-squared error
VH Vu · 2006
Earlier work this paper cites.
On the power of membership queries in agnostic learning
Vitaly Feldman · 2009
Earlier work this paper cites.
Cryptographic hardness for learning intersections of halfspaces
Adam R Klivans and Alexander A Sherstov · 2009
Earlier work this paper cites.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Earlier work this paper cites.
The learning with errors problem
Oded Regev · 2010
Earlier work this paper cites.
Pseudorandom functions and lattices
Abhishek Banerjee, Chris Peikert, and Alon Rosen · 2012
Earlier work this paper cites.
Learning with rounding, revisited
Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs · 2013
Earlier work this paper cites.
Learning sparse polynomial functions
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang · 2014
Earlier work this paper cites.
New and improved key-homomorphic pseudorandom functions
Abhishek Banerjee and Chris Peikert · 2014
Earlier work this paper cites.
From average case complexity to improper learning complexity
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz · 2014
Earlier work this paper cites.
Embedding hard learning problems into gaussian space
Adam Klivans and Pravesh Kothari · 2014
Earlier work this paper cites.
On the computational efficiency of training neural networks
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir · 2014
Earlier work this paper cites.
Aggregate pseudorandom functions and connections to learning
Aloni Cohen, Shafi Goldwasser, and Vinod Vaikuntanathan · 2015
Earlier work this paper cites.
Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar · 2015
Earlier work this paper cites.
On the hardness of learning with rounding over small modulus
Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen · 2016
Earlier work this paper cites.
Complexity theoretic limitations on learning dnf’s
Amit Daniely and Shai Shalev-Shwartz · 2016
Cited alongside, same era.
Optimal key consensus in presence of noise
Zhengzhong Jin and Yunlei Zhao · 2016
Cited alongside, same era.
A decade of lattice cryptography
Chris Peikert · 2016
Cited alongside, same era.
Stealing machine learning models via prediction apis
Florian Tramèr, Fan Zhang 0022, Ari Juels, Michael K. Reiter, and Thomas Ristenpart · 2016
Cited alongside, same era.
Globally optimal gradient descent for a convnet with gaussian inputs
Alon Brutzkus and Amir Globerson · 2017
Cited alongside, same era.
Pseudorandom functions: Three decades later
Learning deep relu networks is fixed-parameter tractable
Sitan Chen, Adam R Klivans, and Raghu Meka · 2020
Later among the works it cites.
Approximation schemes for relu regression
Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi · 2020
Later among the works it cites.
On the learnability of random deep networks
Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, and Rina Panigrahy · 2020
Later among the works it cites.
Small covers for near-zero sets of polynomials and learning latent variable models
Ilias Diakonikolas and Daniel M. Kane · 2020
Later among the works it cites.
Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis · 2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Andrej Bogdanov and Alon Rosen · 2017
Cited alongside, same era.
Reliably learning the relu in polynomial time
Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler · 2017
Cited alongside, same era.
Convergence analysis of two-layer neural networks with relu activation
Yuanzhi Li and Yang Yuan · 2017
Cited alongside, same era.
Practical black-box attacks against machine learning
Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami · 2017
Cited alongside, same era.
Alternating sum of binomial coefficients identity
PSPACEhard · 2017
Cited alongside, same era.
On the complexity of learning neural networks
Le Song, Santosh Vempala, John Wilmes, and Bo Xie · 2017
Cited alongside, same era.
An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis
Yuandong Tian · 2017
Cited alongside, same era.
Ilias Diakonikolas, Daniel M Kane, and Nikos Zarifis · 2020
Later among the works it cites.
Hardness of learning neural networks with natural weights
Amit Daniely and Gal Vardi · 2020
Later among the works it cites.
Superpolynomial lower bounds for learning one-layer neural networks using gradient descent
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans · 2020
Later among the works it cites.
Statistical-query lower bounds via functional gradients
Surbhi Goel, Aravind Gollakota, and Adam Klivans · 2020
Later among the works it cites.
High accuracy and high fidelity extraction of neural networks
Matthew Jagielski, Nicholas Carlini, David Berthelot, Alex Kurakin, and Nicolas Papernot · 2020
Later among the works it cites.
Span recovery for deep neural networks with applications to input obfuscation
Rajesh Jayaram, David P. Woodruff, and Qiuyi Zhang · 2020
Later among the works it cites.
Learning over-parametrized two-layer neural networks beyond ntk
Yuanzhi Li, Tengyu Ma, and Hongyang R. Zhang · 2020
Later among the works it cites.
Statistical queries and statistical algorithms: Foundations and applications
Lev Reyzin · 2020
Later among the works it cites.
Reverse-engineering deep relu networks
David Rolnick and Konrad P. Kording · 2020
Later among the works it cites.
A deep conditioning treatment of neural networks
Naman Agarwal, Pranjal Awasthi, and Satyen Kale · 2021
Later among the works it cites.
Efficient algorithms for learning depth-2 neural networks with general relu activations
Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan · 2021
Later among the works it cites.
Personal communication, 2021
Andrej Bogdanov · 2021
Later among the works it cites.
Continuous lwe
Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang · 2021
Later among the works it cites.
Efficiently learning one hidden layer relu networks from queries
Sitan Chen, Adam Klivans, and Raghu Meka · 2021
Later among the works it cites.
An exact poly-time membership-queries algorithm for extraction a three-layer relu network
Amit Daniely and Elad Granot · 2021
Later among the works it cites.
Non-gaussian component analysis via lattice basis reduction, 2021
Ilias Diakonikolas and Daniel M. Kane · 2021
Later among the works it cites.
From local pseudorandom generators to hardness of learning
Amit Daniely and Gal Vardi · 2021
Later among the works it cites.
On the cryptographic hardness of learning single periodic neurons
Min Jae Song, Ilias Zadik, and Joan Bruna · 2021
Later among the works it cites.
Size and depth separation in approximating natural functions with neural networks
Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir · 2021
Later among the works it cites.
Algorithms for efficiently learning low-rank neural networks, 2022
Kiran Vodrahalli, Rakesh Shivanna, Mahesh Sathiamoorthy, Sagar Jain, and Ed Chi · 2022
Closest in time.
Lattice-based methods surpass sum-of-squares in clustering, 2022
Ilias Zadik, Min Jae Song, Alexander S. Wein, and Joan Bruna · 2022
Closest in time.