Conference on Learning Theory 2015: Preface

Peter Grünwald, Elad Hazan; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1-3

[abs][Download PDF]

Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs

Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1752-1755

[abs][Download PDF]

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

Anna Choromanska, Yann LeCun, Gérard Ben Arous; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1756-1760

[abs][Download PDF]

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

Cristóbal Guzmán; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1761-1763

[abs][Download PDF]

Open Problem: Online Sabotaged Shortest Path

Wouter M. Koolen, Manfred K. Warmuth, Dmitri Adamskiy; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1764-1766

[abs][Download PDF]

Open Problem: Learning Quantum Circuits with Queries

Jeremy Kun, Lev Reyzin; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1767-1769

[abs][Download PDF]

Open Problem: Recursive Teaching Dimension Versus VC Dimension

Hans U. Simon, Sandra Zilles; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1770-1772

[abs][Download PDF]

On Consistent Surrogate Risk Minimization and Property Elicitation

Arpit Agarwal, Shivani Agarwal; Proceedings of The 28th Conference on Learning Theory, PMLR 40:4-22

[abs][Download PDF]

Online Learning with Feedback Graphs: Beyond Bandits

Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, Tomer Koren; Proceedings of The 28th Conference on Learning Theory, PMLR 40:23-35

[abs][Download PDF]

Learning Overcomplete Latent Variable Models through Tensor Methods

Animashree Anandkumar, Rong Ge, Majid Janzamin; Proceedings of The 28th Conference on Learning Theory, PMLR 40:36-112

[abs][Download PDF]

Simple, Efficient, and Neural Algorithms for Sparse Coding

Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra; Proceedings of The 28th Conference on Learning Theory, PMLR 40:113-149

[abs][Download PDF]

Label optimal regret bounds for online local learning

Pranjal Awasthi, Moses Charikar, Kevin A Lai, Andrej Risteski; Proceedings of The 28th Conference on Learning Theory, PMLR 40:150-166

[abs][Download PDF]

Efficient Learning of Linear Separators under Bounded Noise

Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Ruth Urner; Proceedings of The 28th Conference on Learning Theory, PMLR 40:167-190

[abs][Download PDF]

Efficient Representations for Lifelong Learning and Autoencoding

Maria-Florina Balcan, Avrim Blum, Santosh Vempala; Proceedings of The 28th Conference on Learning Theory, PMLR 40:191-210

[abs][Download PDF]

Optimally Combining Classifiers Using Unlabeled Data

Akshay Balsubramani, Yoav Freund; Proceedings of The 28th Conference on Learning Theory, PMLR 40:211-225

[abs][Download PDF]

Minimax Fixed-Design Linear Regression

Peter L. Bartlett, Wouter M. Koolen, Alan Malek, Eiji Takimoto, Manfred K. Warmuth; Proceedings of The 28th Conference on Learning Theory, PMLR 40:226-239

[abs][Download PDF]

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

Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin; Proceedings of The 28th Conference on Learning Theory, PMLR 40:240-265

[abs][Download PDF]

Bandit Convex Optimization: \sqrtT Regret in One Dimension

Sébastien Bubeck, Ofer Dekel, Tomer Koren, Yuval Peres; Proceedings of The 28th Conference on Learning Theory, PMLR 40:266-278

[abs][Download PDF]

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

Sébastien Bubeck, Ronen Eldan; Proceedings of The 28th Conference on Learning Theory, PMLR 40:279-279

[abs][Download PDF]

Optimum Statistical Estimation with Strategic Data Sources

Yang Cai, Constantinos Daskalakis, Christos Papadimitriou; Proceedings of The 28th Conference on Learning Theory, PMLR 40:280-296

[abs][Download PDF]

On the Complexity of Learning with Kernels

Nicolò Cesa-Bianchi, Yishay Mansour, Ohad Shamir; Proceedings of The 28th Conference on Learning Theory, PMLR 40:297-325

[abs][Download PDF]

Learnability of Solutions to Conjunctive Queries: The Full Dichotomy

Hubie Chen, Matthew Valeriote; Proceedings of The 28th Conference on Learning Theory, PMLR 40:326-337

[abs][Download PDF]

Sequential Information Maximization: When is Greedy Near-optimal?

Yuxin Chen, S. Hamed Hassani, Amin Karbasi, Andreas Krause; Proceedings of The 28th Conference on Learning Theory, PMLR 40:338-363

