[edit]
[edit]
Editors: Shipra Agrawal, Aaron Roth
Conference on Learning Theory 2024: Preface
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:i-i
[abs][Download PDF]
Limits of Approximating the Median Treatment Effect
Raghavendra Addanki, Siddharth Bhandari; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1-21
[abs][Download PDF]
Majority-of-Three: The Simplest Optimal Learner?
Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:22-45
[abs][Download PDF]
Metalearning with Very Few Samples Per Task
Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro, Jonathan Ullman; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:46-93
[abs][Download PDF]
A Unified Characterization of Private Learnability via Graph Theory
Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:94-129
[abs][Download PDF]
Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning
Philip Amortila, Tongyi Cao, Akshay Krishnamurthy; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:130-160
[abs][Download PDF]
Fast parallel sampling under isoperimetry
Nima Anari, Sinho Chewi, Thuy-Duong Vuong; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:161-185
[abs][Download PDF]
Two fundamental limits for uncertainty quantification in predictive inference
Felipe Areces, Chen Cheng, John Duchi, Kuditipudi Rohith; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:186-218
[abs][Download PDF]
Mode Estimation with Partial Feedback
Charles Arnal, Vivien Cabannes, Vianney Perchet; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:219-220
[abs][Download PDF]
Universally Instance-Optimal Mechanisms for Private Statistical Estimation
Hilal Asi, John C. Duchi, Saminul Haque, Zewei Li, Feng Ruan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:221-259
[abs][Download PDF]
Regularization and Optimal Multiclass Learning
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:260-310
[abs][Download PDF]
The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
Sepehr Assadi, Chen Wang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:311-358
[abs][Download PDF]
Universal Rates for Regression: Separations between Cut-Off and Absolute Loss
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:359-405
[abs][Download PDF]
Learning Neural Networks with Sparse Activations
Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:406-425
[abs][Download PDF]
The SMART approach to instance-optimal online learning
Siddhartha Banerjee, Alankrita Bhatt, Christina Lee Yu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:426-426
[abs][Download PDF]
Detection of $L_∞$ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion
Kiril Bangachev, Guy Bresler; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:427-497
[abs][Download PDF]
Metric Clustering and MST with Strong and Weak Distance Oracles
MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, Chen Wang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:498-550
[abs][Download PDF]
Correlated Binomial Process
Moïse Blanchard, Doron Cohen, Aryeh Kontorovich; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:551-595
[abs][Download PDF]
On the Performance of Empirical Risk Minimization with Smoothed Data
Adam Block, Alexander Rakhlin, Abhishek Shetty; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:596-629
[abs][Download PDF]
Errors are Robustly Tamed in Cumulative Knowledge Processes
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:630-631
[abs][Download PDF]
Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
Guy Bresler, Chenghao Guo, Yury Polyanskiy; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:632-647
A Theory of Interpretable Approximations
Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:648-668
[abs][Download PDF]
Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
Marco Bressan, Emmanuel Esposito, Maximilian Thiessen; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:669-696
[abs][Download PDF]
Online Stackelberg Optimization via Nonlinear Control
William Brown, Christos Papadimitriou, Tim Roughgarden; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:697-749
[abs][Download PDF]
Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract
Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C Perdomo, Adam Smith; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:750-751
[abs][Download PDF]
Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
Rares-Darius Buhai, Jingqiu Ding, Stefan Tiegel; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:752-771
[abs][Download PDF]
The Price of Adaptivity in Stochastic Convex Optimization
Yair Carmon, Oliver Hinder; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:772-774
[abs][Download PDF]
Information-theoretic generalization bounds for learning from quantum data
Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:775-839
[abs][Download PDF]
Non-Clashing Teaching Maps for Balls in Graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:840-875
[abs][Download PDF]
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:876-922
[abs][Download PDF]
Dual VC Dimension Obstructs Sample Compression by Embeddings
Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:923-946
[abs][Download PDF]
On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis
Lesi Chen, Jing Xu, Jingzhao Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:947-980
[abs][Download PDF]
A faster and simpler algorithm for learning shallow networks
Sitan Chen, Shyam Narayanan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:981-994
[abs][Download PDF]
Near-Optimal Learning and Planning in Separated Latent MDPs
Fan Chen, Constantinos Daskalakis, Noah Golowich, Alexander Rakhlin; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:995-1067
[abs][Download PDF]
Scale-free Adversarial Reinforcement Learning
Mingyu Chen, Xuezhou Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1068-1101
[abs][Download PDF]
The power of an adversary in Glauber dynamics
Byron Chin, Ankur Moitra, Elchanan Mossel, Colin Sandon; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1102-1124
[abs][Download PDF]
Undetectable Watermarks for Language Models
Miranda Christ, Sam Gunn, Or Zamir; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1125-1139
[abs][Download PDF]
Risk-Sensitive Online Algorithms (Extended Abstract)
Nicolas Christianson, Bo Sun, Steven Low, Adam Wierman; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1140-1141
[abs][Download PDF]
Statistical curriculum learning: An elimination algorithm achieving an oracle risk
Omer Cohen, Ron Meir, Nir Weinberger; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1142-1199
[abs][Download PDF]
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1200-1222
[abs][Download PDF]
Learnability Gaps of Strategic Classification
Lee Cohen, Yishay Mansour, Shay Moran, Han Shao; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1223-1259
[abs][Download PDF]
Refined Sample Complexity for Markov Games with Independent Linear Function Approximation (Extended Abstract)
Yan Dai, Qiwen Cui, Simon S. Du; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1260-1261
[abs][Download PDF]
Computational-Statistical Gaps in Gaussian Single-Index Models (Extended Abstract)
Alex Damian, Loucas Pillaud-Vivien, Jason Lee, Joan Bruna; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1262-1262
[abs][Download PDF]
Is Efficient PAC Learning Possible with an Oracle That Responds "Yes" or "No"?
Constantinos Daskalakis, Noah Golowich; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1263-1307
[abs][Download PDF]
Testable Learning of General Halfspaces with Adversarial Label Noise
Ilias Diakonikolas, Daniel Kane, Sihan Liu, Nikos Zarifis; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1308-1335
[abs][Download PDF]
Statistical Query Lower Bounds for Learning Truncated Gaussians
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1336-1363
[abs][Download PDF]
Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials
Ilias Diakonikolas, Daniel M. Kane; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1364-1378
[abs][Download PDF]
On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective
Daniil Dmitriev, Kristóf Szabó, Amartya Sanyal; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1379-1398
[abs][Download PDF]
Physics-informed machine learning as a kernel method
Nathan Doumèche, Francis Bach, Gérard Biau, Claire Boyer; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1399-1450
[abs][Download PDF]
Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models
Maximilien Dreveton, Alperen Gözeten, Matthias Grossglauser, Patrick Thiran; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1451-1485
[abs][Download PDF]
An information-theoretic lower bound in time-uniform estimation
John Duchi, Saminul Haque; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1486-1500
[abs][Download PDF]
On sampling diluted Spin-Glasses using Glauber Dynamics
Charilaos Efthymiou, Kostas Zampetakis; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1501-1515
[abs][Download PDF]
Minimax Linear Regression under the Quantile Risk
Ayoub El Hanchi, Chris Maddison, Murat Erdogdu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1516-1572
[abs][Download PDF]
The Real Price of Bandit Information in Multiclass Classification
Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1573-1598
[abs][Download PDF]
Topological Expressivity of ReLU Neural Networks
Ekin Ergen, Moritz Grillo; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1599-1642
[abs][Download PDF]
Contraction of Markovian Operators in Orlicz Spaces and Error Bounds for Markov Chain Monte Carlo (Extended Abstract)
Amedeo Roberto Esposito, Marco Mondelli; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1643-1645
[abs][Download PDF]
Computation-information gap in high-dimensional clustering
Bertrand Even, Christophe Giraud, Nicolas Verzelen; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1646-1712
[abs][Download PDF]
Online Newton Method for Bandit Convex Optimisation Extended Abstract
Hidde Fokkema, Dirk Van der Hoeven, Tor Lattimore, Jack J. Mayo; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1713-1714
[abs][Download PDF]
Agnostic Active Learning of Single Index Models with Linear Sample Complexity
Aarshvi Gajjar, Wai Ming Tai, Xu Xingyu, Chinmay Hegde, Christopher Musco, Yi Li; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1715-1754
[abs][Download PDF]
Safe Linear Bandits over Unknown Polytopes
Aditya Gangrade, Tianrui Chen, Venkatesh Saligrama; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1755-1795
[abs][Download PDF]
Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier
Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1796-1881
[abs][Download PDF]
(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits
Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, Alberto Maria Metelli; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1882-1915
[abs][Download PDF]
On Convex Optimization with Semi-Sensitive Features
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1916-1938
[abs][Download PDF]
Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
Noah Golowich, Ankur Moitra; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1939-1981
[abs][Download PDF]
Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems extended abstract
Tomas Gonzalez, Cristobal Guzman, Courtney Paquette; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1982-1982
[abs][Download PDF]
On Computationally Efficient Multi-Class Calibration
Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1983-2026
[abs][Download PDF]
Omnipredictors for regression and the approximate rank of convex functions
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, Mihir Singhal; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2027-2070
[abs][Download PDF]
Identification of mixtures of discrete product distributions in near-optimal sample and time complexity
Spencer L. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2071-2091
[abs][Download PDF]
On the Computability of Robust PAC Learning
Pascale Gourdeau, Lechner. Tosca, Ruth Urner; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2092-2121
[abs][Download PDF]
Principal eigenstate classical shadows
Daniel Grier, Hakop Pashayan, Luke Schaeffer; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2122-2165
[abs][Download PDF]
Community detection in the hypergraph stochastic block model and reconstruction on hypertrees
Yuzhou Gu, Aaradhya Pandey; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2166-2203
[abs][Download PDF]
Stochastic Constrained Contextual Bandits via Lyapunov Optimization Based Estimation to Decision Framework
Hengquan Guo, Xin Liu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2204-2231
[abs][Download PDF]
Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation
Shivam Gupta, Samuel Hopkins, Eric Price; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2232-2269
[abs][Download PDF]
Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes
Yanjun Han, Tianze Jiang, Yihong Wu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2270-2307
[abs][Download PDF]
The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement
Steve Hanneke; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2308-2359
[abs][Download PDF]
List Sample Compression and Uniform Convergence
Steve Hanneke, Shay Moran, Waknine Tom; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2360-2388
[abs][Download PDF]
Adversarially-Robust Inference on Trees via Belief Propagation
Samuel B. Hopkins, Anqui Li; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2389-2417
[abs][Download PDF]
On the sample complexity of parameter estimation in logistic regression with normal design
Daniel Hsu, Arya Mazumdar; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2418-2437
[abs][Download PDF]
Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo
Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, Tong Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2438-2493
[abs][Download PDF]
Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs
Dong Huang, Xianwen Song, Pengkun Yang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2494-2518
[abs][Download PDF]
Reconstructing the Geometry of Random Geometric Graphs (Extended Abstract)
Han Huang, Pakawut Jiradilok, Elchanan Mossel; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2519-2521
[abs][Download PDF]
Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds
Shinji Ito, Taira Tsuchiya, Junya Honda; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2522-2563
[abs][Download PDF]
Black-Box k-to-1-PCA Reductions: Theory and Applications
Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia, Kevin Tian; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2564-2607
[abs][Download PDF]
Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
Arun Jambulapati, Aaron Sidford, Kevin Tian; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2608-2643
[abs][Download PDF]
Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data
Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, Chen-Yu Wei; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2644-2719
[abs][Download PDF]
Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space
Yiheng Jiang, Sinho Chewi, Aram-Alexandre Pooladian; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2720-2721
[abs][Download PDF]
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract)
Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2722-2722
[abs][Download PDF]
Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise
Matthew Joseph, Alexander Yu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2723-2766
[abs][Download PDF]
Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening (Extended Abstract)
Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2767-2767
[abs][Download PDF]
New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions
Yuqian Cheng, Daniel Kane, Zheng Zhicheng; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2768-2794
[abs][Download PDF]
Choosing the p in Lp Loss: Adaptive Rates for Symmetric Mean Estimation
Yu-Chun Kao, Min Xu, Cun-Hui Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2795-2839
[abs][Download PDF]
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2840-2886
[abs][Download PDF]
Testable Learning with Distribution Shift
Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2887-2943
[abs][Download PDF]
Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2944-2978
[abs][Download PDF]
Superconstant Inapproximability of Decision Tree Learning
Caleb Koch, Carmen Strassle, Li-Yang Tan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2979-3010
[abs][Download PDF]
Convergence of Kinetic Langevin Monte Carlo on Lie groups
Lingkai Kong, Molei Tao; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3011-3063
Active Learning with Simple Questions
Kontonis Vasilis, Ma Mingchen, Tzamos Christos; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3064-3098
[abs][Download PDF]
Sampling from the Mean-Field Stationary Distribution
Yunbum Kook, Matthew S. Zhang, Sinho Chewi, Murat A. Erdogdu, Mufan (Bill) Li; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3099-3136
[abs][Download PDF]
Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
Yunbum Kook, Santosh S. Vempala; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3137-3240
[abs][Download PDF]
Simple online learning with consistent oracle
Alexander Kozachinskiy, Tomasz Steifer; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3241-3256
[abs][Download PDF]
Accelerated Parameter-Free Stochastic Optimization
Itai Kreisler, Maor Ivgi, Oliver Hinder, Yair Carmon; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3257-3324
[abs][Download PDF]
Better-than-KL PAC-Bayes Bounds
Ilja Kuzborskij, Kwang-Sung Jun, Yulian Wu, Kyoungseok Jang, Francesco Orabona; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3325-3352
[abs][Download PDF]
Inherent limitations of dimensions for characterizing learnability of distribution classes
Tosca Lechner, Shai Ben-David; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3353-3374
[abs][Download PDF]
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; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3375-3430
[abs][Download PDF]
Minimax-optimal reward-agnostic exploration in reinforcement learning
Gen Li, Yuling Yan, Yuxin Chen, Jianqing Fan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3431-3436
[abs][Download PDF]
Optimistic Rates for Learning from Label Proportions
Gene Li, Lin Chen, Adel Javanmard, Vahab Mirrokni; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3437-3474
[abs][Download PDF]
Online Policy Optimization in Unknown Nonlinear Systems
Yiheng Lin, James A. Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung, Yisong Yue, Adam Wierman; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3475-3522
[abs][Download PDF]
The role of randomness in quantum state certification with unentangled measurements
Yuhan Liu, Jayadev Acharya; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3523-3555
[abs][Download PDF]
Spatial properties of Bayesian unsupervised trees
Linxi Liu, Li Ma; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3556-3581
[abs][Download PDF]
The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations
Quanquan C. Liu, Vaidehi Srinivas; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3582-3641
[abs][Download PDF]
Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3642-3643
[abs][Download PDF]
Linear bandits with polylogarithmic minimax regret
Josep Lumbreras, Marco Tomamichel; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3644-3682
[abs][Download PDF]
Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion
Jianhao Ma, Salar Fattahi; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3683-3742
[abs][Download PDF]
Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs
Davide Maran, Alberto Maria Metelli, Matteo Papini, Marcello Restelli; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3743-3774
[abs][Download PDF]
Harmonics of Learning: Universal Fourier Features Emerge in Invariant Networks
Giovanni Luca Marchetti, Christopher J Hillar, Danica Kragic, Sophia Sanborn; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3775-3797
[abs][Download PDF]
Low-degree phase transitions for detecting a planted clique in sublinear time
Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3798-3822
[abs][Download PDF]
Fast, blind, and accurate: Tuning-free sparse regression with global linear convergence
Claudio Mayrink Verdun, Oleh Melnyk, Felix Krahmer, Peter Jung; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3823-3872
[abs][Download PDF]
Fundamental Limits of Non-Linear Low-Rank Matrix Estimation
Pierre Mergny, Justin Ko, Florent Krzakala, Lenka Zdeborová; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3873-3873
[abs][Download PDF]
Finding Super-spreaders in Network Cascades
Elchanan Mossel, Anirudh Sridhar; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3874-3914
[abs][Download PDF]
Exact Mean Square Linear Stability Analysis for SGD
Rotem Mulayoff, Tomer Michaeli; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3915-3969
[abs][Download PDF]
Optimistic Information Directed Sampling
Gergely Neu, Matteo Papini, Ludovic Schwartz; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3970-4006
[abs][Download PDF]
Robust Distribution Learning with Local and Global Adversarial Corruptions (extended abstract)
Sloan Nietert, Ziv Goldfeld, Soroosh Shafiee; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4007-4008
[abs][Download PDF]
Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations
Kazusato Oko, Yujin Song, Taiji Suzuki, Denny Wu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4009-4081
[abs][Download PDF]
Depth Separation in Norm-Bounded Infinite-Width Neural Networks
Suzanna Parkinson, Greg Ongie, Rebecca Willett, Ohad Shamir, Nathan Srebro; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4082-4114
[abs][Download PDF]
The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication
Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U Stich, Ziheng Cheng, Nirmit Joshi, Nathan Srebro; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4115-4157
The complexity of approximate (coarse) correlated equilibrium for incomplete information games
Binghui Peng, Aviad Rubinstein; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4158-4184
[abs][Download PDF]
The sample complexity of multi-distribution learning
Binghui Peng; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4185-4204
[abs][Download PDF]
The Sample Complexity of Simple Binary Hypothesis Testing
Ankit Pensia, Varun Jog, Po-Ling Loh; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4205-4206
[abs][Download PDF]
Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes
Naty Peter, Eliad Tsfadia, Jonathan Ullman; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4207-4239
[abs][Download PDF]
Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity
Alireza F. Pour, Hassan Ashtiani, Shahab Asoodeh; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4240-4275
[abs][Download PDF]
Dimension-free Structured Covariance Estimation
Nikita Puchkin, Maxim Rakhuba; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4276-4306
[abs][Download PDF]
On the Distance from Calibration in Sequential Prediction
Mingda Qiao, Letian Zheng; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4307-4357
[abs][Download PDF]
Apple Tasting: Combinatorial Dimensions and Minimax Rates
Vinod Raman, Unique Subedi, Ananth Raman, Ambuj Tewari; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4358-4380
[abs][Download PDF]
Online Learning with Set-valued Feedback
Vinod Raman, Unique Subedi, Ambuj Tewari; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4381-4412
[abs][Download PDF]
Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions
Yilong Qin, Andrej Risteski; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4413-4457
[abs][Download PDF]
Online Structured Prediction with Fenchel–Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss
Shinsaku Sakaue, Han Bao, Taira Tsuchiya, Taihei Oki; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4458-4486
[abs][Download PDF]
Provable Advantage in Quantum PAC Learning
Wilfred Salmon, Sergii Strelchuk, Tom Gur; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4487-4510
[abs][Download PDF]
Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, Eric Moulines; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4511-4547
[abs][Download PDF]
Adversarial Online Learning with Temporal Feedback Graphs
Khashayar Gatmiry, Jon Schneider; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4548-4572
[abs][Download PDF]
Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality (extended abstract)
Chen Siyu, Sheen Heejune, Wang Tianhao, Yang Zhuoran; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4573-4573
[abs][Download PDF]
A Non-Adaptive Algorithm for the Quantitative Group Testing Problem
Mahdi Soleymani, Tara Javidi; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4574-4592
[abs][Download PDF]
Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm
Vishwak Srinivasan, Andre Wibisono, Ashia Wilson; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4593-4635
[abs][Download PDF]
A non-backtracking method for long matrix and tensor completion
Ludovic Stephan, Yizhe Zhu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4636-4690
[abs][Download PDF]
Second Order Methods for Bandit Optimization and Control
Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, Elad Hazan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4691-4763
[abs][Download PDF]
Improved Hardness Results for Learning Intersections of Halfspaces
Stefan Tiegel; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4764-4786
[abs][Download PDF]
Pruning is Optimal for Learning Sparse Features in High-Dimensions
Nuri Mert Vural, Murat A Erdogdu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4787-4861
[abs][Download PDF]
Nearly Optimal Regret for Decentralized Online Convex Optimization
Yuanyu Wan, Tong Wei, Mingli Song, Lijun Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4862-4888
[abs][Download PDF]
Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation Extended Abstract
Ziao Wang, Weina Wang, Lele Wang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4889-4890
[abs][Download PDF]
Nonlinear spiked covariance matrices and signal propagation in deep neural networks
Zhichao Wang, Denny Wu, Zhou Fan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4891-4957
[abs][Download PDF]
Optimal score estimation via empirical Bayes smoothing
Andre Wibisono, Yihong Wu, Kaylee Yingxi Yang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4958-4991
[abs][Download PDF]
Oracle-Efficient Hybrid Online Learning with Unknown Distribution
Changlong Wu, Jin Sima, Wojciech Szpankowski; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4992-5018
[abs][Download PDF]
Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, Bin Yu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5019-5073
[abs][Download PDF]
Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization
Jiancong Xiao, Ruoyu Sun, Qi Long, Weijie Su; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5074-5075
[abs][Download PDF]
Multiple-output composite quantile regression through an optimal transport lens
Xuzhi Yang, Tengyao Wang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5076-5122
[abs][Download PDF]
Top-$K$ ranking with a monotone adversary
Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5123-5162
[abs][Download PDF]
Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract
Xifan Yu, Ilias Zadik, Peiyuan Zhang; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5163-5165
[abs][Download PDF]
Fast two-time-scale stochastic gradient method with applications in reinforcement learning
Sihan Zeng, Thinh Doan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5166-5212
[abs][Download PDF]
Settling the sample complexity of online reinforcement learning
Zihan Zhang, Yuxin Chen, Jason D Lee, Simon S Du; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5213-5219
[abs][Download PDF]
Optimal Multi-Distribution Learning
Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S Du, Jason D Lee; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5220-5223
[abs][Download PDF]
Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing (Extended Abstract)
Yihan Zhang, Hong Chang Ji, Ramji Venkataramanan, Marco Mondelli; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5224-5230
[abs][Download PDF]
Gap-Free Clustering: Sensitivity and Robustness of SDP
Matthew Zurek, Yudong Chen; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5231-5300
[abs][Download PDF]
Open Problem: Can Local Regularization Learn All Multiclass Problems?
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5301-5305
[abs][Download PDF]
Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?
Achraf Azize, Debabrota Basu; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5306-5311
[abs][Download PDF]
Open Problem: Tight Characterization of Instance-Optimal Identity Testing
Clément Canonne; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5312-5316
[abs][Download PDF]
Open Problem: Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization
Xinyi Chen, Elad Hazan; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5317-5324
[abs][Download PDF]
Open problem: Direct Sums in Learning Theory
Steve Hanneke, Shay Moran, Waknine Tom; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5325-5329
[abs][Download PDF]
Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy
Bingshan Hu, Nishant A. Mehta; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5330-5334
[abs][Download PDF]
Open Problem: Anytime Convergence Rate of Gradient Descent
Guy Kornowski, Ohad Shamir; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5335-5339
[abs][Download PDF]
Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning
Sattar Vakili; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5340-5344
[abs][Download PDF]
Open problem: Convergence of single-timescale mean-field Langevin descent-ascent for two-player zero-sum games
Guillaume Wang, Lénaïc Chizat; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5345-5350
[abs][Download PDF]
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。