Papers
Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
Prateek Jain, Sewoong Oh
Online Linear Optimization via Smoothing
Jacob Abernethy, Chansoo Lee, Abhinav Sinha et al.
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Sanjeev Arora, Rong Ge, Ankur Moitra
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
Robust Multi-objective Learning with Mentor Feedback
Alekh Agarwal, Ashwinkumar Badanidiyuru, Miroslav Dudík et al.
Computational Limits for Matrix Completion
Moritz Hardt, Raghu Meka, Prasad Raghavendra et al.
Learning Coverage Functions and Private Release of Marginals
Vitaly Feldman, Pravesh Kothari
Fast matrix completion without the condition number
Moritz Hardt, Mary Wootters
Most Correlated Arms Identification
Che-Yu Liu, Sébastien Bubeck
Efficiency of conformalized ridge regression
Evgeny Burnaev, Vladimir Vovk
A Convex Formulation for Mixed Regression with Two Components: Minimax Optimal Rates
Yudong Chen, Xinyang Yi, Constantine Caramanis
Density-preserving quantization with application to graph downsampling
Morteza Alamgir, Gábor Lugosi, Ulrike Luxburg
The sample complexity of agnostic learning under deterministic labels
Shai Ben-David, Ruth Urner
Elicitation and Identification of Properties
Ingo Steinwart, Chloé Pasin, Robert Williamson et al.
On the Complexity of A/B Testing
Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning
Andreas Maurer, Massimiliano Pontil, Bernardino Romera-Paredes
lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
Kevin Jamieson, Matthew Malloy, Robert Nowak et al.
Volumetric Spanners: an Efficient Exploration Basis for Learning
Elad Hazan, Zohar Karnin, Raghu Meka
Finding a most biased coin with fewest flips
Karthekeyan Chandrasekaran, Richard Karp
Sample Compression for Multi-label Concept Classes
Rahim Samei, Pavel Semukhin, Boting Yang et al.
Belief propagation, robust reconstruction and optimal recovery of block models
Elchanan Mossel, Joe Neeman, Allan Sly
Approachability in unknown games: Online learning meets multi-objective optimization
Shie Mannor, Vianney Perchet, Gilles Stoltz
Stochastic Regret Minimization via Thompson Sampling
Sudipto Guha, Kamesh Munagala
Optimal learners for multiclass problems
Amit Daniely, Shai Shalev-Shwartz
The Complexity of Learning Halfspaces using Generalized Linear Methods
Amit Daniely, Nati Linial, Shai Shalev-Shwartz