COLT 2024

170 papers

Open problem: Convergence of single-timescale mean-field Langevin descent-ascent for two-player zero-sum games

Guillaume Wang, Lénaïc Chizat

Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning

Sattar Vakili

Open Problem: Anytime Convergence Rate of Gradient Descent

Guy Kornowski, Ohad Shamir

Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy

Bingshan Hu, Nishant A. Mehta

Open problem: Direct Sums in Learning Theory

Steve Hanneke, Shay Moran, Waknine Tom

Open Problem: Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization

Xinyi Chen, Elad Hazan

Open Problem: Tight Characterization of Instance-Optimal Identity Testing

Clement Canonne

Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?

Achraf Azize, Debabrota Basu

Open Problem: Can Local Regularization Learn All Multiclass Problems?

Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng

Gap-Free Clustering: Sensitivity and Robustness of SDP

Matthew Zurek, Yudong Chen

Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing (Extended Abstract)

Yihan Zhang, Hong Chang Ji, Ramji Venkataramanan, Marco Mondelli

Optimal Multi-Distribution Learning

Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S Du, Jason D Lee

Settling the sample complexity of online reinforcement learning

Zihan Zhang, Yuxin Chen, Jason D Lee, Simon S Du

Fast two-time-scale stochastic gradient method with applications in reinforcement learning

Sihan Zeng, Thinh Doan

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract

Xifan Yu, Ilias Zadik, Peiyuan Zhang

Top-K ranking with a monotone adversary

Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma

Multiple-output composite quantile regression through an optimal transport lens

Xuzhi Yang, Tengyao Wang

Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization

Jiancong Xiao, Ruoyu Sun, Qi Long, Weijie Su

Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency

Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, Bin Yu

Oracle-Efficient Hybrid Online Learning with Unknown Distribution

Changlong Wu, Jin Sima, Wojciech Szpankowski

Optimal score estimation via empirical Bayes smoothing

Andre Wibisono, Yihong Wu, Kaylee Yingxi Yang

Nonlinear spiked covariance matrices and signal propagation in deep neural networks

Zhichao Wang, Denny Wu, Zhou Fan

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation Extended Abstract

Ziao Wang, Weina Wang, Lele Wang

Nearly Optimal Regret for Decentralized Online Convex Optimization

Yuanyu Wan, Tong Wei, Mingli Song, Lijun Zhang

Pruning is Optimal for Learning Sparse Features in High-Dimensions

Nuri Mert Vural, Murat A Erdogdu

Improved Hardness Results for Learning Intersections of Halfspaces

Stefan Tiegel

Second Order Methods for Bandit Optimization and Control

Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, Elad Hazan

A non-backtracking method for long matrix and tensor completion

Ludovic Stephan, Yizhe Zhu

Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm

Vishwak Srinivasan, Andre Wibisono, Ashia Wilson

A Non-Adaptive Algorithm for the Quantitative Group Testing Problem

Mahdi Soleymani, Tara Javidi

Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality (extended abstract)

Chen Siyu, Sheen Heejune, Wang Tianhao, Yang Zhuoran

Adversarial Online Learning with Temporal Feedback Graphs

Khashayar Gatmiry, Jon Schneider

Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability

Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, Eric Moulines

Provable Advantage in Quantum PAC Learning

Wilfred Salmon, Sergii Strelchuk, Tom Gur

Online Structured Prediction with Fenchel–Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss

Shinsaku Sakaue, Han Bao, Taira Tsuchiya, Taihei Oki

Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions

Yilong Qin, Andrej Risteski

Online Learning with Set-valued Feedback

Vinod Raman, UNIQUE SUBEDI, Ambuj Tewari

Apple Tasting: Combinatorial Dimensions and Minimax Rates

Vinod Raman, UNIQUE SUBEDI, Ananth Raman, Ambuj Tewari

On the Distance from Calibration in Sequential Prediction

Mingda Qiao, Letian Zheng

Dimension-free Structured Covariance Estimation

Nikita Puchkin, Maxim Rakhuba

Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity

Alireza F. Pour, Hassan Ashtiani, Shahab Asoodeh

Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes

Naty Peter, Eliad Tsfadia, Jonathan Ullman

The Sample Complexity of Simple Binary Hypothesis Testing

Ankit Pensia, Varun Jog, Po-ling Loh

The sample complexity of multi-distribution learning

Binghui Peng

The complexity of approximate (coarse) correlated equilibrium for incomplete information games

Binghui Peng, Aviad Rubinstein

The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication

Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U Stich

Depth Separation in Norm-Bounded Infinite-Width Neural Networks

Suzanna Parkinson, Greg Ongie, Rebecca Willett, Ohad Shamir, Nathan Srebro

Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations

Kazusato Oko, Yujin Song, Taiji Suzuki, Denny Wu

Robust Distribution Learning with Local and Global Adversarial Corruptions (extended abstract)

