Search papers, labs, and topics across Lattice.
This paper investigates the agnostic learning of general ReLUs under Gaussian distribution, focusing on an interactive learning setting with query access to labels. The authors present a computationally efficient learner that requires significantly fewer black-box label queries than previous methods, achieving an error rate of \(O(opt)+ε\). Their findings reveal that query access is essential for improving label complexity in active learning scenarios, with established near-optimality of their query complexity bound.
Achieving robust regression of general ReLUs with a dramatically reduced query complexity could redefine the efficiency of active learning strategies.
We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses $poly(d,1/ε)$ labeled examples and outputs a hypothesis with error $O(opt)+ε$, where $opt$ is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses $d polylog(1/ε)+\tilde{O}(\min\{1/p, 1/ε\})$ black-box label queries, where $p$ is the bias of the target function, and achieves error $O(opt)+ε$. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires $\tildeΩ(d/ε)$ labels, unless it draws a super-polynomial number of unlabeled examples.
