ALT 2025

52 papers

The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis

Matthew Zurek, Yudong Chen

Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit

Julien Zhou, Pierre Gaillard, Thibaud Rahier, Julyan Arbel

How rotation invariant algorithms are fooled by noise on sparse targets

Manfred K. Warmuth, Wojciech Kot\polishlowski, Matt Jones, Ehsan Amid

Noisy Computing of the Threshold Function

Ziao Wang, Nadim Ghaddar, Banghua Zhu, Lele Wang

Online Learning of Quantum States with Logarithmic Loss via VB-FTRL

Wei-Fu Tseng, Kai-Chun Chen, Zi-Hong Xiao, Yen-Huan Li

Clustering with bandit feedback: breaking down the computation/information gap

Victor Thuot, Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen

High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm

Vishwak Srinivasan, Andre Wibisono, Ashia Wilson

Self-Directed Node Classification on Graphs

Georgy Sokolov, Maximilian Thiessen, Margarita Akhmejanova, Fabio Vitale, Francesco Orabona

Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate

Jie Shen

The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization

Matan Schliserman, Uri Sherman, Tomer Koren

An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems.

Sarah Sachs, Hedi Hadiji, Tim van Erven, Mathias Staudigl

A Unified Theory of Supervised Online Learnability

Vinod Raman, UNIQUE SUBEDI, Ambuj Tewari

Data Dependent Regret Bounds for Online Portfolio Selection with Predicted Returns

Sudeep Raja Putta, Shipra Agrawal

On Generalization Bounds for Neural Networks with Low Rank Layers

Andrea Pinto, Akshay Rangamani, Tomaso A Poggio

A Characterization of List Regression

Chirag Pabbaraju, Sahasrajit Sarmasarkar

Fast Convergence of $Φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler

Siddharth Mitra, Andre Wibisono

Center-Based Approximation of a Drifting Distribution

Alessio Mazzetto, Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, Eli Upfal

Enhanced H-Consistency Bounds

Anqi Mao, Mehryar Mohri, Yutao Zhong

Computationally efficient reductions between some statistical models

Mengqi Lou, Guy Bresler, Ashwin Pananjady

Error dynamics of mini-batch gradient descent with random reshuffling for least squares regression

Jackie Lok, Rishi Sonthalia, Elizaveta Rebrova

Minimax-optimal and Locally-adaptive Online Nonparametric Regression

Paul Liautaud, Pierre Gaillard, Olivier Wintenberger

On the Hardness of Learning One Hidden Layer Neural Networks

Shuchen Li, Ilias Zadik, Manolis Zampetakis

Quantile Multi-Armed Bandits with 1-bit Feedback

Ivan Lau, Jonathan Scarlett

Sharp bounds on aggregate expert error

Aryeh Kontorovich, Ariel Avital

Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements

Eren C. Kızıldağ

Optimal and learned algorithms for the online list update problem with Zipfian accesses

Piotr Indyk, Isabelle Quaye, Ronitt Rubinfeld, Sandeep Silwal

Do PAC-Learners Learn the Marginal Distribution?

Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan

Efficient Optimal PAC Learning

Mikael Høgsgaard Møller

A Complete Characterization of Learnability for Stochastic Noisy Bandits

Steve Hanneke, Kun Wang

For Universal Multiclass Online Learning, Bandit Feedback and Full Supervision are Equivalent

Steve Hanneke, Amirreza Shaeiri, Hongao Wang

Reliable Active Apprenticeship Learning

Steve Hanneke, Liu Yang, Gongju Wang, Yulun Song

A PAC-Bayesian Link Between Generalisation and Flat Minima

Maxime Haddouche, Paul Viallard, Umut Simsekli, Benjamin Guedj

Full Swap Regret and Discretized Calibration

Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider

Is Transductive Learning Equivalent to PAC Learning?

Shaddin Dughmi, Yusuf Hakan Kalayci, Grayson York

Effective Littlestone dimension

Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer

Boosting, Voting Classifiers and Randomized Sample Compression Schemes

Arthur da Cunha, Kasper Green Larsen, Martin Ritzert

Generalisation under gradient descent via deterministic PAC-Bayes

Eugenio Clerico, Tyler Farghly, George Deligiannidis, Benjamin Guedj, Arnaud Doucet

Near-Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches

Christopher A. Choquette-Choo, Arun Ganesh, Abhradeep Guha Thakurta

Differentially Private Multi-Sampling from Distributions

Albert Cheu, Debanuj Nayak

A Model for Combinatorial Dictionary Learning and Inference

Avrim Blum, Kavya Ravichandran

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem

Avrim Blum, Kavya Ravichandran

Non-stochastic Bandits With Evolving Observations

Yogev Bar-On, Yishay Mansour

Cost-Free Fairness in Online Correlation Clustering

Eric Balkanski, Jason Chatzitheodorou, Andreas Maggiori

Strategyproof Learning with Advice

Eric Balkanski, Cherlin Zhu

Sample Compression Scheme Reductions

Idan Attias, Steve Hanneke, Arvind Ramaswami

Proper Learnability and the Role of Unlabeled Data

Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng

Understanding Aggregations of Proper Learners in Multiclass Classification

Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas

Refining the Sample Complexity of Comparative Learning

Sajad Ashkezari, Ruth Urner

Agnostic Private Density Estimation for GMMs via List Global Stability

Mohammad Afzali, Hassan Ashtiani, Christopher Liaw

Generalization bounds for mixing processes via delayed online-to-PAC conversions

Baptiste Abélès, Eugenio Clerico, Gergely Neu

When and why randomised exploration works (in linear bandits)

Marc Abeille, David Janz, Ciara Pike-Burke

Algorithmic Learning Theory 2025: Preface

Gautam Kamath, Po-ling Loh