Attribute-Efficient Learning of Halfspaces with Malicious Noise:
  Near-Optimal Label Complexity and Noise Tolerance
  This paper is concerned with computationally efficient learning of
homogeneous sparse halfspaces in $\mathbb{R}^d$ under noise. Though recent
works have established attribute-efficient learning algorithms under various
types of label noise (e.g. bounded noise), it remains an open question when and
how $s$-sparse halfspaces can be efficiently learned under the challenging
malicious noise model, where an adversary may corrupt both the unlabeled
examples and the labels. We answer this question in the affirmative by
designing a computationally efficient active learning algorithm with
near-optimal label complexity of $\tilde{O}\big({s \log^4 \frac d \epsilon}
\big)$ and noise tolerance $\eta = \Omega(\epsilon)$, where $\epsilon \in (0,
1)$ is the target error rate, under the assumption that the distribution over
(uncorrupted) unlabeled examples is isotropic log-concave. Our algorithm can be
straightforwardly tailored to the passive learning setting, and we show that
the sample complexity is $\tilde{O}\big({\frac 1 \epsilon s^2 \log^5 d} \big)$
which also enjoys the attribute efficiency. Our main techniques include
attribute-efficient paradigms for instance reweighting and for empirical risk
minimization, and a new analysis of uniform concentration for unbounded data --
all of them crucially take the structure of the underlying halfspace into
account.
