Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach

Abstract

We study the problem of computationally and label efficient PAC active learning $d$-dimensional halfspaces with Tsybakov Noise~\citep{tsybakov2004optimal} under structured unlabeled data distributions. Inspired by~\cite{diakonikolas2020learning}, we prove that any approximate first-order stationary point of a smooth nonconvex loss function yields a halfspace with a low excess error guarantee. In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of $\tilde{O}(d(\frac{1}{\hat{I}}\mu {)}^{\frac{8-6\hat{I}\pm }{3\hat{I}\pm -1}})$, under the assumption that the Tsybakov noise parameter $\hat{I}\pm \in (\frac{1}{3},1]$, which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the information-theoretic lower bound in this setting.

29 pages