| 2022 | (Nearly) Optimal Private Linear Regression for Sub-Gaussian Data via Adaptive Clipping. Prateek Varshney, Abhradeep Thakurta, Prateek Jain |
| 2022 | A Private and Computationally-Efficient Estimator for Unbounded Gaussians. Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, Jonathan R. Ullman |
| 2022 | A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits. Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil |
| 2022 | A bounded-noise mechanism for differential privacy. Yuval Dagan, Gil Kur |
| 2022 | Accelerated SGD for Non-Strongly-Convex Least Squares. Aditya Varre, Nicolas Flammarion |
| 2022 | Adaptive Bandit Convex Optimization with Heterogeneous Curvature. Haipeng Luo, Mengxiao Zhang, Peng Zhao |
| 2022 | Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds. Shinji Ito, Taira Tsuchiya, Junya Honda |
| 2022 | An Efficient Minimax Optimal Estimator For Multivariate Convex Regression. Gil Kur, Eli Putterman |
| 2022 | Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev. Sinho Chewi, Murat A. Erdogdu, Mufan (Bill) Li, Ruoqi Shen, Shunshi Zhang |
| 2022 | Approximate Cluster Recovery from Noisy Labels. Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson |
| 2022 | Assemblies of neurons learn to classify well-separated distributions. Max Dabagia, Santosh S. Vempala, Christos H. Papadimitriou |
| 2022 | Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data. Spencer Frei, Niladri S. Chatterji, Peter L. Bartlett |
| 2022 | Better Private Algorithms for Correlation Clustering. Daogao Liu |
| 2022 | Beyond No Regret: Instance-Dependent PAC Reinforcement Learning. Andrew J. Wagenmaker, Max Simchowitz, Kevin Jamieson |
| 2022 | Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan |
| 2022 | Can Q-learning be Improved with Advice? Noah Golowich, Ankur Moitra |
| 2022 | Chained generalisation bounds. Eugenio Clerico, Amitis Shidani, George Deligiannidis, Arnaud Doucet |
| 2022 | Chasing Convex Bodies and Functions with Black-Box Advice. Nicolas Christianson, Tinashe Handina, Adam Wierman |
| 2022 | Clustering with Queries under Semi-Random Noise. Alberto Del Pia, Mingchen Ma, Christos Tzamos |
| 2022 | Community Recovery in the Degree-Heterogeneous Stochastic Block Model. Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic |
| 2022 | Complete Policy Regret Bounds for Tallying Bandits. Dhruv Malik, Yuanzhi Li, Aarti Singh |
| 2022 | Computational-Statistical Gap in Reinforcement Learning. Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan |
| 2022 | Conference on Learning Theory, 2-5 July 2022, London, UK. Po-Ling Loh, Maxim Raginsky |
| 2022 | Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits. Haipeng Luo, Mengxiao Zhang, Peng Zhao, Zhi-Hua Zhou |
| 2022 | Corruption-Robust Contextual Search through Density Updates. Renato Paes Leme, Chara Podimata, Jon Schneider |
| 2022 | Damped Online Newton Step for Portfolio Selection. Zakaria Mhammedi, Alexander Rakhlin |
| 2022 | Depth and Feature Learning are Provably Beneficial for Neural Network Discriminators. Carles Domingo-Enrich |
| 2022 | Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning. Pierre C. Bellec, Yiwei Shen |
| 2022 | Differential privacy and robust statistics in high dimensions. Xiyang Liu, Weihao Kong, Sewoong Oh |
| 2022 | Dimension-free convergence rates for gradient Langevin dynamics in RKHS. Boris Muzellec, Kanji Sato, Mathurin Massias, Taiji Suzuki |
| 2022 | EM's Convergence in Gaussian Latent Tree Models. Yuval Dagan, Anthimos Vardis Kandiros, Constantinos Daskalakis |
| 2022 | Efficient Convex Optimization Requires Superlinear Memory. Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant |
| 2022 | Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics. Asaf B. Cassel, Alon Cohen, Tomer Koren |
| 2022 | Efficient Projection-Free Online Convex Optimization with Membership Oracle. Zakaria Mhammedi |
| 2022 | Efficient decentralized multi-agent learning in asymmetric queuing systems. Daniel Freund, Thodoris Lykouris, Wentao Weng |
| 2022 | Eigenspace Restructuring: A Principle of Space and Frequency in Neural Networks. Lechao Xiao |
| 2022 | Exact Community Recovery in Correlated Stochastic Block Models. Julia Gaudio, Miklós Z. Rácz, Anirudh Sridhar |
| 2022 | Fast algorithm for overcomplete order-3 tensor decomposition. Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, David Steurer, Stefan Tiegel |
| 2022 | Faster online calibration without randomization: interval forecasts and the power of two choices. Chirag Gupta, Aaditya Ramdas |
| 2022 | From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization. Nima Anari, Thuy-Duong Vuong |
| 2022 | Gardner formula for Ising perceptron models at small densities. Erwin Bolthausen, Shuta Nakajima, Nike Sun, Changji Xu |
| 2022 | Generalization Bounds for Data-Driven Numerical Linear Algebra. Peter L. Bartlett, Piotr Indyk, Tal Wagner |
| 2022 | Generalization Bounds via Convex Analysis. Gábor Lugosi, Gergely Neu |
| 2022 | Hardness of Maximum Likelihood Learning of DPPs. Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie |
| 2022 | Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds. Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab Mirrokni, Chen Wang |
| 2022 | High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks. Kangjie Zhou, Andrea Montanari |
| 2022 | Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies. Zihan Zhang, Xiangyang Ji, Simon S. Du |
| 2022 | How catastrophic can catastrophic forgetting be in linear regression? Itay Evron, Edward Moroshko, Rachel A. Ward, Nathan Srebro, Daniel Soudry |
| 2022 | Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem. Yingli Ran, Zhao Zhang, Shaojie Tang |
| 2022 | Improved analysis for a proximal algorithm for sampling. Yongxin Chen, Sinho Chewi, Adil Salim, Andre Wibisono |
| 2022 | Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm. Meena Jagadeesan, Ilya P. Razenshteyn, Suriya Gunasekar |
| 2022 | Kernel interpolation in Sobolev spaces is not consistent in low dimensions. Simon Buchholz |
| 2022 | Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation. Loucas Pillaud-Vivien, Julien Reygner, Nicolas Flammarion |
| 2022 | Lattice-Based Methods Surpass Sum-of-Squares in Clustering. Ilias Zadik, Min Jae Song, Alexander S. Wein, Joan Bruna |
| 2022 | Learning GMMs with Nearly Optimal Robustness Guarantees. Allen Liu, Ankur Moitra |
| 2022 | Learning Low Degree Hypergraphs. Eric Balkanski, Oussama Hanguir, Shatian Wang |
| 2022 | Learning a Single Neuron with Adversarial Label Noise via Gradient Descent. Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis |
| 2022 | Learning to Control Linear Systems can be Hard. Anastasios Tsiamis, Ingvar M. Ziemann, Manfred Morari, Nikolai Matni, George J. Pappas |
| 2022 | Learning with metric losses. Dan Tsir Cohen, Aryeh Kontorovich |
| 2022 | Low-Degree Multicalibration. Parikshit Gopalan, Michael P. Kim, Mihir Singhal, Shengjia Zhao |
| 2022 | Making SGD Parameter-Free. Yair Carmon, Oliver Hinder |
| 2022 | Mean-field nonparametric estimation of interacting particle systems. Rentian Yao, Xiaohui Chen, Yun Yang |
| 2022 | Memorize to generalize: on the necessity of interpolation in high dimensional linear regression. Chen Cheng, John C. Duchi, Rohith Kuditipudi |
| 2022 | Minimax Regret Optimization for Robust Machine Learning under Distribution Shift. Alekh Agarwal, Tong Zhang |
| 2022 | Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret. Tor Lattimore |
| 2022 | Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering. Jennifer Tang |
| 2022 | Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance. Nuri Mert Vural, Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, Murat A. Erdogdu |
| 2022 | Monotone Learning. Olivier Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer |
| 2022 | Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms. Jibang Wu, Haifeng Xu, Fan Yao |
| 2022 | Multilevel Optimization for Inverse Problems. Simon Weissmann, Ashia Wilson, Jakob Zech |
| 2022 | Near optimal efficient decoding from pooled data. Max Hahn-Klimroth, Noëla Müller |
| 2022 | Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise. Ilias Diakonikolas, Daniel Kane |
| 2022 | Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis |
| 2022 | Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles. Christopher Criscitiello, Nicolas Boumal |
| 2022 | Neural Networks can Learn Representations with Gradient Descent. Alexandru Damian, Jason D. Lee, Mahdi Soltanolkotabi |
| 2022 | New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees. Dan Garber, Ben Kretzu |
| 2022 | Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares. Blake E. Woodworth, Francis R. Bach, Alessandro Rudi |
| 2022 | Non-Gaussian Component Analysis via Lattice Basis Reduction. Ilias Diakonikolas, Daniel Kane |
| 2022 | Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling. Alekh Agarwal, Tong Zhang |
| 2022 | Offline Reinforcement Learning with Realizability and Single-policy Concentrability. Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, Jason D. Lee |
| 2022 | Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation. Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Levi, Yunzong Xu |
| 2022 | On Almost Sure Convergence Rates of Stochastic Gradient Methods. Jun Liu, Ye Yuan |
| 2022 | On The Memory Complexity of Uniformity Testing. Tomer Berg, Or Ordentlich, Ofer Shayevitz |
| 2022 | On characterizations of learnability with computable learners. Tom F. Sterkenburg |
| 2022 | On the Benefits of Large Learning Rates for Kernel Methods. Gaspard Beugnot, Julien Mairal, Alessandro Rudi |
| 2022 | On the Role of Channel Capacity in Learning Gaussian Mixture Models. Elad Romanov, Tamir Bendory, Or Ordentlich |
| 2022 | On the power of adaptivity in statistical adversaries. Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan |
| 2022 | On the well-spread property and its relation to linear regression. Hongjie Chen, Tommaso d'Orsi |
| 2022 | Online Learning to Transport via the Minimal Selection Principle. Wenxuan Guo, Yoonhaeng Hur, Tengyuan Liang, Chris Ryan |
| 2022 | Optimal Mean Estimation without a Variance. Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter L. Bartlett, Michael I. Jordan |
| 2022 | Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise. Rajai Nasser, Stefan Tiegel |
| 2022 | Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun |
| 2022 | Optimal and instance-dependent guarantees for Markovian linear stochastic approximation. Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright, Peter L. Bartlett |
| 2022 | Optimization-Based Separations for Neural Networks. Itay Safran, Jason D. Lee |
| 2022 | Orthogonal Statistical Learning with Self-Concordant Loss. Lang Liu, Carlos Cinelli, Zaïd Harchaoui |
| 2022 | Parameter-free Mirror Descent. Andrew Jacobsen, Ashok Cutkosky |
| 2022 | Policy Optimization for Stochastic Shortest Path. Liyu Chen, Haipeng Luo, Aviv Rosenberg |
| 2022 | Private Convex Optimization via Exponential Mechanism. Sivakanth Gopi, Yin Tat Lee, Daogao Liu |
| 2022 | Private High-Dimensional Hypothesis Testing. Shyam Narayanan |
| 2022 | Private Matrix Approximation and Geometry of Unitary Orbits. Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, Nisheeth K. Vishnoi |
| 2022 | Private Robust Estimation by Stabilizing Convex Relaxations. Pravesh Kothari, Pasin Manurangsi, Ameya Velingker |
| 2022 | Private and polynomial time algorithms for learning Gaussians and beyond. Hassan Ashtiani, Christopher Liaw |
| 2022 | Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States. Julian Zimmert, Naman Agarwal, Satyen Kale |
| 2022 | ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm. Chris Junchi Li, Wenlong Mou, Martin J. Wainwright, Michael I. Jordan |
| 2022 | Random Graph Matching in Geometric Models: the Case of Complete Graphs. Haoyu Wang, Yihong Wu, Jiaming Xu, Israel Yolou |
| 2022 | Rate of Convergence of Polynomial Networks to Gaussian Processes. Adam Klukowski |
| 2022 | Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms. Milad Sefidgaran, Amin Gohari, Gaël Richard, Umut Simsekli |
| 2022 | Realizable Learning is All You Need. Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan |
| 2022 | Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. Julian Zimmert, Tor Lattimore |
| 2022 | Risk bounds for aggregated shallow neural networks using Gaussian priors. Laura Tinsi, Arnak S. Dalalyan |
| 2022 | Robust Estimation for Random Graphs. Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, Huanyu Zhang |
| 2022 | Robust Sparse Mean Estimation via Sum of Squares. Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas |
| 2022 | Robustly-reliable learners under poisoning attacks. Maria-Florina Balcan, Avrim Blum, Steve Hanneke, Dravyansh Sharma |
| 2022 | Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information. Yonathan Efroni, Dylan J. Foster, Dipendra Misra, Akshay Krishnamurthy, John Langford |
| 2022 | Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods. Frederic Koehler, Holden Lee, Andrej Risteski |
| 2022 | Scale-free Unconstrained Online Learning for Curved Losses. Jack J. Mayo, Hédi Hadiji, Tim van Erven |
| 2022 | Self-Consistency of the Fokker Planck Equation. Zebang Shen, Zhenfu Wang, Satyen Kale, Alejandro Ribeiro, Amin Karbasi, Hamed Hassani |
| 2022 | Sharp Constants in Uniformity Testing via the Huber Statistic. Shivam Gupta, Eric Price |
| 2022 | Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods. Yujia Jin, Aaron Sidford, Kevin Tian |
| 2022 | Single Trajectory Nonparametric Learning of Nonlinear Dynamics. Ingvar M. Ziemann, Henrik Sandberg, Nikolai Matni |
| 2022 | Smoothed Online Learning is as Easy as Statistical Learning. Adam Block, Yuval Dagan, Noah Golowich, Alexander Rakhlin |
| 2022 | Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond. Matan Schliserman, Tomer Koren |
| 2022 | Statistical Estimation and Online Inference via Local SGD. Xiang Li, Jiadong Liang, Xiangyu Chang, Zhihua Zhang |
| 2022 | Statistical and Computational Phase Transitions in Group Testing. Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S. Wein, Ilias Zadik |
| 2022 | Stochastic Variance Reduction for Variational Inequality Methods. Ahmet Alacaoglu, Yura Malitsky |
| 2022 | Stochastic linear optimization never overfits with quadratically-bounded losses on general data. Matus Telgarsky |
| 2022 | Strategizing against Learners in Bayesian Games. Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan |
| 2022 | Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin |
| 2022 | Strong Gaussian Approximation for the Sum of Random Vectors. Nazar Buzun, Nikolay Shvetsov, Dmitry V. Dylov |
| 2022 | Strong Memory Lower Bounds for Learning Natural Models. Gavin Brown, Mark Bun, Adam D. Smith |
| 2022 | The Dynamics of Riemannian Robbins-Monro Algorithms. Mohammad Reza Karimi, Ya-Ping Hsieh, Panayotis Mertikopoulos, Andreas Krause |
| 2022 | The Implicit Bias of Benign Overfitting. Ohad Shamir |
| 2022 | The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication. Allen Liu, Mark Sellke |
| 2022 | The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance. Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, Rachel A. Ward |
| 2022 | The Price of Tolerance in Distribution Testing. Clément L. Canonne, Ayush Jain, Gautam Kamath, Jerry Li |
| 2022 | The Query Complexity of Local Search and Brouwer in Rounds. Simina Brânzei, Jiawei Li |
| 2022 | The Role of Interactivity in Structured Estimation. Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi, Ziteng Sun |
| 2022 | The Structured Abstain Problem and the Lovász Hinge. Enrique B. Nueve, Rafael M. Frongillo, Jessica Finocchiaro |
| 2022 | The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks. Emmanuel Abbe, Enric Boix Adserà, Theodor Misiakiewicz |
| 2022 | The query complexity of sampling from strongly log-concave distributions in one dimension. Sinho Chewi, Patrik R. Gerber, Chen Lu, Thibaut Le Gouic, Philippe Rigollet |
| 2022 | Thompson Sampling Achieves $\tilde{O}(\sqrt{T})$ Regret in Linear Quadratic Control. Taylan Kargin, Sahin Lale, Kamyar Azizzadenesheli, Animashree Anandkumar, Babak Hassibi |
| 2022 | Tight query complexity bounds for learning graph partitions. Xizhi Liu, Sayan Mukherjee |
| 2022 | Toward Instance-Optimal State Certification With Incoherent Measurements. Sitan Chen, Jerry Li, Ryan O'Donnell |
| 2022 | Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information. Wei Huang, Richard Combes, Cindy Trinh |
| 2022 | Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo. Krishna Balasubramanian, Sinho Chewi, Murat A. Erdogdu, Adil Salim, Shunshi Zhang |
| 2022 | Trace norm regularization for multi-task learning with scarce data. Etienne Boursier, Mikhail Konobeev, Nicolas Flammarion |
| 2022 | Tracking Most Significant Arm Switches in Bandits. Joe Suk, Samory Kpotufe |
| 2022 | Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression. Theophile Thiery, Justin Ward |
| 2022 | Understanding Riemannian Acceleration via a Proximal Extragradient Framework. Jikai Jin, Suvrit Sra |
| 2022 | Uniform Stability for First-Order Empirical Risk Minimization. Amit Attia, Tomer Koren |
| 2022 | Universal Online Learning with Bounded Loss: Reduction to Binary Classification. Moïse Blanchard, Romain Cosson |
| 2022 | Universal Online Learning: an Optimistically Universal Learning Rule. Moïse Blanchard |
| 2022 | Universality of empirical risk minimization. Andrea Montanari, Basil Saeed |
| 2022 | Wasserstein GANs with Gradient Penalty Compute Congested Transport. Tristan Milne, Adrian I. Nachman |
| 2022 | When Is Partially Observable Reinforcement Learning Not Scary? Qinghua Liu, Alan Chung, Csaba Szepesvári, Chi Jin |
| 2022 | Width is Less Important than Depth in ReLU Neural Networks. Gal Vardi, Gilad Yehudai, Ohad Shamir |