COLT 2019

127 papers

Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory

Blake Woodworth, Nathan Srebro

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: Do Good Algorithms Necessarily Query Bad Points?

Rong Ge, Prateek Jain, Sham M. Kakade, Rahul Kidambi, Dheeraj M. Nagaraj

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

Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate

Lijun Zhang, Zhi-Hua Zhou

Estimating the Mixing Time of Ergodic Markov Chains

Geoﬀrey Wolfer, Aryeh Kontorovich

Estimation of smooth densities in Wasserstein distance

Jonathan Weed, Quentin Berthet

Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds

Santosh Vempala, John Wilmes

Theoretical guarantees for sampling and inference in generative models with latent diffusions

Belinda Tzen, Maxim Raginsky

The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint

Stephen Tu, Benjamin Recht

The Relative Complexity of Maximum Likelihood Estimation, MAP Estimation, and Sampling

Christopher Tosh, Sanjoy Dasgupta

Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

Adrien Taylor, Francis Bach

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

Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression

Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, Prateek Jain

Maximum Entropy Distributions: Bit Complexity and Stability

Damian Straszak, Nisheeth K. Vishnoi

Robustness of Spectral Methods for Community Detection

Ludovic Stephan, Laurent Massoulié

Finite-Time Error Bounds For Linear Stochastic Approximation andTD Learning

R. Srikant, Lei Ying

Learning Linear Dynamical Systems with Semi-Parametric Least Squares

Max Simchowitz, Ross Boczar, Benjamin Recht

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

Ohad Shamir

How do infinite width bounded norm networks look in function space?

Pedro Savarese, Itay Evron, Daniel Soudry, Nathan Srebro

Depth Separations in Neural Networks: What is Actually Being Separated?

Itay Safran, Ronen Eldan, Ohad Shamir

The All-or-Nothing Phenomenon in Sparse Linear Regression

Galen Reeves, Jiaming Xu, Ilias Zadik

Classification with unknown class-conditional label noise on non-compact feature spaces

Henry Reeve, Kabán

Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon

Alexander Rakhlin, Xiyu Zhai

A Theory of Selective Prediction

Mingda Qiao, Gregory Valiant

Stochastic Gradient Descent Learns State Equations with Nonlinear Activations

Samet Oymak

Affine Invariant Covariance Estimation for Heavy-Tailed Distributions

Dmitrii M. Ostrovskii, Alessandro Rudi

VC Classes are Adversarially Robustly Learnable, but Only Improperly

Omar Montasser, Steve Hanneke, Nathan Srebro

Lipschitz Adaptivity with Multiple Learning Rates in Online Learning

Zakaria Mhammedi, Wouter M Koolen, Tim van Erven

Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem

Nadav Merlis, Shie Mannor

Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit

Song Mei, Theodor Misiakiewicz, Andrea Montanari

Uniform concentration and symmetrization for weak interactions

Andreas Maurer, Massimiliano Pontil

Planting trees in graphs, and finding them back

Laurent Massoulié, Ludovic Stephan, Don Towsley

Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance

Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach, Alessandro Rudi

Nonconvex sampling with the Metropolis-adjusted Langevin algorithm

Oren Mangoubi, Nisheeth K Vishnoi

Combinatorial Algorithms for Optimal Design

Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, Weijun Xie

Sharp Theoretical Analysis for Nonparametric Testing under Random Projection

Meimei Liu, Zuofeng Shang, Guang Cheng

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits

Yingkai Li, Yining Wang, Yuan Zhou

On Mean Estimation for General Norms with Statistical Queries

Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Yin Tat Lee, Zhao Song, Qiuyi Zhang

An Information-Theoretic Approach to Minimax Regret in Partial Monitoring

Tor Lattimore, Csaba Szepesvári

Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression

Jeongyeol Kwon, Wei Qian, Constantine Caramanis, Yudong Chen, Damek Davis

Distribution-Dependent Analysis of Gibbs-ERM Principle

Ilja Kuzborskij, Nicolò Cesa-bianchi, Csaba Szepesvári

Contextual bandits with continuous actions: Smoothing, zooming, and adapting

Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, Chicheng Zhang

Bandit Principal Component Analysis

Wojciech Kotłowski, Gergely Neu

Discrepancy, Coresets, and Sketches in Machine Learning

Zohar Karnin, Edo Liberty

Non-asymptotic Analysis of Biased Stochastic Approximation Scheme

Belhal Karimi, Blazej Miasojedow, Eric Moulines, Hoi-To Wai