Sloan Nietert, Ziv Goldfeld, Soroosh Shafiee

Optimistic Information Directed Sampling

Gergely Neu, Matteo Papini, Ludovic Schwartz

Exact Mean Square Linear Stability Analysis for SGD

Rotem Mulayoff, Tomer Michaeli

Finding Super-spreaders in Network Cascades

Elchanan Mossel, Anirudh Sridhar

Fundamental Limits of Non-Linear Low-Rank Matrix Estimation

Pierre Mergny, Justin Ko, Florent Krzakala, Lenka Zdeborová

Fast, blind, and accurate: Tuning-free sparse regression with global linear convergence

Claudio Mayrink Verdun, Oleh Melnyk, Felix Krahmer, Peter Jung

Low-degree phase transitions for detecting a planted clique in sublinear time

Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein

Harmonics of Learning: Universal Fourier Features Emerge in Invariant Networks

Giovanni Luca Marchetti, Christopher J Hillar, Danica Kragic, Sophia Sanborn

Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs

Davide Maran, Alberto Maria Metelli, Matteo Papini, Marcello Restelli

Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion

Jianhao Ma, Salar Fattahi

Linear bandits with polylogarithmic minimax regret

Josep Lumbreras, Marco Tomamichel

Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics

Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang

The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations

Quanquan C. Liu, Vaidehi Srinivas

Spatial properties of Bayesian unsupervised trees

Linxi Liu, Li Ma

The role of randomness in quantum state certification with unentangled measurements

Yuhan Liu, Jayadev Acharya

Online Policy Optimization in Unknown Nonlinear Systems

Yiheng Lin, James A. Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung

Optimistic Rates for Learning from Label Proportions

Gene Li, Lin Chen, Adel Javanmard, Vahab Mirrokni

Minimax-optimal reward-agnostic exploration in reinforcement learning

Gen Li, Yuling Yan, Yuxin Chen, Jianqing Fan

Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds

Jongyeong Lee, Junya Honda, Shinji Ito, Min-hwan Oh

Inherent limitations of dimensions for characterizing learnability of distribution classes

Tosca Lechner, Shai Ben-David

Better-than-KL PAC-Bayes Bounds

Ilja Kuzborskij, Kwang-Sung Jun, Yulian Wu, Kyoungseok Jang, Francesco Orabona

Accelerated Parameter-Free Stochastic Optimization

Itai Kreisler, Maor Ivgi, Oliver Hinder, Yair Carmon

Simple online learning with consistent oracle

Alexander Kozachinskiy, Tomasz Steifer

Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling

Yunbum Kook, Santosh S. Vempala

Sampling from the Mean-Field Stationary Distribution

Yunbum Kook, Matthew S. Zhang, Sinho Chewi, Murat A. Erdogdu, Mufan (Bill) Li

Active Learning with Simple Questions

Kontonis Vasilis, Ma Mingchen, Tzamos Christos

Convergence of Kinetic Langevin Monte Carlo on Lie groups

Lingkai Kong, Molei Tao

Superconstant Inapproximability of Decision Tree Learning

Caleb Koch, Carmen Strassle, Li-Yang Tan

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Testable Learning with Distribution Shift

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps

Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Choosing the p in Lp Loss: Adaptive Rates for Symmetric Mean Estimation

Yu-Chun Kao, Min Xu, Cun-hui Zhang

New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions

Yuqian Cheng, Daniel Kane, Zheng Zhicheng

Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening (Extended Abstract)

Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis

Some Constructions of Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise

Matthew Joseph, Alexander Yu

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract)

Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh

Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space

Yiheng Jiang, Sinho Chewi, Aram-Alexandre Pooladian

Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data

Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, Chen-Yu Wei

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

Arun Jambulapati, Aaron Sidford, Kevin Tian

Black-Box k-to-1-PCA Reductions: Theory and Applications

Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia

Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds

Shinji Ito, Taira Tsuchiya, Junya Honda

Reconstructing the Geometry of Random Geometric Graphs (Extended Abstract)

Han Huang, Pakawut Jiradilok, Elchanan Mossel

Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs

Dong Huang, Xianwen Song, Pengkun Yang

Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo

Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, Tong Zhang

On the sample complexity of parameter estimation in logistic regression with normal design

Daniel Hsu, Arya Mazumdar

Adversarially-Robust Inference on Trees via Belief Propagation

Samuel B. Hopkins, Anqui Li

List Sample Compression and Uniform Convergence

Steve Hanneke, Shay Moran, Waknine Tom

The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement

Steve Hanneke

Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes

Yanjun Han, Tianze Jiang, Yihong Wu

Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation

Shivam Gupta, Samuel Hopkins, Eric Price

Stochastic Constrained Contextual Bandits via Lyapunov Optimization Based Estimation to Decision Framework

Hengquan Guo, Xin Liu

Community detection in the hypergraph stochastic block model and reconstruction on hypertrees

Yuzhou Gu, Aaradhya Pandey