PPaperPicks
← All conferences
Editions202620252024

COLT 2025

A*

Annual Conference on Learning Theory

Official site ↗
183
accepted papers
476
authors
June 30 - July 4, 2025
dates
France
location

183 / 183 papers

  1. 1
    "All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery (Extended Abstract)
    Julia Gaudio
    ,
    Colin Sandon
    ,
    Jiaming Xu
    ,
    Dana Yang
  2. 2
    A Distributional-Lifting Theorem for PAC Learning
    Guy Blanc
    ,
    Jane Lange
    ,
    Carmen Strassle
    ,
    Li-Yang Tan
  3. 3
    A Fine-grained Characterization of PAC Learnability
    Marco Bressan
    ,
    Nataly Brukhim
    ,
    Nicolò Cesa-Bianchi
    ,
    Emmanuel Esposito
    ,
    Yishay Mansour
    ,
    Shay Moran
    ,
    Maximilian Thiessen
  4. 4
    A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis
    Akash Kumar
    ,
    Rahul Parhi
    ,
    Mikhail Belkin
  5. 5
    A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
    Junfan Li
    ,
    Shizhong Liao
    ,
    Zenglin Xu
    ,
    Liqiang Nie
  6. 6
    A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
    Hang Du
    ,
    Shuyang Gong
    ,
    Jiaming Xu
  7. 7
    A Theory of Learning with Autoregressive Chain of Thought
    Nirmit Joshi
    ,
    Gal Vardi
    ,
    Adam Block
    ,
    Surbhi Goel
    ,
    Zhiyuan Li
    ,
    Theodor Misiakiewicz
    ,
    Nathan Srebro
  8. 8
    Accelerating Proximal Gradient Descent via Silver Stepsizes
    Jinho Bok
    ,
    Jason M. Altschuler
  9. 9
    Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
    Anxin Guo
    ,
    Aravindan Vijayaraghavan
  10. 10
    Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)
    Xue Chen
    ,
    Wenxuan Shu
    ,
    Zhaienhe Zhou
  11. 11
    Alternating Regret for Online Convex Optimization
    Soumita Hait
    ,
    Ping Li
    ,
    Haipeng Luo
    ,
    Mengxiao Zhang
  12. 12
    An uncertainty principle for Linear Recurrent Neural Networks
    Alexandre François
    ,
    Antonio Orvieto
    ,
    Francis R. Bach
  13. 13
    Anytime Acceleration of Gradient Descent
    Zihan Zhang
    ,
    Jason D. Lee
    ,
    Simon S. Du
    ,
    Yuxin Chen
  14. 14
    Approximating the total variation distance between spin systems
    Weiming Feng
    ,
    Hongyang Liu
    ,
    Minji Yang
  15. 15
    Are all models wrong? Fundamental limits in distribution-free empirical model falsification
    Manuel M. Müller
    ,
    Yuetian Luo
    ,
    Rina Foygel Barber
  16. 16
    Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
    Kaito Fujii
  17. 17
    Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
    Maryam Aliakbarpour
    ,
    Arnav Burudgunte
    ,
    Clément L. Canonne
    ,
    Ronitt Rubinfeld
  18. 18
    Beyond propagation of chaos: A stochastic algorithm for mean field optimization
    Chandan Tankala
    ,
    Dheeraj Nagaraj
    ,
    Anant Raj
  19. 19
    Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
    Omar Montasser
    ,
    Abhishek Shetty
    ,
    Nikita Zhivotovskiy
  20. 20
    Black-Box Reductions for Decentralized Online Convex Optimization in Changing Environments
    Yuanyu Wan
  21. 21
    Blackwell's Approachability with Approximation Algorithms
    Dan Garber
    ,
    Mhna Massalha
  22. 22
    Can a calibration metric be both testable and actionable?
    Raphael Rossellini
    ,
    Jake A. Soloff
    ,
    Rina Foygel Barber
    ,
    Zhimei Ren
    ,
    Rebecca Willett
  23. 23
    Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
    Alexander Ryabchenko
    ,
    Idan Attias
    ,
    Daniel M. Roy
  24. 24
    Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Φ-Mutual Information (Extended Abstract)
    Jiaming Liang
    ,
    Siddharth Mitra
    ,
    Andre Wibisono
  25. 25
    Community detection with the Bethe-Hessian
    Ludovic Stephan
    ,
    Yizhe Zhu
  26. 26
    Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract)
    Vincent Froese
    ,
    Moritz Grillo
    ,
    Martin Skutella
  27. 27
    Compression Barriers in Autoregressive Transformers
    Themistoklis Haris
    ,
    Krzysztof Onak
  28. 28
    Computable learning of natural hypothesis classes
    Syed Akbari
    ,
    Matthew Harrison-Trainor
  29. 29
    Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
    Guy Bresler
    ,
    Alina Harbuzova
  30. 30
    Computational Intractability of Strategizing against Online Learners
    Angelos Assos
    ,
    Yuval Dagan
    ,
    Nived Rajaraman
  31. 31
    Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification (extended abstract)
    Dhruv Rohatgi
    ,
    Adam Block
    ,
    Audrey Huang
    ,
    Akshay Krishnamurthy
    ,
    Dylan J. Foster
  32. 32
    Computing High-dimensional Confidence Sets for Arbitrary Distributions
    Chao Gao
    ,
    Liren Shan
    ,
    Vaidehi Srinivas
    ,
    Aravindan Vijayaraghavan
  33. 33
    Computing Optimal Regularizers for Online Linear Optimization
    Khashayar Gatmiry
    ,
    Jon Schneider
    ,
    Stefanie Jegelka
  34. 34
    Conference on Learning Theory 2025: Preface
    Nika Haghtalab
    ,
    Ankur Moitra
  35. 35
    Corrupted Learning Dynamics in Games
    Taira Tsuchiya
    ,
    Shinji Ito
    ,
    Haipeng Luo
  36. 36
    Data Selection for ERMs
    Steve Hanneke
    ,
    Shay Moran
    ,
    Alexander Shlimovich
    ,
    Amir Yehudayoff
  37. 37
    Data-dependent Bounds with T-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits using Stability-Penalty Matching
    Quan M. Nguyen
    ,
    Shinji Ito
    ,
    Junpei Komiyama
    ,
    Nishant A. Mehta
  38. 38
    Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
    Fan Chen
    ,
    Alexander Rakhlin
  39. 39
    Decision Making in Hybrid Environments: A Model Aggregation Approach
    Haolin Liu
    ,
    Chen-Yu Wei
    ,
    Julian Zimmert
  40. 40
    Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
    Itay Safran
    ,
    Daniel Reichman
    ,
    Paul Valiant
  41. 41
    Detecting Arbitrary Planted Subgraphs in Random Graphs
    Dor Elimelech
    ,
    Wasim Huleihel
  42. 42
    Deterministic Apple Tasting
    Zachary Chase
    ,
    Idan Mehalel
  43. 43
    Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
    Pan Peng
    ,
    Hangyu Xu
  44. 44
    DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory
    Jerry Chee
    ,
    Arturs Backurs
    ,
    Rainie Heck
    ,
    Li Zhang
    ,
    Janardhan Kulkarni
    ,
    Thomas Rothvoss
    ,
    Sivakanth Gopi
  45. 45
    Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries
    Arnab Maiti
    ,
    Zhiyuan Fan
    ,
    Kevin Jamieson
    ,
    Lillian J. Ratliff
    ,
    Gabriele Farina
  46. 46
    Efficiently learning and sampling multimodal distributions with data-based initialization
    Frederic Koehler
    ,
    Holden Lee
    ,
    Thuy-Duong Vuong
  47. 47
    Estimating stationary mass, frequency by frequency
    Milind Nakul
    ,
    Vidya Muthukumar
    ,
    Ashwin Pananjady
  48. 48
    Existence of Adversarial Examples for Random Convolutional Networks via Isoperimetric Inequalities on $\mathbb{SO}(d)$
    Amit Daniely
  49. 49
    Experimental Design for Semiparametric Bandits
    Seok-Jin Kim
    ,
    Gi-Soo Kim
    ,
    Min-hwan Oh
  50. 50
    Exploring Facets of Language Generation in the Limit
    Moses Charikar
    ,
    Chirag Pabbaraju