Accepted papers

Download accepted papers here

Online Learning (I)

Session Chair: Sébastien Bubeck

Long talks (20 minutes + 5 minutes for questions)

  1. Oren Anava, Elad Hazan, Shie Mannor and Ohad Shamir.
    Online Learning for Time Series Prediction
  2. Lachlan Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman and Adam Wierman.
    A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret
  3. Wei Han, Alexander Rakhlin and Karthik Sridharan.
    Competing With Strategies

Short talks (5 minutes)

  1. Alexander Rakhlin and Karthik Sridharan.
    Online Learning with Predictable Sequences
  2. Shie Mannor and Vianney Perchet.
    Approachability, fast and slow
  3. Peter Bartlett, Peter Grunwald, Peter Harremoes, Fares Hedayati and Wojciech Kotlowski.
    Horizon-Independent Optimal Prediction with Log-Loss in Exponential Families

Online Learning (II)

Session Chair: Sasha Rakhlin

Long talks (20 minutes + 5 minutes for questions)

  1. Andrey Bernstein, Shie Mannor and Nahum Shimkin.
    Opportunistic Strategies for Generalized No-Regret Problems
  2. Luc Devroye, Gábor Lugosi and Gergely Neu.
    Prediction by random-walk perturbation
  3. Eyal Gofer, Nicolò Cesa-Bianchi, Claudio Gentile and Yishay Mansour.
    Regret Minimization for Branching Experts
  4. Claudio Gentile, Mark Herbster and Stephen Pasteris.
    Online Similarity Prediction of Networked Data from Known and Unknown Graphs


Session Chair: Nicolo Cesa-Bianchi

Long talks (20 minutes + 5 minutes for questions)

  1. Ohad Shamir.
    On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
  2. Amit Daniely and Tom Halbertal.
    The price of bandit information in multiclass online classification
  3. Sébastien Bubeck, Vianney Perchet and Philippe Rigollet.
    Bounded regret in stochastic multi-armed bandits
  4. Chao-Kai Chiang, Chia-Jung Lee and Chi-Jen Lu.
    Beating Bandits in Gradually Evolving Worlds

Short talks (5 minutes)

  1. Emilie Kaufmann and Shivaram Kalyanakrishnan.
    Information Complexity in Bandit Subset Selection
  2. Gabor Bartok
    A near-optimal algorithm for finite partial-monitoring games against adversarial opponents
  3. Ittai Abraham, Omar Alonso, Vasilis Kandylas and Aleksandrs Slivkins.
    Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem

Computational learning theory (I)

Session Chair: Vitaly Feldman

Long talks (20 minutes + 5 minutes for questions)

  1. Quentin Berthet and Philippe Rigollet.
    Complexity Theoretic Lower Bounds for Sparse Principal Component Detection (best paper)
  2. Daniel Kane, Adam Klivans and Raghu Meka.
    Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching

Computational learning theory (II)

Session Chair: Elad Hazan

Long talks (20 minutes + 5 minutes for questions)

  1. Vitaly Feldman, Pravesh Kothari and Jan Vondrak.
    Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
  2. Sung-Soon Choi.
    Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights
  3. Moritz Hardt and Ankur Moitra.
    Algorithms and Hardness for Robust Subspace Recovery
  4. Lijun Zhang, Mehrdad Mahdavi, Rong Jin, Tianbao Yang and Shenghuo Zhu.
    Recovering Optimal Solution by Dual Random Projection

Computational learning theory (III)

Session Chair: Daniel Hsu

Long talks (20 minutes + 5 minutes for questions)

  1. Joseph Anderson, Navin Goyal and Luis Rademacher.
    Efficient Learning of Simplices
  2. Sanjoy Dasgupta and Kaushik Sinha.
    Randomized partition trees for exact nearest neighbor search

Statistical learning theory (I)

Session Chair: Philippe Rigollet

Long talks (20 minutes + 5 minutes for questions)

  1. Mehrdad Mahdavi and Rong Jin.
    Passive Learning with Target Risk
  2. Clayton Scott, Gilles Blanchard and Gregory Handy.
    Classification with Asymmetric Label Noise: Consistency and Maximal Denoising
  3. Yuchen Zhang, John Duchi and Martin Wainwright.
    Divide and Conquer Kernel Ridge Regression

Short talks (5 minutes)

  1. Francis Bach.
    Sharp analysis of low-rank kernel matrix approximations
  2. Robert Vandermeulen and Clayton Scott.
    Consistency of Robust Kernel Density Estimators
  3. Andreas Maurer and Massimiliano Pontil.
    Excess risk bounds for multitask learning with trace norm regularization
  4. Cheng Li, Wenxin Jiang and Martin Tanner.
    General Oracle Inequalities for Gibbs Posterior with Application to Classification and Ranking
  5. Matus Telgarsky.
    Boosting with the Logistic Loss is Consistent

Statistical learning theory (II)

Session Chair: Manfred Warmuth

Long talks (20 minutes + 5 minutes for questions)

  1. Roi Livni and Pierre Simon.
    Honest Compressions and Their Application to Compression Schemes (Mark Fulk award)
  2. Abhradeep Guha Thakurta and Adam Smith.
    Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso

Active learning

Session Chair: Sanjoy Dasgupta

Long talks (20 minutes + 5 minutes for questions)

  1. Pranjal Awasthi, Vitaly Feldman and Varun Kanade.
    Learning Using Local Membership Queries (best student paper)
  2. Ruth Urner, Sharon Wulff and Shai Ben-David.
    PLAL: Cluster-based active learning
  3. Stanislav Minsker.
    Estimation of Extreme Values and Associated Level Sets of a Regression Function via Selective Sampling
  4. Maria-Florina Balcan and Phil Long.
    Active and passive learning of linear separators under log-concave distributions

Dimensionality reduction and loss functions

Session Chair: Rob Schapire

Long talks (20 minutes + 5 minutes for questions)

  1. David Woodruff and Qin Zhang.
    Subspace Embeddings and $\ell_p$-Regression Using Exponential Random Variables
  2. Shivani Agarwal.
    Surrogate Regret Bounds for the Area Under the ROC Curve via Strongly Proper Losses

Short talk (5 minutes)

  1. Yining Wang, Liwei Wang, Yuanzhi Li, Di He and Tie-Yan Liu.
    A Theoretical Analysis of NDCG Type Ranking Measures

Unsupervised learning

Session Chair: Shai Ben-David

Long talks (20 minutes + 5 minutes for questions)

  1. Animashree Anandkumar, Rong Ge, Daniel Hsu and Sham Kakade.
    A Tensor Spectral Approach to Learning Mixed Membership Community Models
  2. Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky and Ananda Theertha Suresh.
    Optimal Probability Estimation with Applications to Prediction and Classification
  3. Mikhail Belkin, Luis Rademacher and James Voss.
    Blind Signal Separation in the Presence of Gaussian Noise

Short talks (5 minutes)

  1. Wouter M. Koolen, Nie Jiazhong and Manfred Warmuth.
    Learning a set of directions
  2. Marcus Hutter.
    Sparse Adaptive Dirichlet-Like Process Redundancy Bounds