![[The Thirty Seventh Annual Conference on Learning Theory Logo]](/v247/assets/images/logo-pmlr.svg){kind=logo}
[edit]
Volume 247: The Thirty Seventh Annual Conference on Learning Theory, 30-3 July 2023, Edmonton, Canada
[edit]
Editors: Shipra Agrawal, Aaron Roth
Preface
Conference on Learning Theory 2024: Preface
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:i-i
[abs][Download PDF]
Original Papers
Limits of Approximating the Median Treatment Effect
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1-21
[abs][Download PDF]
Majority-of-Three: The Simplest Optimal Learner?
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:22-45
[abs][Download PDF]
Metalearning with Very Few Samples Per Task
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:46-93
[abs][Download PDF]
A Unified Characterization of Private Learnability via Graph Theory
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:130-160
[abs][Download PDF]
Fast parallel sampling under isoperimetry
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:161-185
[abs][Download PDF]
Two fundamental limits for uncertainty quantification in predictive inference
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:186-218
[abs][Download PDF]
Mode Estimation with Partial Feedback
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:219-220
[abs][Download PDF]
Universally Instance-Optimal Mechanisms for Private Statistical Estimation
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:221-259
[abs][Download PDF]
Regularization and Optimal Multiclass Learning
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:359-405
[abs][Download PDF]
Learning Neural Networks with Sparse Activations
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:406-425
[abs][Download PDF]
The SMART approach to instance-optimal online learning
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:498-550
[abs][Download PDF]
Correlated Binomial Process
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:596-629
[abs][Download PDF]
Errors are Robustly Tamed in Cumulative Knowledge Processes
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:630-631
[abs][Download PDF]
Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:632-647
A Theory of Interpretable Approximations
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:648-668
[abs][Download PDF]
Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:669-696
[abs][Download PDF]
Online Stackelberg Optimization via Nonlinear Control
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:752-771
[abs][Download PDF]
The Price of Adaptivity in Stochastic Convex Optimization
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:772-774
[abs][Download PDF]
Information-theoretic generalization bounds for learning from quantum data
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:775-839
[abs][Download PDF]
Non-Clashing Teaching Maps for Balls in Graphs
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:840-875
[abs][Download PDF]
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:876-922
[abs][Download PDF]
Dual VC Dimension Obstructs Sample Compression by Embeddings
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:947-980
[abs][Download PDF]
A faster and simpler algorithm for learning shallow networks
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:981-994
[abs][Download PDF]
Near-Optimal Learning and Planning in Separated Latent MDPs
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:995-1067
[abs][Download PDF]
Scale-free Adversarial Reinforcement Learning
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1068-1101
[abs][Download PDF]
The power of an adversary in Glauber dynamics
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1102-1124
[abs][Download PDF]
Undetectable Watermarks for Language Models
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1125-1139
[abs][Download PDF]
Risk-Sensitive Online Algorithms (Extended Abstract)
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1200-1222
[abs][Download PDF]
Learnability Gaps of Strategic Classification
; 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)
; 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)
; 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"?
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1263-1307
[abs][Download PDF]
Testable Learning of General Halfspaces with Adversarial Label Noise
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1308-1335
[abs][Download PDF]
Statistical Query Lower Bounds for Learning Truncated Gaussians
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1336-1363
[abs][Download PDF]
Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1379-1398
[abs][Download PDF]
Physics-informed machine learning as a kernel method
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1451-1485
[abs][Download PDF]
An information-theoretic lower bound in time-uniform estimation
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1486-1500
[abs][Download PDF]
On sampling diluted Spin-Glasses using Glauber Dynamics
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1501-1515
[abs][Download PDF]
Minimax Linear Regression under the Quantile Risk
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1516-1572
[abs][Download PDF]
The Real Price of Bandit Information in Multiclass Classification
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1573-1598
[abs][Download PDF]
Topological Expressivity of ReLU Neural Networks
; 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)
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1643-1645
[abs][Download PDF]
Computation-information gap in high-dimensional clustering
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1646-1712
[abs][Download PDF]
Online Newton Method for Bandit Convex Optimisation Extended Abstract
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1715-1754
[abs][Download PDF]
Safe Linear Bandits over Unknown Polytopes
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1796-1881
[abs][Download PDF]
$(ε, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1882-1915
[abs][Download PDF]
On Convex Optimization with Semi-Sensitive Features
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1982-1982
[abs][Download PDF]
On Computationally Efficient Multi-Class Calibration
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2071-2091
[abs][Download PDF]
On the Computability of Robust PAC Learning
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2092-2121
[abs][Download PDF]
Principal eigenstate classical shadows
; 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
; 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
; 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
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2308-2359
[abs][Download PDF]
List Sample Compression and Uniform Convergence
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2360-2388
[abs][Download PDF]
Adversarially-Robust Inference on Trees via Belief Propagation
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2418-2437
[abs][Download PDF]
Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2494-2518
[abs][Download PDF]
Reconstructing the Geometry of Random Geometric Graphs (Extended Abstract)
; 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
; 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
; 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
; 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
; 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
; 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)
; 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
; 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)
; 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
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2840-2886
[abs][Download PDF]
Testable Learning with Distribution Shift
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2944-2978
[abs][Download PDF]
The title of the paper
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2979-3010
[abs][Download PDF]
Convergence of Kinetic Langevin Monte Carlo on Lie groups
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3011-3063
Active Learning with Simple Questions
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3064-3098
[abs][Download PDF]
Sampling from the Mean-Field Stationary Distribution
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3137-3240
[abs][Download PDF]
Simple online learning with consistent oracle
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3241-3256
[abs][Download PDF]
Accelerated Parameter-Free Stochastic Optimization
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3257-3324
[abs][Download PDF]
Better-than-KL PAC-Bayes Bounds
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3375-3430
[abs][Download PDF]
Minimax-optimal reward-agnostic exploration in reinforcement learning
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3431-3436
[abs][Download PDF]
Optimistic Rates for Learning from Label Proportions
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3437-3474
[abs][Download PDF]
Online Policy Optimization in Unknown Nonlinear Systems
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3523-3555
[abs][Download PDF]
Spatial properties of Bayesian unsupervised trees
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3642-3643
[abs][Download PDF]
Linear bandits with polylogarithmic minimax regret
; 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
; 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
; 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
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3823-3872
[abs][Download PDF]
Fundamental Limits of Non-Linear Low-Rank Matrix Estimation
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3873-3873
[abs][Download PDF]
Finding Super-spreaders in Network Cascades
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3874-3914
[abs][Download PDF]
Exact Mean Square Linear Stability Analysis for SGD
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3915-3969
[abs][Download PDF]
Optimistic Information Directed Sampling
; 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)
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4009-4081
[abs][Download PDF]
Depth Separation in Norm-Bounded Infinite-Width Neural Networks
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4115-4157
The complexity of approximate (coarse) correlated equilibrium for incomplete information games
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4158-4184
[abs][Download PDF]
The sample complexity of multi-distribution learning
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4185-4204
[abs][Download PDF]
The Sample Complexity of Simple Binary Hypothesis Testing
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4240-4275
[abs][Download PDF]
Dimension-free Structured Covariance Estimation
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4276-4306
[abs][Download PDF]
On the Distance from Calibration in Sequential Prediction
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4307-4357
[abs][Download PDF]
Apple Tasting: Combinatorial Dimensions and Minimax Rates
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4358-4380
[abs][Download PDF]
Online Learning with Set-valued Feedback
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4458-4486
[abs][Download PDF]
Provable Advantage in Quantum PAC Learning
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4511-4547
[abs][Download PDF]
Adversarial Online Learning with Temporal Feedback Graphs
; 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)
; 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
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4636-4690
[abs][Download PDF]
Second Order Methods for Bandit Optimization and Control
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4691-4763
[abs][Download PDF]
Improved Hardness Results for Learning Intersections of Halfspaces
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4787-4861
[abs][Download PDF]
Nearly Optimal Regret for Decentralized Online Convex Optimization
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4891-4957
[abs][Download PDF]
Optimal score estimation via empirical Bayes smoothing
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4958-4991
[abs][Download PDF]
Oracle-Efficient Hybrid Online Learning with Unknown Distribution
; 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
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5076-5122
[abs][Download PDF]
Top-$K$ ranking with a monotone adversary
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5166-5212
[abs][Download PDF]
Settling the sample complexity of online reinforcement learning
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5213-5219
[abs][Download PDF]
Optimal Multi-Distribution Learning
; 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)
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5224-5230
[abs][Download PDF]
Gap-Free Clustering: Sensitivity and Robustness of SDP
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5231-5300
[abs][Download PDF]
Open Problems
Open Problem: Can Local Regularization Learn All Multiclass Problems?
; 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?
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5306-5311
[abs][Download PDF]
Open Problem: Tight Characterization of Instance-Optimal Identity Testing
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5317-5324
[abs][Download PDF]
Open problem: Direct Sums in Learning Theory
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5330-5334
[abs][Download PDF]
Open Problem: Anytime Convergence Rate of Gradient Descent
; 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
; 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
; Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5345-5350
[abs][Download PDF]
subscribe via RSS