-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
189 lines (171 loc) · 39.7 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
<html>
<head>
<title> Frederic Koehler </title>
<style type="text/css">
body{
line-height: 1.5;
padding: 4em 1em;
width:800px;
margin-left:auto;
margin-right:auto;
font-size:1.05em;
}
li{
margin: .9em 0;
}
.pubs-heading-container {
display: flex;
}
</style>
</head>
<body>
<img src="headshot.jpg" style="float:right;height:250px" hspace="20px">
<h1> Frederic Koehler </h1>
<p> Hi! I am an Assistant Professor of <a href="https://stat.uchicago.edu/">Statistics</a> and <a href="https://datascience.uchicago.edu/">Data Science</a> at the University of Chicago. </p>
<p> Previously I was at Stanford University as a <a href="https://theory.stanford.edu/main/index.shtml">Motwani Postdoctoral Fellow</a> in the Department of Computer Science. Right before, I was a research fellow in UC Berkeley's <a href="https://simons.berkeley.edu/">Simons Institute</a> in the Program on Computational Complexity of Statistical Inference. I received my PHD in <em>Mathematics and Statistics</em> from MIT, where I was coadvised by
<a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a> and <a href="http://math.mit.edu/~elmos/">Elchanan Mossel</a>, and before that I received my undergraduate degree in Mathematics at Princeton University. </p>
<p> 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. </p>
<p> Please feel free to reach out --- unfortunately, I may not be able to reply to every email. <br /> Email: [first initial][last name]@uchicago.edu <br /> Office: Room 203, Searle Chemistry Laboratory </p>
<h2> Teaching </h2>
<p> Winter 2025. Stat 24400: Statistical Theory and Methods I </p>
<p> Winter 2025. Data 37200/Stat 37201. Learning, Decisions, and Limits. Cotaught with Haifeng Xu. </p>
<p> Spring 2024. <a href="stat31512-s2024/index.html">Stat 31512: Analysis of Sampling Algorithms</a> </p>
<!-- <div id="pubs-heading-container">
<div style="flex: 1"> -->
<h2 style="display:inline"> Publications and Preprints </h2>
<!--
</div>
<div style="flex: 1"> -->
<a id="" href="#" onclick="document.getElementById('chronological').hidden = false;document.getElementById('subjectical').hidden = true">Chronological</a>
<a id="" href="#" onclick="document.getElementById('chronological').hidden = true;document.getElementById('subjectical').hidden = false">Subject</a>
<!--
</div>
</div> -->
<ol reversed id="chronological">
<li> <em>Efficiently learning and sampling multimodal distributions with data-based initialization</em>, joint with <a href="https://holdenlee.github.io/">Holden Lee</a> and <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. <a href="https://arxiv.org/abs/2411.09117">[arXiv:2411.09117]</a></li>
<li> <em>Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Conference on Learning Theory (COLT) 2024, To Appear. <a href="https://arxiv.org/abs/2402.15409">[arXiv:2402.15409]</a></li>
<li> <em>Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting</em>, joint with <a href="https://serinachang5.github.io/">Serina Chang</a>, <a href="https://www.zhaonanq.com/">Zhaonan Qu</a>, <a href="https://cs.stanford.edu/people/jure/">Jure Leskovec</a>, and <a href="https://web.stanford.edu/~jugander/">Johan Ugander</a>. International Conference on Machine Learning (ICML) 2024, To Appear. <a href="https://arxiv.org/abs/2402.18697">[arXiv:2402.18697]</a></li>
<li> <em>Trickle-Down in Localization Schemes and Applications</em>, joint with <a href="https://nimaanari.com">Nima Anari</a> and <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. Symposium on Theory of Computing (STOC) 2024, To Appear. <a href="http://arxiv.org/abs/2407.16104">[arXiv:2407.16104]</a> <a href="https://www.youtube.com/watch?v=UmyRoQIGtd0">[Video]</a></li>
<li> <em>Influences in Mixing Measures</em>, joint with <a href="https://mathematics.huji.ac.il/people/noam-lifshitz">Noam Lifshitz</a>, <a href="https://sites.google.com/view/dorminzer/home">Dor Minzer</a>, and <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Symposium on Theory of Computing (STOC) 2024, To Appear. <a href="https://arxiv.org/abs/2307.07625">[arXiv:2307.07625]</a> <a href="https://www.youtube.com/watch?v=_ahjeiho7CA">[Video]</a></li>
<li> <em>Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization</em>, joint with <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. International Conference on Learning Representations (ICLR), 2024.<a href="https://arxiv.org/abs/2310.01762">[arXiv:2310.01762]</a></li>
<li> <em>A Phase Transition in Arrow's Theorem with Three Alternatives</em>, joint with <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Annals of Applied Probability (AAP), 2024+, To Appear. <a href="https://arxiv.org/abs/2004.12580">[arXiv:2004.12580]</a>. </li>
<li> <em>Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses</em>, joint with <a href="https://nimaanari.com">Nima Anari</a>, <a href="https://jainvishesh.github.io">Vishesh Jain</a>, <a href="https://web.stanford.edu/~huypham/">Huy Tuan Pham</a>, and <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024. <a href="https://arxiv.org/abs/2307.10466">[arXiv:2307.10466]</a></li>
<li> <em>Uniform Convergence with Square-Root Lipschitz Loss</em>, joint with <a href="https://zhoulijia.github.io/">Lijia Zhou</a>, <a href="https://cam.uchicago.edu/people/profile/zhen-dai/">Zhen Dai</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. Advances in Neural Information Processing Systems (NeurIPS) 2023. <a href="https://arxiv.org/abs/2306.13188">[arXiv:2306.13188]</a> <a href="generalization_simons2024.pdf">[Related slides]</a></li>
<li> <em>Feature Adaptation for Sparse Linear Regression</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Advances in Neural Information Processing Systems (NeurIPS) 2023 (Spotlight Presentation). <a href="https://arxiv.org/abs/2305.16892">[arXiv:2305.16892]</a></li>
<li> <em>Statistical Efficiency of Score Matching: The View from Isoperimetry</em>, joint with Alexander Heckett and <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>. 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). <a href="https://arxiv.org/abs/2210.00726">[arXiv:2210.00726]</a> <a href="sm_slides.pdf">[slides]</a></li>
<li> <em>A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models</em>, joint with <a href="https://stat.uchicago.edu/people/profile/lijia-zhou/">Lijia Zhou</a>, <a href="https://statistics.fas.harvard.edu/people/pragya-sur-0">Pragya Sur</a>, <a href="https://djsutherland.ml">Danica J. Sutherland</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. Advances in Neural Information Processing Systems (NeurIPS) 2022. <a href="https://arxiv.org/abs/2210.12082">[arXiv:2210.12082]</a></li>
<li> <em>Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Advances in Neural Information Processing Systems (NeurIPS) 2022. <a href="https://arxiv.org/abs/2203.02824">[arXiv:2203.02823]</a></li>
<li> <em>Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods</em>, joint with <a href="https://holdenlee.github.io/">Holden Lee</a> and <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>. Conference on Learning Theory (COLT) 2022. <a href="https://arxiv.org/abs/2202.08907">[arXiv:2202.08907]</a> <a href="fodsi_june2023.pdf">[Slides]</a> <a href="https://www.youtube.com/watch?v=xuWxva7tV9g">[Video]</a></li>
<li> <em>Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression</em>, joint with <a href="https://stat.uchicago.edu/people/profile/lijia-zhou/">Lijia Zhou</a>, <a href="https://djsutherland.ml">Danica J. Sutherland</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. ACM/IMS Journal of Data Science (JDS) 2024. <a href="https://arxiv.org/abs/2112.04470">[arXiv:2112.04470]</a> <a href="https://www.youtube.com/watch?v=02KVK7MYuT4&t=3229s">[Video]</a></li>
<li> <em>Reconstruction on Trees and Low-Degree Polynomials</em>, joint with <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Advances in Neural Information Processing Systems (NeurIPS) 2022 (Oral Presentation). <a href="https://arxiv.org/abs/2109.06915">[arXiv:2109.06915]</a> </li>
<li> <em>Variational autoencoders in the presence of low-dimensional data: landscape and implicit bias</em>, joint with <a href="https://virajm.com">Viraj Mehta</a>, <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>, and <a href="https://www.cs.cmu.edu/directory/chenghuz">Chenghui Zhou</a>. International Conference on Learning Representations (ICLR) 2022. <a href="https://arxiv.org/abs/2112.06868">[arXiv:2112.06868]</a> </li>
<li> <em>Kalman Filtering with Adversarial Corruptions</em>, joint with <a href="http://people.csail.mit.edu/sitanc/">Sitan Chen</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>, and <a href="https://scholar.google.com/citations?user=maa1m0oAAAAJ&hl=en">Morris Yau</a>. Symposium on Theory of Computing (STOC) 2022. <a href="https://arxiv.org/abs/2111.06395">[arXiv:2111.06395]</a> </li>
<li> <em>Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities</em>, joint with <a href="https://nimaanari.com">Nima Anari</a>, <a href="https://jainvishesh.github.io">Vishesh Jain</a>, <a href="https://web.stanford.edu/~huypham/">Huy Tuan Pham</a>, and <a href="https://tdvuong.people.stanford.edu/about">Thuy-Duong Vuong</a>. Symposium on Theory of Computing (STOC) 2022 (extended abstract merged w/ Ent. Ind. I). <a href="https://arxiv.org/abs/2111.03247">[arXiv:2111.03247]</a>. </li>
<li> <em>Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models</em>, joint with <a href="https://nimaanari.com">Nima Anari</a>, <a href="https://jainvishesh.github.io">Vishesh Jain</a>, <a href="https://web.stanford.edu/~huypham/">Huy Tuan Pham</a>, and <a href="https://tdvuong.people.stanford.edu/about">Thuy-Duong Vuong</a>. Symposium on Theory of Computing (STOC) 2022. <a href="https://arxiv.org/abs/2106.04105">[arXiv:2106.04105]</a></li>
<li> <em>Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting</em>, joint with <a href="https://stat.uchicago.edu/people/profile/lijia-zhou/">Lijia Zhou</a>, <a href="https://djsutherland.ml">Danica J. Sutherland</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. Advances in Neural Information Processing Systems (NeurIPS) 2021 (Oral Presentation). <a href="https://arxiv.org/abs/2106.09276">[arXiv:2106.09276]</a> <a href="https://www.youtube.com/watch?v=02KVK7MYuT4&t=3331s">[Video]</a></li>
<li> <em>On the Power of Preconditioning in Sparse Linear Regression</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Symposium on Foundations of Computer Science (FOCS) 2021. <a href="https://arxiv.org/abs/2106.09207">[arXiv:2106.09207]</a> <a href="https://www.youtube.com/watch?v=PY06fuGf84o">[Video]</a> </li>
<li> <em>Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models</em>, joint with <a href="http://web.mit.edu/eboix/www/">Enric Boix-Adserà</a> and <a href="https://www.mit.edu/~gbresler/">Guy Bresler</a>. Symposium on Foundations of Computer Science (FOCS) 2021. <a href="https://arxiv.org/abs/2106.03969">[arXiv:2106.03969]</a> <a href="https://www.youtube.com/watch?v=mdajdR9Ks1E">[Video]</a></li>
<li> <em>Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination</em>, joint with <a href="http://people.csail.mit.edu/sitanc/">Sitan Chen</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>, and <a href="https://scholar.google.com/citations?user=maa1m0oAAAAJ&hl=en">Morris Yau</a>. Symposium on Foundations of Computer Science (FOCS) 2021.
<a href="https://arxiv.org/abs/2010.04157">[arXiv:2010.04157]</a>. <a href="https://www.youtube.com/watch?v=h5UReQwuzYw">[Video (Morris)]</a> </li>
<li> <em>Multidimensional Scaling: Approximation and Complexity</em>, joint with <a href="http://erikdemaine.org">Erik Demaine</a>, <a href="https://www.seas.harvard.edu/person/adam-hesterberg">Adam Hesterberg</a>, <a href="https://cs.uwaterloo.ca/about/people/jayson-lynch">Jayson Lynch</a>, and <a href="https://math.mit.edu/~urschel/">John Urschel</a>. International Conference on Machine Learning (ICML) 2021. <a href="https://arxiv.org/abs/2109.11505">[arXiv:2109.11505]</a> <a href="https://slideslive.com/38959388/multidimensional-scaling-approximation-and-complexity?ref=speaker-22321-latest">[Video]</a> </li>
<li> <em>Representational aspects of depth and conditioning in normalizing flows</em>, joint with <a href="https://github.com/virajmehta">Viraj Mehta</a> and <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>.
International Conference on Machine Learning (ICML) 2021. <a href="https://arxiv.org/abs/2010.01155">[arXiv:2010.01155]</a>. </li>
<li> <em>A Spectral Condition for Spectral Gap: Fast Mixing in High-Temperature Ising Models</em>, joint with <a href="http://www.wisdom.weizmann.ac.il/~ronene/">Ronen Eldan</a> and <a href="http://www.wisdom.weizmann.ac.il/~zeitouni/">Ofer Zeitouni</a>. Probability Theory and Related Fields (PTRF) 2021.
<a href="https://arxiv.org/abs/2007.08200">[arXiv:2007.08200]</a> <a href="https://www.youtube.com/watch?v=mRXh6t8r-OM">[Video (Ronen)]</a></li>
<li> <em>From Boltzmann Machines to Neural Networks and Back Again</em>, joint with <a href="https://www.cs.utexas.edu/~surbhi/">Surbhi Goel</a> and <a href="https://www.cs.utexas.edu/~klivans/">Adam Klivans</a>. Advances in Neural Information Processing Systems (NeurIPS) 2020.
<a href="https://arxiv.org/abs/2007.12815">[arXiv:2007.12815]</a> </li>
<li> <em>Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability</em>, joint with <a href="http://people.csail.mit.edu/sitanc/">Sitan Chen</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>, and <a href="https://scholar.google.com/citations?user=maa1m0oAAAAJ&hl=en">Morris Yau</a>. Advances in Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). <a href="https://arxiv.org/abs/2006.04787">[arXiv:2006.04787]</a> <a href="https://www.youtube.com/watch?v=MbADMtbIFz0&t=1s">[Video]</a>
</li>
<li> <em>Learning Some Popular Gaussian Graphical Models without Condition Number Bounds</em>, joint with <a href="http://math.mit.edu/~kelner/index.html">Jonathan Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. Advances in Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). <a href="http://arxiv.org/abs/1905.01282">[arXiv:1905.01282]</a>. <a href="https://www.youtube.com/watch?v=V6NMDZB6LI4&t=1136s">[Video]</a> </li>
<li> <em>Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay.</em> Advances in Neural Information Processing Systems (NeurIPS) 2019 (Spotlight presentation).
<a href="https://arxiv.org/abs/1905.09992">[arXiv:1905.09992]</a> </li>
<li> <em>Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a>, <a href="http://web.mit.edu/jingbo/www/">Jingbo Liu</a>, and <a href="http://math.mit.edu/~elmos/">Elchanan Mossel</a>. Conference on Learning Theory (COLT) 2019. <a href="https://arxiv.org/abs/1905.10031"> [arXiv:1905.10031] </a>
</li>
<li> <em>How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories</em>, joint with <a href="http://www-math.mit.edu/~younhun/">Younhun Kim</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>,
<a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>, and
<a href="http://www.mit.edu/~govind/"> Govind Ramnarayan</a>. International Conference on Research in Computational Molecular Biology (RECOMB) 2019; Journal of Computational Biology (JCB) Special Issue. <a href="https://arxiv.org/abs/1811.03177">[arXiv:1811.03177]</a></li>
<li> <em>Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a> and <a href="https://math.mit.edu/~risteski/">Andrej Risteski</a>. Symposium on Theory of Computing (STOC) 2019. <a href="https://arxiv.org/abs/1808.07226">[arXiv:1808.07226]</a></li>
<li> <em>Learning Restricted Boltzmann Machines via Influence Maximization</em>, joint with <a href="http://www.mit.edu/~gbresler/">Guy Bresler</a> and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. Symposium on Theory of Computing (STOC) 2019. <a href="https://arxiv.org/abs/1805.10262">[arXiv:1805.10262]</a> <a href="https://www.youtube.com/watch?v=eMEasYm_VWU">[Video (Ankur)]</a></li>
<li> <em> The Comparative Power of ReLU Networks and Polynomial Kernels in the Presence of Sparse Latent Structure</em>, joint with <a href="https://math.mit.edu/~risteski/">Andrej Risteski</a>. International Conference on Learning Representations (ICLR) 2019. <a href="https://arxiv.org/abs/1805.11405">[arXiv:1805.11405]</a> <a href="https://openreview.net/forum?id=rJgTTjA9tX"> [OpenReview] </a> </li>
<li> <em>The Vertex Sample Complexity of Free Energy is Polynomial</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a> and <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Conference on Learning Theory (COLT) 2018. <a href="https://arxiv.org/abs/1802.06129">[arXiv:1802.06129]</a><a href="https://www.youtube.com/watch?v=HbS80x05JQI">[Video]</a></li>
<li> <em>The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a> and <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Conference on Learning Theory (COLT) 2018. <a href="https://arxiv.org/abs/1802.06126">[arXiv:1802.06126]</a> <a href="https://www.youtube.com/watch?v=rPzczF1Ec-k">[Video]</a></li>
<li> <em> Information theoretic properties of Markov random fields, and their algorithmic applications</em>, joint with <a href="https://math.mit.edu/directory/profile.php?pid=1780">Linus Hamilton</a> and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. Advances in Neural Information Processing Systems (NeurIPS) 2017. <a href="https://arxiv.org/abs/1705.11107"> [arXiv:1705.11107] </a></li>
<li> <em> Busy Time Scheduling on a Bounded Number of Machines</em>, joint with <a href="https://www.cs.umd.edu/~samir/">Samir Khuller</a>. Algorithm and Data Structures Symposium (WADS) 2017. (<a href="busytime.pdf">Full Version</a>, <a href="wads_presentation.pdf">slides</a>) </li>
<li> <em> Provable algorithms for inference in topic models</em>, joint with <a href="https://www.cs.princeton.edu/~arora/">Sanjeev Arora</a>, <a href="https://users.cs.duke.edu/~rongge/">Rong Ge</a>, <a href="https://ai.stanford.edu/~tengyuma/">Tengyu Ma</a>, and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. International Conference on Machine Learning (ICML) 2016. <a href="https://arxiv.org/abs/1605.08491"> [arXiv:1605.08491] </a></li>
<li> <em>Optimal batch schedules for parallel machines</em>, joint with <a href="https://www.cs.umd.edu/~samir/">Samir Khuller</a>. Algorithm and Data Structures Symposium (WADS) 2013.
<a href="https://www.cs.umd.edu/~samir/grant/sched-wads.pdf">(Full version)</a> </li>
</ol>
<div id="subjectical" hidden>
<h4> Generalization theory and approximation</h4>
<ol>
<li> <em>Uniform Convergence with Square-Root Lipschitz Loss</em>, joint with <a href="https://zhoulijia.github.io/">Lijia Zhou</a>, <a href="https://cam.uchicago.edu/people/profile/zhen-dai/">Zhen Dai</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. Advances in Neural Information Processing Systems (NeurIPS) 2023. <a href="https://arxiv.org/abs/2306.13188">[arXiv:2306.13188]</a> <a href="generalization_simons2024.pdf">[Related slides]</a></li>
<li> <em>A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models</em>, joint with <a href="https://stat.uchicago.edu/people/profile/lijia-zhou/">Lijia Zhou</a>, <a href="https://statistics.fas.harvard.edu/people/pragya-sur-0">Pragya Sur</a>, <a href="https://djsutherland.ml">Danica J. Sutherland</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. Advances in Neural Information Processing Systems (NeurIPS) 2022. <a href="https://arxiv.org/abs/2210.12082">[arXiv:2210.12082]</a></li>
<li> <em>Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression</em>, joint with <a href="https://stat.uchicago.edu/people/profile/lijia-zhou/">Lijia Zhou</a>, <a href="https://djsutherland.ml">Danica J. Sutherland</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. ACM/IMS Journal of Data Science (JDS) 2024. <a href="https://arxiv.org/abs/2112.04470">[arXiv:2112.04470]</a> <a href="https://www.youtube.com/watch?v=02KVK7MYuT4&t=3229s">[Video]</a></li>
<li> <em>Reconstruction on Trees and Low-Degree Polynomials</em>, joint with <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Advances in Neural Information Processing Systems (NeurIPS) 2022 (Oral Presentation). <a href="https://arxiv.org/abs/2109.06915">[arXiv:2109.06915]</a> </li>
<li> <em>Variational autoencoders in the presence of low-dimensional data: landscape and implicit bias</em>, joint with <a href="https://virajm.com">Viraj Mehta</a>, <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>, and <a href="https://www.cs.cmu.edu/directory/chenghuz">Chenghui Zhou</a>. International Conference on Learning Representations (ICLR) 2022. <a href="https://arxiv.org/abs/2112.06868">[arXiv:2112.06868]</a> </li>
<li> <em>Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting</em>, joint with <a href="https://stat.uchicago.edu/people/profile/lijia-zhou/">Lijia Zhou</a>, <a href="https://djsutherland.ml">Danica J. Sutherland</a>, and <a href="https://home.ttic.edu/~nati/">Nathan Srebro</a>. Advances in Neural Information Processing Systems (NeurIPS) 2021 (Oral Presentation). <a href="https://arxiv.org/abs/2106.09276">[arXiv:2106.09276]</a> <a href="https://www.youtube.com/watch?v=02KVK7MYuT4&t=3331s">[Video]</a></li>
<li> <em>Representational aspects of depth and conditioning in normalizing flows</em>, joint with <a href="https://github.com/virajmehta">Viraj Mehta</a> and <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>.
International Conference on Machine Learning (ICML) 2021. <a href="https://arxiv.org/abs/2010.01155">[arXiv:2010.01155]</a>. </li>
<li> <em> The Comparative Power of ReLU Networks and Polynomial Kernels in the Presence of Sparse Latent Structure</em>, joint with <a href="https://math.mit.edu/~risteski/">Andrej Risteski</a>. International Conference on Learning Representations (ICLR) 2019. <a href="https://arxiv.org/abs/1805.11405">[arXiv:1805.11405]</a> <a href="https://openreview.net/forum?id=rJgTTjA9tX"> [OpenReview] </a> </li>
</ol>
<h4> Learning algorithms </h4>
<ol>
<li> <em>Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting</em>, joint with <a href="https://serinachang5.github.io/">Serina Chang</a>, <a href="https://www.zhaonanq.com/">Zhaonan Qu</a>, <a href="https://cs.stanford.edu/people/jure/">Jure Leskovec</a>, and <a href="https://web.stanford.edu/~jugander/">Johan Ugander</a>. International Conference on Machine Learning (ICML) 2024. <a href="https://arxiv.org/abs/2402.18697">[arXiv:2402.18697]</a></li>
<li> <em>Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Conference on Learning Theory (COLT) 2024. <a href="https://arxiv.org/abs/2402.15409">[arXiv:2402.15409]</a></li>
<li> <em>Feature Adaptation for Sparse Linear Regression</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Advances in Neural Information Processing Systems (NeurIPS) 2023 (Spotlight Presentation). <a href="https://arxiv.org/abs/2305.16892">[arXiv:2305.16892]</a></li>
<li> <em>Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Advances in Neural Information Processing Systems (NeurIPS) 2022. <a href="https://arxiv.org/abs/2203.02824">[arXiv:2203.02823]</a></li>
<li> <em>Kalman Filtering with Adversarial Corruptions</em>, joint with <a href="http://people.csail.mit.edu/sitanc/">Sitan Chen</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>, and <a href="https://scholar.google.com/citations?user=maa1m0oAAAAJ&hl=en">Morris Yau</a>. Symposium on Theory of Computing (STOC) 2022. <a href="https://arxiv.org/abs/2111.06395">[arXiv:2111.06395]</a> </li>
<li> <em>On the Power of Preconditioning in Sparse Linear Regression</em>, joint with <a href="https://math.mit.edu/~kelner/">Jon Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://www.mit.edu/~drohatgi/">Dhruv Rohatgi</a>. Symposium on Foundations of Computer Science (FOCS) 2021. <a href="https://arxiv.org/abs/2106.09207">[arXiv:2106.09207]</a> <a href="https://www.youtube.com/watch?v=PY06fuGf84o">[Video]</a> </li>
<li> <em>Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models</em>, joint with <a href="http://web.mit.edu/eboix/www/">Enric Boix-Adserà</a> and <a href="https://www.mit.edu/~gbresler/">Guy Bresler</a>. Symposium on Foundations of Computer Science (FOCS) 2021. <a href="https://arxiv.org/abs/2106.03969">[arXiv:2106.03969]</a> <a href="https://www.youtube.com/watch?v=mdajdR9Ks1E">[Video]</a></li>
<li> <em>Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination</em>, joint with <a href="http://people.csail.mit.edu/sitanc/">Sitan Chen</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>, and <a href="https://scholar.google.com/citations?user=maa1m0oAAAAJ&hl=en">Morris Yau</a>. Symposium on Foundations of Computer Science (FOCS) 2021.
<a href="https://arxiv.org/abs/2010.04157">[arXiv:2010.04157]</a>. <a href="https://www.youtube.com/watch?v=h5UReQwuzYw">[Video (Morris)]</a> </li>
<li> <em>Multidimensional Scaling: Approximation and Complexity</em>, joint with <a href="http://erikdemaine.org">Erik Demaine</a>, <a href="https://www.seas.harvard.edu/person/adam-hesterberg">Adam Hesterberg</a>, <a href="https://cs.uwaterloo.ca/about/people/jayson-lynch">Jayson Lynch</a>, and <a href="https://math.mit.edu/~urschel/">John Urschel</a>. International Conference on Machine Learning (ICML) 2021. <a href="https://arxiv.org/abs/2109.11505">[arXiv:2109.11505]</a> <a href="https://slideslive.com/38959388/multidimensional-scaling-approximation-and-complexity?ref=speaker-22321-latest">[Video]</a> </li>
<li> <em>Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability</em>, joint with <a href="http://people.csail.mit.edu/sitanc/">Sitan Chen</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>, and <a href="https://scholar.google.com/citations?user=maa1m0oAAAAJ&hl=en">Morris Yau</a>. Advances in Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). <a href="https://arxiv.org/abs/2006.04787">[arXiv:2006.04787]</a> <a href="https://www.youtube.com/watch?v=MbADMtbIFz0&t=1s">[Video]</a>
</li>
<li> <em>From Boltzmann Machines to Neural Networks and Back Again</em>, joint with <a href="https://www.cs.utexas.edu/~surbhi/">Surbhi Goel</a> and <a href="https://www.cs.utexas.edu/~klivans/">Adam Klivans</a>. Advances in Neural Information Processing Systems (NeurIPS) 2020.
<li> <em>Learning Some Popular Gaussian Graphical Models without Condition Number Bounds</em>, joint with <a href="http://math.mit.edu/~kelner/index.html">Jonathan Kelner</a>, <a href="https://raghumeka.github.io">Raghu Meka</a>, and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. Advances in Neural Information Processing Systems (NeurIPS) 2020 (Spotlight Presentation). <a href="http://arxiv.org/abs/1905.01282">[arXiv:1905.01282]</a>. <a href="https://www.youtube.com/watch?v=V6NMDZB6LI4&t=1136s">[Video]</a> </li>
<li> <em>How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories</em>, joint with <a href="http://www-math.mit.edu/~younhun/">Younhun Kim</a>, <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>,
<a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>, and
<a href="http://www.mit.edu/~govind/"> Govind Ramnarayan</a>. International Conference on Research in Computational Molecular Biology (RECOMB) 2019; Journal of Computational Biology (JCB) Special Issue. <a href="https://arxiv.org/abs/1811.03177">[arXiv:1811.03177]</a></li>
<li> <em>Learning Restricted Boltzmann Machines via Influence Maximization</em>, joint with <a href="http://www.mit.edu/~gbresler/">Guy Bresler</a> and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. Symposium on Theory of Computing (STOC) 2019. <a href="https://arxiv.org/abs/1805.10262">[arXiv:1805.10262]</a> <a href="https://www.youtube.com/watch?v=eMEasYm_VWU">[Video (Ankur)]</a></li>
<li> <em> Information theoretic properties of Markov random fields, and their algorithmic applications</em>, joint with <a href="https://math.mit.edu/directory/profile.php?pid=1780">Linus Hamilton</a> and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. Advances in Neural Information Processing Systems (NeurIPS) 2017. <a href="https://arxiv.org/abs/1705.11107"> [arXiv:1705.11107] </a></li>
<li> <em> Provable algorithms for inference in topic models</em>, joint with <a href="https://www.cs.princeton.edu/~arora/">Sanjeev Arora</a>, <a href="https://users.cs.duke.edu/~rongge/">Rong Ge</a>, <a href="https://ai.stanford.edu/~tengyuma/">Tengyu Ma</a>, and <a href="http://people.csail.mit.edu/moitra/">Ankur Moitra</a>. International Conference on Machine Learning (ICML) 2016. <a href="https://arxiv.org/abs/1605.08491"> [arXiv:1605.08491] </a></li>
</ol>
<h4> Sampling and variational inference </h4>
<ol>
<li> <em>Efficiently learning and sampling multimodal distributions with data-based initialization</em>, joint with <a href="https://holdenlee.github.io/">Holden Lee</a> and <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. <a href="https://arxiv.org/abs/2411.09117">[arXiv:2411.09117]</a></li>
<li> <em>Trickle-Down in Localization Schemes and Applications</em>, joint with <a href="https://nimaanari.com">Nima Anari</a> and <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. Symposium on Theory of Computing (STOC) 2024, To Appear. <a href="http://arxiv.org/abs/2407.16104">[arXiv:2407.16104]</a> <a href="https://www.youtube.com/watch?v=UmyRoQIGtd0">[Video]</a> </li>
<li> <em>Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization</em>, joint with <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. International Conference on Learning Representations (ICLR), 2024. <a href="https://arxiv.org/abs/2310.01762">[arXiv:2310.01762]</a></li>
<li> <em>Influences in Mixing Measures</em>, joint with <a href="https://mathematics.huji.ac.il/people/noam-lifshitz">Noam Lifshitz</a>, <a href="https://sites.google.com/view/dorminzer/home">Dor Minzer</a>, and <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Symposium on Theory of Computing (STOC) 2024, To Appear. <a href="https://arxiv.org/abs/2307.07625">[arXiv:2307.07625]</a><a href="https://www.youtube.com/watch?v=_ahjeiho7CA">[Video]</a></li>
<li> <em>A Phase Transition in Arrow's Theorem with Three Alternatives</em>, joint with <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Annals of Applied Probability (AAP), 2024+ (To Appear). <a href="https://arxiv.org/abs/2004.12580">[arXiv:2004.12580]</a> </li>
<li> <em>Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses</em>, joint with <a href="https://nimaanari.com">Nima Anari</a>, <a href="https://jainvishesh.github.io">Vishesh Jain</a>, <a href="https://web.stanford.edu/~huypham/">Huy Tuan Pham</a>, and <a href="https://thuyduongvuong.github.io/index.html">Thuy-Duong Vuong</a>. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024, To Appear. <a href="https://arxiv.org/abs/2307.10466">[arXiv:2307.10466]</a></li>
<li> <em>Statistical Efficiency of Score Matching: The View from Isoperimetry</em>, joint with Alexander Heckett and <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>. 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), To Appear. <a href="https://arxiv.org/abs/2210.00726">[arXiv:2210.00726]</a></li>
<li> <em>Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods</em>, joint with <a href="https://holdenlee.github.io/">Holden Lee</a> and <a href="https://www.andrew.cmu.edu/user/aristesk/">Andrej Risteski</a>. Conference on Learning Theory (COLT) 2022. <a href="https://arxiv.org/abs/2202.08907">[arXiv:2202.08907]</a><a href="fodsi_june2023.pdf">[Slides]</a> <a href="https://www.youtube.com/watch?v=xuWxva7tV9g">[Video]</a></li>
<li> <em>Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities</em>, joint with <a href="https://nimaanari.com">Nima Anari</a>, <a href="https://jainvishesh.github.io">Vishesh Jain</a>, <a href="https://web.stanford.edu/~huypham/">Huy Tuan Pham</a>, and <a href="https://tdvuong.people.stanford.edu/about">Thuy-Duong Vuong</a>. Symposium on Theory of Computing (STOC) 2022 (extended abstract merged w/ Ent. Ind. I). <a href="https://arxiv.org/abs/2111.03247">[arXiv:2111.03247]</a>. </li>
<li> <em>Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models</em>, joint with <a href="https://nimaanari.com">Nima Anari</a>, <a href="https://jainvishesh.github.io">Vishesh Jain</a>, <a href="https://web.stanford.edu/~huypham/">Huy Tuan Pham</a>, and <a href="https://tdvuong.people.stanford.edu/about">Thuy-Duong Vuong</a>. Symposium on Theory of Computing (STOC) 2022. <a href="https://arxiv.org/abs/2106.04105">[arXiv:2106.04105]</a></li>
<li> <em>A Spectral Condition for Spectral Gap: Fast Mixing in High-Temperature Ising Models</em>, joint with <a href="http://www.wisdom.weizmann.ac.il/~ronene/">Ronen Eldan</a> and <a href="http://www.wisdom.weizmann.ac.il/~zeitouni/">Ofer Zeitouni</a>. Probability Theory and Related Fields (PTRF) 2021.
<a href="https://arxiv.org/abs/2007.08200">[arXiv:2007.08200]</a> <a href="https://www.youtube.com/watch?v=mRXh6t8r-OM">[Video (Ronen)]</a></li>
<li> <em>Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay.</em> Advances in Neural Information Processing Systems (NeurIPS) 2019 (Spotlight presentation).
<a href="https://arxiv.org/abs/1905.09992">[arXiv:1905.09992]</a> </li>
<li> <em>Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a>, <a href="http://web.mit.edu/jingbo/www/">Jingbo Liu</a>, and <a href="http://math.mit.edu/~elmos/">Elchanan Mossel</a>. Conference on Learning Theory (COLT) 2019. <a href="https://arxiv.org/abs/1905.10031"> [arXiv:1905.10031] </a>
</li>
<li> <em>Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a> and <a href="https://math.mit.edu/~risteski/">Andrej Risteski</a>. Symposium on Theory of Computing (STOC) 2019. <a href="https://arxiv.org/abs/1808.07226">[arXiv:1808.07226]</a></li>
<li> <em>The Vertex Sample Complexity of Free Energy is Polynomial</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a> and <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Conference on Learning Theory (COLT) 2018. <a href="https://arxiv.org/abs/1802.06129">[arXiv:1802.06129]</a><a href="https://www.youtube.com/watch?v=HbS80x05JQI">[Video]</a></li>
<li> <em>The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity</em>, joint with <a href="http://math.mit.edu/~visheshj/">Vishesh Jain</a> and <a href="http://www-math.mit.edu/~elmos/"> Elchanan Mossel</a>. Conference on Learning Theory (COLT) 2018. <a href="https://arxiv.org/abs/1802.06126">[arXiv:1802.06126]</a> <a href="https://www.youtube.com/watch?v=rPzczF1Ec-k">[Video]</a></li>
</ol>
<h4> Scheduling algorithms </h4>
<ol>
<li> <em> Busy Time Scheduling on a Bounded Number of Machines</em>, joint with <a href="https://www.cs.umd.edu/~samir/">Samir Khuller</a>. Algorithm and Data Structures Symposium (WADS) 2017. (<a href="busytime.pdf">Full Version</a>, <a href="wads_presentation.pdf">slides</a>) </li>
<li> <em>Optimal batch schedules for parallel machines</em>, joint with <a href="https://www.cs.umd.edu/~samir/">Samir Khuller</a>. Algorithm and Data Structures Symposium (WADS) 2013.
<a href="https://www.cs.umd.edu/~samir/grant/sched-wads.pdf">(Full version)</a> </li>
</ol>
</div>
<p> In most cases, authors are listed in alphabetical order, following the convention in mathematics and theoretical computer science. </p>
<p> <b> Miscellaneous service: </b> 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). </p>
<!-- <p> (Publications list: for now refer to <a href="https://scholar.google.com/citations?user=Atc5w-4AAAAJ&hl=en"> Google Scholar </a>) </p>
<p> For anyone looking for a full version of Busy Time Scheduling on a Bounded Number of Machines (WADS 2017): (<a href="busytime.pdf"> busytime.pdf </a>, <a href="wads_presentation.pdf"> slides </a>) </p> -->
<h2> Notes </h2>
<ol> <li> <a href="tv_note.pdf"> A Note on Minimax Learning of Tree Models.</a> Superceded by Appendix to "Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models." </li>
</ol>
</body>
</html>