[edit]

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

[edit]

Editors: Vitaly Feldman, Alexander Rakhlin, Ohad Shamir

[bib][citeproc]

Contents:

Preface

Conference on Learning Theory 2016: Preface

Vitaly Feldman, Alexander Rakhlin; 29th Annual Conference on Learning Theory, 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; 29th Annual Conference on Learning Theory, PMLR 49:1639-1642

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

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

Open Problem: Second order regret bounds based on scaling time

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

Open Problem: Property Elicitation and Elicitation Complexity

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

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

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

Learning and Testing Junta Distributions

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

Sign rank versus VC dimension

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

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

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

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

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

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

Reinforcement Learning of POMDPs using Spectral Methods

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

Highly-Smooth Zero-th Order Online Optimization

Francis Bach, Vianney Perchet; 29th Annual Conference on Learning Theory, 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; 29th Annual Conference on Learning Theory, PMLR 49:284-309

Learning Combinatorial Functions from Pairwise Comparisons

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

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

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

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

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

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

Basis Learning as an Algorithmic Primitive

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

Aggregation of supports along the Lasso path

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

Dropping Convexity for Faster Semi-definite Optimization

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

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

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

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

On the Approximability of Sparse PCA

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

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

Provably manipulation-resistant reputation systems

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

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

A Light Touch for Heavily Constrained SGD

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

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

Complexity Theoretic Limitations on Learning DNF’s

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

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

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

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

The Power of Depth for Feedforward Neural Networks

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

Online Learning and Blackwell Approachability in Quitting Games

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

Spectral thresholds in the bipartite stochastic block model

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

Online Sparse Linear Regression

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

Preference-based Teaching

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

Optimal Best Arm Identification with Fixed Confidence

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

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

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

Online Learning with Low Rank Experts

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

Optimal rates for total variation denoising

Jan-Christian Hütter, Philippe Rigollet; 29th Annual Conference on Learning Theory, 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; 29th Annual Conference on Learning Theory, PMLR 49:1147-1164

Online Isotonic Regression

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

Time series prediction and online learning

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

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

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

Learning Communities in the Presence of Errors

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

On the capacity of information processing systems

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

Learning Simple Auctions

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

Density Evolution in the Degree-correlated Stochastic Block Model

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

Cortical Computation via Iterative Constructions

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

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

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

Simple Bayesian Algorithms for Best Arm Identification

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

Interactive Algorithms: from Pool to Stream

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

Best-of-K-bandits

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

Memory, Communication, and Statistical Queries

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

benefits of depth in neural networks

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

A Guide to Learning Arithmetic Circuits

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

Online learning in repeated auctions

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

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

First-order Methods for Geodesically Convex Optimization

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

subscribe via RSS