ALT 2025

51 papers

A Characterization of List Regression Chirag Pabbaraju, Sahasrajit Sarmasarkar

A Complete Characterization of Learnability for Stochastic Noisy Bandits Steve Hanneke, Kun Wang

A Model for Combinatorial Dictionary Learning and Inference Avrim Blum, Kavya Ravichandran

A PAC-Bayesian Link Between Generalisation and Flat Minima Maxime Haddouche, Paul Viallard, Umut Simsekli, Benjamin Guedj

A Unified Theory of Supervised Online Learnability Vinod Raman, Unique Subedi, Ambuj Tewari

Agnostic Private Density Estimation for GMMs via List Global Stability Mohammad Afzali, Hassan Ashtiani, Christopher Liaw

An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems. Sarah Sachs, Hedi Hadiji, Tim Van Erven, Mathias Staudigl

Boosting, Voting Classifiers and Randomized Sample Compression Schemes Arthur Cunha, Kasper Green Larsen, Martin Ritzert

Center-Based Approximation of a Drifting Distribution Alessio Mazzetto, Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, Eli Upfal

Clustering with Bandit Feedback: Breaking Down the Computation/information Gap Victor Thuot, Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen

Computationally Efficient Reductions Between Some Statistical Models Mengqi Lou, Guy Bresler, Ashwin Pananjady

Cost-Free Fairness in Online Correlation Clustering Eric Balkanski, Jason Chatzitheodorou, Andreas Maggiori

Data Dependent Regret Bounds for Online Portfolio Selection with Predicted Returns Sudeep Raja Putta, Shipra Agrawal

Differentially Private Multi-Sampling from Distributions Albert Cheu, Debanuj Nayak

Do PAC-Learners Learn the Marginal Distribution? Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan

Effective Littlestone Dimension Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer

Efficient Optimal PAC Learning Mikael Høgsgaard Møller

Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate Jie Shen

Enhanced $h$-Consistency Bounds Anqi Mao, Mehryar Mohri, Yutao Zhong

Error Dynamics of Mini-Batch Gradient Descent with Random Reshuffling for Least Squares Regression Jackie Lok, Rishi Sonthalia, Elizaveta Rebrova

Fast Convergence of $φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler Siddharth Mitra, Andre Wibisono

For Universal Multiclass Online Learning, Bandit Feedback and Full Supervision Are Equivalent Steve Hanneke, Amirreza Shaeiri, Hongao Wang

Full Swap Regret and Discretized Calibration Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, Yifeng Teng

Generalisation Under Gradient Descent via Deterministic PAC-Bayes Eugenio Clerico, Tyler Farghly, George Deligiannidis, Benjamin Guedj, Arnaud Doucet

Generalization Bounds for Mixing Processes via Delayed Online-to-PAC Conversions Baptiste Abélès, Eugenio Clerico, Gergely Neu

High-Accuracy Sampling from Constrained Spaces with the Metropolis-Adjusted Preconditioned Langevin Algorithm Vishwak Srinivasan, Andre Wibisono, Ashia Wilson

How Rotation Invariant Algorithms Are Fooled by Noise on Sparse Targets Manfred K. Warmuth, Wojciech Kot\polishlowski, Matt Jones, Ehsan Amid

Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements Eren C. Kızıldağ

Is Transductive Learning Equivalent to PAC Learning? Shaddin Dughmi, Yusuf Hakan Kalayci, Grayson York

Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit Julien Zhou, Pierre Gaillard, Thibaud Rahier, Julyan Arbel

Minimax-Optimal and Locally-Adaptive Online Nonparametric Regression Paul Liautaud, Pierre Gaillard, Olivier Wintenberger

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

Nearly-Tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem Avrim Blum, Kavya Ravichandran

Noisy Computing of the Threshold Function Ziao Wang, Nadim Ghaddar, Banghua Zhu, Lele Wang

Non-Stochastic Bandits with Evolving Observations Yogev Bar-On, Yishay Mansour

On Generalization Bounds for Neural Networks with Low Rank Layers Andrea Pinto, Akshay Rangamani, Tomaso A Poggio

On the Hardness of Learning One Hidden Layer Neural Networks Shuchen Li, Ilias Zadik, Manolis Zampetakis

Online Learning of Quantum States with Logarithmic Loss via VB-FTRL Wei-Fu Tseng, Kai-Chun Chen, Zi-Hong Xiao, Yen-Huan Li

Optimal and Learned Algorithms for the Online List Update Problem with Zipfian Accesses Piotr Indyk, Isabelle Quaye, Ronitt Rubinfeld, Sandeep Silwal

Proper Learnability and the Role of Unlabeled Data Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng

Quantile Multi-Armed Bandits with 1-Bit Feedback Ivan Lau, Jonathan Scarlett

Refining the Sample Complexity of Comparative Learning Sajad Ashkezari, Ruth Urner

Reliable Active Apprenticeship Learning Steve Hanneke, Liu Yang, Gongju Wang, Yulun Song

Sample Compression Scheme Reductions Idan Attias, Steve Hanneke, Arvind Ramaswami

Self-Directed Node Classification on Graphs Georgy Sokolov, Maximilian Thiessen, Margarita Akhmejanova, Fabio Vitale, Francesco Orabona

Sharp Bounds on Aggregate Expert Error Aryeh Kontorovich, Ariel Avital

Strategyproof Learning with Advice Eric Balkanski, Cherlin Zhu

The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization Matan Schliserman, Uri Sherman, Tomer Koren

The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis Matthew Zurek, Yudong Chen

Understanding Aggregations of Proper Learners in Multiclass Classification Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas

When and Why Randomised Exploration Works (in Linear Bandits) Marc Abeille, David Janz, Ciara Pike-Burke