COLT 2019

126 papers

A Near-Optimal Algorithm for Approximating the John Ellipsoid Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang

A New Algorithm for Non-Stationary Contextual Bandits: Efficient, Optimal and Parameter-Free Yifang Chen, Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei

A Rank-1 Sketch for Matrix Multiplicative Weights Yair Carmon, John C Duchi, Sidford Aaron, Tian Kevin

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition Samuel B. Hopkins, Tselil Schramm, Jonathan Shi

A Theory of Selective Prediction Mingda Qiao, Gregory Valiant

A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise Francis Bach, Kfir Y Levy

Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation Vishesh Jain, Frederic Koehler, Jingbo Liu, Elchanan Mossel

Achieving Optimal Dynamic Regret for Non-Stationary Bandits Without Prior Information Peter Auer, Yifang Chen, Pratik Gajane, Chung-Wei Lee, Haipeng Luo, Ronald Ortner, Chen-Yu Wei

Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly Yingjie Fei, Yudong Chen

Active Regression via Linear-Sample Sparsification Xue Chen, Eric Price

Adaptive Hard Thresholding for Near-Optimal Consistent Robust Regression Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, Prateek Jain

Adaptively Tracking the Best Bandit Arm with an Unknown Number of Distribution Changes Peter Auer, Pratik Gajane, Ronald Ortner

Affine Invariant Covariance Estimation for Heavy-Tailed Distributions Dmitrii M. Ostrovskii, Alessandro Rudi

An Information-Theoretic Approach to Minimax Regret in Partial Monitoring Tor Lattimore, Csaba Szepesvári

An Optimal High-Order Tensor Method for Convex Optimization Bo Jiang, Haoyue Wang, Shuzhong Zhang

Approximate Guarantees for Dictionary Learning Aditya Bhaskara, Wai Ming Tai

Artificial Constraints and Hints for Unbounded Online Learning Ashok Cutkosky

Bandit Principal Component Analysis Wojciech Kotłowski, Gergely Neu

Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem Nadav Merlis, Shie Mannor

Better Algorithms for Stochastic Bandits with Adversarial Corruptions Anupam Gupta, Tomer Koren, Kunal Talwar

Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization Through Self-Concordance Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach, Alessandro Rudi

Classification with Unknown Class-Conditional Label Noise on Non-Compact Feature Spaces Henry Reeve, Kabán

Combinatorial Algorithms for Optimal Design Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, Weijun Xie

Combining Online Learning Guarantees Ashok Cutkosky

Communication and Memory Efficient Testing of Discrete Distributions Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao

Computational Limitations in Robust Classification and Win-Win Results Akshay Degwekar, Preetum Nakkiran, Vinod Vaikuntanathan

Computationally and Statistically Efficient Truncated Regression Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis

Consistency of Interpolation with Laplace Kernels Is a High-Dimensional Phenomenon Alexander Rakhlin, Xiyu Zhai

Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, Chicheng Zhang

Depth Separations in Neural Networks: What Is Actually Being Separated? Itay Safran, Ronen Eldan, Ohad Shamir

Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm Tongyi Cao, Akshay Krishnamurthy

Discrepancy, Coresets, and Sketches in Machine Learning Zohar Karnin, Edo Liberty

Distribution-Dependent Analysis of Gibbs-ERM Principle Ilja Kuzborskij, Nicolò Cesa-Bianchi, Csaba Szepesvári

Estimating the Mixing Time of Ergodic Markov Chains Geoffrey Wolfer, Aryeh Kontorovich

Estimation of Smooth Densities in Wasserstein Distance Jonathan Weed, Quentin Berthet

Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks Ohad Shamir

Fast Determinantal Point Processes via Distortion-Free Intermediate Sampling Michał Dereziński

Fast Mean Estimation with Sub-Gaussian Rates Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter L. Bartlett

Faster Algorithms for High-Dimensional Robust Covariance Estimation Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff

Finite-Time Error Bounds for Linear Stochastic Approximation andTD Learning R. Srikant, Lei Ying

Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, Lorenzo Rosasco

Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression Jeongyeol Kwon, Wei Qian, Constantine Caramanis, Yudong Chen, Damek Davis

Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds Santosh Vempala, John Wilmes

High Probability Generalization Bounds for Uniformly Stable Algorithms with Nearly Optimal Rate Vitaly Feldman, Jan Vondrak

