Efficiently Learning Any One Hidden Layer ReLU Network From Queries
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).
Code (0)
등록된 구현이 없습니다.
Tasks
Model extractionSimilar Papers 제목 키워드 기반
Efficiently Learning One Hidden Layer ReLU Networks From Queries
While the problem of PAC learning neural networks from samples has received considerable attention in recent years, in certain settings like model extraction attacks, it is reasonable to imagine having more than just the…
Model extractionPAC learningHardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
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. No general SQ lower bounds were known for learni…
PAC learningVocal Bursts Valence PredictionOn the Principles of Deep Feedforward ReLU Networks
The architecture of deep feedforward neural networks is ubiquitous in deep learning, either as a whole system or as a subnetwork of other architectures, and thus its mechanism is a key ingredient of the black box of neur…
Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting
Deep neural networks (DNNs) are valuable assets, yet their public accessibility raises security concerns about parameter extraction by malicious actors. Recent work by Carlini et al. (crypto'20) and Canales-Mart\'inez et…
CryptanalysisNo Spurious Local Minima in a Two Hidden Unit ReLU Network
Deep learning models can be efficiently optimized via stochastic gradient descent, but there is little theoretical evidence to support this. A key question in optimization is to understand when the optimization landscape…
Vocal Bursts Valence Prediction