Algorithmic Learning Theory 2021: Preface

Vitaly Feldman, Katrina Ligett, Sivan Sabato; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1-2

[abs][Download PDF]

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

Jacob Abernethy, Kevin A. Lai, Andre Wibisono; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:3-47

[abs][Download PDF]

Differentially Private Assouad, Fano, and Le Cam

Jayadev Acharya, Ziteng Sun, Huanyu Zhang; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:48-78

[abs][Download PDF]

Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints

Jayadev Acharya, Peter Kairouz, Yuhan Liu, Ziteng Sun; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:79-98

[abs][Download PDF]

Efficient Algorithms for Stochastic Repeated Second-price Auctions

Juliette Achddou, Olivier Cappé, Aurélien Garivier; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:99-150

[abs][Download PDF]

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs

Raghavendra Addanki, Andrew McGregor, Cameron Musco; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:151-184

[abs][Download PDF]

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

Ishaq Aden-Ali, Hassan Ashtiani, Gautam Kamath; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:185-216

[abs][Download PDF]

Stochastic Dueling Bandits with Adversarial Corruption

Arpit Agarwal, Shivani Agarwal, Prathamesh Patil; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:217-248

[abs][Download PDF]

A Deep Conditioning Treatment of Neural Networks

Naman Agarwal, Pranjal Awasthi, Satyen Kale; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:249-305

[abs][Download PDF]

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

Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, Abhishek K. Umrawal; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:306-339

[abs][Download PDF]

Sequential prediction under log-loss with side information

Alankrita Bhatt, Young-Han Kim; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:340-344

[abs][Download PDF]

No-substitution k-means Clustering with Adversarial Order

Robi Bhattacharjee, Michal Moshkovitz; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:345-366

[abs][Download PDF]

Testing Product Distributions: A Closer Look

Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, N. V. Vinodchandran; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:367-396

[abs][Download PDF]

Online Boosting with Bandit Feedback

Nataly Brukhim, Elad Hazan; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:397-420

[abs][Download PDF]

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

Mark Cesar, Ryan Rogers; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:421-457

[abs][Download PDF]

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

Siu On Chan, Qinghua Ding, Sing Hei Li; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:458-480

[abs][Download PDF]

Learning a mixture of two subspaces over finite fields

Aidao Chen, Anindya De, Aravindan Vijayaraghavan; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:481-504

[abs][Download PDF]

Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

Thibaut Cuvelier, Richard Combes, Eric Gourdin; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:505-528

[abs][Download PDF]

An Efficient Algorithm for Cooperative Semi-Bandits

Riccardo Della Vecchia, Tommaso Cesari; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:529-552

[abs][Download PDF]

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

Le Cong Dinh, Tri-Dung Nguyen, Alain B. Zemhoho, Long Tran-Thanh; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:553-577

[abs][Download PDF]

Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, Michal Valko; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:578-598

[abs][Download PDF]

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

Ehsan Emamjomeh-Zadeh, Chen-Yu Wei, Haipeng Luo, David Kempe; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:599-618

[abs][Download PDF]

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

Louis Faury, Yoan Russac, Marc Abeille, Clément Calauzènes; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:619-626

[abs][Download PDF]

Subspace Embeddings under Nonlinear Transformations

Aarshvi Gajjar, Cameron Musco; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:656-672

[abs][Download PDF]

Efficient sampling from the Bingham distribution

Rong Ge, Holden Lee, Jianfeng Lu, Andrej Risteski; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:673-685

[abs][Download PDF]

Near-tight Closure Bounds for the Littlestone and Threshold Dimensions

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:686-696

[abs][Download PDF]

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

Steve Hanneke, Aryeh Kontorovich; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:697-721

[abs][Download PDF]

Submodular combinatorial information measures with applications in machine learning

Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, Himanshu Asanani; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:722-754

[abs][Download PDF]

Precise Minimax Regret for Logistic Regression with Categorical Feature Values

Philippe Jacquet, Gil Shamir, Wojciech Szpankowski; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:755-771

[abs][Download PDF]

Characterizing the implicit bias via a primal-dual analysis

Ziwei Ji, Matus Telgarsky; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:772-804

[abs][Download PDF]

Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback

Marc Jourdan, Mojmír Mutný, Johannes Kirschner, Andreas Krause; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:805-849

[abs][Download PDF]

Efficient Learning with Arbitrary Covariate Shift

Adam Tauman Kalai, Varun Kanade; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:850-864

[abs][Download PDF]

Adaptive Reward-Free Exploration

Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, Michal Valko; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:865-891

[abs][Download PDF]

Unexpected Effects of Online no-Substitution $k$-means Clustering

Michal Moshkovitz; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:892-930

[abs][Download PDF]

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

Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:931-962

[abs][Download PDF]

Uncertainty quantification using martingales for misspecified Gaussian processes

Willie Neiswanger, Aaditya Ramdas; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:963-982

[abs][Download PDF]

Learning with Comparison Feedback: Online Estimation of Sample Statistics

Michela Meister, Sloan Nietert; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:983-1001

[abs][Download PDF]

Online Learning of Facility Locations

Stephen Pasteris, Ting He, Fabio Vitale, Shiqiang Wang, Mark Herbster; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1002-1050

[abs][Download PDF]

Statistical guarantees for generative models without domination

Nicolas Schreuder, Victor-Emmanuel Brunel, Arnak Dalalyan; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1051-1071

[abs][Download PDF]

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

Jie Shen, Chicheng Zhang; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1072-1113

[abs][Download PDF]

Self-Tuning Bandits over Unknown Covariate-Shifts

Joseph Suk, Samory Kpotufe; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1114-1156

[abs][Download PDF]

Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

Jean Tarbouriech, Matteo Pirotta, Michal Valko, Alessandro Lazaric; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1157-1178

[abs][Download PDF]

Contrastive learning, multi-view redundancy, and linear models

Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1179-1206

[abs][Download PDF]

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

Di Wang, Huangyu Zhang, Marco Gaboardi, Jinhui Xu; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1207-1213

[abs][Download PDF]

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; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1214-1236

[abs][Download PDF]

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

Gellért Weisz, Philip Amortila, Csaba Szepesvári; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1237-1264

[abs][Download PDF]

Non-uniform Consistency of Online Learning with Random Sampling

Changlong Wu, Narayana Santhanam; Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1265-1285

[abs][Download PDF]