| 2019 | A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal and Parameter-free. Yifang Chen, Chung-wei Lee, Haipeng Luo, Chen-Yu Wei |
| 2019 | A Rank-1 Sketch for Matrix Multiplicative Weights. Yair Carmon, John C. Duchi, Aaron Sidford, Kevin Tian |
| 2019 | A Robust Spectral Algorithm for Overcomplete Tensor Decomposition. Samuel B. Hopkins, Tselil Schramm, Jonathan Shi |
| 2019 | A Theory of Selective Prediction. Mingda Qiao, Gregory Valiant |
| 2019 | A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise. Francis R. Bach, Kfir Y. Levy |
| 2019 | A near-optimal algorithm for approximating the John Ellipsoid. Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang |
| 2019 | Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation. Vishesh Jain, Frederic Koehler, Jingbo Liu, Elchanan Mossel |
| 2019 | 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 |
| 2019 | Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly. Yingjie Fei, Yudong Chen |
| 2019 | Active Regression via Linear-Sample Sparsification. Xue Chen, Eric Price |
| 2019 | Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression. Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, Prateek Jain |
| 2019 | Adaptively Tracking the Best Bandit Arm with an Unknown Number of Distribution Changes. Peter Auer, Pratik Gajane, Ronald Ortner |
| 2019 | Affine Invariant Covariance Estimation for Heavy-Tailed Distributions. Dmitrii M. Ostrovskii, Alessandro Rudi |
| 2019 | An Information-Theoretic Approach to Minimax Regret in Partial Monitoring. Tor Lattimore, Csaba Szepesvári |
| 2019 | An Optimal High-Order Tensor Method for Convex Optimization. Bo Jiang, Haoyue Wang, Shuzhong Zhang |
| 2019 | Approximate Guarantees for Dictionary Learning. Aditya Bhaskara, Wai Ming Tai |
| 2019 | Artificial Constraints and Hints for Unbounded Online Learning. Ashok Cutkosky |
| 2019 | Bandit Principal Component Analysis. Wojciech Kotlowski, Gergely Neu |
| 2019 | Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem. Nadav Merlis, Shie Mannor |
| 2019 | Better Algorithms for Stochastic Bandits with Adversarial Corruptions. Anupam Gupta, Tomer Koren, Kunal Talwar |
| 2019 | Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance. Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis R. Bach, Alessandro Rudi |
| 2019 | Classification with unknown class-conditional label noise on non-compact feature spaces. Henry W. J. Reeve, Ata Kabán |
| 2019 | Combinatorial Algorithms for Optimal Design. Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, Weijun Xie |
| 2019 | Combining Online Learning Guarantees. Ashok Cutkosky |
| 2019 | Communication and Memory Efficient Testing of Discrete Distributions. Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao |
| 2019 | Computational Limitations in Robust Classification and Win-Win Results. Akshay Degwekar, Preetum Nakkiran, Vinod Vaikuntanathan |
| 2019 | Computationally and Statistically Efficient Truncated Regression. Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis |
| 2019 | Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA Alina Beygelzimer, Daniel Hsu |
| 2019 | Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon. Alexander Rakhlin, Xiyu Zhai |
| 2019 | Contextual bandits with continuous actions: Smoothing, zooming, and adapting. Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, Chicheng Zhang |
| 2019 | Depth Separations in Neural Networks: What is Actually Being Separated? Itay Safran, Ronen Eldan, Ohad Shamir |
| 2019 | Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm. Tongyi Cao, Akshay Krishnamurthy |
| 2019 | Discrepancy, Coresets, and Sketches in Machine Learning. Zohar S. Karnin, Edo Liberty |
| 2019 | Distribution-Dependent Analysis of Gibbs-ERM Principle. Ilja Kuzborskij, Nicolò Cesa-Bianchi, Csaba Szepesvári |
| 2019 | Estimating the Mixing Time of Ergodic Markov Chains. Geoffrey Wolfer, Aryeh Kontorovich |
| 2019 | Estimation of smooth densities in Wasserstein distance. Jonathan Weed, Quentin Berthet |
| 2019 | Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks. Ohad Shamir |
| 2019 | Fast Mean Estimation with Sub-Gaussian Rates. Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter L. Bartlett |
| 2019 | Fast determinantal point processes via distortion-free intermediate sampling. Michal Derezinski |
| 2019 | Faster Algorithms for High-Dimensional Robust Covariance Estimation. Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff |
| 2019 | Finite-Time Error Bounds For Linear Stochastic Approximation andTD Learning. R. Srikant, Lei Ying |
| 2019 | Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret. Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, Lorenzo Rosasco |
| 2019 | Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression. Jeongyeol Kwon, Wei Qian, Constantine Caramanis, Yudong Chen, Damek Davis |
| 2019 | Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds. Santosh S. Vempala, John Wilmes |
| 2019 | High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. Vitaly Feldman, Jan Vondrák |
| 2019 | How Hard is Robust Mean Estimation? Samuel B. Hopkins, Jerry Li |
| 2019 | How do infinite width bounded norm networks look in function space? Pedro Savarese, Itay Evron, Daniel Soudry, Nathan Srebro |
| 2019 | Improved Path-length Regret Bounds for Bandits. Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, Chen-Yu Wei |
| 2019 | Inference under Information Constraints: Lower Bounds from Chi-Square Contraction. Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi |
| 2019 | Is your function low dimensional? Anindya De, Elchanan Mossel, Joe Neeman |
| 2019 | Learning Ising Models with Independent Failures. Surbhi Goel, Daniel M. Kane, Adam R. Klivans |
| 2019 | Learning Linear Dynamical Systems with Semi-Parametric Least Squares. Max Simchowitz, Ross Boczar, Benjamin Recht |
| 2019 | Learning Neural Networks with Two Nonlinear Layers in Polynomial Time. Surbhi Goel, Adam R. Klivans |
| 2019 | Learning Two Layer Rectified Neural Networks in Polynomial Time. Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff |
| 2019 | Learning from Weakly Dependent Data under Dobrushin's Condition. Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Siddhartha Jayanti |
| 2019 | Learning in Non-convex Games with an Optimization Oracle. Naman Agarwal, Alon Gonen, Elad Hazan |
| 2019 | Learning rates for Gaussian mixtures under group action. Victor-Emmanuel Brunel |
| 2019 | Learning to Prune: Speeding up Repeated Computations. Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, Ellen Vitercik |
| 2019 | Lipschitz Adaptivity with Multiple Learning Rates in Online Learning. Zakaria Mhammedi, Wouter M. Koolen, Tim van Erven |
| 2019 | Lower Bounds for Locally Private Estimation via Communication Complexity. John C. Duchi, Ryan Rogers |
| 2019 | Lower Bounds for Parallel and Randomized Convex Optimization. Jelena Diakonikolas, Cristóbal Guzmán |
| 2019 | Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models. Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda |
| 2019 | Making the Last Iterate of SGD Information Theoretically Optimal. Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli |
| 2019 | Maximum Entropy Distributions: Bit Complexity and Stability. Damian Straszak, Nisheeth K. Vishnoi |
| 2019 | Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. Song Mei, Theodor Misiakiewicz, Andrea Montanari |
| 2019 | Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression. Michal Derezinski, Kenneth L. Clarkson, Michael W. Mahoney, Manfred K. Warmuth |
| 2019 | 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 |
| 2019 | Multi-armed Bandit Problems with Strategic Arms. Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg |
| 2019 | Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives. Alexander V. Gasnikov, Pavel E. Dvurechensky, Eduard Gorbunov, Evgeniya A. 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 |
| 2019 | Near-optimal method for highly smooth convex optimization. Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford |
| 2019 | Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits. Yingkai Li, Yining Wang, Yuan Zhou |
| 2019 | Non-asymptotic Analysis of Biased Stochastic Approximation Scheme. Belhal Karimi, Blazej Miasojedow, Eric Moulines, Hoi-To Wai |
| 2019 | Nonconvex sampling with the Metropolis-adjusted Langevin algorithm. Oren Mangoubi, Nisheeth K. Vishnoi |
| 2019 | Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT. Andreas Anastasiou, Krishnakumar Balasubramanian, Murat A. Erdogdu |
| 2019 | On Communication Complexity of Classification Problems. Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff |
| 2019 | On Mean Estimation for General Norms with Statistical Queries. Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2019 | On the Computational Power of Online Gradient Descent. Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang |
| 2019 | On the Performance of Thompson Sampling on Logistic Bandits. Shi Dong, Tengyu Ma, Benjamin Van Roy |
| 2019 | On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA. Dan Garber |
| 2019 | Open Problem: Do Good Algorithms Necessarily Query Bad Points? Rong Ge, Prateek Jain, Sham M. Kakade, Rahul Kidambi, Dheeraj M. Nagaraj, Praneeth Netrapalli |
| 2019 | Open Problem: How fast can a multiclass test set be overfit? Vitaly Feldman, Roy Frostig, Moritz Hardt |
| 2019 | Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning? Amit Daniely, Vitaly Feldman |
| 2019 | Open Problem: Monotonicity of Learning. Tom J. Viering, Alexander Mey, Marco Loog |
| 2019 | Open Problem: Risk of Ruin in Multiarmed Bandits. Filipo Studzinski Perotto, Mathieu Bourgais, Bruno C. Silva, Laurent Vercouter |
| 2019 | Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory. Blake E. Woodworth, Nathan Srebro |
| 2019 | Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness. Matthew S. Brennan, Guy Bresler |
| 2019 | Optimal Learning of Mallows Block Model. Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, Manolis Zampetakis |
| 2019 | Optimal Tensor Methods in Smooth Convex and Uniformly ConvexOptimization. Alexander V. Gasnikov, Pavel E. Dvurechensky, Eduard Gorbunov, Evgeniya A. Vorontsova, Daniil Selikhanovych, César A. Uribe |
| 2019 | Parameter-Free Online Convex Optimization with Sub-Exponential Noise. Kwang-Sung Jun, Francesco Orabona |
| 2019 | Planting trees in graphs, and finding them back. Laurent Massoulié, Ludovic Stephan, Don Towsley |
| 2019 | Preface. |
| 2019 | Private Center Points and Learning of Halfspaces. Amos Beimel, Shay Moran, Kobbi Nissim, Uri Stemmer |
| 2019 | Privately Learning High-Dimensional Distributions. Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan R. Ullman |
| 2019 | Pure entropic regularization for metrical task systems. Christian Coester, James R. Lee |
| 2019 | Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard. Jan Hazla, Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian |
| 2019 | Reconstructing Trees from Traces. Sami Davies, Miklós Z. Rácz, Cyrus Rashtchian |
| 2019 | Robustness of Spectral Methods for Community Detection. Ludovic Stephan, Laurent Massoulié |
| 2019 | Sample complexity of partition identification using multi-armed bandits. Sandeep Juneja, Subhashini Krishnasamy |
| 2019 | Sample-Optimal Low-Rank Approximation of Distance Matrices. Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff |
| 2019 | Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature. Navin Goyal, Abhishek Shetty |
| 2019 | Sharp Analysis for Nonconvex SGD Escaping from Saddle Points. Cong Fang, Zhouchen Lin, Tong Zhang |
| 2019 | Sharp Theoretical Analysis for Nonparametric Testing under Random Projection. Meimei Liu, Zuofeng Shang, Guang Cheng |
| 2019 | Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. Yin Tat Lee, Zhao Song, Qiuyi Zhang |
| 2019 | Sorted Top-k in Rounds. Mark Braverman, Jieming Mao, Yuval Peres |
| 2019 | Space lower bounds for linear prediction in the streaming model. Yuval Dagan, Gil Kur, Ohad Shamir |
| 2019 | Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization. Rong Ge, Zhize Li, Weiyao Wang, Xiang Wang |
| 2019 | Statistical Learning with a Nuisance Component. Dylan J. Foster, Vasilis Syrgkanis |
| 2019 | Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate. Lijun Zhang, Zhi-Hua Zhou |
| 2019 | Stochastic Gradient Descent Learns State Equations with Nonlinear Activations. Samet Oymak |
| 2019 | Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions. Adrien B. Taylor, Francis R. Bach |
| 2019 | Sum-of-squares meets square loss: Fast rates for agnostic tensor completion. Dylan J. Foster, Andrej Risteski |
| 2019 | Testing Identity of Multidimensional Histograms. Ilias Diakonikolas, Daniel M. Kane, John Peebles |
| 2019 | Testing Mixtures of Discrete Distributions. Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld |
| 2019 | Testing Symmetric Markov Chains Without Hitting. Yeshwanth Cherapanamjeri, Peter L. Bartlett |
| 2019 | The All-or-Nothing Phenomenon in Sparse Linear Regression. Galen Reeves, Jiaming Xu, Ilias Zadik |
| 2019 | The Complexity of Making the Gradient Small in Stochastic Convex Optimization. Dylan J. Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, Blake E. Woodworth |
| 2019 | The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint. Stephen Tu, Benjamin Recht |
| 2019 | The Optimal Approximation Factor in Density Estimation. Olivier Bousquet, Daniel Kane, Shay Moran |
| 2019 | The Relative Complexity of Maximum Likelihood Estimation, MAP Estimation, and Sampling. Christopher Tosh, Sanjoy Dasgupta |
| 2019 | The implicit bias of gradient descent on nonseparable data. Ziwei Ji, Matus Telgarsky |
| 2019 | Theoretical guarantees for sampling and inference in generative models with latent diffusions. Belinda Tzen, Maxim Raginsky |
| 2019 | Tight analyses for non-smooth stochastic gradient descent. Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, Sikander Randhawa |
| 2019 | Towards Testing Monotonicity of Distributions Over General Posets. Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee |
| 2019 | Uniform concentration and symmetrization for weak interactions. Andreas Maurer, Massimiliano Pontil |
| 2019 | Universality of Computational Lower Bounds for Submatrix Detection. Matthew S. Brennan, Guy Bresler, Wasim Huleihel |
| 2019 | VC Classes are Adversarially Robustly Learnable, but Only Improperly. Omar Montasser, Steve Hanneke, Nathan Srebro |
| 2019 | Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games. Yun Kuen Cheung, Georgios Piliouras |
| 2019 | When can unlabeled data improve the learning rate? Christina Göpfert, Shai Ben-David, Olivier Bousquet, Sylvain Gelly, Ilya O. Tolstikhin, Ruth Urner |