An Exact Poly-Time Membership-Queries Algorithm for Extraction a three-Layer ReLU Network

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