Fetching the paper…
Reading the bibliography…
We study the problem of {\em distribution-independent} PAC learning of halfspaces in the presence of Massart noise.
Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator
A. Dvoretzky, J. Kiefer, and J. Wolfowitz · 1956
Earlier work this paper cites.
The Perceptron: a probabilistic model for information storage and organization in the brain
F. Rosenblatt · 1958
Earlier work this paper cites.
Estimation of Dependences Based on Empirical Data: Springer Series in Statistics
V. Vapnik · 1982
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Learning from noisy examples
D. Angluin and P. Laird · 1988
Earlier work this paper cites.
Types of noise in data for concept learning
R. H. Sloan · 1988
Earlier work this paper cites.
Decision theoretic generalizations of the PAC model for neural net and other learning applications
D. Haussler · 1992
Earlier work this paper cites.
Corrigendum to types of noise in data for concept learning
R. H. Sloan · 1992
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
M. J. Kearns · 1993
Earlier work this paper cites.
Learning linear threshold functions in the presence of classification noise
T. Bylander · 1994
Earlier work this paper cites.
Toward Efficient Agnostic Learning
M. Kearns, R. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
How fast can a threshold gate learn?
W. Maass and G. Turan · 1994
Earlier work this paper cites.
A formal model of hierarchical concept learning
R. Rivest and R. Sloan · 1994
Earlier work this paper cites.
A polynomial-time algorithm for learning noisy linear threshold functions
A. Blum, A. M. Frieze, R. Kannan, and S. Vempala · 1996
Earlier work this paper cites.
Pac Learning, Noise, and Geometry
R. H. Sloan · 1996
Cited alongside, same era.
A polynomial time algorithm for learning noisy linear threshold functions
A. Blum, A. Frieze, R. Kannan, and S. Vempala · 1997
Cited alongside, same era.
Learning noisy perceptrons by a perceptron in polynomial time
E. Cohen · 1997
Cited alongside, same era.
Efficient noise-tolerant learning from statistical queries
M. J. Kearns · 1998
Cited alongside, same era.
Machine learning: My favorite results, directions, and open problems
A. Blum · 2003
Cited alongside, same era.
Optimal outlier removal in high-dimensional spaces
J. Dunagan and S. Vempala · 2004
Cited alongside, same era.
Learning and 1-bit compressed sensing under asymmetric noise
P. Awasthi, M. F. Balcan, N. Haghtalab, and H. Zhang · 2016
Later among the works it cites.
Complexity theoretic limitations on learning halfspaces
A. Daniely · 2016
Later among the works it cites.
Robust estimators in high dimensions without the computational intractability
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2016
Later among the works it cites.
Introductory lectures on stochastic convex optimization
J. C. Duchi · 2016
Later among the works it cites.
Agnostic estimation of mean and covariance
K. A. Lai, A. B. Rao, and S. Vempala · 2016
Later among the works it cites.
The power of localization for efficiently learning linear separators with noise
P. Awasthi, M. F. Balcan, and P. M. Long · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A simple polynomial-time rescaling algorithm for solving linear programs
J. Dunagan and S. Vempala · 2004
Cited alongside, same era.
Robust estimators are hard to compute
T. Bernholt · 2006
Cited alongside, same era.
New results for learning noisy parities and halfspaces
V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami · 2006
Cited alongside, same era.
Hardness of learning halfspaces with noise
V. Guruswami and P. Raghavendra · 2006
Cited alongside, same era.
Risk bounds for statistical learning
P. Massart and E. Nedelec · 2006
Cited alongside, same era.
Learning halfspaces with malicious noise
A. Klivans, P. Long, and R. Servedio · 2009
Cited alongside, same era.
Being robust (in high dimensions) can be practical
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2017
Later among the works it cites.
Revisiting perceptron: Efficient and label-optimal learning of halfspaces
S. Yan and C. Zhang · 2017
Later among the works it cites.
A hitting time analysis of stochastic gradient langevin dynamics
Y. Zhang, P. Liang, and M. Charikar · 2017
Later among the works it cites.
Robustly learning a gaussian: Getting optimal error, efficiently
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2018
Later among the works it cites.
Learning geometric concepts with nasty noise
I. Diakonikolas, D. M. Kane, and A. Stewart · 2018
Later among the works it cites.
Efficient algorithms for outlier-robust regression
A. R. Klivans, P. K. Kothari, and R. Meka · 2018
Later among the works it cites.
Sever: A robust meta-algorithm for stochastic optimization
I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and Alistair Stewart · 2019
Closest in time.
Efficient algorithms and lower bounds for robust linear regression
I. Diakonikolas, W. Kong, and A. Stewart · 2019
Closest in time.