ML Anthology

ALT 2021

46 papers

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
PDF
A Deep Conditioning Treatment of Neural Networks Naman Agarwal, Pranjal Awasthi, Satyen Kale
PDF
A Technical Note on Non-Stationary Parametric Bandits: Existing Mistakes and Preliminary Solutions Louis Faury, Yoan Russac, Marc Abeille, Clément Calauzènes
PDF
Adaptive Reward-Free Exploration Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, Michal Valko
PDF
Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds Ehsan Emamjomeh-Zadeh, Chen-Yu Wei, Haipeng Luo, David Kempe
PDF
An Efficient Algorithm for Cooperative Semi-Bandits Riccardo Della Vecchia, Tommaso Cesari
PDF
Asymptotically Optimal Strategies for Combinatorial Semi-Bandits in Polynomial Time Thibaut Cuvelier, Richard Combes, Eric Gourdin
PDF
Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance Jie Shen, Chicheng Zhang
PDF
Bounding, Concentrating, and Truncating: Unifying Privacy Loss Composition for Data Analytics Mark Cesar, Ryan Rogers
PDF
Characterizing the Implicit Bias via a Primal-Dual Analysis Ziwei Ji, Matus Telgarsky
PDF
Contrastive Learning, Multi-View Redundancy, and Linear Models Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu
PDF
Descent-to-Delete: Gradient-Based Methods for Machine Unlearning Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi
PDF
Differentially Private Assouad, Fano, and Le Cam Jayadev Acharya, Ziteng Sun, Huanyu Zhang
PDF
Efficient Algorithms for Stochastic Repeated Second-Price Auctions Juliette Achddou, Olivier Cappé, Aurélien Garivier
PDF
Efficient Learning with Arbitrary Covariate Shift Adam Tauman Kalai, Varun Kanade
PDF
Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback Marc Jourdan, Mojmír Mutný, Johannes Kirschner, Andreas Krause
PDF
Efficient Sampling from the Bingham Distribution Rong Ge, Holden Lee, Jianfeng Lu, Andrej Risteski
PDF
Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, Michal Valko
PDF
Estimating Smooth GLM in Non-Interactive Local Differential Privacy Model with Public Unlabeled Data Di Wang, Huangyu Zhang, Marco Gaboardi, Jinhui Xu
PDF
Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints Jayadev Acharya, Peter Kairouz, Yuhan Liu, Ziteng Sun
PDF
Exponential Lower Bounds for Planning in MDPs with Linearly-Realizable Optimal Action-Value Functions Gellért Weisz, Philip Amortila, Csaba Szepesvári
PDF
Intervention Efficient Algorithms for Approximate Learning of Causal Graphs Raghavendra Addanki, Andrew McGregor, Cameron Musco
PDF
Last Round Convergence and No-Dynamic Regret in Asymmetric Repeated Games Le Cong Dinh, Tri-Dung Nguyen, Alain B. Zemhoho, Long Tran-Thanh
PDF
Last-Iterate Convergence Rates for Min-Max Optimization: Convergence of Hamiltonian Gradient Descent and Consensus Optimization Jacob Abernethy, Kevin A. Lai, Andre Wibisono
PDF
Learning a Mixture of Two Subspaces over Finite Fields Aidao Chen, Anindya De, Aravindan Vijayaraghavan
PDF
Learning and Testing Irreducible Markov Chains via the $k$-Cover Time Siu On Chan, Qinghua Ding, Sing Hei Li
PDF
Learning with Comparison Feedback: Online Estimation of Sample Statistics Michela Meister, Sloan Nietert
PDF
Near-Tight Closure Bounds for the Littlestone and Threshold Dimensions Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
PDF
No-Substitution K-Means Clustering with Adversarial Order Robi Bhattacharjee, Michal Moshkovitz
PDF
Non-Uniform Consistency of Online Learning with Random Sampling Changlong Wu, Narayana Santhanam
PDF
On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians Ishaq Aden-Ali, Hassan Ashtiani, Gautam Kamath
PDF
Online Boosting with Bandit Feedback Nataly Brukhim, Elad Hazan
PDF
Online Learning of Facility Locations Stephen Pasteris, Ting He, Fabio Vitale, Shiqiang Wang, Mark Herbster
PDF
Precise Minimax Regret for Logistic Regression with Categorical Feature Values Philippe Jacquet, Gil Shamir, Wojciech Szpankowski
PDF
Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model Jean Tarbouriech, Matteo Pirotta, Michal Valko, Alessandro Lazaric
PDF
Self-Tuning Bandits over Unknown Covariate-Shifts Joseph Suk, Samory Kpotufe
PDF
Sequential Prediction Under Log-Loss with Side Information Alankrita Bhatt, Young-Han Kim
PDF
Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound Steve Hanneke, Aryeh Kontorovich
PDF
Statistical Guarantees for Generative Models Without Domination Nicolas Schreuder, Victor-Emmanuel Brunel, Arnak Dalalyan
PDF
Stochastic Dueling Bandits with Adversarial Corruption Arpit Agarwal, Shivani Agarwal, Prathamesh Patil
PDF
Stochastic Top-$k$ Subset Bandits with Linear Space and Non-Linear Feedback Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, Abhishek K. Umrawal
PDF
Submodular Combinatorial Information Measures with Applications in Machine Learning Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, Himanshu Asanani
PDF
Subspace Embeddings Under Nonlinear Transformations Aarshvi Gajjar, Cameron Musco
PDF
Testing Product Distributions: A Closer Look Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, N. V. Vinodchandran
PDF
Uncertainty Quantification Using Martingales for Misspecified Gaussian Processes Willie Neiswanger, Aaditya Ramdas
PDF
Unexpected Effects of Online No-Substitution $k$-Means Clustering Michal Moshkovitz
PDF