Learning Theory

AdaBoost Always Cycles? (Global Dynamics Conjecture)

Posed by Rudin, Daubechies, and Schapire (2004)

Tight PAC-Bayes Bounds for Deep Neural Networks

Optimal Distribution-Free Prediction Intervals

Online Conformal Prediction Beyond Symmetric Intervals and Toward Conditional Validity

Posed by Liu, Dobriban, and Orabona (2026)

Decision-Optimal Prediction Sets with Group/Label-Conditional Guarantees

Posed by Wang and Dobriban (2026)

Multiple Risk Control Beyond Sequential Order: Graph-Structured Dependencies

Posed by Joshi, Sun, Hassani, and Dobriban (2025)

Computational Threshold for Tensor PCA

Posed by Richard & Montanari (2014)

Sharp minimax rate for central-space estimation in the low-signal SIR regime

Sourced from the work of Dongming Huang, Songtao Tian, Qian Lin

Universality of exponential decay of the $d$-th SIR eigenvalue

Sourced from the work of Dongming Huang, Songtao Tian, Qian Lin

Remove the Polylogarithmic Gap to Exact Minimax Optimality

Sourced from the work of Kaizheng Wang

Local-asymptotic limit law with unknown diffusivity levels under vanishing jump

Sourced from the work of Markus Reiß, Claudia Strauch, Lukas Trottner

Multiple change-point inference for piecewise constant diffusivity

Sourced from the work of Markus Reiß, Claudia Strauch, Lukas Trottner

Higher-dimensional change-set (interface) estimation for discontinuous diffusivity

Sourced from the work of Markus Reiß, Claudia Strauch, Lukas Trottner

Rigorous tempered-overfitting guarantees for MDL ReLU interpolators under label noise

Sourced from the work of Sourav Chatterjee, Timothy Sudijono

Does the score-matched optimal convex estimator attain the full semiparametric efficiency bound?

Sourced from the work of Oliver Y. Feng, Yu-Chun Kao, Min Xu, Richard J. Samworth

Quantify and characterize the efficiency gap induced by convex-loss restriction for non-log-concave errors

Sourced from the work of Oliver Y. Feng, Yu-Chun Kao, Min Xu, Richard J. Samworth

Finite-sample error-rate control and power guarantees under the linear subspace model

Sourced from the work of Amitay Eldar, Keren Mor Waknin, Samuel Davenport, Tamir Bendory, Armin Schwartzman, Yoel Shkolnisky

Complete Generic Identifiability in Cyclic LiNGAM with General Confounding

Sourced from the work of Daniele Tramontano, Jalal Etesami, Mathias Drton

Full Causal Graph Recovery Under Arbitrary Nonlinear Latent Confounding

Sourced from the work of Daniele Tramontano, Jalal Etesami, Mathias Drton

Provable Estimation Procedures Under the New Identifiability Criterion

Sourced from the work of Daniele Tramontano, Mathias Drton, Jalal Etesami

State evolution for gradient descent beyond the mean-field scaling

Sourced from the work of Qiyang Han, Xiaocong Xu

Sharp characterization of misspecification robustness for debiased GD inference

Sourced from the work of Qiyang Han, Xiaocong Xu

Log-factor-free adaptive contraction on general Minkowski-dimensional domains

Sourced from the work of Tao Tang, Nan Wu, Xiuyuan Cheng, David Dunson

Optimal adaptation beyond compact manifolds

Sourced from the work of Tao Tang, Nan Wu, Xiuyuan Cheng, David Dunson

Generalization-error estimation beyond Gaussian designs

Sourced from the work of Pierre C Bellec, Kai Tan

Early-stopping optimality without a U-shape risk assumption

Sourced from the work of Pierre C Bellec, Kai Tan

Machine-learning debiased efficient estimation under generalized data-fusion alignments

Sourced from the work of Ellen Sandra Graham, Marco Carone, Andrea Rotnitzky

Beyond smooth finite-dimensional targets in unified semiparametric data fusion

Sourced from the work of Ellen Sandra Graham, Marco Carone, Andrea Rotnitzky

Polynomial-time warm initialization at statistically optimal thresholds

Sourced from the work of Wanteng Ma, Dong Xia

Sharp computational lower bounds for valid inference in the intermediate regime

Sourced from the work of Wanteng Ma, Dong Xia

General-rank intrinsic Cramér–Rao lower bound on Tucker manifolds

