PPaperPicks
← All conferences
Editions202620252024

COLT 2024

A*

Annual Conference on Learning Theory

Official site ↗
170
accepted papers
458
authors
June 30 - July 3, 2024
dates
Canada
location

170 / 170 papers

  1. 1
    (ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits
    Gianmarco Genalti
    ,
    Lupo Marsigli
    ,
    Nicola Gatti
    ,
    Alberto Maria Metelli
  2. 2
    A faster and simpler algorithm for learning shallow networks
    Sitan Chen
    ,
    Shyam Narayanan
  3. 3
    A Non-Adaptive Algorithm for the Quantitative Group Testing Problem
    Mahdi Soleymani
    ,
    Tara Javidi
  4. 4
    A non-backtracking method for long matrix and tensor completion
    Ludovic Stephan
    ,
    Yizhe Zhu
  5. 5
    A Theory of Interpretable Approximations
    Marco Bressan
    ,
    Nicolò Cesa-Bianchi
    ,
    Emmanuel Esposito
    ,
    Yishay Mansour
    ,
    Shay Moran
    ,
    Maximilian Thiessen
  6. 6
    A Unified Characterization of Private Learnability via Graph Theory
    Noga Alon
    ,
    Shay Moran
    ,
    Hilla Schefler
    ,
    Amir Yehudayoff
  7. 7
    Accelerated Parameter-Free Stochastic Optimization
    Itai Kreisler
    ,
    Maor Ivgi
    ,
    Oliver Hinder
    ,
    Yair Carmon
  8. 8
    Active Learning with Simple Questions
    Vasilis Kontonis
    ,
    Mingchen Ma
    ,
    Christos Tzamos
  9. 9
    Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds
    Shinji Ito
    ,
    Taira Tsuchiya
    ,
    Junya Honda
  10. 10
    Adversarial Online Learning with Temporal Feedback Graphs
    Khashayar Gatmiry
    ,
    Jon Schneider
  11. 11
    Adversarially-Robust Inference on Trees via Belief Propagation
    Samuel B. Hopkins
    ,
    Anqi Li
  12. 12
    Agnostic Active Learning of Single Index Models with Linear Sample Complexity
    Aarshvi Gajjar
    ,
    Wai Ming Tai
    ,
    Xingyu Xu
    ,
    Chinmay Hegde
    ,
    Christopher Musco
    ,
    Yi Li
  13. 13
    Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space
    Yiheng Jiang
    ,
    Sinho Chewi
    ,
    Aram-Alexandre Pooladian
  14. 14
    An information-theoretic lower bound in time-uniform estimation
    John C. Duchi
    ,
    Saminul Haque
  15. 15
    Apple Tasting: Combinatorial Dimensions and Minimax Rates
    Vinod Raman
    ,
    Unique Subedi
    ,
    Ananth Raman
    ,
    Ambuj Tewari
  16. 16
    Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
    Brendan Lucier
    ,
    Sarath Pattathil
    ,
    Aleksandrs Slivkins
    ,
    Mengxiao Zhang
  17. 17
    Better-than-KL PAC-Bayes Bounds
    Ilja Kuzborskij
    ,
    Kwang-Sung Jun
    ,
    Yulian Wu
    ,
    Kyoungseok Jang
    ,
    Francesco Orabona
  18. 18
    Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation
    Shivam Gupta
    ,
    Samuel B. Hopkins
    ,
    Eric C. Price
  19. 19
    Black-Box k-to-1-PCA Reductions: Theory and Applications
    Arun Jambulapati
    ,
    Syamantak Kumar
    ,
    Jerry Li
    ,
    Shourya Pandey
    ,
    Ankit Pensia
    ,
    Kevin Tian
  20. 20
    Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization
    Jiancong Xiao
    ,
    Ruoyu Sun
    ,
    Qi Long
    ,
    Weijie Su
  21. 21
    Choosing the p in Lp Loss: Adaptive Rates for Symmetric Mean Estimation
    Yu-Chun Kao
    ,
    Min Xu
    ,
    Cun-Hui Zhang
  22. 22
    Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
    Arun Jambulapati
    ,
    Aaron Sidford
    ,
    Kevin Tian
  23. 23
    Community detection in the hypergraph stochastic block model and reconstruction on hypertrees
    Yuzhou Gu
    ,
    Aaradhya Pandey
  24. 24
    Computation-information gap in high-dimensional clustering
    Bertrand Even
    ,
    Christophe Giraud
    ,
    Nicolas Verzelen
  25. 25
    Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
    Rares-Darius Buhai
    ,
    Jingqiu Ding
    ,
    Stefan Tiegel
  26. 26
    Computational-Statistical Gaps in Gaussian Single-Index Models (Extended Abstract)
    Alex Damian
    ,
    Loucas Pillaud-Vivien
    ,
    Jason D. Lee
    ,
    Joan Bruna
  27. 27
    Contraction of Markovian Operators in Orlicz Spaces and Error Bounds for Markov Chain Monte Carlo (Extended Abstract)
    Amedeo Roberto Esposito
    ,
    Marco Mondelli
  28. 28
    Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion
    Jianhao Ma
    ,
    Salar Fattahi
  29. 29
    Convergence of Kinetic Langevin Monte Carlo on Lie groups
    Lingkai Kong
    ,
    Molei Tao
  30. 30
    Correlated Binomial Process
    Moïse Blanchard
    ,
    Doron Cohen
    ,
    Aryeh Kontorovich
  31. 31
    Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract
    Xifan Yu
    ,
    Ilias Zadik
    ,
    Peiyuan Zhang
  32. 32
    Depth Separation in Norm-Bounded Infinite-Width Neural Networks
    Suzanna Parkinson
    ,
    Greg Ongie
    ,
    Rebecca Willett
    ,
    Ohad Shamir
    ,
    Nathan Srebro
  33. 33
    Detection of L∞ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion
    Kiril Bangachev
    ,
    Guy Bresler
  34. 34
    Dimension-free Structured Covariance Estimation
    Nikita Puchkin
    ,
    Maxim V. Rakhuba
  35. 35
    Dual VC Dimension Obstructs Sample Compression by Embeddings
    Zachary Chase
    ,
    Bogdan Chornomaz
    ,
    Steve Hanneke
    ,
    Shay Moran
    ,
    Amir Yehudayoff
  36. 36
    Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation Extended Abstract
    Ziao Wang
    ,
    Weina Wang
    ,
    Lele Wang
  37. 37
    Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
    Marco Bressan
    ,
    Emmanuel Esposito
    ,
    Maximilian Thiessen
  38. 38
    Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials
    Ilias Diakonikolas
    ,
    Daniel M. Kane
  39. 39
    Errors are Robustly Tamed in Cumulative Knowledge Processes
    Anna M. Brandenberger
    ,
    Cassandra Marcussen
    ,
    Elchanan Mossel
    ,
    Madhu Sudan
  40. 40
    Exact Mean Square Linear Stability Analysis for SGD
    Rotem Mulayoff
    ,
    Tomer Michaeli
  41. 41
    Fast parallel sampling under isoperimetry
    Nima Anari
    ,
    Sinho Chewi
    ,
    Thuy-Duong Vuong
  42. 42
    Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm
    Vishwak Srinivasan
    ,
    Andre Wibisono
    ,
    Ashia C. Wilson
  43. 43
    Fast two-time-scale stochastic gradient method with applications in reinforcement learning
    Sihan Zeng
    ,
    Thinh T. Doan
  44. 44
    Fast, blind, and accurate: Tuning-free sparse regression with global linear convergence
    Claudio Mayrink Verdun
    ,
    Oleh Melnyk
    ,
    Felix Krahmer
    ,
    Peter Jung
  45. 45
    Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo
    Xunpeng Huang
    ,
    Difan Zou
    ,
    Hanze Dong
    ,
    Yi-An Ma
    ,
    Tong Zhang
  46. 46
    Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract)
    Yujia Jin
    ,
    Ishani Karmarkar
    ,
    Christopher Musco
    ,
    Aaron Sidford
    ,
    Apoorv Vikram Singh
  47. 47
    Finding Super-spreaders in Network Cascades
    Elchanan Mossel
    ,
    Anirudh Sridhar
  48. 48
    Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions
    Yilong Qin
    ,
    Andrej Risteski
  49. 49
    Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds
    Jongyeong Lee
    ,
    Junya Honda
    ,
    Shinji Ito
    ,
    Min-hwan Oh
  50. 50
    Fundamental Limits of Non-Linear Low-Rank Matrix Estimation
    Pierre Mergny
    ,
    Justin Ko
    ,
    Florent Krzakala
    ,
    Lenka Zdeborová