Fetching the paper…
Reading the bibliography…
We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best known non-private algorithms.
M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization , Combinatorica 1
1981
Earlier work this paper cites.
William B Johnson, Extensions of lipschitz mappings into a hilbert space , Contemp. Math. 26
1984
Earlier work this paper cites.
N. Z. Shor, Quadratic optimization problems , Izv. Akad. Nauk SSSR Tekhn. Kibernet. (1987), no. 1, 128–139, 222. MR 939596
1987
Earlier work this paper cites.
Yurii Nesterov, Squared functional systems and optimization problems , High performance optimization, Appl. Optim., vol. 33, Kluwer Acad. Publ., Dordrecht, 2000, pp. 405–440. MR 1748764
2000
Earlier work this paper cites.
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, California Institute of Technology, 2000
2000
Earlier work this paper cites.
Jean B. Lasserre, New positive semidefinite relaxations for nonconvex quadratic programs , Advances in convex analysis and global optimization (Pythagorion, 2000), Nonconvex Optim. Appl., vol. 54, Kluwer Acad. Publ., Dordrecht, 2001, pp. 319–331. MR 1846160
2001
Earlier work this paper cites.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith, Calibrating noise to sensitivity in private data analysis , Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings (Shai Halevi and Tal Rabin, eds.), Lecture Notes in Computer Science, vol. 3876, Springer, 2006, pp. 265–284
2006
Earlier work this paper cites.
Sanjeev Arora and Satyen Kale, A combinatorial, primal-dual approach to semidefinite programs , Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 227–236
2007
Earlier work this paper cites.
Frank McSherry and Kunal Talwar, Mechanism design via differential privacy , 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), IEEE, 2007, pp. 94–103
2007
Earlier work this paper cites.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith, Smooth sensitivity and sampling in private data analysis , STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 75–84. MR 2402430
2007
Earlier work this paper cites.
Cynthia Dwork and Jing Lei, Differential privacy and robust statistics , STOC’09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, ACM, New York, 2009, pp. 371–380. MR 2780083
2009
Earlier work this paper cites.
Ankur Moitra and Gregory Valiant, Settling the polynomial learnability of mixtures of gaussians , 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, IEEE, 2010, pp. 93–102
2010
Earlier work this paper cites.
David Steurer, Fast sdp algorithms for constraint satisfaction problems , Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 2010, pp. 684–697
2010
Earlier work this paper cites.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate, Differentially private empirical risk minimization. , Journal of Machine Learning Research 12
2011
Earlier work this paper cites.
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications , Physical Review E 84
2011
Earlier work this paper cites.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta, Private convex empirical risk minimization and high-dimensional regression , Conference on Learning Theory, JMLR Workshop and Conference Proceedings, 2012, pp. 25–1
2012
Earlier work this paper cites.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate, Stochastic gradient descent with differentially private updates , 2013 IEEE global conference on signal and information processing, IEEE, 2013, pp. 245–248
2013
Earlier work this paper cites.
Raef Bassily, Adam Smith, and Abhradeep Thakurta, Private empirical risk minimization: Efficient algorithms and tight error bounds , 2014 IEEE 55th annual symposium on foundations of computer science, IEEE, 2014, pp. 464–473
2014
Earlier work this paper cites.
Laurent Massoulié, Community detection thresholds and the weak ramanujan property , Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014, pp. 694–703
2014
Earlier work this paper cites.
Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall, Exact recovery in the stochastic block model , IEEE Transactions on information theory 62
2015
Earlier work this paper cites.
Christian Borgs, Jennifer Chayes, and Adam Smith, Private graphon estimation for sparse graphs , Advances in Neural Information Processing Systems 28
2015
Earlier work this paper cites.
Elchanan Mossel, Joe Neeman, and Allan Sly, Consistency thresholds for the planted bisection model , Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 69–75
2015
Cited alongside, same era.
Olivier Guédon and Roman Vershynin, Community detection in sparse networks via Grothendieck’s inequality , Probab. Theory Related Fields 165
2016
Cited alongside, same era.
Kevin A. Lai, Anup B. Rao, and Santosh S. Vempala, Agnostic estimation of mean and covariance , IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA (Irit Dinur, ed.), IEEE Computer Society, 2016, pp. 665–674
2016
Cited alongside, same era.
Ankur Moitra, William Perry, and Alexander S Wein, How robust are reconstruction thresholds for community detection? , Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 828–841
2016
Cited alongside, same era.
Tommaso d’Orsi, Pravesh K. Kothari, Gleb Novikov, and David Steurer, Sparse PCA: algorithms, adversarial perturbations and certificates , 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 (Sandy Irani, ed.), IEEE, 2020, pp. 553–564
2020
Later among the works it cites.
Yingjie Fei and Yudong Chen, Achieving the Bayes error rate in synchronization and block models by SDP, robustly , IEEE Trans. Inform. Theory 66
2020
Later among the works it cites.
Andres Munoz, Umar Syed, Sergei Vassilvtiskii, and Ellen Vitercik, Private optimization without constraint violations , International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 2557–2565
2021
Later among the works it cites.
David Steurer and Stefan Tiegel, Sos degree reduction with applications to clustering and robust moment estimation , Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, pp. 374–393
2021
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Andrea Montanari and Subhabrata Sen, Semidefinite programs on sparse random graphs and their application to community detection , Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 814–827
2016
Cited alongside, same era.
2016
Cited alongside, same era.
Emmanuel Abbe, Community detection and stochastic block models: recent developments , The Journal of Machine Learning Research 18
2017
Cited alongside, same era.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant, Learning from untrusted data , Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 47–60
2017
Cited alongside, same era.
Oded Regev and Aravindan Vijayaraghavan, On learning mixtures of well-separated gaussians , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 85–96
2017
Cited alongside, same era.
Di Wang, Minwei Ye, and Jinhui Xu, Differentially private empirical risk minimization revisited: Faster and more general , Advances in Neural Information Processing Systems 30
2017
Cited alongside, same era.
Christian Borgs, Jennifer Chayes, Adam Smith, and Ilias Zadik, Revealing network structure, confidentially: Improved rates for node-private graphon estimation , 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2018, pp. 533–543
2018
Cited alongside, same era.
Samuel B. Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 (Ilias Diakonikolas, David Kempe, and Monika Henzinger, eds.), ACM, 2018, pp. 1021–1034
2018
Cited alongside, same era.
Later among the works it cites.
Hassan Ashtiani and Christopher Liaw, Private and polynomial time algorithms for learning gaussians and beyond , Proceedings of Thirty Fifth Conference on Learning Theory (Po-Ling Loh and Maxim Raginsky, eds.), Proceedings of Machine Learning Research, vol. 178, PMLR, 02–05 Jul 2022, pp. 1075–1076
2022
Later among the works it cites.
Learning with privacy at scale , https://docs-assets.developer.apple.com/ml-research/papers/learning-with-privacy-at-scale.pdf , 2017, Accessed: 2022-11-06
2022
Later among the works it cites.
Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala, Robustly learning mixtures of k arbitrary gaussians , STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 (Stefano Leonardi and Anupam Gupta, eds.), ACM, 2022, pp. 1234–1247
2022
Later among the works it cites.
Jingqiu Ding, Tommaso d’Orsi, Rajai Nasser, and David Steurer, Robust recovery for stochastic block models , 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 387–394
2022
Later among the works it cites.
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas, Robust sparse mean estimation via sum of squares , Conference on Learning Theory, 2-5 July 2022, London, UK (Po-Ling Loh and Maxim Raginsky, eds.), Proceedings of Machine Learning Research, vol. 178, PMLR, 2022, pp. 4703–4763
2022
Later among the works it cites.
Tackling urban mobility with technology , https://europe.googleblog.com/2015/11/tackling-urban-mobility-with-technology.html , 2015, Accessed: 2022-11-06
2022
Later among the works it cites.
Samuel B Hopkins, Gautam Kamath, and Mahbod Majid, Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism , Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1406–1417
2022
Later among the works it cites.
Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker, Private robust estimation by stabilizing convex relaxations , Conference on Learning Theory, 2-5 July 2022, London, UK (Po-Ling Loh and Maxim Raginsky, eds.), Proceedings of Machine Learning Research, vol. 178, PMLR, 2022, pp. 723–777
2022
Later among the works it cites.
Xiyang Liu, Weihao Kong, and Sewoong Oh, Differential privacy and robust statistics in high dimensions , Conference on Learning Theory, PMLR, 2022, pp. 1167–1246
2022
Later among the works it cites.
Allen Liu and Jerry Li, Clustering mixtures with almost optimal separation in polynomial time , Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1248–1261
2022
Later among the works it cites.
Allen Liu and Ankur Moitra, Minimax rates for robust community detection , CoRR abs/2207.11903
2022
Later among the works it cites.
Mohamed M. Seif, Dung Nguyen, Anil Vullikanti, and Ravi Tandon, Differentially private community detection for stochastic block models , International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA (Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, eds.), Proceedings of Machine Learning Research, vol. 162, PMLR, 2022, pp. 15858–15894
2022
Later among the works it cites.
Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer, Friendlycore: Practical differentially private aggregation , International Conference on Machine Learning, PMLR, 2022, pp. 21828–21863
2022
Later among the works it cites.
Disclosure avoidance for the 2020 census: An introduction , https://www2.census.gov/library/publications/decennial/2020/2020-census-disclosure-avoidance-handbook.pdf , 2021, Accessed: 2022-11-06
2022
Later among the works it cites.
2023
Closest in time.
Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia, Differentially-private clustering of easy instances , International Conference on Machine Learning, PMLR, 2021, pp. 2049–2059
2059
Closest in time.