Volume 49: Conference on Learning Theory, 23-26 June 2016, Columbia University, New York, New York, USA


Editors: Vitaly Feldman, Alexander Rakhlin, Ohad Shamir




Conference on Learning Theory 2016: Preface

Vitaly Feldman, Alexander Rakhlin; PMLR 49:1-3

Regular Papers

Open Problems

Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar; PMLR 49:1639-1642

Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture

Lijie Chen, Jian Li; PMLR 49:1643-1646

Open Problem: Kernel methods on manifolds and metric spaces. What is the probability of a positive definite geodesic exponential kernel?

Aasa Feragen, Søren Hauberg; PMLR 49:1647-1650

Open Problem: Second order regret bounds based on scaling time

Yoav Freund; PMLR 49:1651-1654

Open Problem: Property Elicitation and Elicitation Complexity

Rafael Frongillo, Ian Kash, Stephen Becker; PMLR 49:1655-1658

Open Problem: Parameter-Free and Scale-Free Online Algorithms

Francesco Orabona, Dávid Pál; PMLR 49:1659-1664

An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives

Shipra Agrawal, Nikhil R. Devanur, Lihong Li; PMLR 49:4-18

Learning and Testing Junta Distributions

Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld; PMLR 49:19-46

Sign rank versus VC dimension

Noga Alon, Shay Moran, Amir Yehudayoff; PMLR 49:47-80

Efficient approaches for escaping higher order saddle points in non-convex optimization

Animashree Anandkumar, Rong Ge; PMLR 49:81-102

Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes

Nima Anari, Shayan Oveis Gharan, Alireza Rezaei; PMLR 49:103-115

An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits

Peter Auer, Chao-Kai Chiang; PMLR 49:116-120

Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models

Bernardo Ávila Pires, Csaba Szepesvári; PMLR 49:121-151

Learning and 1-bit Compressed Sensing under Asymmetric Noise

Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Hongyang Zhang; PMLR 49:152-192

Reinforcement Learning of POMDPs using Spectral Methods

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar; PMLR 49:193-256

Highly-Smooth Zero-th Order Online Optimization

Francis Bach, Vianney Perchet; PMLR 49:257-283

An Improved Gap-Dependency Analysis of the Noisy Power Method

Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, Adams Wei Yu; PMLR 49:284-309

Learning Combinatorial Functions from Pairwise Comparisons

Maria-Florina Balcan, Ellen Vitercik, Colin White; PMLR 49:310-335

Instance-dependent Regret Bounds for Dueling Bandits

Akshay Balsubramani, Zohar Karnin, Robert E. Schapire, Masrour Zoghi; PMLR 49:336-360

On the low-rank approach for semidefinite programs arising in synchronization and community detection

Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski; PMLR 49:361-382

Information-theoretic thresholds for community detection in sparse networks

Jess Banks, Cristopher Moore, Joe Neeman, Praneeth Netrapalli; PMLR 49:383-416

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak, Ankur Moitra; PMLR 49:417-445

Basis Learning as an Algorithmic Primitive

Mikhail Belkin, Luis Rademacher, James Voss; PMLR 49:446-487

Aggregation of supports along the Lasso path

Pierre C. Bellec; PMLR 49:488-529

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi; PMLR 49:530-582

Multi-scale exploration of convex functions and bandit convex optimization

Sébastien Bubeck, Ronen Eldan; PMLR 49:583-589

Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem

Alexandra Carpentier, Andrea Locatelli; PMLR 49:590-604

Delay and Cooperation in Nonstochastic Bandits

Nicol‘o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, Alberto Minora; PMLR 49:605-622

On the Approximability of Sparse PCA

Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein; PMLR 49:623-646

Pure Exploration of Multi-armed Bandit Under Matroid Constraints

Lijie Chen, Anupam Gupta, Jian Li; PMLR 49:647-669

Provably manipulation-resistant reputation systems

Paul Christiano; PMLR 49:670-697

On the Expressive Power of Deep Learning: A Tensor Analysis

Nadav Cohen, Or Sharir, Amnon Shashua; PMLR 49:698-728

A Light Touch for Heavily Constrained SGD

Andrew Cotter, Maya Gupta, Jan Pfeifer; PMLR 49:729-771

