COLT 2016

69 papers

A Guide to Learning Arithmetic Circuits Ilya Volkovich

A Light Touch for Heavily Constrained SGD Andrew Cotter, Maya R. Gupta, Jan Pfeifer

Adaptive Learning with Robust Generalization Guarantees Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, Zhiwei Steven Wu

Aggregation of Supports Along the Lasso Path Pierre C. Bellec

An Algorithm with Nearly Optimal Pseudo-Regret for Both Stochastic and Adversarial Bandits Peter Auer, Chao-Kai Chiang

An Efficient Algorithm for Contextual Bandits with Knapsacks, and an Extension to Concave Objectives Shipra Agrawal, Nikhil R. Devanur, Lihong Li

An Improved Gap-Dependency Analysis of the Noisy Power Method Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, Adams Wei Yu

Asymptotic Behavior of \(\ell_p\)-Based Laplacian Regularization in Semi-Supervised Learning Ahmed El Alaoui

Basis Learning as an Algorithmic Primitive Mikhail Belkin, Luis Rademacher, James R. Voss

Benefits of Depth in Neural Networks Matus Telgarsky

Best-of-K-Bandits Max Simchowitz, Kevin G. Jamieson, Benjamin Recht

Complexity Theoretic Limitations on Learning DNF's Amit Daniely, Shai Shalev-Shwartz

Cortical Computation via Iterative Constructions Christos H. Papadimitriou, Samantha Petti, Santosh S. Vempala

Delay and Cooperation in Nonstochastic Bandits Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour, Alberto Minora

Density Evolution in the Degree-Correlated Stochastic Block Model Elchanan Mossel, Jiaming Xu

Dropping Convexity for Faster Semi-Definite Optimization Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi

Efficient Approaches for Escaping Higher Order Saddle Points in Non-Convex Optimization Animashree Anandkumar, Rong Ge

First-Order Methods for Geodesically Convex Optimization Hongyi Zhang, Suvrit Sra

Gradient Descent Only Converges to Minimizers Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht

Highly-Smooth Zero-Th Order Online Optimization Francis R. Bach, Vianney Perchet

How to Calculate Partition Functions Using Convex Programming Hierarchies: Provable Bounds for Variational Methods Andrej Risteski

Information-Theoretic Thresholds for Community Detection in Sparse Networks Jess Banks, Cristopher Moore, Joe Neeman, Praneeth Netrapalli

Instance-Dependent Regret Bounds for Dueling Bandits Akshay Balsubramani, Zohar S. Karnin, Robert E. Schapire, Masrour Zoghi

Interactive Algorithms: From Pool to Stream Sivan Sabato, Tom Hess

Learning and 1-Bit Compressed Sensing Under Asymmetric Noise Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Hongyang Zhang

Learning and Testing Junta Distributions Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld

Learning Combinatorial Functions from Pairwise Comparisons Maria-Florina Balcan, Ellen Vitercik, Colin White

Learning Communities in the Presence of Errors Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Learning Simple Auctions Jamie Morgenstern, Tim Roughgarden

Maximin Action Identification: A New Bandit Framework for Games Aurélien Garivier, Emilie Kaufmann, Wouter M. Koolen

Memory, Communication, and Statistical Queries Jacob Steinhardt, Gregory Valiant, Stefan Wager

Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes Nima Anari, Shayan Oveis Gharan, Alireza Rezaei

Multi-Scale Exploration of Convex Functions and Bandit Convex Optimization Sébastien Bubeck, Ronen Eldan

Noisy Tensor Completion via the Sum-of-Squares Hierarchy Boaz Barak, Ankur Moitra

On the Approximability of Sparse PCA Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein

On the Capacity of Information Processing Systems Laurent Massoulié, Kuang Xu

On the Expressive Power of Deep Learning: A Tensor Analysis Nadav Cohen, Or Sharir, Amnon Shashua

On the Low-Rank Approach for Semidefinite Programs Arising in Synchronization and Community Detection Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski

Online Isotonic Regression Wojciech Kotlowski

Online Learning and Blackwell Approachability in Quitting Games János Flesch, Rida Laraki, Vianney Perchet

Online Learning in Repeated Auctions Jonathan Weed, Vianney Perchet, Philippe Rigollet

Online Learning with Low Rank Experts Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour

Online Sparse Linear Regression Dean P. Foster, Satyen Kale, Howard J. Karloff

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: Parameter-Free and Scale-Free Online Algorithms Francesco Orabona, Dávid Pál

Open Problem: Property Elicitation and Elicitation Complexity Rafael M. Frongillo, Ian A. Kash, Stephen Becker

Open Problem: Second Order Regret Bounds Based on Scaling Time Yoav Freund

Optimal Best Arm Identification with Fixed Confidence Aurélien Garivier, Emilie Kaufmann

Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Optimal Rates for Total Variation Denoising Jan-Christian Hü

Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models Bernardo Ávila Pires

Preference-Based Teaching Ziyuan Gao, Christoph Ries, Hans Ulrich Simon, Sandra Zilles

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Provably Manipulation-Resistant Reputation Systems Paul F. Christiano

Pure Exploration of Multi-Armed Bandit Under Matroid Constraints Lijie Chen, Anupam Gupta, Jian Li

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

Reinforcement Learning of POMDPs Using Spectral Methods Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar

Semidefinite Programs for Exact Recovery of a Hidden Community Bruce E. Hajek, Yihong Wu, Jiaming Xu

Sign Rank Versus VC Dimension Noga Alon, Shay Moran, Amir Yehudayoff

Simple Bayesian Algorithms for Best Arm Identification Daniel Russo

Spectral Thresholds in the Bipartite Stochastic Block Model Laura Florescu, Will Perkins

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

The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions Chicheng Zhang, Kamalika Chaudhuri

The Power of Depth for Feedforward Neural Networks Ronen Eldan, Ohad Shamir

Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem Alexandra Carpentier, Andrea Locatelli

Time Series Prediction and Online Learning Vitaly Kuznetsov, Mehryar Mohri

When Can We Rank Well from Comparisons of \(O(n\log(n))\) Non-Actively Chosen Pairs? Arun Rajkumar, Shivani Agarwal