Session 1 Schedule

• Nika Haghtalab (UC Berkeley)
• Shipra Agrawal (Columbia)
• Doina Precup (DeepMind and McGill University)
• Dana Angluin (Yale, Emeritus)

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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

• 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