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