ALT 2022

43 papers

Efficient local planning with linear function approximation

Dong Yin, Botao Hao, Yasin Abbasi-Yadkori, Nevena Lazic, Csaba Szepesvári

Faster Noisy Power Method

Zhiqiang Xu, Ping Li

TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions

Gellert Weisz, Csaba Szepesvári, András György

A Model Selection Approach for Corruption Robust Reinforcement Learning

Chen-Yu Wei, Christoph Dann, Julian Zimmert

Distributed Online Learning for Joint Regret with Communication Constraints

Dirk van der Hoeven, Hedi Hadiji, Tim van Erven

Faster Rates of Private Stochastic Convex Optimization

Jinyan Su, Lijie Hu, Di Wang

Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability

Aadirupa Saha, Akshay Krishnamurthy

Asymptotic Degradation of Linear Regression Estimates with Strategic Data Sources

Benjamin Roussillon, Nicolas Gast, Patrick Loiseau, Panayotis Mertikopoulos

Scale-Free Adversarial Multi Armed Bandits

Sudeep Raja Putta, Shipra Agrawal

Infinitely Divisible Noise in the Low Privacy Regime

Rasmus Pagh, Nina Mesing Stausholm

Inductive Bias of Gradient Descent for Weight Normalized Smooth Homogeneous Neural Nets

Depen Morwani, Harish G. Ramaswamy

Global Riemannian Acceleration in Hyperbolic and Spherical Spaces

David Martínez-Rubio

On the Initialization for Convex-Concave Min-max Problems

Mingrui Liu, Francesco Orabona

The Mirror Langevin Algorithm Converges with Vanishing Bias

Ruilin Li, Molei Tao, Santosh S. Vempala, Andre Wibisono

On the Last Iterate Convergence of Momentum Methods

Xiaoyu Li, Mingrui Liu, Francesco Orabona

Improved rates for prediction and identification of partially observed linear dynamical systems

Holden Lee

Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally

Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang

Minimization by Incremental Stochastic Surrogate Optimization for Large Scale Nonconvex Problems

Belhal Karimi, Hoi-To Wai, Eric Moulines, Ping Li

Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure

Hsu Kao, Chen-Yu Wei, Vijay Subramanian

Adversarial Interpretation of Bayesian Inference

Hisham Husain, Jeremias Knoblauch

Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability

Lunjia Hu, Charlotte Peale, Omer Reingold

Distinguishing Relational Pattern Languages With a Small Number of Short Strings

Robert C. Holte, S. Mahmoud Mousawi, Sandra Zilles

Universally Consistent Online Learning with Arbitrarily Dependent Responses

Steve Hanneke

Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems

Benjamin Grimmer, Haihao Lu, Pratik Worah, Vahab Mirrokni

Efficient and Optimal Fixed-Time Regret with Two Experts

Laura Greenstreet, Nicholas J. A. Harvey, Victor Sanches Portella

Multicalibrated Partitions for Importance Weights

Parikshit Gopalan, Omer Reingold, Vatsal Sharan, Udi Wieder

Privacy Amplification via Shuffling for Linear Contextual Bandits

Evrard Garcelon, Kamalika Chaudhuri, Vianney Perchet, Matteo Pirotta

Beyond Bernoulli: Generating Random Outcomes that cannot be Distinguished from Nature

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona

Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians

Sami Davies, Arya Mazumdar, Soumyabrata Pal, Cyrus Rashtchian

Leveraging Initial Hints for Free in Stochastic Linear Bandits

Ashok Cutkosky, Chris Dann, Abhimanyu Das, Qiuyi Zhang

Refined Lower Bounds for Nearest Neighbor Condensation

Rajesh Chitnis

Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games

Zixiang Chen, Dongruo Zhou, Quanquan Gu

Algorithms for learning a mixture of linear classifiers

Aidao Chen, Anindya De, Aravindan Vijayaraghavan

Faster Perturbed Stochastic Gradient Methods for Finding Local Minima

Zixiang Chen, Dongruo Zhou, Quanquan Gu

Implicit Parameter-free Online Learning with Truncated Linear Models

Keyi Chen, Ashok Cutkosky, Francesco Orabona

Iterated Vector Fields and Conservatism, with Applications to Federated Learning

Zachary Charles, Keith Rush

Social Learning in Non-Stationary Environments

Etienne Boursier, Vianney Perchet, Marco Scarsini

Universal Online Learning with Unbounded Losses: Memory Is All You Need

Moise Blanchard, Romain Cosson, Steve Hanneke

Learning with Distributional Inverters

Eric Binnendyk, Marco Carmosino, Antonina Kolokolova, R Ramyaa, Manuel Sabin

Learning what to remember

Robi Bhattacharjee, Gaurav Mahajan

Understanding Simultaneous Train and Test Robustness

Pranjal Awasthi, Sivaraman Balakrishnan, Aravindan Vijayaraghavan

Efficient Methods for Online Multiclass Logistic Regression

Naman Agarwal, Satyen Kale, Julian Zimmert

Algorithmic Learning Theory 2022: Preface

Sanjoy Dasgupta, Nika Haghtalab