Fetching the paper…
Reading the bibliography…
We present a private learner for halfspaces over an arbitrary finite domain $X\subset \mathbb{R}^d$ with sample complexity $mathrm{poly}(d,2^{\log^*|X|})$.
Convex figures
I. M. Yaglom and V. G. Boltyanskiǐ · 1961
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1972
Earlier work this paper cites.
Mathematics and the picturing of data
J. W. Tukey · 1975
Earlier work this paper cites.
Algorithms in Combinatorial Geometry
H. Edelsbrunner · 1987
Earlier work this paper cites.
Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
B. Gärtner and E. Welzl · 1994
Earlier work this paper cites.
Combinatorial variability of vapnik-chervonenkis classes with applications to sample compression schemes
S. Ben-David and A. Litman · 1998
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
M. J. Kearns · 1998
Earlier work this paper cites.
Practical privacy: The SuLQ framework
A. Blum, C. Dwork, F. McSherry, and K. Nissim · 2005
Earlier work this paper cites.
Mechanism design via differential privacy
F. McSherry and K. Talwar · 2007
Earlier work this paper cites.
A learning theory approach to non-interactive database privacy
A. Blum, K. Ligett, and A. Roth · 2008
Earlier work this paper cites.
A simple polynomial-time rescaling algorithm for solving linear programs
J. Dunagan and S. Vempala · 2008
Cited alongside, same era.
Differential privacy and robust statistics
C. Dwork and J. Lei · 2009
Cited alongside, same era.
Boosting and differential privacy
C. Dwork, G. N. Rothblum, and S. P. Vadhan · 2010
Cited alongside, same era.
Approximate centerpoints with proofs
G. L. Miller and D. R. Sheehy · 2010
Cited alongside, same era.
Sample complexity bounds for differentially private learning
K. Chaudhuri and D. Hsu · 2011
Cited alongside, same era.
What can we learn privately?
S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. D. Smith · 2011
Cited alongside, same era.
Learning privately with labeled and unlabeled examples
A. Beimel, K. Nissim, and U. Stemmer · 2015
Later among the works it cites.
Differentially private release and learning of threshold functions
M. Bun, K. Nissim, U. Stemmer, and S. P. Vadhan · 2015
Later among the works it cites.
Sample complexity bounds on differentially private learning via communication complexity
V. Feldman and D. Xiao · 2015
Later among the works it cites.
Private learning and sanitization: Pure vs. approximate differential privacy
A. Beimel, K. Nissim, and U. Stemmer · 2016
Later among the works it cites.
New Separations in the Complexity of Differential Privacy
M. Bun · 2016
Later among the works it cites.
Order-revealing encryption and the hardness of private learning
M. Bun and M. Zhandry · 2016
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. Beimel, H. Brenner, S. P. Kasiviswanathan, and K. Nissim · 2014
Cited alongside, same era.
Privately solving linear programs
J. Hsu, A. Roth, T. Roughgarden, and J. Ullman · 2014
Cited alongside, same era.
Fast computation of Tukey trimmed regions and median in dimension p > 2 p>2
X. Liu, K. Mosler, and P. Mozharovskyi · 2014
Cited alongside, same era.
Understanding Machine Learning: From Theory to Algorithms
S. Shalev-Shwartz and S. Ben-David · 2014
Cited alongside, same era.
Characterizing the sample complexity of private learners
A. Beimel, K. Nissim, and U. Stemmer
Cited in the paper.
Private learning and sanitization: Pure vs. approximate differential privacy
A. Beimel, K. Nissim, and U. Stemmer
Cited in the paper.
Simultaneous private learning of multiple concepts
M. Bun, K. Nissim, and U. Stemmer · 2016
Later among the works it cites.
Private PAC learning implies finite littlestone dimension
N. Alon, R. Livni, M. Malliaris, and S. Moran · 2018
Later among the works it cites.
Model-agnostic private learning
R. Bassily, A. G. Thakurta, and O. D. Thakkar · 2018
Later among the works it cites.
Privacy-preserving prediction
C. Dwork and V. Feldman · 2018
Later among the works it cites.