Gautam Kamath Office: DC 3124 (currently empty) Cell: 657-c0mpsci (657-206-7724) (currently inactive) Email: ?@csail.mit.edu, but replace ? with the first letter of my first name Links to: CV (as of March 2021); Google Scholar; DBLP; arXiv; GitHub; Twitter; Youtube; Blog. My lab is The Salon. Feel free to send me comments anonymously here. Note that, by design, I won't be able to respond -- if you need me to, it's better handled via email, or leaving some way for me to reply. I am unable to respond to requests for internships or graduate admission applications from outside the university. If you do feel compelled to contact me in this way, I am far more likely to remember you if you demonstrate that you have genuinely engaged with my work. Instead, I recommend that you apply for graduate studies through the standard channels.

About Me

I am an Assistant Professor at the University of Waterloo's Cheriton School of Computer Science, and a faculty affiliate at the Vector Institute. I run The Salon. I'm interested in reliable and trustworthy statistics and machine learning, including considerations such as data privacy and robustness.

I was a Microsoft Research Fellow at the Simons Institute for the Theory of Computing for the Fall 2018 semester program on Foundations of Data Science and the Spring 2019 semester program on Data Privacy: Foundations and Applications. Before that, I completed my Ph.D. at MIT, affiliated with the Theory of Computing group in CSAIL. I was very fortunate to be advised by Costis Daskalakis.

Before MIT, I spent four wonderful years at Cornell University, graduating in May 2012 with a degree in Computer Science and Electrical and Computer Engineering. At Cornell, I was incredibly lucky to have the opportunity to work with Bobby Kleinberg.

I really enjoy giving talks and communicating my work! Please don't hesitate to ask if you'd like to hear about it.

News

• (7/23/21) I will be a reader for Elliot Nelson Master's thesis.
• (7/10/21) I will be on the PC for ALT 2022.
• (7/9/21) I will be on Tosca Lechner's and Jimit Majmudar's Ph.D. thesis committees.
• (6/28/21) I will be a reader for Thomas Humphries's Master's thesis.
• (6/28/21) New paper on arXiv: The Price of Tolerance in Distribution Testing.
• (6/16/21) I will be an area chair for ICLR 2022.
• (6/2/21) New paper on arXiv: Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data.
• (5/28/21) I will be on Guojun Zhang's Ph.D. thesis committee.
• (5/8/21) PAPRIKA accepted to ICML 2021.
• (4/27/21) I will be a reader for Nivasini Ananthakrishnan's Master's thesis.
• (4/20/21) I am editor for ALT Highlights.
• (4/9/21) I gave a talk at the Boston-area DP Seminar.
• (4/2/21) Rachel Cummings and I are co-chairing the 2021 workshop on Theory and Practice of Differential Privacy (TPDP 2021), to be held at ICML 2021.
• (4/1/21) PAPRIKA accepted to FORC 2021 (non-archival track).
• (4/1/21) I gave a talk at the TrustML Seminar.
• (3/24/21) I will be a reader for Lingyi Zhang's Master's thesis.
• (3/18/21) I will be an area chair for NeurIPS 2021.
• (3/8/21) New paper on arXiv: Remember What You Want to Forget: Algorithms for Machine Unlearning.
• (3/2/21) I'm on the PC for SODA 2022.
• (3/1/21) I'm giving a talk at the (virtual) London Symposium on Information Theory (LSIT), held on May 19 to 21.
• (3/1/21) I'm giving a talk at a conference on robustness and privacy on March 22 or 23.
• (2/19/21) I'm a reviewer for ICML 2021 workshops.
• (1/27/21) I'm giving a talk at Google on March 5.
• (1/27/21) I'm organizing a workshop on Distributed and Private Machine Learning at ICLR 2021.
• (1/18/21) I gave a talk at Waterloo's ML + Logic Seminar.
• (1/17/21) I will be a social chair for NeurIPS 2021.
• (1/11/21) I will be giving a talk at McGill's statistics seminar.
• (1/7/21) I hosted Graduating Bits at ITCS 2021, and helped out with a few other things behind the scenes.
• (1/4/21) I started mirroring my videos on Bilibili, the "Chinese Youtube". A popular WeChat account wrote about my joining (in Chinese).
• (12/22/20) I am now a faculty affiliate at the Vector Institute.

