COLT 2023

170 papers

Open Problem: Is There a First-Order Method that Only Converges to Local Minimax Optima?

Jiseok Chae, Kyuwon Kim, Donghwan Kim

Open Problem: Polynomial linearly-convergent method for g-convex optimization?

Christopher Criscitiello, David Martínez-Rubio, Nicolas Boumal

Open Problem: The Sample Complexity of Multi-Distribution Learning for VC Classes

Pranjal Awasthi, Nika Haghtalab, Eric Zhao

Open Problem: Learning sparse linear concepts by priming the features

Manfred K. Warmuth, Ehsan Amid

Open problem: log(n) factor in "Local Glivenko-Cantelli"

Doron Cohen, Aryeh Kontorovich

Efficient median of means estimator

Stanislav Minsker

Fine-Grained Distribution-Dependent Learning Curves

Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, Ilya Tolstikhin

Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique

Guy Bresler, Tianze Jiang

Bandit Learnability can be Undecidable

Steve Hanneke, Liu Yang

Limits of Model Selection under Transfer Learning

Steve Hanneke, Samory Kpotufe, Yasaman Mahdaviyeh

On a Class of Gibbs Sampling over Networks

Bo Yuan, Jiaojiao Fan, Jiaming Liang, Andre Wibisono, Yongxin Chen

The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks

Yuan Cao, Difan Zou, Yuanzhi Li, Quanquan Gu

Local Risk Bounds for Statistical Aggregation

Jaouad Mourtada, Tomas Vaskevicius, Nikita Zhivotovskiy

Multiclass Online Learning and Uniform Convergence

Steve Hanneke, Shay Moran, Vinod Raman, UNIQUE SUBEDI, Ambuj Tewari

Universal Rates for Multiclass Learning

Steve Hanneke, Shay Moran, Qian Zhang

Learning Narrow One-Hidden-Layer ReLU Networks

Sitan Chen, Zehao Dou, Surbhi Goel, Adam Klivans, Raghu Meka

Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions

Gavin Brown, Samuel Hopkins, Adam Smith

Sharp thresholds in inference of planted subgraphs

Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization

Alexandros Hollender, Emmanouil Zampetakis

A Blackbox Approach to Best of Both Worlds in Bandits and Beyond

Chris Dann, Chen-Yu Wei, Julian Zimmert

The Aggregation–Heterogeneity Trade-off in Federated Learning

Xuyang Zhao, Huiyuan Wang, Wei LIN

Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes

Zihan Zhang, Qiaomin Xie

Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions

Ilias Diakonikolas, Sushrut Karmalkar, Jong Ho Park, Christos Tzamos

Improper Multiclass Boosting

Nataly Brukhim, Steve Hanneke, Shay Moran

Minimax optimal testing by classification

Patrik R. Gerber, Yanjun Han, Yury Polyanskiy

Moments, Random Walks, and Limits for Spectrum Approximation

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

Is Planted Coloring Easier than Planted Clique?

Pravesh Kothari, Santosh S Vempala, Alexander S Wein, Jeff Xu

Sparsity-aware generalization theory for deep neural networks

Ramchandran Muthukumar, Jeremias Sulam

Statistical and Computational Limits for Tensor-on-Tensor Association Detection

Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo, Anru Zhang

Kernelized Diffusion Maps

Loucas Pillaud-Vivien, Francis Bach

Empirical Bayes via ERM and Rademacher complexities: the Poisson model

Soham Jana, Yury Polyanskiy, Anzo Z. Teh, Yihong Wu

STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games

Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis, Emmanouil Zampetakis

U-Calibration: Forecasting for an Unknown Agent

Bobby Kleinberg, Renato Paes Leme, Jon Schneider, Yifeng Teng

Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing

Mahdi Soltanolkotabi, Dominik Stöger, Changzhi Xie

Ticketed Learning–Unlearning Schemes

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari

Active Coverage for PAC Reinforcement Learning

Aymen Al-Marjani, Andrea Tirinzoni, Emilie Kaufmann

PAC Verification of Statistical Algorithms

Saachi Mutreja, Jonathan Shafer

Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency

Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, Quanquan Gu

Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage

Ibrahim Issa, Amedeo Roberto Esposito, Michael Gastpar

On Classification-Calibration of Gamma-Phi Losses

Yutong Wang, Clayton Scott

ℓ_p-Regression in the Arbitrary Partition Model of Communication

Yi Li, Honghao Lin, David Woodruff

Shortest Program Interpolation Learning

Naren Sarayu Manoj, Nathan Srebro

Generalization Guarantees via Algorithm-dependent Rademacher Complexity

Sarah Sachs, Tim van Erven, Liam Hodgkinson, Rajiv Khanna, Umut Simsekli

Fast Algorithms for a New Relaxation of Optimal Transport

Moses Charikar, Beidi Chen, Christopher Re, Erik Waingarten

Finite-Sample Symmetric Mean Estimation with Fisher Information Rate

Shivam Gupta, Jasper C. H. Lee, Eric Price

Sparse PCA Beyond Covariance Thresholding

Gleb Novikov

Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal

Moise Blanchard, Junhui Zhang, Patrick Jaillet

Law of Large Numbers for Bayesian two-layer Neural Network trained with Variational Inference

Arnaud Descours, Tom Huix, Arnaud Guillin, Manon Michel, Eric Moulines

Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression

