2021/05/20 by Amit Daniely, Daniely, Amit, Elad Granot +1 · 3 citations
Computer Science · #Adversarial Robustness in Machine Learning #Anomaly Detection Techniques and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and ELM #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2105.09673
openalex publication_date 2021/05/20 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We consider the natural problem of learning a ReLU network from queries,\nwhich was recently remotivated by model extraction attacks. In this work, we\npresent a polynomial-time algorithm that can learn a depth-two ReLU network\nfrom queries under mild general position assumptions. We also present a\npolynomial-time algorithm that, under mild general position assumptions, can\nlearn a rich class of depth-three ReLU networks from queries. For instance, it\ncan learn most networks where the number of first layer neurons is smaller than\nthe dimension and the number of second layer neurons. These two results\nsubstantially improve state-of-the-art: Until our work, polynomial-time\nalgorithms were only shown to learn from queries depth-two networks under the\nassumption that either the underlying distribution is Gaussian (Chen et al.\n(2021)) or that the weights matrix rows are linearly independent (Milli et al.\n(2019)). For depth three or more, there were no known poly-time results.\n