Accepted Papers

The proceedings of COLT 2016 are available on the Proceedings of Machine Learning Research (PMLR)

  • Tor Lattimore. Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
  • Ronen Eldan and Ohad Shamir. The Power of Depth for Feedforward Neural Networks
  • Nadav Cohen, Or Sharir and Amnon Shashua. On the Expressive Power of Deep Learning: A Tensor Analysis
  • Jason Lee, Max Simchowitz, Benjamin Recht and Michael Jordan. Gradient Descent only Converges to Minimizers
  • Pierre C. Bellec. Aggregation of supports along the Lasso path
  • Dean Foster, Satyen Kale and Howard Karloff. Online Sparse Linear Regression
  • Siu On Chan, Dimitris Papailliopoulos and Aviad Rubinstein. On the Approximability of Sparse PCA
  • Ilias Diakonikolas, Daniel Kane and Alistair Stewart. Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
  • Aurélien Garivier and Emilie Kaufmann. Optimal Best Arm Identification with Fixed Confidence
  • Konstantin Makarychev, Yury Makarychev and Aravindan Vijayaraghavan. Learning Communities in the Presence of Errors
  • Shay Moran, Noga Alon and Amir Yehudayoff. Sign rank versus VC dimension
  • Sébastien Bubeck and Ronen Eldan. Multi-scale exploration of convex functions and bandit convex optimization
  • Maria-Florina Balcan, Simon Du, Yining Wang and Adams Wei Yu. An Improved Gap-Dependency Analysis of the Noisy Power Method
  • Nicolo’ Cesa-Bianchi, Claudio Gentile, Yishay Mansour and Alberto Minora. Delay and Cooperation in Nonstochastic Bandits
  • Ilias Diakonikolas, Daniel Kane and Alistair Stewart. Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
  • Chicheng Zhang and Kamalika Chaudhuri. The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions
  • Alexandra Carpentier and Andrea Locatelli. Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
  • Jonathan Weed, Vianney Perchet and Philippe Rigollet. Online learning in repeated auctions
  • Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning DNF’s
  • Jacob Steinhardt, Stefan Wager and Gregory Valiant. Memory, Communication, and Statistical Queries
  • Sivan Sabato and Tom Hess. Interactive Algorithms: from Pool to Stream
  • Max Simchowitz, Kevin Jamieson and Ben Recht. Best-of-K Bandits
  • Mikhail Belkin, Luis Rademacher and James Voss. Basis Learning as an Algorithmic Primitive
  • Kuang Xu and Laurent Massoulie. On the capacity of information processing systems
  • Boaz Barak and Ankur Moitra. Noisy Tensor Completion via the Sum-of-Squares Hierarchy
  • Matus Telgarsky. Benefits of depth in neural networks
  • Shipra Agrawal, Nikhil R. Devanur and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
  • Andrew Cotter, Maya Gupta and Jan Pfeifer. A Light Touch for Heavily Constrained SGD
  • Srinadh Bhojanapalli, Anastasios Kyrillidis and Sujay Sanghavi. Dropping Convexity for Faster Semi-definite Optimization
  • Wojciech Kotlowski, Wouter M. Koolen and Alan Malek. Online Isotonic Regression
  • Aurélien Garivier, Emilie Kaufmann and Wouter M. Koolen. Maximin Action Identification: A New Bandit Framework for Games
  • Ilya Volkovich. A Guide to Learning Arithmetic Circuits
  • Jamie Morgenstern and Tim Roughgarden. Learning Simple Auctions
  • Elad Hazan, Tomer Koren, Roi Livni and Yishay Mansour. Online Learning with Low Rank Experts
  • Jess Banks, Cristopher Moore, Joe Neeman and Praneeth Netrapalli. Information-theoretic thresholds for community detection in sparse networks
  • Animashree Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization
  • Janos Flesch, Rida Laraki and Vianney Perchet. Online Learning and Blackwell Approachability in Quitting Games
  • Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli and Aaron Sidford. Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja’s Algorithm
  • Ziyuan Gao, Christoph Ries, Hans Simon and Sandra Zilles. Preference-based Teaching
  • Nima Anari, Shayan Oveis Gharan and Alireza Rezaei. Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
  • Bernardo Avila Pires and Csaba Szepesvari. Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
  • Christos Papadimitriou, Samantha Petti and Santosh Vempala. Cortical Computation via Iterative Constructions
  • Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin Wainwright and Michael Jordan. Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
  • Akshay Balsubramani, Zohar Karnin, Robert Schapire and Masrour Zoghi. Instance-dependent Regret Bounds for Dueling Bandits
  • Paul Christiano. Provably manipulation-resistant reputation systems
  • Francis Bach and Vianney Perchet. Highly-Smooth Zero-th Order Online Optimization
  • Laura Florescu and Will Perkins. Spectral thresholds in the bipartite stochastic block model
  • Rachel Cummings, Katrina Ligett, Zhiwei Steven Wu, Aaron Roth and Kobbi Nissim. Adaptive Learning with Robust Generalization Guarantees
  • Lijie Chen, Anupam Gupta and Jian Li. Pure Exploration of Multi-armed Bandit Under Matroid Constraints
  • Pranjal Awasthi, Maria Florina Balcan, Nika Haghtalab and Hongyang Zhang. Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
  • Maryam Aliakbarpour, Eric Blais and Ronitt Rubinfeld. Learning and Testing Junta Distributions
  • Kamyar Azizzadenesheli, Alessandro Lazaric and Animashree Anandkumar. Reinforcement Learning of POMDP’s using Spectral Methods
  • Elchanan Mossel and Jiaming Xu. Density Evolution in the Degree-correlated Stochastic Block Model
  • Andrej Risteski. How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
  • Vitaly Kuznetsov and Mehryar Mohri. Time Series Prediction and Online Learning
  • Maria-Florina Balcan, Ellen Vitercik and Colin White. Learning Combinatorial Functions from Pairwise Comparisons
  • Bruce Hajek, Yihong Wu and Jiaming Xu. Semidefinite Programs for Exact Recovery of a Hidden Community
  • Hongyi Zhang and Suvrit Sra. First-order Methods for Geodesically Convex Optimization
  • Afonso S. Bandeira, Nicolas Boumal and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection
  • Peter Auer and Chao-Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
  • Jan-Christian Hütter and Philippe Rigollet. Optimal rates for total variation denoising
  • Arun Rajkumar and Shivani Agarwal. When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs?
  • Daniel Russo. Simple Bayesian Algorithms for Best Arm Identification