Optimal Sample Complexity

Follow this topic Ask about this topic

Recent momentum

-45%

16 papers in the last 28 days · 0.3% of indexed attention

Twelve weeks of publication activity for this topic as it is defined today.

Weekly history

Recent digests

What was published in this topic, kept on the site without email delivery.

Period ending 2026-09-21

8 new papers

A weekly snapshot of new work published in Optimal Sample Complexity.

Period ending 2026-09-14

7 new papers

A weekly snapshot of new work published in Optimal Sample Complexity.

Period ending 2026-09-07

4 new papers

A weekly snapshot of new work published in Optimal Sample Complexity.

210 papers

Latest in Optimal Sample Complexity

Browse all topics →

Beyond the $d^{2.5}$ -mixing bound for Dikin walks on polytopes
Jul 15, 2026Yunbum KookPolytopes Optimal Sample Complexity
From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
Jul 13, 2026Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau +1Transformer Architectures Sample Complexity
Efficient Online Proportional Sampling with Applications to Smoothed Online Learning
Jul 13, 2026Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh BeyhaghiLearning-Augmented Algorithms Optimal Sample Complexity
Optimal Top- $k$ Identification from Pairwise Comparisons
Jul 9, 2026Motti Goldberger, Nils RudiOptimal Sample Complexity Top-K
High-Dimensional Procrustes Matching via Tree Counts
Jul 9, 2026Xiaochun Niu, Tselil Schramm, Jiaming XuHigh-Dimensional Data Feature Matching
Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
Jul 9, 2026Weiming Feng, Xiongxin Yang, Yixiao Yu +1Optimal Sample Complexity Singular Learning Theory
Near-Optimal Learning of Gaussian Sobolev Operators
Jul 8, 2026Ben Adcock, Michael Griebel, Gregor MaierLogarithmic Sobolev Inequalities Probabilistic Operator Learning
Distributed Sketching on Data Partitions for OLS Regression
Jul 8, 2026Luyuan Yang, Brayden Garner, Shayan Shafaei +1Least Squares Partitioning
The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
Jul 8, 2026Zhiyuan LiOptimal Sample Complexity Sample Complexity
Is Randomness Necessary for Adaptive Data Analysis?
Jul 8, 2026Edith Cohen, Haim Kaplan, Yishay Mansour +2Optimal Sample Complexity Data Collection
Fast determinantal sampling on general spaces and diffusion geometry
Jul 7, 2026Hoang-Son Tran, Pranav Gupta, Subhroshekhar GhoshDeterminantal Point Process Optimal Sample Complexity
Active Learning on Adversarially Corrupted Graphs
Jul 6, 2026Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi +2Graph Theory Active Learning
Selectivity Estimation for Linear Queries via Online Learning
Jul 3, 2026Fangzhu Shen, Debmalya Panigrahi, Sudeepa RoyLearning-Augmented Algorithms Selectivity
From Spectral Methods to Sample Complexity Bounds for Fourier Neural Operators
Jul 1, 2026Nisha Chandramoorthy, Daniel Sanz-Alonso, Nathan WaniorekFourier Neural Operators Neural Operators
Distributionally Robust Linear Regression With Block Lewis Weights
Jun 30, 2026Naren Sarayu Manoj, Kumar Kshitij PatelLeast Squares Proximal Gradient Descent
Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing
Jun 30, 2026Eric Shen, Tony Wu, Mahbod Majid +1Conditional Independence Temporal Dependence
Behavior Cloning is Not All You Need: The Optimality of On-Policy Distillation for Noisy Expert Feedback
Jun 29, 2026Ved Sriraman, Peihan Liu, Daniel Hsu +1On-Policy Distillation Imitation Learning
Adjusted Wasserstein distances for bridging empirical and true distributions with applications to MDS
Jun 29, 2026Flor Martinez-Sermeno, Arturo Jaramillo, Johan Van HorebeekWasserstein Distance Optimal Sample Complexity
Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
Jun 26, 2026Andrea Montanari, Kangjie ZhouEmpirical Risk Minimization Optimal Sample Complexity
Surprises in Proper Positive-Only Learning
Jun 26, 2026Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1Binary Classification Optimal Sample Complexity
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
Jun 25, 2026Haitong Liu, Deepak Narayanan Sridharan, David Steurer +1Optimal Sample Complexity Gaussian Mixture Models
Sketched Linear Contrastive Learning: Approximation, Optimization, and Statistical Scaling
Jun 25, 2026Ziyan Chen, Zhongzhu Zhou, Ding-Xuan ZhouContrastive Learning Scaling Laws
Space-Efficient Language Generation in the Limit
Jun 24, 2026Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2Context-Free Grammars Data Generation
Sample complexity of unbalanced entropic OT
Jun 23, 2026Francisco Andrade, Gabriel Peyré, Clarice PoonEntropy-Regularized Equilibrium Selection Optimal Sample Complexity
Uniform Sampling from High-dimensional Spectral Norm Balls
Jun 23, 2026Michael R. MetelSpectral Norm Singular Value Decomposition
Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling
Jun 22, 2026Trenton Lau, Gary P. T. ChoiMaximum Likelihood Optimal Sample Complexity
Diffusion Models Adapt to Low-Dimensional Structure Under Flexible Coefficient Choices
Jun 22, 2026Changxiao Cai, Yuchen Jiao, Gen LiDiffusion Sampling Low-Dimensional Structure
On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
Jun 20, 2026Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar +1Differential Privacy Principal Component Analysis
Breaking chains with trees: Deep learning with $\mathcal{O}(\log N)$ parallel time complexity
Jun 19, 2026Neeraj Mohan Sushma, Aditya Nagarsekar, Cabrel Teguemne Fokam +4Backpropagation Neural Architectures
Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation
Jun 19, 2026Jianwei LouLearning-Augmented Algorithms Cold-Start
Optimal Deterministic Multicalibration and Omniprediction
Jun 18, 2026Georgy Noarov, Aaron RothMulticalibration and Calibration Optimal Sample Complexity
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
Jun 18, 2026Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2Optimal Sample Complexity Polytopes
Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Jun 15, 2026Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1Optimal Sample Complexity Sample Complexity
Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
Jun 15, 2026Jongmin Lee, Ernest K. Ryu, Vaneet AggarwalMarkov Decision Processes Model-Free Reinforcement Learning
Active Learning with Low-Rank Structure for Data Selection
Jun 14, 2026Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni +3Geometry-Aware Uncertainty Coresets Low-Rank Factorization
Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model
Jun 13, 2026Siyu Chen, Beining Wu, Miao Lu +2Optimal Sample Complexity Two-Layer Neural Networks
A Complexity Measure for Active Learning in Multi-group Mean Estimation
Jun 12, 2026Abdellah Aznag, Rachel Cummings, Adam N. ElmachtoubActive Learning Optimal Sample Complexity
Online Convex Optimization with Sublinear Noisy Probes
Jun 12, 2026Simone Di Gregorio, Anupam Gupta, Stefano Leonardi +1O(T^Β)$ Simultaneous Regret Convex Optimization
Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success
Jun 12, 2026Florian Hübler, Thomas Pethick, Suvrit SraSpectral Norm Muon Optimizer
A solvable model for unsupervised federated learning
Jun 11, 2026Giovanni Catania, Aurélien Decelle, Gianluca Manzan +2Federated Learning Distributional Learning
Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning
Jun 10, 2026Jeongho Bang, Kyoungho Cho, Jeongwoo JaeQuantum Machine Learning Optimal Sample Complexity
Efficient Multinomial Logistic Bandit via Frequent Directions
Jun 10, 2026Linzhe He, Yu-Jie Zhang, Sifan Yang +1Generalized Linear Bandit Semiparametric Framework
Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more
Jun 9, 2026Spencer Compton, Jerry LiDensity Ratio Estimation Optimal Sample Complexity
The Power of Test-Time Training for Approximate Sampling
Jun 9, 2026Noah Golowich, Ankur Moitra, Dhruv RohatgiOptimal Sample Complexity Inference-Time
Bellman-sufficient Information Complexity
Jun 9, 2026Yunbei XuInformation-Theoretic Limits Optimal Sample Complexity
Efficiently Learning Drifting Halfspaces with Massart Noise
Jun 9, 2026Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1Optimal Sample Complexity Learning-Augmented Algorithms
Robust Regression of General ReLUs with Queries
Jun 9, 2026Ilias Diakonikolas, Daniel M. Kane, Mingchen MaRectified Linear Unit Optimal Sample Complexity
Tight Sample Complexity of Transformers
Jun 8, 2026Chenxiao Yang, Nathan Srebro, Zhiyuan LiTransformer Architectures Sample Complexity
Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming
Jun 7, 2026Siddharth Prasad, Dravyansh SharmaHyperparameter Optimization Primal-Dual Methods
The Sharp Phase Transition of Tyler's M-Estimator for Robust Subspace Recovery
Jun 4, 2026Gilad Lerman, Teng ZhangSparse Recovery Estimators
Provably Reduced Sample Cost in Prior-Guided Hyperparameter Optimization
Jun 3, 2026Leona Hennig, Jasmin Brandt, Lukas Fehring +3Hyperparameter Optimization Optimal Sample Complexity
The price of multi-group transductive learning
Jun 3, 2026Noah Bergam, Samuel Deng, Daniel HsuTransductive Active Labeling Multiclass Classification
A Biconvex Formulation for Stable Transport of Mixture Models with a Unique Solution
Jun 1, 2026Yeganeh Marghi, Kelly Jin, Uygar SümbülOptimal Transport Mixture Models
Query-Limited Community Recovery in Stochastic Block Models
Jun 1, 2026Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen +1Optimal Sample Complexity Subgraphs
Provable Data Scaling Law for Meta Learning via Complexity Minimization
Jun 1, 2026Kazuto Fukuchi, Ryuichiro Hataya, Kota MatsuiMeta-Learning Model Pretraining
Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses
Jun 1, 2026Matthew Regehr, Gautam Kamath, Andrew LowyMachine Unlearning Several Approximate Unlearning Strategies
Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learning
May 31, 2026Tehila Dahan, Bassel Hamoud, Roie Reshef +2Distributional Learning Mini-Batch Stochastic Gradient Descent
Approximation and learning of anisotropic and mixed smooth functions by deep ReLU neural networks
May 29, 2026Yunfei Yang, Jun FanLogarithmic Sobolev Inequalities Neural-Network Approximation
Universal Multiclass Transductive Online Learning
May 28, 2026Steve Hanneke, Hongao WangTransductive Active Labeling Learning-Augmented Algorithms
Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions
May 28, 2026Jingda Wu, Changxiao CaiLow-Dimensional Structure Score-Based Diffusion Model

