28th Annual Conference on Learning Theory (COLT), Paris 2015

28th Annual Conference on Learning Theory (COLT), Paris 2015

76 Lectures · Jul 2, 2015

About

Learning Theory is a research field devoted to studying the design and analysis of machine learning algorithms. In particular, such algorithms aim at making accurate predictions or representations based on observations.

The emphasis in COLT is on rigorous mathematical analysis using techniques from various connected fields such as probability, statistics, optimization, information theory and geometry. While theoretically rooted, learning theory puts a strong emphasis on efficient computation as well.

For more information visit the COLT 2015 website.

Related categories

Uploaded videos:

Invited Talks

video-img
55:53

Applications of Learning Theory in Algorithmic Game Theory

Tim Roughgarden

Aug 20, 2015

 · 

4344 Views

Invited Talk
video-img
01:05:49

Laplacian Matrices of Graphs: Algorithms and Applications

Daniel A. Spielman

Aug 20, 2015

 · 

4448 Views

Invited Talk
video-img
01:00:19

Synthetic theory of Ricci curvature - when information theory, optimization, geo...

Cédric Villani

Aug 20, 2015

 · 

3869 Views

Invited Talk

Computational Learning

video-img
18:37

An Almost Optimal PAC Algorithm

Hans U. Simon

Aug 20, 2015

 · 

2218 Views

Lecture
video-img
19:42

Cortical Learning via Prediction

Christos H. Papadimitriou

Aug 20, 2015

 · 

2495 Views

Lecture

Optimization I

video-img
13:17

On the Complexity of Learning with Kernels

Ohad Shamir

Aug 20, 2015

 · 

1832 Views

Lecture
video-img
19:42

Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposit...

Furong Huang

Aug 20, 2015

 · 

3525 Views

Lecture
video-img
04:30

Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity

Rasmus J. Kyng

Aug 20, 2015

 · 

1534 Views

Lecture
video-img
05:14

Adaptive recovery of signals by convex optimization

Dmitry Ostrovsky

Aug 20, 2015

 · 

1656 Views

Lecture
video-img
04:01

Competing with the Empirical Risk Minimizer in a Single Pass

Roy Frostig

Aug 20, 2015

 · 

2073 Views

Lecture

On-Line Learning & Bandits I

video-img
14:52

From Averaging to Acceleration, There is Only a Step-size

Nicolas Flammarion

Aug 20, 2015

 · 

1877 Views

Lecture
video-img
05:09

Achieving All with No Parameters: Adaptive NormalHedge

Haipeng Luo

Aug 20, 2015

 · 

3092 Views

Lecture
video-img
17:47

On-Line Learning Algorithms for Path Experts with Non-Additive Losses

Vitaly Kuznetsov

Aug 20, 2015

 · 

2139 Views

Lecture
video-img
06:02

Second-order Quantile Methods for Experts and Combinatorial Games

Wouter M. Koolen

Aug 20, 2015

 · 

1802 Views

Lecture
video-img
06:42

Online Density Estimation of Bradley-Terry Models

Eiji Takimoto

Aug 20, 2015

 · 

1643 Views

Lecture
video-img
06:20

Hierarchies of Relaxations for Online Prediction Problems with Evolving Constrai...

Karthik Sridharan

Aug 20, 2015

 · 

1726 Views

Lecture
video-img
03:47

On the Complexity of Bandit Linear Optimization

Ohad Shamir

Aug 20, 2015

 · 

1726 Views

Lecture
video-img
04:29

Bandit Convex Optimization: sqrt{T} Regret in One Dimension

Tomer Koren

Aug 20, 2015

 · 

1789 Views

Lecture
video-img
06:27

Batched Bandit Problems

Philippe Rigollet

Aug 20, 2015

 · 

1733 Views

Lecture

Classification

video-img
18:38

MCMC Learning

Varun Kanade

Aug 20, 2015

 · 

2055 Views

Lecture
video-img
18:50

Learning and inference in the presence of corrupted inputs

Yishay Mansour

Aug 20, 2015

 · 

1901 Views

Lecture
video-img
03:55

A PTAS for Agnostically Learning Halfspaces

Amit Daniely

Aug 20, 2015

 · 

1575 Views

Lecture
video-img
05:12

Convex Risk Minimization and Conditional Probability Estimation

