Attribute-Efficient Learning of Halfspaces with Malicious Noise:\n Near-Optimal Label Complexity and Noise Tolerance

2020/06/06 by Jie Shen, Chicheng Zhang, Shen, Jie +1 · 2 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Big data #Binary logarithm #Bounded function #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #Data mining #Discrete mathematics #Empirical risk minimization #FOS: Computer and information sciences #Homogeneous #Imbalanced Data Classification Techniques #Isotropy #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #Mathematical analysis #Mathematics #Noise (video) #Omega #Physics #Sample complexity #Statistical Methods and Inference #Tilde #cs.DS #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2006.03781

published in arXiv (Cornell University) (Cornell University) · V1/V2 had a problematic argument on polynomial-time solvability of a form of sparse principal component analysis. V3 fixed it by using a new approach based on semidefinite programming. V4/V5 polishes the writing and is accepted to ALT 2021

openalex publication_date 2020/06/06 · arxiv created 2021/03/02 · arxiv updated 2021/03/03 · openalex created_date 2021/04/13 · openalex updated_date 2026/08/06

Abstract

This paper is concerned with computationally efficient learning of\nhomogeneous sparse halfspaces in \ℝ^d under noise. Though recent\nworks have established attribute-efficient learning algorithms under various\ntypes of label noise (e.g. bounded noise), it remains an open question when and\nhow s-sparse halfspaces can be efficiently learned under the challenging\nmalicious noise model, where an adversary may corrupt both the unlabeled\nexamples and the labels. We answer this question in the affirmative by\ndesigning a computationally efficient active learning algorithm with\nnear-optimal label complexity of \O\(s \log⁴ frac d \ε\n\) and noise tolerance \η = \Ω(\ε), where \ε \∈ (0,\n1) is the target error rate, under the assumption that the distribution over\n(uncorrupted) unlabeled examples is isotropic log-concave. Our algorithm can be\nstraightforwardly tailored to the passive learning setting, and we show that\nthe sample complexity is \O\( frac 1 \ε s² \log⁵ d \)\nwhich also enjoys the attribute efficiency. Our main techniques include\nattribute-efficient paradigms for instance reweighting and for empirical risk\nminimization, and a new analysis of uniform concentration for unbounded data --\nall of them crucially take the structure of the underlying halfspace into\naccount.\n

Citations

• Sparse Principal Component Analysis
• Atomic Decomposition by Basis Pursuit
• The perceptron: A probabilistic model for information storage and organization in the brain.
• An Introduction To Compressive Sampling [A sensing/sampling paradigm that goes against the common knowledge in data acquisition]
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• Recent Advances in Algorithmic High-Dimensional Robust Statistics

Cited by

• Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
• Immunological Density Shapes Recovery Trajectories in Long COVID

Related

• Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate