Like previous years (2014, 2015) I have compiled the list of accepted papers for this year’s edition of COLT together with links to the arxiv submission whenever I could find one. These 63 papers were selected from about 200 submissions (a healthy 11% increase in terms of submissions from last year).

**COLT 2016 accepted papers**

- Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
- The Power of Depth for Feedforward Neural Networks
- On the Expressive Power of Deep Learning: A Tensor Analysis
- Gradient Descent only Converges to Minimizers
- Aggregation of supports along the Lasso path
- Online Sparse Linear Regression
- On the Approximability of Sparse PCA
- Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
- Optimal Best Arm Identification with Fixed Confidence
- Learning Communities in the Presence of Errors
- Sign rank versus VC dimension
- Multi-scale exploration of convex functions and bandit convex optimization
- An Improved Gap-Dependency Analysis of the Noisy Power Method
- Delay and Cooperation in Nonstochastic Bandits
- Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
- The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions
- Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
- Online learning in repeated auctions
- Complexity theoretic limitations on learning DNF’s
- Memory, Communication, and Statistical Queries
- Interactive Algorithms: from Pool to Stream
- Best-of-K Bandits
- Basis Learning as an Algorithmic Primitive
- On the capacity of information processing systems
- Noisy Tensor Completion via the Sum-of-Squares Hierarchy
- Benefits of depth in neural networks
- An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
- A Light Touch for Heavily Constrained SGD
- Dropping Convexity for Faster Semi-definite Optimization
- Online Isotonic Regression
- Maximin Action Identification: A New Bandit Framework for Games
- A Guide to Learning Arithmetic Circuits
- Learning Simple Auctions
- Online Learning with Low Rank Experts
- Information-theoretic thresholds for community detection in sparse networks
- Efficient approaches for escaping higher order saddle points in non-convex optimization
- Online Learning and Blackwell Approachability in Quitting Games
- Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja’s Algorithm
- Preference-based Teaching
- Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
- Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
- Cortical Computation via Iterative Constructions
- Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
- Instance-dependent Regret Bounds for Dueling Bandits
- Provably manipulation-resistant reputation systems
- Highly-Smooth Zero-th Order Online Optimization
- Spectral thresholds in the bipartite stochastic block model
- Adaptive Learning with Robust Generalization Guarantees
- Pure Exploration of Multi-armed Bandit Under Matroid Constraints
- Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
- Learning and Testing Junta Distributions
- Reinforcement Learning of POMDP’s using Spectral Methods
- Density Evolution in the Degree-correlated Stochastic Block Model
- How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
- Time Series Prediction and Online Learning
- Learning Combinatorial Functions from Pairwise Comparisons
- Semidefinite Programs for Exact Recovery of a Hidden Community
- First-order Methods for Geodesically Convex Optimization
- On the low-rank approach for semidefinite programs arising in synchronization and community detection
- An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
- Optimal rates for total variation denoising
- When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs?
- Simple Bayesian Algorithms for Best Arm Identification