Research

I received my Ph.D. from Princeton, where I was advised by Sanjeev Arora.

I focus on machine learning theory and applied probability, and also have broad interests in theoretical computer science and related math.

Research interests

Current interests include:

• Probabilistic methods in machine learning, with a focus on sampling (MCMC) algorithms: How to design provable algorithms for learning probability distributions and sampling from them?
• Control theory and reinforcement learning, with a focus on learning dynamical systems: It is a well-studied problem how to find the optimal control for a known linear dynamical system. However, reinforcement learning deals with learning how to act in unknown, combinatorially complex systems; algorithms are heuristic and slow. How to bridge this gap?
• Neural networks: Neural networks tackle highly nonconvex problems but do very well in practice. Why? What kind of algorithmic improvements can we come up with by understanding their theoretical foundations more deeply?
• Natural language understanding: Language is a fundamental part of human intelligence and a big frontier for machine learning. How do we create machines that can understand “grammar” and “semantics”?

Papers

The publication list is available as pdf.

[A] denotes alphabetical order of authors.

Generative modeling, learning probability distributions

• Learning mixtures of gaussians using diffusion models

  [A] Khashayar Gatmiry, Jonathan Kelner, Holden Lee.

  Preprint, 2024. arxiv

• Provable benefits of score matching

  Chirag Pabbaraju, Dhruv Rohatgi, Anish Prasad Sevekari, Holden Lee, Ankur Moitra, Andrej Risteski.

  NeurIPS 2023 (Spotlight). [arxiv]

• The probability flow ODE is provably fast

  [A] Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, Adil Salim

  NeurIPS 2023. [arxiv]

• Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions

  [A] Hongrui Chen, Holden Lee, and Jianfeng Lu.

  ICML 2023. [arxiv]

• Pitfalls of Gaussians as a noise distribution in NCE

  Holden Lee, Chirag Pabbaraju, Anish Sevekari, and Andrej Risteski.

  ICLR 2023, NeurIPS 2022 Workshop on Self-Supervised Learning. [arxiv]

• Convergence of score-based generative modeling for general data distributions

  [A] Holden Lee, Jianfeng Lu, and Yixin Tan.

  ALT 2023, NeurIPS 2022 Workshop on Score-Based Methods. [arxiv]

• Convergence for score-based generative modeling with polynomial complexity

  [A] Holden Lee, Jianfeng Lu, and Yixin Tan.

  NeurIPS 2022 (oral). [arxiv, slides]

• Universal Approximation for Log-concave Distributions using Well-conditioned Normalizing Flows.

  Holden Lee, Chirag Pabbaraju, Anish Sevekari, Andrej Risteski.

  NeurIPS 2021. [arXiv, pdf, slides]

Algorithms for sampling and counting

• Sampling from the Continuous Random Energy Model in Total Variation Distance

  [A] Holden Lee, Qiang Wu.

  Preprint, 2024. arxiv

• Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition

  [A] Holden Lee, Matheau Santana-Gijzen.

  Preprint, 2024. arxiv

• Sampling List Packings

  [A] Evan Camrud, Ewan Davies, Alex Karduna, Holden Lee.

  Preprint, 2023. arxiv

• Parallelising Glauber Dynamics

  Holden Lee.

  RANDOM 2024. arxiv, presentation.

• Fisher information lower bounds for sampling

  [A] Sinho Chewi, Patrik Gerber, Holden Lee, Chen Lu.

  ALT 2023. [arxiv]

• Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods

  [A] Frederic Koehler, Holden Lee, and Andrej Risteski.

  COLT 2022. [arXiv, pdf, slides, video]

• Approximation algorithms for the random-field Ising model

  [A] Tyler Helmuth, Holden Lee, Will Perkins, Mohan Ravichandran, and Qiang Wu.

  SIAM Journal on Discrete Mathematics 37 (3), 1610-1629. 2024. [arXiv, pdf]

• Efficient sampling from the Bingham distribution

  [A] Rong Ge, Holden Lee, Jianfeng Lu, and Andrej Risteski.

  ALT 2021. [arXiv, pdf, video]

• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds

  [A] Rong Ge, Holden Lee, and Jianfeng Lu.

  STOC 2020. [arXiv, pdf, STOC 2020:579–586, slides, video]

• Online Sampling from Log-Concave Distributions

  [A] Holden Lee, Oren Mangoubi, and Nisheeth Vishnoi.

  NeurIPS 2019. [arXiv, pdf, webpage]

• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo. webpage

  [A] Rong Ge, Holden Lee, and Andrej Risteski.

  • NeurIPS 2018. [arXiv, pdf]
  • NIPS AABI Workshop 2017. [arXiv, pdf]
  • Blog post on offconvex: 1, 2.

Reinforcement learning and control theory

• Extracting Latent State Representations with Linear Dynamics from Rich Observations

  Abraham Frandsen, Rong Ge, and Holden Lee.

  ICML 2022.

• Improved rates for identification of partially observed linear dynamical systems

  Holden Lee.

  ALT 2022. [arXiv, pdf]

• No-Regret Prediction in Marginally Stable Systems

  [A] Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang.

  COLT 2020. [arxiv, pdf, slides, summary slide, videos]

• Statistical Guarantees for Learning an Autoregressive Filter

  [A] Holden Lee and Cyril Zhang.

  ALT 2020. [arxiv, pdf]

• Spectral Filtering for General Linear Dynamical Systems

  [A] Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang.

  NeurIPS 2018 (oral). [arxiv, pdf]

• Towards Provable Control for Unknown Linear Dynamical Systems.

  [A] Sanjeev Arora, Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang.

  ICLR workshop 2018. [ICLR page, pdf]

Natural language processing

• When is a Language Process a Language Model?

  Li Du, Holden Lee, Jason Eisner, Ryan Cotterell.

  ACL 2024.

• Principled Gradient-based Markov Chain Monte Carlo for Text Generation

  Li Du, Afra Amini, Lucas Torroba Hennigen, Xinyan Velocity Yu, Jason Eisner, Holden Lee, Ryan Cotterell.

  Preprint, 2023. arxiv

• Connecting Pre-trained Language Model and Downstream Task via Properties of Representation

  Chenwei Wu, Holden Lee, Rong Ge.

  NeurIPS 2023.

Neural networks

• Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets.

  Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, and Sanjeev Arora.

  NeurIPS 2019. [arXiv, pdf]

• On the Ability of Neural Nets to Express Distributions.

  Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora.

  COLT 2017. [arXiv, pdf, PMLR 65:1271-1296, webpage]

Machine Learning (other)

• How Flawed is ECE? An Analysis via Logit Smoothing

  [A] Muthu Chidambaram, Holden Lee, Colin McSwiggen, Semon Rezchikov.

  ICML 2024. arxiv

Complexity theory

• Quadratic polynomials of small modulus cannot represent OR.

  Holden Lee

  Unpublished, 2015. [arXiv, pdf]

Number theory

• l-adic properties of partition functions.

  [A] Eva Belmont, Holden Lee, Alexandra Musat, and Sarah Trebat-Leder.

  Monatshefte für Mathematik, 173(1), 1-34, 2014. [arXiv, pdf, presentation, webpage]

Survey slides

• Probabilistic foundations for machine learning (Job talk, 2022)
• Changing the temperature for algorithm design (Frontiers of Statistical Mechanics and Theoretical Computer Science, 2021/12/14)