COLT 2022
162 papers
A Private and Computationally-Efficient Estimator for Unbounded Gaussians
Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, Jonathan Ullman Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev
Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, Shunshi Zhang Approximate Cluster Recovery from Noisy Labels
Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
Jonathan Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan Chained Generalisation Bounds
Eugenio Clerico, Amitis Shidani, George Deligiannidis, Arnaud Doucet Computational-Statistical Gap in Reinforcement Learning
Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan Efficient Convex Optimization Requires Superlinear Memory
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant EM’s Convergence in Gaussian Latent Tree Models
Yuval Dagan, Vardis Kandiros, Constantinos Daskalakis Fast Algorithm for Overcomplete Order-3 Tensor Decomposition
Jingqiu Ding, Tommaso d’Orsi, Chih-Hung Liu, David Steurer, Stefan Tiegel Hardness of Maximum Likelihood Learning of DPPs
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie How Catastrophic Can Catastrophic Forgetting Be in Linear Regression?
Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, Daniel Soudry Learning Low Degree Hypergraphs
Eric Balkanski, Oussama Hanguir, Shatian Wang Learning to Control Linear Systems Can Be Hard
Anastasios Tsiamis, Ingvar M Ziemann, Manfred Morari, Nikolai Matni, George J. Pappas Learning with Metric Losses
Dan Tsir Cohen, Aryeh Kontorovich Low-Degree Multicalibration
Parikshit Gopalan, Michael P Kim, Mihir A Singhal, Shengjia Zhao Making SGD Parameter-Free
Yair Carmon, Oliver Hinder Monotone Learning
Olivier J Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer Optimal Mean Estimation Without a Variance
Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter Bartlett, Michael Jordan Parameter-Free Mirror Descent
Andrew Jacobsen, Ashok Cutkosky Private Matrix Approximation and Geometry of Unitary Orbits
Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, Nisheeth K. Vishnoi Realizable Learning Is All You Need
Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan Robust Estimation for Random Graphs
Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, Huanyu Zhang Robust Sparse Mean Estimation via Sum of Squares
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas Robustly-Reliable Learners Under Poisoning Attacks
Maria-Florina Balcan, Avrim Blum, Steve Hanneke, Dravyansh Sharma Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information
Yonathan Efroni, Dylan J Foster, Dipendra Misra, Akshay Krishnamurthy, John Langford Self-Consistency of the Fokker Planck Equation
Zebang Shen, Zhenfu Wang, Satyen Kale, Alejandro Ribeiro, Amin Karbasi, Hamed Hassani Statistical and Computational Phase Transitions in Group Testing
Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, Ilias Zadik Strategizing Against Learners in Bayesian Games
Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan The Dynamics of Riemannian Robbins-Monro Algorithms
Mohammad Reza Karimi, Ya-Ping Hsieh, Panayotis Mertikopoulos, Andreas Krause 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 Ward The Price of Tolerance in Distribution Testing
Clement L Canonne, Ayush Jain, Gautam Kamath, Jerry Li The Role of Interactivity in Structured Estimation
Jayadev Acharya, Clement L. Canonne, Ziteng Sun, Himanshu Tyagi The Structured Abstain Problem and the Lovász Hinge
Jessica J Finocchiaro, Rafael Frongillo, Enrique B Nueve Thompson Sampling Achieves $\tilde{O}(\sqrt{T})$ Regret in Linear Quadratic Control
Taylan Kargin, Sahin Lale, Kamyar Azizzadenesheli, Animashree Anandkumar, Babak Hassibi