COLT 2017 Video Archive

These are the videos recorded at the Conference on Learning Theory, 2017, Amsterdam.

Friday, July 7th


video
09:00
Vitaly Feldman and Thomas Steinke
Generalization for Adaptively-chosen Estimators via Stable Median

video
09:20
Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian and Nathan Srebro
Learning Non-Discriminatory Predictors

video
09:40
Mitali Bafna and Jonathan Ullman
The Price of Selection in Differential Privacy

video
09:50
Pranjal Awasthi, Avrim Blum, Nika Haghtalab and Yishay Mansour
Efficient PAC Learning from the Crowd

video
10:20
Yuchen Zhang, Percy Liang and Moses Charikar
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (Best Paper Award)

video
10:40
Maxim Raginsky, Alexander Rakhlin and Matus Telgarsky
Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis

video
10:50
Arnak Dalalyan
Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent

video
11:00
Nicolas Brosse, Alain Durmus, Eric Moulines and Marcelo Pereyra
Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo

video
11:10
Alon Gonen and Shai Shalev-Shwartz
Fast Rates for Empirical Risk Minimization of Strict Saddle Problems

video
11:35
Scott Aaronson
PAC-Learning and Reconstruction of Quantum States

video
14:30
Yury Polyanskiy, Ananda Theertha Suresh and Yihong Wu
Sample complexity of population recovery

video
14:50
Shachar Lovett and Jiapeng Zhang
Noisy Population Recovery from Unknown Noise

video
15:00
Ilias Diakonikolas, Daniel Kane and Alistair Stewart
Learning Multivariate Log-concave Distributions

video
15:10
Constantinos Daskalakis, Manolis Zampetakis and Christos Tzamos
Ten Steps of EM Suffice for Mixtures of Two Gaussians

video
15:20
Ravi Kannan and Santosh Vempala
The Hidden Hubs Problem

video
16:00
Joon Kwon, Vianney Perchet and Claire Vernade
Sparse Stochastic Bandits

video
16:10
Yevgeny Seldin and Gabor Lugosi
An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits

video
16:20
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur and Robert Schapire
Corralling a Band of Bandit Algorithms

video
16:30
Jonathan Scarlett, Ilija Bogunovic and Volkan Cevher
Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

video
16:40
Lijie Chen, Jian Li and Mingda Qiao
Towards Instance Optimal Bounds for Best Arm Identification

video
16:50
Tomer Koren, Roi Livni and Yishay Mansour
Bandits with Movement Costs and Adaptive Pricing

video
17:20
Alon Cohen, Tamir Hazan and Tomer Koren
Tight Bounds for Bandit Combinatorial Optimization

video
17:30
Nicolò Cesa-Bianchi, Pierre Gaillard, Claudio Gentile and Sébastien Gerchinovitz
Online Nonparametric Learning, Chaining, and the Role of Partial Feedback

video
17:40
Open Problems Session
Open Problem Session

Saturday, July 8th


video
09:00
Andrea Locatelli, Alexandra Carpentier and Samory Kpotufe
Adaptivity to Noise Parameters in Nonparametric Active Learning

video
09:20
Simon Du, Sivaraman Balakrishnan, Jerry Li and Aarti Singh
Computationally Efficient Robust Estimation of Sparse Functionals

video
09:30
Jerry Li and Ludwig Schmidt
Robust Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities

video
09:40
Daniel Vainsencher, Shie Mannor and Huan Xu
Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization

video
09:50
Yeshwanth Cherapanamjeri, Prateek Jain and Praneeth Netrapalli
Thresholding based Efficient Outlier Robust PCA

video
10:20
Song Mei, Theodor Misiakiewicz, Andrea Montanari and Roberto Oliveira
Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality

video
10:40
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik and Colin White
Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems

video
10:50
Moran Feldman, Christopher Harshaw and Amin Karbasi
Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization

video
11:00
Avinatan Hassidim and Yaron Singer
Submodular Optimization under Noise

video
11:10
Alexandr Andoni, Daniel Hsu, Kevin Shi and Xiaorui Sun
Correspondence retrieval

video
11:35
Ashok Cutkosky and Kwabena Boahen
Online Learning Without Prior Information (Best Student Paper Award)

video
11:55
Alexander Rakhlin and Karthik Sridharan
On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities

video
12:15
Gergely Neu and Vicenç Gómez
Fast rates for online learning in Linearly Solvable Markov Decision Processes