Research

Selected Papers (Show all)

The Price of Tolerance in Distribution Testing.
Clément L. Canonne, Ayush Jain, Gautam Kamath, Jerry Li.
Manuscript.


Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data.
Gautam Kamath, Xingtu Liu, Huanyu Zhang.
Manuscript.
• Presented at the ICML 2021 Workshop on Theory and Practice of Differential Privacy (TPDP 2021).


Remember What You Want to Forget: Algorithms for Machine Unlearning.
Ayush Sekhari, Jayadev Acharya*, Gautam Kamath*, Ananda Theertha Suresh*. (Contribution order)
Manuscript.
• Presented at the ICML 2021 Workshop on Theory and Practice of Differential Privacy (TPDP 2021).


Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization.
Pranav Subramani*, Nicholas Vadivelu*, Gautam Kamath. (Contribution order)
Manuscript.
• Presented at the NeurIPS 2020 Workshop on Privacy Preserving Machine Learning (PPML 2020).
• Presented at the ICML 2021 Workshop on Theory and Practice of Differential Privacy (TPDP 2021).
• Code is available here.
• Inspired changes in TensorFlow Privacy.
• Featured in: DeepMind Blog (Using JAX to accelerate our research), Google AI Blog (Google Research: Looking Back at 2020, and Forward to 2021).


PAPRIKA: Private Online False Discovery Rate Control.
Wanrong Zhang, Gautam Kamath*, Rachel Cummings*. (Contribution order)
Proceedings of the 38th International Conference on Machine Learning (ICML 2021).
• Presented at FORC 2021, non-archival track.
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Code is available here.


On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians.
Ishaq Aden-Ali, Hassan Ashtiani, Gautam Kamath.
Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT 2021).
• Presented at the NeurIPS 2020 Workshop on Privacy Preserving Machine Learning (PPML 2020).


Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten.
Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
• ECCC link.
• Featured in: Property Testing Review.
• Talk by Erik here.


CoinPress: Practical Private Mean and Covariance Estimation.
Sourav Biswas, Yihe Dong, Gautam Kamath, Jonathan Ullman.
Advances in Neural Information Processing Systems 33 (NeurIPS 2020).
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Video of a talk is available here.
• Code is available here.


The Discrete Gaussian for Differential Privacy.
Clément L. Canonne, Gautam Kamath, Thomas Steinke.
Advances in Neural Information Processing Systems 33 (NeurIPS 2020).
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Code is available here.


Private Identity Testing for High-Dimensional Distributions.
Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, Lydia Zakynthinou.
Advances in Neural Information Processing Systems 33 (NeurIPS 2020).
• Selected for a Spotlight Presentation.
• Presented at the CCS 2019 Workshop on Theory and Practice of Differential Privacy (TPDP 2019).
• Presented at the NeurIPS 2019 Workshop on Privacy in Machine Learning (PriML 2019).
• Featured in: Property Testing Review.


Privately Learning Markov Random Fields.
Huanyu Zhang, Gautam Kamath*, Janardhan Kulkarni*, Zhiwei Steven Wu*. (Contribution order)
Proceedings of the 37th International Conference on Machine Learning (ICML 2020).
• Presented at the CCS 2019 Workshop on Theory and Practice of Differential Privacy (TPDP 2019).
• Presented at the NeurIPS 2019 Workshop on Privacy in Machine Learning (PriML 2019).


Private Mean Estimation of Heavy-Tailed Distributions.
Gautam Kamath, Vikrant Singhal, Jonathan Ullman.
Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020).
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• COLT talk by Vikrant available here.


