Conference on Learning Theory 2016: Preface

Vitaly Feldman, Alexander Rakhlin; 29th Annual Conference on Learning Theory, PMLR 49:1-3

[abs][Download PDF]

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

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar; 29th Annual Conference on Learning Theory, PMLR 49:1639-1642

[abs][Download PDF]

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

Lijie Chen, Jian Li; 29th Annual Conference on Learning Theory, PMLR 49:1643-1646

[abs][Download PDF]

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; 29th Annual Conference on Learning Theory, PMLR 49:1647-1650

[abs][Download PDF]

Open Problem: Second order regret bounds based on scaling time

Yoav Freund; 29th Annual Conference on Learning Theory, PMLR 49:1651-1654

[abs][Download PDF]

Open Problem: Property Elicitation and Elicitation Complexity

Rafael Frongillo, Ian Kash, Stephen Becker; 29th Annual Conference on Learning Theory, PMLR 49:1655-1658

[abs][Download PDF]

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

Francesco Orabona, Dávid Pál; 29th Annual Conference on Learning Theory, PMLR 49:1659-1664

[abs][Download PDF]

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

Shipra Agrawal, Nikhil R. Devanur, Lihong Li; 29th Annual Conference on Learning Theory, PMLR 49:4-18

[abs][Download PDF]

Learning and Testing Junta Distributions

Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld; 29th Annual Conference on Learning Theory, PMLR 49:19-46

[abs][Download PDF]

Sign rank versus VC dimension

Noga Alon, Shay Moran, Amir Yehudayoff; 29th Annual Conference on Learning Theory, PMLR 49:47-80

[abs][Download PDF]

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

Animashree Anandkumar, Rong Ge; 29th Annual Conference on Learning Theory, PMLR 49:81-102

[abs][Download PDF]

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

Nima Anari, Shayan Oveis Gharan, Alireza Rezaei; 29th Annual Conference on Learning Theory, PMLR 49:103-115

[abs][Download PDF]

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

Peter Auer, Chao-Kai Chiang; 29th Annual Conference on Learning Theory, PMLR 49:116-120

[abs][Download PDF]

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

Bernardo Ávila Pires, Csaba Szepesvári; 29th Annual Conference on Learning Theory, PMLR 49:121-151

[abs][Download PDF]

Learning and 1-bit Compressed Sensing under Asymmetric Noise

Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Hongyang Zhang; 29th Annual Conference on Learning Theory, PMLR 49:152-192

[abs][Download PDF]

Reinforcement Learning of POMDPs using Spectral Methods

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar; 29th Annual Conference on Learning Theory, PMLR 49:193-256

[abs][Download PDF]

Highly-Smooth Zero-th Order Online Optimization

Francis Bach, Vianney Perchet; 29th Annual Conference on Learning Theory, PMLR 49:257-283

[abs][Download PDF]

An Improved Gap-Dependency Analysis of the Noisy Power Method

Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, Adams Wei Yu; 29th Annual Conference on Learning Theory, PMLR 49:284-309

[abs][Download PDF]

Learning Combinatorial Functions from Pairwise Comparisons

Maria-Florina Balcan, Ellen Vitercik, Colin White; 29th Annual Conference on Learning Theory, PMLR 49:310-335

[abs][Download PDF]

Instance-dependent Regret Bounds for Dueling Bandits

Akshay Balsubramani, Zohar Karnin, Robert E. Schapire, Masrour Zoghi; 29th Annual Conference on Learning Theory, PMLR 49:336-360

[abs][Download PDF]

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

Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski; 29th Annual Conference on Learning Theory, PMLR 49:361-382

[abs][Download PDF]

Information-theoretic thresholds for community detection in sparse networks

Jess Banks, Cristopher Moore, Joe Neeman, Praneeth Netrapalli; 29th Annual Conference on Learning Theory, PMLR 49:383-416

[abs][Download PDF]

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak, Ankur Moitra; 29th Annual Conference on Learning Theory, PMLR 49:417-445

[abs][Download PDF]

Basis Learning as an Algorithmic Primitive

Mikhail Belkin, Luis Rademacher, James Voss; 29th Annual Conference on Learning Theory, PMLR 49:446-487

