The power of localization for efficiently learning linear separators with noise

By Pranjal Awasthi, Maria-Florina Balcan, Philip M. Long. 2013

224 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “Recent work in theoretical computer science has resulted in eﬃcient robust estimators for classical problems such as linear classiﬁcation [KLS09, ABL14], mean and covariance estimation [DKK + 16, LRV16], clustering [CSV17], and regression [BJK15, BJKK17, BDLS17].”
Certified Defenses for Data Poisoning Attacks (2017, background): “…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 crowdsourced data…”
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.”
Learning geometric concepts with nasty noise (2017, methodology): “On the other hand, theO (ε ) bound of [1] holds for the more general family of isotropic log-concave distributions.”
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].”
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.”
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).”
Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners (2017, background): “, see [2, 41, 45]) has studied attacks against specific learners, while our result can be applied to any learner.”
Deep Active Learning for Named Entity Recognition (2017, methodology): “, 2009; Awasthi et al., 2014; Yan & Zhang, 2017; Beygelzimer et al., 2009), classic algorithms and guarantees cannot be generalized to DNNs, which are currently are the state-of-the-art techniques for NER. Owing to the limitations of current theoretical analysis, more practical active learning appli”
Decoupling "when to update" from "how to update" (2017, background): “The effects of noisy labels was vastly studied in many different learning algorithms (see for example the survey in [13]), and various solutions to this problem have been proposed, some of them with theoretically provable bounds, including methods like statistical queries, boosting, bagging and more”
Learning under p-Tampering Attacks (2018, background): “a causative) attacks [4, 36, 42] in which an adversary aims at directing a learner towards generating a hypothesis that performs badly during the test phase.”
Complexity theoretic limitations on learning halfspaces (2015, background): “Better guarantees are known under various assumptions on the marginal distribution [10, 20, 30, 44].”