COLT 2016

70 papers

First-order Methods for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra

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

Chicheng Zhang, Kamalika Chaudhuri

Online learning in repeated auctions

Jonathan Weed, Vianney Perchet, Philippe Rigollet

A Guide to Learning Arithmetic Circuits

Ilya Volkovich

benefits of depth in neural networks

Matus Telgarsky

Memory, Communication, and Statistical Queries

Jacob Steinhardt, Gregory Valiant, Stefan Wager

Best-of-K-bandits

Max Simchowitz, Kevin Jamieson, Benjamin Recht

Interactive Algorithms: from Pool to Stream

Sivan Sabato, Tom Hess

Simple Bayesian Algorithms for Best Arm Identification

Daniel Russo

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

Andrej Risteski

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

Arun Rajkumar, Shivani Agarwal

Cortical Computation via Iterative Constructions

Christos Papadimitriou, Samantha Petti, Santosh Vempala

Density Evolution in the Degree-correlated Stochastic Block Model

Elchanan Mossel, Jiaming Xu

Learning Simple Auctions

Jamie Morgenstern, Tim Roughgarden

On the capacity of information processing systems

Laurent Massoulié, Kuang Xu

Learning Communities in the Presence of Errors

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Gradient Descent Only Converges to Minimizers

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

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

Tor Lattimore

Time series prediction and online learning

Vitaly Kuznetsov, Mehryar Mohri

Online Isotonic Regression

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

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

Optimal rates for total variation denoising

Jan-Christian Hütter, Philippe Rigollet

Online Learning with Low Rank Experts

Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour

Semidefinite Programs for Exact Recovery of a Hidden Community

Bruce Hajek, Yihong Wu, Jiaming Xu

Maximin Action Identification: A New Bandit Framework for Games

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

Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier, Emilie Kaufmann

Preference-based Teaching

Ziyuan Gao, Christoph Ries, Hans Simon, Sandra Zilles

Online Sparse Linear Regression

Dean Foster, Satyen Kale, Howard Karloff

Spectral thresholds in the bipartite stochastic block model

Laura Florescu, Will Perkins

Online Learning and Blackwell Approachability in Quitting Games

Janos Flesch, Rida Laraki, Vianney Perchet

The Power of Depth for Feedforward Neural Networks

Ronen Eldan, Ohad Shamir

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

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

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

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

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

Complexity Theoretic Limitations on Learning DNF’s

Amit Daniely, Shai Shalev-shwartz

Adaptive Learning with Robust Generalization Guarantees

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

A Light Touch for Heavily Constrained SGD

Andrew Cotter, Maya Gupta, Jan Pfeifer

On the Expressive Power of Deep Learning: A Tensor Analysis

Nadav Cohen, Or Sharir, Amnon Shashua

Provably manipulation-resistant reputation systems

Paul Christiano

Pure Exploration of Multi-armed Bandit Under Matroid Constraints

Lijie Chen, Anupam Gupta, Jian Li

On the Approximability of Sparse PCA

Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein

Delay and Cooperation in Nonstochastic Bandits

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

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

Alexandra Carpentier, Andrea Locatelli

Multi-scale exploration of convex functions and bandit convex optimization

Sébastien Bubeck, Ronen Eldan

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi

Aggregation of supports along the Lasso path

Pierre C. Bellec

Basis Learning as an Algorithmic Primitive

Mikhail Belkin, Luis Rademacher, James Voss

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak, Ankur Moitra

Information-theoretic thresholds for community detection in sparse networks

Jess Banks, Cristopher Moore, Joe Neeman, Praneeth Netrapalli

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

Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski

Instance-dependent Regret Bounds for Dueling Bandits

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

Learning Combinatorial Functions from Pairwise Comparisons

Maria-Florina Balcan, Ellen Vitercik, Colin White

An Improved Gap-Dependency Analysis of the Noisy Power Method

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

Highly-Smooth Zero-th Order Online Optimization

Francis Bach, Vianney Perchet

Reinforcement Learning of POMDPs using Spectral Methods

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar

Learning and 1-bit Compressed Sensing under Asymmetric Noise

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

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

Bernardo Avila Pires, Csaba Szepesvári

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

Peter Auer, Chao-Kai Chiang

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

Nima Anari, Shayan Oveis Gharan, Alireza Rezaei

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

Animashree Anandkumar, Rong Ge

Sign rank versus VC dimension

Noga Alon, Shay Moran, Amir Yehudayoff

Learning and Testing Junta Distributions

Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld

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

Shipra Agrawal, Nikhil R. Devanur, Lihong Li

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

Francesco Orabona, Dávid Pál

Open Problem: Property Elicitation and Elicitation Complexity

Rafael Frongillo, Ian Kash, Stephen Becker

Open Problem: Second order regret bounds based on scaling time

Yoav Freund

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: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture

Lijie Chen, Jian Li

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

Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar

Conference on Learning Theory 2016: Preface

Vitaly Feldman, Alexander Rakhlin