ALT 2020

38 papers

A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields Mikito Nanashima

A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates Yossi Arjevani, Ohad Shamir, Nathan Srebro

Adversarially Robust Learning Could Leverage Computational Hardness. Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mahmoody Mohammad

Algebraic and Analytic Approaches for Parameter Learning in Mixture Models Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal

An Adaptive Stochastic Optimization Algorithm for Resource Allocation Xavier Fontaine, Shie Mannor, Vianney Perchet

Approximate Representer Theorems in Non-Reflexive Banach Spaces Kevin Schlegel

Bandit Algorithms Based on Thompson Sampling for Bounded Reward Distributions Charles Riou, Junya Honda

Cautious Limit Learning Vanja Doskoč, Timo Kötzing

Cooperative Online Learning: Keeping Your Neighbors Updated Nicolò Cesa-Bianchi, Tommaso Cesari, Claire Monteleoni

Distribution Free Learning with Local Queries Galit Bary-Weisberg, Amit Daniely, Shai Shalev-Shwartz

Don’t Jump Through Hoops and Remove Those Loops: SVRG and Katyusha Are Better Without the Outer Loop Dmitry Kovalev, Samuel Horváth, Peter Richtárik

Efficient Private Algorithms for Learning Large-Margin Halfspaces Huy Lê Nguyễn, Jonathan Ullman, Lydia Zakynthinou

Exponentiated Gradient Meets Gradient Descent Udaya Ghai, Elad Hazan, Yoram Singer

Feedback Graph Regret Bounds for Thompson Sampling and UCB Thodoris Lykouris, Éva Tardos, Drishti Wali

Finding Robust Nash Equilibria Vianney Perchet

First-Order Bayesian Regret Analysis of Thompson Sampling Sébastien Bubeck, Mark Sellke

Interactive Learning of a Dynamic Structure Ehsan Emamjomeh-Zadeh, David Kempe, Mohammad Mahdian, Robert E. Schapire

Leverage Score Sampling for Faster Accelerated Regression and ERM Naman Agarwal, Sham Kakade, Rahul Kidambi, Yin-Tat Lee, Praneeth Netrapalli, Aaron Sidford

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

On Learnability Wih Computable Learners Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner

On Learning Causal Structures from Non-Experimental Data Without Any Faithfulness Assumption Hanti Lin, Jiji Zhang

On the Analysis of EM for Truncated Mixtures of Two Gaussians Sai Ganesh Nagarajan, Ioannis Panageas

On the Complexity of Proper Distribution-Free Learning of Linear Classifiers Philip M. Long, Raphael J. Long

On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes Kothari K. Pravesh, Livni Roi

Online Non-Convex Learning: Following the Perturbed Leader Is Optimal Arun Sai Suggala, Praneeth Netrapalli

Optimal $δ$-Correct Best-Arm Selection for Heavy-Tailed Distributions Shubhada Agrawal, Sandeep Juneja, Peter Glynn

Optimal Multiclass Overfitting by Sequence Reconstruction from Hamming Queries Jayadev Acharya, Ananda Theertha Suresh

Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies Tom Zahavy, Avinatan Hasidim, Haim Kaplan, Yishay Mansour

Privately Answering Classification Queries in the Agnostic PAC Model Anupama Nandi, Raef Bassily

Robust Algorithms for Online $k$-Means Clustering Aditya Bhaskara, Aravinda Kanchana Ruwanpathirana

Robust Guarantees for Learning an Autoregressive Filter Holden Lee, Cyril Zhang

Sampling Without Compromising Accuracy in Adaptive Data Analysis Benjamin Fish, Lev Reyzin, Benjamin I. P. Rubinstein

Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling Cindy Trinh, Emilie Kaufmann, Claire Vernade, Richard Combes

The Nonstochastic Control Problem Elad Hazan, Sham Kakade, Karan Singh

Thompson Sampling for Adversarial Bit Prediction Yuval Lewi, Haim Kaplan, Yishay Mansour

Top-$k$ Combinatorial Bandits with Full-Bandit Feedback Idan Rejwan, Yishay Mansour

Toward Universal Testing of Dynamic Network Models Abram Magner, Wojciech Szpankowski

What Relations Are Reliably Embeddable in Euclidean Space? Robi Bhattacharjee, Sanjoy Dasgupta