Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

JMLR Workshop and Conference Proceedings

Volume 49: 29th Annual Conference on Learning Theory

Editors: Vitaly Feldman, Alexander Rakhlin, Ohad Shamir

Contents:

Preface

Conference on Learning Theory 2016: Preface

Vitaly Feldman, Alexander Rakhlin

Regular Papers

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

Shipra Agrawal, Nikhil R. Devanur, Lihong Li

Learning and Testing Junta Distributions

Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld

Sign rank versus VC dimension

Noga Alon, Shay Moran, Amir Yehudayoff

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

Animashree Anandkumar, Rong Ge

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

Nima Anari, Shayan Oveis Gharan, Alireza Rezaei

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

Peter Auer, Chao-Kai Chiang

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

Bernardo Ávila Pires, Csaba Szepesvári

Learning and 1-bit Compressed Sensing under Asymmetric Noise

Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Hongyang Zhang

Reinforcement Learning of POMDPs using Spectral Methods

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar

Highly-Smooth Zero-th Order Online Optimization

Francis Bach, Vianney Perchet

An Improved Gap-Dependency Analysis of the Noisy Power Method

Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, Adams Wei Yu

Learning Combinatorial Functions from Pairwise Comparisons

Maria-Florina Balcan, Ellen Vitercik, Colin White

Instance-dependent Regret Bounds for Dueling Bandits

Akshay Balsubramani, Zohar Karnin, Robert E. Schapire, Masrour Zoghi

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

Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski

Information-theoretic thresholds for community detection in sparse networks

Jess Banks, Cristopher Moore, Joe Neeman, Praneeth Netrapalli

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak, Ankur Moitra

Basis Learning as an Algorithmic Primitive

Mikhail Belkin, Luis Rademacher, James Voss

Aggregation of supports along the Lasso path

Pierre C. Bellec

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi

Multi-scale exploration of convex functions and bandit convex optimization

Sébastien Bubeck, Ronen Eldan

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

Alexandra Carpentier, Andrea Locatelli

Delay and Cooperation in Nonstochastic Bandits

Nicol`o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, Alberto Minora

On the Approximability of Sparse PCA

Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein

Pure Exploration of Multi-armed Bandit Under Matroid Constraints

Lijie Chen, Anupam Gupta, Jian Li

Provably manipulation-resistant reputation systems

Paul Christiano

On the Expressive Power of Deep Learning: A Tensor Analysis

Nadav Cohen, Or Sharir, Amnon Shashua

A Light Touch for Heavily Constrained SGD

Andrew Cotter, Maya Gupta, Jan Pfeifer

Adaptive Learning with Robust Generalization Guarantees

Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, Zhiwei Steven Wu

Complexity Theoretic Limitations on Learning DNF’s

Amit Daniely, Shai Shalev-Shwartz

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

I. Diakonikolas, D. M. Kane, A. Stewart

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

I. Diakonikolas, D. M. Kane, A. Stewart

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

The Power of Depth for Feedforward Neural Networks

Ronen Eldan, Ohad Shamir

Online Learning and Blackwell Approachability in Quitting Games

Janos Flesch, Rida Laraki, Vianney Perchet

Spectral thresholds in the bipartite stochastic block model

Laura Florescu, Will Perkins

Online Sparse Linear Regression

Dean Foster, Satyen Kale, Howard Karloff

Preference-based Teaching

Ziyuan Gao, Christoph Ries, Hans Simon, Sandra Zilles

Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier, Emilie Kaufmann

Maximin Action Identification: A New Bandit Framework for Games

Aurélien Garivier, Emilie Kaufmann, Wouter M. Koolen

Semidefinite Programs for Exact Recovery of a Hidden Community

Bruce Hajek, Yihong Wu, Jiaming Xu

Online Learning with Low Rank Experts

Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour

Optimal rates for total variation denoising

Jan-Christian Hütter, Philippe Rigollet

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

Online Isotonic Regression

Wojciech Kotłowski, Wouter M. Koolen, Alan Malek

Time series prediction and online learning

Vitaly Kuznetsov, Mehryar Mohri

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

Tor Lattimore

Gradient Descent Only Converges to Minimizers

Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht

Learning Communities in the Presence of Errors

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

On the capacity of information processing systems

Laurent Massoulie, Kuang Xu

Learning Simple Auctions

Jamie Morgenstern, Tim Roughgarden

Density Evolution in the Degree-correlated Stochastic Block Model

Elchanan Mossel, Jiaming Xu

Cortical Computation via Iterative Constructions

Christos Papadimitriou, Samantha Petti, Santosh Vempala

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

Arun Rajkumar, Shivani Agarwal

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

Andrej Risteski

Simple Bayesian Algorithms for Best Arm Identification

Daniel Russo

Interactive Algorithms: from Pool to Stream

Sivan Sabato, Tom Hess

Best-of-K-bandits

Max Simchowitz, Kevin Jamieson, Benjamin Recht

Memory, Communication, and Statistical Queries

Jacob Steinhardt, Gregory Valiant, Stefan Wager

benefits of depth in neural networks

Matus Telgarsky

A Guide to Learning Arithmetic Circuits

Ilya Volkovich

Online learning in repeated auctions

Jonathan Weed, Vianney Perchet, Philippe Rigollet

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

Chicheng Zhang, Kamalika Chaudhuri

First-order Methods for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra

Open Problems

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

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar

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

Lijie Chen, Jian Li

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

Open Problem: Second order regret bounds based on scaling time

Yoav Freund

Open Problem: Property Elicitation and Elicitation Complexity

Rafael Frongillo, Ian Kash, Stephen Becker

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

Francesco Orabona, Dávid Pál