[abs][Download PDF]

Aggregation of supports along the Lasso path

Pierre C. Bellec; 29th Annual Conference on Learning Theory, PMLR 49:488-529

[abs][Download PDF]

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi; 29th Annual Conference on Learning Theory, PMLR 49:530-582

[abs][Download PDF]

Multi-scale exploration of convex functions and bandit convex optimization

Sébastien Bubeck, Ronen Eldan; 29th Annual Conference on Learning Theory, PMLR 49:583-589

[abs][Download PDF]

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

Alexandra Carpentier, Andrea Locatelli; 29th Annual Conference on Learning Theory, PMLR 49:590-604

[abs][Download PDF]

Delay and Cooperation in Nonstochastic Bandits

Nicol‘o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, Alberto Minora; 29th Annual Conference on Learning Theory, PMLR 49:605-622

[abs][Download PDF]

On the Approximability of Sparse PCA

Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein; 29th Annual Conference on Learning Theory, PMLR 49:623-646

[abs][Download PDF]

Pure Exploration of Multi-armed Bandit Under Matroid Constraints

Lijie Chen, Anupam Gupta, Jian Li; 29th Annual Conference on Learning Theory, PMLR 49:647-669

[abs][Download PDF]

Provably manipulation-resistant reputation systems

Paul Christiano; 29th Annual Conference on Learning Theory, PMLR 49:670-697

[abs][Download PDF]

On the Expressive Power of Deep Learning: A Tensor Analysis

Nadav Cohen, Or Sharir, Amnon Shashua; 29th Annual Conference on Learning Theory, PMLR 49:698-728

[abs][Download PDF]

A Light Touch for Heavily Constrained SGD

Andrew Cotter, Maya Gupta, Jan Pfeifer; 29th Annual Conference on Learning Theory, PMLR 49:729-771

[abs][Download PDF]

Adaptive Learning with Robust Generalization Guarantees

Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, Zhiwei Steven Wu; 29th Annual Conference on Learning Theory, PMLR 49:772-814

[abs][Download PDF]

Complexity Theoretic Limitations on Learning DNF’s

Amit Daniely, Shai Shalev-Shwartz; 29th Annual Conference on Learning Theory, PMLR 49:815-830

[abs][Download PDF]

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

I. Diakonikolas, D. M. Kane, A. Stewart; 29th Annual Conference on Learning Theory, PMLR 49:831-849

[abs][Download PDF]

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

I. Diakonikolas, D. M. Kane, A. Stewart; 29th Annual Conference on Learning Theory, PMLR 49:850-878

[abs][Download PDF]

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; 29th Annual Conference on Learning Theory, PMLR 49:879-906

[abs][Download PDF]

The Power of Depth for Feedforward Neural Networks

Ronen Eldan, Ohad Shamir; 29th Annual Conference on Learning Theory, PMLR 49:907-940

[abs][Download PDF]

Online Learning and Blackwell Approachability in Quitting Games

Janos Flesch, Rida Laraki, Vianney Perchet; 29th Annual Conference on Learning Theory, PMLR 49:941-942

[abs][Download PDF]

Spectral thresholds in the bipartite stochastic block model

Laura Florescu, Will Perkins; 29th Annual Conference on Learning Theory, PMLR 49:943-959

[abs][Download PDF]

Online Sparse Linear Regression

Dean Foster, Satyen Kale, Howard Karloff; 29th Annual Conference on Learning Theory, PMLR 49:960-970

[abs][Download PDF]

Preference-based Teaching

Ziyuan Gao, Christoph Ries, Hans Simon, Sandra Zilles; 29th Annual Conference on Learning Theory, PMLR 49:971-997

[abs][Download PDF]

Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier, Emilie Kaufmann; 29th Annual Conference on Learning Theory, PMLR 49:998-1027

[abs][Download PDF]

Maximin Action Identification: A New Bandit Framework for Games

Aurélien Garivier, Emilie Kaufmann, Wouter M. Koolen; 29th Annual Conference on Learning Theory, PMLR 49:1028-1050

[abs][Download PDF]

Semidefinite Programs for Exact Recovery of a Hidden Community