Jul 15, 2026 · cs.DSJ/K move · Enter open · S save

Beyond the $d^{2.5}$ -mixing bound for Dikin walks on polytopes

Yunbum Kook

Georgia Tech

Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPMs, the Dikin walk is affine-invariant, and its convergence is governed by the barrier geometry used to define its local proposal. They showed that the Dikin walk with the logarithmic barrier for a polytope in

\mathbb{R}^{d}

with

m

linear inequalities mixes in

md

iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved this to

d^{2.5}

using a Lewis-weight barrier, and conjectured that the correct mixing time should be

d^{2}

. We make progress toward this conjecture by improving the previous

d^{2.5}

-mixing bound. For exponential sampling over a polytope, we prove that the Dikin walk with a scaled Lee--Sidford metric mixes from a warm start in

d^{2.25}

iterations. This also yields an improved cold-start complexity via a known annealing framework. The main technical ingredient is improved average self-concordance of the Lee--Sidford metric, which gives high acceptance probability for the Metropolis filter along a random Dikin proposal. While previous analyses were effectively limited to second-order control due to technical difficulties, we develop a principled higher-order analysis. The proof combines a selective higher-order expansion of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives of the Lewis weights, and Wiener-chaos decompositions via multiple stochastic integrals to control the resulting Gaussian polynomials.

Polytopes Optimal Sample Complexity Random

Open paper Ask about it PDF

Recent momentum

Neighbouring directions

Recent digests

8 new papers

7 new papers

4 new papers

Latest in Optimal Sample Complexity