Fetching the paper…
Reading the bibliography…
We study the efficient learnability of geometric concept classes - specifically, low-degree polynomial threshold functions (PTFs) and intersections of halfspaces - when a fraction of the data is adversarially corrupted.
On the characterization of threshold functions
C.K. Chow · 1961
Earlier work this paper cites.
Threshold Logic: A Synthesis Approach
M. Dertouzos · 1965
Earlier work this paper cites.
Perceptrons: an introduction to computational geometry
M. Minsky and S. Papert · 1968
Earlier work this paper cites.
Threshold logic and its applications
S. Muroga · 1971
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Learning disjunctions of conjunctions
L. Valiant · 1985
Earlier work this paper cites.
Harmonic analysis of polynomial threshold functions
J. Bruck · 1990
Earlier work this paper cites.
A polynomial time algorithm that learns two hidden unit nets
E. Baum · 1991
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.
Learning in the presence of malicious errors
M. Kearns and M. Li · 1993
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.
Distributional and L q L^{q} norm inequalities for polynomials over convex bodies in R n R^{n}
A. Carbery and J. Wright · 2001
Earlier work this paper cites.
Combinatorial methods in density estimation
L. Devroye and G. Lugosi · 2001
Earlier work this paper cites.
PAC Learning with Nasty Noise
N. Bshouty, N. Eiron, and E. Kushilevitz · 2002
Cited alongside, same era.
Agnostically learning halfspaces
A. Kalai, A. Klivans, Y. Mansour, and R. Servedio · 2008
Cited alongside, same era.
Learning geometric concepts via Gaussian surface area
A. Klivans, R. O’Donnell, and R. Servedio · 2008
Cited alongside, same era.
Regularity, Boosting and Efficiently Simulating every High Entropy Distribution
L. Trevisan, M. Tulsiani, and S. Vadhan · 2008
Cited alongside, same era.
Learning Halfspaces with Malicious Noise
A. Klivans, P. Long, and R. Servedio · 2009
Cited alongside, same era.
Baum’s algorithm learns intersections of halfspaces with respect to log-concave distributions
A. R. Klivans, P. M. Long, and A. K. Tang · 2009
Cited alongside, same era.
From average case complexity to improper learning complexity
A. Daniely, N. Linial, and S. S.-Shwartz · 2014
Later among the works it cites.
Average sensitivity and noise sensitivity of polynomial threshold functions
I. Diakonikolas, P. Raghavendra, R. A. Servedio, and L. Y. Tan · 2014
Later among the works it cites.
Bounding the sensitivity of polynomial threshold functions
P. Harsha, A. R. Klivans, and R. Meka · 2014
Later among the works it cites.
The average sensitivity of an intersection of half spaces
D. M. Kane · 2014
Later among the works it cites.
The correct exponent for the gotsman-linial conjecture
D. M. Kane · 2014
Later among the works it cites.
A PTAS for agnostically learning halfspaces
A. Daniely · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
I. Diakonikolas, P. Harsha, A. Klivans, R. Meka, P. Raghavendra, R. A. Servedio, and L. Y. Tan · 2010
Cited alongside, same era.
Learning convex concepts from gaussian distributions with PCA
S. Vempala · 2010
Cited alongside, same era.
A random-sampling-based algorithm for learning intersections of halfspaces
S. Vempala · 2010
Cited alongside, same era.
The gaussian surface area and noise sensitivity of degree- d polynomial threshold functions
D. M. Kane · 2011
Cited alongside, same era.
Learning Poisson Binomial Distributions
C. Daskalakis, I. Diakonikolas, and R.A. Servedio · 2012
Cited alongside, same era.
The inverse shapley value problem
A. De, I. Diakonikolas, and R. A. Servedio · 2012
Cited alongside, same era.
Learning from satisfying assignments
A. De, I. Diakonikolas, and R. Servedio · 2015
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.
I. Diakonikolas, D. M. Kane, and A. Stewart · 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
Closest in time.
Being robust (in high dimensions) can be practical
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2017
Closest in time.
Robustly learning a gaussian: Getting optimal error, efficiently
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2017
Closest in time.