For authors

Awards Accepted papers Call for papers Submission instructions Call for open problems


Best Paper Award

Statistical Learning with a Nuisance Component

Dylan Foster, Vasilis Syrgkanis

Best Student Paper Awards

The Complexity of Making the Gradient Small in Stochastic Convex Optimization

Dylan Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, Blake Woodworth

VC Classes are Adversarially Robustly Learnable, but Only Improperly

Omar Montasser, Steve Hanneke, Nathan Srebro

The best student paper awards are sponsored by the Mark Fulk Foundation and:
Machine Learning


Uniform concentration and symmetrization for weak interactions

Andreas Maurer, Massimiliano Pontil

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

Ohad Shamir

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

Christopher Tosh, Sanjoy Dasgupta

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

Tongyi Cao, Akshay Krishnamurthy

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

Lijun Zhang, Zhi-Hua Zhou

An Optimal High-Order Tensor Method for Convex Optimization

Bo Jiang, Haoyue Wang, Shuzhong Zhang

Testing Identity of Multidimensional Histograms

Ilias Diakonikolas, Daniel M. Kane, John Peebles

Improved Path-length Regret Bounds for Bandits

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

Sorted Top-k in Rounds

Mark Braverman, Jieming Mao, Yuval Peres

Privately Learning High-Dimensional Distributions

Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

Surbhi Goel, Adam R. Klivans

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

Dan Garber

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits

Yingkai Li, Yining Wang, Yuan Zhou

Lower Bounds for Parallel and Randomized Convex Optimization

Jelena Diakonikolas, Cristóbal Guzmán

Learning Two Layer Rectified Neural Networks in Polynomial Time

Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff

Stochastic Gradient Descent Learns State Equations with Nonlinear Activations

Samet Oymak

Learning Ising Models with Independent Failures

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

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

Stephen Tu, Benjamin Recht

Tight analyses for non smooth stochastic gradient descent

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

Estimating the Mixing Time of Ergodic Markov Chains

Wolfer Geoffrey, Kontorovich Aryeh

Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Cong Fang, Zhouchen Lin, Tong Zhang

Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard

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

Learning in Non-convex Games with an Optimization Oracle

Naman Agarwal, Alon Gonen, Elad Hazan

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

Itay Safran, Ronen Eldan, Ohad Shamir

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

Santosh Vempala, John Wilmes

A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise

Francis Bach, Kfir Y. Levy

Multi-armed Bandit Problems with Strategic Arms

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

Distribution-Dependent Analysis of Gibbs-ERM Principle

Ilja Kuzborskij, Nicolò Cesa-Bianchi, Csaba Szepesvari

Sample complexity of partition identification using multi-armed bandits

Sandeep Juneja, Subhashini Krishnasamy

The Optimal Approximation Factor in Density Estimation

Olivier Bousquet, Daniel Kane, Shay Moran

Planting trees in graphs, and finding them back

Laurent Massoulié, Ludovic Stephan, Don Towsley

Fast determinantal point processes via distortion-free intermediate sampling

Michal Derezinski

Is your function low dimensional?

Anindya De, Elchanan Mossel, Joe Neeman

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

Sharp Theoretical Analysis for Nonparametric Testing under Random Projection

Meimei Liu, Zuofeng Shang, Guang Cheng

Robustness of spectral methods for community detection

Ludovic Stephan, Laurent Massoulié

An Information-Theoretic Approach to Minimax Regret in Partial Monitoring

Tor Lattimore, Csaba Szepesvari

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

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

Near-optimal method for highly smooth convex optimization

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

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

Navin Goyal, Abhishek Shetty

Learning to Prune: Speeding up Repeated Computations

Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, Ellen Vitercik

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

Alexander Rakhlin, Xiyu Zhai

On Communication Complexity of Classification Problems

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

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

Belinda Tzen, Maxim Raginsky

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

Song Mei, Theodor Misiakiewicz, Andrea Montanari

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

Nadav Merlis, Shie Mannor

Combinatorial Algorithms for Optimal Design

Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, Weijun Xie

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

Budgeted Kernelized Bandits for Large Scale Gaussian Process Optimization

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

Combining Online Learning Guarantees

Ashok Cutkosky

Estimation of smooth densities in Wasserstein distance

Jonathan Weed, Quentin Berthet

Artificial Constraints and Hints for Unbounded Online Learning

Ashok Cutkosky

Inference under Local Constraints: Lower Bounds from Chi-Square Contractions

Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi

Communication and Memory Efficient Testing of Discrete Distributions

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

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

Adrien Taylor, Francis Bach

Learning rates for Gaussian mixtures under group invariance

Victor-Emmanuel Brunel

Optimal Tensor Methods in Smooth Convex and Uniformly Convex Optimization

Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, Cesar A. Uribe

Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting

Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, Chicheng Zhang

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

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi

Discrepancy, Coresets, and Sketches in Machine Learning

Zohar Karnin, Edo Liberty

When can unlabeled data improve the learning rate?

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

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

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

A Theory of Selective Prediction

Mingda Qiao, Gregory Valiant

Reconstructing Trees from Traces

