#### 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

### Applications of Learning Theory in Algorithmic Game Theory

Aug 20, 2015

·

4341 Views

### Laplacian Matrices of Graphs: Algorithms and Applications

Aug 20, 2015

·

4447 Views

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

Aug 20, 2015

·

3865 Views

## Computational Learning

### An Almost Optimal PAC Algorithm

Aug 20, 2015

·

2218 Views

### Cortical Learning via Prediction

Aug 20, 2015

·

2494 Views

## Optimization I

### On the Complexity of Learning with Kernels

Aug 20, 2015

·

1832 Views

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

Aug 20, 2015

·

3525 Views

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

Aug 20, 2015

·

1533 Views

### Adaptive recovery of signals by convex optimization

Aug 20, 2015

·

1655 Views

### Competing with the Empirical Risk Minimizer in a Single Pass

Aug 20, 2015

·

2071 Views

## On-Line Learning & Bandits I

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

Aug 20, 2015

·

1869 Views

### Achieving All with No Parameters: Adaptive NormalHedge

Aug 20, 2015

·

3092 Views

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

Aug 20, 2015

·

2138 Views

### Second-order Quantile Methods for Experts and Combinatorial Games

Aug 20, 2015

·

1799 Views

### Online Density Estimation of Bradley-Terry Models

Aug 20, 2015

·

1643 Views

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

Aug 20, 2015

·

1725 Views

### On the Complexity of Bandit Linear Optimization

Aug 20, 2015

·

1726 Views

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

Aug 20, 2015

·

1782 Views

### Batched Bandit Problems

Aug 20, 2015

·

1727 Views

## Classification

### MCMC Learning

Aug 20, 2015

·

2055 Views

### Learning and inference in the presence of corrupted inputs

Aug 20, 2015

·

1899 Views

### A PTAS for Agnostically Learning Halfspaces

Aug 20, 2015

·

1573 Views

### Convex Risk Minimization and Conditional Probability Estimation

Sep 09, 2015

·

2535 Views

### Efficient Learning of Linear Separators under Bounded Noise

Aug 20, 2015

·

1911 Views

### Optimally Combining Classifiers Using Unlabeled Data

Aug 20, 2015

·

1690 Views

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

Aug 20, 2015

·

1579 Views

### Hierarchical label queries with data-dependent partitions

Aug 20, 2015

·

1695 Views

### Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

Aug 20, 2015

·

1678 Views

## Unsupervised Learning

### Analyzing Non-Convex Optimization for Sparse Coding

Aug 20, 2015

·

2508 Views

### Tensor principal component analysis

Aug 20, 2015

·

1628 Views

### Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Aug 20, 2015

·

1630 Views

### Online PCA with Spectral Bounds

Aug 20, 2015

·

2260 Views

### Correlation Clustering with Noisy Partial Information

Aug 20, 2015

·

1347 Views

### Norm-Based Capacity Control in Neural Networks

Aug 20, 2015

·

1926 Views

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

Aug 20, 2015

·

1676 Views

## Optimization, Online Learning, Loss Functions

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

Aug 20, 2015

·

2676 Views

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

Aug 20, 2015

·

1903 Views

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

Aug 20, 2015

·

1644 Views

### Sequential Information Maximization: When is Greedy Near-optimal?

Aug 20, 2015

·

1974 Views

### Low Rank Matrix Completion with Exponential Family Noise

Aug 20, 2015

·

1904 Views

### Fast Exact Matrix Completion with Finite Samples

Aug 20, 2015

·

1735 Views

### Exp-Concavity of Proper Composite Losses

Aug 20, 2015

·

1590 Views

### Vector-Valued Property Elicitation

Aug 20, 2015

·

1773 Views

### Generalized Mixability via Entropic Duality

Aug 20, 2015

·

1688 Views

### On Consistent Surrogate Risk Minimization and Property Elicitation

Aug 20, 2015

·

2197 Views

### Label optimal regret bounds for online local learning

Aug 20, 2015

·

2415 Views

## Estimation, Generative Models

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

Aug 20, 2015

·

1826 Views

### On Learning Distributions from their Samples

Aug 20, 2015

·

1941 Views

### Optimum Statistical Estimation with Strategic Data Sources

Aug 20, 2015

·

1800 Views

### Learning Overcomplete Latent Variable Models through Tensor Methods

Aug 20, 2015

·

3752 Views

### Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification

Aug 20, 2015

·

1885 Views

## On-Line Learning & Bandits II

### Minimax Fixed-Design Linear Regression

Aug 20, 2015

·

1981 Views

### A Chaining Algorithm for Online Nonparametric Regression

Aug 20, 2015

·

1830 Views

### First-order regret bounds for combinatorial semi-bandits

Aug 20, 2015

·

1704 Views

### Online Learning with Feedback Graphs: Beyond Bandits

Aug 20, 2015

·

1850 Views

### Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

Aug 20, 2015

·

1617 Views

### Contextual Dueling Bandits

Aug 20, 2015

·

1904 Views

## Open Problems Session

### Restricted Eigen Condition for Heavy Tailed Designs

Aug 20, 2015

·

1640 Views

### The landscape of the loss surfaces of multilayer networks

Aug 20, 2015

·

7471 Views

### The oracle Complexity of Smooth Convex Optimization in Nonstandard Settings

Aug 20, 2015

·

1579 Views

### Online Sabotaged Shortest Path

Aug 20, 2015

·

1813 Views

### Learning Quantum Circuits with Queries

Aug 20, 2015

·

1464 Views

### Recursive Teaching Dimension Versus VC Dimension

Aug 20, 2015

·

1966 Views

## Probabilistic Models and Reinforcement Learning

### Computational Lower Bounds for Community Detection on Random Graphs

Aug 20, 2015

·

1669 Views

### Bad Universal Priors and Notions of Optimality

Aug 20, 2015

·

1544 Views

### Thompson Sampling for Learning Parameterized Markov Decision Processes

Aug 20, 2015

·

1726 Views

### Fast Mixing for Discrete Point Processes

Aug 20, 2015

·

1952 Views

### On Convergence of Emphatic Temporal-Difference Learning

Aug 20, 2015

·

2150 Views

### Faster Algorithms for Testing under Conditional Sampling

Aug 20, 2015

·

1938 Views

### Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Sep 17, 2015

·

1581 Views

## Regression

### Learning with Square Loss: Localization through Offset Rademacher Complexity

Aug 20, 2015

·

2058 Views

### Minimax rates for memory-bounded sparse linear regression

Aug 20, 2015

·

2292 Views

### Algorithms for Lipschitz Learning on Graphs

Aug 20, 2015

·

2945 Views

### Variable Selection is Hard

Aug 20, 2015

·

1877 Views

### Regularized Linear Regression: A Precise Analysis of the Estimation Error

Aug 20, 2015

·

2416 Views

### Truthful Linear Regression

Aug 20, 2015

·

3292 Views