COLT 2022

163 papers

Open Problem: Optimal Best Arm Identification with Fixed-Budget

Chao Qin

Open Problem: Finite-Time Instance Dependent Optimality for Stochastic Online Learning with Feedback Graphs

Teodor Vanislavov Marinov, Mehryar Mohri, Julian Zimmert

Open Problem: Better Differentially Private Learning Algorithms with Margin Guarantees

Raef Bassily, Mehryar Mohri, Ananda Theertha Suresh

Open Problem: Do you pay for Privacy in Online learning?

Amartya Sanyal, Giorgia Ramponi

Open Problem: Running time complexity of accelerated ℓ_1-regularized PageRank

Kimon Fountoulakis, Shenghao Yang

Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits

Sattar Vakili

Open Problem: Properly learning decision trees in polynomial time?

Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan

From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization

Nima Anari, Thuy-Duong Vuong

Damped Online Newton Step for Portfolio Selection

Zakaria Mhammedi, Alexander Rakhlin

Memorize to generalize: on the necessity of interpolation in high dimensional linear regression

Chen Cheng, John Duchi, Rohith Kuditipudi

High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks

Kangjie Zhou, Andrea Montanari

Multilevel Optimization for Inverse Problems

Simon Weissmann, Ashia Wilson, Jakob Zech

Stochastic linear optimization never overfits with quadratically-bounded losses on general data

Matus Telgarsky

Neural Networks can Learn Representations with Gradient Descent

Alexandru Damian, Jason Lee, Mahdi Soltanolkotabi

Better Private Algorithms for Correlation Clustering

Daogao Liu

Efficient Projection-Free Online Convex Optimization with Membership Oracle

Zakaria Mhammedi

Clustering with Queries under Semi-Random Noise

Alberto Del Pia, Mingchen Ma, Christos Tzamos

Orthogonal Statistical Learning with Self-Concordant Loss

Lang Liu, Carlos Cinelli, Zaïd Harchaoui

Strategizing against Learners in Bayesian Games

Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan

When Is Partially Observable Reinforcement Learning Not Scary?

Qinghua Liu, Alan Chung, Csaba Szepesvári, Chi Jin

Complete Policy Regret Bounds for Tallying Bandits

Dhruv Malik, Yuanzhi Li, Aarti Singh

The Query Complexity of Local Search and Brouwer in Rounds

Simina Branzei, Jiawei Li

Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information

Yonathan Efroni, Dylan J Foster, Dipendra Misra, Akshay Krishnamurthy, John Langford

On the power of adaptivity in statistical adversaries

Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan

Strong Memory Lower Bounds for Learning Natural Models

Gavin Brown, Mark Bun, Adam Smith

Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods

Frederic Koehler, Holden Lee, Andrej Risteski

Eigenspace Restructuring: A Principle of Space and Frequency in Neural Networks

Lechao Xiao

The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks

Emmanuel Abbe, Enric Boix Adsera, Theodor Misiakiewicz

Statistical and Computational Phase Transitions in Group Testing

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, Ilias Zadik

Robust Sparse Mean Estimation via Sum of Squares

Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas

Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds

Sepehr Assadi, Vaggos Chatziafratis, Jakub \Lącki, Vahab Mirrokni, Chen Wang

Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares

Blake Woodworth, Francis Bach, Alessandro Rudi

Can Q-learning be Improved with Advice?

Noah Golowich, Ankur Moitra

Non-Gaussian Component Analysis via Lattice Basis Reduction

Ilias Diakonikolas, Daniel Kane

Robustly-reliable learners under poisoning attacks

Maria-Florina Balcan, Avrim Blum, Steve Hanneke, Dravyansh Sharma

Scale-free Unconstrained Online Learning for Curved Losses

Jack J. Mayo, Hedi Hadiji, Tim van Erven

Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms

Milad Sefidgaran, Amin Gohari, Gaël RICHARD, Umut Simsekli

Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

Yujia Jin, Aaron Sidford, Kevin Tian

Learning a Single Neuron with Adversarial Label Noise via Gradient Descent

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

Universality of empirical risk minimization

Andrea Montanari, Basil N. Saeed

Faster online calibration without randomization: interval forecasts and the power of two choices

Chirag Gupta, Aaditya Ramdas

Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise

Ilias Diakonikolas, Daniel Kane

Chained generalisation bounds

Eugenio Clerico, Amitis Shidani, George Deligiannidis, Arnaud Doucet

Parameter-free Mirror Descent

Andrew Jacobsen, Ashok Cutkosky

On the Role of Channel Capacity in Learning Gaussian Mixture Models

Elad Romanov, Tamir Bendory, Or Ordentlich

Online Learning to Transport via the Minimal Selection Principle

Wenxuan Guo, YoonHaeng Hur, Tengyuan Liang, Chris Ryan

Efficient decentralized multi-agent learning in asymmetric queuing systems

Daniel Freund, Thodoris Lykouris, Wentao Weng

How catastrophic can catastrophic forgetting be in linear regression?

Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, Daniel Soudry

Private High-Dimensional Hypothesis Testing