Bruce Hajek, Yihong Wu, Jiaming Xu; 29th Annual Conference on Learning Theory, PMLR 49:1051-1095

[abs][Download PDF]

Online Learning with Low Rank Experts

Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour; 29th Annual Conference on Learning Theory, PMLR 49:1096-1114

[abs][Download PDF]

Optimal rates for total variation denoising

Jan-Christian Hütter, Philippe Rigollet; 29th Annual Conference on Learning Theory, PMLR 49:1115-1146

[abs][Download PDF]

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; 29th Annual Conference on Learning Theory, PMLR 49:1147-1164

[abs][Download PDF]

Online Isotonic Regression

Wojciech Kotłowski, Wouter M. Koolen, Alan Malek; 29th Annual Conference on Learning Theory, PMLR 49:1165-1189

[abs][Download PDF]

Time series prediction and online learning

Vitaly Kuznetsov, Mehryar Mohri; 29th Annual Conference on Learning Theory, PMLR 49:1190-1213

[abs][Download PDF]

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

Tor Lattimore; 29th Annual Conference on Learning Theory, PMLR 49:1214-1245

[abs][Download PDF]

Gradient Descent Only Converges to Minimizers

Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht; 29th Annual Conference on Learning Theory, PMLR 49:1246-1257

[abs][Download PDF]

Learning Communities in the Presence of Errors

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan; 29th Annual Conference on Learning Theory, PMLR 49:1258-1291

[abs][Download PDF]

On the capacity of information processing systems

Laurent Massoulie, Kuang Xu; 29th Annual Conference on Learning Theory, PMLR 49:1292-1297

[abs][Download PDF]

Learning Simple Auctions

Jamie Morgenstern, Tim Roughgarden; 29th Annual Conference on Learning Theory, PMLR 49:1298-1318

[abs][Download PDF]

Density Evolution in the Degree-correlated Stochastic Block Model

Elchanan Mossel, Jiaming Xu; 29th Annual Conference on Learning Theory, PMLR 49:1319-1356

[abs][Download PDF]

Cortical Computation via Iterative Constructions

Christos Papadimitriou, Samantha Petti, Santosh Vempala; 29th Annual Conference on Learning Theory, PMLR 49:1357-1375

[abs][Download PDF]

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

Arun Rajkumar, Shivani Agarwal; 29th Annual Conference on Learning Theory, PMLR 49:1376-1401

[abs][Download PDF]

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

Andrej Risteski; 29th Annual Conference on Learning Theory, PMLR 49:1402-1416

[abs][Download PDF]

Simple Bayesian Algorithms for Best Arm Identification

Daniel Russo; 29th Annual Conference on Learning Theory, PMLR 49:1417-1418

[abs][Download PDF]

Interactive Algorithms: from Pool to Stream

Sivan Sabato, Tom Hess; 29th Annual Conference on Learning Theory, PMLR 49:1419-1439

[abs][Download PDF]

Best-of-K-bandits

Max Simchowitz, Kevin Jamieson, Benjamin Recht; 29th Annual Conference on Learning Theory, PMLR 49:1440-1489

[abs][Download PDF]

Memory, Communication, and Statistical Queries

Jacob Steinhardt, Gregory Valiant, Stefan Wager; 29th Annual Conference on Learning Theory, PMLR 49:1490-1516

[abs][Download PDF]

benefits of depth in neural networks

Matus Telgarsky; 29th Annual Conference on Learning Theory, PMLR 49:1517-1539

[abs][Download PDF]

A Guide to Learning Arithmetic Circuits

Ilya Volkovich; 29th Annual Conference on Learning Theory, PMLR 49:1540-1561

[abs][Download PDF]

Online learning in repeated auctions

Jonathan Weed, Vianney Perchet, Philippe Rigollet; 29th Annual Conference on Learning Theory, PMLR 49:1562-1583

[abs][Download PDF]

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

Chicheng Zhang, Kamalika Chaudhuri; 29th Annual Conference on Learning Theory, PMLR 49:1584-1616

[abs][Download PDF]

First-order Methods for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra; 29th Annual Conference on Learning Theory, PMLR 49:1617-1638

[abs][Download PDF]