Publications by Group Members

Clément Canonne, Ayush Jain, Gautam, Kamath, Jerry Li (2022). The Price of Tolerance in Distribution Testing. Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022).

PDF

Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, Huanyu Zhang (2022). Robust Estimation for Random Graphs. Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022).

PDF

Gautam, Kamath, Xingtu Liu, Huanyu Zhang (2022). Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data. Proceedings of the 39th International Conference on Machine Learning (ICML 2022).

PDF

Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, Jonathan Ullman (2022). A Private and Computationally-Efficient Estimator for Unbounded Gaussians. Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022).

PDF

Da Yu, Gautam Kamath, Janardhan Kulkarni, Tie-Yan Liu, Jian Yin, Huishuai Zhang (2022). Per-Instance Privacy Accounting for Differentially Private Stochastic Gradient Descent. arXiv preprint arXiv:2206.02617.

PDF

Samuel B Hopkins, Gautam Kamath, Mahbod Majid (2022). Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism. Proceedings of the 54th Annual ACM Symposium on the Theory of Computing (STOC 2022).

PDF

Wenxin Ding, Gautam Kamath, Weina Wang, Nihar B. Shah (2022). Calibration with Privacy in Peer Review. Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT 2022).

PDF

Gautam Kamath, Argyris Mouzakis, Vikrant Singhal (2022). New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma. arXiv preprint arXiv:2205.08532.

PDF

Yiwei Lu, Gautam Kamath, Yaoliang Yu (2022). Indiscriminate Data Poisoning Attacks on Neural Networks. arXiv preprint arXiv:2204.09092.

PDF

Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, Huishuai Zhang (2022). Differentially Private Fine-tuning of Language Models. Proceedings of the 10th International Conference on Learning Representations (ICLR 2022).

PDF

Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, Om Thakkar (2022). The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection. Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI 2022).

PDF

Ayush Sekhari, Jayadev Acharya, Gautam Kamath, Ananda Theertha Suresh (2021). Remember What You Want to Forget: Algorithms for Machine Unlearning. Advances in Neural Information Processing Systems 34 (NeurIPS 2021).

PDF

Pranav Subramani, Nicholas Vadivelu, Gautam Kamath (2021). Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization. Advances in Neural Information Processing Systems 34 (NeurIPS 2021).

PDF

Tianshi Cao, Alex Bie, Arash Vahdat, Sanja Fidler, Karsten Kreis (2021). Don’t Generate Me: Training Differentially Private Generative Models with Sinkhorn Divergence. Advances in Neural Information Processing Systems 34 (NeurIPS 2021).

PDF

Christian Covington, Xi He, James Honaker, Gautam Kamath (2021). Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacy. arXiv preprint arXiv:2110.14465.

PDF

Wanrong Zhang, Gautam Kamath, Rachel Cummings (2021). PAPRIKA: Private Online False Discovery Rate Control. Proceedings of the 38th International Conference on Machine Learning (ICML 2021).

PDF

Ishaq Aden-Ali, Hassan Ashtiani, Gautam Kamath (2021). On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians. Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT 2021).

PDF

Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten (2021). Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).

PDF Video

Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu (2021). Private Hypothesis Selection. IEEE Transactions on Information Theory.

PDF

Clément L. Canonne, Gautam Kamath, Thomas Steinke (2020). The Discrete Gaussian for Differential Privacy. Advances in Neural Information Processing Systems 33 (NeurIPS 2020).

PDF Code

Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, Lydia Zakynthinou (2020). Private Identity Testing for High-Dimensional Distributions. Advances in Neural Information Processing Systems 33 (NeurIPS 2020).

PDF

Sourav Biswas, Yihe Dong, Gautam Kamath, Jonathan Ullman (2020). CoinPress: Practical Private Mean and Covariance Estimation. Advances in Neural Information Processing Systems 33 (NeurIPS 2020).

PDF Code Video

Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni, Zhiwei Steven Wu (2020). Privately Learning Markov Random Fields. Proceedings of the 37th International Conference on Machine Learning (ICML 2020).

PDF

Gautam Kamath, Vikrant Singhal, Jonathan Ullman (2020). Private Mean Estimation of Heavy-Tailed Distributions. Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020).

PDF Video

Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang (2020). Locally Private Hypothesis Selection. Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020).

PDF Video

Jayadev Acharya, Gautam Kamath, Ziteng Sun, Huanyu Zhang (2020). INSPECTRE: Privately Estimating the Unseen. Journal of Privacy and Confidentiality.

