Frederic Koehler

Hi! I am currently a fifth year graduate student in the Department of Mathematics at MIT, where I am fortunate to be co-advised by Ankur Moitra and Elchanan Mossel. Before coming to MIT, I did my undergraduate studies at Princeton, where I was fortunate to do a Junior Paper with Assaf Naor and Senior Thesis with Sanjeev Arora. 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]@mit.edu

Publications and Preprints

  1. Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting, joint with Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. [arXiv:2106.09276]
  2. On the Power of Preconditioning in Sparse Linear Regression, joint with Jon Kelner, Raghu Meka, and Dhruv Rohatgi. [arXiv:2106.09207]
  3. Entropic Independence in High-Dimensional Expanders: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Polynomials and the Ising Model, joint with Nima Anari, Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. [arXiv:2106.04105]
  4. Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models, joint with Enric Boix-Adsera and Guy Bresler. [arXiv:2106.03969]
  5. Multidimensional Scaling: Approximation and Complexity, joint with Erik Demaine, Adam Hesterberg, Jayson Lynch, and John Urschel. International Conference on Machine Learning (ICML) 2021, To Appear.
  6. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination, joint with Sitan Chen, Ankur Moitra, and Morris Yau. [arXiv:2010.04157].
  7. Representational aspects of depth and conditioning in normalizing flows, joint with Viraj Mehta and Andrej Risteski. International Conference on Machine Learning (ICML) 2021, To Appear. [arXiv:2010.01155].
  8. From Boltzmann Machines to Neural Networks and Back Again, joint with Surbhi Goel and Adam Klivans. Neural Information Processing Systems (NeurIPS) 2020. [arXiv:2007.12815]
  9. A Spectral Condition for Spectral Gap: Fast Mixing in High-Temperature Ising Models, joint with Ronen Eldan and Ofer Zeitouni. [arXiv:2007.08200]
  10. Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability, joint with Sitan Chen, Ankur Moitra, and Morris Yau. Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). [arXiv:2006.04787]
  11. A Phase Transition in Arrow's Theorem, joint with Elchanan Mossel. [arXiv:2004.12580]
  12. Learning Some Popular Gaussian Graphical Models without Condition Number Bounds, joint with Jonathan Kelner, Raghu Meka, and Ankur Moitra. Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). [arXiv:1905.01282].
  13. Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay. Neural Information Processing Systems (NeurIPS) 2019 (Spotlight presentation). [arXiv:1905.09992]
  14. 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]
  15. 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]
  16. 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]
  17. Learning Restricted Boltzmann Machines via Influence Maximization, joint with Guy Bresler and Ankur Moitra. Symposium on Theory of Computing (STOC) 2019. [arXiv:1805.10262]
  18. 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]
  19. 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]
  20. 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]
  21. Information theoretic properties of Markov random fields, and their algorithmic applications, joint with Linus Hamilton and Ankur Moitra. Neural Information Processing Systems (NeurIPS) 2017. [arXiv:1705.11107]
  22. Busy Time Scheduling on a Bounded Number of Machines, joint with Samir Khuller. Algorithm and Data Structures Symposium (WADS) 2017. (Full Version, slides)
  23. 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]
  24. 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