Matus Telgarsky

Sep 09, 2015

 · 

2542 Views

Lecture
video-img
03:31

Efficient Learning of Linear Separators under Bounded Noise

Ruth Urner

Aug 20, 2015

 · 

1912 Views

Lecture
video-img
05:45

Optimally Combining Classifiers Using Unlabeled Data

Akshay Balsubramani

Aug 20, 2015

 · 

1690 Views

Lecture
video-img
04:43

An Efficient Graph Based Active Learning Algorithm with Application to Nonparame...

Gautam Dasarathy

Aug 20, 2015

 · 

1580 Views

Lecture
video-img
05:10

Hierarchical label queries with data-dependent partitions

Samory Kpotufe

Aug 20, 2015

 · 

1696 Views

Lecture
video-img
19:05

Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

Justin Eldridge

Aug 20, 2015

 · 

1679 Views

Lecture

Unsupervised Learning

video-img
18:29

Analyzing Non-Convex Optimization for Sparse Coding

Tengyu Ma

Aug 20, 2015

 · 

2508 Views

Lecture
video-img
18:12

Tensor principal component analysis

David Steurer

Aug 20, 2015

 · 

1628 Views

Lecture
video-img
04:42

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Luca Zanetti

Aug 20, 2015

 · 

1630 Views

Lecture
video-img
05:28

Online PCA with Spectral Bounds

Edo Liberty

Aug 20, 2015

 · 

2262 Views

Lecture
video-img
04:24

Correlation Clustering with Noisy Partial Information

Aravindan Vijayaraghavan

Aug 20, 2015

 · 

1348 Views

Lecture
video-img
05:09

Norm-Based Capacity Control in Neural Networks

Ryota Tomioka

Aug 20, 2015

 · 

1927 Views

Lecture
video-img
04:22

Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral ...

Peter Chin

Aug 20, 2015

 · 

1676 Views

Lecture

Optimization, Online Learning, Loss Functions

video-img
19:23

The entropic barrier: a simple and optimal universal self-concordant barrier

Sébastien Bubeck

Aug 20, 2015

 · 

2678 Views

Lecture
video-img
17:06

Escaping the Local Minima via Simulated Annealing: Optimization of Approximately...

Tengyuan Liang

Aug 20, 2015

 · 

1904 Views

Lecture
video-img
16:33

Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Prob...

Yash Deshpande

Aug 20, 2015

 · 

1645 Views

Lecture
video-img
04:58

Sequential Information Maximization: When is Greedy Near-optimal?

Yuxin Chen

Aug 20, 2015

 · 

1976 Views

Lecture
video-img
04:38

Low Rank Matrix Completion with Exponential Family Noise

Jean Lafond

Aug 20, 2015

 · 

1904 Views

Lecture
video-img
04:12

Fast Exact Matrix Completion with Finite Samples

Praneeth Netrapalli

Aug 20, 2015

 · 

1736 Views

Lecture
video-img
05:02

Exp-Concavity of Proper Composite Losses

Parameswaran Kamalaruban

Aug 20, 2015

 · 

1590 Views

Lecture
video-img
04:19

Vector-Valued Property Elicitation

Rafael M. Frongillo

Aug 20, 2015

 · 

1775 Views

Lecture
video-img
05:18

Generalized Mixability via Entropic Duality

Mark Reid

Aug 20, 2015

 · 

1690 Views

Lecture
video-img
05:31

On Consistent Surrogate Risk Minimization and Property Elicitation

Shivani Agarwal

Aug 20, 2015

 · 

2197 Views

Lecture
video-img
04:12

Label optimal regret bounds for online local learning

Andrej Risteski

Aug 20, 2015

 · 

2419 Views

Lecture

Estimation, Generative Models

video-img
16:01

Learning the dependence structure of rare events: a non-asymptotic study

Nicolas Goix

Aug 20, 2015

 · 

1826 Views

Lecture
video-img
04:38

On Learning Distributions from their Samples

Sudeep Kamath

Aug 20, 2015

 · 

1942 Views

Lecture
video-img
05:19

Optimum Statistical Estimation with Strategic Data Sources

Constantinos Daskalakis

Aug 20, 2015

 · 

1800 Views

Lecture
video-img
05:12

