ALT 2026

69 papers

Efficient and Provable Algorithms for Covariate Shift

Deeksha Adil, Jaroslaw Blasiok

Convex optimization with p-norm oracles

Deeksha Adil, Brian Bullins, Arun Jambulapati, Aaron Sidford

Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data

Shubhada Agrawal, Aaditya Ramdas

Learning from Synthetic Data: Limitations of ERM

Kareem Amin, Alex Bie, Weiwei Kong, Umar Syed, Sergei Vassilvitskii

Group-realizable multi-group learning by minimizing empirical risk

Navid Ardeshir, Samuel Deng, Daniel Hsu, Jingwen Liu

Robust Online Learning

Sajad Ashkezari

On the Hardness of Learning Regular Expressions

Idan Attias, Lev Reyzin, Nathan Srebro, Gal Vardi

Reward Selection with Noisy Observations

Kamyar Azizzadenesheli, Trung Dang, Aranyak Mehta, Alexandros Psomas, Qian Zhang

Discriminative Feature Feedback with General Teacher Classes

Omri Bar Oz, Tosca Lechner, Sivan Sabato

Predictive inference for time series: why is split conformal effective despite temporal dependence?

Rina Foygel Barber, Ashwin Pananjady

Beyond Discrepancy: A Closer Look at the Theory of Distribution Shift

Robi Bhattacharjee, Nicholas Rittler, Kamalika Chaudhuri

Sink equilibria and the attractors of learning in games

Oliver Biggar, Christos H. Papadimitriou

Regularized Robustly Reliable Learners

Avrim Blum, Donya Saless

Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm

Pierre Boudart, Pierre Gaillard, Alessandro Rudi

Privately Learning Decision Lists and a Differentially Private Winnow

Mark Bun, William Fang

Closeness testing from distributed measurements

Clement Louis Canonne, Aditya Vikram Singh

Pareto-optimal Non-uniform Language Generation

Moses Charikar, Chirag Pabbaraju

A Martingale Kernel Two-Sample Test

Anirban Chatterjee, Aaditya Ramdas

Talagrand Meets Talagrand: Upper and Lower Bounds on Expected Soft Maxima of Gaussian Processes with Finite Index Sets

Yifeng Chu, Maxim Raginsky

Sample-Near-Optimal Agnostic Boosting with Improved Running Time

Arthur da Cunha, Mikael Møller Høgsgaard, Andrea Paudice

On Purely Private Covariance Estimation

Tommaso d’Orsi, Gleb Novikov

Suspicious Alignment of SGD:A Fine-Grained Step Size Condition Analysis

Shenyang Deng, Boyao Liao, Zhuoli Ouyang, Tianyu Pang, Minhak Song

Uniform Convergence Beyond Glivenko-Cantelli

Tanmay Devale, Pramith Devulapalli, Steve Hanneke

Phase Transition of Regret for Logistic Regression with Large Weights

Michael Drmota, Philippe Jacquet, Changlong Wu, Wojciech Szpankowski

From Continual Learning to SGD and Back: Better Rates for Continual Linear Models

Itay Evron, Ran Levinstein, Matan Schliserman, Uri Sherman, Tomer Koren

Online and Offline Learning of Orderly Hypergraphs Using Queries

Shaun Fallat, Kamyar Khodamoradi, David G. Kirkpatrick, Valerii Maliuk, Seyed Ahmad Mojallal

Sparse Nonparametric Contextual Bandits

Hamish Flynn, Julia Olkhovskaya, Paul Rognon-Vael

Relative Information Gain and Gaussian Process Regression

Hamish Flynn

Distribution-Dependent Rates for Multi-Distribution Learning

Rafael Hanashiro, Patrick Jaillet

Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability

Dirk van der Hoeven, Julia Olkhovskaya, Tim van Erven

Strategy-robust Online Learning in Contextual Pricing

Joon Suk Huh, Kirthevasan Kandasamy

Reusing Samples in Variance Reduction

Yujia Jin, Ishani Karmarkar, Aaron Sidford, Jiayi Wang

On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability

Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas

