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.
Videos
Invited Talks

Synthetic theory of Ricci curvature - when information theory, optimization, geo...
Aug 20, 2015
·
3922 views

Laplacian Matrices of Graphs: Algorithms and Applications
Aug 20, 2015
·
4477 views

Applications of Learning Theory in Algorithmic Game Theory
Aug 20, 2015
·
4374 views
Computational Learning

An Almost Optimal PAC Algorithm
Aug 20, 2015
·
2252 views

Cortical Learning via Prediction
Aug 20, 2015
·
2518 views
Optimization I

Adaptive recovery of signals by convex optimization
Aug 20, 2015
·
1676 views

Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposit...
Aug 20, 2015
·
3544 views

Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
Aug 20, 2015
·
1544 views

Competing with the Empirical Risk Minimizer in a Single Pass
Aug 20, 2015
·
2088 views

On the Complexity of Learning with Kernels
Aug 20, 2015
·
1846 views
On-Line Learning & Bandits I

Hierarchies of Relaxations for Online Prediction Problems with Evolving Constrai...
Aug 20, 2015
·
1743 views

Online Density Estimation of Bradley-Terry Models
Aug 20, 2015
·
1657 views

Batched Bandit Problems
Aug 20, 2015
·
1745 views

Bandit Convex Optimization: sqrt{T} Regret in One Dimension
Aug 20, 2015
·
1819 views

Second-order Quantile Methods for Experts and Combinatorial Games
Aug 20, 2015
·
1823 views

Achieving All with No Parameters: Adaptive NormalHedge
Aug 20, 2015
·
3116 views

On the Complexity of Bandit Linear Optimization
Aug 20, 2015
·
1745 views

On-Line Learning Algorithms for Path Experts with Non-Additive Losses
Aug 20, 2015
·
2160 views

From Averaging to Acceleration, There is Only a Step-size
Aug 20, 2015
·
1916 views
Classification

Hierarchical label queries with data-dependent partitions
Aug 20, 2015
·
1714 views

Learning and inference in the presence of corrupted inputs
Aug 20, 2015
·
1915 views

An Efficient Graph Based Active Learning Algorithm with Application to Nonparame...
Aug 20, 2015
·
1602 views

Optimally Combining Classifiers Using Unlabeled Data
Aug 20, 2015
·
1701 views

Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering
Aug 20, 2015
·
1695 views

MCMC Learning
Aug 20, 2015
·
2075 views

Convex Risk Minimization and Conditional Probability Estimation
Sep 9, 2015
·
2585 views

Efficient Learning of Linear Separators under Bounded Noise
Aug 20, 2015
·
1928 views

A PTAS for Agnostically Learning Halfspaces
Aug 20, 2015
·
1590 views
Unsupervised Learning

Tensor principal component analysis
Aug 20, 2015
·
1650 views

Analyzing Non-Convex Optimization for Sparse Coding
Aug 20, 2015
·
2527 views

Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral ...
Aug 20, 2015
·
1695 views

Online PCA with Spectral Bounds
Aug 20, 2015
·
2288 views

Correlation Clustering with Noisy Partial Information
Aug 20, 2015
·
1362 views

Partitioning Well-Clustered Graphs: Spectral Clustering Works!
Aug 20, 2015
·
1644 views

Norm-Based Capacity Control in Neural Networks
Aug 20, 2015
·
1940 views
Optimization, Online Learning, Loss Functions

Exp-Concavity of Proper Composite Losses
Aug 20, 2015
·
1608 views

Label optimal regret bounds for online local learning
Aug 20, 2015
·
2441 views

On Consistent Surrogate Risk Minimization and Property Elicitation
Aug 20, 2015
·
2214 views

Low Rank Matrix Completion with Exponential Family Noise
Aug 20, 2015
·
1920 views

Escaping the Local Minima via Simulated Annealing: Optimization of Approximately...
Aug 20, 2015
·
1921 views

Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Prob...
Aug 20, 2015
·
1658 views

Generalized Mixability via Entropic Duality
Aug 20, 2015
·
1705 views

Sequential Information Maximization: When is Greedy Near-optimal?
Aug 20, 2015
·
2000 views

The entropic barrier: a simple and optimal universal self-concordant barrier
Aug 20, 2015
·
3132 views

Fast Exact Matrix Completion with Finite Samples
Aug 20, 2015
·
1751 views

Vector-Valued Property Elicitation
Aug 20, 2015
·
1803 views
Estimation, Generative Models

On Learning Distributions from their Samples
Aug 20, 2015
·
1956 views

Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
Aug 20, 2015
·
1907 views

Optimum Statistical Estimation with Strategic Data Sources
Aug 20, 2015
·
1815 views

Learning Overcomplete Latent Variable Models through Tensor Methods
Aug 20, 2015
·
3770 views

Learning the dependence structure of rare events: a non-asymptotic study
Aug 20, 2015
·
1839 views
On-Line Learning & Bandits II

Minimax Fixed-Design Linear Regression
Aug 20, 2015
·
2005 views

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
Aug 20, 2015
·
1634 views

A Chaining Algorithm for Online Nonparametric Regression
Aug 20, 2015
·
1872 views

Online Learning with Feedback Graphs: Beyond Bandits
Aug 20, 2015
·
1885 views

Contextual Dueling Bandits
Aug 20, 2015
·
1926 views

First-order regret bounds for combinatorial semi-bandits
Aug 20, 2015
·
1724 views
Open Problems Session

The landscape of the loss surfaces of multilayer networks
Aug 20, 2015
·
7511 views

Recursive Teaching Dimension Versus VC Dimension
Aug 20, 2015
·
1991 views

The oracle Complexity of Smooth Convex Optimization in Nonstandard Settings
Aug 20, 2015
·
1599 views

Online Sabotaged Shortest Path
Aug 20, 2015
·
1827 views

Learning Quantum Circuits with Queries
Aug 20, 2015
·
1476 views

Restricted Eigen Condition for Heavy Tailed Designs
Aug 20, 2015
·
1654 views
Probabilistic Models and Reinforcement Learning

Thompson Sampling for Learning Parameterized Markov Decision Processes
Aug 20, 2015
·
1754 views

Bad Universal Priors and Notions of Optimality
Aug 20, 2015
·
1564 views

Faster Algorithms for Testing under Conditional Sampling
Aug 20, 2015
·
1953 views

On Convergence of Emphatic Temporal-Difference Learning
Aug 20, 2015
·
2170 views

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
Sep 17, 2015
·
1622 views

Fast Mixing for Discrete Point Processes
Aug 20, 2015
·
1978 views

Computational Lower Bounds for Community Detection on Random Graphs
Aug 20, 2015
·
1682 views
Regression

Minimax rates for memory-bounded sparse linear regression
Aug 20, 2015
·
2332 views

Learning with Square Loss: Localization through Offset Rademacher Complexity
Aug 20, 2015
·
2120 views

Algorithms for Lipschitz Learning on Graphs
Aug 20, 2015
·
2990 views

Truthful Linear Regression
Aug 20, 2015
·
3307 views

Regularized Linear Regression: A Precise Analysis of the Estimation Error
Aug 20, 2015
·
2451 views

Variable Selection is Hard
Aug 20, 2015
·
1899 views