COLT 2021 Schedule
COLT 2021 features virtual, hybrid, and in-person components--where each component features its own set of events. The virtual part will be held on gather.town and will be accessible using the following link with the email ID used for registration: https://www.virtualchair.net/events/colt-2021. Use the buttons below to view the full program or a specific component's program. All times are in MT (UTC-6).
The program for the hybrid days can be found below. A compact overview of all 4-days is available here. Be sure to take note of whether an event you are interested in is virtual, hybrid, or in-person! Note that all hybrid events are located in rooms with the same name both physically and on Gathertown.
Sunday, August 15th, 2021
Monday, August 16, 2021
8:45 AM MT – 9:10 AM MT (No Specific Room [Virtual & In-person])
Break
Hybrid
9:10 AM MT - 9:15 AM MT (Muenzinger Auditorium)
Program Chairs’ Welcome Remark
Hybrid
9:15 AM MT – 9:30 AM MT (Muenzinger Auditorium)
Best Student Paper: Optimal Dynamic Regret in Exp-Concave Online Learning
Dheeraj Baby, Yu-Xiang Wang
Hybrid
9:30 AM MT - 9:40 AM MT (Muenzinger Auditorium)
Open Problem: Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?
Chulhee Yun, Suvrit Sra, Ali Jadbabaie
Hybrid
9:50 AM MT - 10:15 AM MT (Muenzinger Auditorium)
Minimally Supervised Learning (A)
Session Chair: Aryeh Kontorovich
Hybrid
- Title: Exponential savings in agnostic active learning through abstention
Author(s): Nikita Puchkin, Nikita Zhivotovskiy - Title: Bounded Memory Active Learning through Enriched Queries
Author(s): Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz - Title: Learning sparse mixtures of permutations from noisy information
Author(s): Anindya De, Ryan O'Donnell, Rocco Servedio - Title: The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood
Author(s): Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford - Title: Adaptivity in Adaptive Submodularity
Author(s): Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni
9:50 AM MT – 10:10 AM MT (Gold Auditorium)
Optimization(A)
Session Chair: Simon Du
Hybrid
- Title: Optimizing Optimizers: Regret-optimal gradient descent algorithms
Author(s): Philippe Casgrain, Anastasis Kratsios - Title: Frank-Wolfe with Nearest Extreme Point Oracle
Author(s): Dan Garber, Noam Wolf - Title: Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
Author(s): Peter Kairouz, Monica Ribero Diaz, Keith Rush, Abhradeep Thakurta - Title: Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
Author(s): Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
10:20 AM MT - 10:40 AM MT (Muenzinger Auditorium)
Minimally Supervised Learning (B)
Session Chair: Aryeh Kontorovich
Hybrid
- Title: Learning and testing junta distributions with sub cube conditioning
Author(s): Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten - Title: Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
Author(s): Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun - Title: Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints
Author(s): Wei-Ning Chen, Peter Kairouz, Ayfer Ozgur - Title: The Sample Complexity of Robust Covariance Testing
Author(s): Ilias Diakonikolas, Daniel M Kane
10:20 AM MT – 10:40 AM MT (Gold Auditorium)
Optimization(B)
Session Chair: Simon Du
Hybrid
- Title: Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning
Author(s): Andrew Lamperski - Title: The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities
Author(s): Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos - Title: A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
Author(s): Mo Zhou, Rong Ge, Chi Jin
10:40 AM MT – 11:10 AM MT (Garden Space [Virtual], Tent [In-person])
Break
Hybrid
11:10 AM MT – 11:30 AM MT (Muenzinger Auditorium)
Online Learning, Game Theory 1 (A)
Session Chair: Haipeng Luo
Hybrid
- Title: Lazy OCO: Online Convex Optimization on a Switching Budget
Author(s): Uri Sherman, Tomer Koren - Title: Deterministic Finite-Memory Bias Estimation
Author(s): Tomer Berg, Or Ordentlich, Ofer Shayevitz - Title: Online Learning from Optimal Actions
Author(s): Yuri Fonseca - Title: Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
Author(s): Steve Hanneke, Roi Livni, Shay Moran
11:10 AM MT – 11:35 AM MT (Gold Auditorium)
Approximation and Complexity
Session Chair: Murat Erdogdu
Hybrid
- Title: Reconstructing weighted voting schemes from partial information about their power indices
Author(s): Emmanouil Vasileios Vlatakis-Gkaragkounis, Huck Bennett, Anindya De, Rocco Servedio - Title: Weak learning convex sets under normal distributions
Author(s): Anindya De, Rocco Servedio - Title: Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent
Author(s): Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, Tselil Schramm - Title: A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation
Author(s): Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis Bach, Francois-Xavier Vialard - Title: Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
Author(s): Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, Alex Wein
11:35 AM MT – 11:55 AM MT (Muenzinger Auditorium)
Online Learning, Game Theory 1 (B)
Session Chair: Haipeng Luo
Hybrid
- Title: Online Markov Decision Processes with Aggregate Bandit Feedback
Author(s): Alon Cohen, Haim Kaplan, Tomer Koren, Yishay Mansour - Title: Exponential Weights Algorithms for Selective Learning
Author(s): Mingda Qiao, Gregory Valiant - Title: Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
Author(s): Liyu Chen, Haipeng Luo, Chen-Yu Wei
11:40 AM MT – 11:55 AM MT (Gold Auditorium)
Randomized Linear Algebra
Session Chair: Pan Peng
Hybrid
- Title: Sparse sketches with small inversion bias
Author(s): Michal Derezinski, Zhenyu Liao, Edgar Dobriban, Michael Mahoney - Title: Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing
Author(s): Taisuke Yasuda, David Woodruff, Yi Li - Title: Average-Case Communication Complexity of Statistical Problems
Author(s): Cyrus Rashtchian, David Woodruff, Peng Ye, Hanlin Zhu
1:00 PM MT – 2:00 PM MT (Muenzinger Auditorium [Virtual], Tent [In-person])
Lunch & Business Meeting
Hybrid
2:00 PM MT – 5:00 PM MT (Location details decided by each group)
Local Outdoor Activity (Hiking, Biking, or Walking Downtown)
In-Person
Tuesday, August 17, 2021
8:45 AM MT – 9:15 AM MT (No Specific Room [Virtual & In-person])
Break
Hybrid
9:50 AM MT – 10:15 AM MT (Muenzinger Auditorium)
Neural Networks/Deep Learning (A)
Session Chair: Quanquan Gu
Hybrid
- Title: Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks
Author(s): Cong Fang, Jason Lee, Pengkun Yang, Tong Zhang - Title: Provable Memorization via Deep Neural Networks using Sub-linear Parameters
Author(s): Sejun Park, Jaeho Lee, Chulhee Yun, Jinwoo Shin - Title: The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
Author(s): Itay M Safran, Gilad Yehudai, Ohad Shamir - Title: Non-asymptotic approximations of neural networks by Gaussian processes
Author(s): Ronen Eldan, Dan Mikulincer, Tselil Schramm - Title: Size and Depth Separation in Approximating Natural Functions with Neural Networks
Author(s): Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir
9:50 AM MT – 10:15 AM MT (Gold Auditorium)
Robustness, Privacy and Fairness (A)
Session Chair: Thomas Steinke
Hybrid
- Title: Differentially Private Nonparametric Regression Under a Growth Condition
Author(s): Noah Golowich - Title: On Avoiding the Union Bound When AnsweringMultiple Differentially Private Queries
Author(s): Badih Ghazi, Ravi Kumar, Pasin Manurangsi - Title: Non-Euclidean Differentially Private Stochastic Convex Optimization
Author(s): Raef Bassily, Cristobal Guzman, Anupama Nandi - Title: The Sparse Vector Technique, Revisited
Author(s): Haim Kaplan, Yishay Mansour, Uri Stemmer - Title: Machine unlearning via Algorithmic stability
Author(s): Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, Raman Arora
10:20 AM MT – 10:40 AM MT (Muenzinger Auditorium)
Neural Networks/Deep Learning (B)
Session Chair: Quanquan Gu
Hybrid
- Title: The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
Author(s): Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, Ohad Shamir - Title: Implicit Regularization in ReLU Networks with the Square Loss
Author(s): Gal Vardi, Ohad Shamir - Title: On the Approximation Power of Two-Layer Networks of Random ReLUs
Author(s): Daniel Hsu, Clayton H Sanford, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis - Title: When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
Author(s): Niladri S Chatterji, Philip M Long, Peter Bartlett
10:20 AM MT – 10:40 AM MT (Gold Auditorium)
Robustness, Privacy and Fairness (B)
Session Chair: Thomas Steinke
Hybrid
- Title: A Law of Robustness for Two-Layers Neural Networks
Author(s): Sebastien Bubeck, Yuanzhi Li, Dheeraj M Nagaraj - Title: Adversarially Robust Low Dimensional Representations
Author(s): Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan - Title: Moment Multicalibration for Uncertainty Estimation
Author(s): Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, Rakesh Vohra - Title: Adversarially Robust Learning with Unknown Perturbation Sets
Author(s): Omar Montasser, Steve Hanneke, Nathan Srebro
10:40 AM MT – 11:10 AM MT (Garden Space [Virtual], Tent [In-person])
Break
Hybrid
11:10 AM MT – 11:30 AM MT (Muenzinger Auditorium)
Online Learning, Game Theory 2 (A)
Session Chair: Vidya K Muthukumar
Hybrid
- Title: Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information
Author(s): Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos - Title: Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
Author(s): Yu-Guan Hsieh, Kimon Antonakopoulos, Panayotis Mertikopoulos - Title: Learning in Matrix Games can be Arbitrarily Complex
Author(s): Gabriel P Andrade, Rafael Frongillo, Georgios Piliouras - Title: Robust Online Convex Optimization in the Presence of Outliers
Author(s): Tim van Erven, Sarah Sachs, Wouter M Koolen, Wojciech Kotlowski
11:10 AM MT – 11:35 AM MT (Gold Auditorium)
Bandits, RL and Control 1 (A)
Session Chair: Yuxin Chen
Hybrid
- Title: Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
Author(s): Liyu Chen, Haipeng Luo, Chen-Yu Wei - Title: Towards a Dimension-Free Understanding of Adaptive Linear Control
Author(s): Juan C Perdomo, Max Simchowitz, Alekh Agarwal, Peter Bartlett - Title: Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
Author(s): Haike Xu, Tengyu Ma, Simon Du - Title: Improved Regret for Zeroth-Order Stochastic Convex Bandits
Author(s): Tor Lattimore, Andras Gyorgy
11:35 AM MT – 11:55 AM MT (Muenzinger Auditorium)
Online Learning, Game Theory 2 (B)
Session Chair: Vidya K Muthukumar
Hybrid
- Title: Sequential prediction under log-loss and misspecification
Author(s): Meir Feder, Yury Polyanskiy - Title: Black-Box Control for Linear Dynamical Systems
Author(s): Xinyi Chen, Elad Hazan - Title: Majorizing Measures, Sequential Complexities, and Online Learning
Author(s): Adam Block, Yuval Dagan, Alexander Rakhlin - Title: Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
Author(s): Dylan Foster, Alexander Rakhlin, David Simchi-Levi, Yunzong Xu
11:35 AM MT – 11:55 AM MT (Gold Auditorium)
Bandits, RL and Control 1 (B)
Session Chair: Yuxin Chen
Hybrid
- Title: Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
Author(s): Zihan Zhang, Xiangyang Ji, Simon Du - Title: Corruption-robust exploration in episodic reinforcement learning
Author(s): Thodoris Lykouris, Max Simchowitz, Alex Slivkins, Wen Sun - Title: On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
Author(s): Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, Csaba Szepesvari - Title: Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
Author(s): Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo
1:00 PM MT – 2:00 PM MT (On-your-own [Virtual & In-person])
Lunch
Hybrid
2:00 PM MT – 3:00 PM MT (Tent)
Break
In-Person
3:00 PM MT – 3:50 PM MT (Tent)
Impromptu Talks (Whiteboard or Slides)
In-Person
4:00 PM MT – 5:00 PM MT (Tent)
Panel Discussion: Theory in Machine Learning: Yesterday, Today, Tomorrow
Moderator: Nati Srebro (TTIC)
Panelists: Satyen Kale (Google), Jason Lee (Princeton), Claire Monteleoni (CU Boulder), Nati Srebro (TTIC)
In-Person
Wednesday, August 18, 2021
8:45 AM MT – 9:15 AM MT (No Specific Room [Virtual & In-person])
Break
Hybrid
9:15 AM MT – 9:30 AM MT (Muenzinger Auditorium)
Best Student Paper: Stochastic block model entropy and broadcasting on trees with survey
Emmanuel Abbe, Elisabetta Cornacchia, Yuzhou Gu, Yury Polyanskiy
Hybrid
9:30 AM MT - 9:40 AM MT (Muenzinger Auditorium)
Open Problem: Are all VC classes learnable with computable learners?
Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner
Hybrid
9:50 AM MT – 10:15 AM MT (Muenzinger Auditorium)
Generalization and PAC-Learning 1 (A)
Session Chair: Dylan Foster
Hybrid
- Title: Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
Author(s): Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, Xinzhi Zhang - Title: PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
Author(s): Peter Grunwald, Thomas Steinke, Lydia Zakynthinou - Title: Agnostic Proper Learning of Halfspaces under Gaussian Marginals
Author(s): Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis - Title: Benign Overfitting of Constant-Stepsize SGD for Linear Regression
Author(s): Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Sham Kakade - Title: Boosting in the Presence of Massart Noise
Author(s): Ilias Diakonikolas, Russell Impagliazzo, Daniel M Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
9:50 AM MT – 10:15 AM MT (Gold Auditorium)
Regression and High-Dimensional Statistics (A)
Session Chair: Yuting Wei
Hybrid
- Title: Efficient Algorithms for Learning from Coarse Labels
Author(s): Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos Tzamos - Title: Impossibility of Partial Recovery in the Graph Alignment Problem
Author(s): Luca Ganassali, Laurent Massoulie, Marc Lelarge - Title: Hypothesis testing with low-degree polynomials in the Morris class of exponential families
Author(s): Dmitriy Kunisky - Title: Group testing and local search: is there a computational-statistical gap?
Author(s): Fotis Iliopoulos, Ilias Zadik - Title: Johnson-Lindenstrauss Transforms with Best Confidence
Author(s): Maciej Skorski
10:20 AM MT – 10:40 AM MT (Muenzinger Auditorium)
Generalization and PAC-Learning 1 (B)
Session Chair: Dylan Foster
Hybrid
- Title: Fast Rates for Structured Prediction
Author(s): Vivien A Cabannnes, Francis Bach, Alessandro Rudi - Title: A Priori Generalization Analysis of the Deep Ritz Method for Solving High Dimensional Elliptic Partial Differential Equations
Author(s): Yulong Lu, Jianfeng Lu, Min Wang - Title: On Empirical Bayes Variational Autoencoder: An Excess Risk Bound
Author(s): Rong Tang, Yun Yang - Title: Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
Author(s): Gergely Neu, Gintare Karolina Dziugiate, Mahdi Haghifam, Daniel M. Roy
10:20 AM MT – 10:40 AM MT (Gold Auditorium)
Regression and High-Dimensional Statistics (B)
Session Chair: Yuting Wei
Hybrid
- Title: Reduced-Rank Regression with Operator Norm Error
Author(s): Praneeth Kacham, David Woodruff - Title: Rank-one matrix estimation: analytic time evolution of gradient descent dynamics
Author(s): Antoine Bodin, Nicolas Macris - Title: It was ``all'' for ``nothing'': sharp phase transitions for noiseless discrete channels
Author(s): Ilias Zadik, Jonathan Niles-Weed
10:40 AM MT – 11:10 AM MT (Garden Space [Virtual], Tent [In-person])
Break
Hybrid
11:10 AM MT – 11:35 AM MT (Muenzinger Auditorium)
Networks and Graphs
Session Chair: Simina Branzei
Hybrid
- Title: Random Graph Matching with Improved Noise Robustness
Author(s): Cheng Mao, Mark Rudelson, Konstantin Tikhomirov - Title: Quantifying Variational Approximation for Log-Partition Function
Author(s): Romain Cosson, Devavrat Shah - Title: Source Identification for Mixtures of Product Distributions
Author(s): Spencer Gordon, Bijan H Mazaheri, Yuval Rabani, Leonard Schulman - Title: Learning to Sample from Censored Markov Random Fields
Author(s): Ankur Moitra, Elchanan Mossel, Colin P Sandon - Title: Learning from Censored and Dependent Data: The case of Linear Dynamics
Author(s): Orestis Plevrakis
11:10 AM MT – 11:30 AM MT (Gold Auditorium)
Bandits, RL and Control 2 (A)
Session Chair: Sattar Vakili
Hybrid
- Title: Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
Author(s): Mark Sellke, Sebastien Bubeck, Thomas Budzinski - Title: Softmax Policy Gradient Methods Can Take Exponential Time to Converge
Author(s): Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen - Title: Asymptotically Optimal Information-Directed Sampling
Author(s): Johannes Kirschner, Tor Lattimore, Claire Vernade, Csaba Szepesvari - Title: Fast Rates for the Regret of Offline Reinforcement Learning
Author(s): Yichun Hu, Nathan Kallus, Masatoshi Uehara
11:40 AM MT – 11:55 AM MT (Muenzinger Auditorium)
Clustering
Session Chair: Michal Moshkovitz
Hybrid
- Title: Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle
Author(s): Pan Peng, Jiapeng Zhang - Title: Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
Author(s): Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi, Andrea Paudice - Title: Approximation Algorithms for Socially Fair Clustering
Author(s): Yury Makarychev, Ali Vakilian
11:35 AM MT – 11:55 AM MT (Gold Auditorium)
Bandits, RL and Control 2 (B)
Session Chair: Sattar Vakili
Hybrid
- Title: Nearly Minimax Optimal Reinforcement Learning for Linear Mixture MDPs
Author(s): Dongruo Zhou, Quanquan Gu, Csaba Szepesvari - Title: Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds
Author(s): Shinji Ito - Title: Learning to Stop with Surprisingly Few Samples
Author(s): Tianyi Zhang, Daniel Russo, Assaf Zeevi - Title: Tsallis-INF: Improved Robustness to Adversarial Corruptions inStochastic Multi-armed Bandits and Beyond
Author(s): Saeed Masoudian, Yevgeny Seldin
1:00 PM MT – 2:00 PM MT (On-your-own [Virtual & In-person])
Lunch
Hybrid
2:00 PM MT – 3:00 PM MT (Tent)
Break
In-Person
3:00 PM MT – 3:50 PM MT (Tent)
Impromptu Talks (Whiteboard or Slides)
In-Person
4:00 PM MT – 5:00 PM MT (Tent)
Panel Discussion: Statistics in Learning Theory: Yesterday, Today, Tomorrow
Moderator: Aaditya Ramdas (CMU)
Panelists: Vitaly Feldman (Apple), Steve Hanneke (TTIC), Vidya Muthukumar (GaTech), Aaditya Ramdas (CMU), Csaba Szepesvári (University of Alberta and DeepMind)
In-Person
Thursday, August 19, 2021
8:45 AM MT – 9:15 AM MT (No Specific Room [Virtual & In-person])
Break
Hybrid
9:15 AM MT – 9:30 AM MT (Muenzinger Auditorium)
Best Paper: The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
Blake E Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro
Hybrid
9:30 AM MT - 9:40 AM MT (Muenzinger Auditorium)
Open Problem: Tight Online Confidence Intervals for RKHS Elements
Sattar Vakili, Jonathan Scarlett, Tara Javidi
Hybrid
9:50 AM MT – 10:15 AM MT (Muenzinger Auditorium)
Generalization and PAC-Learning 2 (A)
Session Chair: Steve Hanneke
Hybrid
- Title: Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization
Author(s): Mathieu Even, Laurent Massoulie - Title: A Theory of Heuristic Learnability
Author(s): Mikito Nanashima - Title: From Local Pseudorandom Generators to Hardness of Learning
Author(s): Amit Daniely, Gal Vardi - Title: Functions with average smoothness: structure, algorithms, and learning
Author(s): Yair Ashlagi, Lee-Ad Gottlieb, Aryeh Kontorovich - Title: Robust learning under clean-label attack
Author(s): Avrim Blum, Steve Hanneke, Jian Qian, Han Shao
9:50 AM MT – 10:15 AM MT (Gold Auditorium)
Nonparametrics
Session Chair: Cheng Mao
Hybrid
- Title: Learning with invariances in random features and kernel models
Author(s): Song Mei, Theodor Misiakiewicz, Andrea Montanari - Title: Kernel Thinning
Author(s): Raaz Dwivedi, Lester Mackey - Title: On the Minimal Error of Empirical Risk Minimization
Author(s): Gil Kur, Alexander Rakhlin - Title: Nonparametric Regression with Shallow Overparametrized Neural Networks Trained by GD with Early Stopping
Author(s): Ilja Kuzborskij , Csaba Szepesvari - Title: A Statistical Taylor Theorem and Extrapolation of Truncated Densities
Author(s): Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, Emmanouil Zampetakis
10:20 AM MT – 10:40 AM MT (Muenzinger Auditorium)
Generalization and PAC-Learning 2 (B)
Session Chair: Steve Hanneke
Hybrid
- Title: Query complexity of least absolute deviation regression via robust uniform convergence
Author(s): Xue Chen, Michal Derezinski - Title: Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise
Author(s): Chicheng Zhang, Yinan Li - Title: The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
Author(s): Ilias Diakonikolas, Daniel M Kane, Thanasis Pittas, Nikos Zarifis - Title: Near Optimal Distributed Learning of Halfspaces with Two Parties
Author(s): Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
10:20 AM MT – 10:45 AM MT (Gold Auditorium)
Sampling Algorithms
Session Chair: Jonathan Niles-Weed
Hybrid
- Title: Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
Author(s): Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, Philippe Rigollet - Title: Random Coordinate Langevin Monte Carlo
Author(s): Zhiyan Ding, Qin Li, Jianfeng Lu, Stephen J Wright - Title: Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Author(s): Vladimir Braverman, Robert Krauthgamer, Aditya R Krishnan, Shay Sapir - Title: Structured Logconcave Sampling with a Restricted Gaussian Oracle
Author(s): Yin Tat Lee, Ruoqi Shen, Kevin Tian - Title: On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
Author(s): Murat A Erdogdu, Rasa Hosseinzadeh
10:45 AM MT – 11:10 AM MT (Garden Space [Virtual], Tent [In-person])
Break
Hybrid
11:10 AM MT – 11:30 AM MT (Muenzinger Auditorium)
Stochastic Optimization (A)
Session Chair: Brian Bullins
Hybrid
- Title: Shape Matters: Understanding the Implicit Bias of the Noise Covariance
Author(s): Jeff Z. HaoChen, Colin Wei, Jason Lee, Tengyu Ma - Title: SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
Author(s): Courtney Paquette, Kiwon Lee, Fabian Pedregosa, Elliot Paquette - Title: Stochastic Approximation for Online Tensorial Independent Component Analysis
Author(s): Chris Junchi Li, Michael Jordan - Title: On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning
Author(s): Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Hoi-To Wai
11:10 AM MT – 11:35 AM MT (Gold Auditorium)
Bandits, RL and Control 3 (A)
Session Chair: Ilja Kuzborskij
Hybrid
- Title: Double Explore-then-Commit: Asymptotic Optimality and Beyond
Author(s): Tianyuan Jin, Pan Xu, Xiaokui Xiao, Quanquan Gu - Title: Adaptive Discretization for Adversarial Lipschitz Bandits
Author(s): Chara Podimata, Alex Slivkins - Title: Efficient Bandit Convex Optimization: Beyond Linear Losses
Author(s): Arun Sai Suggala, Pradeep Ravikumar, Praneeth Netrapalli - Title: Mirror Descent and the Information Ratio
Author(s): Tor Lattimore, Andras Gyorgy
11:35 AM MT – 11:55 AM MT (Muenzinger Auditorium)
Stochastic Optimization (B)
Session Chair: Brian Bullins
Hybrid
- Title: On the (asymptotic) convergence of Stochastic Gradient Descent and Stochastic Heavy Ball
Author(s): Othmane Sebbouh, Robert M Gower, Aaron Defazio - Title: SGD Generalizes Better Than GD (And Regularization Doesn't Help)
Author(s): Idan Amir, Tomer Koren, Roi Livni - Title: Convergence rates and approximation results for SGD and its continuous-time counterpart
Author(s): Xavier Fontaine, Valentin De Bortoli, Alain Durmus - Title: Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
Author(s): De Huang, Jonathan Niles-Weed, Rachel Ward
11:40 AM MT – 11:55 AM MT (Gold Auditorium)
Bandits, RL and Control 3 (B)
Session Chair: Ilja Kuzborskij
Hybrid
- Title: Multiplayer Bandit Learning, from Competition to Cooperation
Author(s): Simina Branzei, Yuval Peres - Title: Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
Author(s): Andrea Zanette, Ching-An Cheng, Alekh Agarwal - Title: Regret Minimization in Heavy-Tailed Bandits
Author(s): Shubhada Agrawal, Sandeep K Juneja, Wouter M Koolen
1:00 PM MT – 2:00 PM MT (Garden Space [Virtual], Tent [In-person])
Lunch & Game Show
Hybrid
2:00 PM MT – 5:00 PM MT (Location details decided by each group)
Local Outdoor Activity (Hiking, Biking, or Walking Downtown)
In-Person