COLT 2015: 28TH ANNUAL CONFERENCE ON LEARNING THEORY
PROGRAM

Days: Thursday, July 2nd Friday, July 3rd Saturday, July 4th Sunday, July 5th Monday, July 6th

Thursday, July 2nd

View this program: with abstractssession overviewtalk overview

Friday, July 3rd

View this program: with abstractssession overviewtalk overview

09:00-09:40 Session 3: Computational Learning
09:00
An Almost Optimal PAC Algorithm (Best Paper Award!) (abstract)
09:20
Cortical Learning via Prediction (abstract)
09:40-10:40 Session 4: Optimization I
09:40
On the Complexity of Learning with Kernels (abstract)
10:00
Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition (abstract)
10:20
Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity (abstract)
10:25
Adaptive recovery of signals by convex optimization (abstract)
10:30
Competing with the Empirical Risk Minimizer in a Single Pass (abstract)
10:35
Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization (abstract)
10:40-11:10Coffee Break
11:10-12:30 Session 5: On-Line Learning & Bandits I
11:10
From Averaging to Acceleration, There is Only a Step-size (abstract)
11:30
On-Line Learning Algorithms for Path Experts with Non-Additive Losses (abstract)
11:50
Achieving All with No Parameters: Adaptive NormalHedge (abstract)
11:55
Second-order Quantile Methods for Experts and Combinatorial Games (abstract)
12:00
Online Density Estimation of Bradley-Terry Models (abstract)
12:05
Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints (abstract)
12:10
On the Complexity of Bandit Linear Optimization (abstract)
12:15
Bandit Convex Optimization: sqrt{T} Regret in One Dimension (abstract)
12:20
Batched Bandit Problems (abstract)
12:25
Learnability of Solutions to Conjunctive Queries: The Full Dichotomy (abstract)
12:30-14:30Lunch Break
14:30-15:40 Session 6: Classification
14:30
MCMC Learning (abstract)
14:50
Learning and inference in the presence of corrupted inputs (abstract)
15:10
A PTAS for Agnostically Learning Halfspaces (abstract)
15:15
Convex Risk Minimization and Conditional Probability Estimation (abstract)
15:20
Efficient Learning of Linear Separators under Bounded Noise (abstract)
15:25
Optimally Combining Classifiers Using Unlabeled Data (abstract)
15:30
$S^2$: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification (abstract)
15:35
Hierarchical label queries with data-dependent partitions (abstract)
15:40-16:00Coffee Break
18:45-23:00 Session : Cocktail on top of Zamansky Tower

Cocktails and Light Fare will be served on the top floor of a high university building. We booked the room until 11 PM so that there is no rush, but note that this is not really a dinner.

Saturday, July 4th

View this program: with abstractssession overviewtalk overview

09:00-10:45 Session 9: Unsupervised Learning
09:00
Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering (abstract)
09:20
Simple, Efficient, and Neural Algorithms for Sparse Coding (abstract)
09:40
Efficient Representations for Lifelong Learning and Autoencoding (abstract)
10:00
Tensor principal component analysis (abstract)
10:20
Partitioning Well-Clustered Graphs: Spectral Clustering Works! (abstract)
10:25
Online PCA with Spectral Bounds (abstract)
10:30
Correlation Clustering with Noisy Partial Information (abstract)
10:35
Norm-Based Capacity Control in Neural Networks (abstract)
10:40
Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery (abstract)
10:45-11:15Coffee Break
11:15-12:15 Session 10: Invited Talk
Chair:
11:15
Laplacian Matrices of Graphs: Algorithms and Applications (abstract)
Sunday, July 5th

View this program: with abstractssession overviewtalk overview

09:00-10:40 Session 11: Optimization, Online Learning, Loss Functions
09:00
The entropic barrier: a simple and optimal universal self-concordant barrier (abstract)
09:20
Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions (abstract)
09:40
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems (abstract)
10:00
Sequential Information Maximization: When is Greedy Near-optimal? (abstract)
10:05
Low Rank Matrix Completion with Exponential Family Noise (abstract)
10:10
Fast Exact Matrix Completion with Finite Samples (abstract)
10:15
Exp-Concavity of Proper Composite Losses (abstract)
10:20
Vector-Valued Property Elicitation (abstract)
10:25
Generalized Mixability via Entropic Duality (abstract)
10:30
On Consistent Surrogate Risk Minimization and Property Elicitation (abstract)
10:35
Label optimal regret bounds for online local learning (abstract)
10:40-11:10Coffee Break
11:10-12:10 Session 12: Invited Talk
Chair:
11:10
Applications of Learning Theory in Algorithmic Game Theory (abstract)
12:40-14:30Lunch Break
14:30-15:10 Session 14: Estimation, Generative Models
14:30
Learning the dependence structure of rare events: a non-asymptotic study (abstract)
14:50
On Learning Distributions from their Samples (abstract)
14:55
Optimum Statistical Estimation with Strategic Data Sources (abstract)
15:00
Learning Overcomplete Latent Variable Models through Tensor Methods (abstract)
15:05
Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification (abstract)
15:10-15:40 Session 15: On-Line Learning & Bandits II
15:10
Minimax Fixed-Design Linear Regression (abstract)
15:15
A Chaining Algorithm for Online Nonparametric Regression (abstract)
15:20
First-order regret bounds for combinatorial semi-bandits (abstract)
15:25
Online Learning with Feedback Graphs: Beyond Bandits (abstract)
15:30
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem (abstract)
15:35
Contextual Dueling Bandits (abstract)
15:40-16:00Coffee Break
Monday, July 6th

View this program: with abstractssession overviewtalk overview

09:00-10:00 Session 18: Invited Talk
09:00
Synthetic theory of Ricci curvature - when information theory, optimization, geometry and gradient flows meet (abstract)
10:00-10:40 Session 19: Probabilistic Models and Reinforcement Learning
10:00
Computational Lower Bounds for Community Detection on Random Graphs (abstract)
10:05
Bad Universal Priors and Notions of Optimality (abstract)
10:10
Thompson Sampling for Learning Parameterized Markov Decision Processes (abstract)
10:15
Fast Mixing for Discrete Point Processes (abstract)
10:20
On Convergence of Emphatic Temporal-Difference Learning (abstract)
10:25
Faster Algorithms for Testing under Conditional Sampling (abstract)
10:30
Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery (abstract)
10:40-11:10Coffee Break
11:10-12:25 Session 20: Regression
11:10
Learning with Square Loss: Localization through Offset Rademacher Complexity (abstract)
11:30
Minimax rates for memory-bounded sparse linear regression (abstract)
11:50
Algorithms for Lipschitz Learning on Graphs (abstract)
12:10
Variable Selection is Hard (abstract)
12:15
Regularized Linear Regression: A Precise Analysis of the Estimation Error (abstract)
12:20
Truthful Linear Regression (abstract)