How Do Infinite Width Bounded Norm Networks Look in Function Space? Pedro Savarese, Itay Evron, Daniel Soudry, Nathan Srebro

How Hard Is Robust Mean Estimation? Samuel B. Hopkins, Jerry Li

Improved Path-Length Regret Bounds for Bandits Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, Chen-Yu Wei

Inference Under Information Constraints: Lower Bounds from Chi-Square Contraction Jayadev Acharya, Clément L Canonne, Himanshu Tyagi

Is Your Function Low Dimensional? Anindya De, Elchanan Mossel, Joe Neeman

Learning from Weakly Dependent Data Under Dobrushin’s Condition Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Siddhartha Jayanti

Learning in Non-Convex Games with an Optimization Oracle Naman Agarwal, Alon Gonen, Elad Hazan

Learning Ising Models with Independent Failures Surbhi Goel, Daniel M. Kane, Adam R. Klivans

Learning Linear Dynamical Systems with Semi-Parametric Least Squares Max Simchowitz, Ross Boczar, Benjamin Recht

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time Surbhi Goel, Adam R. Klivans

Learning Rates for Gaussian Mixtures Under Group Action Victor-Emmanuel Brunel

Learning to Prune: Speeding up Repeated Computations Daniel Alabi, Adam Tauman Kalai, Katrina Liggett, Cameron Musco, Christos Tzamos, Ellen Vitercik

Learning Two Layer Rectified Neural Networks in Polynomial Time Ainesh Bakshi, Rajesh Jayaram, David P Woodruff

Lipschitz Adaptivity with Multiple Learning Rates in Online Learning Zakaria Mhammedi, Wouter M Koolen, Tim Van Erven

Lower Bounds for Locally Private Estimation via Communication Complexity John Duchi, Ryan Rogers

Lower Bounds for Parallel and Randomized Convex Optimization Jelena Diakonikolas, Cristóbal Guzmán

Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda

Making the Last Iterate of SGD Information Theoretically Optimal Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli

Maximum Entropy Distributions: Bit Complexity and Stability Damian Straszak, Nisheeth K. Vishnoi

Mean-Field Theory of Two-Layers Neural Networks: Dimension-Free Bounds and Kernel Limit Song Mei, Theodor Misiakiewicz, Andrea Montanari

Minimax Experimental Design: Bridging the Gap Between Statistical and Worst-Case Approaches to Least Squares Regression Michał Dereziński, Kenneth L. Clarkson, Michael W. Mahoney, Manfred K. Warmuth

Model-Based RL in Contextual Decision Processes: PAC Bounds and Exponential Improvements over Model-Free Approaches Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford

Multi-Armed Bandit Problems with Strategic Arms Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg

Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-Th Derivatives Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, César A. Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford

Near-Optimal Method for Highly Smooth Convex Optimization Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits Yingkai Li, Yining Wang, Yuan Zhou

Non-Asymptotic Analysis of Biased Stochastic Approximation Scheme Belhal Karimi, Blazej Miasojedow, Eric Moulines, Hoi-To Wai

Nonconvex Sampling with the Metropolis-Adjusted Langevin Algorithm Oren Mangoubi, Nisheeth K Vishnoi

Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT Andreas Anastasiou, Krishnakumar Balasubramanian, Murat A. Erdogdu

On Communication Complexity of Classification Problems Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

On Mean Estimation for General Norms with Statistical Queries Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten

On the Computational Power of Online Gradient Descent Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang

On the Performance of Thompson Sampling on Logistic Bandits Shi Dong, Tengyu Ma, Benjamin Van Roy

On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA Dan Garber

Open Problem: Do Good Algorithms Necessarily Query Bad Points? Rong Ge, Prateek Jain, Sham M. Kakade, Rahul Kidambi, Dheeraj M. Nagaraj, Praneeth Netrapalli

Open Problem: How Fast Can a Multiclass Test Set Be Overfit? Vitaly Feldman, Roy Frostig, Moritz Hardt

Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning? Amit Daniely, Vitaly Feldman

Open Problem: Monotonicity of Learning Tom Viering, Alexander Mey, Marco Loog

Open Problem: Risk of Ruin in Multiarmed Bandits Filipo S. Perotto, Mathieu Bourgais, Bruno C. Silva, Laurent Vercouter

Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory Blake Woodworth, Nathan Srebro

Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness Matthew Brennan, Guy Bresler

