ALT 2021

47 papers

Non-uniform Consistency of Online Learning with Random Sampling

Changlong Wu, Narayana Santhanam

Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions

Gellert Weisz, Philip Amortila, Csaba Szepesvári

A case where a spindly two-layer linear network decisively outperforms any neural network with a fully connected input layer

Manfred K. Warmuth, Wojciech Kotłowski, Ehsan Amid

Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data

Di Wang, Huangyu Zhang, Marco Gaboardi, Jinhui Xu

Contrastive learning, multi-view redundancy, and linear models

Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu

Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

Jean Tarbouriech, Matteo Pirotta, Michal Valko, Alessandro Lazaric

Self-Tuning Bandits over Unknown Covariate-Shifts

Joseph Suk, Samory Kpotufe

Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance

Jie Shen, Chicheng Zhang

Statistical guarantees for generative models without domination

Nicolas Schreuder, Victor-Emmanuel Brunel, Arnak Dalalyan

Online Learning of Facility Locations

Stephen Pasteris, Ting He, Fabio Vitale, Shiqiang Wang, Mark Herbster

Learning with Comparison Feedback: Online Estimation of Sample Statistics

Michela Meister, Sloan Nietert

Uncertainty quantification using martingales for misspecified Gaussian processes

Willie Neiswanger, Aaditya Ramdas

Descent-to-Delete: Gradient-Based Methods for Machine Unlearning

Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi

Unexpected Effects of Online no-Substitution k-means Clustering

Michal Moshkovitz

Adaptive Reward-Free Exploration

Emilie Kaufmann, Pierre Menard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent

Efficient Learning with Arbitrary Covariate Shift

Adam Tauman Kalai, Varun Kanade

Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback

Marc Jourdan, Mojmir Mutny, Johannes Kirschner, Andreas Krause

Characterizing the implicit bias via a primal-dual analysis

Ziwei Ji, Matus Telgarsky

Precise Minimax Regret for Logistic Regression with Categorical Feature Values

Philippe Jacquet, Gil Shamir, Wojciech Szpankowski

Submodular combinatorial information measures with applications in machine learning

Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, Himanshu Asanani

Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound

Steve Hanneke, Aryeh Kontorovich

Near-tight Closure Bounds for the Littlestone and Threshold Dimensions

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi

Efficient sampling from the Bingham distribution

Rong Ge, Holden Lee, Jianfeng Lu, Andrej Risteski

Subspace Embeddings under Nonlinear Transformations

Aarshvi Gajjar, Cameron Musco

A Technical Note on Non-Stationary Parametric Bandits: Existing Mistakes and Preliminary Solutions

Louis Faury, Yoan Russac, Marc Abeille, Clément Calauzènes

Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds

Ehsan Emamjomeh-Zadeh, Chen-Yu Wei, Haipeng Luo, David Kempe

Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

Omar Darwiche Domingues, Pierre Menard, Emilie Kaufmann, Michal Valko

Last Round Convergence and No-Dynamic Regret in Asymmetric Repeated Games

Le Cong Dinh, Tri-Dung Nguyen, Alain B. Zemhoho, Long Tran-Thanh

An Efficient Algorithm for Cooperative Semi-Bandits

Riccardo Della Vecchia, Tommaso Cesari

Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

Thibaut Cuvelier, Richard Combes, Eric Gourdin

Learning a mixture of two subspaces over finite fields

Aidao Chen, Anindya De, Aravindan Vijayaraghavan

Learning and Testing Irreducible Markov Chains via the k-Cover Time

Siu On Chan, Qinghua Ding, Sing Hei Li

Bounding, Concentrating, and Truncating: Unifying Privacy Loss Composition for Data Analytics

Mark Cesar, Ryan Rogers

Online Boosting with Bandit Feedback

Nataly Brukhim, Elad Hazan

Testing Product Distributions: A Closer Look

Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, N. V. Vinodchandran

No-substitution k-means Clustering with Adversarial Order

Robi Bhattacharjee, Michal Moshkovitz

Sequential prediction under log-loss with side information

Alankrita Bhatt, Young-Han Kim

Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback

Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, Abhishek K. Umrawal

A Deep Conditioning Treatment of Neural Networks

Naman Agarwal, Pranjal Awasthi, Satyen Kale

Stochastic Dueling Bandits with Adversarial Corruption

Arpit Agarwal, Shivani Agarwal, Prathamesh Patil

On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians

Ishaq Aden-Ali, Hassan Ashtiani, Gautam Kamath

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs

Raghavendra Addanki, Andrew McGregor, Cameron Musco

Efficient Algorithms for Stochastic Repeated Second-price Auctions

Juliette Achddou, Olivier Cappe, Aurélien Garivier

Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints

Jayadev Acharya, Peter Kairouz, Yuhan Liu, Ziteng Sun

Differentially Private Assouad, Fano, and Le Cam

Jayadev Acharya, Ziteng Sun, Huanyu Zhang

Last-Iterate Convergence Rates for Min-Max Optimization: Convergence of Hamiltonian Gradient Descent and Consensus Optimization

Jacob Abernethy, Kevin A. Lai, Andre Wibisono

Algorithmic Learning Theory 2021: Preface

Vitaly Feldman, Katrina Ligett, Sivan Sabato