ML Anthology

COLT 2020

125 papers

A Closer Look at Small-Loss Bounds for Bandits with Graph Feedback Chung-Wei Lee, Haipeng Luo, Mengxiao Zhang
PDF
A Corrective View of Neural Networks: Representation, Memorization and Learning Guy Bresler, Dheeraj Nagaraj
PDF
A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates Zhixian Lei, Kyle Luh, Prayaag Venkat, Fred Zhang
PDF
A Greedy Anytime Algorithm for Sparse PCA Guy Holtzman, Adam Soffer, Dan Vilenchik
PDF
A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere Marco Schmalhofer
PDF
Active Learning for Identification of Linear Dynamical Systems Andrew Wagenmaker, Kevin Jamieson
PDF
Active Local Learning Arturs Backurs, Avrim Blum, Neha Gupta
PDF
Adaptive Submodular Maximization Under Stochastic Item Costs Srinivasan Parthasarathy
PDF
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis
PDF
An $\widetilde\mathcal{O}(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints Yin Tat Lee, Swati Padmanabhan
PDF
Approximate Is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity Pritish Kamath, Omar Montasser, Nathan Srebro
PDF
Approximation Schemes for ReLU Regression Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, Mahdi Soltanolkotabi
PDF
Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression Beyond Gaussian Matrices Cédric Gerbelot, Alia Abbara, Florent Krzakala
PDF
Balancing Gaussian Vectors in High Dimension Paxton Turner, Raghu Meka, Philippe Rigollet
PDF
Bessel Smoothing and Multi-Distribution Property Estimation Yi Hao, Ping Li
PDF
Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation Allen Liu, Ankur Moitra
PDF
Bounds in Query Learning Hunter Chase, James Freitag
PDF
Calibrated Surrogate Losses for Adversarially Robust Classification Han Bao, Clay Scott, Masashi Sugiyama
PDF
Closure Properties for Private Classification and Online Prediction Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer
PDF
Complexity Guarantees for Polyak Steps with Momentum Mathieu Barré, Adrien Taylor, Alexandre d’Aspremont
PDF
Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang
PDF
Coordination Without Communication: Optimal Regret in Two Players Multi-Armed Bandits Sébastien Bubeck, Thomas Budzinski
PDF
Costly Zero Order Oracles Renato Paes Leme, Jon Schneider
PDF
Covariance-Adapting Algorithm for Semi-Bandits with Application to Sparse Outcomes Pierre Perrault, Michal Valko, Vianney Perchet
PDF
Data-Driven Confidence Bands for Distributed Nonparametric Regression Valeriy Avanesov
PDF
Dimension-Free Bounds for Chasing Convex Functions C.J. Argue, Anupam Gupta, Guru Guruganesh
PDF
Distributed Signal Detection Under Communication Constraints Jayadev Acharya, Clément L Canonne, Himanshu Tyagi
PDF
Domain Compression and Its Application to Randomness-Optimal Distributed Goodness-of-Fit Jayadev Acharya, Clément L Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi
PDF
Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits Gergely Neu, Julia Olkhovskaya
PDF
Efficient Improper Learning for Online Logistic Regression Rémi Jézéquel, Pierre Gaillard, Alessandro Rudi
PDF
Efficient Parameter Estimation of Truncated Boolean Product Distributions Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
PDF
Efficient, Noise-Tolerant, and Private Learning via Boosting Mark Bun, Marco Leandro Carmosino, Jessica Sorrell
PDF
Embedding Dimension of Polyhedral Losses Jessie Finocchiaro, Rafael Frongillo, Bo Waggoner
PDF
Estimating Principal Components Under Adversarial Perturbations Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
PDF
Estimation and Inference with Trees and Forests in High Dimensions Vasilis Syrgkanis, Manolis Zampetakis
PDF
Exploration by Optimisation in Partial Monitoring Tor Lattimore, Csaba Szepesvári
PDF
Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning Mikito Nanashima
PDF
Extrapolating the Profile of a Finite Population Soham Jana, Yury Polyanskiy, Yihong Wu
PDF
Fast Rates for Online Prediction with Abstention Gergely Neu, Nikita Zhivotovskiy
PDF
Faster Projection-Free Online Learning Elad Hazan, Edgar Minasyan
PDF
Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent James P. Bailey, Gauthier Gidel, Georgios Piliouras
PDF
Finite Time Analysis of Linear Two-Timescale Stochastic Approximation with Markovian Noise Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, Hoi-To Wai
PDF
Finite-Time Analysis of Asynchronous Stochastic Approximation and $q$-Learning Guannan Qu, Adam Wierman
PDF
Free Energy Wells and Overlap Gap Property in Sparse PCA Gérard Ben Arous, Alexander S. Wein, Ilias Zadik
PDF
From Nesterov’s Estimate Sequence to Riemannian Acceleration Kwangjun Ahn, Suvrit Sra
PDF
From Tree Matching to Sparse Graph Alignment Luca Ganassali, Laurent Massoulié
PDF
Gradient Descent Algorithms for Bures-Wasserstein Barycenters Sinho Chewi, Tyler Maunu, Philippe Rigollet, Austin J. Stromme
PDF
Gradient Descent Follows the Regularization Path for General Losses Ziwei Ji, Miroslav Dudík, Robert E. Schapire, Matus Telgarsky
PDF
Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities Jelena Diakonikolas
PDF
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts Models Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda
PDF
Hierarchical Clustering: A 0.585 Revenue Approximation Noga Alon, Yossi Azar, Danny Vainstein
PDF
High Probability Guarantees for Stochastic Convex Optimization Damek Davis, Dmitriy Drusvyatskiy
PDF
Highly Smooth Minimization of Non-Smooth Problems Brian Bullins
PDF
How Good Is SGD with Random Shuffling? Itay Safran, Ohad Shamir
PDF
How to Trap a Gradient Flow Sébastien Bubeck, Dan Mikulincer
PDF
ID3 Learns Juntas for Smoothed Product Distributions Alon Brutzkus, Amit Daniely, Eran Malach
PDF
Implicit Bias of Gradient Descent for Wide Two-Layer Neural Networks Trained with the Logistic Loss Lénaïc Chizat, Francis Bach
PDF
Implicit Regularization for Deep Neural Networks Driven by an Ornstein-Uhlenbeck like Process Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant
PDF
Improper Learning for Non-Stochastic Control Max Simchowitz, Karan Singh, Elad Hazan
PDF
Information Directed Sampling for Linear Partial Monitoring Johannes Kirschner, Tor Lattimore, Andreas Krause
PDF
Information Theoretic Optimal Learning of Gaussian Graphical Models Sidhant Misra, Marc Vuffray, Andrey Y. Lokhov
PDF
Kernel and Rich Regimes in Overparametrized Models Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, Nathan Srebro
PDF
Last Iterate Is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar
PDF
Learning a Single Neuron with Gradient Methods Gilad Yehudai, Shamir Ohad
PDF
Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model Yingyu Liang, Hui Yuan
PDF
Learning Halfspaces with Massart Noise Under Structured Distributions Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
PDF
Learning Over-Parametrized Two-Layer Neural Networks Beyond NTK Yuanzhi Li, Tengyu Ma, Hongyang R. Zhang
PDF
Learning Polynomials in Few Relevant Dimensions Sitan Chen, Raghu Meka
PDF
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang
PDF
Lipschitz and Comparator-Norm Adaptivity in Online Learning Zakaria Mhammedi, Wouter M. Koolen
PDF
List Decodable Subspace Recovery Prasad Raghavendra, Morris Yau
PDF
Locally Private Hypothesis Selection Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang
PDF
Logistic Regression Regret: What’s the Catch? Gil I Shamir
PDF
Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo Yin Tat Lee, Ruoqi Shen, Kevin Tian
PDF
Model-Based Reinforcement Learning with a Generative Model Is Minimax Optimal Alekh Agarwal, Sham Kakade, Lin F. Yang
PDF
Near-Optimal Algorithms for Minimax Optimization Tianyi Lin, Chi Jin, Michael I. Jordan
PDF
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond Oliver Hinder, Aaron Sidford, Nimit Sohoni
PDF
Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding Xiao-Tong Yuan, Ping Li
PDF
New Potential-Based Bounds for Prediction with Expert Advice Vladimir A. Kobzar, Robert V. Kohn, Zhilei Wang
PDF
No-Regret Prediction in Marginally Stable Systems Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang
PDF
Noise-Tolerant, Reliable Active Classification with Comparison Queries Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
PDF
Non-Asymptotic Analysis for Nonparametric Testing Yun Yang, Zuofeng Shang, Guang Cheng
PDF
Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate with Collision Information, Sublinear Without Sébastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke
PDF
ODE-Inspired Analysis for the Biological Version of Oja’s Rule in Solving Streaming PCA Chi-Ning Chou, Mien Brabeeba Wang
PDF
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
PDF
On Suboptimality of Least Squares with Application to Estimation of Convex Bodies Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina
PDF
On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems Dan Garber
PDF
On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels Tengyuan Liang, Alexander Rakhlin, Xiyu Zhai
PDF
Online Learning with Vector Costs and Bandits with Knapsacks Thomas Kesselheim, Sahil Singla
PDF
Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection Yuetian Luo, Anru R Zhang
PDF
Open Problem: Fast and Optimal Online Portfolio Selection Tim Van Erven, Dirk Van der Hoeven, Wojciech Kotłowski, Wouter M. Koolen
PDF
Open Problem: Information Complexity of VC Learning Thomas Steinke, Lydia Zakynthinou
PDF
Open Problem: Model Selection for Contextual Bandits Dylan J. Foster, Akshay Krishnamurthy, Haipeng Luo
PDF
Open Problem: Tight Convergence of SGD in Constant Dimension Tomer Koren, Shahar Segal
PDF
Optimal Group Testing Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick
PDF
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes Alekh Agarwal, Sham M Kakade, Jason D Lee, Gaurav Mahajan
PDF
PAC Learning with Stable and Private Predictions Yuval Dagan, Vitaly Feldman
PDF
Pan-Private Uniformity Testing Kareem Amin, Matthew Joseph, Jieming Mao
PDF
Parallels Between Phase Transitions and Circuit Complexity? Ankur Moitra, Elchanan Mossel, Colin Sandon
PDF
Pessimism About Unknown Unknowns Inspires Conservatism Michael K. Cohen, Marcus Hutter
PDF
Precise Tradeoffs in Adversarial Training for Linear Regression Adel Javanmard, Mahdi Soltanolkotabi, Hamed Hassani
PDF
Private Mean Estimation of Heavy-Tailed Distributions Gautam Kamath, Vikrant Singhal, Jonathan Ullman
PDF
Privately Learning Thresholds: Closing the Exponential Gap Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, Uri Stemmer
PDF
Proper Learning, Helly Number, and an Optimal SVM Bound Olivier Bousquet, Steve Hanneke, Shay Moran, Nikita Zhivotovskiy
PDF
Provably Efficient Reinforcement Learning with Linear Function Approximation Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I Jordan
PDF
Reasoning About Generalization via Conditional Mutual Information Thomas Steinke, Lydia Zakynthinou
PDF
Reducibility and Statistical-Computational Gaps from Secret Leakage Matthew Brennan, Guy Bresler
PDF
Rigorous Guarantees for Tyler’s M-Estimator via Quantum Expansion William Cole Franks, Ankur Moitra
PDF
Robust Causal Inference Under Covariate Shift via Worst-Case Subpopulation Treatment Effects Sookyo Jeong, Hongseok Namkoong
PDF
Root-N-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank Kefan Dong, Jian Peng, Yining Wang, Yuan Zhou
PDF
Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, Karthik Sridharan
PDF
Selfish Robustness and Equilibria in Multi-Player Bandits Etienne Boursier, Vianney Perchet
PDF
Sharper Bounds for Uniformly Stable Algorithms Olivier Bousquet, Yegor Klochkov, Nikita Zhivotovskiy
PDF
Smooth Contextual Bandits: Bridging the Parametric and Non-Differentiable Regret Regimes Yichun Hu, Nathan Kallus, Xiaojie Mao
PDF
Taking a Hint: How to Leverage Loss Predictors in Contextual Bandits? Chen-Yu Wei, Haipeng Luo, Alekh Agarwal
PDF
The EM Algorithm Gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians Jeongyeol Kwon, Constantine Caramanis
PDF
The Estimation Error of General First Order Methods Michael Celentano, Andrea Montanari, Yuchen Wu
PDF
The Gradient Complexity of Linear Regression Mark Braverman, Elad Hazan, Max Simchowitz, Blake Woodworth
PDF
The Influence of Shape Constraints on the Thresholding Bandit Problem James Cheshire, Pierre Menard, Alexandra Carpentier
PDF
Tight Lower Bounds for Combinatorial Multi-Armed Bandits Nadav Merlis, Shie Mannor
PDF
Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs Sheng Xu, Zhou Fan, Sahand Negahban
PDF
Tsallis-INF for Decoupled Exploration and Exploitation in Multi-Armed Bandits Chloé Rouyer, Yevgeny Seldin
PDF
Universal Approximation with Deep Narrow Networks Patrick Kidger, Terry Lyons
PDF
Wasserstein Control of Mirror Langevin Monte Carlo Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, Marcelo Pereyra
PDF
Winnowing with Gradient Descent Ehsan Amid, Manfred K. Warmuth
PDF