Optimal Learning of Mallows Block Model Robert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, Manolis Zampetakis

Optimal Tensor Methods in Smooth Convex and Uniformly ConvexOptimization Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, César A. Uribe

Parameter-Free Online Convex Optimization with Sub-Exponential Noise Kwang-Sung Jun, Francesco Orabona

Planting Trees in Graphs, and Finding Them Back Laurent Massoulié, Ludovic Stephan, Don Towsley

Private Center Points and Learning of Halfspaces Amos Beimel, Shay Moran, Kobbi Nissim, Uri Stemmer

Privately Learning High-Dimensional Distributions Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman

Pure Entropic Regularization for Metrical Task Systems Christian Coester, James R. Lee

Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard Jan Hązła, Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian

Reconstructing Trees from Traces Sami Davies, Miklos Z. Racz, Cyrus Rashtchian

Robustness of Spectral Methods for Community Detection Ludovic Stephan, Laurent Massoulié

Sample Complexity of Partition Identification Using Multi-Armed Bandits Sandeep Juneja, Subhashini Krishnasamy

Sample-Optimal Low-Rank Approximation of Distance Matrices Pitor Indyk, Ali Vakilian, Tal Wagner, David P Woodruff

Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature Navin Goyal, Abhishek Shetty

Sharp Analysis for Nonconvex SGD Escaping from Saddle Points Cong Fang, Zhouchen Lin, Tong Zhang

Sharp Theoretical Analysis for Nonparametric Testing Under Random Projection Meimei Liu, Zuofeng Shang, Guang Cheng

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time Yin Tat Lee, Zhao Song, Qiuyi Zhang

Sorted Top-K in Rounds Mark Braverman, Jieming Mao, Yuval Peres

Space Lower Bounds for Linear Prediction in the Streaming Model Yuval Dagan, Gil Kur, Ohad Shamir

Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization Rong Ge, Zhize Li, Weiyao Wang, Xiang Wang

Statistical Learning with a Nuisance Component Dylan J. Foster, Vasilis Syrgkanis

Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate Lijun Zhang, Zhi-Hua Zhou

Stochastic First-Order Methods: Non-Asymptotic and Computer-Aided Analyses via Potential Functions Adrien Taylor, Francis Bach

Stochastic Gradient Descent Learns State Equations with Nonlinear Activations Samet Oymak

Sum-of-Squares Meets Square Loss: Fast Rates for Agnostic Tensor Completion Dylan J. Foster, Andrej Risteski

Testing Identity of Multidimensional Histograms Ilias Diakonikolas, Daniel M. Kane, John Peebles

Testing Mixtures of Discrete Distributions Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld

Testing Symmetric Markov Chains Without Hitting Yeshwanth Cherapanamjeri, Peter L. Bartlett

The All-or-Nothing Phenomenon in Sparse Linear Regression Galen Reeves, Jiaming Xu, Ilias Zadik

The Complexity of Making the Gradient Small in Stochastic Convex Optimization Dylan J. Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, Blake Woodworth

The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint Stephen Tu, Benjamin Recht

The Implicit Bias of Gradient Descent on Nonseparable Data Ziwei Ji, Matus Telgarsky

The Optimal Approximation Factor in Density Estimation Olivier Bousquet, Daniel Kane, Shay Moran

The Relative Complexity of Maximum Likelihood Estimation, MAP Estimation, and Sampling Christopher Tosh, Sanjoy Dasgupta

Theoretical Guarantees for Sampling and Inference in Generative Models with Latent Diffusions Belinda Tzen, Maxim Raginsky

Tight Analyses for Non-Smooth Stochastic Gradient Descent Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, Sikander Randhawa

Towards Testing Monotonicity of Distributions over General Posets Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee

Uniform Concentration and Symmetrization for Weak Interactions Andreas Maurer, Massimiliano Pontil

Universality of Computational Lower Bounds for Submatrix Detection Matthew Brennan, Guy Bresler, Wasim Huleihel

VC Classes Are Adversarially Robustly Learnable, but Only Improperly Omar Montasser, Steve Hanneke, Nathan Srebro

Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games Yun Kuen Cheung, Georgios Piliouras

When Can Unlabeled Data Improve the Learning Rate? Christina Göpfert, Shai Ben-David, Olivier Bousquet, Sylvain Gelly, Ilya Tolstikhin, Ruth Urner