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~tsybakov2004optimal under structured unlabeled data distributions. Inspired by~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 O(d (1)^8-63-1), under the assumption that the Tsybakov noise parameter (13, 1], which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~diakonikolas2020polynomial,zhang2021improved and the information-theoretic lower bound in this setting.

Tasks

Reproductions