Locally Private Hypothesis Selection.
Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang.
Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020).
• Presented at the CCS 2020 Workshop on Theory and Practice of Differential Privacy (TPDP 2020).
• Featured in: Property Testing Review.
• I gave a talk more generally on hypothesis selection with privacy constraints: here.
• COLT talk by Janardhan available here.


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


Private Hypothesis Selection.
Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu.
IEEE Transactions on Information Theory, to appear.
Advances in Neural Information Processing Systems 32 (NeurIPS 2019).
• Presented at the CCS 2019 Workshop on Theory and Practice of Differential Privacy (TPDP 2019). Oral Presentation.
• I gave a talk more generally on hypothesis selection with privacy constraints: here.
• Video of a talk by Mark is available here.


Sever: A Robust Meta-Algorithm for Stochastic Optimization.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart.
Proceedings of the 36th International Conference on Machine Learning (ICML 2019).
• Presented at the NeurIPS 2018 Workshop on Security in Machine Learning (SECML 2018). Oral Presentation.
• Code is available here.
• Video of a talk by Jerry is available here.


Privately Learning High-Dimensional Distributions.
Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman.
Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019).
• Presented at the 2018 Workshop on Theory and Practice of Differential Privacy (TPDP 2018).
• Video of a talk by Jon is available here.


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


Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing.
Gautam Kamath, Christos Tzamos.
Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
• ECCC link.
• Slides from my talk at SODA available here.
• Featured in: Property Testing Review.


INSPECTRE: Privately Estimating the Unseen.
Jayadev Acharya, Gautam Kamath, Ziteng Sun, Huanyu Zhang.
Journal of Privacy and Confidentiality, 10(2), 2020. Special issue for TPDP 2018.
Proceedings of the 35th International Conference on Machine Learning (ICML 2018).
• Presented at the CCS 2018 Workshop on Theory and Practice of Differential Privacy (TPDP 2018).
• Code is available here.
• Featured in: Property Testing Review
• Video of a talk by Huanyu is available here.


Actively Avoiding Nonsense in Generative Models.
Steve Hanneke, Adam Kalai, Gautam Kamath, Christos Tzamos.
Proceedings of the 31st Annual Conference on Learning Theory (COLT 2018).
• Video of Adam's talk at COLT can be viewed here.


Which Distribution Distances are Sublinearly Testable?
Constantinos Daskalakis, Gautam Kamath, John Wright.
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
• ECCC link.
• Featured in: Property Testing Review.


Testing Ising Models.
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath.
IEEE Transactions on Information Theory, 65(11), 2019.
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
• ECCC link.
• Featured in: Property Testing Review.


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


Concentration of Multilinear Functions of the Ising Model with Applications to Network Data.
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath.
Advances in Neural Information Processing Systems 30 (NIPS 2017).
• Code is available here.
• A three-minute summary video for NIPS is available here.
• Our NIPS poster is viewable here.


Priv'IT: Private and Sample Efficient Identity Testing.
Bryan Cai, Constantinos Daskalakis, Gautam Kamath.
Proceedings of the 34th International Conference on Machine Learning (ICML 2017).
• Presented at the ICML 2017 Workshop on Private and Secure Machine Learning 2017 (PSML 2017). Oral Presentation.
• Video of my talk at ICML can be viewed here.
• Code is available here.
• Featured in: Property Testing Review.


Being Robust (in High Dimensions) Can Be Practical.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart.
Proceedings of the 34th International Conference on Machine Learning (ICML 2017).
• Code is available here.
• Video of Jerry's talk at ICML can be viewed here.


Robust Estimators in High Dimensions without the Computational Intractability.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart.
SIAM Journal on Computing, 48(2), 2019. Special Issue for FOCS 2016.
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
• Invited to the SIAM Journal on Computing Special Issue for FOCS 2016.
• Invited to Highlights of Algorithms 2017.
• Invited to Communications of the ACM, Research Highlights.
• Video of Jerry's talk at TCS+ can be viewed here. Video of Ankur's talk at the Simons Institute can be viewed here.
• Featured in: MIT News, USC Viterbi News


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