Shyam Narayanan

Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models

Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun

On the well-spread property and its relation to linear regression

Hongjie Chen, Tommaso d’Orsi

Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies

Zihan Zhang, Xiangyang Ji, Simon Du

Learning to Control Linear Systems can be Hard

Anastasios Tsiamis, Ingvar M Ziemann, Manfred Morari, Nikolai Matni, George J. Pappas

Hardness of Maximum Likelihood Learning of DPPs

Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

Fast algorithm for overcomplete order-3 tensor decomposition

Jingqiu Ding, Tommaso d’Orsi, Chih-Hung Liu, David Steurer, Stefan Tiegel

The Structured Abstain Problem and the Lovász Hinge

Jessica J Finocchiaro, Rafael Frongillo, Enrique B Nueve

Assemblies of neurons learn to classify well-separated distributions

Max Dabagia, Santosh S Vempala, Christos Papadimitriou

Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits

Haipeng Luo, Mengxiao Zhang, Peng Zhao, Zhi-Hua Zhou

Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression

Theophile Thiery, Justin Ward

Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics

Asaf B Cassel, Alon Cohen, Tomer Koren

Private Matrix Approximation and Geometry of Unitary Orbits

Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, Nisheeth K. Vishnoi

Generalization Bounds via Convex Analysis

Gabor Lugosi, Gergely Neu

On The Memory Complexity of Uniformity Testing

Tomer Berg, Or Ordentlich, Ofer Shayevitz

Corruption-Robust Contextual Search through Density Updates

Renato Paes Leme, Chara Podimata, Jon Schneider

The Dynamics of Riemannian Robbins-Monro Algorithms

Mohammad Reza Karimi, Ya-Ping Hsieh, Panayotis Mertikopoulos, Andreas Krause

Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Yingli Ran, Zhao Zhang, Shaojie Tang

Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation

Dylan J Foster, Akshay Krishnamurthy, David Simchi-Levi, Yunzong Xu

Random Graph Matching in Geometric Models: the Case of Complete Graphs

Haoyu Wang, Yihong Wu, Jiaming Xu, Israel Yolou

Kernel interpolation in Sobolev spaces is not consistent in low dimensions

Simon Buchholz

Near optimal efficient decoding from pooled data

Max Hahn-Klimroth, Noela Müller

Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond

Matan Schliserman, Tomer Koren

On characterizations of learnability with computable learners

Tom F. Sterkenburg

Single Trajectory Nonparametric Learning of Nonlinear Dynamics

Ingvar M Ziemann, Henrik Sandberg, Nikolai Matni

Uniform Stability for First-Order Empirical Risk Minimization

Amit Attia, Tomer Koren

Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits

Julian Zimmert, Tor Lattimore

Thompson Sampling Achieves Õ(√T) Regret in Linear Quadratic Control

Taylan Kargin, Sahin Lale, Kamyar Azizzadenesheli, Animashree Anandkumar, Babak Hassibi

Low-Degree Multicalibration

Parikshit Gopalan, Michael P Kim, Mihir A Singhal, Shengjia Zhao

Sharp Constants in Uniformity Testing via the Huber Statistic

Shivam Gupta, Eric Price

Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering

Jennifer Tang

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication

Allen X Liu, Mark Sellke

Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin

Realizable Learning is All You Need

Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan

Improved analysis for a proximal algorithm for sampling

Yongxin Chen, Sinho Chewi, Adil SALIM, Andre Wibisono

On Almost Sure Convergence Rates of Stochastic Gradient Methods

Jun Liu, Ye Yuan

Understanding Riemannian Acceleration via a Proximal Extragradient Framework

Jikai Jin, Suvrit Sra

Towards a Theory of Non-Log-Concave Sampling:First-Order Stationarity Guarantees for Langevin Monte Carlo

Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil SALIM, Shunshi Zhang

Learning GMMs with Nearly Optimal Robustness Guarantees

Allen Liu, Ankur Moitra

Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling

Alekh Agarwal, Tong Zhang

Offline Reinforcement Learning with Realizability and Single-policy Concentrability

Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, Jason Lee

Minimax Regret Optimization for Robust Machine Learning under Distribution Shift

Alekh Agarwal, Tong Zhang

Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data

Spencer Frei, Niladri S Chatterji, Peter Bartlett

EM’s Convergence in Gaussian Latent Tree Models

Yuval Dagan, Vardis Kandiros, Constantinos Daskalakis

Toward Instance-Optimal State Certification With Incoherent Measurements

Sitan Chen, Jerry Li, Ryan O’Donnell

Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales

Jonathan Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant

Efficient Convex Optimization Requires Superlinear Memory

Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant

Making SGD Parameter-Free

Yair Carmon, Oliver Hinder

New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees

Dan Garber, Ben Kretzu

Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm

Meena Jagadeesan, Ilya Razenshteyn, Suriya Gunasekar

Mean-field nonparametric estimation of interacting particle systems

Rentian Yao, Xiaohui Chen, Yun Yang

Exact Community Recovery in Correlated Stochastic Block Models

Julia Gaudio, Miklós Z. Rácz, Anirudh Sridhar