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

We study the problem of computationally and label efficient PAC active learning d-dimensional halfspaces with Tsybakov Noise (Tsybakov, 2004) under structured unlabeled data distributions. Inspired by Diakonikolas et al. (2020c), 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 Õ(d(¹_ϵ ) ^{3 8 α − − 6α 1} )¹, under the assumption that the Tsybakov noise parameter α ∈ (¹₃, 1], which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms (Diakonikolas et al., 2020b; Zhang and Li, 2021) and the information-theoretic lower bound in this setting.