Sample-Optimal PAC Learning of Halfspaces with Malicious Noise
원문 초록
We study efficient PAC learning of homogeneous halfspaces in $\mathbb{R}^d$ in the presence of malicious noise of Valiant (1985). This is a challenging noise model and only until recently has near-optimal noise tolerance bound been established under the mild condition that the unlabeled data distribution is isotropic log-concave. However, it remains unsettled how to obtain the optimal sample complexity simultaneously. In this work, we present a new analysis for the algorithm of Awasthi et al. (2017) and show that it essentially achieves the near-optimal sample complexity bound of $\tilde{O}(d)$, improving the best known result of $\tilde{O}(d^2)$. Our main ingredient is a novel incorporation of a matrix Chernoff-type inequality to bound the spectrum of an empirical covariance matrix for well-behaved distributions, in conjunction with a careful exploration of the localization schemes of Awasthi et al. (2017). We further extend the algorithm and analysis to the more general and stronger nasty noise model of Bshouty et al. (2002), showing that it is still possible to achieve near-optimal noise tolerance and sample complexity in polynomial time.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Lean Formalization of Generalization Error Bound by Rademacher Complexity
Prospective Learning: Learning for a Dynamic Future
Optimistic Rates for Learning from Label Proportions
Towards a theory of model distillation
SAT-Based PAC Learning of Description Logic Concepts
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
토론
이 논문과 연결된 포럼 글이 아직 없습니다.