ALT 2023

49 papers

Universal Bias Reduction in Estimation of Smooth Additive Function in High Dimensions

Fan Zhou, Ping Li, Cun-hui Zhang

Dictionary Learning for the Almost-Linear Sparsity Regime

Alexei Novikov, Stephen White

Best-of-Both-Worlds Algorithms for Partial Monitoring

Taira Tsuchiya, Shinji Ito, Junya Honda

Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States

Chung-En Tsai, Hao-Chung Cheng, Yen-Huan Li

Optimistic PAC Reinforcement Learning: the Instance-Dependent View

Andrea Tirinzoni, Aymen Al-Marjani, Emilie Kaufmann

Implicit Regularization Towards Rank Minimization in ReLU Networks

Nadav Timor, Gal Vardi, Ohad Shamir

Tournaments, Johnson Graphs and NC-Teaching

Hans U. Simon

Adaptive Power Method: Eigenvector Estimation from Sampled Data

Seiyun Shin, Han Zhao, Ilan Shomorony

Constant regret for sequence prediction with limited advice

El Mehdi Saad, Gilles Blanchard

Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares

Anant Raj, Melih Barsbey, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Şim\scekli

Perceptronic Complexity and Online Matrix Completion

Stephen Pasteris

Towards Empirical Process Theory for Vector-Valued Functions: Metric Entropy of Smooth Function Classes

Junhyung Park, Krikamol Muandet

An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit

Aldo Pacchiano, Peter Bartlett, Michael Jordan

Adversarial Online Multi-Task Reinforcement Learning

Quan Nguyen, Nishant Mehta

Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization

Gergely Neu, Nneka Okolo

Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs

Haipeng Luo, Hanghang Tong, Mengxiao Zhang, Yuheng Zhang

Projection-free Adaptive Regret with Membership Oracles

Zhou Lu, Nataly Brukhim, Paula Gradu, Elad Hazan

Private Stochastic Optimization with Large Worst-Case Lipschitz Parameter: Optimal Rates for (Non-Smooth) Convex Losses and Extension to Non-Convex Losses

Andrew Lowy, Meisam Razaviyayn

Convergence of score-based generative modeling for general data distributions

Holden Lee, Jianfeng Lu, Yixin Tan

Max-Quantile Grouped Infinite-Arm Bandits

Ivan Lau, Yan Hao Ling, Mayank Shrivastava, Jonathan Scarlett

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems

Enikő Kevi, Kim Thang Nguyen

Complexity Analysis of a Countable-armed Bandit Problem

Anand Kalvit, Assaf Zeevi

Dealing with Unknown Variances in Best-Arm Identification

Marc Jourdan, Degenne Rémy, Kaufmann Emilie

Linear Reinforcement Learning with Ball Structure Action Space

Zeyu Jia, Randy Jia, Dhruv Madeka, Dean P. Foster

Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems

Junya Honda, Shinji Ito, Taira Tsuchiya

On Computable Online Learning

Niki Hasrati, Shai Ben-David

Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization

Mahdi Haghifam, Borja Rodríguez-Gálvez, Ragnar Thobaben, Mikael Skoglund, Daniel M. Roy

Online Learning for Traffic Navigation in Congested Networks

Sreenivas Gollapudi, Kostas Kollias, Chinmay Maheshwari, Manxi Wu

Online Learning with Off-Policy Feedback

Germano Gabbianelli, Gergely Neu, Matteo Papini

On The Computational Complexity of Self-Attention

Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, Chinmay Hegde

SQ Lower Bounds for Random Sparse Planted Vector Problem

Jingqiu Ding, Yiding Hua

A Unified Algorithm for Stochastic Path Problems

Christoph Dann, Chen-Yu Wei, Julian Zimmert

Pseudonorm Approachability and Applications to Regret Minimization

Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balubramanian Sivan

Wide stochastic networks: Gaussian limit and PAC-Bayesian training

Eugenio Clerico, George Deligiannidis, Arnaud Doucet

Robust Estimation of Discrete Distributions under Local Differential Privacy

Julien Chhor, Flore Sentenac

Fisher information lower bounds for sampling

Sinho Chewi, Patrik Gerber, Holden Lee, Chen Lu

On the complexity of finding stationary points of smooth functions in one dimension

Sinho Chewi, Sébastien Bubeck, Adil SALIM

Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path

Liyu Chen, Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric

Spatially Adaptive Online Prediction of Piecewise Regular Functions

sabyasachi chatterjee, Subhajit Goswami

A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs

Deeparnab Chakrabarty, Hang Liao

The Replicator Dynamic, Chain Components and the Response Graph

Oliver Biggar, Iman Shames

Online k-means Clustering on Arbitrary Data Streams

Robi Bhattacharjee, Jacob Imola, Michal Moshkovitz, Sanjoy Dasgupta

Robust Empirical Risk Minimization with Tolerance

Robi Bhattacharjee, Max Hopkins, Akash Kumar, Hantao Yu, Kamalika Chaudhuri

On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits

Antoine Barrier, Aurélien Garivier, Gilles Stoltz

Adversarially Robust Learning with Tolerance

Hassan Ashtiani, Vinayak Pathak, Ruth Urner

Reconstructing Ultrametric Trees from Noisy Experiments

Eshwar Ram Arunachaleswaran, Anindya De, Sampath Kannan

Testing Tail Weight of a Distribution Via Hazard Rate

Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld

Variance-Reduced Conservative Policy Iteration

Naman Agarwal, Brian Bullins, Karan Singh

Algorithmic Learning Theory 2023: Preface

Shipra Agrawal, Francesco Orabona