COLT 2026

197 papers

Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion

Xunpeng Huang, Yingyu Lin, Lijing Kuang, Hanze Dong, Difan Zou

Reconstructing Riemannian Metrics From Random Geometric Graphs

Han Huang, Pakawut Jiradilok, Elchanan Mossel

Wasserstein Policy Learning for Distributional Outcomes

Yiyan Huang, Cheuk Hang Leung, Qi Wu, Zhiheng Zhang

Efficient Swap Multicalibration of Elicitable Properties

Lunjia Hu, Haipeng Luo, Spandan Senapati, Vatsal Sharan

Near-optimal Swap Regret Minimization for Convex Losses

Lunjia Hu, Jon Schneider, Yifan Wu

Recovery thresholds for hidden weighted sparse graphs (extended abstract)

Zhe Hou, Jingcheng Liu

Uniform Laws of Large Numbers in Product Spaces

Ron Holzman, Shay Moran, Alexander Shlimovich

A Perfectly Truthful Calibration Measure

Jason Hartline, Lunjia Hu, Yifan Wu

Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget (extended abstract)

Michael O. Harding, Vikas Singh, Kirthevasan Kandasamy

Price of metric universality in vector quantization is at most 0.11 bit

Alina Harbuzova, Or Ordentlich, Yury Polyanskiy

Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise

Rafael Hanashiro, Abhishek Shetty, Patrick Jaillet

An Empirical Bayes Perspective on Heteroskedastic Mean Estimation

Yanjun Han, Abhishek Shetty, Jacob Shkrob

High Probability Convergence Guarantees of Stochastic Gradient Descent Ascent in Structured Nonconvex Min-Max Games

Junsoo Ha

Functional Stochastic Localization

Anming Gu, Bobby Shi, Kevin Tian

A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions

Yuzhou Gu, Xin Li, Yinzhan Xu

Computing Lewis weights to high precision using local relative smoothness

Sander Gribling, Aaron Sidford, Chenyi Zhang

Randomization for Faster Exact Optimization of Discounted Markov Decision Processes

Andrei Graur, Aaron Sidford, Ta-Wei Tu

Compact Geometric Representations of Hierarchies

Prashant Gokhale, Piotr Indyk, Yuhao Liu, Sandeep Silwal, Tony Wang

Testing Noise Assumptions of Learning Algorithms

Surbhi Goel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations

Andreas Göbel, Marcus Pappik, Leon Schiller

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares

Andreas Göbel, Janosch Ruff, Leon Schiller

Sample-Efficient Omniprediction for Proper Losses

Isaac Gibbs, Ryan J. Tibshirani

On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani, Jason D. Lee

Universality of high-dimensional scaling limits of stochastic gradient descent (extended abstract)

Reza Gheissari, Aukosh Jagannath

Fixed-Parameter Tractability of Private Synthetic Data Generation

Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar

Nearly Linear-Time User-Level DP-SCO with Optimal Rates

Badih Ghazi, Ravi Kumar, Daogao Liu, Pasin Manurangsi

Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods

Ferdinand Genans

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs

David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach

Learning Ising Models from Evolutions (Extended Abstract)

Jason Gaitonde, Ankur Moitra, Elchanan Mossel

Toward Simultaneously Optimal Regret in U-Calibration

Rafael Frongillo, Haipeng Luo, Nishant A. Mehta, Jon Schneider

Space-Efficient Language Generation in the Limit

Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, Ola Svensson

Optimal Reconstruction from Linear Queries

Yuval Filmus, Shay Moran, Elizaveta Nesterova

Defensive Generation

Gabriele Farina, Juan Carlos Perdomo

Tight Sample Complexity Bounds for Entropic Best Policy Identification

Amer Essakine, Claire Vernade

The Sample Complexity of Multiclass and Sparse Contextual Bandits

Liad Erez, Fan Chen, Alon Cohen, Tomer Koren, Yishay Mansour

Leveraging Similarities in Multi-Armed Bandits

Khaled Eldowa, Thibaud Rahier, Augustin Cablant, Panayotis Mertikopoulos, Pierre Gaillard

Theoretical Compression Bounds for Wide Multilayer Perceptrons

Houssam El Cheairi, David Gamarnik, Rahul Mazumder

The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network

Abhigyan Dutta, Itay Safran, Paul Valiant

Relatively Smart: A New Approach for Instance-Optimal Learning

Shaddin Dughmi, Alireza F. Pour

Online Realizable Regression and Applications for ReLU Networks

Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

Daniil Dmitriev, Zhihan Huang, Yuting Wei

Rate-optimal community detection near the KS threshold via node-robust algorithms

Jingqiu Ding, Yiding Hua, Kasper Lindberg, David Steurer, Aleksandr Storozhenko

Minimax optimal differentially private synthetic data for smooth queries

Rundong Ding, Yiyun He, Yizhe Zhu

Online Convex Optimization with Sublinear Noisy Probes

Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance

Ilias Diakonikolas, Jingyi Gao, Giannis Iakovidis, Daniel M. Kane, Sihan Liu

Linear Regression under Missing or Corrupted Coordinates

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size

Michał Dereziński, Xiaoyu Dong

The matrix-vector complexity of Ax=b

Michał Dereziński, Ethan N Epperly, Raphael A Meyer

Stochastic Safe Action Model Learning

