ALT 2023

48 papers

A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs Deeparnab Chakrabarty, Hang Liao

A Unified Algorithm for Stochastic Path Problems Christoph Dann, Chen-Yu Wei, Julian Zimmert

Adaptive Power Method: Eigenvector Estimation from Sampled Data Seiyun Shin, Han Zhao, Ilan Shomorony

Adversarial Online Multi-Task Reinforcement Learning Quan Nguyen, Nishant Mehta

Adversarially Robust Learning with Tolerance Hassan Ashtiani, Vinayak Pathak, Ruth Urner

Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares Anant Raj, Melih Barsbey, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Şim\scekli

An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit Aldo Pacchiano, Peter Bartlett, Michael Jordan

Best-of-Both-Worlds Algorithms for Partial Monitoring Taira Tsuchiya, Shinji Ito, Junya Honda

Complexity Analysis of a Countable-Armed Bandit Problem Anand Kalvit, Assaf Zeevi

Constant Regret for Sequence Prediction with Limited Advice El Mehdi Saad, Gilles Blanchard

Convergence of Score-Based Generative Modeling for General Data Distributions Holden Lee, Jianfeng Lu, Yixin Tan

Dealing with Unknown Variances in Best-Arm Identification Marc Jourdan, Degenne Rémy, Kaufmann Emilie

Dictionary Learning for the Almost-Linear Sparsity Regime Alexei Novikov, Stephen White

Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization Gergely Neu, Nneka Okolo

Fisher Information Lower Bounds for Sampling Sinho Chewi, Patrik Gerber, Holden Lee, Chen Lu

Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems Junya Honda, Shinji Ito, Taira Tsuchiya

Implicit Regularization Towards Rank Minimization in ReLU Networks Nadav Timor, Gal Vardi, Ohad Shamir

Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs Haipeng Luo, Hanghang Tong, Mengxiao Zhang, Yuheng Zhang

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

Linear Reinforcement Learning with Ball Structure Action Space Zeyu Jia, Randy Jia, Dhruv Madeka, Dean P. Foster

Max-Quantile Grouped Infinite-Arm Bandits Ivan Lau, Yan Hao Ling, Mayank Shrivastava, Jonathan Scarlett

On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits Antoine Barrier, Aurélien Garivier, Gilles Stoltz

On Computable Online Learning Niki Hasrati, Shai Ben-David

On the Complexity of Finding Stationary Points of Smooth Functions in One Dimension Sinho Chewi, Sébastien Bubeck, Adil Salim

On the Computational Complexity of Self-Attention Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, Chinmay Hegde

Online K-Means Clustering on Arbitrary Data Streams Robi Bhattacharjee, Jacob Imola, Michal Moshkovitz, Sanjoy Dasgupta

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

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

Perceptronic Complexity and Online Matrix Completion Stephen Pasteris

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems Enikő Kevi, Kim Tháng Nguyễn

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

Projection-Free Adaptive Regret with Membership Oracles Zhou Lu, Nataly Brukhim, Paula Gradu, Elad Hazan

Pseudonorm Approachability and Applications to Regret Minimization Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balubramanian Sivan

Reaching Goals Is Hard: Settling the Sample Complexity of the Stochastic Shortest Path Liyu Chen, Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric

Reconstructing Ultrametric Trees from Noisy Experiments Eshwar Ram Arunachaleswaran, Anindya De, Sampath Kannan

Robust Empirical Risk Minimization with Tolerance Robi Bhattacharjee, Max Hopkins, Akash Kumar, Hantao Yu, Kamalika Chaudhuri

Robust Estimation of Discrete Distributions Under Local Differential Privacy Julien Chhor, Flore Sentenac

Spatially Adaptive Online Prediction of Piecewise Regular Functions Sabyasachi Chatterjee, Subhajit Goswami

SQ Lower Bounds for Random Sparse Planted Vector Problem Jingqiu Ding, Yiding Hua

Testing Tail Weight of a Distribution via Hazard Rate Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld

The Replicator Dynamic, Chain Components and the Response Graph Oliver Biggar, Iman Shames

Tournaments, Johnson Graphs and NC-Teaching Hans U. Simon

Towards Empirical Process Theory for Vector-Valued Functions: Metric Entropy of Smooth Function Classes Junhyung Park, Krikamol Muandet

Universal Bias Reduction in Estimation of Smooth Additive Function in High Dimensions Fan Zhou, Ping Li, Cun-Hui Zhang

Variance-Reduced Conservative Policy Iteration Naman Agarwal, Brian Bullins, Karan Singh

Wide Stochastic Networks: Gaussian Limit and PAC-Bayesian Training Eugenio Clerico, George Deligiannidis, Arnaud Doucet