Sami Davies, Miklos Racz, Cyrus Rashtchian

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Yin Tat Lee, Zhao Song, Qiuyi Zhang

Nonconvex sampling with the Metropolis-adjusted Langevin algorithm

Oren Mangoubi, Nisheeth K. Vishnoi

Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

Rong Ge, Zhize Li, Weiyao Wang, Xiang Wang

On Mean Estimation for General Norms with Statistical Queries

Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten

Maximum Entropy Distributions: Bit Complexity and Stability

Damian Straszak, Nisheeth K. Vishnoi

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

Henry Reeve, Ata Kaban

Testing Markov Chains Without Hitting

Yeshwanth Cherapanamjeri, Peter Bartlett

Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning

R. Srikant, Lei Ying

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

Dylan Foster, Andrej Risteski

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

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

Statistical Learning with a Nuisance Component

Dylan Foster, Vasilis Syrgkanis

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

Matthew Brennan, Guy Bresler

Affine Invariant Covariance Estimation for Heavy-Tailed Distributions

Dmitrii M. Ostrovskii, Alessandro Rudi

Learning Linear Dynamical Systems with Semi-Parametric Least Squares

Max Simchowitz, Ross Boczar, Benjamin Recht

Non-asymptotic Analysis of Biased Stochastic Approximation Scheme

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

Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression

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

On the Performance of Thompson Sampling on Logistic Bandits

Shi Dong, Tengyu Ma, Benjamin Van Roy

Lower Bounds for Locally Private Estimation via Communication Complexity

John Duchi, Ryan Rogers

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

Ivona Bezakova, Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda

Space lower bounds for linear prediction

Yuval Dagan, Gil Kur, Ohad Shamir

Testing Mixtures of Discrete Distributions

Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld

Universality of Computational Lower Bounds for Submatrix Detection

Matthew Brennan, Guy Bresler, Wasim Huleihel

How Hard is Robust Mean Estimation?

Samuel B. Hopkins, Jerry Li

Approximate Guarantees for Dictionary Learning

Aditya Bhaskara, Wai Ming Tai

Private Center Points and Learning of Halfspaces

Amos Beimel, Shay Moran, Kobbi NIssim, Uri Stemmer

Fast Mean Estimation with Sub-Gaussian Rates

Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter Bartlett

Better Algorithms for Stochastic Bandits with Adversarial Corruptions

Anupam Gupta, Tomer Koren, Kunal Talwar

Sample-Optimal Low-Rank Approximation of Distance Matrices

Piotr Indyk, Ali Vakilian, Tal Wagner, David Woodruff

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

Vitaly Feldman, Jan Vondrak

Computational Limitations in Robust Classification and Win-Win Results

Akshay Degwekar, Preetum Nakkiran, Vinod Vaikuntanathan

The implicit bias of gradient descent on nonseparable data

Ziwei Ji, Matus Telgarsky

Bandit Principal Component Analysis

Wojciech Kotlowski, Gergely Neu

A near-optimal algorithm for approximating the John Ellipsoid

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

Pure Entropic Regularization for MTS

Christian Coester, James R. Lee

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

Andreas Anastasiou, Krishnakumar Balasubramanian, Murat Erdogdu

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

Yingjie Fei, Yudong Chen

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

Peter Auer, Pratik Gajane, and Ronald Ortner

VC Classes are Adversarially Robustly Learnable, but Only Improperly

Omar Montasser, Steve Hanneke, Nathan Srebro

The Complexity of Making the Gradient Small in Stochastic Convex Optimization

Dylan Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, Blake Woodworth

Towards Testing Monotonicity of Distributions Over General Posets

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

On the Computational Power of Online Gradient Descent

Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang

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

Pedro Savarese, Itay Evron, Daniel Soudry, 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

Active Regression via Linear-Sample Sparsification

Xue Chen, Eric Price

Faster Algorithms for High-Dimensional Robust Covariance Estimation

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

Parameter-free Online Convex Optimization with Sub-Exponential Noise

Kwang-Sung Jun, Francesco Orabona

Computationally and Statistically Efficient Truncated Regression

Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Emmanouil Zampetakis

Lipschitz Adaptivity with Multiple Learning Rates in Online Learning

Zakaria Mhammedi, Wouter M. Koolen, Tim van Erven

The All-or-Nothing Phenomenon in Sparse Linear Regression

Galen Reeves, Jiaming Xu, Ilias Zadik

A Rank-1 Sketch for Matrix Multiplicative Weights

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

Optimal Learning for Mallows Block Model

Robert Busa-Fekete, Dimitris Fotakis, Balazs Szorenyi, Manolis Zampetakis

Generalization and learning under Dobrushin's condition

Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Siddhartha Jayanti

Call for papers

