Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise

We give a computationally-efficient PAC active learning algorithm for\n$d$-dimensional homogeneous halfspaces that can tolerate Massart noise (Massart\nand N\\'ed\\'elec, 2006) and Tsybakov noise (Tsybakov, 2004). Specialized to the\n$\\eta$-Massart noise setting, our algorithm achieves an\ninformation-theoretically near-optimal label complexity of $\\tilde{O}\\left(\n\\frac{d}{(1-2\\eta)^2} \\mathrm{polylog}(\\frac1\\epsilon) \\right)$ under a wide\nrange of unlabeled data distributions (specifically, the family of "structured\ndistributions" defined in Diakonikolas et al. (2020)). Under the more\nchallenging Tsybakov noise condition, we identify two subfamilies of noise\nconditions, under which our efficient algorithm provides label complexity\nguarantees strictly lower than passive learning algorithms.\n