PDF Code Video

Gautam Kamath, Jonathan Ullman (2020). A Primer on Private Statistics. arXiv preprint arXiv:2005.00010.

PDF

Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu (2019). Private Hypothesis Selection. Advances in Neural Information Processing Systems 32 (NeurIPS 2019).

PDF Video

Gautam Kamath, Or Sheffet, Vikrant Singhal, Jonathan Ullman (2019). Differentially Private Algorithms for Learning Mixtures of Separated Gaussians. Advances in Neural Information Processing Systems 32 (NeurIPS 2019).

PDF

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath (2019). Testing Ising Models. IEEE Transactions on Information Theory.

PDF

Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, Jonathan Ullman (2019). The Structure of Optimal Private Tests for Simple Hypotheses. Proceedings of the 51st Annual ACM Symposium on the Theory of Computing (STOC 2019).

PDF Video

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart (2019). Sever: A Robust Meta-Algorithm for Stochastic Optimization. Proceedings of the 36th International Conference on Machine Learning (ICML 2019).

PDF Code Video

Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman (2019). Privately Learning High-Dimensional Distributions. Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019).

PDF Video

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart (2019). Robust Estimators in High-Dimensions Without the Computational Intractability. SIAM Journal on Computing.

PDF Code Video

Gautam Kamath, Christos Tzamos (2019). Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing. Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).

PDF

Jayadev Acharya, Clément L. Canonne, Gautam Kamath (2018). A Chasm Between Identity and Equivalence Testing with Conditional Queries. Theory of Computing.

PDF

Gautam Kamath (2018). Modern Challenges in Distribution Testing.

PDF Video

Jayadev Acharya, Gautam Kamath, Ziteng Sun, Huanyu Zhang (2018). INSPECTRE: Privately Estimating the Unseen. Proceedings of the 35th International Conference on Machine Learning (ICML 2018).

PDF Code Video

Steve Hanneke, Adam Kalai, Gautam Kamath, Christos Tzamos (2018). Actively Avoiding Nonsense in Generative Models. Proceedings of the 31st Annual Conference on Learning Theory (COLT 2018).

PDF Video

Constantinos Daskalakis, Gautam Kamath, John Wright (2018). Which Distribution Distances are Sublinearly Testable?. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

PDF

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath (2018). Testing Ising Models. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

PDF

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart (2018). Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

PDF

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath (2017). Concentration of Multilinear Functions of the Ising Model with Applications to Network Data. Advances in Neural Information Processing Systems 30 (NIPS 2017).

PDF Code Video

Bryan Cai, Constantinos Daskalakis, Gautam Kamath (2017). Priv'IT: Private and Sample Efficient Identity Testing. Proceedings of the 34th International Conference on Machine Learning (ICML 2017).

PDF Code Video

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart (2017). Being Robust (in High Dimensions) Can Be Practical. Proceedings of the 34th International Conference on Machine Learning (ICML 2017).

PDF Code Video

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart (2016). Robust Estimators in High Dimensions without the Computational Intractability. Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).

PDF Code Video

Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos (2016). A Size-Free CLT for Poisson Multinomials and its Applications. Proceedings of the 48th Annual ACM Symposium on the Theory of Computing (STOC 2016).

PDF

Jayadev Acharya, Constantinos Daskalakis, Gautam Kamath (2015). Optimal Testing for Properties of Distributions (NIPS 2015). Advances in Neural Information Processing Systems 28.

PDF Video

Constantinos Daskalakis, Gautam Kamath, Christos Tzamos (2015). On the Structure, Covering, and Learning of Poisson Multinomial Distributions. Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015).

PDF Video

Jayadev Acharya, Clément L. Canonne, Gautam Kamath (2015). A Chasm Between Identity and Equivalence Testing with Conditional Queries. Proceedings of the 19th International Workshop of Randomization and Computation (RANDOM 2015).

PDF

Jayadev Acharya, Clément L. Canonne, Gautam Kamath (2015). Adaptive Estimation in Weighted Group Testing. Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT 2015).

PDF

Gautam Kamath (2014). On Learning and Covering Structured Distributions.

PDF

Constantinos Daskalakis, Gautam Kamath (2014). Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians. Proceedings of the 27th Annual Conference on Learning Theory (COLT 2014).

PDF Video

Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg (2012). An Analysis of One-Dimensional Schelling Segregation. Proceedings of the 44th Annual ACM Symposium on the Theory of Computing (STOC 2012).

PDF Video