Aleksandrs Slivkins, Karthik Abinav Sankararaman, Dylan J Foster

Differentially Private and Lazy Online Convex Optimization

Naman Agarwal, Satyen Kale, Karan Singh, Abhradeep Thakurta

Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning

Zeyuan Allen-Zhu, Yuanzhi Li

Deterministic Nonsmooth Nonconvex Optimization

Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, Manolis Zampetakis

Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators

Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh Vempala

Quasi-Newton Steps for Efficient Online Exp-Concave Optimization

Zakaria Mhammedi, Khashayar Gatmiry

Zeroth-order Optimization with Weak Dimension Dependency

Pengyun Yue, Long Yang, Cong Fang, Zhouchen Lin

Sharp analysis of EM for learning mixtures of pairwise differences

Abhishek Dhawan, Cheng Mao, Ashwin Pananjady

Minimizing Dynamic Regret on Geodesic Metric Spaces

Zihao Hu, Guanghui Wang, Jacob D. Abernethy

Entropic characterization of optimal rates for learning Gaussian mixtures

Zeyu Jia, Yury Polyanskiy, Yihong Wu

Near-optimal fitting of ellipsoids to random points

Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein

The Complexity of Markov Equilibrium in Stochastic Games

Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang

Precise Asymptotic Analysis of Deep Random Feature Models

David Bosch, Ashkan Panahi, Babak Hassibi

The Expressive Power of Tuning Only the Normalization Layers

Angeliki Giannou, Shashank Rajput, Dimitris Papailiopoulos

Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms

Aniket Das, Dheeraj M. Nagaraj, Anant Raj

Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions

Jingqiu Ding, Tommaso d’Orsi, Yiding Hua, David Steurer

Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient

Dylan J. Foster, Noah Golowich, Yanjun Han

Algorithmically Effective Differentially Private Synthetic Data

Yiyun He, Roman Vershynin, Yizhe Zhu

Asymptotic confidence sets for random linear programs

Shuyu Liu, Florentina Bunea, Jonathan Niles-Weed

A High-dimensional Convergence Theorem for U-statistics with Applications to Kernel-based Testing

Kevin H. Huang, Xing Liu, Andrew Duncan, Axel Gandy

Causal Matrix Completion

Anish Agarwal, Munther Dahleh, Devavrat Shah, Dennis Shen

Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models

Yuchen Wu, Kangjie Zhou

Approximately Stationary Bandits with Knapsacks

Giannis Fikioris, Eva Tardos

Near Optimal Heteroscedastic Regression with Symbiotic Learning

Aniket Das, Dheeraj M. Nagaraj, Praneeth Netrapalli, Dheeraj Baby

Linearization Algorithms for Fully Composite Optimization

Maria-Luiza Vladarean, Nikita Doikov, Martin Jaggi, Nicolas Flammarion

A new ranking scheme for modern data and its application to two-sample hypothesis testing

Doudou Zhou, Hao Chen

From Pseudorandomness to Multi-Group Fairness and Back

Cynthia Dwork, Daniel Lee, Huijia Lin, Pranay Tankala

Efficient Algorithms for Sparse Moment Problems without Separation

Zhiyuan Fan, Jian Li

The k-Cap Process on Geometric Random Graphs

Mirabel E. Reid, Santosh S. Vempala

Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective

Max Simchowitz, Abhishek Gupta, Kaiqing Zhang

Online Nonconvex Optimization with Limited Instantaneous Oracle Feedback

Ziwei Guan, Yi Zhou, Yingbin Liang

Improved Dynamic Regret for Online Frank-Wolfe

Yuanyu Wan, Lijun Zhang, Mingli Song

Intrinsic dimensionality and generalization properties of the R-norm inductive bias

Navid Ardeshir, Daniel J. Hsu, Clayton H. Sanford

Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization

David Gamarnik, Eren C. Kizildağ, Will Perkins, Changji Xu

Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints

Ankit Pensia, Amir Reza Asadi, Varun Jog, Po-ling Loh

Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization

Spencer Frei, Gal Vardi, Peter Bartlett, Nathan Srebro

Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs

Michał Dereziński

Testing of Index-Invariant Properties in the Huge Object Model

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems

Stefan Tiegel

A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points

Daniel Kane, Ilias Diakonikolas

Curvature and complexity: Better lower bounds for geodesically convex optimization

Christopher Criscitiello, Nicolas Boumal

On the Lower Bound of Minimizing Polyak-Łojasiewicz functions

Pengyun Yue, Cong Fang, Zhouchen Lin

Self-Directed Linear Classification

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

Toward L_∞Recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields

Kefan Dong, Tengyu Ma

Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond

David Martínez-Rubio, Elias Wirth, Sebastian Pokutta

Information-Directed Selection for Top-Two Algorithms

Wei You, Chao Qin, Zihao Wang, Shuoguang Yang

Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures

Wai Ming Tai, Bryon Aragam

Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation

Yuanhao Wang, Qinghua Liu, Yu Bai, Chi Jin

On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring

Dean Foster, Dylan J. Foster, Noah Golowich, Alexander Rakhlin

Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds

Shinji Ito, Kei Takemura

Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation

Qiwen Cui, Kaiqing Zhang, Simon Du

Optimal Scoring Rules for Multi-dimensional Effort

Jason D. Hartline, Liren Shan, Yingkai Li, Yifan Wu