[edit]
[edit]
Editors: Steve Hanneke, Tor Lattimore
Conference on Learning Theory 2026: Preface
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:i-i
[abs][Download PDF]
How fast can you find a good hypothesis?
Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Sandeep Silwal; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1-2
[abs][Download PDF]
On efficient robust regression with subquadratic samples
Deeksha Adil, Jarosław Błasiok, Hongjie Chen, Deepak Narayanan Sridharan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3-74
[abs][Download PDF]
Quiet Planting for $k$-SAT, Multiple Solutions of Arbitrary Geometry
Ali Ahmadi, Kiarash Banihashem, Iman Gholami, Mohammad Taghi Hajiaghayi, Jan Olkowski; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:75-105
[abs][Download PDF]
Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
Maryam Aliakbarpour, Alireza Azizi, Ria Stevens; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:106-157
[abs][Download PDF]
Query Efficient Structured Matrix Learning
Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Christopher Musco, Cameron Musco, David Persson; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:158-194
[abs][Download PDF]
Swap Regret Minimization Through Response-Based Approachability
Ioannis Anagnostides, Gabriele Farina, Maxwell Fishelson, Haipeng Luo, Jon Schneider; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:195-223
[abs][Download PDF]
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; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:224-289
[abs][Download PDF]
Statistical Learning from Attribution Sets
Lorne Applebaum, Robert Busa-Fekete, August Chen, Claudio Gentile, Tomer Koren, Aryan Mokhtari; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:290-336
[abs][Download PDF]
Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization
Aleksandar Armacki, Dragana Bajović, Dušan Jakovetić, Soummya Kar, Ali H Sayed; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:337-370
[abs][Download PDF]
Learning depth-3 circuits via quantum agnostic boosting
Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael De Oliveira; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:371-426
[abs][Download PDF]
Strongly Polynomial Time Complexity of Policy Iteration for $L_∞$ Robust MDPs
Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:427-457
[abs][Download PDF]
Margin in Abstract Spaces
Yair Ashlagi, Roi Livni, Shay Moran, Tom Waknine; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:458-471
[abs][Download PDF]
A Complexity Measure for Active Learning in Multi-group Mean Estimation
Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:472-473
[abs][Download PDF]
Variational Tail Bounds for Norms of Random Vectors and Matrices
Sohail Bahmani; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:474-504
[abs][Download PDF]
Cloning is as Hard as Learning for Stabilizer States
Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:505-558
[abs][Download PDF]
Limitations of SGD for Multi-Index Models Beyond Statistical Queries
Daniel Barzilai, Ohad Shamir; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:559-612
[abs][Download PDF]
Algorithmic Thinking Theory
MohammadHossein Bateni, Vincent Cohen-Addad, Yuzhou Gu, Silvio Lattanzi, Simon Meierhans, Christopher Mohri; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:613-639
[abs][Download PDF]
Omniprediction with Long-Term Constraints
Yahav Bechavod, Jiuyao Lu, Aaron Roth; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:640-683
[abs][Download PDF]
Adaptive Weighted Averaging
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:684-707
[abs][Download PDF]
Actively Learning Halfspaces without Synthetic Data
Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:708-728
[abs][Download PDF]
Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
Moïse Blanchard, Abhishek Shetty, Alexander Rakhlin; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:729-759
[abs][Download PDF]
Partition Function Estimation under Bounded $f$-Divergence
Adam Block, Abhishek Shetty; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:760-790
[abs][Download PDF]
Tight list replicability bounds via a novel sphere covering theorem
Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:791-807
[abs][Download PDF]
Learning from Equivalence Queries, Revisited
Mark Braverman, Roi Livni, Yishay Mansour, Shay Moran, Kobbi Nissim; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:808-836
[abs][Download PDF]
Learning Conditional Averages
Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:837-858
[abs][Download PDF]
Active Learning on Adversarially Corrupted Graphs
Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d’Orsi, Emmanuel Esposito, Silvio Lattanzi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:859-895
[abs][Download PDF]
Universal priors: solving empirical Bayes via Bayesian inference and pretraining
Nick Cannella, Anzo Teh, Yanjun Han, Yury Polyanskiy; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:896-937
[abs][Download PDF]
Phase Transition for Stochastic Block Model with more than $\sqrtn$ Communities
Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:938-1000
[abs][Download PDF]
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; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1001-1021
[abs][Download PDF]
A Characterization of List Language Identification in the Limit
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1022-1053
[abs][Download PDF]
Language Identification with Succinct Machine-Independent Traces
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1054-1074
[abs][Download PDF]
A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice
Zachary Chase, Shinji Ito, Idan Mehalel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1075-1087
[abs][Download PDF]
Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity
Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1088-1112
[abs][Download PDF]
Separating Oblivious and Adaptive Models of Variable Selection (Extended Abstract)
Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1113-1114
[abs][Download PDF]
Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach
Senrui Chen, Weiyuan Gong, Sisi Zhou; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1115-1185
[abs][Download PDF]
Information-computation gaps in quantum learning via low-degree likelihood
Sitan Chen, Weiyuan Gong, Jonas Haferkamp, Yihui Quek; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1186-1278
[abs][Download PDF]
Optimal Inference Schedules for Masked Diffusion Models
Sitan Chen, Kevin Cong, Jerry Li; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1279-1311
[abs][Download PDF]
Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
Fan Chen, Jian Qian, Alexander Rakhlin, Nikita Zhivotovskiy; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1312-1340
[abs][Download PDF]
High-Accuracy Log-Concave Sampling with Stochastic Queries
Fan Chen, Sinho Chewi, Constantinos Daskalakis, Alexander Rakhlin; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1341-1372
[abs][Download PDF]
Calibeating Made Simple
Yurong Chen, Zhiyi Huang, Michael I. Jordan, Haipeng Luo; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1373-1398
[abs][Download PDF]
Is Memorization Helpful or Harmful? Prior Information Sets the Threshold
Chen Cheng, Rina Foygel Barber; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1399-1433
[abs][Download PDF]
DDPM Score Matching and Distribution Learning (Extended Abstract)
Sinho Chewi, Alkis Kalavasis, Anay Mehrotra, Omar Montasser; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1434-1435
[abs][Download PDF]
Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more
Spencer Compton, Jerry Li; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1436-1475
[abs][Download PDF]
Eigen-Spike Emergence and Quadratic Equivalents for Conjugate Kernels on Nonlinearly Separable Data
Collin Cranston, Zhichao Wang, Todd Kemp, W. Michael Mahoney; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1476-1574
[abs][Download PDF]
Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension
Michael Crawshaw, Mingrui Liu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1575-1610
[abs][Download PDF]
Rigorous Asymptotics for First-Order Algorithms Through the Dynamical Cavity Method
Yatin Dandi, David Gamarnik, Francisco Pernice, Lenka Zdeborová; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1611-1646
[abs][Download PDF]
Estimating Ising Models in Total Variation Distance
Constantinos Daskalakis, Vardis Kandiros, Rui Yao; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1647-1714
[abs][Download PDF]
Stochastic Safe Action Model Learning
Zihao Deng, Brendan Juba; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1715-1736
The matrix-vector complexity of Ax=b
Michał Dereziński, Ethan N Epperly, Raphael A Meyer; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1737-1770
[abs][Download PDF]
Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
Michał Dereziński, Xiaoyu Dong; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1771-1813
[abs][Download PDF]
High-Dimensional Gaussian Mean Estimation under Realizable Contamination
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1814-1856
[abs][Download PDF]
Linear Regression under Missing or Corrupted Coordinates
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1857-1901
[abs][Download PDF]
A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance
Ilias Diakonikolas, Jingyi Gao, Giannis Iakovidis, Daniel M. Kane, Sihan Liu, Thanasis Pittas; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1902-1937
[abs][Download PDF]
Online Convex Optimization with Sublinear Noisy Probes
Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1938-1962
[abs][Download PDF]
Minimax optimal differentially private synthetic data for smooth queries
Rundong Ding, Yiyun He, Yizhe Zhu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1963-1964
[abs][Download PDF]
Rate-optimal community detection near the KS threshold via node-robust algorithms
Jingqiu Ding, Yiding Hua, Kasper Lindberg, David Steurer, Aleksandr Storozhenko; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1965-2037
[abs][Download PDF]
Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
Daniil Dmitriev, Zhihan Huang, Yuting Wei; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2038-2104
[abs][Download PDF]
Online Realizable Regression and Applications for ReLU Networks
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2105-2106
[abs][Download PDF]
Relatively Smart: A New Approach for Instance-Optimal Learning
Shaddin Dughmi, Alireza F. Pour; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2107-2144
[abs][Download PDF]
The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
Abhigyan Dutta, Itay Safran, Paul Valiant; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2145-2199
[abs][Download PDF]
Theoretical Compression Bounds for Wide Multilayer Perceptrons
Houssam El Cheairi, David Gamarnik, Rahul Mazumder; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2200-2258
[abs][Download PDF]
Leveraging Similarities in Multi-Armed Bandits
Khaled Eldowa, Thibaud Rahier, Augustin Cablant, Panayotis Mertikopoulos, Pierre Gaillard; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2259-2306
[abs][Download PDF]
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Liad Erez, Fan Chen, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran, Alexander Rakhlin; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2307-2338
[abs][Download PDF]
Tight Sample Complexity Bounds for Entropic Best Policy Identification
Amer Essakine, Claire Vernade; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2339-2398
[abs][Download PDF]
Defensive Generation
Gabriele Farina, Juan Carlos Perdomo; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2399-2427
[abs][Download PDF]
Optimal Reconstruction from Linear Queries
Yuval Filmus, Shay Moran, Elizaveta Nesterova; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2428-2476
[abs][Download PDF]
Space-Efficient Language Generation in the Limit
Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, Ola Svensson; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2477-2502
[abs][Download PDF]
Toward Simultaneously Optimal Regret in U-Calibration
Rafael Frongillo, Haipeng Luo, Nishant A. Mehta, Jon Schneider; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2503-2534
[abs][Download PDF]
Learning Ising Models from Evolutions (Extended Abstract)
Jason Gaitonde, Ankur Moitra, Elchanan Mossel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2535-2536
[abs][Download PDF]
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2537-2560
[abs][Download PDF]
Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods
Ferdinand Genans; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2561-2600
[abs][Download PDF]
Nearly Linear-Time User-Level DP-SCO with Optimal Rates
Badih Ghazi, Ravi Kumar, Daogao Liu, Pasin Manurangsi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2601-2636
[abs][Download PDF]
Fixed-Parameter Tractability of Private Synthetic Data Generation
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2637-2637
[abs][Download PDF]
Universality of high-dimensional scaling limits of stochastic gradient descent (extended abstract)
Reza Gheissari, Aukosh Jagannath; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2638-2638
[abs][Download PDF]
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani, Jason D. Lee; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2639-2678
[abs][Download PDF]
Sample-Efficient Omniprediction for Proper Losses
Isaac Gibbs, Ryan J. Tibshirani; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2679-2719
[abs][Download PDF]
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
Andreas Göbel, Janosch Ruff, Leon Schiller; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2720-2802
[abs][Download PDF]
Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations
Andreas Göbel, Marcus Pappik, Leon Schiller; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2803-2803
[abs][Download PDF]
Testing Noise Assumptions of Learning Algorithms
Surbhi Goel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2804-2853
[abs][Download PDF]
Compact Geometric Representations of Hierarchies
Prashant Gokhale, Piotr Indyk, Yuhao Liu, Sandeep Silwal, Tony Wang, Haike Xu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2854-2877
[abs][Download PDF]
Randomization for Faster Exact Optimization of Discounted Markov Decision Processes
Andrei Graur, Aaron Sidford, Ta-Wei Tu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2878-2900
[abs][Download PDF]
Computing Lewis weights to high precision using local relative smoothness
Sander Gribling, Aaron Sidford, Chenyi Zhang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2901-2939
[abs][Download PDF]
A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions
Yuzhou Gu, Xin Li, Yinzhan Xu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2940-2962
[abs][Download PDF]
Functional Stochastic Localization
Anming Gu, Bobby Shi, Kevin Tian; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2963-3004
[abs][Download PDF]
High Probability Convergence Guarantees of Stochastic Gradient Descent Ascent in Structured Nonconvex Min-Max Games
Junsoo Ha; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3005-3075
[abs][Download PDF]
An Empirical Bayes Perspective on Heteroskedastic Mean Estimation
Yanjun Han, Abhishek Shetty, Jacob Shkrob; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3076-3108
[abs][Download PDF]
Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise
Rafael Hanashiro, Abhishek Shetty, Patrick Jaillet; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3109-3142
[abs][Download PDF]
Price of metric universality in vector quantization is at most 0.11 bit
Alina Harbuzova, Or Ordentlich, Yury Polyanskiy; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3143-3183
[abs][Download PDF]
Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget (extended abstract)
Michael O. Harding, Vikas Singh, Kirthevasan Kandasamy; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3184-3184
[abs][Download PDF]
A Perfectly Truthful Calibration Measure
Jason Hartline, Lunjia Hu, Yifan Wu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3185-3223
[abs][Download PDF]
Uniform Laws of Large Numbers in Product Spaces
Ron Holzman, Shay Moran, Alexander Shlimovich; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3224-3279
[abs][Download PDF]
Recovery thresholds for hidden weighted sparse graphs (extended abstract)
Zhe Hou, Jingcheng Liu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3280-3284
[abs][Download PDF]
Near-optimal Swap Regret Minimization for Convex Losses
Lunjia Hu, Jon Schneider, Yifan Wu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3285-3313
[abs][Download PDF]
Efficient Swap Multicalibration of Elicitable Properties
Lunjia Hu, Haipeng Luo, Spandan Senapati, Vatsal Sharan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3314-3348
[abs][Download PDF]
Wasserstein Policy Learning for Distributional Outcomes
Yiyan Huang, Cheuk Hang Leung, Qi Wu, Zhiheng Zhang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3349-3350
[abs][Download PDF]
Reconstructing Riemannian Metrics From Random Geometric Graphs
Han Huang, Pakawut Jiradilok, Elchanan Mossel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3351-3440
[abs][Download PDF]
Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion
Xunpeng Huang, Yingyu Lin, Lijing Kuang, Hanze Dong, Difan Zou, Yian Ma, Tong Zhang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3441-3487
Recovery of Planted Subgraphs
Wasim Huleihel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3488-3592
[abs][Download PDF]
Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
Lunjia Hu, Kevin Tian, Chutong Yang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3593-3634
[abs][Download PDF]
On Randomized Algorithms in Online Strategic Classification
Chase Hutton, Adam Melrod, Han Shao; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3635-3665
[abs][Download PDF]
Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret
Shinji Ito, Haipeng Luo, Arnab Maiti, Taira Tsuchiya, Yue Wu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3666-3692
[abs][Download PDF]
On the Importance of Randomization in Discriminative Feature Feedback
Valentio Iverson, Tosca Lechner, Sivan Sabato; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3693-3715
[abs][Download PDF]
Sharp analysis of linear ensemble sampling
David Janz, Arya Akhavan, Csaba Szepesvári; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3716-3750
[abs][Download PDF]
Low-Degree Method Fails to Predict Robust Subspace Recovery
He Jia, Aravindan Vijayaraghavan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3751-3781
[abs][Download PDF]
Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization
Ruichen Jiang, Zakaria Mhammedi, Mehryar Mohri, Aryan Mokhtari; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3782-3824
[abs][Download PDF]
Avoiding exp($k^*$) Scaling for Thompson Sampling in Combinatorial Semi-Bandits: From Multiple Seeds to a Single Seed
Tianyuan Jin, Heyang Zhao, Vincent Y. F. Tan, Quanquan Gu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3825-3855
[abs][Download PDF]
Ripple Mechanisms for Discrete and Private Statistics
Matthew Joseph, Alex Kulesza, Yuyan Wang, Alexander Yu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3856-3903
[abs][Download PDF]
Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases (Extended Abstract)
Alkis Kalavasis, Anay Mehrotra, Felix Zhou; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3904-3905
[abs][Download PDF]
Fast, Parallel, Query-Efficient Binary Classification
Ishani Karmarkar, Liam O’Carroll, Aaron Sidford; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3906-3949
[abs][Download PDF]
Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
David Kattermann, Lothar Sebastian Krapp; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3950-3969
[abs][Download PDF]
Spectral Valleys and Sharp Failures in Greedy Determinant Maximization
Rajiv Khanna; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3970-3992
[abs][Download PDF]
Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3993-4021
[abs][Download PDF]
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
Shyamal Patel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4022-4049
[abs][Download PDF]
Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz-Parisi Potential
Frederic Koehler, Joonhyung Shin; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4050-4228
[abs][Download PDF]
Ambiguous Online Learning
Vanessa Kosoy; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4229-4266
[abs][Download PDF]
Clipping the Price of Adaptivity at the Tail
Itai Kreisler, Yair Carmon, Oliver Hinder; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4267-4307
[abs][Download PDF]
A Distribution Testing Approach to Clustering Distributions
Gunjan Kumar, Yash Pote, Jonathan Scarlett; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4308-4348
[abs][Download PDF]
On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar, Kevin Tian; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4349-4400
[abs][Download PDF]
How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-dimensional Neural Network Regression?
Kuo-Wei Lai, Guanghui Wang, Molei Tao, Vidya Muthukumar; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4401-4477
[abs][Download PDF]
Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader
Jongyeong Lee, Junya Honda, Shinji Ito, Chansoo Kim; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4478-4519
[abs][Download PDF]
Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
Harin Lee, Min-hwan Oh; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4520-4584
[abs][Download PDF]
Blackwell Approachability and Gradient Equilibrium are Equivalent
Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4585-4587
[abs][Download PDF]
A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak–Ruppert Averaging
Wei-Cheng Lee, Francesco Orabona; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4588-4634
[abs][Download PDF]
Self-Concordant Perturbations for Linear Bandits
Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4635-4673
[abs][Download PDF]
Second-Order Bounds for $[0,1]$-Valued Regression via Betting Loss
Yinan Li, Sungjoon Yoon, Ethan Huang, Kwang-Sung Jun; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4674-4721
[abs][Download PDF]
Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup–Stable–Decay (Extended Abstract)
Binghui Li, Zilin Wang, Fengling Chen, Shiyang Zhao, Ruiheng Zheng, Lei Wu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4722-4723
[abs][Download PDF]
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4724-4818
[abs][Download PDF]
Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation
Junyan Liu, Haipeng Luo, Zihan Zhang, Lillian J. Ratliff; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4819-4856
[abs][Download PDF]
Regret Minimization with Adaptive Opponents in Repeated Games
Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4857-4858
[abs][Download PDF]
Random Reshuffling Dominates Stochastic Gradient Descent
Zijian Liu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4859-4882
[abs][Download PDF]
Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity
Hengrui Luo, Anna Ma, Ludovic Stephan, Yizhe Zhu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4883-4884
[abs][Download PDF]
Polynomial-time sampling despite disorder chaos
Eric Ma, Tselil Schramm; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4885-4910
[abs][Download PDF]
On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits
Arnab Maiti, Yunbei Xu, Kevin Jamieson; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4911-4968
[abs][Download PDF]
Online Market Making and the Value of Observing the Order Book
Davide Maran, Marcello Restelli; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4969-4998
[abs][Download PDF]
Phase Transition in Convex Relaxations for Graph Alignment
Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux, Irène Waldspurger; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4999-5020
[abs][Download PDF]
On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5021-5052
[abs][Download PDF]
Language Generation with Infinite Contamination
Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5053-5112
[abs][Download PDF]
Differentially Private Language Generation and Identification in the Limit (Extended Abstract)
Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5113-5114
[abs][Download PDF]
On the Gradient Complexity of Private Optimization with Private Oracles
Michael Menart, Aleksandar Nikolov; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5115-5158
[abs][Download PDF]
On the implicit regularization of Langevin dynamics with projected noise
Govind Menon, Austin Stromme, Adrien Vacher; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5159-5187
[abs][Download PDF]
Steering diffusion models with quadratic rewards: a fine-grained analysis
Ankur Moitra, Andrej Risteski, Dhruv Rohatgi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5188-5209
[abs][Download PDF]
On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentials
Rotem Mulayoff, Sebastian U. Stich; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5210-5243
[abs][Download PDF]
Optimal Neural Network Approximation of Smooth Compositional Functions on Sets with Low Intrinsic Dimension
Thomas Nagler, Sophie Langer; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5244-5272
[abs][Download PDF]
Graph neural networks extrapolate out-of-distribution for shortest paths
Robert R. Nerem, Samantha Chen, Sanjoy Dasgupta, Yusu Wang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5273-5331
[abs][Download PDF]
An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs
Pan Peng, Yuyang Wang, Joy Qiping Yang, Yichun Yang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5332-5357
[abs][Download PDF]
How Many Features Can a Language Model Store Under the Linear Representation Hypothesis?
Nikhil Garg, Jon Kleinberg, Kenny Peng; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5358-5376
[abs][Download PDF]
Boosting with List-Decodable Codes
Addison Prairie, Li-Yang Tan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5377-5396
[abs][Download PDF]
Deep Q-Learning on Hölder Spaces
Qian Qi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5397-5398
[abs][Download PDF]
Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits
Hao Qin, Chicheng Zhang; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5399-5464
[abs][Download PDF]
Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach
Hao Qiu, Mengxiao Zhang, Nicolò Cesa-Bianchi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5465-5517
[abs][Download PDF]
Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum
Nived Rajaraman, Audrey Huang, Miro Dudik, Rob Schapire, Dylan Foster, Akshay Krishnamurthy; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5518-5555
[abs][Download PDF]
Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining
Yunwei Ren, Yatin Dandi, Florent Krzakala, Jason D. Lee; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5556-5597
[abs][Download PDF]
Continuous time policy evaluation is easier with noisy dynamics
Samuel Robertson, Thomas Newton, Csaba Szepesvári; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5598-5624
[abs][Download PDF]
Model Agreement via Anchoring
Eric Eaton, Surbhi Goel, Marcel Hussing, Michael Kearns, Aaron Roth, Sikata Bela Sengupta, Jessica Sorrell; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5625-5661
[abs][Download PDF]
Private Linear Regression via a Down-Sensitivity to Privacy Reduction
Ittai Rubinstein, Chris Ge, Samuel B. Hopkins; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5662-5720
[abs][Download PDF]
A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory
Itay Safran; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5721-5742
[abs][Download PDF]
Convergence of Continual Learning in Homogeneous Deep Networks
Matan Schliserman, Gon Buzaglo, Itay Evron, Daniel Soudry; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5743-5784
[abs][Download PDF]
The Hidden Cost of Approximation in Online Mirror Descent
Ofir Schlisselberg, Uri Sherman, Tomer Koren, Yishay Mansour; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5785-5827
[abs][Download PDF]
Optimal Sample Complexity Lower Bounds on Conditional Independence Testing
Jan Seyfried, Neelkanth Mishra, Sayantan Sen, Marco Tomamichel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5828-5873
[abs][Download PDF]
Testing for a Hidden Geometry in Random Graphs
Amit Silber, Mor Oren-Loberman, Wasim Huleihel; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5874-5927
[abs][Download PDF]
Finite Sample Bounds for Learning with Score Matching
Devin Smedira, Abhijith Jayakumar, Sidhant Misra, Marc Vuffray, Andrey Y. Lokhov; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5928-5949
[abs][Download PDF]
Efficient Learning and Symmetry Discovery under Exact Invariances
Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, Stefanie Jegelka; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5950-5979
[abs][Download PDF]
Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment
Ved Sriraman, Adam Block; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5980-6028
[abs][Download PDF]
Privately Estimating Black-Box Statistics
Günter Steinke, Thomas Steinke; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6029-6074
[abs][Download PDF]
Truly Adapting to Adversarial Constraints in Constrained MABs
Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6075-6113
[abs][Download PDF]
Data Augmentation: A Fourier Analysis Perspective
Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6114-6155
[abs][Download PDF]
CONVERGENCE RATES FOR DISTRIBUTION MATCHING WITH SLICED OPTIMAL TRANSPORT
Gauthier Thurin, Claire Boyer, Kimia Nadjahi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6156-6196
[abs][Download PDF]
On the Asymptotics of Self-Supervised Pre-training: Two-Stage M-Estimation and Representation Symmetry
Mohammad Tinati, Stephen Tu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6197-6309
[abs][Download PDF]
When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networks
Berk Tinaz, Changzhi Xie, Mahdi Soltanolkotabi; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6310-6371
[abs][Download PDF]
Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear $q^\pi$-Realizability and Concentrability
Volodymyr Tkachuk, Csaba Szepesvári, Xiaoqi Tan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6372-6405
[abs][Download PDF]
The Monotonicity of the Franz–Parisi Potential Is Equivalent to Low-Degree MMSE Lower Bounds: Extended Abstract
Konstantinos Tsirkas, Leda Wang, Ilias Zadik; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6406-6409
[abs][Download PDF]
Spectral Recovery of a Planted Triangle-Dense Subgraph
Sam van der Poel, Cheng Mao, Benjamin McKenna; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6410-6457
[abs][Download PDF]
On-Average Stability of Multipass Preconditioned SGD and Effective Dimension
Simon Vary, Tyler Farghly, Ilja Kuzborskij, Patrick Rebeschini; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6458-6495
[abs][Download PDF]
The Geometry of Efficient Nonconvex Sampling
Santosh S. Vempala, Andre Wibisono; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6496-6532
[abs][Download PDF]
Learning with Simulators: No Regret in a Computationally Bounded World
Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6533-6591
[abs][Download PDF]
Fast Score-Based Sampling via Log-Concave Reductions
Martin J. Wainwright; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6592-6621
[abs][Download PDF]
Almost sure null bankruptcy of testing-by-betting strategies
Hongjian Wang, Shubhada Agrawal, Aaditya Ramdas; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6622-6650
[abs][Download PDF]
A simple, optimal and efficient algorithm for online exp-concave optimization
Yi-Han Wang, Peng Zhao, Zhi-Hua Zhou; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6651-6691
[abs][Download PDF]
Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time
Xiuyuan Wang, Vishwak Srinivasan, Qiang Fu, Siddharth Mitra, Andre Wibisono, Ashia Wilson; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6692-6742
[abs][Download PDF]
Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds
Ziao Wang, Lei Ying; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6743-6810
[abs][Download PDF]
Minimax Limits of $k$-Fold Cross-Validation via Majority
Ido Nachum, Ruediger Urbanke, Thomas Weinberger; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6811-6848
[abs][Download PDF]
Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization (Extended Abstract)
Jingfeng Wu, Peter L. Bartlett, Sham M. Kakade, Jason D. Lee, Bin Yu; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6849-6851
[abs][Download PDF]
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs (extended abstract)
Wu Tianhao, Matthew Zurek, Weina Wang, Qiaomin Xie; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6852-6857
[abs][Download PDF]
Worst-case Error Bounds for Online Learning of Smooth Functions
Weian (Andrew) Xie; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6858-6884
[abs][Download PDF]
Optimism Stabilizes Thompson Sampling for Adaptive Inference
Shunxing Yan, Han Zhong; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6885-6886
[abs][Download PDF]
Tight Sample Complexity of Transformers
Chenxiao Yang, Nathan Srebro, Zhiyuan Li; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6887-6923
[abs][Download PDF]
Learning Decision-Sufficient Representations for Linear Optimization
Yuhan Ye, Saurabh Amin, Asuman Özdağlar; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6924-6975
[abs][Download PDF]
Distribution-Free Sequential Prediction with Abstentions
Jialin Yu, Moïse Blanchard; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6976-7011
[abs][Download PDF]
Stable algorithms Lower Bounds for Estimation from MMSE Discontinuities: Extended Abstract
Xifan Yu, Ilias Zadik; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7012-7015
[abs][Download PDF]
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Guy Zamir, Matthew Zurek, Yudong Chen; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7016-7061
[abs][Download PDF]
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi, Peng Zhao; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7062-7104
[abs][Download PDF]
Open Problem: How much overparametrization is needed for ALS in tensor decomposition?
Dionysis Arvanitakis, Vaidehi Srinivas, Aravindan Vijayaraghavan; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7105-7110
[abs][Download PDF]
Invited Open Problem: Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design
Maria-Florina Balcan, Wesley Pegden, Dravyansh Sharma; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7111-7116
[abs][Download PDF]
Invited Open Problem: Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent?
Vitaly Feldman, Pritish Kamath, Nathan Srebro; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7117-7122
[abs][Download PDF]
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
Ivan Lau, Jonathan Scarlett; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7123-7128
[abs][Download PDF]
Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder?
Kobbi Nissim, Uri Stemmer, Eliad Tsfadia; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7129-7135
[abs][Download PDF]
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。