COLT 2025

182 papers

On the query complexity of sampling from non-log-concave distributions (extended abstract)

Yuchen He, Chihao Zhang

Compression Barriers in Autoregressive Transformers

Themistoklis Haris, Krzysztof Onak

Universal Rates for Multiclass Learning with Bandit Feedback

Steve Hanneke, Amirreza Shaeiri, Qian Zhang

Universal Rates of ERM for Agnostic Learning

Steve Hanneke, Mingyue Xu

Data Selection for ERMs

Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff

Alternating Regret for Online Convex Optimization

Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals

Anxin Guo, Aravindan Vijayaraghavan

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold

Yuzhou Gu, Xin Li, Yinzhan Xu

Mean-field analysis of polynomial-width two-layer neural network beyond finite time horizon

Margalit Glasgow, Denny Wu, Joan Bruna

PREM: Privately Answering Statistical Queries with Relative Error

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

“All-Something-Nothing” Phase Transitions in Planted k-Factor Recovery (Extended Abstract)

Julia Gaudio, Colin Sandon, Jiaming Xu, Dana Yang

Learning Mixtures of Gaussians Using Diffusion Models

Khashayar Gatmiry, Jonathan Kelner, Holden Lee

Computing Optimal Regularizers for Online Linear Optimization

Khashayar Gatmiry, Jon Schneider, Stefanie Jegelka

Model predictive control is almost optimal for restless bandits

Nicolas "Gast, Dheeraj" Narasimha

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method

Sachin Garg, Michał Dereziński

Blackwell’s Approachability with Approximation Algorithms

Dan Garber, Massalha Mhna

Computing High-dimensional Confidence Sets for Arbitrary Distributions

Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan

Gradient Methods with Online Scaling

Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, Madeleine Udell

Kaito Fujii

Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract)

Vincent Froese, Moritz Grillo, Martin Skutella

An uncertainty principle for Linear Recurrent Neural Networks

Alexandre François, Antonio Orvieto, Francis Bach

Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration

Dylan J Foster, Zakaria Mhammedi, Dhruv Rohatgi

Approximating the total variation distance between spin systems

Weiming Feng, Hongyang Liu, Minji Yang

Trade-offs in Data Memorization via Strong Data Processing Inequalities

Vitaly Feldman, Guy Kornowski, Xin Lyu

Learning Augmented Graph k-Clustering

Chenglin Fan, Kijun Shin

Universality of High-Dimensional Logistic Regression and a Novel CGMT under Dependence with Applications to Data Augmentation

Matthew Esmaili Mallory, Kevin Han Huang, Morgane Austern

Detecting Arbitrary Planted Subgraphs in Random Graphs

Dor Elimelech, Wasim Huleihel

Logarithmic Width Suffices for Robust Memorization

Amitsour Egosi, Gilad Yehudai, Ohad Shamir

From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs

Cynthia Dwork, Chris Hays, Nicole Immorlica, Juan C. Perdomo, Pranay Tankala

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models

Hang Du, Shuyang Gong, Jiaming Xu

Faster Algorithms for Agnostically Learning Disjunctions and their Implications

Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren

Learning Intersections of Two Margin Halfspaces under Factorizable Distributions

Ilias Diakonikolas, Ma Mingchen, Ren Lisheng, Tzamos Christos

Low-rank fine-tuning lies between lazy training and feature learning

Arif Kerem Dayi, Sitan Chen

Rate-Preserving Reductions for Blackwell Approachability

Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan

Existence of Adversarial Examples for Random Convolutional Networks via Isoperimetric Inequalities on SO(d)

Amit Daniely

Non-Monetary Mechanism Design without Distributional Information: Using Scarce Audits Wisely (Extended Abstract)

Yan Dai, Moise Blanchard, Patrick Jaillet

Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions

Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel

Non-Euclidean High-Order Smooth Convex Optimization Extended Abstract

Juan Pablo Contreras, Cristóbal Guzmán, David Martı́nez-Rubio

Lower Bounds for Greedy Teaching Set Constructions

Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy

Spherical Dimension

Bogdan Chornomaz, Shay Moran, Tom Waknine

Stochastic block models with many communities and the Kesten–Stigum bound - extended abstract

Byron Chin, Elchanan Mossel, Youngtak Sohn, Alexander S. Wein

Quantum State and Unitary Learning Implies Circuit Lower Bounds

Nai-Hui Chia, Daniel Liang, Fang Song

The Space Complexity of Learning-Unlearning Algorithms (extended abstract)

