Image

Frederic Koehler

Hi! I am an Assistant Professor of Statistics and Data Science at the University of Chicago. I am also a member of the Committee on Computational and Applied Mathematics.

Previously I was at Stanford University as a Motwani Postdoctoral Fellow in the Department of Computer Science. Right before, I was a research fellow in UC Berkeley's Simons Institute in the Program on Computational Complexity of Statistical Inference. I received my PHD in Mathematics and Statistics from MIT, where I was coadvised by Ankur Moitra and Elchanan Mossel, and before that I received my undergraduate degree in Mathematics at Princeton University.

I am interested in machine learning, theoretical computer science, and high-dimensional probability and statistics. Some recent topics of interest include generalization theory, algorithms for learning and inference in graphical models, sampling algorithms and generative modeling, related aspects of statistical physics, etc.

Please feel free to reach out --- unfortunately, I may not be able to reply to every email.
Email: [first initial][last name]@uchicago.edu
Office: Room 303, 5460 S. University Avenue

Teaching

Winter 2026. Data 37200/Stat 37201. Learning, Decisions, and Limits. JCL 011, T-Thu 11am-12:20pm.

Winter 2026. Stat 24510: Statistical Theory and Methods IIa. Eckhart 133, T-Thu 2-3:20pm.

Autumn 2025. Stat 33612: Randomness and High-Dimensional Optimization. Jones 303, T-Thu 12:30-1:50.

Spring 2025. Stat 31512: Analysis of Sampling Algorithms. Jones 226, T-Thu 9:30-10:50.

Winter 2025. Stat 24400: Statistical Theory and Methods I. Eckhart 133, T-Thu 9:30-10:50.

Winter 2025. Data 37200/Stat 37201. Learning, Decisions, and Limits.

Spring 2024. Stat 31512: Analysis of Sampling Algorithms

Publications and Preprints

