COLT

Publications

2024

Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U. Stich, Ziheng Cheng, Nirmit Joshi, Nathan Srebro
The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication. COLT (2024)
Vinod Raman, Unique Subedi, Ananth Raman, Ambuj Tewari
Apple Tasting: Combinatorial Dimensions and Minimax Rates. COLT (2024)
Binghui Peng, Aviad Rubinstein
The complexity of approximate (coarse) correlated equilibrium for incomplete information games. COLT (2024)
Hengquan Guo, Xin Liu
Stochastic Constrained Contextual Bandits via Lyapunov Optimization Based Estimation to Decision Framework. COLT (2024)
Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff
Dual VC Dimension Obstructs Sample Compression by Embeddings. COLT (2024)
Sepehr Assadi, Chen Wang
The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits. COLT (2024)
Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran
The Real Price of Bandit Information in Multiclass Classification. COLT (2024)
Wilfred Salmon, Sergii Strelchuk, Tom Gur
Provable Advantage in Quantum PAC Learning. COLT (2024)
Adam Block, Alexander Rakhlin, Abhishek Shetty
On the Performance of Empirical Risk Minimization with Smoothed Data. COLT (2024)
Lee Cohen, Yishay Mansour, Shay Moran, Han Shao
Learnability Gaps of Strategic Classification. COLT (2024)
Guillaume Wang, Lénaïc Chizat
Open problem: Convergence of single-timescale mean-field Langevin descent-ascent for two-player zero-sum games. COLT (2024)
Aditya Gangrade, Tianrui Chen, Venkatesh Saligrama
Safe Linear Bandits over Unknown Polytopes. COLT (2024)
Zhichao Wang, Denny Wu, Zhou Fan
Nonlinear spiked covariance matrices and signal propagation in deep neural networks. COLT (2024)
Clément L. Canonne
Open Problem: Tight Characterization of Instance-Optimal Identity Testing. COLT (2024)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
On Convex Optimization with Semi-Sensitive Features. COLT (2024)
Siyu Chen, Heejune Sheen, Tianhao Wang, Zhuoran Yang
Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality (extended abstract). COLT (2024)
Daniel Grier, Hakop Pashayan, Luke Schaeffer
Principal eigenstate classical shadows. COLT (2024)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. COLT (2024)
Philip Amortila, Tongyi Cao, Akshay Krishnamurthy
Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning. COLT (2024)
Yair Carmon, Oliver Hinder
The Price of Adaptivity in Stochastic Convex Optimization. COLT (2024)
Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng
New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions. COLT (2024)
Josep Lumbreras, Marco Tomamichel
Linear bandits with polylogarithmic minimax regret. COLT (2024)
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
Statistical Query Lower Bounds for Learning Truncated Gaussians. COLT (2024)
Alexander Kozachinskiy, Tomasz Steifer
Simple online learning with consistent oracle. COLT (2024)
Arun Sai Suggala, Y. Jennifer Sun, Praneeth Netrapalli, Elad Hazan
Second Order Methods for Bandit Optimization and Control. COLT (2024)
Maximilien Dreveton, Alperen Gözeten, Matthias Grossglauser, Patrick Thiran
Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models. COLT (2024)
Xuzhi Yang, Tengyao Wang
Multiple-output composite quantile regression through an optimal transport lens. COLT (2024)
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Regularization and Optimal Multiclass Learning. COLT (2024)
Nuri Mert Vural, Murat A. Erdogdu
Pruning is Optimal for Learning Sparse Features in High-Dimensions. COLT (2024)
Achraf Azize, Debabrota Basu
Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits? COLT (2024)
Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
A Unified Characterization of Private Learnability via Graph Theory. COLT (2024)
Elchanan Mossel, Anirudh Sridhar
Finding Super-spreaders in Network Cascades. COLT (2024)
Arun Jambulapati, Aaron Sidford, Kevin Tian
Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization. COLT (2024)
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Nikos Zarifis
Testable Learning of General Halfspaces with Adversarial Label Noise. COLT (2024)
Mahdi Soleymani, Tara Javidi
A Non-Adaptive Algorithm for the Quantitative Group Testing Problem. COLT (2024)
Giovanni Luca Marchetti, Christopher J. Hillar, Danica Kragic, Sophia Sanborn
Harmonics of Learning: Universal Fourier Features Emerge in Invariant Networks. COLT (2024)
Binghui Peng
The sample complexity of multi-distribution learning. COLT (2024)
Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka
Learning Neural Networks with Sparse Activations. COLT (2024)
Yunbum Kook, Santosh S. Vempala
Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling. COLT (2024)
Ilja Kuzborskij, Kwang-Sung Jun, Yulian Wu, Kyoungseok Jang, Francesco Orabona
Better-than-KL PAC-Bayes Bounds. COLT (2024)
Stefan Tiegel
Improved Hardness Results for Learning Intersections of Halfspaces. COLT (2024)
Steve Hanneke
The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement. COLT (2024)
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Open Problem: Can Local Regularization Learn All Multiclass Problems? COLT (2024)
Mingda Qiao, Letian Zheng
On the Distance from Calibration in Sequential Prediction. COLT (2024)
Yiheng Jiang, Sinho Chewi, Aram-Alexandre Pooladian
Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space. COLT (2024)
Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen
A Theory of Interpretable Approximations. COLT (2024)
Daniil Dmitriev, Kristóf Szabó, Amartya Sanyal
On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective. COLT (2024)
Andre Wibisono, Yihong Wu, Kaylee Yingxi Yang
Optimal score estimation via empirical Bayes smoothing. COLT (2024)
Xinyi Chen, Elad Hazan
Open Problem: Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization. COLT (2024)

volume 247, 2024

The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada. COLT 247 (2024)