[edit]
[edit]
Editors: Nika Haghtalab, Ankur Moitra
Conference on Learning Theory 2025: Preface
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:i-i
[abs][Download PDF]
Optimistic Q-learning for average reward and episodic reinforcement learning extended abstract
Priyank Agrawal, Shipra Agrawal; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1-1
[abs][Download PDF]
Computable learning of natural hypothesis classes
Syed Akbari, Matthew Harrison-Trainor; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2-21
[abs][Download PDF]
Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
Maryam Aliakbarpour, Arnav Burudgunte, Clément Canonne, Ronitt Rubinfeld; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:22-63
[abs][Download PDF]
Regret Bounds for Robust Online Decision Making
Alexander Appel, Vanessa Kosoy; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:64-146
[abs][Download PDF]
Simplifying Adversarially Robust PAC Learning With Tolerance
Hassan Ashtiani, Vinayak Pathak, Ruth Urner; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:147-168
[abs][Download PDF]
Computational Intractability of Strategizing against Online Learners
Angelos Assos, Yuval Dagan, Nived Rajaraman; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:169-199
[abs][Download PDF]
Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions
Samuel Baguley, Andreas Göbel, Marcus Pappik, Leon Schiller; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:200-201
[abs][Download PDF]
Faster Acceleration for Steepest Descent
Cedar Site Bai, Brian Bullins; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:202-230
[abs][Download PDF]
Thompson Sampling for Bandit Convex Optimisation
Alireza Bakhtiari, Tor Lattimore, Csaba Szepesvári; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:231-263
[abs][Download PDF]
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Ainesh Bakshi, Vincent Cohen-Addad, Rajesh Jayaram, Samuel B. Hopkins, Silvio Lattanzi; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:264-279
[abs][Download PDF]
How to safely discard features based on aggregate SHAP values
Robi Bhattacharjee, Karolin Frohnapfel, Ulrike von Luxburg; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:280-314
[abs][Download PDF]
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:315-343
[abs][Download PDF]
Learning Partitions with Optimal Query and Round Complexities
Hadley Black, Arya Mazumdar, Barna Saha; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:344-374
[abs][Download PDF]
A Distributional-Lifting Theorem for PAC Learning
Guy Blanc, Jane Lange, Carmen Strassle, Li-Yang Tan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:375-379
[abs][Download PDF]
Stability and List-Replicability for Agnostic Learners
Ari Blondal, Gao Shan, Hamed Hatami, Pooya Hatami; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:380-400
[abs][Download PDF]
Proofs as Explanations: Short Certificates for Reliable Predictions
Avrim Blum, Steve Hanneke, Chirag Pabbaraju, Donya Saless; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:401-420
[abs][Download PDF]
Accelerating Proximal Gradient Descent via Silver Stepsizes
Jinho Bok, Jason M. Altschuler; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:421-453
[abs][Download PDF]
Logarithmic regret of exploration in average reward Markov decision processes
Victor Boone, Bruno Gaujal; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:454-533
[abs][Download PDF]
Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
Guy Bresler, Chenghao Guo, Yury Polyanskiy, Andrew Yao; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:534-593
[abs][Download PDF]
Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Guy Bresler, Alina Harbuzova; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:594-595
[abs][Download PDF]
Of Dice and Games: A Theory of Generalized Boosting
Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:596-640
[abs][Download PDF]
A Fine-grained Characterization of PAC Learnability
Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:641-676
[abs][Download PDF]
On the Convergence of Min-Max Langevin Dynamics and Algorithm
Yang Cai, Siddharth Mitra, Xiuyuan Wang, Andre Wibisono; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:677-754
[abs][Download PDF]
What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness (Extended Abstract)
Yang Cai, Alkis Kalavasis, Katerina Mamali, Anay Mehrotra, Manolis Zampetakis; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:755-756
[abs][Download PDF]
Information-theoretic reduction of deep neural networks to linear models in the overparametrized proportional regime
Francesco Camilli, Daria Tieplova, Eleonora Bergamin, Jean Barbier; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:757-798
[abs][Download PDF]
Market Making without Regret
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, Vinayak Pathak; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:799-837
[abs][Download PDF]
Towards Fair Representation: Clustering and Consensus
Diptarka Chakraborty, Kushagra Chatterjee, Debarati Das, Tien Long Nguyen, Romina Nobahari; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:838-853
[abs][Download PDF]
Exploring Facets of Language Generation in the Limit
Moses Charikar, Chirag Pabbaraju; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:854-887
[abs][Download PDF]
Deterministic Apple Tasting
Zachary Chase, Idan Mehalel; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:888-923
[abs][Download PDF]
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; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:924-951
[abs][Download PDF]
Solving Convex-Concave Problems with $\mathcal{O}(\epsilon^{-4/7})$ Second-Order Oracle Complexity
Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:952-982
[abs][Download PDF]
Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
Fan Chen, Alexander Rakhlin; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:983-985
[abs][Download PDF]
Predicting quantum channels over general product distributions
Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange, Jerry Li; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:986-1007
[abs][Download PDF]
Improved sample upper and lower bounds for trace estimation of quantum state powers
Kean Chen, Qisheng Wang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1008-1028
[abs][Download PDF]
Learning general Gaussian mixtures with efficient score matching
Sitan Chen, Vasilis Kontonis, Kulin Shah; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1029-1090
[abs][Download PDF]
Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)
Xue Chen, Wenxuan Shu, Zhaienhe Zhou; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1091-1093
[abs][Download PDF]
Optimization, Isoperimetric Inequalities, and Sampling via Lyapunov Potentials
August Y Chen, Karthik Sridharan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1094-1153
[abs][Download PDF]
Heavy-tailed Estimation is Easier than Adversarial Contamination
Yeshwanth Cherapanamjeri, Daniel Lee; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1154-1184
[abs][Download PDF]
The Space Complexity of Learning-Unlearning Algorithms (extended abstract)
Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman, Ayush Sekhari, Abhishek Shetty; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1185-1193
[abs][Download PDF]
Quantum State and Unitary Learning Implies Circuit Lower Bounds
Nai-Hui Chia, Daniel Liang, Fang Song; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1194-1252
[abs][Download PDF]
Stochastic block models with many communities and the Kesten–Stigum bound - extended abstract
Byron Chin, Elchanan Mossel, Youngtak Sohn, Alexander S. Wein; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1253-1258
[abs][Download PDF]
Spherical Dimension
Bogdan Chornomaz, Shay Moran, Tom Waknine; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1259-1313
[abs][Download PDF]
Lower Bounds for Greedy Teaching Set Constructions
Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1314-1329
[abs][Download PDF]
Non-Euclidean High-Order Smooth Convex Optimization Extended Abstract
Juan Pablo Contreras, Cristóbal Guzmán, David Martı́nez-Rubio; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1330-1330
[abs][Download PDF]
Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions
Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1331-1365
[abs][Download PDF]
Non-Monetary Mechanism Design without Distributional Information: Using Scarce Audits Wisely (Extended Abstract)
Yan Dai, Moïse Blanchard, Patrick Jaillet; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1366-1367
[abs][Download PDF]
Existence of Adversarial Examples for Random Convolutional Networks via Isoperimetric Inequalities on $\mathbb{SO}(d)$
Amit Daniely; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1368-1379
[abs][Download PDF]
Rate-Preserving Reductions for Blackwell Approachability
Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1380-1414
[abs][Download PDF]
Low-rank fine-tuning lies between lazy training and feature learning
Arif Kerem Dayi, Sitan Chen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1415-1471
[abs][Download PDF]
Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
Ilias Diakonikolas, Ma Mingchen, Ren Lisheng, Tzamos Christos; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1472-1530
[abs][Download PDF]
Faster Algorithms for Agnostically Learning Disjunctions and their Implications
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1531-1558
[abs][Download PDF]
A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
Hang Du, Shuyang Gong, Jiaming Xu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1559-1563
[abs][Download PDF]
From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs
Cynthia Dwork, Chris Hays, Nicole Immorlica, Juan C. Perdomo, Pranay Tankala; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1564-1637
[abs][Download PDF]
Logarithmic Width Suffices for Robust Memorization
Amitsour Egosi, Gilad Yehudai, Ohad Shamir; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1638-1690
[abs][Download PDF]
Detecting Arbitrary Planted Subgraphs in Random Graphs
Dor Elimelech, Wasim Huleihel; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1691-1798
[abs][Download PDF]
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; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1799-1918
[abs][Download PDF]
Learning Augmented Graph $k$-Clustering
Chenglin Fan, Kijun Shin; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1919-1934
[abs][Download PDF]
Trade-offs in Data Memorization via Strong Data Processing Inequalities
Vitaly Feldman, Guy Kornowski, Xin Lyu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1935-1973
[abs][Download PDF]
Approximating the total variation distance between spin systems
Weiming Feng, Hongyang Liu, Minji Yang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1974-2025
[abs][Download PDF]
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; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2026-2142
[abs][Download PDF]
An uncertainty principle for Linear Recurrent Neural Networks
Alexandre François, Antonio Orvieto, Francis Bach; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2143-2187
[abs][Download PDF]
Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract)
Vincent Froese, Moritz Grillo, Martin Skutella; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2188-2189
[abs][Download PDF]
Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
Kaito Fujii; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2190-2191
[abs][Download PDF]
Gradient Methods with Online Scaling
Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, Madeleine Udell; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2192-2226
[abs][Download PDF]
Computing High-dimensional Confidence Sets for Arbitrary Distributions
Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2227-2269
[abs][Download PDF]
Blackwell’s Approachability with Approximation Algorithms
Dan Garber, Massalha Mhna; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2270-2290
[abs][Download PDF]
Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
Sachin Garg, Michał Dereziński; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2291-2325
[abs][Download PDF]
Model predictive control is almost optimal for restless bandits
Nicolas "Gast, Dheeraj" Narasimha; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2326-2361
Computing Optimal Regularizers for Online Linear Optimization
Khashayar Gatmiry, Jon Schneider, Stefanie Jegelka; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2362-2402
[abs][Download PDF]
Learning Mixtures of Gaussians Using Diffusion Models
Khashayar Gatmiry, Jonathan Kelner, Holden Lee; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2403-2456
[abs][Download PDF]
“All-Something-Nothing” Phase Transitions in Planted $k$-Factor Recovery (Extended Abstract)
Julia Gaudio, Colin Sandon, Jiaming Xu, Dana Yang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2457-2459
[abs][Download PDF]
PREM: Privately Answering Statistical Queries with Relative Error
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Sushant Sachdeva; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2460-2460
[abs][Download PDF]
Mean-field analysis of polynomial-width two-layer neural network beyond finite time horizon
Margalit Glasgow, Denny Wu, Joan Bruna; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2461-2539
[abs][Download PDF]
Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
Yuzhou Gu, Xin Li, Yinzhan Xu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2540-2591
[abs][Download PDF]
Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
Anxin Guo, Aravindan Vijayaraghavan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2592-2631
[abs][Download PDF]
Alternating Regret for Online Convex Optimization
Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2632-2633
[abs][Download PDF]
Data Selection for ERMs
Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2634-2665
[abs][Download PDF]
Universal Rates of ERM for Agnostic Learning
Steve Hanneke, Mingyue Xu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2666-2703
[abs][Download PDF]
Universal Rates for Multiclass Learning with Bandit Feedback
Steve Hanneke, Amirreza Shaeiri, Qian Zhang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2704-2756
[abs][Download PDF]
Compression Barriers in Autoregressive Transformers
Themistoklis Haris, Krzysztof Onak; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2757-2785
[abs][Download PDF]
On the query complexity of sampling from non-log-concave distributions (extended abstract)
Yuchen He, Chihao Zhang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2786-2787
[abs][Download PDF]
Learning DNF through Generalized Fourier Representations
Mohsen Heidari, Roni Khardon; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2788-2804
[abs][Download PDF]
Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient
Lukas Hintze, Lena Krieg, Olga Scheftelowitsch, Haodong Zhu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2805-2821
[abs][Download PDF]
Improved Margin Generalization Bounds for Voting Classifiers
Mikael Høgsgaard Møller, Kasper Green Larsen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2822-2855
[abs][Download PDF]
Polynomial low degree hardness for Broadcasting on Trees (Extended Abstract)
Han Huang, Elchanan Mossel; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2856-2857
[abs][Download PDF]
Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback
Shinji Ito, Haipeng Luo, Taira Tsuchiya, Yue Wu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2858-2892
Optimal Differentially Private Sampling of Unbounded Gaussians
Valentio Iverson, Gautam Kamath, Argyris Mouzakis; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2893-2941
[abs][Download PDF]
Local Regularizers Are Not Transductive Learners
Sky Jafar, Julian Asilis, Shaddin Dughmi; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2942-2957
[abs][Download PDF]
On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
Zeyu Jia, Alexander Rakhlin, Yury Polyanskiy; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2958-3016
[abs][Download PDF]
Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
Minhui Jiang, Yuansi Chen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3017-3078
[abs][Download PDF]
Online Covariance Estimation in Nonsmooth Stochastic Approximation
Liwei Jiang, Abhishek Roy, Krishnakumar Balasubramanian, Damek Davis, Dmitriy Drusvyatskiy, Sen Na; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3079-3123
[abs][Download PDF]
Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
Ruichen Jiang, Devyani Maladkar, Aryan Mokhtari; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3124-3158
[abs][Download PDF]
Structure-agnostic Optimality of Doubly Robust Learning for Treatment Effect Estimation (Extended Abstract)
Jikai Jin, Vasilis Syrgkanis; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3159-3160
[abs][Download PDF]
A Theory of Learning with Autoregressive Chain of Thought
Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, Nathan Srebro; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3161-3212
[abs][Download PDF]
The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints
Hadi Kazemi, Ankit Pensia, Jog Varun; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3213-3214
[abs][Download PDF]
Experimental Design for Semiparametric Bandits
Seok-Jin Kim, Gi-Soo Kim, Min-hwan Oh; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3215-3252
Learning Constant-Depth Circuits in Malicious Noise Models
Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3253-3263
[abs][Download PDF]
Efficiently learning and sampling multimodal distributions with data-based initialization
Frederic Koehler, Holden Lee, Thuy-Duong Vuong; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3264-3326
[abs][Download PDF]
The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria
Guy Kornowski, Ohad Shamir; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3327-3353
[abs][Download PDF]
Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery
Filip Kovačević, Zhang Yihan, Marco Mondelli; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3354-3404
[abs][Download PDF]
The Role of Environment Access in Agnostic Reinforcement Learning (Extended Abstract)
Akshay Krishnamurthy, Gene Li, Ayush Sekhari; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3405-3406
[abs][Download PDF]
Spike-and-Slab Posterior Sampling in High Dimensions
Symantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3407-3462
[abs][Download PDF]
A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis
Akash Kumar, Rahul Parhi, Mikhail Belkin; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3463-3485
[abs][Download PDF]
Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
Dmitriy Kunisky; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3486-3526
[abs][Download PDF]
Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
John Lazarsfeld, Georgios Piliouras, Ryann Sim, Andre Wibisono; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3527-3577
[abs][Download PDF]
The Fundamental Limits of Recovering Planted Subgraphs (extended abstract)
Daniel Z. Lee, Francisco Pernice, Amit Rajaraman, Ilias Zadik; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3578-3579
[abs][Download PDF]
Robust random graph matching in Gaussian models via vector approximate message passing
Zhangsong Li; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3580-3581
[abs][Download PDF]
Some easy optimization problems have the overlap-gap property
Shuangping Li, Tselil Schramm; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3582-3622
[abs][Download PDF]
A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
Junfan Li, Shizhong Liao, Zenglin Xu, Liqiang Nie; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3623-3670
[abs][Download PDF]
Multi-Pass Memory Lower Bounds for Learning Problems
Qian Li, Shuo Wang, Jiapeng Zhang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3671-3699
[abs][Download PDF]
Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity
Bo Li, Wei Wang, Peng Ye; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3700-3722
[abs][Download PDF]
Low-dimensional adaptation of diffusion models: Convergence in total variation (extended abstract)
Jiadong Liang, Zhihan Huang, Yuxin Chen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3723-3729
[abs][Download PDF]
Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of $Φ$-Mutual Information (Extended Abstract)
Jiaming Liang, Siddharth Mitra, Andre Wibisono; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3730-3731
[abs][Download PDF]
Decision Making in Hybrid Environments: A Model Aggregation Approach
Haolin Liu, Chen-Yu Wei, Zimmert Julian; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3732-3765
[abs][Download PDF]
Robust Algorithms for Recovering Planted $r$-Colorable Graphs
Anand Louis, Rameesh Paul, Prasad Raghavendra; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3766-3794
[abs][Download PDF]
Sparsity-Based Interpolation of External, Internal and Swap Regret
Zhou Lu, Y Jennifer Sun, Zhiyu Zhang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3795-3828
[abs][Download PDF]
Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
Jiuyao Lu, Aaron Roth, Mirah Shi; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3829-3878
[abs][Download PDF]
Identifiability and Estimation in High-Dimensional Nonparametric Latent Structure Models
Yichen Lyu, Pengkun Yang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3879-3880
[abs][Download PDF]
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; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3881-3932
[abs][Download PDF]
Learning sparse generalized linear models with binary outcomes via iterative hard thresholding
Namiko Matsumoto, Arya Mazumdar; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3933-4032
[abs][Download PDF]
Online Convex Optimization with a Separation Oracle
Zakaria Mhammedi; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4033-4077
[abs][Download PDF]
Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
Zakaria Mhammedi; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4078-4165
[abs][Download PDF]
The Planted Spanning Tree Problems: Exact Overlap Characterization via Local Weak Convergence Extended Abstract
Mehrdad Moharrami, Cristopher Moore, Jiaming Xu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4166-4167
[abs][Download PDF]
Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
Omar Montasser, Abhishek Shetty, Nikita Zhivotovskiy; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4168-4202
[abs][Download PDF]
Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning
Antoine Moulin, Gergely Neu, Luca Viano; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4203-4270
[abs][Download PDF]
Are all models wrong? Fundamental limits in distribution-free empirical model falsification
Manuel M. Müller, Yuetian Luo, Rina Foygel Barber; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4271-4308
[abs][Download PDF]
Sharper Bounds for Chebyshev Moment Matching, with Applications
Cameron Musco, Christopher Musco, Lucas Rosenblatt, Apoorv Vikram Singh; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4309-4358
[abs][Download PDF]
Estimating stationary mass, frequency by frequency
Milind Nakul, Vidya Muthukumar, Ashwin Pananjady; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4359-4359
[abs][Download PDF]
Improved algorithms for learning quantum Hamiltonians, via flat polynomials
Shyam Narayanan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4360-4385
[abs][Download PDF]
Data-dependent Bounds with $T$-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits using Stability-Penalty Matching
Quan Nguyen, Shinji Ito, Junpei Komiyama, Mehta Nishant; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4386-4451
[abs][Download PDF]
On the Hardness of Bandit Learning
Nataly Brukhim, Aldo Pacchiano, Miroslav Dudik, Robert Schapire; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4452-4485
[abs][Download PDF]
Learning Algorithms in the Limit
Hristo Papazov, Nicolas Flammarion; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4486-4510
[abs][Download PDF]
Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
Pan Peng, Hangyu Xu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4511-4564
[abs][Download PDF]
Recovering Labels from Crowdsourced Data: an Optimal and Polynomial-Time Method
Emmanuel Pilliat; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4565-4595
[abs][Download PDF]
Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
Thanasis Pittas, Ankit Pensia; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4596-4639
[abs][Download PDF]
Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes
Victor S. Portella, Nicholas J. A. Harvey; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4640-4667
[abs][Download PDF]
Linear Convergence of Diffusion Models Under the Manifold Hypothesis
Peter Potaptchik, Iskander Azangulov, George Deligiannidis; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4668-4685
[abs][Download PDF]
Truthfulness of Decision-Theoretic Calibration Measures
Mingda Qiao, Eric Zhao; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4686-4739
[abs][Download PDF]
Generation through the lens of learning theory
Vinod Raman, Jiaxun Li, Ambuj Tewari; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4740-4776
[abs][Download PDF]
Metric Clustering and Graph Optimization Problems using Weak Comparison Oracles
Rahul Raychaudhury, Wen-Zhi Li, Syamantak Das, Sainyam Galhotra, Stavros Sintos; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4777-4830
[abs][Download PDF]
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; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4831-4837
[abs][Download PDF]
Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement Learning
Dhruv Rohatgi, Dylan J. Foster; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4838-4936
[abs][Download PDF]
Can a calibration metric be both testable and actionable?
Raphael Rossellini, Jake A. Soloff, Rina Foygel Barber, Zhimei Ren, Rebecca Willett; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4937-4972
Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
Alexander Ryabchenko, Idan Attias, Daniel M. Roy; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4973-5014
[abs][Download PDF]
Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing
J. Jon Ryu, Jeongyeol Kwon, Benjamin Koppe, Kwang-Sung Jun; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5015-5053
[abs][Download PDF]
New Lower Bounds for Non-Convex Stochastic Optimization through Divergence Decomposition
El Mehdi Saad, Wei-Cheng Lee, Francesco Orabona; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5054-5107
[abs][Download PDF]
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
Itay Safran, Daniel Reichman, Paul Valiant; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5108-5142
[abs][Download PDF]
The late-stage training dynamics of (stochastic) subgradient descent on homogeneous neural networks
Sholom Schechtman, Nicolas Schreuder; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5143-5172
[abs][Download PDF]
Private List Learnability vs. Online List Learnability
Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5173-5213
[abs][Download PDF]
Testing Juntas and Junta Subclasses with Relative Error
Xi Chen, William Pires, Toniann Pitassi, R. A. Servedio; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5214-5245
[abs][Download PDF]
Testing (Conditional) Mutual Information - Extended Abstract
Jan Seyfried, Sayantan Sen, Marco Tomamichel; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5246-5247
[abs][Download PDF]
The Pitfalls of Imitation Learning when Actions are Continuous
Max Simchowitz, Daniel Pfrommer, Ali Jadbabaie; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5248-5351
[abs][Download PDF]
Community detection with the Bethe-Hessian
Ludovic Stephan, Yizhe Zhu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5352-5353
[abs][Download PDF]
Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity Extended Abstract
Dominik Stöger, Yizhe Zhu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5354-5355
[abs][Download PDF]
Optimal Online Bookmaking for Any Number of Outcomes
Hadar Tal, Oron Sabag; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5356-5409
[abs][Download PDF]
Beyond propagation of chaos: A stochastic algorithm for mean field optimization
Chandan Tankala, Dheeraj Nagaraj, Anant Raj; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5410-5440
[abs][Download PDF]
Optimal Scheduling of Dynamic Transport
Panos Tsimpos, Ren Zhi, Jakob Zech, Youssef Marzouk; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5441-5505
[abs][Download PDF]
Corrupted Learning Dynamics in Games
Taira Tsuchiya, Shinji Ito, Haipeng Luo; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5506-5552
[abs][Download PDF]
Learning shallow quantum circuits with many-qubit gates
Francisca Vasconcelos, Hsin-Yuan Huang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5553-5604
[abs][Download PDF]
Black-Box Reductions for Decentralized Online Convex Optimization in Changing Environments
Yuanyu Wan; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5605-5631
[abs][Download PDF]
Learning Compositional Functions with Transformers from Easy-to-Hard Data
Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D Lee, Denny Wu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5632-5711
[abs][Download PDF]
Orthogonal Causal Calibration (Extended Abstract)
Justin Whitehouse, Christopher Jung, Vasilis Syrgkanis, Bryan Wilder, Zhiwei Steven Wu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5712-5713
[abs][Download PDF]
Time-Uniform Self-Normalized Concentration for Vector-Valued Processes (Extended Abstract)
Justin Whitehouse, Zhiwei Steven Wu, Aaditya Ramdas; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5714-5715
[abs][Download PDF]
Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality (Extended Abstract)
Andre Wibisono; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5716-5717
[abs][Download PDF]
Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorization
Yu-Han Wu, Pierre Marion, Gérard Biau, Claire Boyer; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5718-5756
[abs][Download PDF]
Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications
Yizhou Xu, Antoine Maillard, Lenka Zdeborová, Florent Krzakala; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5757-5823
[abs][Download PDF]
Generalization error bound for denoising score matching under relaxed manifold assumption
Konstantin Yakovlev, Nikita Puchkin; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5824-5891
[abs][Download PDF]
Improved Algorithms for Effective Resistance Computation on Graphs
Yang Yichun, Li Rong-Hua, Liao Meihao, Wang Guoren; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5892-5920
[abs][Download PDF]
Robustly Learning Monotone Generalized Linear Models via Data Augmentation
Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, Jelena Diakonikolas; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5921-5990
[abs][Download PDF]
Anytime Acceleration of Gradient Descent
Zihan Zhang, Jason Lee, Simon Du, Yuxin Chen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5991-6013
[abs][Download PDF]
Fast and Multiphase Rates for Nearest Neighbor Classifiers
Pengkun Yang, Jingzhao Zhang; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6014-6015
[abs][Download PDF]
Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
Raymond Zhang, Hadiji Hédi, Combes Richard; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6016-6040
[abs][Download PDF]
Towards Fundamental Limits for Active Multi-distribution Learning
Chicheng Zhang, Yihan Zhou; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6041-6090
[abs][Download PDF]
The Adaptive Complexity of Finding a Stationary Point
Zhou Huanjian, Han Andi, Takeda Akiko, Sugiyama Masashi; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6091-6123
[abs][Download PDF]
Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification
Xiaohan Zhu, Nathan Srebro; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6124-6155
[abs][Download PDF]
Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL
Matthew Zurek, Yudong Chen; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6156-6209
[abs][Download PDF]
Open Problem: Fixed-Parameter Tractability of Zonotope Problems
Vincent Froese, Moritz Grillo, Christoph Hertrich, Martin Skutella; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6210-6214
[abs][Download PDF]
Open Problem: Structure-Agnostic Minimax Risk for Partial Linear Model
Yihong Gu; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6220-6224
[abs][Download PDF]
Open Problem: Data Selection for Regression Tasks
Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6225-6229
[abs][Download PDF]
Open Problem: Optimal Instance-Dependent Sample Complexity for finding Nash Equilibrium in Two Player Zero-Sum Matrix games
Arnab Maiti; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6230-6234
[abs][Download PDF]
Open Problem: Regret Minimization in Heavy-Tailed Bandits with Unknown Distributional Parameters
Gianmarco Genalti, Alberto Maria Metelli; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1-5
[abs][Download PDF]
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。