Nuit Blanche: Proceedings of The 28th Conference on Learning Theory

Friday, July 03, 2015

Proceedings of The 28th Conference on Learning Theory - COLT 2015

So the COLT conference started this morning in sweltering Paris. Many of the presentations have been featured in a fashion or another on Nuit Blanche. Here are the full proceedings:

Conference on Learning Theory 2015: Preface, Peter Grünwald, Elad Hazan [abs] [pdf]

Regular Papers

On Consistent Surrogate Risk Minimization and Property Elicitation, Arpit Agarwal, Shivani Agarwal, [abs] [pdf]
Online Learning with Feedback Graphs: Beyond Bandits, Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, Tomer Koren [abs] [pdf]
Learning Overcomplete Latent Variable Models through Tensor Methods, Animashree Anandkumar, Rong Ge, Majid Janzamin [abs] [pdf]
Simple, Efficient, and Neural Algorithms for Sparse Coding, Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra [abs] [pdf]
Label optimal regret bounds for online local learning, Pranjal Awasthi, Moses Charikar, Kevin A Lai, Andrej Risteski [abs] [pdf]
Efficient Learning of Linear Separators under Bounded Noise, Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Ruth Urner, [abs] [pdf]
Efficient Representations for Lifelong Learning and Autoencoding, Maria-Florina Balcan, Avrim Blum, Santosh Vempala [abs] [pdf]
Optimally Combining Classifiers Using Unlabeled Data, Akshay Balsubramani, Yoav Freund [abs] [pdf]
Minimax Fixed-Design Linear Regression, Peter L. Bartlett, Wouter M. Koolen, Alan Malek, Eiji Takimoto, Manfred K. Warmuth [abs] [pdf]
Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions, Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin [abs] [pdf]
Bandit Convex Optimization: T√ Regret in One Dimension, Sébastien Bubeck, Ofer Dekel, Tomer Koren, Yuval Peres [abs] [pdf]
The entropic barrier: a simple and optimal universal self-concordant barrier, Sébastien Bubeck, Ronen Eldan [abs] [pdf]
Optimum Statistical Estimation with Strategic Data Sources, Yang Cai, Constantinos Daskalakis, Christos Papadimitriou [abs] [pdf]
On the Complexity of Learning with Kernels, Nicolò Cesa-Bianchi, Yishay Mansour, Ohad Shamir [abs] [pdf]
Learnability of Solutions to Conjunctive Queries: The Full Dichotomy, Hubie Chen, Matthew Valeriote [abs] [pdf]
Sequential Information Maximization: When is Greedy Near-optimal? Yuxin Chen, S. Hamed, Hassani, Amin Karbasi, Andreas Krause [abs] [pdf]
Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification, Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng [abs] [pdf]
Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery, Peter Chin, Anup Rao, Van Vu [abs] [pdf]
On-Line Learning Algorithms for Path Experts with Non-Additive Losses, Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Manfred Warmuth [abs] [pdf]
Truthful Linear Regression, Rachel Cummings, Stratis Ioannidis, Katrina Ligett, [abs] [pdf]
A PTAS for Agnostically Learning Halfspaces, Amit Daniely [abs] [pdf]
S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification, Gautam Dasarathy, Robert Nowak, Xiaojin Zhu [abs] [pdf]
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems, Yash Deshpande, Andrea Montanari [abs] [pdf]
Contextual Dueling Bandits, Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, Masrour Zoghi [abs] [pdf]
Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering, Justin Eldridge, Mikhail Belkin, Yusu Wang [abs] [pdf]
Faster Algorithms for Testing under Conditional Sampling, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh [abs] [pdf]
Learning and inference in the presence of corrupted inputs, Uriel Feige, Yishay Mansour, Robert Schapire [abs] [pdf]
From Averaging to Acceleration, There is Only a Step-size, Nicolas Flammarion, Francis Bach [abs] [pdf]
Variable Selection is Hard, Dean Foster, Howard Karloff, Justin Thaler [abs] [pdf]
Vector-Valued Property Elicitation, Rafael Frongillo, Ian A. Kash [abs] [pdf]
Competing with the Empirical Risk Minimizer in a Single Pass, Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford [abs] [pdf]
A Chaining Algorithm for Online Nonparametric Regression, Pierre Gaillard, Sébastien Gerchinovitz [abs] [pdf]
Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition, Rong Ge, Furong Huang, Chi Jin, Yang Yuan [abs] [pdf]
Learning the dependence structure of rare events: a non-asymptotic study, Nicolas Goix, Anne Sabourin, Stéphan Clémençon [abs] [pdf]
Thompson Sampling for Learning Parameterized Markov Decision Processes, Aditya Gopalan, Shie Mannor [abs] [pdf]
Computational Lower Bounds for Community Detection on Random Graphs, Bruce Hajek, Yihong Wu, Jiaming Xu [abs] [pdf]
Adaptive Recovery of Signals by Convex Optimization, Zaid Harchaoui, Anatoli Juditsky, Arkadi Nemirovski, Dmitry Ostrovsky [abs] [pdf]
Tensor principal component analysis via sum-of-square proofs, Samuel B. Hopkins, Jonathan Shi, David Steurer [abs] [pdf]
Fast Exact Matrix Completion with Finite Samples, Prateek Jain, Praneeth Netrapalli [abs] [pdf]
Exp-Concavity of Proper Composite Losses, Parameswaran Kamalaruban, Robert Williamson, Xinhua Zhang [abs] [pdf]
On Learning Distributions from their Samples, Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, Ananda Theertha Suresh [abs] [pdf]
MCMC Learning, Varun Kanade, Elchanan Mossel, [abs] [pdf]
Online with Spectral Bounds, Zohar Karnin, Edo Liberty, [abs] [pdf]
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem, Junpei Komiyama, Junya Honda, Hisashi Kashima, Hiroshi Nakagawa [abs] [pdf]
Second-order Quantile Methods for Experts and Combinatorial Games, Wouter M. Koolen, Tim Van Erven [abs] [pdf]
Hierarchical Label Queries with Data-Dependent Partitions, Samory Kpotufe, Ruth Urner, Shai Ben-David [abs] [pdf]
Algorithms for Lipschitz Learning on Graphs, Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman [abs] [pdf]
Low Rank Matrix Completion with Exponential Family Noise, Jean Lafond [abs] [pdf]
Bad Universal Priors and Notions of Optimality, Jan Leike, Marcus Hutter [abs] [pdf]
Learning with Square Loss: Localization through Offset Rademacher Complexity, Tengyuan Liang, Alexander Rakhlin, Karthik Sridharan [abs] [pdf]
Achieving All with No Parameters: AdaNormalHedge, Haipeng Luo, Robert E. Schapire [abs] [pdf]
Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization, Mehrdad Mahdavi, Lijun Zhang, Rong Jin [abs] [pdf]
Correlation Clustering with Noisy Partial Information Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan [abs] [pdf]
Online Density Estimation of Bradley-Terry Models, Issei Matsumoto, Kohei Hatano, Eiji Takimoto [abs] [pdf]
First-order regret bounds for combinatorial semi-bandits, Gergely Neu [abs] [pdf]
Norm-Based Capacity Control in Neural Networks, Behnam Neyshabur, Ryota Tomioka, Nathan Srebro [abs] [pdf]
Cortical Learning via Prediction, Christos H. Papadimitriou, Santosh S. Vempala [abs] [pdf]
Partitioning Well-Clustered Graphs: Spectral Clustering Works!, Richard Peng, He Sun, Luca Zanetti [abs] [pdf]
Batched Bandit Problems, Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg [abs] [pdf]
Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints, Alexander Rakhlin, Karthik Sridharan [abs] [pdf]
Fast Mixing for Discrete Point Processes, Patrick Rebeschini, Amin Karbasi [abs] [pdf]
Generalized Mixability via Entropic Duality, Mark D. Reid, Rafael M. Frongillo, Robert C. Williamson, Nishant Mehta [abs] [pdf]
On the Complexity of Bandit Linear Optimization, Ohad Shamir [abs] [pdf]
An Almost Optimal PAC Algorithm, Hans U. Simon [abs] [pdf]
Minimax rates for memory-bounded sparse linear regression, Jacob Steinhardt, John Duchi [abs] [pdf]
Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery, Thomas Steinke, Jonathan Ullman [abs] [pdf]
Convex Risk Minimization and Conditional Probability Estimation, Matus Telgarsky, Miroslav Dudík, Robert Schapire [abs] [pdf]
Regularized Linear Regression: A Precise Analysis of the Estimation Error, Christos Thrampoulidis, Samet Oymak, Babak Hassibi, [abs] [pdf]
Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity, Santosh S. Vempala, Ying. Xiao, [abs] [pdf]
On Convergence of Emphatic Temporal-Difference Learning, H. Yu, [abs] [pdf]

Open Problems

Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs, Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar, [abs] [pdf]
Open Problem: The landscape of the loss surfaces of multilayer networks, Anna, Choromanska, Yann, LeCun, Gérard Ben Arous [abs] [pdf]
Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings, Cristóbal Guzmán [abs] [pdf]
Open Problem: Online Sabotaged Shortest Path, Wouter M. Koolen, Manfred K. Warmuth, Dmitri Adamskiy, [abs] [pdf]
Open Problem: Learning Quantum Circuits with Queries, Jeremy Kun, Lev Reyzin, [abs] [pdf]
Open Problem: Recursive Teaching Dimension Versus VC Dimension, Hans U. Simon, Sandra Zilles, [abs] [pdf]