![[The Thirty Ninth Annual Conference on Learning Theory Logo]](/v336/assets/images/logo-pmlr.svg){kind=logo}
[edit]
Volume 336: The Thirty Ninth Annual Conference on Learning Theory, 29-3 July 2026, San Diego, California
[edit]
Editors: Steve Hanneke, Tor Lattimore
Preface
Conference on Learning Theory 2026: Preface
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:i-i
[abs][Download PDF]
Original Papers
How fast can you find a good hypothesis?
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1-2
[abs][Download PDF]
On efficient robust regression with subquadratic samples
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:75-105
[abs][Download PDF]
Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:106-157
[abs][Download PDF]
Query Efficient Structured Matrix Learning
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:158-194
[abs][Download PDF]
Swap Regret Minimization Through Response-Based Approachability
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:224-289
[abs][Download PDF]
Statistical Learning from Attribution Sets
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:337-370
[abs][Download PDF]
Learning depth-3 circuits via quantum agnostic boosting
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:427-457
[abs][Download PDF]
Margin in Abstract Spaces
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:474-504
[abs][Download PDF]
Cloning is as Hard as Learning for Stabilizer States
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:559-612
[abs][Download PDF]
Algorithmic Thinking Theory
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:613-639
[abs][Download PDF]
Omniprediction with Long-Term Constraints
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:640-683
[abs][Download PDF]
Adaptive Weighted Averaging
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:684-707
[abs][Download PDF]
Actively Learning Halfspaces without Synthetic Data
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:729-759
[abs][Download PDF]
Partition Function Estimation under Bounded $f$-Divergence
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:791-807
[abs][Download PDF]
Learning from Equivalence Queries, Revisited
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:808-836
[abs][Download PDF]
Learning Conditional Averages
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:837-858
[abs][Download PDF]
Active Learning on Adversarially Corrupted Graphs
; 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
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1001-1021
[abs][Download PDF]
A Characterization of List Language Identification in the Limit
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1022-1053
[abs][Download PDF]
Language Identification with Succinct Machine-Independent Traces
; 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
; 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
; 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)
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1186-1278
[abs][Download PDF]
Optimal Inference Schedules for Masked Diffusion Models
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1312-1340
[abs][Download PDF]
High-Accuracy Log-Concave Sampling with Stochastic Queries
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1341-1372
[abs][Download PDF]
Calibeating Made Simple
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1399-1433
[abs][Download PDF]
DDPM Score Matching and Distribution Learning (Extended Abstract)
; 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
; 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
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1611-1646
[abs][Download PDF]
Estimating Ising Models in Total Variation Distance
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1647-1714
[abs][Download PDF]
Stochastic Safe Action Model Learning
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1715-1736
The matrix-vector complexity of Ax=b
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1771-1813
[abs][Download PDF]
High-Dimensional Gaussian Mean Estimation under Realizable Contamination
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1814-1856
[abs][Download PDF]
Linear Regression under Missing or Corrupted Coordinates
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1902-1937
[abs][Download PDF]
Online Convex Optimization with Sublinear Noisy Probes
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1938-1962
[abs][Download PDF]
Minimax optimal differentially private synthetic data for smooth queries
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2038-2104
[abs][Download PDF]
Online Realizable Regression and Applications for ReLU Networks
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2105-2106
[abs][Download PDF]
Relatively Smart: A New Approach for Instance-Optimal Learning
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2145-2199
[abs][Download PDF]
Theoretical Compression Bounds for Wide Multilayer Perceptrons
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2200-2258
[abs][Download PDF]
Leveraging Similarities in Multi-Armed Bandits
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2259-2306
[abs][Download PDF]
The Sample Complexity of Multiclass and Sparse Contextual Bandits
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2307-2338
[abs][Download PDF]
Tight Sample Complexity Bounds for Entropic Best Policy Identification
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2339-2398
[abs][Download PDF]
Defensive Generation
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2399-2427
[abs][Download PDF]
Optimal Reconstruction from Linear Queries
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2428-2476
[abs][Download PDF]
Space-Efficient Language Generation in the Limit
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2477-2502
[abs][Download PDF]
Toward Simultaneously Optimal Regret in U-Calibration
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2503-2534
[abs][Download PDF]
Learning Ising Models from Evolutions (Extended Abstract)
; 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
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2601-2636
[abs][Download PDF]
Fixed-Parameter Tractability of Private Synthetic Data Generation
; 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)
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2639-2678
[abs][Download PDF]
Sample-Efficient Omniprediction for Proper Losses
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2803-2803
[abs][Download PDF]
Testing Noise Assumptions of Learning Algorithms
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2804-2853
[abs][Download PDF]
Compact Geometric Representations of Hierarchies
; 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
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2940-2962
[abs][Download PDF]
Functional Stochastic Localization
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3005-3075
[abs][Download PDF]
An Empirical Bayes Perspective on Heteroskedastic Mean Estimation
; 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
; 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
; 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)
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3184-3184
[abs][Download PDF]
A Perfectly Truthful Calibration Measure
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3185-3223
[abs][Download PDF]
Uniform Laws of Large Numbers in Product Spaces
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3224-3279
[abs][Download PDF]
Recovery thresholds for hidden weighted sparse graphs (extended abstract)
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3280-3284
[abs][Download PDF]
Near-optimal Swap Regret Minimization for Convex Losses
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3285-3313
[abs][Download PDF]
Efficient Swap Multicalibration of Elicitable Properties
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3314-3348
[abs][Download PDF]
Wasserstein Policy Learning for Distributional Outcomes
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3349-3350
[abs][Download PDF]
Reconstructing Riemannian Metrics From Random Geometric Graphs
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3441-3487
Recovery of Planted Subgraphs
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3488-3592
[abs][Download PDF]
Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3593-3634
[abs][Download PDF]
On Randomized Algorithms in Online Strategic Classification
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3666-3692
[abs][Download PDF]
On the Importance of Randomization in Discriminative Feature Feedback
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3693-3715
[abs][Download PDF]
Sharp analysis of linear ensemble sampling
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3716-3750
[abs][Download PDF]
Low-Degree Method Fails to Predict Robust Subspace Recovery
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3825-3855
[abs][Download PDF]
Ripple Mechanisms for Discrete and Private Statistics
; 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)
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3904-3905
[abs][Download PDF]
Fast, Parallel, Query-Efficient Binary Classification
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3950-3969
[abs][Download PDF]
Spectral Valleys and Sharp Failures in Greedy Determinant Maximization
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3970-3992
[abs][Download PDF]
Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4050-4228
[abs][Download PDF]
Ambiguous Online Learning
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4229-4266
[abs][Download PDF]
Clipping the Price of Adaptivity at the Tail
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4267-4307
[abs][Download PDF]
A Distribution Testing Approach to Clustering Distributions
; 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
; 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?
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4520-4584
[abs][Download PDF]
Blackwell Approachability and Gradient Equilibrium are Equivalent
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4588-4634
[abs][Download PDF]
Self-Concordant Perturbations for Linear Bandits
; 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
; 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)
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4819-4856
[abs][Download PDF]
Regret Minimization with Adaptive Opponents in Repeated Games
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4857-4858
[abs][Download PDF]
Random Reshuffling Dominates Stochastic Gradient Descent
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4883-4884
[abs][Download PDF]
Polynomial-time sampling despite disorder chaos
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4969-4998
[abs][Download PDF]
Phase Transition in Convex Relaxations for Graph Alignment
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5021-5052
[abs][Download PDF]
Language Generation with Infinite Contamination
; 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)
; 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
; 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
; 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
; 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
; 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
; 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
; 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
; 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?
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5358-5376
[abs][Download PDF]
Boosting with List-Decodable Codes
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5377-5396
[abs][Download PDF]
Deep Q-Learning on Hölder Spaces
; 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
; 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
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5556-5597
[abs][Download PDF]
Continuous time policy evaluation is easier with noisy dynamics
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5598-5624
[abs][Download PDF]
Model Agreement via Anchoring
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5721-5742
[abs][Download PDF]
Convergence of Continual Learning in Homogeneous Deep Networks
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5743-5784
[abs][Download PDF]
The Hidden Cost of Approximation in Online Mirror Descent
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5785-5827
[abs][Download PDF]
Optimal Sample Complexity Lower Bounds on Conditional Independence Testing
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5828-5873
[abs][Download PDF]
Testing for a Hidden Geometry in Random Graphs
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5874-5927
[abs][Download PDF]
Finite Sample Bounds for Learning with Score Matching
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5928-5949
[abs][Download PDF]
Efficient Learning and Symmetry Discovery under Exact Invariances
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5980-6028
[abs][Download PDF]
Privately Estimating Black-Box Statistics
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6029-6074
[abs][Download PDF]
Truly Adapting to Adversarial Constraints in Constrained MABs
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6075-6113
[abs][Download PDF]
Data Augmentation: A Fourier Analysis Perspective
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6114-6155
[abs][Download PDF]
CONVERGENCE RATES FOR DISTRIBUTION MATCHING WITH SLICED OPTIMAL TRANSPORT
; 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
; 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
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6406-6409
[abs][Download PDF]
Spectral Recovery of a Planted Triangle-Dense Subgraph
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6458-6495
[abs][Download PDF]
The Geometry of Efficient Nonconvex Sampling
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6533-6591
[abs][Download PDF]
Fast Score-Based Sampling via Log-Concave Reductions
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6592-6621
[abs][Download PDF]
Almost sure null bankruptcy of testing-by-betting strategies
; 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
; 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
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6743-6810
[abs][Download PDF]
Minimax Limits of $k$-Fold Cross-Validation via Majority
; 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)
; 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)
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6858-6884
[abs][Download PDF]
Optimism Stabilizes Thompson Sampling for Adaptive Inference
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6885-6886
[abs][Download PDF]
Tight Sample Complexity of Transformers
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6887-6923
[abs][Download PDF]
Learning Decision-Sufficient Representations for Linear Optimization
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6924-6975
[abs][Download PDF]
Distribution-Free Sequential Prediction with Abstentions
; 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
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7012-7015
[abs][Download PDF]
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7016-7061
[abs][Download PDF]
Gradient-Variation Regret Bounds for Unconstrained Online Learning
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7062-7104
[abs][Download PDF]
Open Problems
Open Problem: How much overparametrization is needed for ALS in tensor decomposition?
; 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
; 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?
; 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?
; 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?
; Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7129-7135
[abs][Download PDF]
subscribe via RSS