Optimal Testing for Properties of Distributions.
Jayadev Acharya, Constantinos Daskalakis, Gautam Kamath.
Advances in Neural Information Processing Systems 28 (NIPS 2015).
• Selected for a Spotlight Presentation (4.5% acceptance rate).
• Video of a talk by Costis at UT Austin can be viewed here. Video of the spotlight talk by Jayadev at NIPS can be viewed here (at 9:15).
• Featured in: MIT Theory of Computation Student Blog, Property Testing Review.
• An extremely condensed version of this paper appeared in Volume Four of Tiny Transactions on Computer Science (Tiny ToCS).


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


A Chasm Between Identity and Equivalence Testing with Conditional Queries.
Jayadev Acharya, Clément L. Canonne, Gautam Kamath.
Theory of Computing, 14(19), 2018.
Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM 2015).
• ECCC link.
• Slides from Clément's talk at RANDOM available here.
• Featured in: Oded Goldreich's Choices, Property Testing Review, Sublinear.info.


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


Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians.
Constantinos Daskalakis, Gautam Kamath.
Proceedings of the 27th Annual Conference on Learning Theory (COLT 2014).
• Slides from the talk at COLT available here. Video of the talk can be viewed here.


An Analysis of One-Dimensional Schelling Segregation.
Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg.
Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012).
• I was very lucky to be awarded the inaugural STOC Best Student Presentation Award by SIGACT for this talk.
• Slides from the talk at STOC available here, adapted from slides from a talk by Nicole at MSR. Video of the talk can be viewed here.
• Featured in: American Scientist.

Selected Workshop Papers (Show)

Theses

• Modern Challenges in Distribution Testing.
  Gautam Kamath.
  Ph.D. Thesis, 2018.
• On Learning and Covering Structured Distributions.
  Gautam Kamath.
  M.Sc. Thesis, 2014.

Talk Videos

• Hypothesis Selection with Privacy Constraints.
• CoinPress: Practical Private Mean and Covariance Estimation.
• Privately Learning High-Dimensional Distributions. Presented at Data Privacy: From Foundations to Applications.
• Private Statistics: A TCS Perspective. Presented as part of the mini-course on private statistics at the Data Privacy Boot Camp.
• Realizing Robustness. Presented at the Robust and High-Dimensional Statistics Workshop.
• Modern Challenges in Distribution Testing. My PhD defense talk.
• Differentially Private Hypothesis Testing and Property Estimation. Presented at Mathematical Foundations of Data Privacy.
• Robustness in Unsupervised and Supervised Learning. Presented at Modern Challenges of Learning Theory.
• Testing with Alternative Distances. Presented at Frontiers of Distribution Testing workshop at FOCS 2017.
• Priv'IT: Private and Sample Efficient Identity Testing. Presented at ICML 2017.
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians. Presented at COLT 2014.
• An Analysis of One-Dimensional Schelling Segregation. Presented at STOC 2012.

Coauthors

Other Writings

• We wrote a "Behind the Screens" look at STOC 2020, a document which may be useful to other virtual conference organizers. With Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, and input from Julia Chuzhoy.
• Jonathan Ullman and I wrote a brief survey of differentially private statistics: A Primer on Private Statistics.
• For Advanced Algorithms (6.854), I wrote a survey of matroid secretary problem algorithms as a final project.
• Some bounds on the expectation of the maximum of samples from a Gaussian. I thought this was a fairly natural problem, but when I wrote it, I was unable to find anyone else who had computed the explicit lower bound here.

Service