Sourced from the work of Wanteng Ma, Dong Xia

Fixed-Parameter Tractability of Zonotope Problems

Posed by Vincent Froese et al. (2025)

Structure-Agnostic Minimax Risk for Partial Linear Model

Posed by Yihong Gu (2025)

Data Selection for Regression Tasks

Posed by Steve Hanneke et al. (2025)

Optimal Instance-Dependent Sample Complexity for finding Nash Equilibrium in Two Player Zero-Sum Matrix games

Posed by Arnab Maiti (2025)

Regret Minimization in Heavy-Tailed Bandits with Unknown Distributional Parameters

Posed by Gianmarco Genalti et al. (2025)

Can Local Regularization Learn All Multiclass Problems?

Posed by Julian Asilis et al. (2024)

What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?

Posed by Achraf Azize et al. (2024)

Tight Characterization of Instance-Optimal Identity Testing

Posed by Clément Canonne (2024)

Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization

Posed by Xinyi Chen et al. (2024)

Direct Sums in Learning Theory

Posed by Steve Hanneke et al. (2024)

Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy

Posed by Bingshan Hu et al. (2024)

Anytime Convergence Rate of Gradient Descent

Posed by Guy Kornowski et al. (2024)

Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning

Posed by Sattar Vakili (2024)

Convergence of single-timescale mean-field Langevin descent-ascent for two-player zero-sum games

Posed by Guillaume Wang et al. (2024)

log(n) factor in "Local Glivenko-Cantelli"

Posed by Doron Cohen et al. (2023)

Learning sparse linear concepts by priming the features

Posed by Manfred K. Warmuth et al. (2023)

The Sample Complexity of Multi-Distribution Learning for VC Classes

Posed by Pranjal Awasthi et al. (2023)

Polynomial linearly-convergent method for g-convex optimization?

Posed by Christopher Criscitiello et al. (2023)

Is There a First-Order Method that Only Converges to Local Minimax Optima?

Posed by Jiseok Chae et al. (2023)

Properly learning decision trees in polynomial time?

Posed by Guy Blanc et al. (2022)

Regret Bounds for Noise-Free Kernel-Based Bandits

Posed by Sattar Vakili (2022)

Running time complexity of accelerated $\ell_1$-regularized PageRank

Posed by Kimon Fountoulakis et al. (2022)

Do you pay for Privacy in Online learning?

Posed by Amartya Sanyal et al. (2022)

Better Differentially Private Learning Algorithms with Margin Guarantees

Posed by Raef Bassily et al. (2022)

Finite-Time Instance Dependent Optimality for Stochastic Online Learning with Feedback Graphs

Posed by Teodor Vanislavov Marinov et al. (2022)

Optimal Best Arm Identification with Fixed-Budget

Posed by Chao Qin (2022)

Are all VC-classes CPAC learnable?

Posed by Sushant Agarwal et al. (2021)

Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?

Posed by Steve Hanneke (2021)

Tight Online Confidence Intervals for RKHS Elements

Posed by Sattar Vakili et al. (2021)

Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?

Posed by Chulhee Yun et al. (2021)

Model Selection for Contextual Bandits

Posed by Dylan J. Foster et al. (2020)

Tight Convergence of SGD in Constant Dimension

Posed by Tomer Koren et al. (2020)

Average-Case Hardness of Hypergraphic Planted Clique Detection

Posed by Yuetian Luo et al. (2020)

Information Complexity of VC Learning

Posed by Thomas Steinke et al. (2020)

Fast and Optimal Online Portfolio Selection

Posed by Tim Van Erven et al. (2020)

Is Margin Sufficient for Non-Interactive Private Distributed Learning?

Posed by Amit Daniely et al. (2019)

How fast can a multiclass test set be overfit?

Posed by Vitaly Feldman et al. (2019)

Do Good Algorithms Necessarily Query Bad Points?

Posed by Rong Ge et al. (2019)

Risk of Ruin in Multiarmed Bandits

Posed by Filipo S. Perotto et al. (2019)

Monotonicity of Learning

Posed by Tom Viering et al. (2019)

The Oracle Complexity of Convex Optimization with Limited Memory

Posed by Blake Woodworth et al. (2019)

The Dependence of Sample Complexity Lower Bounds on Planning Horizon

Posed by Nan Jiang et al. (2018)

Improper learning of mixtures of Gaussians

Posed by Elad Hazan et al. (2018)