Links:
Google Scholar
Twitter

Papers

• Learning in observable POMDPs, without computationally intractable oracles.
  Noah Golowich, Ankur Moitra, and Dhruv Rohatgi.
  To appear in NeurIPS 2022.
• Planning in observable POMDPs in quasipolynomial time.
  Noah Golowich, Ankur Moitra, and Dhruv Rohatgi.
  
• The complexity of Markov equilibrium in stochastic games.
  Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang.
  My talk at the Simons workshop on reinforcement learning and bandit learning. [talk video] [slides]
  

• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games
  Constantinos Daskalakis and Noah Golowich.
  In STOC 2022. [conf] [talk video]
  
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games.
  Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm.
  In STOC 2022. [conf]
  
• Can Q-learning be improved with advice?
  Noah Golowich and Ankur Moitra.
  In COLT 2022. [conf] [slides]
  
• Smoothed online learning is as easy as statistical learning.
  Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin
  In COLT 2022. [conf] [slides]
  
• Near-Optimal No-Regret Learning in General Games.
  Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich.
  In NeurIPS 2021 (Oral presentation). [conf]
  My talk at the Simons workshop on Adversarial approaches in machine learning. [talk video]
  
• Littlestone Classes are Privately Online Learnable.
  Noah Golowich and Roi Livni.
  In NeurIPS 2021 (Spotlight presentation). [conf]
• On Deep Learning with Label Differential Privacy.
  Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang.
  In NeurIPS 2021. [conf]
• Differentially private nonparametric regression under a growth condition.
  Noah Golowich.
  In COLT 2021. [conf] [talk video] [slides]
• Sample-efficient proper PAC learning with approximate differential privacy.
  Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi.
  Extended abstract at PriML/PPML 2020 workshop (Oral presentation). [workshop link] [talk video] [slides]
  In STOC 2021. [conf] [talk video]
  My talk at MIT Algorithms & Complexity Seminar, March 2021. [talk video] [slides]
  My talk at Boston-area DP seminar (BU, Harvard & Northeastern), February 2021. [slides]
• Near-tight closure bounds for Littlestone and threshold dimensions.
  Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi.
  In ALT 2021 (Best student paper award). [conf] [talk video] [slides]
• On the power of multiple anonymous messages.
  Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker.
  Extended abstract at FORC 2020. [conf] [talk video] [slides]
  In Eurocrypt 2021. [conf] [talk video]
  My talk at MIT CIS seminar, December 2019. [slides]
• Tight last-iterate convergence rates for no-regret learning in multi-player games.
  () Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis.
  In NeurIPS 2020. [conf]
• Independent Policy Gradient Methods for Competitive Reinforcement Learning.
  Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich.
  In NeurIPS 2020. [conf] [slides]
• Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems.
  () Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar.
  In COLT 2020. [conf] [talk video] [slides]
• Pure differentially private summation from anonymous messages.
  Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker.
  In ITC 2020. [conf]
• Round complexity of common randomness generation: the amortized setting.
  Noah Golowich and Madhu Sudan.
  In SODA 2020. [conf] [slides]
• A convergence analysis of gradient descent for deep linear neural networks.
  Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu.
  In ICLR 2019. [conf]
• Communication-rounds tradeoffs for common randomness and secret key generation.
  Mitali Bafna, Badih Ghazi, Noah Golowich, and Madhu Sudan.
  In SODA 2019. [conf] [slides]
• Machine learning for optimal economic design.
  Paul Dütting, Zhe Feng, Noah Golowich, Harikrishna Narasimhan, and David C. Parkes.
  In The Future of Economic Design, 2019. [journal]
• Deep learning for multi-facility location mechanism design.
  Noah Golowich, Harikrishna Narasimhan, and David C. Parkes.
  In IJCAI 2018. [conf]
• Size-independent sample complexity of neural networks.
  Noah Golowich, Alexander Rakhlin, and Ohad Shamir.
  In COLT 2018. [conf]
  In Information and Inference, 2019. [journal]
• Coloring chains for compression with uncertain priors.
  Noah Golowich.
  In The Electronic Journal of Combinatorics, 2018. [journal]
• The m-degenerate chromatic number of a digraph.
  Noah Golowich.
  In Discrete Mathematics, 2016. [journal]
• Acyclic subgraphs of planar digraphs.
  Noah Golowich and David Rolnick.
  In The Electronic Journal of Combinatorics, 2016. [journal]
• Resolving a conjecture on degree of regularity of linear homogeneous equations.
  Noah Golowich.
  In The Electronic Journal of Combinatorics, 2014. [journal]
• Degree of regularity of linear homogeneous equations.
  Kavish Gandhi, Noah Golowich, and László M. Lovász.
  In Journal of Combinatorics, 2014. [journal]

Lecture Notes

• 6.S977 - The Sum of Squares Method (taught by Sam Hopkins).