COLT 2020

126 papers

Open Problem: Fast and Optimal Online Portfolio Selection

Tim van Erven, Dirk van der Hoeven, Wojciech Kotłowski, Wouter M. Koolen

Open Problem: Information Complexity of VC Learning

Thomas Steinke, Lydia Zakynthinou

Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection

Yuetian Luo, Anru R Zhang

Open Problem: Tight Convergence of SGD in Constant Dimension

Tomer Koren, Shahar Segal

Open Problem: Model Selection for Contextual Bandits

Dylan J. Foster, Akshay Krishnamurthy, Haipeng Luo

Wasserstein Control of Mirror Langevin Monte Carlo

Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, Marcelo Pereyra

Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding

Xiao-Tong Yuan, Ping Li

Learning a Single Neuron with Gradient Methods

Gilad Yehudai, Shamir Ohad

Non-asymptotic Analysis for Nonparametric Testing

Yun Yang, Zuofeng Shang, Guang Cheng

Tree-projected gradient descent for estimating gradient-sparse parameters on graphs

Sheng Xu, Zhou Fan, Sahand Negahban

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang

Kernel and Rich Regimes in Overparametrized Models

Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese

Taking a hint: How to leverage loss predictors in contextual bandits?

Chen-Yu Wei, Haipeng Luo, Alekh Agarwal

Active Learning for Identification of Linear Dynamical Systems

Andrew Wagenmaker, Kevin Jamieson

Balancing Gaussian vectors in high dimension

Paxton Turner, Raghu Meka, Philippe Rigollet

Estimation and Inference with Trees and Forests in High Dimensions

Vasilis Syrgkanis, Manolis Zampetakis

Reasoning About Generalization via Conditional Mutual Information

Thomas Steinke, Lydia Zakynthinou

Improper Learning for Non-Stochastic Control

Max Simchowitz, Karan Singh, Elad Hazan

Logistic Regression Regret: What’s the Catch?

Gil I Shamir

A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere

Marco Schmalhofer

How Good is SGD with Random Shuffling?

Itay Safran, Ohad Shamir

Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits

Chloé Rouyer, Yevgeny Seldin

List Decodable Subspace Recovery

Prasad Raghavendra, Morris Yau

Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning

Guannan Qu, Adam Wierman

Covariance-adapting algorithm for semi-bandits with application to sparse outcomes

Pierre Perrault, Michal Valko, Vianney Perchet

Adaptive Submodular Maximization under Stochastic Item Costs

Srinivasan Parthasarathy

Costly Zero Order Oracles

Renato Paes Leme, Jon Schneider

An Õ(m/ε^3.5)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints

Yin Tat Lee, Swati Padmanabhan

Efficient and robust algorithms for adversarial linear contextual bandits

Gergely Neu, Julia Olkhovskaya

Fast Rates for Online Prediction with Abstention

Gergely Neu, Nikita Zhivotovskiy

Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning

Mikito Nanashima

On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration

Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Peter L Bartlett, Michael I Jordan

Parallels Between Phase Transitions and Circuit Complexity?

Ankur Moitra, Elchanan Mossel, Colin Sandon

Information Theoretic Optimal Learning of Gaussian Graphical Models

Sidhant Misra, Marc Vuffray, Andrey Y. Lokhov

Lipschitz and Comparator-Norm Adaptivity in Online Learning

Zakaria Mhammedi, Wouter M. Koolen

Tight Lower Bounds for Combinatorial Multi-Armed Bandits

Nadav Merlis, Shie Mannor

Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation

Allen Liu, Ankur Moitra

Near-Optimal Algorithms for Minimax Optimization

Tianyi Lin, Chi Jin, Michael I. Jordan

Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model

Yingyu Liang, Hui Yuan

On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels

Tengyuan Liang, Alexander Rakhlin, Xiyu Zhai

Learning Over-Parametrized Two-Layer Neural Networks beyond NTK

Yuanzhi Li, Tengyu Ma, Hongyang R. Zhang

A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates

Zhixian Lei, Kyle Luh, Prayaag Venkat, Fred Zhang

Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo

Yin Tat Lee, Ruoqi Shen, Kevin Tian

A Closer Look at Small-loss Bounds for Bandits with Graph Feedback

Chung-Wei Lee, Haipeng Luo, Mengxiao Zhang

Exploration by Optimisation in Partial Monitoring

Tor Lattimore, Csaba Szepesvári

The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians

Jeongyeol Kwon, Constantine Caramanis

On Suboptimality of Least Squares with Application to Estimation of Convex Bodies

Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina

New Potential-Based Bounds for Prediction with Expert Advice

Vladimir A. Kobzar, Robert V. Kohn, Zhilei Wang