Zihao Deng, Brendan Juba

Estimating Ising Models in Total Variation Distance

Constantinos Daskalakis, Vardis Kandiros, Rui Yao

Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method

Yatin Dandi, David Gamarnik, Francisco Pernice, Lenka Zdeborová

Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension

Michael Crawshaw, Mingrui Liu

Eigen-Spike Emergence and Quadratic Equivalents for Conjugate Kernels on Nonlinearly Separable Data

Collin Cranston, Zhichao Wang, Todd Kemp, W. Michael Mahoney

Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more

Spencer Compton, Jerry Li

DDPM Score Matching and Distribution Learning (Extended Abstract)

Sinho Chewi, Alkis Kalavasis, Anay Mehrotra, Omar Montasser

Is Memorization Helpful or Harmful? Prior Information Sets the Threshold

Chen Cheng, Rina Foygel Barber

Calibeating Made Simple

Yurong Chen, Zhiyi Huang, Michael I. Jordan, Haipeng Luo

High-Accuracy Log-Concave Sampling with Stochastic Queries

Fan Chen, Sinho Chewi, Constantinos Daskalakis, Alexander Rakhlin

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression

Fan Chen, Jian Qian, Alexander Rakhlin, Nikita Zhivotovskiy

Optimal Inference Schedules for Masked Diffusion Models

Sitan Chen, Kevin Cong, Jerry Li

Information-computation gaps in quantum learning via low-degree likelihood

Sitan Chen, Weiyuan Gong, Jonas Haferkamp, Yihui Quek

Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach

Senrui Chen, Weiyuan Gong, Sisi Zhou

Separating Oblivious and Adaptive Models of Variable Selection (Extended Abstract)

Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu

Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity

Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang

A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

Zachary Chase, Shinji Ito, Idan Mehalel

Language Identification with Succinct Machine-Independent Traces

Moses Charikar, Jon Kleinberg, Chirag Pabbaraju

A Characterization of List Language Identification in the Limit

Moses Charikar, Chirag Pabbaraju, Ambuj Tewari

Learning Periodic Strategies in Blocking Bandits Is as Hard as Bandits with Switching Costs

Nicolò Cesa-bianchi, Junya Honda, Yuko Kuroki, Atsushi Miyauchi, Lukas Zierahn

Phase Transition for Stochastic Block Model with more than $\sqrtn$ Communities

Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen

Universal priors: solving empirical Bayes via Bayesian inference and pretraining

Nick Cannella, Anzo Teh, Yanjun Han, Yury Polyanskiy

Active Learning on Adversarially Corrupted Graphs

Marco Bressan, Nicolò Cesa-bianchi, Tommaso d’Orsi, Emmanuel Esposito, Silvio Lattanzi

Learning Conditional Averages

Marco Bressan, Nataly Brukhim, Nicolò Cesa-bianchi, Emmanuel Esposito, Yishay Mansour

Learning from Equivalence Queries, Revisited

Mark Braverman, Roi Livni, Yishay Mansour, Shay Moran, Kobbi Nissim

Tight list replicability bounds via a novel sphere covering theorem

Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak

Partition Function Estimation under Bounded f-Divergence

Adam Block, Abhishek Shetty

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness

Moise Blanchard, Abhishek Shetty, Alexander Rakhlin

Actively Learning Halfspaces without Synthetic Data

Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So

Adaptive Weighted Averaging

Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit

Omniprediction with Long-Term Constraints

Yahav Bechavod, Jiuyao Lu, Aaron Roth

Algorithmic Thinking Theory

Mohammadhossein Bateni, Vincent Cohen-Addad, Yuzhou Gu, Silvio Lattanzi, Simon Meierhans

Limitations of SGD for Multi-Index Models Beyond Statistical Queries

Daniel Barzilai, Ohad Shamir

Cloning is as Hard as Learning for Stabilizer States

Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan

Variational Tail Bounds for Norms of Random Vectors and Matrices

Sohail Bahmani

A Complexity Measure for Active Learning in Multi-group Mean Estimation

Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub

Margin in Abstract Spaces

Yair Ashlagi, Roi Livni, Shay Moran, Tom Waknine

Strongly Polynomial Time Complexity of Policy Iteration for $L_∞$ Robust MDPs

Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri

Learning depth-3 circuits via quantum agnostic boosting

Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael De Oliveira

Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization

Aleksandar Armacki, Dragana Bajovic, Dusan Jakovetic, Soummya Kar, Ali H Sayed

Statistical Learning from Attribution Sets

Lorne Applebaum, Róbert Busa-Fekete, August Chen, Claudio Gentile, Tomer Koren

Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures

Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer

Swap Regret Minimization Through Response-Based Approachability

Ioannis Anagnostides, Gabriele Farina, Maxwell Fishelson, Haipeng Luo, Jon Schneider

Query Efficient Structured Matrix Learning

Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

Maryam Aliakbarpour, Alireza Azizi, Ria Stevens

Quiet Planting for k-SAT, Multiple Solutions of Arbitrary Geometry

Ali Ahmadi, Kiarash Banihashem, Iman Gholami, Mohammad Taghi Hajiaghayi, Jan Olkowski

On efficient robust regression with subquadratic samples

Deeksha Adil, Jarosław Błasiok, Hongjie Chen, Deepak Narayanan Sridharan

How fast can you find a good hypothesis?

Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Sandeep Silwal