Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
This solves a fundamental problem in robust machine learning for researchers and practitioners dealing with noisy data, advancing beyond incremental progress by addressing previously unstudied general cases.
The paper tackles the problem of PAC learning general halfspaces with Massart noise under the Gaussian distribution, removing prior assumptions of homogeneity and noise rate strictly less than 1/2, and provides algorithms with sample and computational complexities of d^{O_η(log(1/γ))}poly(1/ε) for η<1/2 and O_ε(1)d^{O(log(1/ε))} for η=1/2, along with matching SQ lower bounds.
We study the problem of PAC learning halfspaces on $\mathbb{R}^d$ with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the label of each point $\mathbf{x}$ with unknown probability $η(\mathbf{x}) \leq η$, for some parameter $η\in [0,1/2]$. The goal is to find a hypothesis with misclassification error of $\mathrm{OPT} + ε$, where $\mathrm{OPT}$ is the error of the target halfspace. This problem had been previously studied under two assumptions: (i) the target halfspace is homogeneous (i.e., the separating hyperplane goes through the origin), and (ii) the parameter $η$ is strictly smaller than $1/2$. Prior to this work, no nontrivial bounds were known when either of these assumptions is removed. We study the general problem and establish the following: For $η<1/2$, we give a learning algorithm for general halfspaces with sample and computational complexity $d^{O_η(\log(1/γ))}\mathrm{poly}(1/ε)$, where $γ=\max\{ε, \min\{\mathbf{Pr}[f(\mathbf{x}) = 1], \mathbf{Pr}[f(\mathbf{x}) = -1]\} \}$ is the bias of the target halfspace $f$. Prior efficient algorithms could only handle the special case of $γ= 1/2$. Interestingly, we establish a qualitatively matching lower bound of $d^{Ω(\log(1/γ))}$ on the complexity of any Statistical Query (SQ) algorithm. For $η= 1/2$, we give a learning algorithm for general halfspaces with sample and computational complexity $O_ε(1) d^{O(\log(1/ε))}$. This result is new even for the subclass of homogeneous halfspaces; prior algorithms for homogeneous Massart halfspaces provide vacuous guarantees for $η=1/2$. We complement our upper bound with a nearly-matching SQ lower bound of $d^{Ω(\log(1/ε))}$, which holds even for the special case of homogeneous halfspaces.