COLT 2021

141 papers

Weak learning convex sets under normal distributions

Anindya De, Rocco Servedio

A Statistical Taylor Theorem and Extrapolation of Truncated Densities

Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, Emmanouil Zampetakis

From Local Pseudorandom Generators to Hardness of Learning

Amit Daniely, Gal Vardi

Quantifying Variational Approximation for Log-Partition Function

Romain Cosson, Devavrat Shah

Online Markov Decision Processes with Aggregate Bandit Feedback

Alon Cohen, Haim Kaplan, Tomer Koren, Yishay Mansour

Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic

Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications

Liyu Chen, Haipeng Luo, Chen-Yu Wei

Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition

Liyu Chen, Haipeng Luo, Chen-Yu Wei

Query complexity of least absolute deviation regression via robust uniform convergence

Xue Chen, Michal Derezinski

Black-Box Control for Linear Dynamical Systems

Xinyi Chen, Elad Hazan

Learning and testing junta distributions with sub cube conditioning

Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints

Wei-Ning Chen, Peter Kairouz, Ayfer Ozgur

When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?

Niladri S. Chatterji, Philip M. Long, Peter Bartlett

Optimizing Optimizers: Regret-optimal gradient descent algorithms

Philippe Casgrain, Anastasis Kratsios

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford

Fast Rates for Structured Prediction

Vivien A Cabannes, Francis Bach, Alessandro Rudi

Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions

Sébastien Bubeck, Thomas Budzinski, Mark Sellke

A Law of Robustness for Two-Layers Neural Networks

Sébastien Bubeck, Yuanzhi Li, Dheeraj M Nagaraj

Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries

Marco Bressan, Nicolò Cesa-bianchi, Silvio Lattanzi, Andrea Paudice

Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent

Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, Tselil Schramm

Near-Optimal Entrywise Sampling of Numerically Sparse Matrices

Vladimir braverman, Robert Krauthgamer, Aditya R. Krishnan, Shay Sapir

Near Optimal Distributed Learning of Halfspaces with Two Parties

Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena

Multiplayer Bandit Learning, from Competition to Cooperation

Simina Branzei, Yuval Peres

Rank-one matrix estimation: analytic time evolution of gradient descent dynamics

Antoine Bodin, Nicolas Macris

Robust learning under clean-label attack

Avrim Blum, Steve Hanneke, Jian Qian, Han Shao

Majorizing Measures, Sequential Complexities, and Online Learning

Adam Block, Yuval Dagan, Alexander Rakhlin

Online Learning from Optimal Actions

Omar Besbes, Yuri Fonseca, Ilan Lobel

Deterministic Finite-Memory Bias Estimation

Tomer Berg, Or Ordentlich, Ofer Shayevitz

Reconstructing weighted voting schemes from partial information about their power indices

Huck Bennett, Anindya De, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis

Non-Euclidean Differentially Private Stochastic Convex Optimization

Raef Bassily, Cristóbal Guzmán, Anupama Nandi

Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, Alex Wein

Optimal Dynamic Regret in Exp-Concave Online Learning

Dheeraj Baby, Yu-Xiang Wang

The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities

Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

Adversarially Robust Low Dimensional Representations

Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan

Functions with average smoothness: structure, algorithms, and learning

Yair Ashlagi, Lee-Ad Gottlieb, Aryeh Kontorovich

Learning in Matrix Games can be Arbitrarily Complex

Gabriel P. Andrade, Rafael Frongillo, Georgios Piliouras

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford

SGD Generalizes Better Than GD (And Regularization Doesn’t Help)

Idan Amir, Tomer Koren, Roi Livni

Regret Minimization in Heavy-Tailed Bandits

Shubhada Agrawal, Sandeep K. Juneja, Wouter M. Koolen

Stochastic block model entropy and broadcasting on trees with survey

Emmanuel Abbe, Elisabetta Cornacchia, Yuzhou Gu, Yury Polyanskiy

Conference on Learning Theory 2021: Post-conference Preface

Mikhail Belkin, Kpotufe Samory