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

 · 

4341 Views

Invited Talk
video-img
01:05:49

Laplacian Matrices of Graphs: Algorithms and Applications

Daniel A. Spielman

Aug 20, 2015

 · 

4447 Views

Invited Talk
video-img
01:00:19

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

Cédric Villani

Aug 20, 2015

 · 

3865 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

 · 

2494 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

 · 

1533 Views

Lecture
video-img
05:14

Adaptive recovery of signals by convex optimization

Dmitry Ostrovsky

Aug 20, 2015

 · 

1655 Views

Lecture
video-img
04:01

Competing with the Empirical Risk Minimizer in a Single Pass

Roy Frostig

Aug 20, 2015

 · 

2071 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

 · 

1869 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

 · 

2138 Views

Lecture
video-img
06:02

Second-order Quantile Methods for Experts and Combinatorial Games

Wouter M. Koolen

Aug 20, 2015

 · 

1799 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

 · 

1725 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

 · 

1782 Views

Lecture
video-img
06:27

Batched Bandit Problems

Philippe Rigollet

Aug 20, 2015

 · 

1727 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

 · 

1899 Views

Lecture
video-img
03:55

A PTAS for Agnostically Learning Halfspaces

Amit Daniely

Aug 20, 2015

 · 

1573 Views

Lecture
video-img
05:12

Convex Risk Minimization and Conditional Probability Estimation

Matus Telgarsky

Sep 09, 2015

 · 

2535 Views

Lecture
video-img
03:31

Efficient Learning of Linear Separators under Bounded Noise

Ruth Urner

Aug 20, 2015

 · 

1911 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

 · 

1579 Views

Lecture
video-img
05:10

Hierarchical label queries with data-dependent partitions

Samory Kpotufe

Aug 20, 2015

 · 

1695 Views

Lecture
video-img
19:05

Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

Justin Eldridge

Aug 20, 2015

 · 

1678 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

 · 

2260 Views

Lecture
video-img
04:24

Correlation Clustering with Noisy Partial Information

Aravindan Vijayaraghavan

Aug 20, 2015

 · 

1347 Views

Lecture
video-img
05:09

Norm-Based Capacity Control in Neural Networks

Ryota Tomioka

Aug 20, 2015

 · 

1926 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

 · 

2676 Views

Lecture
video-img
17:06

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

Tengyuan Liang

Aug 20, 2015

 · 

1903 Views

Lecture
video-img
16:33

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

Yash Deshpande

Aug 20, 2015

 · 

1644 Views

Lecture
video-img
04:58

Sequential Information Maximization: When is Greedy Near-optimal?

Yuxin Chen

Aug 20, 2015

 · 

1974 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

 · 

1735 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

 · 

1773 Views

Lecture
video-img
05:18

Generalized Mixability via Entropic Duality

Mark Reid

Aug 20, 2015

 · 

1688 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

 · 

2415 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

 · 

1941 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

 · 

3752 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

 · 

1830 Views

Lecture
video-img
04:15

First-order regret bounds for combinatorial semi-bandits

Gergely Neu

Aug 20, 2015

 · 

1704 Views

Lecture
video-img
07:00

Online Learning with Feedback Graphs: Beyond Bandits

Tomer Koren

Aug 20, 2015

 · 

1850 Views

Lecture
video-img
04:35

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

Junpei Komiyama

Aug 20, 2015

 · 

1617 Views

Lecture
video-img
05:41

Contextual Dueling Bandits

Katja Hofmann

Aug 20, 2015

 · 

1904 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

 · 

7471 Views

Lecture
video-img
05:27

The oracle Complexity of Smooth Convex Optimization in Nonstandard Settings

Cristóbal Guzmán

Aug 20, 2015

 · 

1579 Views

Lecture
video-img
05:08

Online Sabotaged Shortest Path

Dmitri Adamskiy

Aug 20, 2015

 · 

1813 Views

Lecture
video-img
04:49

Learning Quantum Circuits with Queries

Jeremy Kun

Aug 20, 2015

 · 

1464 Views

Lecture
video-img
06:12

Recursive Teaching Dimension Versus VC Dimension

Hans U. Simon

Aug 20, 2015

 · 

1966 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

 · 

1669 Views

Lecture
video-img
05:02

Bad Universal Priors and Notions of Optimality

Jan Leike

Aug 20, 2015

 · 

1544 Views

Lecture
video-img
03:13

Thompson Sampling for Learning Parameterized Markov Decision Processes

Aditya Gopalan

Aug 20, 2015

 · 

1726 Views

Lecture
video-img
05:13

Fast Mixing for Discrete Point Processes

Patrick Rebeschini

Aug 20, 2015

 · 

1952 Views

Lecture
video-img
07:22

On Convergence of Emphatic Temporal-Difference Learning

Huizhen Yu

Aug 20, 2015

 · 

2150 Views

Lecture
video-img
05:48

Faster Algorithms for Testing under Conditional Sampling

Ananda Theertha Suresh

Aug 20, 2015

 · 

1938 Views

Lecture
video-img
04:47

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Thomas Steinke

Sep 17, 2015

 · 

1581 Views

Lecture

Regression

video-img
17:04

Learning with Square Loss: Localization through Offset Rademacher Complexity

Tengyuan Liang

Aug 20, 2015

 · 

2058 Views

Lecture
video-img
17:38

Minimax rates for memory-bounded sparse linear regression

Jacob Steinhardt

Aug 20, 2015

 · 

2292 Views

Lecture
video-img
18:35

Algorithms for Lipschitz Learning on Graphs

Sushant Sachdeva

Aug 20, 2015

 · 

2945 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

 · 

2416 Views

Lecture
video-img
07:01

Truthful Linear Regression

Rachel Cummings

Aug 20, 2015

 · 

3292 Views

Lecture