ALT 2020

39 papers

Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies

Tom Zahavy, Avinatan Hasidim, Haim Kaplan, Yishay Mansour

Mixing Time Estimation in Ergodic Markov Chains from a Single Trajectory with Contraction Methods

Geoﬀrey Wolfer

Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling

Cindy Trinh, Emilie Kaufmann, Claire Vernade, Richard Combes

Online Non-Convex Learning: Following the Perturbed Leader is Optimal

Arun Sai Suggala, Praneeth Netrapalli

Approximate Representer Theorems in Non-reflexive Banach Spaces

Kevin Schlegel

Bandit Algorithms Based on Thompson Sampling for Bounded Reward Distributions

Charles Riou, Junya Honda

Top-k Combinatorial Bandits with Full-Bandit Feedback

Idan Rejwan, Yishay Mansour

Finding Robust Nash equilibria

Vianney Perchet

Efficient Private Algorithms for Learning Large-Margin Halfspaces

Huy Lê Nguyễn, Jonathan Ullman, Lydia Zakynthinou

Privately Answering Classification Queries in the Agnostic PAC Model

Anupama Nandi, Raef Bassily

A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields

Mikito Nanashima

On the Analysis of EM for truncated mixtures of two Gaussians

Sai Ganesh Nagarajan, Ioannis Panageas

Toward universal testing of dynamic network models

Abram Magner, Wojciech Szpankowski

Feedback graph regret bounds for Thompson Sampling and UCB

Thodoris Lykouris, Eva Tardos, Drishti Wali

On the Complexity of Proper Distribution-Free Learning of Linear Classifiers

Philip M. Long, Raphael J. Long

On Learning Causal Structures from Non-Experimental Data without Any Faithfulness Assumption

Hanti Lin, Jiji Zhang

Thompson Sampling for Adversarial Bit Prediction

Yuval Lewi, Haim Kaplan, Yishay Mansour

Robust guarantees for learning an autoregressive filter

Holden Lee, Cyril Zhang

Algebraic and Analytic Approaches for Parameter Learning in Mixture Models

Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal

Don’t Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop

Dmitry Kovalev, Samuel Horváth, Peter Richtarik

On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes

Kothari K. Pravesh, Livni Roi

The Nonstochastic Control Problem

Elad Hazan, Sham Kakade, Karan Singh

Exponentiated Gradient Meets Gradient Descent

Udaya Ghai, Elad Hazan, Yoram Singer

Adversarially Robust Learning Could Leverage Computational Hardness.

Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mahmoody Mohammad

An adaptive stochastic optimization algorithm for resource allocation

Xavier Fontaine, Shie Mannor, Vianney Perchet

Sampling Without Compromising Accuracy in Adaptive Data Analysis

Benjamin Fish, Lev Reyzin, Benjamin I. P. Rubinstein

Interactive Learning of a Dynamic Structure

Ehsan Emamjomeh-Zadeh, David Kempe, Mohammad Mahdian, Robert E. Schapire

Cautious Limit Learning

Vanja Doskoc, Timo Kötzing

Cooperative Online Learning: Keeping your Neighbors Updated

Nicolò Cesa-bianchi, Tommaso Cesari, Claire Monteleoni

First-Order Bayesian Regret Analysis of Thompson Sampling

Sébastien Bubeck, Mark Sellke

What relations are reliably embeddable in Euclidean space?

Robi Bhattacharjee, Sanjoy Dasgupta

Robust Algorithms for Online k-means Clustering

Aditya Bhaskara, Aravinda Kanchana Ruwanpathirana

Distribution Free Learning with Local Queries

Galit Bary-Weisberg, Amit Daniely, Shai Shalev-shwartz

A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates

Yossi Arjevani, Ohad Shamir, Nathan Srebro

Optimal $δ$-Correct Best-Arm Selection for Heavy-Tailed Distributions

Shubhada Agrawal, Sandeep Juneja, Peter Glynn

On Learnability wih Computable Learners

Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner

Leverage Score Sampling for Faster Accelerated Regression and ERM

Naman Agarwal, Sham Kakade, Rahul Kidambi, Yin-Tat Lee, Praneeth Netrapalli

Optimal multiclass overfitting by sequence reconstruction from Hamming queries

Jayadev Acharya, Ananda Theertha Suresh

Algorithmic Learning Theory 2020: Preface

Aryeh Kontorovich, Gergely Neu