Yeshwanth Cherapanamjeri, Sumegba Garg, Nived Rajaraman, Ayush Sekhari, Abhishek Shetty

Heavy-tailed Estimation is Easier than Adversarial Contamination

Yeshwanth Cherapanamjeri, Daniel Lee

Optimization, Isoperimetric Inequalities, and Sampling via Lyapunov Potentials

August Y Chen, Karthik Sridharan

Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)

Xue Chen, Wenxuan Shu, Zhaienhe Zhou

Learning general Gaussian mixtures with efficient score matching

Sitan Chen, Vasilis Kontonis, Kulin Shah

Improved sample upper and lower bounds for trace estimation of quantum state powers

Kean Chen, Qisheng Wang

Predicting quantum channels over general product distributions

Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange

Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy

Fan Chen, Alexander Rakhlin

Solving Convex-Concave Problems with O(ε^-4/7) Second-Order Oracle Complexity

Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang

DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory

Jerry Chee, Arturs Backurs, Rainie Heck, Li Zhang, Janardhan Kulkarni

Deterministic Apple Tasting

Zachary Chase, Idan Mehalel

Exploring Facets of Language Generation in the Limit

Moses Charikar, Chirag Pabbaraju

Towards Fair Representation: Clustering and Consensus

Diptarka Chakraborty, Kushagra Chatterjee, Debarati Das, Tien Long Nguyen, Romina Nobahari

Market Making without Regret

Nicolò Cesa-bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, Vinayak Pathak

Information-theoretic reduction of deep neural networks to linear models in the overparametrized proportional regime

Francesco Camilli, Daria Tieplova, Eleonora Bergamin, jean barbier

What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness (Extended Abstract)

Yang Cai, Alkis Kalavasis, Katerina Mamali, Anay Mehrotra, Manolis Zampetakis

On the Convergence of Min-Max Langevin Dynamics and Algorithm

Yang Cai, Siddharth Mitra, Xiuyuan Wang, Andre Wibisono

A Fine-grained Characterization of PAC Learnability

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

Of Dice and Games: A Theory of Generalized Boosting

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

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation

Guy Bresler, Alina Harbuzova

Partial and Exact Recovery of a Random Hypergraph from its Graph Projection

Guy Bresler, Chenghao Guo, Yury Polyanskiy, Andrew Yao

Logarithmic regret of exploration in average reward Markov decision processes

Victor Boone, Bruno Gaujal

Accelerating Proximal Gradient Descent via Silver Stepsizes

Jinho Bok, Jason M. Altschuler

Proofs as Explanations: Short Certificates for Reliable Predictions

Avrim Blum, Steve Hanneke, Chirag Pabbaraju, Donya Saless

Stability and List-Replicability for Agnostic Learners

Ari Blondal, Gao Shan, Hamed Hatami, Pooya Hatami

A Distributional-Lifting Theorem for PAC Learning

Guy Blanc, Jane Lange, Carmen Strassle, Li-Yang Tan

Learning Partitions with Optimal Query and Round Complexities

Hadley Black, Arya Mazumdar, Barna Saha

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu

How to safely discard features based on aggregate SHAP values

Robi Bhattacharjee, Karolin Frohnapfel, Ulrike Von Luxburg

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

Ainesh Bakshi, Vincent Cohen-Addad, Rajesh Jayaram, Samuel B. Hopkins, Silvio Lattanzi

Thompson Sampling for Bandit Convex Optimisation

Alireza Bakhtiari, Tor Lattimore, Csaba Szepesvári

Faster Acceleration for Steepest Descent

Cedar Site Bai, Brian Bullins

Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions

Samuel Baguley, Andreas Göbel, Marcus Pappik, Leon Schiller

Computational Intractability of Strategizing against Online Learners

Angelos Assos, Yuval Dagan, Nived Rajaraman

Simplifying Adversarially Robust PAC Learning With Tolerance

Hassan Ashtiani, Vinayak Pathak, Ruth Urner

Regret Bounds for Robust Online Decision Making

Alexander Appel, Vanessa Kosoy

Better Private Distribution Testing by Leveraging Unverified Auxiliary Data

Maryam Aliakbarpour, Arnav Burudgunte, Clement Canonne, Ronitt Rubinfeld

Computable learning of natural hypothesis classes

Syed Akbari, Matthew Harrison-Trainor

Optimistic Q-learning for average reward and episodic reinforcement learning extended abstract

Priyank Agrawal, Shipra Agrawal

Conference on Learning Theory 2025: Preface

Nika Haghtalab, Ankur Moitra