The 32nd Annual Conference on Learning Theory (COLT 2019) will take place in Phoenix, Arizona, June 25-28, 2019, as part of the ACM Federated Computing Research Conference, which also includes EC and STOC. We invite submissions of papers addressing theoretical aspects of machine learning and related topics. We strongly support a broad definition of learning theory, including, but not limited to:
- Design and analysis of learning algorithms
- Statistical and computational complexity of learning
- Optimization methods for learning
- Unsupervised and semi-supervised learning
- Interactive learning, planning and control, and reinforcement learning
- Online learning and decision-making under uncertainty
- Interactions of learning theory with other mathematical fields
- Artificial neural networks, including deep learning
- High-dimensional and non-parametric statistics
- Learning with algebraic or combinatorial structure
- Bayesian methods in learning
- Game theory and learning
- Learning with system constraints (e.g., privacy, computational, memory, communication)
- Learning from complex data: e.g., networks, time series
- Learning in other settings: e.g., computational social science, economics

Submissions by authors who are new to COLT are encouraged. While the primary focus of the conference is theoretical, the authors may support their analysis by including relevant experimental results.
All accepted papers will be presented in a single track at the conference. At least one of each paper’s authors should be present at the conference to present the work. Accepted papers will be published electronically in the Proceedings of Machine Learning Research (PMLR). The authors of accepted papers will have the option of opting-out of the proceedings in favor of a 1-page extended abstract. The full paper reviewed for COLT will then be placed on the arXiv repository.

Paper Awards:

COLT will award both best paper and best student paper awards. To be eligible for the best student paper award, the primary contributor(s) must be full-time students at the time of submission. For eligible papers, authors must indicate at submission time if they wish their paper to be considered for a student paper award. The program committee may decline to make these awards, or may split them among several papers.

Dual Submissions:

Submissions that are substantially similar to papers that have been previously published, accepted for publication, or submitted in parallel to other peer-reviewed conferences with proceedings may not be submitted to COLT, with the sole exception described below. The same policy applies to journals, unless the submission is a short version of a paper submitted to a journal, and not yet published. Authors must declare such dual submissions through the submission server.
In coordination with the STOC 2019 PC chair, we allow papers submitted to STOC to be simultaneously submitted to COLT provided that the authors (1) explicitly state that the submission is under consideration for STOC, (2) immediately withdraw the COLT submission if the STOC submission is accepted, and (3) agree to allow the (anonymized) STOC reviews to be provided to the COLT reviewers once they are available. The authors will be allowed to submit a rebuttal to the STOC reviews a few days after the STOC reviews are available (via the submission server).


Submissions are limited to 12 PMLR-formatted pages, plus unlimited additional pages for references and appendices. All details, proofs and derivations required to substantiate the results must be included in the submission, possibly in the appendices. However, the contribution, novelty and significance of submissions will be judged primarily based on the main text (without appendices), and so enough details, including proof details, must be provided in the main text to convince the reviewers of the submissions’ merits. Formatting and submission instructions can be found on the conference website:

Rebuttal Phase:

As in previous years, there will be a rebuttal phase during the review process. Initial reviews will be sent to authors before final decisions have been made. Authors will have the opportunity to provide a short response on the PC’s initial evaluation.

Important Dates:

All dates are in 2019.
- Paper submission deadline: February 1, 11:00 PM EST
- Author feedback: March 22-27
- Author notification: April 17
- Conference: June 25-28 (welcome reception on June 24)

Submission Instructions

Formatting and anonymization

Submissions are limited to 12 single-column JMLR-formatted pages, plus additional pages for references and appendices.
Please use the following: LaTeX style files and template.
COLT reviewing is not double-blind, and program committee members will have access to author identities. It is expressly allowed to make available online a non-anonymized version of the submission or any other material that might reveal the author identities (e.g., on an author’s web page, on arXiv). However, in order to aid in minimizing the effect of initial impressions based on author identity, and in order to allow program committee members to seek double-blind reviews from sub-referees, submissions should NOT include author names or other identifying information.

Submitting your paper

We will begin accepting submissions via OpenReview on January 11, 2019. Please note that, unlike at some of the other conferences that have used OpenReview, neither submissions nor the reviewing process will be public
The deadline for submissions is 11:00 PM EST on February 1, 2019.
Please contact the COLT program chairs at [email protected] if you have any questions about the policy or technical issues with the submission process.
We looking forward to reading your submissions!

Call for open problems

The Conference on Learning Theory (COLT) 2019 will include a session devoted to the presentation of open problems. A description of these problems will also appear in the COLT proceedings. The deadline for submission is Friday May 10 at 5pm PST. The write-up of an open problem should include:
  • A clearly defined problem
  • The motivation for studying the problem, with an argument why it is important and interesting
  • The current state of this problem (including any known partial or conjectured solutions and relevant references).
We encourage submissions of problems that have not been previously investigated theoretically, as long as there is a convincing reason to include the problem in the conference. You should be able to clearly express the problem in a short presentation. A monetary reward, or non-monetary but fun prize, reward is a great way to stimulate interest in solving the open problem. If you would like to submit a problem, please email it to Jake Abernethy by May 10, 2019, with the subject line “COLT 2019 Open Problem Submission”. Submissions should be at most 4 pages long and should be in the COLT 2019 JMLR format (found here). Submissions are non-anonymous; that is, they should contain authors' names. Examples of open problems from past years: Notification of acceptance or rejection will be sent out by Friday May 24, 2019. For questions please contact the COLT 2019 open problems chair, Jake Abernethy at [email protected].