Information Directed Sampling for Linear Partial Monitoring

Johannes Kirschner, Tor Lattimore, Andreas Krause

Universal Approximation with Deep Narrow Networks

Patrick Kidger, Terry Lyons

Online Learning with Vector Costs and Bandits with Knapsacks

Thomas Kesselheim, Sahil Singla

Privately Learning Thresholds: Closing the Exponential Gap

Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, Uri Stemmer

Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity

Pritish Kamath, Omar Montasser, Nathan Srebro

Private Mean Estimation of Heavy-Tailed Distributions

Gautam Kamath, Vikrant Singhal, Jonathan Ullman

Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise

Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, Hoi-To Wai

Provably efficient reinforcement learning with linear function approximation

Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I Jordan

Gradient descent follows the regularization path for general losses

Ziwei Ji, Miroslav Dudík, Robert E. Schapire, Matus Telgarsky

Efficient improper learning for online logistic regression

Rémi Jézéquel, Pierre Gaillard, Alessandro Rudi

Robust causal inference under covariate shift via worst-case subpopulation treatment effects

Sookyo Jeong, Hongseok Namkoong

Precise Tradeoffs in Adversarial Training for Linear Regression

Adel Javanmard, Mahdi Soltanolkotabi, Hamed Hassani

Extrapolating the profile of a finite population

Soham Jana, Yury Polyanskiy, Yihong Wu

Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes

Yichun Hu, Nathan Kallus, Xiaojie Mao

Noise-tolerant, Reliable Active Classification with Comparison Queries

Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan

A Greedy Anytime Algorithm for Sparse PCA

Guy Holtzman, Adam Soffer, Dan Vilenchik

Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond

Oliver Hinder, Aaron Sidford, Nimit Sohoni

Faster Projection-free Online Learning

Elad Hazan, Edgar Minasyan

Bessel Smoothing and Multi-Distribution Property Estimation

Yi Hao, Ping Li

Locally Private Hypothesis Selection

Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu

Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar

No-Regret Prediction in Marginally Stable Systems

Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang

Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices

Cedric Gerbelot, Alia Abbara, Florent Krzakala

On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems

Dan Garber

From tree matching to sparse graph alignment

Luca Ganassali, Laurent Massoulié

Rigorous Guarantees for Tyler’s M-Estimator via Quantum Expansion

William Cole Franks, Ankur Moitra

Efficient Parameter Estimation of Truncated Boolean Product Distributions

Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos

Embedding Dimension of Polyhedral Losses

Jessie Finocchiaro, Rafael Frongillo, Bo Waggoner

Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

Kefan Dong, Jian Peng, Yining Wang, Yuan Zhou

Consistent recovery threshold of hidden nearest neighbor graphs

Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks

Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis

Learning Halfspaces with Massart Noise Under Structured Distributions

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

Approximation Schemes for ReLU Regression

Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, Mahdi Soltanolkotabi

Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities

Jelena Diakonikolas

High probability guarantees for stochastic convex optimization

Damek Davis, Dmitriy Drusvyatskiy

PAC learning with stable and private predictions

Yuval Dagan, Vitaly Feldman

Optimal Group Testing

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick

Pessimism About Unknown Unknowns Inspires Conservatism

Michael K. Cohen, Marcus Hutter

ODE-Inspired Analysis for the Biological Version of Oja’s Rule in Solving Streaming PCA

Chi-Ning Chou, Mien Brabeeba Wang

Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss

Lénaïc Chizat, Francis Bach

Gradient descent algorithms for Bures-Wasserstein barycenters

Sinho Chewi, Tyler Maunu, Philippe Rigollet, Austin J. Stromme

The Influence of Shape Constraints on the Thresholding Bandit Problem

James Cheshire, Pierre Menard, Alexandra Carpentier

Learning Polynomials in Few Relevant Dimensions

Sitan Chen, Raghu Meka

Bounds in query learning

Hunter Chase, James Freitag

The estimation error of general first order methods

Michael Celentano, Andrea Montanari, Yuchen Wu

Efficient, Noise-Tolerant, and Private Learning via Boosting

Mark Bun, Marco Leandro Carmosino, Jessica Sorrell

Highly smooth minimization of non-smooth problems

Brian Bullins

Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without

Sébastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke

How to Trap a Gradient Flow

Sébastien Bubeck, Dan Mikulincer

Coordination without communication: optimal regret in two players multi-armed bandits

Sébastien Bubeck, Thomas Budzinski

ID3 Learns Juntas for Smoothed Product Distributions

Alon Brutzkus, Amit Daniely, Eran Malach

A Corrective View of Neural Networks: Representation, Memorization and Learning

Guy Bresler, Dheeraj Nagaraj