Accepted Papers

  • Not All Learnable Distributions are Privately Learnable
    Bun, Mark and Kamath, Gautam and Mouzakis, Anargyros-Georgios and Singhal, Vikrant
  • On the Computational Benefit of Multimodal Learning
    Lu, Zhou
  • Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies
    Weitzman, Shlomi and Sabato, Sivan
  • Multiclass Learnability Does Not Imply Sample Compression
    Pabbaraju, Chirag
  • Adversarial Online Collaborative Filtering
    Pasteris, Stephen U and Gentile, Claudio and Herbster, Mark and Panisson, Andre and Vitale, Fabio
  • Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization
    LOU, MENGQI and Chandrasekher, Kabir A and Pananjady, Ashwin
  • Near-continuous time Reinforcement Learning for continuous state-action spaces
    Croissant, Lorenzo and Abeille, Marc and Bouchard, Bruno
  • A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
    Singhal, Vikrant
  • Dueling Optimization with a Monotone Adversary
    Blum, Avrim and Gupta, Meghal and Li, Gene and Manoj, Naren Sarayu and Saha, Aadirupa and Yang, Yuanyuan
  • Universal Representation of Permutation-Invariant Functions on Vectors and Tensors
    Tabaghi, Puoya and Wang, Yusu
  • Online Infinite-Dimensional Regression: Learning Linear Operators
    Subedi, Unique and Raman, Vinod and Tewari, Ambuj
  • Agnostic Membership Query Learning with Nontrivial Savings: New Results and Techniques
    Karchmer, Ari
  • Partially Interpretable Models with Guarantees on Coverage and Accuracy
    Frost, Nave and Lipton, Zachary and Mansour, Yishay and Moshkovitz, Michal
  • Corruption-Robust Lipschitz Contextual Search
    Zuo, Shiliang
  • Multiclass Online Learnability under Bandit Feedback
    Raman, Vinod and Subedi, Unique and Tewari, Ambuj and Raman, Ananth S and Mehalel, Idan
  • The complexity of non-stationary reinforcement learning
    Peng, Binghui and Papadimitriou, Christos
  • Optimal Regret Bounds for Collaborative Learning in Bandits
    Shidani, Amitis and Vakili, Sattar
  • Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples
    Afzali, Mohammad and Ashtiani, Hassan and Liaw, Christopher
  • Improving Adaptive Online Learning Using Refined Discretization
    Zhang, Zhiyu and Yang, Heng and Cutkosky, Ashok and Paschalidis, Ioannis C
  • CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption
    Agrawal, Shubhada and Mathieu, Timothée and Basu, Debabrota and Maillard, Odalric
  • Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries
    Liao, Hang and Chakrabarty, Deeparnab
  • Learning bounded-degree polytrees with known skeleton
    Choo, Davin and Yang, Qiping and Bhattacharyya, Arnab and Canonne, Clement L
  • Efficient Agnostic Learning with Average Smoothness
    Kornowski, Guy and Hanneke, Steve and Kontorovich, Aryeh
  • The Attractor of the Replicator Dynamic in Zero-Sum Games
    Biggar, Oliver and Shames, Iman
  • On the Sample Complexity of Two-Layer Networks: Lipschitz Vs. Element-Wise Lipschitz Activation
    Daniely, Amit and Granot, Elad
  • Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
    Kash, Ian and Reyzin, Lev and Yu, Zishun
  • RedEx: Beyond Fixed Representation Methods via Convex Optimization
    Yehudai, Gilad and Daniely, Amit and Schain, Mariano
  • Semi-supervised Group DRO: Combating Sparsity with Unlabeled Data
    Awasthi, Pranjal and Kale, Satyen and Pensia, Ankit
  • Online Recommendations for Agents with Discounted Adaptive Preferences
    Brown, William and Agarwal, Arpit
  • Learning Hypertrees From Shortest Path Queries
    Fallat, Shaun M and Maliuk, valerii and Mojallal, Seyed Ahmad and Zilles, Sandra
  • Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates
    Menart, Michael and Ullah, Enayat and Arora, Raman and Bassily, Raef and Guzman, Cristobal
  • Concentration of empirical barycenters in metric spaces
    Brunel, Victor-Emmanuel and Serres, Jordan
  • Importance-Weighted Offline Learning Done Right
    Gabbianelli, Germano and Neu, Gergely and Papini, Matteo
  • Distances for Markov Chains, and Their Differentiation
    Brugere, Tristan A and Wan, Zhengchao and Wang, Yusu
  • Adversarial Contextual Bandits Go Kernelized
    Neu, Gergely and Olkhovskaya, Julia and Vakili, Sattar
  • Computation with Sequences of Assemblies in a Model of the Brain
    Dabagia, Max and Papadimitriou, Christos and Vempala, Santosh
  • Tight Bounds for Local Glivenko-Cantelli
    Blanchard, Moise and Voráček, Václav
  • A Mechanism for Sample-Efficient In-Context Learning for Sparse Retrieval Tasks
    Abernethy, Jacob and Agarwal, Alekh and Marinov, Teodor Vanislavov and Warmuth, Manfred K.
  • Provable Accelerated Convergence of Nesterov’s Momentum for Deep ReLU Neural Networks
    Liao, Fangshuo and Kyrillidis, Anastasios
  • The Dimension of Self-Directed Learning
    Devulapalli, Pramith and Hanneke, Steve
  • The Impossibility of Parallelizing Boosting
    Karbasi, Amin and Green Larsen, Kasper
  • Tight bounds for maximum $\ell_1$-margin classifiers
    Stojanovic, Stefan and Donhauser, Konstantin and Yang, Fanny
  • Private PAC Learning May be Harder than Online Learning
    Bun, Mark and Cohen, Aloni and Desai, Rathin
  • Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms
    Mao, Anqi and Mohri, Mehryar and Zhong, Yutao

Outstanding papers

  • “The Attractor of the Replicator Dynamic in Zero-Sum Games” by Oliver Biggar and Iman Shames
  • “Dueling Optimization with a Monotone Adversary” by Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, and Yuanyuan Yang
  • “Multiclass Learnability Does Not Imply Sample Compression” by Chirag Pabbaraju
  • “Private PAC Learning May be Harder than Online Learning” by Mark Bun, Aloni Cohen, and Rathin Desai