Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

JMLR Workshop and Conference Proceedings

Volume 40: Proceedings of The 28th Conference on Learning Theory

Editors: Peter Grünwald, Elad Hazan, Satyen Kale

Contents:

Preface

Conference on Learning Theory 2015: Preface

Peter Grünwald, Elad Hazan

Regular Papers

On Consistent Surrogate Risk Minimization and Property Elicitation

Arpit Agarwal, Shivani Agarwal

Online Learning with Feedback Graphs: Beyond Bandits

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

Learning Overcomplete Latent Variable Models through Tensor Methods

Animashree Anandkumar, Rong Ge, Majid Janzamin

Simple, Efficient, and Neural Algorithms for Sparse Coding

Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra

Label optimal regret bounds for online local learning

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

Efficient Learning of Linear Separators under Bounded Noise

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

Efficient Representations for Lifelong Learning and Autoencoding

Maria-Florina Balcan, Avrim Blum, Santosh Vempala

Optimally Combining Classifiers Using Unlabeled Data

Akshay Balsubramani, Yoav Freund

Minimax Fixed-Design Linear Regression

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

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

Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin

Bandit Convex Optimization: \(\sqrt{T}\) Regret in One Dimension

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

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

Sébastien Bubeck, Ronen Eldan

Optimum Statistical Estimation with Strategic Data Sources

Yang Cai, Constantinos Daskalakis, Christos Papadimitriou

On the Complexity of Learning with Kernels

Nicolò Cesa-Bianchi, Yishay Mansour, Ohad Shamir

Learnability of Solutions to Conjunctive Queries: The Full Dichotomy

Hubie Chen, Matthew Valeriote

Sequential Information Maximization: When is Greedy Near-optimal?

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

Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification

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

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

Peter Chin, Anup Rao, Van Vu

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

Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Manfred Warmuth

Truthful Linear Regression

Rachel Cummings, Stratis Ioannidis, Katrina Ligett

A PTAS for Agnostically Learning Halfspaces

Amit Daniely

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

Gautam Dasarathy, Robert Nowak, Xiaojin Zhu

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

Yash Deshpande, Andrea Montanari

Contextual Dueling Bandits

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

Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

Justin Eldridge, Mikhail Belkin, Yusu Wang

Faster Algorithms for Testing under Conditional Sampling

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

Learning and inference in the presence of corrupted inputs

Uriel Feige, Yishay Mansour, Robert Schapire

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

Nicolas Flammarion, Francis Bach

Variable Selection is Hard

Dean Foster, Howard Karloff, Justin Thaler

Vector-Valued Property Elicitation

Rafael Frongillo, Ian A. Kash

Competing with the Empirical Risk Minimizer in a Single Pass

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

A Chaining Algorithm for Online Nonparametric Regression

Pierre Gaillard, Sébastien Gerchinovitz

Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition

Rong Ge, Furong Huang, Chi Jin, Yang Yuan

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

Nicolas Goix, Anne Sabourin, Stéphan Clémençon

Thompson Sampling for Learning Parameterized Markov Decision Processes

Aditya Gopalan, Shie Mannor

Computational Lower Bounds for Community Detection on Random Graphs

Bruce Hajek, Yihong Wu, Jiaming Xu

Adaptive Recovery of Signals by Convex Optimization

Zaid Harchaoui, Anatoli Juditsky, Arkadi Nemirovski, Dmitry Ostrovsky

Tensor principal component analysis via sum-of-square proofs

Samuel B. Hopkins, Jonathan Shi, David Steurer

Fast Exact Matrix Completion with Finite Samples

Prateek Jain, Praneeth Netrapalli

Exp-Concavity of Proper Composite Losses

Parameswaran Kamalaruban, Robert Williamson, Xinhua Zhang

On Learning Distributions from their Samples

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

MCMC Learning

Varun Kanade, Elchanan Mossel

Online PCA with Spectral Bounds

Zohar Karnin, Edo Liberty

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

Junpei Komiyama, Junya Honda, Hisashi Kashima, Hiroshi Nakagawa

Second-order Quantile Methods for Experts and Combinatorial Games

Wouter M. Koolen, Tim Van Erven

Hierarchical Label Queries with Data-Dependent Partitions

Samory Kpotufe, Ruth Urner, Shai Ben-David

Algorithms for Lipschitz Learning on Graphs

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

Low Rank Matrix Completion with Exponential Family Noise

Jean Lafond

Bad Universal Priors and Notions of Optimality

Jan Leike, Marcus Hutter

Learning with Square Loss: Localization through Offset Rademacher Complexity

Tengyuan Liang, Alexander Rakhlin, Karthik Sridharan

Achieving All with No Parameters: AdaNormalHedge

Haipeng Luo, Robert E. Schapire

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

Mehrdad Mahdavi, Lijun Zhang, Rong Jin

Correlation Clustering with Noisy Partial Information

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Online Density Estimation of Bradley-Terry Models

Issei Matsumoto, Kohei Hatano, Eiji Takimoto

First-order regret bounds for combinatorial semi-bandits

Gergely Neu

Norm-Based Capacity Control in Neural Networks

Behnam Neyshabur, Ryota Tomioka, Nathan Srebro

Cortical Learning via Prediction

Christos H. Papadimitriou, Santosh S. Vempala

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Richard Peng, He Sun, Luca Zanetti

Batched Bandit Problems

Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg

Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints

Alexander Rakhlin, Karthik Sridharan

Fast Mixing for Discrete Point Processes

Patrick Rebeschini, Amin Karbasi

Generalized Mixability via Entropic Duality

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

On the Complexity of Bandit Linear Optimization

Ohad Shamir

An Almost Optimal PAC Algorithm

Hans U. Simon

Minimax rates for memory-bounded sparse linear regression

Jacob Steinhardt, John Duchi

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Thomas Steinke, Jonathan Ullman

Convex Risk Minimization and Conditional Probability Estimation

Matus Telgarsky, Miroslav Dudík, Robert Schapire

Regularized Linear Regression: A Precise Analysis of the Estimation Error

Christos Thrampoulidis, Samet Oymak, Babak Hassibi

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

Santosh S. Vempala, Ying. Xiao

On Convergence of Emphatic Temporal-Difference Learning

H. Yu

Open Problems

Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs

Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar

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

Anna, Choromanska, Yann, LeCun, Gérard Ben Arous

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

Cristóbal Guzmán

Open Problem: Online Sabotaged Shortest Path

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

Open Problem: Learning Quantum Circuits with Queries

Jeremy Kun, Lev Reyzin

Open Problem: Recursive Teaching Dimension Versus VC Dimension

Hans U. Simon, Sandra Zilles