• I have been (or will be) a general chair for the following conferences: STOC 2020.
• I have been (or will be) program chair for the following workshops: TPDP 2021.
• I have been (or will be) on the core program committee or an area chair for the following conferences: SODA 2020, ICML 2020, ICALP 2020, Random 2020,ALT 2021, ICLR 2021, FORC 2021, COLT 2021, CCS 2021, ESA 2021, NeurIPS 2021, SODA 2022, ICLR 2022, ALT 2022.
• I have been (or will be) on the program committee (i.e., a reviewer) of the following machine learning conferences: NIPS 2016, ICML 2018, NeurIPS 2018, AISTATS 2019, ICML 2019, NeurIPS 2019, AAAI 2020, AISTATS 2020, FAccT 2021.
• For completeness, conferences I have reviewed for include: AAAI, AISTATS, ALT, COLT, FAccT, FOCS, ICALP, ICML, ISAAC, ISIT, ITCS, NeurIPS, RANDOM, SODA, STACS, STOC.
• I have (or will be) on the program committee of the following workshops: TPDP 2019, PriML 2019, TPDP 2020, PPML 2020.
• I am a maintainer of the CS Theory Blog Aggregator, along with Arnab Bhattacharyya and Suresh Venkatasubramanian.
• Clément Canonne and I organized a workshop called "A TCS Quiver" at FOCS 2019.
• Clément Canonne and I organized a workshop on distribution testing at FOCS 2017.
• Clément Canonne and I organized a workshop on orthogonal polynomials at FOCS 2016.
• I'm an editor for the MIT Theory of Computation Student Blog and Property Testing Review.
• I'm one of the organizers of TCS+, an online seminar series in theoretical computer science, accessible to the widest possible audience, and ensuring a carbon-free dissemination of ideas across the globe.
• I organized the second Sublinear Day, which was on April 10, 2015 at MIT.
• I was the head organizer for the Second Annual Danny Lewin MIT Theory Student Retreat, which took place in October 2013. Aloni and Themis wrote a bit about this retreat here.
• From Fall 2012 to Fall 2013, I was in charge of the Theory Group lunch, which was the current incarnation of Great Ideas in Theoretical Computer Science at CSAIL. The website for the current offering is here.

Other Projects

• As a final project for a microcontrollers class, my partner Dominick Grochowina and I made an automated vocalist for the game Rock Band. This was featured on the website Hack A Day. Videos of the bot in action can be seen here and here.
• I worked on a project called Plannit, which won second place at Cornell Facebook Hackathon. Partners on this project were Jasdeep Hundal, Sohan Jain, and Harry Terkelsen.

Teaching

• CS 480/680 - Introduction to Machine Learning: Winter 2021, Spring 2021
• CS 860 - Algorithms for Private Data Analysis: Fall 2020
• CS 240 - Data Structures and Data Management: Spring 2020
• CS 761 - Randomized Algorithms: Fall 2019

Advising

Resources

• TCS+: An series of online seminars in theoretical computer science.
• Simons Institute Videos: Videos from workshops hosted at the Simons Institute for the Theory of Computing.
• BIRS Videos: Videos from workshops hosted at the Banff International Research Station.
• Institute for Advanced Studies Videos: Videos from the IAS. Note that many are related to other fields besides computer science.
• Microsoft Research Talks: Talks at Microsoft Research, including a variety of topics beyond theory.
• Shannon Channel: A series of online seminars in information theory.
• Princeton TCS Videos: Videos from theory lunch and workshops within Princeton's theory group.
• Videolectures.net: Lecture videos from a number of conferences and workshops, seems to be primarily focused on machine learning events.

Other

• I used to go by the name "G", though I now prefer Gautam. Also, my name is not Guatam Kamath, though it is commonly misspelled as such.
• My friends Aviv Adler, Greg Bodwin, and primarily Jennifer Tang, made a small puzzle hunt for my graduation. You can check out the puzzles here: 1, 2, 3, 4, 5, 6. Warning that they can be incredibly unfair if you are not me, but oh well. Try them out!