Conference Program
Monday, June 29 (Workshops, Tutorials and Community Events)
Workshop Session 1 (8:30–10:10)
| Track 1 — Mission ABC | Track 2 — Mission DE | Track 3 — WDE Boat 1 |
|---|---|---|
| 8:30–10:10 Workshop on Learning in an Agentic World: Foundations and Challenges Hedyeh Beyhaghi, Avrim Blum, Han Shao, Dravyansh Sharma |
8:30–10:10 Computational Foundations of Reliable Learning Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan |
8:30–10:10 Bridging Computational and Statistical Theories of Machine Learning Shivani Agarwal |
☕ Coffee break (10:10–10:30)
Workshop Session 2 (10:30–12:30)
| Track 1 — Mission ABC | Track 2 — Mission DE | Track 3 — WDE Boat 1 |
|---|---|---|
| 10:30–12:30 Foundations of Learning Reasoning Models Nived Rajaraman, Nirmit Joshi, Nati Srebro |
10:30–12:30 Algorithmic Landscape of Sampling in Modern Generative Models Sitan Chen, Noah Golowich, Dhruv Rohatgi, Abishek Shetty |
10:30–12:30 Learning-Augmented Algorithms: Leveraging Data for Performance with Theoretical Guarantees Maryam Aliakbarpour, Dravyansh Sharma, Sandeep Silwal |
🍽 Lunch & Poster Session (12:30–14:00)
Workshop Session 3 (14:00–16:00)
| Track 1 — Mission ABC | Track 2 — Mission DE | Track 3 — WDE Boat 1 |
|---|---|---|
| 14:30 – 16:00 LeT-All Community Event: A Machine Learning Theory Retrospective Gautam Kamath, Jess Sorrell, Ira Globus-Harris, Bingbin Liu |
14:00–16:00 Second Workshop on the Foundations of Post-training Nived Rajaraman, Ayush Sekhari, Bingbin Liu, Akshay Krishnamurthy, Dylan Foster |
14:00–16:00 Equivalences between lower bounds frameworks: Low-degree polynomials and physics predictions Ilias Zadik |
Workshop Session 4 (16:00–17:00)
| Track 1 — Mission ABC |
|---|
| 16:00–17:00 LeT-All Community Event: Mentoring Tables |
Tuesday, June 30
Session 5 (8:30 – 9:55)
| Track 1 — Mission ABC Bandits / Online Learning |
Track 2 — Mission DE High-Dimensional Statistics |
|---|---|
| 8:30 – 8:38 Truly Adapting to Adversarial Constraints in Constrained MABs Francesco Emanuele Stradi (Politecnico di Milano); Kalana Kalupahana (Politecnico di Milano); Matteo Castiglioni (Politecnico di Milano); Alberto Marchesi (Politecnico di Milano); Nicola Gatti (Politecnico di Milano) |
8:30 – 8:38 Finite Sample Bounds for Learning with Score Matching Devin Smedira (MIT); Abhijith Jayakumar (Los Alamos National Lab); Sidhant Misra (Los Alamos National Lab); Marc Vuffray (Los Alamos National Lab); Andrey Lokhov (Los Alamos National Lab) |
| 8:41 – 8:49 Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret Shinji Ito (University of Tokyo); Haipeng Luo (University of Southern California); Arnab Maiti (University of Washington); Taira Tsuchiya (University of Tokyo); Yue Wu (University of Southern California) |
8:41 – 8:49 Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method Francisco Pernice (MIT); David Gamarnik (MIT); Yatin Dandi (EPFL); Lenka Zdeborova (EPFL) |
| 8:52 – 9:00 The Hidden Cost of Approximation in Online Mirror Descent Ofir Schlisselberg (Tel Aviv University); Uri Sherman (Tel Aviv University); Tomer Koren (Tel Aviv University and Google Research); Yishay Mansour ( Tel Aviv University and Google Research) |
8:52 – 9:00 Variational Tail Bounds for Norms of Random Vectors and Matrices Sohail Bahmani (Georgia Institute of Technology) |
| 9:03 – 9:11 Ambiguous Online Learning Vanessa Kosoy (Technion – Israel Institute of Technology) |
9:03 – 9:11 Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures Prashanti Anderson (MIT); Mitali Bafna (University of Washington); Rares-Darius Buhai (EPFL); Pravesh K. Kothari (Princeton University); David Steurer (ETH Zurich) |
| 9:14 – 9:22 A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization Yi-Han Wang (Nanjing University); Peng Zhao (Nanjing University); Zhi-Hua Zhou (Nanjing University) |
9:14 – 9:22 Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz–Parisi Potential Joonhyung Shin (University of Chicago); Frederic Koehler (University of Chicago) |
| 9:25 – 9:33 Learning from Equivalence Queries, Revisited Mark Braverman (Princeton); Roi Livni (Tel Aviv University); Yishay Mansour (Tel-Aviv University); Shay Moran (-); Kobbi Nissim (Georgetown) |
9:25 – 9:33 Almost sure null bankruptcy of test-by-betting strategies Hongjian Wang (Carnegie Mellon University); Shubhada Agrawal (Indian Institute of Science); Aaditya Ramdas (Carnegie Mellon University) |
| 9:36 – 9:44 Omniprediction with Long-Term Constraints Yahav Bechavod (University of Pennsylvania); Aaron Roth (University of Pennsylvania); Jiuyao Lu ( University of Pennsylvania) |
9:36 – 9:44 A Distribution Testing Approach to Clustering Distributions Gunjan Kumar (IIT Kanpur); Yash Pote (NUS); Jonathan Scarlett (National University of Singapore) |
| 9:47 – 9:55 Swap Regret Minimization Through Response-Based Approachability Ioannis Anagnostides (Carnegie Mellon University); Gabriele Farina (MIT); Maxwell Fishelson (MIT); Haipeng Luo (University of Southern California); Jon Schneider (Google) |
9:47 – 9:55 How fast can you find a good hypothesis? Anders Aamand (University of Copenhagen); Maryam Aliakbarpour (Rice University); Justin Chen (MIT); Sandeep Silwal (UW Madison) |
☕ Coffee Break (9:58 – 10:30)
Invited Talk (10:30 – 11:30): Shafi Goldwasser, MIT and UC Berkeley — Mission ABC
From Cryptography to ML Theory and Practice
Session 6 (11:35 – 12:27)
| Track 1 — Mission ABC Bandits |
Track 2 — Mission DE High-Dimensional Statistics (Graphs) |
|---|---|
| 11:35 – 11:43 Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader Jongyeong Lee (Korea Institute of Science and Technology); Junya Honda (Kyoto University, RIKEN AIP); Shinji Ito (The University of Tokyo, RIKEN AIP); Chansoo Kim (Korea Institute of Science and Technology) |
11:35 – 11:43 Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations Andreas Göbel (Hasso Plattner Institute); Marcus Pappik (Hasso Plattner Institute); Leon Schiller (Hasso Plattner Institute) |
| 11:46 – 11:54 Learning Periodic Strategies in Blocking Bandits is as Hard as Bandits with Switching Costs Nicolò Cesa-Bianchi (Università degli Studi di Milano/Politecnico di Milano); Junya Honda (Kyoto University / RIKEN AIP); Yuko Kuroki (Intesa Sanpaolo AI Research); Atsushi Miyauchi (Intesa Sanpaolo); Lukas Zierahn (Centrum Wiskunde & Informatica/Booking.com) |
11:46 – 11:54 Spectral Recovery of a Planted Triangle-Dense Subgraph Sam van der Poel (Georgia Institute of Technology); Cheng Mao (Georgia Institute of Technology); Benjamin McKenna (Georgia Institute of Technology) |
| 11:57 – 12:05 Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach Hao Qiu (Università degli Studi di Milano); Mengxiao Zhang (University of Iowa); Nicolò Cesa-Bianchi (Università degli Studi di Milano) |
11:57 – 12:05 Recovery thresholds for hidden weighted sparse graphs Zhe Hou (Nanjing University); Jingcheng Liu (Nanjing University) |
| 12:08 – 12:16 On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits Arnab Maiti (University of Washington); Yunbei Xu (National University of Singapore); Kevin Jamieson (University of Washington) |
12:08 – 12:16 Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares Andreas Göbel (Hasso Plattner Institute); Janosch Ruff (Hasso Plattner Institute); Leon Schiller (Hasso Plattner Institute) |
| 12:19 – 12:27 Avoiding exp($k^*$) Scaling for Thompson Sampling in Combinatorial Semi-Bandits: From Multiple Seeds to a Single Seed Tianyuan Jin (National University of Singapore); Heyang Zhao (University of California, Los Angeles); Vincent Tan (National University of Singapore); Quanquan Gu (University of California, Los Angeles) |
12:19 – 12:27 Active Learning on Adversarially Corrupted Graphs Marco Bressan (Università degli Studi di Milano); Nicolò Cesa-Bianchi (Università degli Studi di Milano and Politecnico di Milano); Tommaso d'Orsi (Bocconi); Emmanuel Esposito (Università degli Studi di Milano); Silvio Lattanzi (Google Research) |
🍽 Lunch & Poster Session (12:30 – 14:00)
Session 7 (14:00 – 15:03)
| Track 1 — Mission ABC Reinforcement Learning & Control |
Track 2 — Mission DE Optimization |
|---|---|
| 14:00 – 14:08 Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum Nived Rajaraman (University of California, Berkeley); Audrey Huang (University of Illinois Urbana Champaign); Miro Dudik (Microsoft Research); Robert Schapire (Microsoft Research); Dylan J. Foster (Microsoft Research); Akshay Krishnamurthy (Microsoft Research) |
14:00 – 14:08 Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size Michal Derezinski (University of Michigan); Xiaoyu Dong (National University of Singapore) |
| 14:11 – 14:19 A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak–Ruppert Averaging Wei-Cheng Lee (Kaust); Francesco Orabona (Kaust) |
14:11 – 14:19 Fast, Parallel, Query-Efficient Binary Classification Ishani Karmarkar (Stanford University); Liam O'Carroll (Stanford University); Aaron Sidford (Stanford University) |
| 14:22 – 14:30 Continuous time policy evaluation is easier with noisy dynamics Samuel Robertson (University of Alberta); Thomas Newton (University of Waterloo); Csaba Szepesvari (University of Alberta) |
14:22 – 14:30 Learning Decision-Sufficient Representations for Linear Optimization Yuhan Ye (MIT); Saurabh Amin (MIT); Asuman Ozdaglar (MIT) |
| 14:33 – 14:41 Wasserstein Policy Learning for Distributional Outcomes Yiyan Huang (City University of Hong Kong); Cheuk Hang Leung (City University of Hong Kong); Qi Wu (City University of Hong Kong); Zhiheng Zhang (The Shanghai University of Finance and Economics) |
14:33 – 14:41 Random Reshuffling Dominates Stochastic Gradient Descent Zijian Liu (New York University) |
| 14:44 – 14:52 Randomization for Faster Exact Optimization of Discounted Markov Decision Processes Andrei Graur (Stanford University); Aaron Sidford (Stanford University); Ta-Wei Tu (Stanford University) |
14:44 – 14:52 High Probability Convergence Guarantees of Stochastic Gradient Descent Ascent in Structured Nonconvex Min-Max Games Junsoo Ha (Seoul National University) |
| 14:55 – 15:03 Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs Guy Zamir (University of Wisconsin-Madison); Matthew Zurek (University of Wisconsin-Madison); Yudong Chen (University of Wisconsin-Madison) |
14:55 – 15:03 How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-Dimensional Neural Network Regression? Kuo-Wei Lai (Georgia Institute of Technology); Guanghui Wang (Georgia Institute of Technology); Molei Tao (Georgia Institute of Technology); Vidya Muthukumar (Georgia Institute of Technology) |
☕ Coffee Break (15:06 – 15:40)
Session 8 (15:40 – 16:54)
| Track 1 — Mission ABC Online Learning |
Track 2 — Mission DE Algebra & Structured Computation / Computational Complexity & Combinatorial Optimization |
|---|---|
| 15:40 – 15:48 Revisiting Gradient Equilibrium Nika Haghtalab (University of California, Berkeley); Michael Jordan (UC Berkeley); Brian Lee (UC Berkeley); Ryan Tibshirani (UC Berkeley) |
15:40 – 15:48 Efficient Learning and Symmetry Discovery under Exact Invariances Ashkan Soleymani (MIT); Behrooz Tahmasebi (MIT); Patrick Jaillet (MIT); Stefanie Jegelka (MIT) |
| 15:51 – 15:59 Language Generation with Infinite Contamination Anay Mehrotra (Stanford University); Grigoris Velegkas (Google Research); Xifan Yu (Yale University); Felix Zhou (Yale University) |
15:51 – 15:59 Data Augmentation: A Fourier Analysis Perspective Behrooz Tahmasebi (MIT); Melanie Weber (Harvard University); Stefanie Jegelka (MIT) |
| 16:02 – 16:10 Gradient-Variation Regret Bounds for Unconstrained Online Learning Yuheng Zhao (Nanjing University); Andrew Jacobsen (University of Milan); Nicolò Cesa-Bianchi (University of Milan); Peng Zhao (Nanjing University) |
16:02 – 16:10 Low-Degree Method Fails to Predict Robust Subspace Recovery He Jia (Northwestern University); Aravindan Vijayaraghavan (Northwestern University) |
| 16:13 – 16:21 Online Realizable Regression and Applications for ReLU Networks Ilan Doron-Arad (MIT); Idan Mehalel (The Hebrew University of Jerusalem); Elchanan Mossel (MIT) |
16:13 – 16:21 The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds Konstantinos Tsirkas (Yale University); Leda Wang (Yale University); Ilias Zadik (Yale University) |
| 16:24 – 16:32 Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness Moise Blanchard (Georgia Institute of Technology); Alexander Rakhlin (MIT); Abhishek Shetty (MIT) |
16:24 – 16:32 Spectral Valleys and Sharp Failures in Greedy Determinant Maximization Rajiv Khanna (Purdue University) |
| 16:35 – 16:43 Optimal Reconstruction from Linear Queries Yuval Filmus (Technion); Shay Moran (Technion); Elizaveta Nesterova (Technion) |
16:35 – 16:43 Stable algorithms Lower Bounds for Estimation from MMSE Discontinuities Xifan Yu (Yale University); Ilias Zadik (Yale University) |
| 16:46 – 16:54 Computing Lewis weights to high precision using local relative smoothness Sander Gribling (Tilburg University); Aaron Sidford (Stanford University); Chenyi Zhang (Stanford) |
📋 Business Meeting (17:00 – 18:00) — Mission ABC
Wednesday, July 1
Session 9 (8:30 – 10:06)
| Track 1 — Mission ABC Online Learning |
Track 2 — Mission DE Statistical Learning Theory |
|---|---|
| 8:30 – 8:38 On the Importance of Randomization in Discriminative Feature Feedback Valentio Iverson (University Waterloo); Tosca Lechner (Vector Institute); Sivan Sabato (McMaster University) |
8:30 – 8:38 Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization Jingfeng Wu (University of California, Berkeley); Peter Bartlett (University of California, Berkeley); Jason Lee (University of California, Berkeley); Sham Kakade (Harvard University); Bin Yu (University of California, Berkeley) |
| 8:41 – 8:49 Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization Ruichen Jiang (UT Austin); Zakaria Mhammedi (Google Research); Mehryar Mohri (Google Research); Aryan Mokhtari (UT Austin) |
8:41 – 8:49 Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning David Kattermann (JKU Linz); Lothar Sebastian Krapp (University of Zurich) |
| 8:52 – 9:00 Distribution-Free Sequential Prediction with Abstentions Jialin Yu (Georgia Institute of Technology); Moise Blanchard (Georgia Institute of Technology) |
8:52 – 9:00 Second-Order Bounds for [0,1]-Valued Regression via Betting Loss Yinan Li (University of Arizona); Sungjoon Yoon (University of Arizona); Ethan Huang (University of Arizona); Kwang-Sung Jun (University of Arizona) |
| 9:03 – 9:11 Efficient Swap Multicalibration of Elicitable Properties Lunjia Hu (Northeastern University); Haipeng Luo (University of Southern California); Spandan Senapati (University of Southern California); Vatsal Sharan (University of Southern California) |
9:03 – 9:11 Learning Conditional Averages Marco Bressan (University of Milan); Nataly Brukhim (Institute for Advanced Study); Nicolò Cesa-Bianchi (University of Milan); Emmanuel Esposito (University of Milan); Yishay Mansour (Tel Aviv University and Google Research); Shay Moran (Technion and Google Research); Maximilian Thiessen (TU Wien) |
| 9:14 – 9:22 Space-Efficient Language Generation in the Limit Nicolas Flammarion (EPFL); Chirag Pabbaraju (Stanford); Hristo Papazov (EPFL); Miltiadis Stouras (EPFL); Ola Svensson (EPFL) |
9:14 – 9:22 Uniform Laws of Large Numbers in Product Spaces Ron Holzman (Technion); Shay Moran (Technion); Alexander Shlimovich (Technion) |
| 9:25 – 9:33 Online Learning with Simulators: No Regret in a Computationally Bounded World Sasha Voitovych (Massachusetts Institute of Technology); Alexander Rakhlin (Massachusetts Institute of Technology); Abhishek Shetty (Massachusetts Institute of Technology); Noah Golowich (Microsoft Research) |
9:25 – 9:33 A Perfectly Truthful Calibration Measure Jason Hartline (Northwestern University); Lunjia Hu (Northeastern University); Yifan Wu (Microsoft Research) |
| 9:36 – 9:44 Regret Minimization with Adaptive Opponents in Repeated Games Mingyang Liu (Massachusetts Institute of Technology); Asuman Ozdaglar (Massachusetts Institute of Technology); Tiancheng Yu (OpenAI); Kaiqing Zhang (University of Maryland, College Park) |
9:36 – 9:44 Adaptive Weighted Averaging Aditya Bhaskara (University of Utah); Ashok Cutkosky (Boston University); Ravi Kumar (Google); Manish Purohit (Google) |
| 9:47 – 9:55 Self-normalized martingales under smoothness assumption and uniform regret bounds for sequential linear regression Fan Chen (MIT); Jian Qian (HKU); Alexander Rakhlin (MIT); Nikita Zhivotovskiy (UCB) |
9:47 – 9:55 Sample-Efficient Omniprediction for Proper Losses Isaac Gibbs (University of California, Berkeley); Ryan Tibshirani (University of California, Berkeley) |
| 9:58 – 10:06 On Randomized Algorithms in Online Strategic Classification Chase Hutton (University of Maryland); Adam Melrod (Harvard University); Han Shao (University of Maryland) |
9:58 – 10:06 Statistical Learning from Attribution Sets Lorne Applebaum (Google); Robert Busa-Fekete (Google); August Chen (Cornell); Claudio Gentile (Google Research); Tomer Koren (Google and Tel Aviv University); Aryan Mokhtari (University of Texas at Austin) |
☕ Coffee Break (10:09 – 10:35)
Invited Talk (10:35 – 11:35): Maria-Florina Balcan, CMU — Mission ABC
Learnability of Complex Objects in Modern AI
Show Abstract
As machine learning and AI systems become increasingly pervasive and are deployed in high-stakes domains, developing theoretical foundations to understand and analyze their behavior has become more challenging, yet more pressing than ever before. Modern AI systems learn sophisticated structures that far exceed the analytical reach of classical learning theory and increasingly operate in environments where learning occurs in the presence of other learners.
In this talk, I will present new directions in learning theory that provide principled guarantees for increasingly complex AI systems. I will discuss general learnability guarantees for rich structured objects based on dual function classes and show how they apply to a broad range of settings, including using machine learning for algorithm design and automating hyperparameter tuning for machine learning itself. Finally, I will highlight emerging challenges for learning in the presence of other learners, spanning both cooperative settings and competitive strategic interactions.
Session 10 (11:40 – 12:21)
| Track 1 — Mission ABC Bandits |
Track 2 — Mission DE Quantum Learning |
|---|---|
| 11:40 – 11:48 Self-Concordant Perturbations for Linear Bandits Lucas Lévy (Ecole Polytechnique); Jean-Lou Valeau (ENSAE Paris); Arya Akhavan (University of Oxford); Patrick Rebeschini (University of Oxford) |
11:40 – 11:48 Learning depth-3 circuits via quantum agnostic boosting Srinivasan Arunachalam (IBM); Arkopal Dutt (IBM); Alexandru Gheorghiu (IBM); Michael de Oliveira (LIP6, Sorbonne Universite) |
| 11:51 – 11:59 On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits Leo Maynard-Zhang (University of Washington); Zhihan Xiong (University of Washington); Kevin Jamieson (University of Washington); Maryam Fazel (University of Washington) |
11:51 – 11:59 Cloning is as Hard as Learning for Stabilizer States Nikhil Bansal (University of Warwick); Matthias C. Caro (University of Warwick); Gaurav Mahajan (Yale University) |
| 12:02 – 12:10 A Complexity Measure for Active Learning in Multi-group Mean Estimation Abdellah Aznag (Columbia University); Adam Elmachtoub (Columbia University); Rachel Cummings (Columbia University) |
12:02 – 12:10 Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood Sitan Chen (Harvard University); Weiyuan Gong (Harvard University); Jonas Haferkamp (Saarland University); Yihui Quek (EPFL) |
| 12:13 – 12:21 Sharp analysis of linear ensemble sampling Arya Akhavan (University of Oxford); David Janz (University of Alberta); Csaba Szepesvari (University of Alberta) |
12:13 – 12:21 Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach Senrui Chen (California Institute of Technology); Weiyuan Gong (Harvard University); Sisi Zhou (University of Waterloo) |
🍽 Lunch & Poster Session (12:24 – 13:50)
Session 11 (13:50 – 15:26)
| Track 1 — Mission ABC Online Learning / Reinforcement Learning & Control |
Track 2 — Mission DE Privacy |
|---|---|
| 13:50 – 13:58 Calibeating Made Simple Yurong Chen (Inria, Ecole Normale Supérieure, PSL Research University); Zhiyi Huang (The University of Hong Kong); Michael Jordan (Inria Paris; University of California, Berkeley); Haipeng Luo (University of Southern California) |
13:50 – 13:58 Minimax optimal differentially private synthetic data for smooth queries Rundong Ding (University of Southern California); Yiyun He (University of California San Diego); Yizhe Zhu (University of Southern California) |
| 14:01 – 14:09 Tight Sample Complexity Bounds for Entropic Best Policy Identification Amer Essakine (ENS Paris Saclay); Claire Vernade (University of technology Nuremberg) |
14:01 – 14:09 Nearly Linear-Time User-Level DP-SCO with Optimal Rates Badih Ghazi (Google); Ravi Kumar (Google); Daogao Liu (Google); Pasin Manurangsi (Google) |
| 14:12 – 14:20 Stochastic Safe Action Model Learning Zihao Deng (Amazon); Brendan Juba (Washington University in St Louis) |
14:12 – 14:20 Fixed-Parameter Tractability of Private Synthetic Data Generation Badih Ghazi (Google); Cristobal Guzman (Pontificia Universidad Católica de Chile); Pritish Kamath (Google); Alexander Knop (Google); Ravi Kumar (Google); Pasin Manurangsi (Google) |
| 14:23 – 14:31 Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear q-pi Realizability and Concentrability Volodymyr Tkachuk (University of Alberta); Csaba Szepesvári (University of Alberta); Xiaoqi Tan (University of Alberta) |
14:23 – 14:31 On the Gradient Complexity of Private Optimization with Private Oracles Michael Menart (The Ohio State University); Aleksandar Nikolov (University of Toronto) |
| 14:34 – 14:42 Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning HARIN LEE (University of Washington); Min-hwan Oh (Seoul National University) |
14:34 – 14:42 Differentially Private Language Generation in the Limit Anay Mehrotra (Stanford University); Grigoris Velegkas (Google Research); Xifan Yu (Yale University); Felix Zhou (Yale University) |
| 14:45 – 14:53 Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment Ved Sriraman (Columbia University); Adam Block (Columbia University) |
14:45 – 14:53 Ripple Mechanisms for Discrete and Private Statistics Matthew Joseph (Google); Alex Kulesza (Google Research); Yuyan Wang (Google Research); Alexander Yu (Google Research) |
| 14:56 – 15:04 Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation Junyan Liu (University of Washington); Haipeng Luo (University of Southern California); Zihan Zhang (Hong Kong University of Science and Technology); Lillian Ratliff (University of Washington) |
14:56 – 15:04 On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA Syamantak Kumar (University of Texas at Austin); Shourya Pandey (University of Texas at Austin); Purnamrita Sarkar (University of Texas at Austin); Kevin Tian (University of Texas at Austin) |
| 15:07 – 15:15 Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs Tianhao Wu (University of Wisconsin-Madison); Matthew Zurek (University of Wisconsin-Madison); Weina Wang (Carnegie Mellon University); Qiaomin Xie (University of Wisconsin-Madison) |
15:07 – 15:15 Privately Estimating Black-Box Statistics Gunter Steinke (University of Canterbury); Thomas Steinke (Google) |
| 15:18 – 15:26 Private Linear Regression via a Down-Sensitivity to Privacy Reduction Ittai Rubinstein (Massachusetts Institute of Technology); Chris Ge ( Massachusetts Institute of Technology); Samuel Hopkins ( Massachusetts Institute of Technology) |
☕ Coffee Break (15:29 – 15:55)
Session 12 (15:55 – 16:58)
| Track 1 — Mission ABC Online Learning |
Track 2 — Mission DE Statistical Learning Theory |
|---|---|
| 15:55 – 16:03 Toward Simultaneously Optimal Regret in U-Calibration Rafael Frongillo (University of Colorado Boulder); Haipeng Luo (USC); Nishant Mehta (Victoria); Jon Schneider (Google) |
15:55 – 16:03 Model Agreement via Anchoring Eric Eaton (University of Pennsylvania); Surbhi Goel (University of Pennsylvania); Marcel Hussing (University of Pennsylvania); Michael Kearns (University of Pennsylvania); Aaron Roth (University of Pennsylvania); Sikata Sengupta (University of Pennsylvania); Jessica Sorrell (Johns Hopkins University) |
| 16:06 – 16:14 Defensive Generation Gabriele Farina (MIT); Juan Perdomo (MIT) |
16:06 – 16:14 Boosting with List-Decodable Codes Addison Prairie (Stanford); Li-Yang Tan (Stanford) |
| 16:17 – 16:25 Worst-case Error Bounds for Online Learning of Smooth Functions Weian Xie (Massachusetts Institute of Technology) |
16:17 – 16:25 Tight list replicability bounds via a novel sphere covering theorem Ari Blondal (McGill University); Hamed Hatami (McGill University); Pooya Hatami (Ohio State University); Chavdar Lalov (Ohio State University); Sivan Tretiak (Ohio State University) |
| 16:28 – 16:36 A Characterization of List Language Identification in the Limit Moses Charikar (Stanford University); Chirag Pabbaraju (Stanford University); Ambuj Tewari (University of Michigan, Ann Arbor) |
16:28 – 16:36 Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction Lunjia Hu (Northeastern University); Kevin Tian (UT Austin); Chutong Yang (UT Austin) |
| 16:39 – 16:47 Near-optimal Swap Regret Minimization for Convex Losses Lunjia Hu (Harvard University); Jon Schneider (Google); Yifan Wu (Microsoft Research) |
16:39 – 16:47 Is Memorization Helpful or Harmful? Prior Information Sets the Threshold Chen Cheng (University of Chicago); Rina Barber (University of Chicago) |
| 16:50 – 16:58 Language Identification with Succinct Machine-Independent Traces Moses Charikar (Stanford University); Jon Kleinberg (Cornell University); Chirag Pabbaraju (Stanford University) |
16:50 – 16:58 Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget Michael Harding (University of Wisconsin-Madison); Kirthevasan Kandasamy (University of Wisconsin-Madison); Vikas Singh (University of Wisconsin-Madison) |
💡 Open Problems Session (17:05 – 17:57) — Mission ABC
| 17:05 – 17:13 Does Differential Privacy Make PAC Learning Much Harder? Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia |
| 17:16 – 17:24 Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation? Ivan Lau and Jonathan Scarlett |
| 17:27 – 17:35 Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design Maria-Florina Balcan, Wesley Pegden, and Dravyansh Sharma |
| 17:38 – 17:46 How much overparametrization is needed for ALS in tensor decomposition? Dionysis Arvanitakis, Vaidehi Srinivas, and Aravindan Vijayaraghavan |
| 17:49 – 17:57 Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent? Vitaly Feldman, Pritish Kamath, and Nathan Srebro |
Thursday, July 2
Session 13 (8:30 – 10:06)
| Track 1 — Mission ABC Statistical Learning Theory / Structured & Transfer Learning |
Track 2 — Mission DE Sampling |
|---|---|
| 8:30 – 8:38 Relatively Smart: A New Approach for Instance-Optimal Learning Alireza Pour (University of Waterloo); Shaddin Dughmi (University of Southern California) |
8:30 – 8:38 Polynomial-time sampling despite disorder chaos Eric Ma (Stanford); Tselil Schramm (Stanford) |
| 8:41 – 8:49 Minimax Limits of 𝑘 -Fold Cross-Validation via Majority Ido Nachum (University of Haifa); Rudiger Urbanke (EPFL); Thomas Weinberger (EPFL) |
8:41 – 8:49 The Geometry of Efficient Nonconvex Sampling Santosh Vempala (Georgia Institute of Technology); Andre Wibisono (Yale University) |
| 8:52 – 9:00 Margin in Abstract Spaces Yair Ashlagi (Tel Aviv University); Roi Livni (Tel Aviv University); Shay Moran (Technion, Google); Tom Waknine (Technion) |
8:52 – 9:00 Functional Stochastic Localization Anming Gu (UT Austin); Bobby Shi (UT Austin); Kevin Tian (UT Austin) |
| 9:03 – 9:11 On-Average Stability of Multipass SGD and Effective Dimension Simon Vary (Department of Statistics, University of Oxford); Tyler Farghly (Department of Statistics, University of Oxford); Ilja Kuzborskij (Google DeepMind); Patrick Rebeschini (Department of Statistics, University of Oxford) |
9:03 – 9:11 Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees Daniil Dmitriev (University of Pennsylvania); Zhihan Huang (University of Pennsylvania); Yuting Wei (University of Pennsylvania) |
| 9:14 – 9:22 Actively learning halfspaces without synthetic data Hadley Black (CUNY); Barna Saha (UCSD); Arya Mazumdar (UCSD); Kasper Larsen (Aarhus University); Geelon So (UCSD) |
9:14 – 9:22 Optimal Inference Schedules for Masked Diffusion Models Sitan Chen (Harvard University); Kevin Cong (Harvard University); Jerry Li (Washington University) |
| 9:25 – 9:33 Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities Alexandra Carpentier (Universität Potsdam); Christophe Giraud (Université Paris Saclay); Nicolas Verzelen (INRAE) |
9:25 – 9:33 High-accuracy log-concave sampling with stochastic gradients Fan Chen (MIT); Sinho Chewi (Yale University); Constantinos Daskalakis (MIT); Alexander Rakhlin (MIT) |
| 9:36 – 9:44 Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs David Gamarnik (MIT); Miklos Racz (Northwestern University); Gabe Schoenbach (University of Chicago) |
9:36 – 9:44 Steering diffusion models with quadratic rewards: a fine-grained analysis Ankur Moitra (Massachusetts Institute of Technology); Andrej Risteski (CMU); Dhruv Rohatgi (Massachusetts Institute of Technology) |
| 9:47 – 9:55 An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs Pan Peng (University of Science and Technology of China); Yuyang Wang (University of Science and Technology of China); Qiping Yang (The University of Sydney); Yichun Yang (Beijing Institute of Technology) |
9:47 – 9:55 Why is score-based sampling so effective? A general and adaptive reduction to SLC sub-problems Martin Wainwright (Massachusetts Institute of Technology) |
| 9:58 – 10:06 Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise Rafael Hanashiro (MIT); Abhishek Shetty (MIT); Patrick Jaillet (MIT) |
9:58 – 10:06 Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion Xunpeng Huang (The Hong Kong University of Science and Technology); Yingyu Lin (UCSD); Lijing Kuang (UCSD); Hanze Dong (Microsoft); Difan Zou (HKU); Yian Ma (UCSD); Tong Zhang (UIUC) |
☕ Coffee Break (10:09 – 10:35)
Invited Talk (10:35 – 11:35): Robert Schapire, Microsoft Research — Mission ABC
Convex Analysis at Infinity: An Introduction to Astral Space
Show Abstract
Not all convex functions have finite minimizers; some can only be minimized by a sequence as it heads to infinity, making it much harder, for instance, to prove convergence. This work develops an expansive new theory for understanding such minimizers at infinity, introducing astral space, a compact extension of Euclidean space to which such points at infinity have been added. Astral space is constructed to be as small as possible while still ensuring that all linear functions can be continuously extended to the new space. Astral space is especially compatible with standard convex analysis and is meant to provide the foundation for a more complete theory. Although not a vector space, nor even a metric space, astral space is nevertheless so well-structured as to allow useful and meaningful extensions of the most important concepts from convex analysis, including convexity of sets and functions, conjugacy, separation theorems, subdifferentials, as well as central topics from optimization and applications. Applied to widely used algorithms, these tools afford simplified proofs of convergence, even when the only minimizers are at infinity.
This is joint work with Miroslav Dudík and Matus Telgarsky. For further reading, see aka.ms/astral.
Session 14 (11:40 – 12:21)
| Track 1 — Mission ABC High-Dimensional Statistics (Graphs) |
Track 2 — Mission DE Robust Estimation |
|---|---|
| 11:40 – 11:48 Recovery of Planted Subgraphs Wasim Huleihel (Tel Aviv University) |
11:40 – 11:48 High-Dimensional Gaussian Mean Estimation under Realizable Contamination Ilias Diakonikolas (University of Wisconsin-Madison); Daniel Kane (University of California, San Diego); Thanasis Pittas (University of Wisconsin-Madison) |
| 11:51 – 11:59 Testing for a Hidden Geometry in Random Graphs Amit Silber (Tel Aviv University); Mor Oren ( Tel Aviv University); Wasim Huleihel (Tel Aviv University) |
11:51 – 11:59 Linear Regression under Missing or Corrupted Coordinates Ilias Diakonikolas (University of Wisconsin-Madison); Jelena Diakonikolas (University of Wisconsin-Madison); Daniel Kane (University of California, San Diego); Jasper Lee (University of California, Davis); Thanasis Pittas (University of Wisconsin-Madison) |
| 12:02 – 12:10 Rate-optimal community detection near the KS threshold via node-robust algorithms Jingqiu Ding (ETH Zurich); Yiding Hua (ETH Zurich); Kasper Lindberg (ETH Zurich); David Steurer (ETH Zurich); Aleksandr Storozhenko (Princeton University) |
12:02 – 12:10 A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance Ilias Diakonikolas (University of Wisconsin Madison); Jingyi Gao (University of Wisconsin Madison); Giannis Iakovidis (University of Wisconsin Madison); Daniel Kane (University of California, San Diego); Sihan Liu (University of California, San Diego); Thanasis Pittas (University of Wisconsin Madison) |
| 12:13 – 12:21 Phase Transition in Convex Relaxations for Graph Alignment Laurent Massoulie (INRIA Paris); Sushil Mahavir Varma (INRIA Paris); Louis Vassaux (INRIA Paris); Irene Waldspurger (Université Paris-Dauphine) |
🍽 Lunch & Poster Session (12:24 – 14:00)
Session 15 (14:00 – 15:25)
| Track 1 — Mission ABC Deep Learning Theory / Optimization |
Track 2 — Mission DE Distribution Learning and Statistical Learning Theory |
|---|---|
| 14:00 – 14:08 Graph neural networks extrapolate out-of-distribution for shortest paths Robert Nerem (University of California San Diego); Samantha Chen (University of California San Diego); Sanjoy Dasgupta (University of California San Diego); Yusu Wang (University of California San Diego) |
14:00 – 14:08 Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more Spencer Compton (Stanford University); Jerry Li (University of Washington) |
| 14:11 – 14:19 Convergence of Continual Learning in Homogeneous Deep Networks Matan Schliserman (Blavatnik School of Computer Science, Tel Aviv University); Gon Buzaglo (Princeton University); Itay Evron (Meta); Daniel Soudry (Department of Electrical and Computing Engineering, Technion) |
14:11 – 14:19 Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions Maryam Aliakbarpour (Rice University); Alireza Azizi (Rice University); Ria Stevens (Rice University) |
| 14:22 – 14:30 Eigen-Spike Emergence, Quadratic Deterministic Equivalents, and the Classification of Nonlinearly-Separable Data Collin Cranston (University of California San Diego); Zhichao Wang (University of California San Diego); Todd Kemp (University of California San Diego); Michael Mahoney (University of California Berkeley) |
14:22 – 14:30 Learning Ising Models from Evolutions Jason Gaitonde (Duke University); Ankur Moitra (MIT); Elchanan Mossel (MIT) |
| 14:33 – 14:41 How Many Features Can a Language Model Store Under the Linear Representation Hypothesis? Nikhil Garg (Cornell Tech); Jon Kleinberg (Cornell University); Kenneth Peng (Cornell University) |
14:33 – 14:41 Estimating Ising Models in Total Variation Distance Constantinos Daskalakis (MIT); Vardis Kandiros (Columbia University); Rui Yao (MIT) |
| 14:44 – 14:52 Tight Sample Complexity of Transformers Chenxiao Yang (Toyota Technological Institute at Chicago); Nathan Srebro (Toyota Technological Institute at Chicago); Zhiyuan Li (Toyota Technological Institute at Chicago) |
14:44 – 14:52 DDPM Score Matching and Distribution Learning Sinho Chewi (Yale University); Alkis Kalavasis (Yale University); Anay Mehrotra (Yale University); Omar Montasser (Yale University) |
| 14:55 – 15:03 Optimal Learning-Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay Binghui Li (Peking University); Zilin Wang (Peking University); Fengling Chen (Peking University); Shiyang Zhao (Peking University); Ruiheng Zheng (Peking University); Lei Wu (Peking University) |
14:55 – 15:03 Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds Ziao Wang (University of Michigan, Ann Arbor); Lei Ying (University of Michigan, Ann Arbor) |
| 15:06 – 15:14 When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networks Berk Tinaz (University of Southern California); Changzhi Xie (University of Southern California); Mahdi Soltanolkotabi (University of Southern California) |
15:06 – 15:14 On the Asymptotics of Self-Supervised Pre-training: Two-Stage M-Estimation and Representation Symmetry Mohammad Tinati (University of Southern California); Stephen Tu (University of Southern California) |
| 15:17 – 15:25 Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity Hengrui Luo (Rice University); Anna Ma (University of California Irvine); Ludovic Stephan (ENSAI-CREST); Yizhe Zhu (University of Southern California) |
☕ Coffee Break (15:28 – 15:55)
Session 16 (15:55 – 16:58)
| Track 1 — Mission ABC Deep Learning Theory |
Track 2 — Mission DE Information Theory / Algebra & Structured Computation |
|---|---|
| 15:55 – 16:03 A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory Itay Safran (Ben-Gurion University of the Negev) |
15:55 – 16:03 Optimal Sample Complexity Lower Bounds on Conditional Independence Testing Jan Seyfried (Centre for Quantum Technologies, National University of Singapore); Neelkanth Mishra (Department of Computer Science and Engineering, Indian Institute of Technology Delhi); Sayantan Sen (Centre for Quantum Technologies, National University of Singapore); Marco Tomamichel (Department of Electrical and Computer Engineering, Centre for Quantum Technologies, National University of Singapore) |
| 16:06 – 16:14 Optimal Neural Network Approximation of Smooth Compositional Functions on Sets with Low Intrinsic Dimension Thomas Nagler (LMU Munich); Sophie Langer (Ruhr-Universität Bochum) |
16:06 – 16:14 Partition Function Estimation under Bounded $f$-Divergence Adam Block (Columbia University); Abhishek Shetty (MIT) |
| 16:17 – 16:25 Theoretical Compression Bounds for Wide Multilayer Perceptrons houssam elcheairi (MIT); David Gamarnik (MIT); Rahul Mazumder (MIT) |
16:17 – 16:25 A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions Yuzhou Gu (NYU); Xin Li (Johns Hopkins University); Yinzhan Xu (UCSD) |
| 16:28 – 16:36 Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining Yunwei Ren (Princeton University); Yatin Dandi (EPFL); Florent Krzakala (EPFL); Jason Lee (UC Berkeley) |
16:28 – 16:36 Reconstructing Riemannian Metrics From Random Geometric Graphs Han Huang (University of Missouri); Elchanan Mossel (MIT); Pakawut Jiradilok (Mahidol University International College) |
| 16:39 – 16:47 Limitations of SGD for Multi-Index Models Beyond Statistical Queries Daniel Barzilai (Weizmann Institute of Science); Ohad Shamir (Weizmann Institute of Science) |
16:39 – 16:47 Price of universality in vector quantization is at most 0.11 bit Alina Harbuzova (Massachusetts Institute of Technology); Or Ordentlich (Hebrew University of Jerusalem); Yury Polyanskiy (Massachusetts Institute of Technology) |
| 16:50 – 16:58 The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network Abhigyan Dutta (Purdue University); Itay Safran (Ben Gurion University of the Negev); Paul Valiant (Purdue University) |
16:50 – 16:58 The matrix-vector complexity of Ax=b Raphael Meyer (New York University); Ethan Epperly (UC Berkeley); Michał Dereziński (University of Michigan) |
🎤 Impromptu Session / Open Discussions (17:05 – 18:00) — Mission ABC
Friday, July 3
Session 17 (8:30 – 9:55)
| Track 1 — Mission ABC Optimization |
Track 2 — Mission DE Algebra & Structured Computation / Computational Complexity & Combinatorial Optimization |
|---|---|
| 8:30 – 8:38 Universality of high-dimensional scaling limits of stochastic gradient descent Aukosh Jagannath (University of Waterloo); Reza Gheissari (Northwestern University) |
8:30 – 8:38 On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach George Giapitzakis (University of Waterloo); Kimon Fountoulakis (University of Waterloo); Eshaan Nichani (Princeton University); Jason Lee (University of California, Berkeley) |
| 8:41 – 8:49 Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity Lesi Chen (Tsinghua University); Chengchang Liu (The Chinese University of Hong Kong); Luo Luo (Fudan University); Jingzhao Zhang (Tsinghua University) |
8:41 – 8:49 Query Efficient Structured Matrix Learning Noah Amsel (NYU); Pratyush Avi (NYU); Tyler Chen (NYU); Feyza Duman Keles (NYU); Chinmay Hegde (NYU); Christopher Musco (NYU); Cameron Musco (University of Massachusetts, Amherst); David Persson (Flatiron Institute) |
| 8:52 – 9:00 Online Convex Optimization with Sublinear Noisy Probes Simone Di Gregorio (Sapienza University of Rome); Anupam Gupta (New York University); Stefano Leonardi (Sapienza University of Rome); Matteo Russo (EPFL) |
8:52 – 9:00 Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension Adam Klivans (UT Austin); Konstantinos Stavropoulos (UT Austin); Arsen Vasilyan (UT Austin) |
| 9:03 – 9:11 Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension Michael Crawshaw (George Mason University); Mingrui Liu (George Mason University) |
9:03 – 9:11 Compact Geometric Representations of Hierarchies Prashant Gokhale (University of Wisconsin-Madison); Piotr Indyk (MIT); Yuhao Liu (University of Wisconsin-Madison); Sandeep Silwal (University of Wisconsin-Madison); Tony Wang (University of Wisconsin-Madison); Haike Xu (MIT) |
| 9:14 – 9:22 Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization Aleksandar Armacki (École Polytechnique Fédérale de Lausanne); Dragana Bajović (Faculty of Technical Sciences, University of Novi Sad); Dušan Jakovetić (Faculty of Sciences, University of Novi Sad); Soummya Kar (Carnegie Mellon University); Ali H. Sayed (École Polytechnique Fédérale de Lausanne) |
9:14 – 9:22 Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift Adam Klivans (UT Austin); Shyamal Patel (Columbia University); Konstantinos Stavropoulos (UT Austin); Arsen Vasilyan (UT Austin) |
| 9:25 – 9:33 Clipping the Price of Adaptivity at the Tail Itai Kreisler (Tel Aviv University); Oliver Hinder (University of Pittsburgh); Yair Carmon (Tel Aviv University) |
9:25 – 9:33 Quiet Planting for k-SAT, Multiple Solutions of Arbitrary Geometry Ali Ahmadi (University of Maryland); Kiarash Banihashem (University of Maryland); Iman Gholami (University of Maryland); Mohammad Taghi Hajiaghayi (University of Maryland); Jan Olkowski (University of Maryland) |
| 9:36 – 9:44 Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time Qiang Fu (Yale University); Siddharth Mitra (Yale University); Vishwak Srinivasan (MIT); Xiuyuan Wang (Yale University); Andre Wibisono (Yale University); Ashia Wilson (MIT) |
9:36 – 9:44 Testing Noise Assumptions of Learning Algorithms Surbhi Goel (University of Pennsylvania); Adam Klivans (University of Texas at Austin); Konstantinos Stavropoulos (University of Texas at Austin); Arsen Vasilyan (University of Texas at Austin) |
| 9:47 – 9:55 On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentials Rotem Mulayoff (CISPA - Helmholtz Center for Information Security); Sebastian Stich (CISPA - Helmholtz Center for Information Security) |
9:47 – 9:55 Algorithmic Thinking Theory MohammadHossein Bateni (Google); Vincent Cohen-Addad (Google); Yuzhou Gu (NYU); Silvio Lattanzi (Google); Simon Meierhans (ETH Zurich); Christopher Mohri (Stanford) |
📋 Poster Session (10:09 – 11:40)
Session 18 (11:40 – 12:54)
| Track 1 — Mission ABC Bandits |
Track 2 — Mission DE High-Dimensional Statistics |
|---|---|
| 11:40 – 11:48 Optimism Stabilizes Thompson Sampling for Adaptive Inference Shunxing Yan (Peking University); Han Zhong (Peking University ) |
11:40 – 11:48 Separating Oblivious and Adaptive Models of Variable Selection Ziyun Chen (University of Washington); Jerry Li (University of Washington); Kevin Tian (University of Texas at Austin ); Yusong Zhu (University of Texas at Austin) |
| 11:51 – 11:59 The Sample Complexity of Multiclass and Sparse Contextual Bandits Liad Erez (Tel Aviv University); Fan Chen (MIT); Alexander Rakhlin (MIT); Tomer Koren (Tel Aviv University); Alon Cohen (Tel Aviv University); Yishay Mansour (Tel Aviv University); Shay Moran (Technion) |
11:51 – 11:59 On Efficient Robust Regression with Subquadratic Samples Deeksha Adil (ETH Zurich); Jaroslaw Blasiok (University of Bocconi); Hongjie Chen (ETH Zurich); Deepak Narayanan Sridharan (ETH Zurich) |
| 12:02 – 12:10 Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits Hao Qin (University of Arizona); Chicheng Zhang (University of Arizona) |
12:02 – 12:10 An Empirical Bayes Perspective on Heteroskedastic Mean Estimation Yanjun Han (New York University); Abhishek Shetty (MIT); Jacob Shkrob (New York University) |
| 12:13 – 12:21 Online Market Making and the Value of Observing the Order Book Davide Maran (Politecnico di Milano); Marcello Restelli (Politecnico di Milano) |
12:13 – 12:21 Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond alkis kalavasis (Yale University); Anay Mehrotra (Yale University); Felix Zhou (Yale University) |
| 12:24 – 12:32 Leveraging Similarities in Multi-Armed Bandits Khaled Eldowa (Inria); Thibaud Rahier (Criteo AI Lab); Cablant Augustin (Inria); Panayotis Mertikopoulos (CNRS); Pierre Gaillard (Inria) |
12:24 – 12:32 Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity Haitong Liu (ETH Zurich); Deepak Narayanan Sridharan (ETH Zurich); David Steurer (ETH Zurich); Manuel Wiedmer (ETH Zurich) |
| 12:35 – 12:43 A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice Zachary Chase (Kent State University); Shinji Ito (The University of Tokyo and RIKEN); Idan Mehalel (Technion) |
12:35 – 12:43 Universal priors: solving empirical Bayes via Bayesian inference and pretraining Nick Cannella (NYU); Anzo Teh (Massachusetts Institute of Technology); Yanjun Han (NYU); Yury Polyanskiy (MIT) |
| 12:46 – 12:54 On the implicit regularization of Langevin dynamics with projected noise Austin Stromme (Department of Statistics, CREST, ENSAE, IP Paris); Adrien Vacher (Department of Statistics, CREST, ENSAE, IP Paris); Govind Menon (Division of Applied Mathematics, Brown University and Institute for Advanced Study, Princeton) |