Skip to yearly menu bar Skip to main content


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

Yinan Li · Chicheng Zhang

MR1 & MR2 - Number 63
[ ]
Fri 3 May 8 a.m. PDT — 8:30 a.m. PDT

Abstract: 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 $\tilde{O}(d (\frac{1}{\epsilon})^{\frac{8-6\alpha}{3\alpha-1}})$, under the assumption that the Tsybakov noise parameter $\alpha \in (\frac13, 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.

Live content is unavailable. Log in and register to view live content