mlsanityData to 7 Oct 2026

Efficiently Learning Any One Hidden Layer ReLU Network From Queries

arXiv 2111.04727 ↗First posted 8 Nov 2021cs.LG cs.CR cs.DScited by 6

Not on the map. Why?

Abstract (arXiv)

Model extraction attacks have renewed interest in the classic problem of learning neural networks from queries. In this work we give the first polynomial-time algorithm for learning arbitrary one hidden layer neural networks activations provided black-box access to the network. Formally, we show that if F is an arbitrary one hidden layer neural network with ReLU activations, there is an algorithm with query complexity and running time that is polynomial in all parameters that outputs a network F' achieving low square loss relative to F with respect to the Gaussian measure. While a number of works in the security literature have proposed and empirically demonstrated the effectiveness of certain algorithms for this problem, ours is the first with fully polynomial-time guarantees of efficiency even for worst-case networks (in particular our algorithm succeeds in the overparameterized setting).

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 22 of its 30 references that are in the map. First posted on arXiv 8 Nov 2021.

Builds on

22 of 30 references.

References · 22

  1. 2016Practical Black-Box Attacks against Machine Learningcited by 893
  2. 2016Stealing Machine Learning Models via Prediction APIscited by 602
  3. 2019High Accuracy and High Fidelity Extraction of Neural Networkscited by 208
  4. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  5. 2018Model Reconstruction from Model Explanationscited by 84
  6. 2019Reverse-Engineering Deep ReLU Networkscited by 81
  7. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  8. 2020Cryptanalytic Extraction of Neural Network Modelscited by 65
  9. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  10. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  11. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  12. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
10 more
  1. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  2. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  3. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  4. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  5. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  6. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  7. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
  8. 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
  9. 2021An Exact Poly-Time Membership-Queries Algorithm for Extraction a three-Layer ReLU Networkcited by 11
  10. 2020Span Recovery for Deep Neural Networks with Applications to Input Obfuscationcited by 4

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 3; 2024: 1; 2025: 1.

6 papers.

  1. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  2. 2023A faster and simpler algorithm for learning shallow networkscited by 7
  3. 2022Global Convergence of SGD On Two Layer Neural Netscited by 5
  4. 2023Global Convergence of SGD For Logistic Loss on Two Layer Neural Netscited by 3
  5. 2025Provably Extracting the Features from a General Superpositioncited by 1
  6. 2024Sequencing the Neurome: Towards Scalable Exact Parameter Reconstruction of Black-Box Neural Networkscited by 0