Learning Overcomplete Latent Variable Models through Tensor Methods

Animashree Anandkumar

Aug 20, 2015

 · 

3753 Views

Lecture
video-img
05:04

Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification

Dehua Cheng

Aug 20, 2015

 · 

1885 Views

Lecture

On-Line Learning & Bandits II

video-img
05:38

Minimax Fixed-Design Linear Regression

Alan Malek

Aug 20, 2015

 · 

1981 Views

Lecture
video-img
05:19

A Chaining Algorithm for Online Nonparametric Regression

Sébastien Gerchinovitz

Aug 20, 2015

 · 

1834 Views

Lecture
video-img
04:15

First-order regret bounds for combinatorial semi-bandits

Gergely Neu

Aug 20, 2015

 · 

1706 Views

Lecture
video-img
07:00

Online Learning with Feedback Graphs: Beyond Bandits

Tomer Koren

Aug 20, 2015

 · 

1852 Views

Lecture
video-img
04:35

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

Junpei Komiyama

Aug 20, 2015

 · 

1618 Views

Lecture
video-img
05:41

Contextual Dueling Bandits

Katja Hofmann

Aug 20, 2015

 · 

1906 Views

Lecture

Open Problems Session

video-img
06:33

Restricted Eigen Condition for Heavy Tailed Designs

Arindam Banerjee

Aug 20, 2015

 · 

1640 Views

Lecture
video-img
06:13

The landscape of the loss surfaces of multilayer networks

Anna Choromanska

Aug 20, 2015

 · 

7474 Views

Lecture
video-img
05:27

The oracle Complexity of Smooth Convex Optimization in Nonstandard Settings

Cristóbal Guzmán

Aug 20, 2015

 · 

1580 Views

Lecture
video-img
05:08

Online Sabotaged Shortest Path

Dmitri Adamskiy

Aug 20, 2015

 · 

1814 Views

Lecture
video-img
04:49

Learning Quantum Circuits with Queries

Jeremy Kun

Aug 20, 2015

 · 

1466 Views

Lecture
video-img
06:12

Recursive Teaching Dimension Versus VC Dimension

Hans U. Simon

Aug 20, 2015

 · 

1968 Views

Lecture

Probabilistic Models and Reinforcement Learning

video-img
03:58

Computational Lower Bounds for Community Detection on Random Graphs

Bruce Hajek

Aug 20, 2015

 · 

1670 Views

Lecture
video-img
05:02

Bad Universal Priors and Notions of Optimality

Jan Leike

Aug 20, 2015

 · 

1545 Views

Lecture
video-img
03:13

Thompson Sampling for Learning Parameterized Markov Decision Processes

Aditya Gopalan

Aug 20, 2015

 · 

1727 Views

Lecture
video-img
05:13

Fast Mixing for Discrete Point Processes

Patrick Rebeschini

Aug 20, 2015

 · 

1953 Views

Lecture
video-img
07:22

On Convergence of Emphatic Temporal-Difference Learning

Huizhen Yu

Aug 20, 2015

 · 

2155 Views

Lecture
video-img
05:48

Faster Algorithms for Testing under Conditional Sampling

Ananda Theertha Suresh

Aug 20, 2015

 · 

1940 Views

Lecture
video-img
04:47

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Thomas Steinke

Sep 17, 2015

 · 

1585 Views

Lecture

Regression

video-img
17:04

Learning with Square Loss: Localization through Offset Rademacher Complexity

Tengyuan Liang

Aug 20, 2015

 · 

2094 Views

Lecture
video-img
17:38

Minimax rates for memory-bounded sparse linear regression

Jacob Steinhardt

Aug 20, 2015

 · 

2297 Views

Lecture
video-img
18:35

Algorithms for Lipschitz Learning on Graphs

Sushant Sachdeva

Aug 20, 2015

 · 

2951 Views

Lecture
video-img
04:12

Variable Selection is Hard

Justin Thaler

Aug 20, 2015

 · 

1877 Views

Lecture
video-img
05:37

Regularized Linear Regression: A Precise Analysis of the Estimation Error

Christos Thrampoulidis

Aug 20, 2015

 · 

2418 Views

Lecture
video-img
07:01

Truthful Linear Regression

Rachel Cummings

Aug 20, 2015

 · 

3292 Views

Lecture