ALT 2024

45 papers

Corruption-Robust Lipschitz Contextual Search

Shiliang Zuo

Improving Adaptive Online Learning Using Refined Discretization

Zhiyu Zhang, Heng Yang, Ashok Cutkosky, Ioannis C Paschalidis

Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies

Shlomi Weitzman, Sivan Sabato

Universal Representation of Permutation-Invariant Functions on Vectors and Tensors

Puoya Tabaghi, Yusu Wang

Online Infinite-Dimensional Regression: Learning Linear Operators

UNIQUE SUBEDI, Vinod Raman, Ambuj Tewari

Tight bounds for maximum ℓ_1-margin classifiers

Stefan Stojanovic, Konstantin Donhauser, Fanny Yang

A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions

Vikrant Singhal

Optimal Regret Bounds for Collaborative Learning in Bandits

Amitis Shidani, Sattar Vakili

Multiclass Online Learnability under Bandit Feedback

Ananth Raman, Vinod Raman, UNIQUE SUBEDI, Idan Mehalel, Ambuj Tewari

The complexity of non-stationary reinforcement learning

Binghui Peng, Christos Papadimitriou

Adversarial Online Collaborative Filtering

Stephen Pasteris, Fabio Vitale, Mark Herbster, Claudio Gentile, Andre Panisson

Multiclass Learnability Does Not Imply Sample Compression

Chirag Pabbaraju

Adversarial Contextual Bandits Go Kernelized

Gergely Neu, Julia Olkhovskaya, Sattar Vakili

Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates

Michael Menart, Enayat Ullah, Raman Arora, Raef Bassily, Cristóbal Guzmán

Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms

Anqi Mao, Mehryar Mohri, Yutao Zhong

On the Computational Benefit of Multimodal Learning

Zhou Lu

Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization

Kabir Aladin Verchand, Mengqi Lou, Ashwin Pananjady

Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries

Hang Liao, Deeparnab Chakrabarty

Provable Accelerated Convergence of Nesterov’s Momentum for Deep ReLU Neural Networks

Fangshuo Liao, Anastasios Kyrillidis

Efficient Agnostic Learning with Average Smoothness

Steve Hanneke, Aryeh Kontorovich, Guy Kornowski

Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs

Ian A. Kash, Lev Reyzin, Zishun Yu

Agnostic Membership Query Learning with Nontrivial Savings: New Results and Techniques

Ari Karchmer

The Impossibility of Parallelizing Boosting

Amin Karbasi, Kasper Green Larsen

Importance-Weighted Offline Learning Done Right

Germano Gabbianelli, Gergely Neu, Matteo Papini

Partially Interpretable Models with Guarantees on Coverage and Accuracy

Nave Frost, Zachary Lipton, Yishay Mansour, Michal Moshkovitz

Learning Hypertrees From Shortest Path Queries

Shaun M Fallat, Valerii Maliuk, Seyed Ahmad Mojallal, Sandra Zilles

The Dimension of Self-Directed Learning

Pramith Devulapalli, Steve Hanneke

RedEx: Beyond Fixed Representation Methods via Convex Optimization

Amit Daniely, Mariano Schain, Gilad Yehudai

On the Sample Complexity of Two-Layer Networks: Lipschitz Vs. Element-Wise Lipschitz Activation

Amit Daniely, Elad Granot

Computation with Sequences of Assemblies in a Model of the Brain

Max Dabagia, Christos Papadimitriou, Santosh Vempala

Near-continuous time Reinforcement Learning for continuous state-action spaces

Lorenzo Croissant, Marc Abeille, Bruno Bouchard

Learning bounded-degree polytrees with known skeleton

Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, Clément L Canonne

Not All Learnable Distribution Classes are Privately Learnable

Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal

Private PAC Learning May be Harder than Online Learning

Mark Bun, Aloni Cohen, Rathin Desai

Concentration of empirical barycenters in metric spaces

Victor-Emmanuel Brunel, Jordan Serres

Distances for Markov Chains, and Their Differentiation

Tristan Brugère, Zhengchao Wan, Yusu Wang

Online Recommendations for Agents with Discounted Adaptive Preferences

William Brown, Arpit Agarwal

Dueling Optimization with a Monotone Adversary

Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha

Tight Bounds for Local Glivenko-Cantelli

Moise Blanchard, Václav Voráček

The Attractor of the Replicator Dynamic in Zero-Sum Games

Oliver Biggar, Iman Shames

Semi-supervised Group DRO: Combating Sparsity with Unlabeled Data

Pranjal Awasthi, Satyen Kale, Ankit Pensia

CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption

Shubhada Agrawal, Timothée Mathieu, Debabrota Basu, Odalric-ambrym Maillard

Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples

Mohammad Afzali, Hassan Ashtiani, Christopher Liaw

A Mechanism for Sample-Efficient In-Context Learning for Sparse Retrieval Tasks

Jacob Abernethy, Alekh Agarwal, Teodor Vanislavov Marinov, Manfred K. Warmuth

Algorithmic Learning Theory 2024: Preface

Claire Vernade, Daniel Hsu