Adaptive Learning with Robust Generalization Guarantees

Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, Zhiwei Steven Wu; PMLR 49:772-814

Complexity Theoretic Limitations on Learning DNF’s

Amit Daniely, Shai Shalev-Shwartz; PMLR 49:815-830

Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables

I. Diakonikolas, D. M. Kane, A. Stewart; PMLR 49:831-849

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

I. Diakonikolas, D. M. Kane, A. Stewart; PMLR 49:850-878

Asymptotic behavior of \ell_p-based Laplacian regularization in semi-supervised learning

Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J. Wainwright, Michael I. Jordan; PMLR 49:879-906

The Power of Depth for Feedforward Neural Networks

Ronen Eldan, Ohad Shamir; PMLR 49:907-940

Online Learning and Blackwell Approachability in Quitting Games

Janos Flesch, Rida Laraki, Vianney Perchet; PMLR 49:941-942

Spectral thresholds in the bipartite stochastic block model

Laura Florescu, Will Perkins; PMLR 49:943-959

Online Sparse Linear Regression

Dean Foster, Satyen Kale, Howard Karloff; PMLR 49:960-970

Preference-based Teaching

Ziyuan Gao, Christoph Ries, Hans Simon, Sandra Zilles; PMLR 49:971-997

Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier, Emilie Kaufmann; PMLR 49:998-1027

Maximin Action Identification: A New Bandit Framework for Games

Aurélien Garivier, Emilie Kaufmann, Wouter M. Koolen; PMLR 49:1028-1050

Semidefinite Programs for Exact Recovery of a Hidden Community

Bruce Hajek, Yihong Wu, Jiaming Xu; PMLR 49:1051-1095

Online Learning with Low Rank Experts

Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour; PMLR 49:1096-1114

Optimal rates for total variation denoising

Jan-Christian Hütter, Philippe Rigollet; PMLR 49:1115-1146

Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm

Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford; PMLR 49:1147-1164

Online Isotonic Regression

Wojciech Kotłowski, Wouter M. Koolen, Alan Malek; PMLR 49:1165-1189

Time series prediction and online learning

Vitaly Kuznetsov, Mehryar Mohri; PMLR 49:1190-1213

Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits

Tor Lattimore; PMLR 49:1214-1245

Gradient Descent Only Converges to Minimizers

Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht; PMLR 49:1246-1257

Learning Communities in the Presence of Errors

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan; PMLR 49:1258-1291

On the capacity of information processing systems

Laurent Massoulie, Kuang Xu; PMLR 49:1292-1297

Learning Simple Auctions

Jamie Morgenstern, Tim Roughgarden; PMLR 49:1298-1318

Density Evolution in the Degree-correlated Stochastic Block Model

Elchanan Mossel, Jiaming Xu; PMLR 49:1319-1356

Cortical Computation via Iterative Constructions

Christos Papadimitriou, Samantha Petti, Santosh Vempala; PMLR 49:1357-1375

When can we rank well from comparisons of O(n\log(n)) non-actively chosen pairs?

Arun Rajkumar, Shivani Agarwal; PMLR 49:1376-1401

How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods

Andrej Risteski; PMLR 49:1402-1416

Simple Bayesian Algorithms for Best Arm Identification

Daniel Russo; PMLR 49:1417-1418

Interactive Algorithms: from Pool to Stream

Sivan Sabato, Tom Hess; PMLR 49:1419-1439


Max Simchowitz, Kevin Jamieson, Benjamin Recht; PMLR 49:1440-1489

Memory, Communication, and Statistical Queries

Jacob Steinhardt, Gregory Valiant, Stefan Wager; PMLR 49:1490-1516

benefits of depth in neural networks

Matus Telgarsky; PMLR 49:1517-1539

A Guide to Learning Arithmetic Circuits

Ilya Volkovich; PMLR 49:1540-1561

Online learning in repeated auctions

Jonathan Weed, Vianney Perchet, Philippe Rigollet; PMLR 49:1562-1583

The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions

Chicheng Zhang, Kamalika Chaudhuri; PMLR 49:1584-1616

First-order Methods for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra; PMLR 49:1617-1638

subscribe via RSS