COLT 2015

77 papers

On Convergence of Emphatic Temporal-Difference Learning

H. Yu

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

Santosh S. Vempala, Ying. Xiao

Regularized Linear Regression: A Precise Analysis of the Estimation Error

CHRISTOS THRAMPOULIDIS, Samet Oymak, Babak Hassibi

Convex Risk Minimization and Conditional Probability Estimation

Matus Telgarsky, Miroslav Dudík, Robert Schapire

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Thomas Steinke, Jonathan Ullman

Minimax rates for memory-bounded sparse linear regression

Jacob Steinhardt, John Duchi

An Almost Optimal PAC Algorithm

Hans U. Simon

On the Complexity of Bandit Linear Optimization

Ohad Shamir

Generalized Mixability via Entropic Duality

Mark D. Reid, Rafael M. Frongillo, Robert C. Williamson, Nishant Mehta

Fast Mixing for Discrete Point Processes

Patrick Rebeschini, Amin Karbasi

Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints

Alexander Rakhlin, Karthik Sridharan

Batched Bandit Problems

Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Richard Peng, He Sun, Luca Zanetti

Cortical Learning via Prediction

Christos H. Papadimitriou, Santosh S. Vempala

Norm-Based Capacity Control in Neural Networks

Behnam Neyshabur, Ryota Tomioka, Nathan Srebro

First-order regret bounds for combinatorial semi-bandits

Gergely Neu

Online Density Estimation of Bradley-Terry Models

Issei Matsumoto, Kohei Hatano, Eiji Takimoto

Correlation Clustering with Noisy Partial Information

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization

Mehrdad Mahdavi, Lijun Zhang, Rong Jin

Achieving All with No Parameters: AdaNormalHedge

Haipeng Luo, Robert E. Schapire

Learning with Square Loss: Localization through Offset Rademacher Complexity

Tengyuan Liang, Alexander Rakhlin, Karthik Sridharan

Bad Universal Priors and Notions of Optimality

Jan Leike, Marcus Hutter

Low Rank Matrix Completion with Exponential Family Noise

Jean Lafond

Algorithms for Lipschitz Learning on Graphs

Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman

Hierarchical Label Queries with Data-Dependent Partitions

Samory Kpotufe, Ruth Urner, Shai Ben-David

Second-order Quantile Methods for Experts and Combinatorial Games

Wouter M. Koolen, Tim van Erven

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

Junpei Komiyama, Junya Honda, Hisashi Kashima, Hiroshi Nakagawa

Online PCA with Spectral Bounds

Zohar Karnin, Edo Liberty

MCMC Learning

Varun Kanade, Elchanan Mossel

On Learning Distributions from their Samples

Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, Ananda Theertha Suresh

Exp-Concavity of Proper Composite Losses

Parameswaran Kamalaruban, Robert Williamson, Xinhua Zhang

Fast Exact Matrix Completion with Finite Samples

Prateek Jain, Praneeth Netrapalli

Tensor principal component analysis via sum-of-square proofs

Samuel B. Hopkins, Jonathan Shi, David Steurer

Adaptive Recovery of Signals by Convex Optimization

Zaïd Harchaoui, Anatoli Juditsky, Arkadi Nemirovski, Dmitry Ostrovsky

Computational Lower Bounds for Community Detection on Random Graphs

Bruce Hajek, Yihong Wu, Jiaming Xu

Thompson Sampling for Learning Parameterized Markov Decision Processes

Aditya Gopalan, Shie Mannor

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

Nicolas Goix, Anne Sabourin, Stéphan Clémen\ccon

Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition

Rong Ge, Furong Huang, Chi Jin, Yang Yuan

A Chaining Algorithm for Online Nonparametric Regression

Pierre Gaillard, Sébastien Gerchinovitz

Competing with the Empirical Risk Minimizer in a Single Pass

Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford

Vector-Valued Property Elicitation

Rafael Frongillo, Ian A. Kash

Variable Selection is Hard

Dean Foster, Howard Karloff, Justin Thaler

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

Nicolas Flammarion, Francis Bach

Learning and inference in the presence of corrupted inputs

Uriel Feige, Yishay Mansour, Robert Schapire

Faster Algorithms for Testing under Conditional Sampling

Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh

Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

Justin Eldridge, Mikhail Belkin, Yusu Wang

Contextual Dueling Bandits

Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, Masrour Zoghi

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

Yash Deshpande, Andrea Montanari

S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification

Gautam Dasarathy, Robert Nowak, Xiaojin Zhu

A PTAS for Agnostically Learning Halfspaces

Amit Daniely

Truthful Linear Regression

Rachel Cummings, Stratis Ioannidis, Katrina Ligett

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

Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Manfred Warmuth

Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery

peter chin, Anup Rao, Van Vu

Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification

Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng

Sequential Information Maximization: When is Greedy Near-optimal?

Yuxin Chen, S. Hamed Hassani, Amin Karbasi, Andreas Krause

Learnability of Solutions to Conjunctive Queries: The Full Dichotomy

Hubie Chen, Matthew Valeriote

On the Complexity of Learning with Kernels

Nicolò Cesa-bianchi, Yishay Mansour, Ohad Shamir

Optimum Statistical Estimation with Strategic Data Sources

Yang Cai, Constantinos Daskalakis, Christos Papadimitriou

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

Sébastien Bubeck, Ronen Eldan

Bandit Convex Optimization: \sqrtT Regret in One Dimension

Sébastien Bubeck, Ofer Dekel, Tomer Koren, Yuval Peres

Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions

Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin

Minimax Fixed-Design Linear Regression

Peter L. Bartlett, Wouter M. Koolen, Alan Malek, Eiji Takimoto, Manfred K. Warmuth

Optimally Combining Classifiers Using Unlabeled Data

Akshay Balsubramani, Yoav Freund

Efficient Representations for Lifelong Learning and Autoencoding

Maria-Florina Balcan, Avrim Blum, Santosh Vempala

Efficient Learning of Linear Separators under Bounded Noise

Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Ruth Urner

Label optimal regret bounds for online local learning

Pranjal Awasthi, Moses Charikar, Kevin A Lai, Andrej Risteski

Simple, Efficient, and Neural Algorithms for Sparse Coding

Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra

Learning Overcomplete Latent Variable Models through Tensor Methods

Animashree Anandkumar, Rong Ge, Majid Janzamin

Online Learning with Feedback Graphs: Beyond Bandits

Noga Alon, Nicolò Cesa-bianchi, Ofer Dekel, Tomer Koren

On Consistent Surrogate Risk Minimization and Property Elicitation

Arpit Agarwal, Shivani Agarwal

Open Problem: Recursive Teaching Dimension Versus VC Dimension

Hans U. Simon, Sandra Zilles

Open Problem: Learning Quantum Circuits with Queries

Jeremy Kun, Lev Reyzin

Open Problem: Online Sabotaged Shortest Path

Wouter M. Koolen, Manfred K. Warmuth, Dmitri Adamskiy

Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings

Cristóbal Guzmán

Open Problem: The landscape of the loss surfaces of multilayer networks

Anna Choromanska, Yann LeCun, Gerard Ben Arous

Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs

Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar

Conference on Learning Theory 2015: Preface

Peter Grünwald, Elad Hazan