[abs][Download PDF]

Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification

Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng; Proceedings of The 28th Conference on Learning Theory, PMLR 40:364-390

[abs][Download PDF]

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

Peter Chin, Anup Rao, Van Vu; Proceedings of The 28th Conference on Learning Theory, PMLR 40:391-423

[abs][Download PDF]

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

Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Manfred Warmuth; Proceedings of The 28th Conference on Learning Theory, PMLR 40:424-447

[abs][Download PDF]

Truthful Linear Regression

Rachel Cummings, Stratis Ioannidis, Katrina Ligett; Proceedings of The 28th Conference on Learning Theory, PMLR 40:448-483

[abs][Download PDF]

A PTAS for Agnostically Learning Halfspaces

Amit Daniely; Proceedings of The 28th Conference on Learning Theory, PMLR 40:484-502

[abs][Download PDF]

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

Gautam Dasarathy, Robert Nowak, Xiaojin Zhu; Proceedings of The 28th Conference on Learning Theory, PMLR 40:503-522

[abs][Download PDF]

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

Yash Deshpande, Andrea Montanari; Proceedings of The 28th Conference on Learning Theory, PMLR 40:523-562

[abs][Download PDF]

Contextual Dueling Bandits

Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, Masrour Zoghi; Proceedings of The 28th Conference on Learning Theory, PMLR 40:563-587

[abs][Download PDF]

Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

Justin Eldridge, Mikhail Belkin, Yusu Wang; Proceedings of The 28th Conference on Learning Theory, PMLR 40:588-606

[abs][Download PDF]

Faster Algorithms for Testing under Conditional Sampling

Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh; Proceedings of The 28th Conference on Learning Theory, PMLR 40:607-636

[abs][Download PDF]

Learning and inference in the presence of corrupted inputs

Uriel Feige, Yishay Mansour, Robert Schapire; Proceedings of The 28th Conference on Learning Theory, PMLR 40:637-657

[abs][Download PDF]

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

Nicolas Flammarion, Francis Bach; Proceedings of The 28th Conference on Learning Theory, PMLR 40:658-695

[abs][Download PDF]

Variable Selection is Hard

Dean Foster, Howard Karloff, Justin Thaler; Proceedings of The 28th Conference on Learning Theory, PMLR 40:696-709

[abs][Download PDF]

Vector-Valued Property Elicitation

Rafael Frongillo, Ian A. Kash; Proceedings of The 28th Conference on Learning Theory, PMLR 40:710-727

[abs][Download PDF]

Competing with the Empirical Risk Minimizer in a Single Pass

Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford; Proceedings of The 28th Conference on Learning Theory, PMLR 40:728-763

[abs][Download PDF]

A Chaining Algorithm for Online Nonparametric Regression

Pierre Gaillard, Sébastien Gerchinovitz; Proceedings of The 28th Conference on Learning Theory, PMLR 40:764-796

[abs][Download PDF]

Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition

Rong Ge, Furong Huang, Chi Jin, Yang Yuan; Proceedings of The 28th Conference on Learning Theory, PMLR 40:797-842

[abs][Download PDF]

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

Nicolas Goix, Anne Sabourin, Stéphan Clémen\ccon; Proceedings of The 28th Conference on Learning Theory, PMLR 40:843-860

[abs][Download PDF]

Thompson Sampling for Learning Parameterized Markov Decision Processes

Aditya Gopalan, Shie Mannor; Proceedings of The 28th Conference on Learning Theory, PMLR 40:861-898

[abs][Download PDF]

Computational Lower Bounds for Community Detection on Random Graphs

Bruce Hajek, Yihong Wu, Jiaming Xu; Proceedings of The 28th Conference on Learning Theory, PMLR 40:899-928

[abs][Download PDF]

Adaptive Recovery of Signals by Convex Optimization

Zaid Harchaoui, Anatoli Juditsky, Arkadi Nemirovski, Dmitry Ostrovsky; Proceedings of The 28th Conference on Learning Theory, PMLR 40:929-955

[abs][Download PDF]

Tensor principal component analysis via sum-of-square proofs

Samuel B. Hopkins, Jonathan Shi, David Steurer; Proceedings of The 28th Conference on Learning Theory, PMLR 40:956-1006

[abs][Download PDF]

Fast Exact Matrix Completion with Finite Samples

