![[Conference on Learning Theory Logo]](/v125/assets/images/logo-pmlr.svg){kind=logo}
[edit]
Volume 125: Conference on Learning Theory, 9-12 July 2020,
[edit]
Editors: Jacob Abernethy, Shivani Agarwal
Conference on Learning Theory 2020: Preface
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1-2
[abs][Download PDF]
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3-40
[abs][Download PDF]
Distributed Signal Detection under Communication Constraints
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:41-63
[abs][Download PDF]
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:64-66
[abs][Download PDF]
Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:67-83
[abs][Download PDF]
From Nesterov’s Estimate Sequence to Riemannian Acceleration
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:84-118
[abs][Download PDF]
Closure Properties for Private Classification and Online Prediction
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:119-152
[abs][Download PDF]
Hierarchical Clustering: A 0.585 Revenue Approximation
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:153-162
[abs][Download PDF]
Winnowing with Gradient Descent
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:163-182
[abs][Download PDF]
Pan-Private Uniformity Testing
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:183-218
[abs][Download PDF]
Dimension-Free Bounds for Chasing Convex Functions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:219-241
[abs][Download PDF]
Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:242-299
[abs][Download PDF]
Data-driven confidence bands for distributed nonparametric regression
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:300-322
[abs][Download PDF]
Estimating Principal Components under Adversarial Perturbations
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:323-362
[abs][Download PDF]
Active Local Learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:363-390
[abs][Download PDF]
Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:391-407
[abs][Download PDF]
Calibrated Surrogate Losses for Adversarially Robust Classification
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:408-451
[abs][Download PDF]
Complexity Guarantees for Polyak Steps with Momentum
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:452-478
[abs][Download PDF]
Free Energy Wells and Overlap Gap Property in Sparse PCA
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:479-482
[abs][Download PDF]
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:483-513
[abs][Download PDF]
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:514-529
[abs][Download PDF]
Selfish Robustness and Equilibria in Multi-Player Bandits
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:530-581
[abs][Download PDF]
Proper Learning, Helly Number, and an Optimal SVM Bound
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:582-609
[abs][Download PDF]
Sharper Bounds for Uniformly Stable Algorithms
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:610-626
[abs][Download PDF]
The Gradient Complexity of Linear Regression
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:627-647
[abs][Download PDF]
Reducibility and Statistical-Computational Gaps from Secret Leakage
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:648-847
[abs][Download PDF]
A Corrective View of Neural Networks: Representation, Memorization and Learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:848-901
[abs][Download PDF]
ID3 Learns Juntas for Smoothed Product Distributions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:902-915
[abs][Download PDF]
Coordination without communication: optimal regret in two players multi-armed bandits
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:916-939
[abs][Download PDF]
How to Trap a Gradient Flow
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:940-960
[abs][Download PDF]
Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:961-987
[abs][Download PDF]
Highly smooth minimization of non-smooth problems
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:988-1030
[abs][Download PDF]
Efficient, Noise-Tolerant, and Private Learning via Boosting
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1031-1077
[abs][Download PDF]
The estimation error of general first order methods
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1078-1141
[abs][Download PDF]
Bounds in query learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1142-1160
[abs][Download PDF]
Learning Polynomials in Few Relevant Dimensions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1161-1227
[abs][Download PDF]
The Influence of Shape Constraints on the Thresholding Bandit Problem
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1228-1275
[abs][Download PDF]
Gradient descent algorithms for Bures-Wasserstein barycenters
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1276-1304
[abs][Download PDF]
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1305-1338
[abs][Download PDF]
ODE-Inspired Analysis for the Biological Version of Oja’s Rule in Solving Streaming PCA
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1339-1343
[abs][Download PDF]
Pessimism About Unknown Unknowns Inspires Conservatism
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1344-1373
[abs][Download PDF]
Optimal Group Testing
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1374-1388
[abs][Download PDF]
PAC learning with stable and private predictions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1389-1410
[abs][Download PDF]
High probability guarantees for stochastic convex optimization
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1411-1427
[abs][Download PDF]
Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1428-1451
[abs][Download PDF]
Approximation Schemes for ReLU Regression
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1452-1485
[abs][Download PDF]
Learning Halfspaces with Massart Noise Under Structured Distributions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1486-1513
[abs][Download PDF]
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1514-1539
[abs][Download PDF]
Consistent recovery threshold of hidden nearest neighbor graphs
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1540-1553
[abs][Download PDF]
Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1554-1557
[abs][Download PDF]
Embedding Dimension of Polyhedral Losses
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1558-1585
[abs][Download PDF]
Efficient Parameter Estimation of Truncated Boolean Product Distributions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1586-1600
[abs][Download PDF]
Rigorous Guarantees for Tyler’s M-Estimator via Quantum Expansion
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1601-1632
[abs][Download PDF]
From tree matching to sparse graph alignment
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1633-1665
[abs][Download PDF]
On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1666-1681
[abs][Download PDF]
Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1682-1713
[abs][Download PDF]
No-Regret Prediction in Marginally Stable Systems
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1714-1757
[abs][Download PDF]
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1758-1784
[abs][Download PDF]
Locally Private Hypothesis Selection
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1785-1816
[abs][Download PDF]
Bessel Smoothing and Multi-Distribution Property Estimation
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1817-1876
[abs][Download PDF]
Faster Projection-free Online Learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1877-1893
[abs][Download PDF]
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1894-1938
[abs][Download PDF]
A Greedy Anytime Algorithm for Sparse PCA
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1939-1956
[abs][Download PDF]
Noise-tolerant, Reliable Active Classification with Comparison Queries
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1957-2006
[abs][Download PDF]
Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2007-2010
[abs][Download PDF]
Extrapolating the profile of a finite population
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2011-2033
[abs][Download PDF]
Precise Tradeoffs in Adversarial Training for Linear Regression
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2034-2078
[abs][Download PDF]
Robust causal inference under covariate shift via worst-case subpopulation treatment effects
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2079-2084
[abs][Download PDF]
Efficient improper learning for online logistic regression
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2085-2108
[abs][Download PDF]
Gradient descent follows the regularization path for general losses
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2109-2136
[abs][Download PDF]
Provably efficient reinforcement learning with linear function approximation
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2137-2143
[abs][Download PDF]
Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2144-2203
[abs][Download PDF]
Private Mean Estimation of Heavy-Tailed Distributions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2204-2235
[abs][Download PDF]
Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2236-2262
[abs][Download PDF]
Privately Learning Thresholds: Closing the Exponential Gap
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2263-2285
[abs][Download PDF]
Online Learning with Vector Costs and Bandits with Knapsacks
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2286-2305
[abs][Download PDF]
Universal Approximation with Deep Narrow Networks
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2306-2327
[abs][Download PDF]
Information Directed Sampling for Linear Partial Monitoring
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2328-2369
[abs][Download PDF]
New Potential-Based Bounds for Prediction with Expert Advice
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2370-2405
[abs][Download PDF]
On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2406-2424
[abs][Download PDF]
The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2425-2487
[abs][Download PDF]
Exploration by Optimisation in Partial Monitoring
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2488-2515
[abs][Download PDF]
A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2516-2564
[abs][Download PDF]
Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2565-2597
[abs][Download PDF]
A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2598-2612
Learning Over-Parametrized Two-Layer Neural Networks beyond NTK
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2613-2682
[abs][Download PDF]
On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2683-2711
[abs][Download PDF]
Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2712-2737
[abs][Download PDF]
Near-Optimal Algorithms for Minimax Optimization
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2738-2779
[abs][Download PDF]
Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2780-2829
[abs][Download PDF]
Tight Lower Bounds for Combinatorial Multi-Armed Bandits
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2830-2857
[abs][Download PDF]
Lipschitz and Comparator-Norm Adaptivity in Online Learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2858-2887
[abs][Download PDF]
Information Theoretic Optimal Learning of Gaussian Graphical Models
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2888-2909
[abs][Download PDF]
Parallels Between Phase Transitions and Circuit Complexity?
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2910-2946
[abs][Download PDF]
On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2947-2997
[abs][Download PDF]
Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2998-3029
[abs][Download PDF]
Fast Rates for Online Prediction with Abstention
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3030-3048
[abs][Download PDF]
Efficient and robust algorithms for adversarial linear contextual bandits
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3049-3068
[abs][Download PDF]
An $\widetilde\mathcal{O}(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3069-3119
[abs][Download PDF]
Costly Zero Order Oracles
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3120-3132
[abs][Download PDF]
Adaptive Submodular Maximization under Stochastic Item Costs
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3133-3151
[abs][Download PDF]
Covariance-adapting algorithm for semi-bandits with application to sparse outcomes
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3152-3184
[abs][Download PDF]
Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3185-3205
[abs][Download PDF]
List Decodable Subspace Recovery
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3206-3226
[abs][Download PDF]
Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3227-3249
[abs][Download PDF]
How Good is SGD with Random Shuffling?
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3250-3284
[abs][Download PDF]
A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3285-3295
[abs][Download PDF]
Logistic Regression Regret: What’s the Catch?
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3296-3319
[abs][Download PDF]
Improper Learning for Non-Stochastic Control
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3320-3436
[abs][Download PDF]
Reasoning About Generalization via Conditional Mutual Information
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3437-3452
[abs][Download PDF]
Estimation and Inference with Trees and Forests in High Dimensions
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3453-3454
[abs][Download PDF]
Balancing Gaussian vectors in high dimension
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3455-3486
[abs][Download PDF]
Active Learning for Identification of Linear Dynamical Systems
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3487-3582
[abs][Download PDF]
Taking a hint: How to leverage loss predictors in contextual bandits?
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3583-3634
[abs][Download PDF]
Kernel and Rich Regimes in Overparametrized Models
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3635-3673
[abs][Download PDF]
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3674-3682
[abs][Download PDF]
Tree-projected gradient descent for estimating gradient-sparse parameters on graphs
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3683-3708
[abs][Download PDF]
Non-asymptotic Analysis for Nonparametric Testing
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3709-3755
[abs][Download PDF]
Learning a Single Neuron with Gradient Methods
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3756-3786
[abs][Download PDF]
Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3787-3813
[abs][Download PDF]
Wasserstein Control of Mirror Langevin Monte Carlo
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3814-3841
[abs][Download PDF]
Open Problem: Model Selection for Contextual Bandits
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3842-3846
[abs][Download PDF]
Open Problem: Tight Convergence of SGD in Constant Dimension
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3847-3851
[abs][Download PDF]
Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3852-3856
[abs][Download PDF]
Open Problem: Information Complexity of VC Learning
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3857-3863
[abs][Download PDF]
Open Problem: Fast and Optimal Online Portfolio Selection
; Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3864-3869
[abs][Download PDF]
subscribe via RSS