ALT 2024

44 papers

A Mechanism for Sample-Efficient In-Context Learning for Sparse Retrieval Tasks Jacob Abernethy, Alekh Agarwal, Teodor Vanislavov Marinov, Manfred K. Warmuth

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

Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies Shlomi Weitzman, Sivan Sabato

Adversarial Contextual Bandits Go Kernelized Gergely Neu, Julia Olkhovskaya, Sattar Vakili

Adversarial Online Collaborative Filtering Stephen Pasteris, Fabio Vitale, Mark Herbster, Claudio Gentile, Andre Panisson

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

Alternating Minimization for Generalized Rank One Matrix Sensing: Sharp Predictions from a Random Initialization Kabir Aladin Verchand, Mengqi Lou, Ashwin Pananjady

Computation with Sequences of Assemblies in a Model of the Brain Max Dabagia, Christos Papadimitriou, Santosh Vempala

Concentration of Empirical Barycenters in Metric Spaces Victor-Emmanuel Brunel, Jordan Serres

Corruption-Robust Lipschitz Contextual Search Shiliang Zuo

CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption Shubhada Agrawal, Timothée Mathieu, Debabrota Basu, Odalric-Ambrym Maillard

Differentially Private Non-Convex Optimization Under the KL Condition with Optimal Rates Michael Menart, Enayat Ullah, Raman Arora, Raef Bassily, Cristobal Guzman

Distances for Markov Chains, and Their Differentiation Tristan Brugère, Zhengchao Wan, Yusu Wang

Dueling Optimization with a Monotone Adversary Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, Yuanyuan Yang

Efficient Agnostic Learning with Average Smoothness Steve Hanneke, Aryeh Kontorovich, Guy Kornowski

Importance-Weighted Offline Learning Done Right Germano Gabbianelli, Gergely Neu, Matteo Papini

Improving Adaptive Online Learning Using Refined Discretization Zhiyu Zhang, Heng Yang, Ashok Cutkosky, Ioannis C Paschalidis

Learning Bounded-Degree Polytrees with Known Skeleton Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, Clément L Canonne

Learning Hypertrees from Shortest Path Queries Shaun M Fallat, Valerii Maliuk, Seyed Ahmad Mojallal, Sandra Zilles

Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT Queries Hang Liao, Deeparnab Chakrabarty

Mixtures of Gaussians Are Privately Learnable with a Polynomial Number of Samples Mohammad Afzali, Hassan Ashtiani, Christopher Liaw

Multiclass Learnability Does Not Imply Sample Compression Chirag Pabbaraju

Multiclass Online Learnability Under Bandit Feedback Ananth Raman, Vinod Raman, Unique Subedi, Idan Mehalel, Ambuj Tewari

Near-Continuous Time Reinforcement Learning for Continuous State-Action Spaces Lorenzo Croissant, Marc Abeille, Bruno Bouchard

Not All Learnable Distribution Classes Are Privately Learnable Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal

On the Computational Benefit of Multimodal Learning Zhou Lu

On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation Amit Daniely, Elad Granot

Online Infinite-Dimensional Regression: Learning Linear Operators Unique Subedi, Vinod Raman, Ambuj Tewari

Online Recommendations for Agents with Discounted Adaptive Preferences William Brown, Arpit Agarwal

Optimal Regret Bounds for Collaborative Learning in Bandits Amitis Shidani, Sattar Vakili

Partially Interpretable Models with Guarantees on Coverage and Accuracy Nave Frost, Zachary Lipton, Yishay Mansour, Michal Moshkovitz

Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms Anqi Mao, Mehryar Mohri, Yutao Zhong

Private PAC Learning May Be Harder than Online Learning Mark Bun, Aloni Cohen, Rathin Desai

Provable Accelerated Convergence of Nesterov’s Momentum for Deep ReLU Neural Networks Fangshuo Liao, Anastasios Kyrillidis

RedEx: Beyond Fixed Representation Methods via Convex Optimization Amit Daniely, Mariano Schain, Gilad Yehudai

Semi-Supervised Group DRO: Combating Sparsity with Unlabeled Data Pranjal Awasthi, Satyen Kale, Ankit Pensia

Slowly Changing Adversarial Bandit Algorithms Are Efficient for Discounted MDPs Ian A. Kash, Lev Reyzin, Zishun Yu

The Attractor of the Replicator Dynamic in Zero-Sum Games Oliver Biggar, Iman Shames

The Complexity of Non-Stationary Reinforcement Learning Binghui Peng, Christos Papadimitriou

The Dimension of Self-Directed Learning Pramith Devulapalli, Steve Hanneke

The Impossibility of Parallelizing Boosting Amin Karbasi, Kasper Green Larsen

Tight Bounds for Local Glivenko-Cantelli Moïse Blanchard, Vaclav Voracek

Tight Bounds for Maximum $\ell_1$-Margin Classifiers Stefan Stojanovic, Konstantin Donhauser, Fanny Yang

Universal Representation of Permutation-Invariant Functions on Vectors and Tensors Puoya Tabaghi, Yusu Wang