COLT 2019

127 papers

On the Computational Power of Online Gradient Descent

Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang

A Rank-1 Sketch for Matrix Multiplicative Weights

Yair Carmon, John C Duchi, Sidford Aaron, Tian Kevin

Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm

Tongyi Cao, Akshay Krishnamurthy

Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret

Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, Lorenzo Rosasco

Optimal Learning of Mallows Block Model

Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, Manolis Zampetakis

Improved Path-length Regret Bounds for Bandits

Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, Chen-Yu Wei

Near-optimal method for highly smooth convex optimization

Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford

Learning rates for Gaussian mixtures under group action

Victor-Emmanuel Brunel

Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

Matthew Brennan, Guy Bresler

Universality of Computational Lower Bounds for Submatrix Detection

Matthew Brennan, Guy Bresler, Wasim Huleihel

Multi-armed Bandit Problems with Strategic Arms

Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg

Sorted Top-k in Rounds

Mark Braverman, Jieming Mao, Yuval Peres

The Optimal Approximation Factor in Density Estimation

Olivier Bousquet, Daniel Kane, Shay Moran

Approximate Guarantees for Dictionary Learning

Aditya Bhaskara, Wai Ming Tai

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models

Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda

Private Center Points and Learning of Halfspaces

Amos Beimel, Shay Moran, Kobbi Nissim, Uri Stemmer

Learning Two Layer Rectified Neural Networks in Polynomial Time

Ainesh Bakshi, Rajesh Jayaram, David P Woodruff

A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise

Francis Bach, Kfir Y Levy

Achieving Optimal Dynamic Regret for Non-stationary Bandits without Prior Information

Peter Auer, Yifang Chen, Pratik Gajane, Chung-Wei Lee, Haipeng Luo

Adaptively Tracking the Best Bandit Arm with an Unknown Number of Distribution Changes

Peter Auer, Pratik Gajane, Ronald Ortner

Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT

Andreas Anastasiou, Krishnakumar Balasubramanian, Murat A. Erdogdu

Testing Mixtures of Discrete Distributions

Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld

Towards Testing Monotonicity of Distributions Over General Posets

Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee

Learning to Prune: Speeding up Repeated Computations

Daniel Alabi, Adam Tauman Kalai, Katrina Liggett, Cameron Musco, Christos Tzamos

Learning in Non-convex Games with an Optimization Oracle

Naman Agarwal, Alon Gonen, Elad Hazan

Inference under Information Constraints: Lower Bounds from Chi-Square Contraction

Jayadev Acharya, Clément L Canonne, Himanshu Tyagi

Conference on Learning Theory 2019: Preface

Alina Beygelzimer, Daniel Hsu