Optimal L2 Regularization in High-dimensional Continual Linear Regression

Gilad Karpel, Edward Moroshko, Ran Levinstein, Ron Meir, Daniel Soudry

The Planted Number Partitioning Problem

Eren C. Kizildağ

DS-Compatible Log-Linear Reliability with KL-Prox EM: Monotone Ascent, Identifiability, and Generalization

Shiva Koreddi, Sravani Sowrupilli

Differentially Private Bilevel Optimization

Guy Kornowski

Learning with Monotone Adversarial Corruptions

Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty

Improved Replicable Boosting with Majority-of-Majorities

Kasper Green Larsen, Markus Engelund Mathiasen, Clement Svendsen

No Scale Sensitive Dimension for Distribution Learning

Tosca Lechner, Shai Ben-David

Accelerated Mirror Descent for Non-Euclidean Star-convex Functions

Clement LEZANE, Sophie Langer, Wouter M Koolen

Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method

Jiaming Liang

Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications

Zijian Liu

Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model

Xingtu Liu, Lin F. Yang, Sharan Vaswani

Efficient Opportunistic Approachability

Teodor Vanislavov Marinov, Mehryar Mohri, Princewill Okoroafor, Jon Schneider, Julian Zimmert

Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity

Diego Martinez-Taboada, Tomas Gonzalez, Aaditya Ramdas

Online Markov Decision Processes with Terminal Law Constraints

Bianca Marin Moreno, Margaux Brégère, Pierre Gaillard, Nadia Oudjane

Online Covering with Multiple Experts

Kim Thang Nguyen

How to Set β_1, β_2 in Adam: An Online Learning Perspective

Quan M. Nguyen

A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes

Alireza F. Pour, Shai Ben-David

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers

Abhishek Hegade K. R., Eren C. Kizildağ

Optimal Bounds for Tyler’s M-Estimator for Elliptical Distributions

Akshay Ramachandran, Lap Chi Lau

Recycling History: Efficient Recommendations from Contextual Dueling Bandits

Suryanarayana Sankagiri, Jalal Etesami, Pouria Fatemi, Matthias Grossglauser

Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization

Matan Schliserman, Tomer Koren

Compressibility Barriers to Neighborhood-Preserving Data Visualization

Szymon Snoeck, Noah Bergam, Nakul Verma

Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective

Vishwak Srinivasan, Qijia Jiang

On the Role of Transformer Feed-Forward Layers in Nonlinear In-Context Learning

Haoyuan Sun, Ali Jadbabaie, Navid Azizan

Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization

Subhamon Supantha, Abhishek Sinha

Ranking Items from Discrete Ratings: The Cost of Unknown User Thresholds

Oscar Villemaud, Suryanarayana Sankagiri, Matthias Grossglauser

Universality of conformal prediction under the assumption of randomness

Vladimir Vovk

Multi-distribution Learning: From Worst-Case Optimality to Lexicographic Min-Max Optimality

Guanghui Wang, Umar Syed, Robert E. Schapire, Jacob Abernethy

Last-iterate Convergence for Symmetric, General-sum, 2 × 2 Games Under The Exponential Weights Dynamic

Guanghui Wang, Krishna Acharya, Lokranjan Lakshmikanthan, Juba Ziani, Vidya Muthukumar

Bridging Lifelong and Multi-Task Representation Learning: An Algorithm and a Complexity Measure

Zhi Wang, Chicheng Zhang, Ramya Korlakai Vinayak

Graph Inference with Effective Resistance Queries

Evelyn Warton, Huck Bennett, Mitchell Black, Amir Nayyeri

PAC-Bayesian Analysis of the Surrogate Relation between Joint Embedding and Supervised Downstream Losses

Theresa Wasserer, Maximilian Fleissner, Debarghya Ghoshdastidar

Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy

Ruihan Wu, Yu-Xiang Wang

Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attention

Yingzhen Yang

Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms

Ali Zeynali, Mahsa Sahebdel, QINGSONG LIU, Ramesh K. Sitaraman, Mohammad Hajiesmaili

Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential

Yuping Zheng, Andrew Lamperski