video
12:25
Dylan Foster, Alexander Rakhlin and Karthik Sridharan
ZIGZAG: A new approach to adaptive online learning

video
14:50
Avrim Blum and Yishay Mansour
Efficient Co-Training of Linear Separators under Weak Dependence

video
15:10
Amir Globerson, Roi Livni and Shai Shalev-Shwartz
Effective Semisupervised Learning on Manifolds

video
15:20
Lunjia Hu, Ruihan Wu, Tianhong Li and Liwei Wang
Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes

video
15:30
Nader Bshouty, Dana Drachsler Cohen, Martin Vechev and Eran Yahav
Learning Disjunctions of Predicates

Sunday, July 9th


video
09:00
Vitaly Feldman
A General Characterization of the Statistical Query Complexity

video
09:20
Michal Moshkovitz and Dana Moshkovitz
Mixing Implies Lower Bounds for Space Bounded Learning

video
09:40
Salil Vadhan
On Learning versus Refutation

video
09:50
Pasin Manurangsi and Aviad Rubinstein
Inapproximability of VC Dimension and Littlestone’s Dimension

video
10:20
Rafael Frongillo and Andrew Nobel
Memoryless Sequences for Differentiable Losses

video
10:40
Sebastian Casalaina-Martin, Rafael Frongillo, Tom Morgan and Bo Waggoner
Multi-Observation Elicitation

video
10:50
Clément Canonne, Ilias Diakonikolas, Daniel Kane and Alistair Stewart
Testing Bayesian Networks

video
11:00
Constantinos Daskalakis and Qinxuan Pan
Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing

video
11:10
Debarghya Ghoshdastidar, Ulrike von Luxburg, Maurilio Gutzeit and Alexandra Carpentier
Two-Sample Tests for Large Random Graphs using Network Statistics

video
11:35
Andrea Montanari
Computational barriers in statistical learning

video
14:30
Lijun Zhang, Tianbao Yang and Rong Jin
Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds

video
14:50
Nicolas Flammarion and Francis Bach
Stochastic Composite Least-Squares Regression with convergence rate O(1/n)

video
15:00
Bin Hu, Peter Seiler and Anders Rantzer
A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints

video
15:10
Jialei Wang, Weiran Wang and Nathan Srebro
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox

video
15:20
Eric Balkanski and Yaron Singer
The Sample Complexity of Optimizing a Convex Function

video
16:00
Max Simchowitz, Kevin Jamieson and Benjamin Recht
The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime

video
16:20
Arpit Agarwal, Shivani Agarwal, Sepehr Assadi and Sanjeev Khanna
Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons

video
16:40
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao and Ruosong Wang
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration

video
16:50
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal and Assaf Zeevi
Thompson Sampling for the MNL-Bandit

Monday, July 10th


video
09:00
Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski and Sanjeev Arora
On the Ability of Neural Nets to Express Distributions

video
09:20
Amit Daniely
Depth Separation for Neural Networks

video
09:30
David Helmbold and Phil Long
Surprising properties of dropout in deep networks

video
09:40
Surbhi Goel, Varun Kanade, Adam Klivans and Justin Thaler
Reliably Learning the ReLU in Polynomial Time

video
09:50
Nicholas Harvey, Christopher Liaw and Abbas Mehrabian
Nearly-tight VC-dimension bounds for neural networks

video
10:20
Aaron Potechin and David Steurer
Exact tensor completion with sum-of-squares

video
10:40
Tselil Schramm and David Steurer
Fast and robust tensor decomposition with applications to dictionary learning

video
10:50
Anima Anandkumar, Yuan Deng, Rong Ge and Hossein Mobahi
Homotopy Analysis for Tensor PCA

video
11:00
Marc Lelarge and Léo Miolane
Fundamental limits of symmetric low-rank matrix estimation

video
11:10
David Gamarnik, Quan Li and Hongyi Zhang
Matrix Completion from O(n) Samples in Linear Time

video
11:35
Ilias Zadik and David Gamarnik. High-Dimensional Regression with Binary Coefficients: Estimating Squared Error and a Phase Transition.

video
11:55
Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet and John Urschel
Rates of estimation for determinantal point processes

video
12:05
Michael Kearns and Zhiwei Steven Wu
Predicting with Distributions

video
12:15
Andreas Maurer
A second-order look at stability and generalization

video
12:25
Nikita Zhivotovskiy
Optimal learning via local entropies and sample compression