Algorithmic Learning Theory 2023: Preface

Shipra Agrawal, Francesco Orabona; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1-2

[abs][Download PDF]

Variance-Reduced Conservative Policy Iteration

Naman Agarwal, Brian Bullins, Karan Singh; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:3-33

[abs][Download PDF]

Testing Tail Weight of a Distribution Via Hazard Rate

Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:34-81

[abs][Download PDF]

Reconstructing Ultrametric Trees from Noisy Experiments

Eshwar Ram Arunachaleswaran, Anindya De, Sampath Kannan; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:82-114

[abs][Download PDF]

Adversarially Robust Learning with Tolerance

Hassan Ashtiani, Vinayak Pathak, Ruth Urner; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:115-135

[abs][Download PDF]

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

Antoine Barrier, Aurélien Garivier, Gilles Stoltz; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:136-181

[abs][Download PDF]

Robust Empirical Risk Minimization with Tolerance

Robi Bhattacharjee, Max Hopkins, Akash Kumar, Hantao Yu, Kamalika Chaudhuri; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:182-203

[abs][Download PDF]

Online k-means Clustering on Arbitrary Data Streams

Robi Bhattacharjee, Jacob Imola, Michal Moshkovitz, Sanjoy Dasgupta; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:204-236

[abs][Download PDF]

The Replicator Dynamic, Chain Components and the Response Graph

Oliver Biggar, Iman Shames; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:237-258

[abs][Download PDF]

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

Deeparnab Chakrabarty, Hang Liao; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:259-274

[abs][Download PDF]

Spatially Adaptive Online Prediction of Piecewise Regular Functions

Sabyasachi Chatterjee, Subhajit Goswami; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:275-309

[abs][Download PDF]

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

Liyu Chen, Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:310-357

[abs][Download PDF]

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

Sinho Chewi, Sébastien Bubeck, Adil Salim; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:358-374

[abs][Download PDF]

Fisher information lower bounds for sampling

Sinho Chewi, Patrik Gerber, Holden Lee, Chen Lu; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:375-410

[abs][Download PDF]

Robust Estimation of Discrete Distributions under Local Differential Privacy

Julien Chhor, Flore Sentenac; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:411-446

[abs][Download PDF]

Wide stochastic networks: Gaussian limit and PAC-Bayesian training

Eugenio Clerico, George Deligiannidis, Arnaud Doucet; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:447-470

[abs][Download PDF]

Pseudonorm Approachability and Applications to Regret Minimization

Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balubramanian Sivan; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:471-509

[abs][Download PDF]

A Unified Algorithm for Stochastic Path Problems

Christoph Dann, Chen-Yu Wei, Julian Zimmert; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:510-557

[abs][Download PDF]

SQ Lower Bounds for Random Sparse Planted Vector Problem

Jingqiu Ding, Yiding Hua; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:558-596

[abs][Download PDF]

On The Computational Complexity of Self-Attention

Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, Chinmay Hegde; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:597-619

[abs][Download PDF]

Online Learning with Off-Policy Feedback

Germano Gabbianelli, Gergely Neu, Matteo Papini; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:620-641

[abs][Download PDF]

Online Learning for Traffic Navigation in Congested Networks

Sreenivas Gollapudi, Kostas Kollias, Chinmay Maheshwari, Manxi Wu; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:642-662

[abs][Download PDF]

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, Gintare Karolina Dziugaite; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:663-706

[abs][Download PDF]

On Computable Online Learning

Niki Hasrati, Shai Ben-David; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:707-725

[abs][Download PDF]

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

Junya Honda, Shinji Ito, Taira Tsuchiya; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:726-754

[abs][Download PDF]

Linear Reinforcement Learning with Ball Structure Action Space

Zeyu Jia, Randy Jia, Dhruv Madeka, Dean P. Foster; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:755-775

[abs][Download PDF]

Dealing with Unknown Variances in Best-Arm Identification

Marc Jourdan, Degenne Rémy, Kaufmann Emilie; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:776-849

[abs][Download PDF]

Complexity Analysis of a Countable-armed Bandit Problem

Anand Kalvit, Assaf Zeevi; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:850-890

[abs][Download PDF]

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

Enikő Kevi, Kim Tháng Nguyễn; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:891-908

[abs][Download PDF]

Max-Quantile Grouped Infinite-Arm Bandits

Ivan Lau, Yan Hao Ling, Mayank Shrivastava, Jonathan Scarlett; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:909-945

[abs][Download PDF]

Convergence of score-based generative modeling for general data distributions

Holden Lee, Jianfeng Lu, Yixin Tan; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:946-985

[abs][Download PDF]

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; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:986-1054

[abs][Download PDF]

Projection-free Adaptive Regret with Membership Oracles

Zhou Lu, Nataly Brukhim, Paula Gradu, Elad Hazan; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1055-1073

[abs][Download PDF]

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

Haipeng Luo, Hanghang Tong, Mengxiao Zhang, Yuheng Zhang; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1074-1100

[abs][Download PDF]

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

Gergely Neu, Nneka Okolo; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1101-1123

[abs][Download PDF]

Adversarial Online Multi-Task Reinforcement Learning

Quan Nguyen, Nishant Mehta; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1124-1165

[abs][Download PDF]

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

Aldo Pacchiano, Peter Bartlett, Michael Jordan; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1166-1215

[abs][Download PDF]

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

Junhyung Park, Krikamol Muandet; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1216-1260

[abs][Download PDF]

Perceptronic Complexity and Online Matrix Completion

Stephen Pasteris; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1261-1291

[abs][Download PDF]

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

Anant Raj, Melih Barsbey, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Şim\scekli; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1292-1342

[abs][Download PDF]

Constant regret for sequence prediction with limited advice

El Mehdi Saad, Gilles Blanchard; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1343-1386

[abs][Download PDF]

Adaptive Power Method: Eigenvector Estimation from Sampled Data

Seiyun Shin, Han Zhao, Ilan Shomorony; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1387-1410

[abs][Download PDF]

Tournaments, Johnson Graphs and NC-Teaching

Hans U. Simon; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1411-1428

[abs][Download PDF]

Implicit Regularization Towards Rank Minimization in ReLU Networks

Nadav Timor, Gal Vardi, Ohad Shamir; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1429-1459

[abs][Download PDF]

Optimistic PAC Reinforcement Learning: the Instance-Dependent View

Andrea Tirinzoni, Aymen Al-Marjani, Emilie Kaufmann; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1460-1480

[abs][Download PDF]

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; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1481-1483

[abs][Download PDF]

Best-of-Both-Worlds Algorithms for Partial Monitoring

Taira Tsuchiya, Shinji Ito, Junya Honda; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1484-1515

[abs][Download PDF]

Dictionary Learning for the Almost-Linear Sparsity Regime

Alexei Novikov, Stephen White; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1516-1554

[abs][Download PDF]

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

Fan Zhou, Ping Li, Cun-Hui Zhang; Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:1555-1578

[abs][Download PDF]