Papers
Online learning over a finite action set with limited switching
Jason Altschuler, Kunal Talwar
A Direct Sum Result for the Information Complexity of Learning
Ido Nachum, Jonathan Shafer, Amir Yehudayoff
A Data Prism: Semi-verified learning in the small-alpha regime
Michela Meister, Gregory Valiant
Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
Ashok Cutkosky, Francesco Orabona
Adaptivity to Smoothness in X-armed bandits
Andrea Locatelli, Alexandra Carpentier
An Analysis of the t-SNE Algorithm for Data Visualization
Sanjeev Arora, Wei Hu, Pravesh K. Kothari
Fundamental Limits of Weak Recovery with Applications to Phase Retrieval
Marco Mondelli, Andrea Montanari
Action-Constrained Markov Decision Processes With Kullback-Leibler Cost
Ana Bušić, Sean Meyn
Efficient Algorithms for Outlier-Robust Regression
Adam Klivans, Pravesh K. Kothari, Raghu Meka
The Vertex Sample Complexity of Free Energy is Polynomial
Vishesh Jain, Frederic Koehler, Elchanan Mossel
Non-Convex Matrix Completion Against a Semi-Random Adversary
Yu Cheng, Rong Ge
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
Vishesh Jain, Frederic Koehler, Elchanan Mossel
An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization
Tim Roughgarden, Joshua R. Wang
A General Approach to Multi-Armed Bandits Under Risk Criteria
Asaf Cassel, Shie Mannor, Assaf Zeevi
Efficient Convex Optimization with Membership Oracles
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
More Adaptive Algorithms for Adversarial Bandits
Chen-Yu Wei, Haipeng Luo
Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos et al.
Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
Gal Dalal, Gugan Thoppe, Balázs Szörényi et al.
Detecting Correlations with Little Memory and Communication
Yuval Dagan, Ohad Shamir
Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
Yuanzhi Li, Yingyu Liang
Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing
Oren Mangoubi, Nisheeth K. Vishnoi
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
Chi Jin, Praneeth Netrapalli, Michael I. Jordan
Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression
Shiva Prasad Kasiviswanathan, Mark Rudelson