![[The Thirty Eighth Annual Conference on Learning Theory Logo]](/v291/assets/images/logo-pmlr.svg){kind=logo}
[edit]
Volume 291: The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France
[edit]
Editors: Nika Haghtalab, Ankur Moitra
Preface
Conference on Learning Theory 2025: Preface
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:i-i
[abs][Download PDF]
Original Papers
Optimistic Q-learning for average reward and episodic reinforcement learning extended abstract
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1-1
[abs][Download PDF]
Computable learning of natural hypothesis classes
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2-21
[abs][Download PDF]
Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:22-63
[abs][Download PDF]
Regret Bounds for Robust Online Decision Making
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:64-146
[abs][Download PDF]
Simplifying Adversarially Robust PAC Learning With Tolerance
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:147-168
[abs][Download PDF]
Computational Intractability of Strategizing against Online Learners
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:200-201
[abs][Download PDF]
Faster Acceleration for Steepest Descent
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:202-230
[abs][Download PDF]
Thompson Sampling for Bandit Convex Optimisation
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:231-263
[abs][Download PDF]
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:315-343
[abs][Download PDF]
Learning Partitions with Optimal Query and Round Complexities
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:344-374
[abs][Download PDF]
A Distributional-Lifting Theorem for PAC Learning
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:375-379
[abs][Download PDF]
Stability and List-Replicability for Agnostic Learners
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:380-400
[abs][Download PDF]
Proofs as Explanations: Short Certificates for Reliable Predictions
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:401-420
[abs][Download PDF]
Accelerating Proximal Gradient Descent via Silver Stepsizes
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:594-595
[abs][Download PDF]
Of Dice and Games: A Theory of Generalized Boosting
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:596-640
[abs][Download PDF]
A Fine-grained Characterization of PAC Learnability
; 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
; 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)
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:757-798
[abs][Download PDF]
Market Making without Regret
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:799-837
[abs][Download PDF]
Towards Fair Representation: Clustering and Consensus
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:838-853
[abs][Download PDF]
Exploring Facets of Language Generation in the Limit
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:854-887
[abs][Download PDF]
Deterministic Apple Tasting
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:983-985
[abs][Download PDF]
Predicting quantum channels over general product distributions
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1008-1028
[abs][Download PDF]
Learning general Gaussian mixtures with efficient score matching
; 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)
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1091-1093
[abs][Download PDF]
Optimization, Isoperimetric Inequalities, and Sampling via Lyapunov Potentials
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1094-1153
[abs][Download PDF]
Heavy-tailed Estimation is Easier than Adversarial Contamination
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1154-1184
[abs][Download PDF]
The Space Complexity of Learning-Unlearning Algorithms (extended abstract)
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1185-1193
[abs][Download PDF]
Quantum State and Unitary Learning Implies Circuit Lower Bounds
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1253-1258
[abs][Download PDF]
Spherical Dimension
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1259-1313
[abs][Download PDF]
Lower Bounds for Greedy Teaching Set Constructions
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1314-1329
[abs][Download PDF]
Non-Euclidean High-Order Smooth Convex Optimization Extended Abstract
; 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
; 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)
; 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)$
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1368-1379
[abs][Download PDF]
Rate-Preserving Reductions for Blackwell Approachability
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1415-1471
[abs][Download PDF]
Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1472-1530
[abs][Download PDF]
Faster Algorithms for Agnostically Learning Disjunctions and their Implications
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1564-1637
[abs][Download PDF]
Logarithmic Width Suffices for Robust Memorization
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1638-1690
[abs][Download PDF]
Detecting Arbitrary Planted Subgraphs in Random Graphs
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1799-1918
[abs][Download PDF]
Learning Augmented Graph $k$-Clustering
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1935-1973
[abs][Download PDF]
Approximating the total variation distance between spin systems
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2026-2142
[abs][Download PDF]
An uncertainty principle for Linear Recurrent Neural Networks
; 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)
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2190-2191
[abs][Download PDF]
Gradient Methods with Online Scaling
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2192-2226
[abs][Download PDF]
Computing High-dimensional Confidence Sets for Arbitrary Distributions
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2227-2269
[abs][Download PDF]
Blackwell’s Approachability with Approximation Algorithms
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2291-2325
[abs][Download PDF]
Model predictive control is almost optimal for restless bandits
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2326-2361
Computing Optimal Regularizers for Online Linear Optimization
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2362-2402
[abs][Download PDF]
Learning Mixtures of Gaussians Using Diffusion Models
; 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)
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2457-2459
[abs][Download PDF]
PREM: Privately Answering Statistical Queries with Relative Error
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2540-2591
[abs][Download PDF]
Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2592-2631
[abs][Download PDF]
Alternating Regret for Online Convex Optimization
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2632-2633
[abs][Download PDF]
Data Selection for ERMs
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2634-2665
[abs][Download PDF]
Universal Rates of ERM for Agnostic Learning
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2666-2703
[abs][Download PDF]
Universal Rates for Multiclass Learning with Bandit Feedback
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2704-2756
[abs][Download PDF]
Compression Barriers in Autoregressive Transformers
; 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)
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2786-2787
[abs][Download PDF]
Learning DNF through Generalized Fourier Representations
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2805-2821
[abs][Download PDF]
Improved Margin Generalization Bounds for Voting Classifiers
; 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)
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2858-2892
Optimal Differentially Private Sampling of Unbounded Gaussians
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2893-2941
[abs][Download PDF]
Local Regularizers Are Not Transductive Learners
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3017-3078
[abs][Download PDF]
Online Covariance Estimation in Nonsmooth Stochastic Approximation
; 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
; 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)
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3159-3160
[abs][Download PDF]
A Theory of Learning with Autoregressive Chain of Thought
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3213-3214
[abs][Download PDF]
Experimental Design for Semiparametric Bandits
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3215-3252
Learning Constant-Depth Circuits in Malicious Noise Models
; 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
; 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
; 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
; 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)
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3405-3406
[abs][Download PDF]
Spike-and-Slab Posterior Sampling in High Dimensions
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3527-3577
[abs][Download PDF]
The Fundamental Limits of Recovering Planted Subgraphs (extended abstract)
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3580-3581
[abs][Download PDF]
Some easy optimization problems have the overlap-gap property
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3623-3670
[abs][Download PDF]
Multi-Pass Memory Lower Bounds for Learning Problems
; 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
; 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)
; 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)
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3730-3731
[abs][Download PDF]
Decision Making in Hybrid Environments: A Model Aggregation Approach
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3732-3765
[abs][Download PDF]
Robust Algorithms for Recovering Planted $r$-Colorable Graphs
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3766-3794
[abs][Download PDF]
Sparsity-Based Interpolation of External, Internal and Swap Regret
; 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
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3933-4032
[abs][Download PDF]
Online Convex Optimization with a Separation Oracle
; 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
; 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
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4271-4308
[abs][Download PDF]
Sharper Bounds for Chebyshev Moment Matching, with Applications
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4309-4358
[abs][Download PDF]
Estimating stationary mass, frequency by frequency
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4359-4359
[abs][Download PDF]
Improved algorithms for learning quantum Hamiltonians, via flat polynomials
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4386-4451
[abs][Download PDF]
On the Hardness of Bandit Learning
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4452-4485
[abs][Download PDF]
Learning Algorithms in the Limit
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4486-4510
[abs][Download PDF]
Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4640-4667
[abs][Download PDF]
Linear Convergence of Diffusion Models Under the Manifold Hypothesis
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4668-4685
[abs][Download PDF]
Truthfulness of Decision-Theoretic Calibration Measures
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4686-4739
[abs][Download PDF]
Generation through the lens of learning theory
; 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
; 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)
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4838-4936
[abs][Download PDF]
Can a calibration metric be both testable and actionable?
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4937-4972
Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
; 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
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5143-5172
[abs][Download PDF]
Private List Learnability vs. Online List Learnability
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5173-5213
[abs][Download PDF]
Testing Juntas and Junta Subclasses with Relative Error
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5214-5245
[abs][Download PDF]
Testing (Conditional) Mutual Information - Extended Abstract
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5246-5247
[abs][Download PDF]
The Pitfalls of Imitation Learning when Actions are Continuous
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5248-5351
[abs][Download PDF]
Community detection with the Bethe-Hessian
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5354-5355
[abs][Download PDF]
Optimal Online Bookmaking for Any Number of Outcomes
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5410-5440
[abs][Download PDF]
Optimal Scheduling of Dynamic Transport
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5441-5505
[abs][Download PDF]
Corrupted Learning Dynamics in Games
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5506-5552
[abs][Download PDF]
Learning shallow quantum circuits with many-qubit gates
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5632-5711
[abs][Download PDF]
Orthogonal Causal Calibration (Extended Abstract)
; 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)
; 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)
; 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
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5824-5891
[abs][Download PDF]
Improved Algorithms for Effective Resistance Computation on Graphs
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5892-5920
[abs][Download PDF]
Robustly Learning Monotone Generalized Linear Models via Data Augmentation
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5921-5990
[abs][Download PDF]
Anytime Acceleration of Gradient Descent
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5991-6013
[abs][Download PDF]
Fast and Multiphase Rates for Nearest Neighbor Classifiers
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6014-6015
[abs][Download PDF]
Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6016-6040
[abs][Download PDF]
Towards Fundamental Limits for Active Multi-distribution Learning
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6041-6090
[abs][Download PDF]
The Adaptive Complexity of Finding a Stationary Point
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6156-6209
[abs][Download PDF]
Open Problems
Open Problem: Fixed-Parameter Tractability of Zonotope Problems
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:6220-6224
[abs][Download PDF]
Open Problem: Data Selection for Regression Tasks
; 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
; 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
; Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1-5
[abs][Download PDF]
subscribe via RSS