COLT 2023
169 papers
Active Coverage for PAC Reinforcement Learning
Aymen Al-Marjani, Andrea Tirinzoni, Emilie Kaufmann Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD
Matthew Faw, Litu Rout, Constantine Caramanis, Sanjay Shakkottai Bregman Deviations of Generic Exponential Families
Sayak Ray Chowdhury, Patrick Saux, Odalric Maillard, Aditya Gopalan Causal Matrix Completion
Anish Agarwal, Munther Dahleh, Devavrat Shah, Dennis Shen Deterministic Nonsmooth Nonconvex Optimization
Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, Manolis Zampetakis Differentially Private and Lazy Online Convex Optimization
Naman Agarwal, Satyen Kale, Karan Singh, Abhradeep Thakurta Exponential Hardness of Reinforcement Learning with Linear Function Approximation
Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, Csaba Szepesvári Fast Algorithms for a New Relaxation of Optimal Transport
Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten Find a Witness or Shatter: The Landscape of Computable PAC Learning.
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer Fine-Grained Distribution-Dependent Learning Curves
Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, Ilya Tolstikhin From Pseudorandomness to Multi-Group Fairness and Back
Cynthia Dwork, Daniel Lee, Huijia Lin, Pranay Tankala Improper Multiclass Boosting
Nataly Brukhim, Steve Hanneke, Shay Moran Improved Discretization Analysis for Underdamped Langevin Monte Carlo
Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, Murat A. Erdogdu Inference on Strongly Identified Functionals of Weakly Identified Functions
Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, Masatoshi Uehara InfoNCE Loss Provably Learns Cluster-Preserving Representations
Advait Parulekar, Liam Collins, Karthikeyan Shanmugam, Aryan Mokhtari, Sanjay Shakkottai Is Planted Coloring Easier than Planted Clique?
Pravesh Kothari, Santosh S Vempala, Alexander S Wein, Jeff Xu Kernelized Diffusion Maps
Loucas Pillaud-Vivien, Francis Bach Learning and Testing Latent-Tree Ising Models Efficiently
Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, Davin Choo Learning Hidden Markov Models Using Conditional Samples
Gaurav Mahajan, Sham Kakade, Akshay Krishnamurthy, Cyril Zhang Learning Narrow One-Hidden-Layer ReLU Networks
Sitan Chen, Zehao Dou, Surbhi Goel, Adam Klivans, Raghu Meka Limits of Model Selection Under Transfer Learning
Steve Hanneke, Samory Kpotufe, Yasaman Mahdaviyeh Linearization Algorithms for Fully Composite Optimization
Maria-Luiza Vladarean, Nikita Doikov, Martin Jaggi, Nicolas Flammarion List Online Classification
Shay Moran, Ohad Sharon, Iska Tsubari, Sivan Yosebashvili Local Glivenko-Cantelli
Doron Cohen, Aryeh Kontorovich Local Risk Bounds for Statistical Aggregation
Jaouad Mourtada, Tomas Vaškevičius, Nikita Zhivotovskiy Minimax Optimal Testing by Classification
Patrik R. Gerber, Yanjun Han, Yury Polyanskiy Moments, Random Walks, and Limits for Spectrum Approximation
Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh Multiclass Online Learning and Uniform Convergence
Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, Ambuj Tewari Multitask Learning via Shared Features: Algorithms and Hardness
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, Lydia Zakynthinou Near Optimal Heteroscedastic Regression with Symbiotic Learning
Aniket Das, Dheeraj M. Nagaraj, Praneeth Netrapalli, Dheeraj Baby Near-Optimal Fitting of Ellipsoids to Random Points
Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein On a Class of Gibbs Sampling over Networks
Bo Yuan, Jiaojiao Fan, Jiaming Liang, Andre Wibisono, Yongxin Chen Online Learning and Solving Infinite Games with an ERM Oracle
Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell K. Fishelson Online Reinforcement Learning in Stochastic Continuous-Time Systems
Mohamad Kazem Shirani Faradonbeh, Mohamad Sadegh Shirani Faradonbeh Optimal Scoring Rules for Multi-Dimensional Effort
Jason D. Hartline, Liren Shan, Yingkai Li, Yifan Wu Provable Benefits of Representational Transfer in Reinforcement Learning
Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, Xuezhou Zhang Quantum Channel Certification with Incoherent Measurements
Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir Repeated Bilateral Trade Against a Smoothed Adversary
Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi Self-Directed Linear Classification
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis Semi-Random Sparse Recovery in Nearly-Linear Time
Jonathan Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, Kevin Tian Sharp Thresholds in Inference of Planted Subgraphs
Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik Testing of Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen The One-Inclusion Graph Algorithm Is Not Always Optimal
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy Ticketed Learning–Unlearning Schemes
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, Chiyuan Zhang Tighter PAC-Bayes Bounds Through Coin-Betting
Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij, Francesco Orabona Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality
Alireza Mousavi-Hosseini, Tyler K. Farghly, Ye He, Krishna Balasubramanian, Murat A. Erdogdu U-Calibration: Forecasting for an Unknown Agent
Bobby Kleinberg, Renato Paes Leme, Jon Schneider, Yifeng Teng