Towards Minimax Policies for Online Linear Optimization with Bandit Feedback
- Sébastien Bubeck, Nicolo Cesa-Bianchi and Sham M. Kakade
Consistency of nearest neighbor classification under selective sampling
- Sanjoy Dasgupta
(weak) Calibration is Computationally Hard
- Elad Hazan and Sham Kakade
Near-Optimal Algorithms for Online Matrix Prediction
- Elad Hazan, Satyen Kale and Shai Shalev-Shwartz
PAC-Bayesian Bound for Gaussian Process Regression and Multiple Kernel Additive Model
- Taiji Suzuki
A Conjugate Property between Loss Functions and Uncertainty Sets in Classification Problems
- Takafumi Kanamori, Akiko Takeda and Taiji Suzuki
Rare Probability Estimation under Regularly Varying Heavy Tails
- Mesrob Ohannessian and Munther Dahleh
Random Design Analysis of Ridge Regression
- Daniel Hsu, Sham Kakade and Tong Zhang
Reconstruction from anisotropic random measurements
- Mark Rudelson and Shuheng Zhou
$L_1$ Covering Numbers for Uniformly Bounded Convex Functions
- Adityanand Guntuboyina and Bodhisattva Sen
Toward a noncommutative arithmetic-geometric mean inequality
- Benjamin Recht and Christopher Re
Unsupervised SVMs
- Omri Weinstein, Edo Liberty, Shachar Lovett, Roy Schwartz and Zohar Karnin
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions
- Rocco Servedio, Li-Yang Tan and Justin Thaler
Distance Preserving Embeddings for General n-Dimensional Manifolds
- Nakul Verma
A Method of Moments for Hidden Markov Models and Multi-view Mixture Models
- Animashree Anandkumar, Daniel Hsu and Sham Kakade
Computational Bounds on Statistical Query Learning
- Vitaly Feldman and Varun Kanade
Autonomous Exploration For Navigating In MDPs
- Shiau Hong Lim and Peter Auer
The Optimality of Jeffreys Prior for Online Density Estimation and the Asymptotic Normality of Maximum Likelihood Estimators
- Fares Hedayati and Peter Bartlett
Toward understanding complex spaces
- Mikhail Belkin, Qichao Que, Yusu Wang and Xueyuan Zhou
Kernels based tests with non-asymptotic bootstrap approaches for two-sample problems
- Magalie Fromont, Béatrice Laurent, Matthieu Lerasle and Patricia Reynaud-Bouret
Differentially Private Online Learning
- Prateek Jain, Pravesh Kothari and Abhradeep Thakurta
Active Learning Using Smooth Relative Regret Approximations with Applications
- Nir Ailon, Ron Begleiter and Esther Ezra
The best of both worlds: stochastic and adversarial bandits
- Sébastien Bubeck and Aleksandrs Slivkins
New Bounds for Learning Intervals with Implications for Semi-Supervised Learning
- David Helmbold and Philip Long
Distributed Learning, Communication Complexity and Privacy
- Maria-Florina Balcan, Avrim Blum, Shai Fine and Yishay Mansour
Divergences and Risks for Multiclass Experiments
- Dario Garcia Garcia and Robert C. Williamson
Tight Bounds on Proper Equivalence Query Learning of DNF
- Lisa Hellerstein, Devorah Kletenik, Linda Sellie and Rocco Servedio
Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions
- Yuyang Wang, Roni Khardon, Dmitry Pechyony and Rosie Jones
Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model
- Kamalika Chaudhuri, Fan Chung and Alexander Tsiatas
Exact Recovery of Sparsely-Used Dictionaries
- Daniel Spielman, Huan Wang and John Wright
Learning of DNF Expressions from Fourier Spectrum
- Vitaly Feldman
Analysis of Thompson Sampling for the multi-armed bandit problem
- Shipra Agrawal and Navin Goyal
Learning Valuation Functions
- Maria-Florina Balcan, Florin Constantin, Satoru Iwata and Lei Wang
A Correlation Clustering Approach to Link Classification in Signed Networks
- Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale and Giovanni Zappella
Differentially Private Convex Optimization for Empirical Risk Minimization with Applications to High-dimensional Regression
- Daniel Kifer, Adam Smith and Abhradeep Thakurta
Competitive Classification and Closeness Testing
- Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan and Ananda Theertha Suresh
A Characterization of Scoring Rules for Linear Properties
- Rafael Frongillo and Jacob Abernethy
Unified Algorithms for Online Learning and Competitive Analysis
- Niv Buchbinder, Shahar Chen, Joseph Naor and Ohad Shamir
Robust Interactive Learning
- Maria-Florina Balcan and Steve Hanneke
Learning Functions of Halfspaces using Prefix Covers
- Parikshit Gopalan, Adam Klivans and Raghu Meka
Online Optimization with Gradual Variations
- Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin and Shenghuo Zhu