Frederic Koehler

Hi! I am currently at Stanford University as a Motwani Postdoctoral Fellow. Right before, I was a research fellow in UC Berkeley's Simons Institute in Fall 2021. 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. My current research interests include computational learning theory and related topics: probability theory, high-dimensional statistics, optimization, related aspects of statistical physics, etc. In particular, I am very interested in learning and inference in graphical models.

To reach me: [first initial][last name]@stanford.edu

Publications and Preprints

  1. Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression, joint with Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. [arXiv:2112.04470]
  2. Kalman Filtering with Adversarial Corruptions, joint with Sitan Chen, Ankur Moitra, and Morris Yau.[arXiv:2111.06395]
  3. 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. [arXiv:2111.03247].
  4. Reconstruction on Trees and Low-Degree Polynomials, joint with Elchanan Mossel. [arXiv:2109.06915]
  5. 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. [arXiv:2106.04105]
  6. 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, To Appear (Oral Presentation). [arXiv:2106.09276]
  7. 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, To Appear. [arXiv:2106.09207]
  8. 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, To Appear. [arXiv:2106.03969]
  9. 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, To Appear. [arXiv:2010.04157].
  10. 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]
  11. 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].
  12. 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]
  13. 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]
  14. 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]
  15. A Phase Transition in Arrow's Theorem, joint with Elchanan Mossel. [arXiv:2004.12580]
  16. 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].
  17. Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay. Advances in Neural Information Processing Systems (NeurIPS) 2019 (Spotlight presentation). [arXiv:1905.09992]
  18. 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]
  19. 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]
  20. 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]
  21. Learning Restricted Boltzmann Machines via Influence Maximization, joint with Guy Bresler and Ankur Moitra. Symposium on Theory of Computing (STOC) 2019. [arXiv:1805.10262]
  22. 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]
  23. 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]
  24. 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]
  25. 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]
  26. Busy Time Scheduling on a Bounded Number of Machines, joint with Samir Khuller. Algorithm and Data Structures Symposium (WADS) 2017. (Full Version, slides)
  27. 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]
  28. 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.

Notes

  1. A Note on Minimax Learning of Tree Models. Superceded by Appendix to "Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models."