Fetching the paper…
Reading the bibliography…
We study active learning of homogeneous $s$-sparse halfspaces in $\mathbb{R}^d$ under the setting where the unlabeled data distribution is isotropic log-concave and each label is flipped with probability at most $\eta$ for a parameter $\eta \in \big[0, \frac12\big)$, known as the bounded noise.
The Perceptron: A probabilistic model for information storage and organization in the brain
Frank Rosenblatt · 1958
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
Vladimir Naumovich Vapnik and Alexey Yakovlevich Chervonenkis · 1971
Earlier work this paper cites.
Learning disjunction of conjunctions
Leslie G. Valiant · 1985
Earlier work this paper cites.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm (extended abstract)
Nick Littlestone · 1987
Earlier work this paper cites.
Queries and concept learning
Dana Angluin · 1988
Earlier work this paper cites.
Learning in the presence of malicious errors
Michael J. Kearns and Ming Li · 1988
Earlier work this paper cites.
Types of noise in data for concept learning
Robert H. Sloan · 1988
Earlier work this paper cites.
Learning boolean functions in an infinite attribute space
Avrim Blum · 1990
Earlier work this paper cites.
Corrigendum to types of noise in data for concept learning
Robert H. Sloan · 1992
Earlier work this paper cites.
Learning in the presence of malicious errors
Michael Kearns and Ming Li · 1993
Earlier work this paper cites.
Improving generalization with active learning
David Cohn, Les Atlas, and Richard Ladner · 1994
Earlier work this paper cites.
Toward efficient agnostic learning
Michael J Kearns, Robert E Schapire, and Linda M Sellie · 1994
Earlier work this paper cites.
A formal model of hierarchical concept learning
Ronald L. Rivest and Robert H. Sloan · 1994
Earlier work this paper cites.
A polynomial-time algorithm for learning noisy linear threshold functions
Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala · 1996
Earlier work this paper cites.
Regression shrinkage and selection via the Lasso
Robert Tibshirani · 1996
Earlier work this paper cites.
Atomic decomposition by basis pursuit
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders · 1998
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Statistical Learning Theory
Vladimir Naumovich Vapnik · 1998
Earlier work this paper cites.
Computational sample complexity and attribute-efficient learning
Rocco A. Servedio · 1999
Earlier work this paper cites.
General convergence results for linear discriminant updates
Adam J Grove, Nick Littlestone, and Dale Schuurmans · 2001
Earlier work this paper cites.
The robustness of the p-norm algorithms
Claudio Gentile · 2003
Earlier work this paper cites.
On the generalization ability of on-line learning algorithms
Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile · 2004
Earlier work this paper cites.
Toward attribute efficient learning of decision lists and parities
Adam R. Klivans and Rocco A. Servedio · 2004
Earlier work this paper cites.
Optimal aggregation of classifiers in statistical learning
Alexander B. Tsybakov · 2004
Earlier work this paper cites.
Decoding by linear programming
Emmanuel J. Candès and Terence Tao · 2005
Earlier work this paper cites.
Coarse sample complexity bounds for active learning
Sanjoy Dasgupta · 2005
Earlier work this paper cites.
Compressed sensing
David L. Donoho · 2006
Earlier work this paper cites.
New results for learning noisy parities and halfspaces
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami · 2006
Earlier work this paper cites.
Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions
Philip M. Long and Rocco A. Servedio · 2006
Earlier work this paper cites.
Risk bounds for statistical learning
Pascal Massart and Élodie Nédélec · 2006
Earlier work this paper cites.
Margin based active learning
Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang · 2007
Earlier work this paper cites.
Attribute-efficient and non-adaptive learning of parities and DNF expressions
Vitaly Feldman · 2007
Cited alongside, same era.
The geometry of logconcave functions and sampling algorithms
László Lovász and Santosh Vempala · 2007
Cited alongside, same era.
Online learning: Theory, algorithms, and applications
Shai Shalev-Shwartz and Yoram Singer · 2007
Cited alongside, same era.
Signal recovery from random measurements via orthogonal matching pursuit
Joel A. Tropp and Anna C. Gilbert · 2007
Cited alongside, same era.
1-bit compressive sensing
Petros Boufounos and Richard G. Baraniuk · 2008
Cited alongside, same era.
A simple polynomial-time rescaling algorithm for solving linear programs
John Dunagan and Santosh Vempala · 2008
Cited alongside, same era.
Robust lasso with missing and grossly corrupted observations
Nam H. Nguyen and Trac D. Tran · 2013
Later among the works it cites.
One-bit compressed sensing by linear programming
Yaniv Plan and Roman Vershynin · 2013
Later among the works it cites.
Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach
Yaniv Plan and Roman Vershynin · 2013
Later among the works it cites.
Truncated power method for sparse eigenvalue problems
Xiao-Tong Yuan and Tong Zhang · 2013
Later among the works it cites.
Theory of disagreement-based active learning
Steve Hanneke · 2014
Later among the works it cites.
Near-optimal adaptive compressed sensing
Matthew L. Malloy and Robert D. Nowak · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
High dimensional classification using features annealed independence rules
Jianqing Fan and Yingying Fan · 2008
Cited alongside, same era.
Agnostically learning halfspaces
Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio · 2008
Cited alongside, same era.
Agnostic active learning
Maria-Florina Balcan, Alina Beygelzimer, and John Langford · 2009
Cited alongside, same era.
Iterative hard thresholding for compressed sensing
Thomas Blumensath and Mike E Davies · 2009
Cited alongside, same era.
Analysis of perceptron-based active learning
Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni · 2009
Cited alongside, same era.
Hardness of learning halfspaces with noise
Venkatesan Guruswami and Prasad Raghavendra · 2009
Cited alongside, same era.
Efficient algorithms for robust one-bit compressive sensing
Lijun Zhang, Jinfeng Yi, and Rong Jin · 2014
Later among the works it cites.
Efficient learning of linear separators under bounded noise
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner · 2015
Later among the works it cites.
A PTAS for agnostically learning halfspaces
Amit Daniely · 2015
Later among the works it cites.
Learning and 1-bit compressed sensing under asymmetric noise
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang · 2016
Later among the works it cites.
Active learning - modern learning theory
Maria-Florina Balcan and Ruth Urner · 2016
Later among the works it cites.
Constrained adaptive sensing
Mark A. Davenport, Andrew K. Massimino, Deanna Needell, and Tina Woolf · 2016
Later among the works it cites.
One-bit compressive sensing with norm estimation
Karin Knudson, Rayan Saab, and Rachel Ward · 2016
Later among the works it cites.
The power of localization for efficiently learning linear separators with noise
Pranjal Awasthi, Maria Florina Balcan, and Philip M Long · 2017
Later among the works it cites.
Sample and computationally efficient learning algorithms under s-concave distributions
Maria-Florina Balcan and Hongyang Zhang · 2017
Later among the works it cites.
Exponential decay of reconstruction error from binary measurements of sparse signals
Richard G. Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, and Mary Wootters · 2017
Later among the works it cites.
Near-optimal active learning of halfspaces via query synthesis in the noisy setting
Lin Chen, Hamed Hassani, and Amin Karbasi · 2017
Later among the works it cites.
On the iteration complexity of support recovery via hard thresholding pursuit
Jie Shen and Ping Li · 2017
Later among the works it cites.
Revisiting perceptron: Efficient and label-optimal learning of halfspaces
Songbai Yan and Chicheng Zhang · 2017
Later among the works it cites.
A hitting time analysis of stochastic gradient langevin dynamics
Yuchen Zhang, Percy Liang, and Moses Charikar · 2017
Later among the works it cites.
A tight bound of hard thresholding
Jie Shen and Ping Li · 2018
Later among the works it cites.
High-Dimensional Probability: An Introduction with Applications in Data Science
Roman Vershynin · 2018
Later among the works it cites.
Efficient active learning of sparse halfspaces
Chicheng Zhang · 2018
Later among the works it cites.
Distribution-independent PAC learning of halfspaces with massart noise
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos · 2019
Later among the works it cites.
Nearly tight bounds for robust proper learning of halfspaces with a margin
Ilias Diakonikolas, Daniel Kane, and Pasin Manurangsi · 2019
Later among the works it cites.
A modern introduction to online learning
Francesco Orabona · 2019
Later among the works it cites.
Adaptive hard thresholding for near-optimal consistent robust regression
Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, and Prateek Jain · 2019
Later among the works it cites.
High-dimensional statistics: A non-asymptotic viewpoint
Martin J. Wainwright · 2019
Later among the works it cites.
Learning halfspaces with Massart noise under structured distributions
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis · 2020
Closest in time.
Jie Shen and Chicheng Zhang · 2020
Closest in time.