Chronological | Subject
  1. Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential, joint with Joonhyung Shin. [arXiv:2511.18666]
  2. Stein's unbiased risk estimate and Hyvärinen's score matching, joint with Sulagna Ghosh, Nikos Ignatiadis, and Amber Lee. [arXiv:2502.20123]
  3. Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysis, joint with Beining Wu. Symposium on Theory of Computing (STOC) 2026, To Appear. [arXiv:2512.04371]
  4. Parallel Sampling via Autospeculation, joint with Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Anqi Li, and Thuy-Duong Vuong. Symposium on Theory of Computing (STOC) 2026, To Appear. [arXiv:2511.07689]
  5. Efficiently learning and sampling multimodal distributions with data-based initialization, joint with Holden Lee and Thuy-Duong Vuong. Conference on Learning Theory (COLT) 2025. [arXiv:2411.09117]
  6. Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps, joint with Jon Kelner, Raghu Meka, and Dhruv Rohatgi. Conference on Learning Theory (COLT) 2024. [arXiv:2402.15409]
  7. Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting, joint with Serina Chang, Zhaonan Qu, Jure Leskovec, and Johan Ugander. International Conference on Machine Learning (ICML) 2024. [arXiv:2402.18697]
  8. Trickle-Down in Localization Schemes and Applications, joint with Nima Anari and Thuy-Duong Vuong. Symposium on Theory of Computing (STOC) 2024. [arXiv:2407.16104] [Video]
  9. Influences in Mixing Measures, joint with Noam Lifshitz, Dor Minzer, and Elchanan Mossel. Symposium on Theory of Computing (STOC) 2024. [arXiv:2307.07625] [Video]
  10. Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization, joint with Thuy-Duong Vuong. International Conference on Learning Representations (ICLR), 2024.[arXiv:2310.01762]
  11. A Phase Transition in Arrow's Theorem with Three Alternatives, joint with Elchanan Mossel. Annals of Applied Probability (AAP), 2024. [arXiv:2004.12580]. [slides]
  12. Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses, joint with Nima Anari, Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024. [arXiv:2307.10466]
  13. Uniform Convergence with Square-Root Lipschitz Loss, joint with Lijia Zhou, Zhen Dai, and Nathan Srebro. Advances in Neural Information Processing Systems (NeurIPS) 2023. [arXiv:2306.13188] [Related slides]
  14. Feature Adaptation for Sparse Linear Regression, joint with Jon Kelner, Raghu Meka, and Dhruv Rohatgi. Advances in Neural Information Processing Systems (NeurIPS) 2023 (Spotlight Presentation). [arXiv:2305.16892]
  15. Statistical Efficiency of Score Matching: The View from Isoperimetry, joint with Alexander Heckett and Andrej Risteski. Abridged version in NeurIPS 2022 Workshop on Score-Based Methods (Oral Presentation). International Conference on Learning Representations (ICLR) 2023 (Oral Equivalent, Top 5% of Papers). [arXiv:2210.00726] [slides]
  16. A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models, joint with Lijia Zhou, Pragya Sur, Danica J. Sutherland, and Nathan Srebro. Advances in Neural Information Processing Systems (NeurIPS) 2022. [arXiv:2210.12082] [Lijia's Thesis]
  17. Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs, joint with Jon Kelner, Raghu Meka, and Dhruv Rohatgi. Advances in Neural Information Processing Systems (NeurIPS) 2022. [arXiv:2203.02823]
  18. Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods, joint with Holden Lee and Andrej Risteski. Conference on Learning Theory (COLT) 2022. [arXiv:2202.08907] [Slides] [Video]
  19. Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression, joint with Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. ACM/IMS Journal of Data Science (JDS) 2024. [arXiv:2112.04470] [Video]
  20. Reconstruction on Trees and Low-Degree Polynomials, joint with Elchanan Mossel. Advances in Neural Information Processing Systems (NeurIPS) 2022 (Oral Presentation). [arXiv:2109.06915]
  21. Variational autoencoders in the presence of low-dimensional data: landscape and implicit bias, joint with Viraj Mehta, Andrej Risteski, and Chenghui Zhou. International Conference on Learning Representations (ICLR) 2022. [arXiv:2112.06868]
  22. Kalman Filtering with Adversarial Corruptions, joint with Sitan Chen, Ankur Moitra, and Morris Yau. Symposium on Theory of Computing (STOC) 2022. [arXiv:2111.06395]
  23. Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities, joint with Nima Anari, Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. Symposium on Theory of Computing (STOC) 2022 (extended abstract merged w/ Ent. Ind. I). [arXiv:2111.03247].
  24. Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models, joint with Nima Anari, Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. Symposium on Theory of Computing (STOC) 2022. [arXiv:2106.04105]
  25. Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting, joint with Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. Advances in Neural Information Processing Systems (NeurIPS) 2021 (Oral Presentation). [arXiv:2106.09276] [Video]
  26. On the Power of Preconditioning in Sparse Linear Regression, joint with Jon Kelner, Raghu Meka, and Dhruv Rohatgi. Symposium on Foundations of Computer Science (FOCS) 2021. [arXiv:2106.09207] [Video]
  27. Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models, joint with Enric Boix-Adserà and Guy Bresler. Symposium on Foundations of Computer Science (FOCS) 2021. [arXiv:2106.03969] [Video]
  28. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination, joint with Sitan Chen, Ankur Moitra, and Morris Yau. Symposium on Foundations of Computer Science (FOCS) 2021. [arXiv:2010.04157]. [Video (Morris)]
  29. Multidimensional Scaling: Approximation and Complexity, joint with Erik Demaine, Adam Hesterberg, Jayson Lynch, and John Urschel. International Conference on Machine Learning (ICML) 2021. [arXiv:2109.11505] [Video]
  30. Representational aspects of depth and conditioning in normalizing flows, joint with Viraj Mehta and Andrej Risteski. International Conference on Machine Learning (ICML) 2021. [arXiv:2010.01155].
  31. A Spectral Condition for Spectral Gap: Fast Mixing in High-Temperature Ising Models, joint with Ronen Eldan and Ofer Zeitouni. Probability Theory and Related Fields (PTRF) 2021. [arXiv:2007.08200] [Video (Ronen)]
  32. From Boltzmann Machines to Neural Networks and Back Again, joint with Surbhi Goel and Adam Klivans. Advances in Neural Information Processing Systems (NeurIPS) 2020. [arXiv:2007.12815]
  33. Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability, joint with Sitan Chen, Ankur Moitra, and Morris Yau. Advances in Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). [arXiv:2006.04787] [Video]
  34. Learning Some Popular Gaussian Graphical Models without Condition Number Bounds, joint with Jonathan Kelner, Raghu Meka, and Ankur Moitra. Advances in Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). [arXiv:1905.01282]. [Video]
  35. Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay. Advances in Neural Information Processing Systems (NeurIPS) 2019 (Spotlight presentation). [arXiv:1905.09992]
  36. Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation, joint with Vishesh Jain, Jingbo Liu, and Elchanan Mossel. Conference on Learning Theory (COLT) 2019. [arXiv:1905.10031]
  37. How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories, joint with Younhun Kim, Ankur Moitra, Elchanan Mossel, and Govind Ramnarayan. International Conference on Research in Computational Molecular Biology (RECOMB) 2019; Journal of Computational Biology (JCB) Special Issue. [arXiv:1811.03177]
  38. Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective, joint with Vishesh Jain and Andrej Risteski. Symposium on Theory of Computing (STOC) 2019. [arXiv:1808.07226]
  39. Learning Restricted Boltzmann Machines via Influence Maximization, joint with Guy Bresler and Ankur Moitra. Symposium on Theory of Computing (STOC) 2019. [arXiv:1805.10262] [Video (Ankur)]
  40. The Comparative Power of ReLU Networks and Polynomial Kernels in the Presence of Sparse Latent Structure, joint with Andrej Risteski. International Conference on Learning Representations (ICLR) 2019. [arXiv:1805.11405] [OpenReview]
  41. The Vertex Sample Complexity of Free Energy is Polynomial, joint with Vishesh Jain and Elchanan Mossel. Conference on Learning Theory (COLT) 2018. [arXiv:1802.06129][Video]
  42. The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity, joint with Vishesh Jain and Elchanan Mossel. Conference on Learning Theory (COLT) 2018. [arXiv:1802.06126] [Video]
  43. Information theoretic properties of Markov random fields, and their algorithmic applications, joint with Linus Hamilton and Ankur Moitra. Advances in Neural Information Processing Systems (NeurIPS) 2017. [arXiv:1705.11107]
  44. Busy Time Scheduling on a Bounded Number of Machines, joint with Samir Khuller. Algorithm and Data Structures Symposium (WADS) 2017. (Full Version, slides)
  45. Provable algorithms for inference in topic models, joint with Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. International Conference on Machine Learning (ICML) 2016. [arXiv:1605.08491]
  46. Optimal batch schedules for parallel machines, joint with Samir Khuller. Algorithm and Data Structures Symposium (WADS) 2013. (Full version)

In most cases, authors are listed in alphabetical order, following the convention in mathematics and theoretical computer science.

Miscellaneous service: SODA 2025 PC Member, STOC 2024 PC Member, NeurIPS 2023-2024 Area Chair, COLT 2021,2022,2024 PC Member, ALT 2023 PC Member. Refereeing for many journals and conferences (further information available upon request).

Notes