On Communication Complexity of Classification Problems

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

Privately Learning High-Dimensional Distributions

Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman

Sample complexity of partition identification using multi-armed bandits

Sandeep Juneja, Subhashini Krishnasamy

Parameter-Free Online Convex Optimization with Sub-Exponential Noise

Kwang-Sung Jun, Francesco Orabona

An Optimal High-Order Tensor Method for Convex Optimization

Bo Jiang, Haoyue Wang, Shuzhong Zhang

The implicit bias of gradient descent on nonseparable data

Ziwei Ji, Matus Telgarsky

Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation

Vishesh Jain, Frederic Koehler, Jingbo Liu, Elchanan Mossel

Making the Last Iterate of SGD Information Theoretically Optimal

Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli

Sample-Optimal Low-Rank Approximation of Distance Matrices

Pitor Indyk, Ali Vakilian, Tal Wagner, David P Woodruff

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi

How Hard is Robust Mean Estimation?

Samuel B. Hopkins, Jerry Li

Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard

Jan Hązła, Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian

Tight analyses for non-smooth stochastic gradient descent

Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, Sikander Randhawa

Better Algorithms for Stochastic Bandits with Adversarial Corruptions

Anupam Gupta, Tomer Koren, Kunal Talwar

Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature

Navin Goyal, Abhishek Shetty

When can unlabeled data improve the learning rate?

Christina Göpfert, Shai Ben-David, Olivier Bousquet, Sylvain Gelly, Ilya Tolstikhin

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

Surbhi Goel, Adam R. Klivans

Learning Ising Models with Independent Failures

Surbhi Goel, Daniel M. Kane, Adam R. Klivans

Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

Rong Ge, Zhize Li, Weiyao Wang, Xiang Wang

Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives

Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych

Optimal Tensor Methods in Smooth Convex and Uniformly ConvexOptimization

Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych

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

Dan Garber

Statistical Learning with a Nuisance Component

Dylan J. Foster, Vasilis Syrgkanis

The Complexity of Making the Gradient Small in Stochastic Convex Optimization

Dylan J. Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan

Sum-of-squares meets square loss: Fast rates for agnostic tensor completion

Dylan J. Foster, Andrej Risteski

High probability generalization bounds for uniformly stable algorithms with nearly optimal rate

Vitaly Feldman, Jan Vondrak

Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly

Yingjie Fei, Yudong Chen

Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Cong Fang, Zhouchen Lin, Tong Zhang

Lower Bounds for Locally Private Estimation via Communication Complexity

John Duchi, Ryan Rogers

On the Performance of Thompson Sampling on Logistic Bandits

Shi Dong, Tengyu Ma, Benjamin Van Roy

Lower Bounds for Parallel and Randomized Convex Optimization

Jelena Diakonikolas, Cristóbal Guzmán

Testing Identity of Multidimensional Histograms

Ilias Diakonikolas, Daniel M. Kane, John Peebles

Communication and Memory Efficient Testing of Discrete Distributions

Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao

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

Fast determinantal point processes via distortion-free intermediate sampling

Michał Dereziński

Computational Limitations in Robust Classification and Win-Win Results

Akshay Degwekar, Preetum Nakkiran, Vinod Vaikuntanathan

Is your function low dimensional?

Anindya De, Elchanan Mossel, Joe Neeman

Reconstructing Trees from Traces

Sami Davies, Miklós Z. Rácz, Cyrus Rashtchian

Computationally and Statistically Efficient Truncated Regression

Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis

Space lower bounds for linear prediction in the streaming model

Yuval Dagan, Gil Kur, Ohad Shamir

Learning from Weakly Dependent Data under Dobrushin’s Condition

Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Siddhartha Jayanti

Combining Online Learning Guarantees

Ashok Cutkosky

Artificial Constraints and Hints for Unbounded Online Learning

Ashok Cutkosky

A near-optimal algorithm for approximating the John Ellipsoid

Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang

Pure entropic regularization for metrical task systems

Christian Coester, James R. Lee

Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games

Yun Kuen Cheung, Georgios Piliouras

Fast Mean Estimation with Sub-Gaussian Rates

Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter L. Bartlett

Testing Symmetric Markov Chains Without Hitting

Yeshwanth Cherapanamjeri, Peter L. Bartlett

Faster Algorithms for High-Dimensional Robust Covariance Estimation

Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff

A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal and Parameter-free

Yifang Chen, Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei

Active Regression via Linear-Sample Sparsification

Xue Chen, Eric Price