Prateek Jain, Praneeth Netrapalli; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1007-1034

[abs][Download PDF]

Exp-Concavity of Proper Composite Losses

Parameswaran Kamalaruban, Robert Williamson, Xinhua Zhang; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1035-1065

[abs][Download PDF]

On Learning Distributions from their Samples

Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, Ananda Theertha Suresh; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1066-1100

[abs][Download PDF]

MCMC Learning

Varun Kanade, Elchanan Mossel; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1101-1128

[abs][Download PDF]

Online PCA with Spectral Bounds

Zohar Karnin, Edo Liberty; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1129-1140

[abs][Download PDF]

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

Junpei Komiyama, Junya Honda, Hisashi Kashima, Hiroshi Nakagawa; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1141-1154

[abs][Download PDF]

Second-order Quantile Methods for Experts and Combinatorial Games

Wouter M. Koolen, Tim Van Erven; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1155-1175

[abs][Download PDF]

Hierarchical Label Queries with Data-Dependent Partitions

Samory Kpotufe, Ruth Urner, Shai Ben-David; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1176-1189

[abs][Download PDF]

Algorithms for Lipschitz Learning on Graphs

Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1190-1223

[abs][Download PDF]

Low Rank Matrix Completion with Exponential Family Noise

Jean Lafond; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1224-1243

[abs][Download PDF]

Bad Universal Priors and Notions of Optimality

Jan Leike, Marcus Hutter; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1244-1259

[abs][Download PDF]

Learning with Square Loss: Localization through Offset Rademacher Complexity

Tengyuan Liang, Alexander Rakhlin, Karthik Sridharan; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1260-1285

[abs][Download PDF]

Achieving All with No Parameters: AdaNormalHedge

Haipeng Luo, Robert E. Schapire; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1286-1304

[abs][Download PDF]

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

Mehrdad Mahdavi, Lijun Zhang, Rong Jin; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1305-1320

[abs][Download PDF]

Correlation Clustering with Noisy Partial Information

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1321-1342

[abs][Download PDF]

Online Density Estimation of Bradley-Terry Models

Issei Matsumoto, Kohei Hatano, Eiji Takimoto; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1343-1359

[abs][Download PDF]

First-order regret bounds for combinatorial semi-bandits

Gergely Neu; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1360-1375

[abs][Download PDF]

Norm-Based Capacity Control in Neural Networks

Behnam Neyshabur, Ryota Tomioka, Nathan Srebro; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1376-1401

[abs][Download PDF]

Cortical Learning via Prediction

Christos H. Papadimitriou, Santosh S. Vempala; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1402-1422

[abs][Download PDF]

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

Richard Peng, He Sun, Luca Zanetti; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1423-1455

[abs][Download PDF]

Batched Bandit Problems

Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1456-1456

[abs][Download PDF]

Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints

Alexander Rakhlin, Karthik Sridharan; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1457-1479

[abs][Download PDF]

Fast Mixing for Discrete Point Processes

Patrick Rebeschini, Amin Karbasi; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1480-1500

[abs][Download PDF]

Generalized Mixability via Entropic Duality

Mark D. Reid, Rafael M. Frongillo, Robert C. Williamson, Nishant Mehta; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1501-1522

[abs][Download PDF]

On the Complexity of Bandit Linear Optimization

Ohad Shamir; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1523-1551

[abs][Download PDF]

An Almost Optimal PAC Algorithm

Hans U. Simon; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1552-1563

[abs][Download PDF]

Minimax rates for memory-bounded sparse linear regression

Jacob Steinhardt, John Duchi; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1564-1587

[abs][Download PDF]

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Thomas Steinke, Jonathan Ullman; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1588-1628

[abs][Download PDF]

Convex Risk Minimization and Conditional Probability Estimation

Matus Telgarsky, Miroslav Dudík, Robert Schapire; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1629-1682

[abs][Download PDF]

Regularized Linear Regression: A Precise Analysis of the Estimation Error

Christos Thrampoulidis, Samet Oymak, Babak Hassibi; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1683-1709

[abs][Download PDF]

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

Santosh S. Vempala, Ying. Xiao; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1710-1723

[abs][Download PDF]

On Convergence of Emphatic Temporal-Difference Learning

H. Yu; Proceedings of The 28th Conference on Learning Theory, PMLR 40:1724-1751

[abs][Download PDF]