Learning Halfspaces with Malicious Noise

By Adam R. Klivans, Philip M. Long, Rocco A. Servedio. 2009

145 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “[KLS09] gave the first efficient algorithms for robustly classification under the assumption that the distribution of the good data is isotropic and log-concave.”
Certified Defenses for Data Poisoning Attacks (2017, background): “…been exhibited for mean and covariance estimation and clustering (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017), classiﬁcation (Klivans et al., 2009; Awasthi et al., 2014), regression (Nasrabadi et al., 2011; Nguyen and Tran, 2013; Chen et al., 2013; Bhatia et al., 2015) and…”
Learning Discrete Distributions from Untrusted Batches (2017, background): “Other learning problems, such as robustly learning halfspaces [KLS09], robust linear regression [BJK15] and more general convex optimization [CSV17] have also been considered in similar settings where some fraction of the data is drawn from a distribution of interest, and no assumptions are made…”
Robust Estimators in High Dimensions without the Computational Intractability (2016, background): “A sequence of works studied this problem for the class of halfspaces [44], [45], [46] in the setting where the underlying distribution is a Gaussian, culminating in the work of Awasthi et al. [47], who gave an efficient algorithm that finds a halfspace with agreement O(ε).”
Learning from untrusted data (2016, background): “Klivans et al. (2009) and Awasthi et al. (2014) provide strong bounds for robust classification in high dimensions for isotropic log-concave distributions.”
Adversarial Label Flips Attack on Support Vector Machines (2012, background): “Most of previous work either assume that labels are erased at random [3], or they restrict the underlying distribution of label noise to certain families without considering the attack strategy from the adversary’s perspective [5, 8].”
Robustness and generalization (2010, background): “Learning from samples with outliers has attracted increasing attention in the recent decade (Klivans et al. 2009; Xu et al. 2010a; Yu et al. 2011, and many others).”
Efficient Algorithms for Outlier-Robust Regression (2018, background): “unsupervised learning and efficient learning of halfspaces (Klivans et al., 2009; Diakonikolas et al., 2017) with respect to malicious or “nasty noise” in classification.”
On the Practicality of Integrity Attacks on Document-Level Sentiment Analysis (2014, background): “By training on the feature vectors, the learning system associates each class with particular features.”
The power of localization for efficiently learning linear separators with noise (2013, methodology): “[35] analyzed another approach to limiting the coordination of the noisy examples: they proposed an outlier removal procedure that used PCA to find any direction u onto which projecting the training data led to suspiciously high variance, and removing examples with the most extreme values after proj”
Intrinsic Evaluation of Summarization Datasets (2020, background): “We do note that research in the machine learning and learning theory communities shows that models both theoretically and empirically do substantially worse when trained using low quality examples, even when the examples are not strictly adversarially chosen (Klivans et al., 2009; Biggio et al., 201”
Learning geometric concepts with nasty noise (2017, methodology): “ for isotropic log-concave distributions. Origin-centered LTFsare theonly concept class for whichefﬁcient malicious learning algorithms were previously known. At the technical level, the algorithm of [KLS09] uses a simple outlier removal method to approximate the degree-1 Chow parameters, and then ﬁ”
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017, background): “Introduction What are the fundamental properties that allow one to robustly learn from a dataset, even if some fraction of that dataset consists of arbitrarily corrupted data? While much work has been done in the setting of noisy data, or for restricted families of outliers, it is only recently that”
Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses (2020, background): “[164] presents the first algorithm for learning a linear classifier under adversarial noise.”
Mixture models, robustness, and sum of squares proofs (2017, background): “There has been a long line of work on making algorithms tolerant to error in supervised settings [41, 66], especially for learning halfspaces [4, 28, 42, 60], and for problems such as PCA [15, 16, 47, 70].”
Learning Halfspaces and Neural Networks with Random Initialization (2015, background): “When the label noise is adversarial, the halfspace can be learned if the data distribution is isotropic log-concave and the fraction of labels being corrupted is bounded by a small quantity (Kalai et al., 2008; Klivans et al., 2009; Awasthi et al., 2014).”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, background): “Recent work in the theoretical computer science community [KLS09, ABL14, DKK + 16, LRV16] gave the ﬁrst eﬃcient robust estimators for basic high-dimensional statistical tasks, including learning linear separators, and mean and covariance estimation.”