COLT 2016: THE 29TH ANNUAL CONFERENCE ON LEARNING THEORY
PROGRAM

Days: Thursday, June 23rd Friday, June 24th Saturday, June 25th Sunday, June 26th

Thursday, June 23rd

View this program: with abstractssession overviewtalk overview

14:00-15:10 Session 3: Multi-armed Bandits I
14:00
Simple Bayesian Algorithms for Best Arm Identification ( abstract )
14:20
Optimal Best Arm Identification with Fixed Confidence ( abstract )
14:40
Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem ( abstract )
14:50
Best-of-K Bandits ( abstract )
15:00
Pure Exploration of Multi-armed Bandit Under Matroid Constraints ( abstract )
15:10-15:30Coffee Break
15:30-16:20 Session 4: Multi-armed Bandits II
15:30
Maximin Action Identification: A New Bandit Framework for Games ( abstract )
15:40
Instance-dependent Regret Bounds for Dueling Bandits ( abstract )
15:50
An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives ( abstract )
16:00
Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits ( abstract )
16:10
An algorithm with nearly optimal pseudo-regret \\for both stochastic and adversarial bandits ( abstract )
16:20-16:40Break
16:40-18:00 Session 5: Stochastic Block Models
16:40
Information-theoretic thresholds for community detection in sparse networks ( abstract )
17:00
On the low-rank approach for semidefinite programs arising in synchronization and community detection ( abstract )
17:20
Density Evolution in the Degree-correlated Stochastic Block Model ( abstract )
17:30
Learning Communities in the Presence of Errors ( abstract )
17:40
Semidefinite Programs for Exact Recovery of a Hidden Community ( abstract )
17:50
Spectral thresholds in the bipartite stochastic block model ( abstract )
Friday, June 24th

View this program: with abstractssession overviewtalk overview

09:00-09:50 Session 7: Deep Networks
09:00
The Power of Depth for Feedforward Neural Networks ( abstract )
09:10
Benefits of depth in neural networks ( abstract )
09:20
On the Expressive Power of Deep Learning: A Tensor Analysis ( abstract )
09:30
Cortical Computation via Iterative Constructions ( abstract )
09:40
A Guide to Learning Arithmetic Circuits ( abstract )
09:50-10:10Coffee Break
10:10-11:10 Session 8: Tensor Methods/Programming Hierarchies
10:10
How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods ( abstract )
10:30
Noisy Tensor Completion via the Sum-of-Squares Hierarchy ( abstract )
10:50
Basis Learning as an Algorithmic Primitive ( abstract )
11:10-11:30Break
12:30-14:30Lunch Break
14:30-15:50 Session 10: Bandits and Reinforcement Learning
Chair:
14:30
Multi-scale exploration of convex functions and bandit convex optimization (Best Paper Award) ( abstract )
14:50
Delay and Cooperation in Nonstochastic Bandits ( abstract )
15:10
Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models ( abstract )
15:30
Reinforcement Learning of POMDPs using Spectral Methods ( abstract )
15:50-16:20Coffee Break
16:20-17:30 Session 11: PAC Learning
16:20
Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables ( abstract )
16:40
Properly Learning Poisson Binomial Distributions in Almost Polynomial Time ( abstract )
16:50
Learning and Testing Junta Distributions ( abstract )
17:00
Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise ( abstract )
17:10
Complexity theoretic limitations on learning DNF's ( abstract )
17:20
Sign rank versus VC dimension ( abstract )
17:30-17:50Break
Saturday, June 25th

View this program: with abstractssession overviewtalk overview

09:00-10:00 Session 13: Online Learning I
09:00
Provably manipulation-resistant reputation systems (Best Student Paper Award) ( abstract )
09:20
On the capacity of information processing systems ( abstract )
09:40
Online learning in repeated auctions ( abstract )
10:00-10:20Coffee Break
10:20-11:10 Session 14: Statistical inference
10:20
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes ( abstract )
10:30
When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs? ( abstract )
10:40
Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning ( abstract )
10:50
Optimal rates for total variation denoising ( abstract )
11:00
Aggregation of supports along the Lasso path ( abstract )
11:10-11:30Break
12:30-14:30Lunch Break
14:30-15:40 Session 16: Supervised learning
14:30
Adaptive Learning with Robust Generalization Guarantees ( abstract )
14:40
Interactive Algorithms: from Pool to Stream ( abstract )
14:50
The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions ( abstract )
15:00
Learning Combinatorial Functions from Pairwise Comparisons ( abstract )
15:10
Learning Simple Auctions ( abstract )
15:20
Preference-based Teaching ( abstract )
15:40-16:10Coffee Break
16:10-17:20 Session 17: Optimization
16:10
Dropping Convexity for Faster Semi-definite Optimization ( abstract )
16:30
Efficient approaches for escaping higher order saddle points in non-convex optimization ( abstract )
16:40
Gradient Descent only Converges to Minimizers ( abstract )
16:50
First-order Methods for Geodesically Convex Optimization ( abstract )
17:00
A Light Touch for Heavily Constrained SGD ( abstract )
17:10
Highly-Smooth Zero-th Order Online Optimization ( abstract )
17:20-17:40Break
Sunday, June 26th

View this program: with abstractssession overviewtalk overview

09:00-10:00 Session 19: Online Learning II
09:00
Online Sparse Linear Regression ( abstract )
09:20
Online Learning with Low Rank Experts ( abstract )
09:30
Online Isotonic Regression ( abstract )
09:40
Online Learning and Blackwell Approachability in Quitting Games ( abstract )
09:50
Time Series Prediction and Online Learning ( abstract )
10:00-10:20Coffee Break
10:20-11:10 Session 20: Learning with additional constraints/PCA
Chair:
10:20
Memory, Communication, and Statistical Queries ( abstract )
10:40
Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm ( abstract )
10:50
An Improved Gap-Dependency Analysis of the Noisy Power Method ( abstract )
11:00
On the Approximability of Sparse PCA ( abstract )
11:10-11:30Break
12:30-14:30Lunch Break