Optimal Sample Complexity

Ask about this topic

Momentum

22 papers in the last four weeks, up 450% on the four weeks before. 0.2% of all new papers.

Jul 13Week of Sep 28
View on map

Latest papers 161

All topics
CardsList

  1. Sharp dimensional analysis of midpoint methods for Langevin sampling

    Oct 5, 2026Fan Chen, Sinho Chewi, Jianfeng Lu +1Langevin DynamicsLarge Deviation Principle

    Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. · Department of Statistics and Data Science, Yale University. · Department of Mathematics, Duke University. +1

  2. Two-Point Local Optimality in kk-Means via Boundary-Point Screening

    Oct 5, 2026Wenlong Lyu, Xujie Xiao, Yuheng JiaK-MeansOptimal Sample Complexity

    School of Computer Science and Engineering Southeast University Nanjing, Jiangsu 211189, China

  3. Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization

    Oct 5, 2026Yuanyu Wan, Lan Xue, Haomin Bai +2Stochastic Convex OptimizationOptimal Sample Complexity

    School of Software Technology, Zhejiang University · State Key Laboratory of Blockchain and Security, Zhejiang University · School of Artificial Intelligence, Nanjing University +1

  4. Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

    Oct 1, 2026Shivam Kumar, Nabarun DebScore-Based Diffusion ModelMarkov

    Booth School of Business, University of Chicago

  5. Sharp Non-Asymptotic Analysis of the Penalized Challenger in ββ-EB-TCI for Bernoulli Bandits

    Oct 1, 2026Nam Nguyen, Tuan Quang DamOptimal Sample ComplexityBest-Of-N

    Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam

  6. Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability

    Oct 1, 2026Haodong Wen, Kaiyue Wen, Jiaye TengLogistic RegressionOptimal Sample Complexity

    Stanford University · Shanghai University of Finance and Economics

  7. Low-Budget Active Learning through Entropic Optimal Transport

    Oct 1, 2026Rim Hajal, Mathieu Besançon, Jérôme MalickPool-Based Active LearningOptimal Sample Complexity

    Univ. Grenoble Alpes, CNRS, Inria, LIG, LJK · Univ. Grenoble Alpes, Inria, CNRS, LIG · Univ. Grenoble Alpes, CNRS, LJK

  8. Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory

    Sep 30, 2026Xiaomian Yang, Sungho ShinOptimal Sample ComplexityLeast Squares

    Department of Chemical Engineering Massachusetts Institute of Technology Cambridge, MA 02139

  9. Efficient Active Auditing of Multi-Group Fairness with Bias Probes

    Sep 30, 2026Ayoub Ajarra, Debabrota BasuFairness AuditsAlgorithmic Fairness

    ´Equipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRIStAL

  10. Can Domain Generalization be Guaranteed in Small-Sample Learning?

    Sep 30, 2026Hong ZhengMultimodal Domain GeneralizationGeneralization Bounds

    This work was completed during my Ph.D. period and was the result of a flash of inspiration. I decided to submit it to arXiv and leave its value to the readers.

  11. How Many Samples Are Enough for Learning Across Domains?

    Sep 30, 2026Hong ZhengMultimodal Domain GeneralizationGeneralization Bounds

    This work was completed during my Ph.D. period and was the result of a flash of inspiration. I decided to submit it to arXiv and leave its value to the readers.

  12. Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

    Sep 30, 2026Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng XiongMirror DescentImperfect-Information Games

    Department of Computer Sciences, University of Wisconsin-Madison

  13. Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral LrL_r Norms

    Sep 27, 2026Soham DanInhomogeneous Random GraphsTwo-Sample Testing

  14. Geometry-Adaptive Mechanisms for Private Synthetic Data

    Sep 27, 2026Raoof Zare Moayedi, Amir R. Asadi, Mohammad Hossein Yassaee +1Synthetic DataWasserstein Distance

    Sharif University of Technology · University of Birmingham · The Alan Turing Institute

  15. Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy

    Sep 22, 2026Anming Gu, Syamantak Kumar, Kevin Tian +1Principal Component AnalysisOptimal Sample Complexity

    University of Texas at Austin

  16. Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis

    Sep 22, 2026Jun LI, Yanlong Guo, Zhaozhao ZengSimplexOptimal Sample Complexity

    School of Computer Science, China University of Geosciences

  17. Revisiting Distributed Sign-Based Variance Reduction

    Sep 16, 2026Wei Jiang, Zechao Li, Lijun ZhangDecentralized OptimizationVariance Reduction

    School of Computer Science and Engineering, Nanjing University of Science and Technology, China · National Key Laboratory for Novel Software Technology,Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

  18. Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start

    Sep 14, 2026Yunbum Kook, Santosh S. VempalaLog-Concave DistributionsOptimal Sample Complexity

    University of Michigan · Georgia Tech

  19. Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

    Sep 14, 2026Weiming Feng, Yixiao Yu, Yiyao ZhangOptimal Sample ComplexityNormalizing Flows

    School of Computing and Data Science, The University of Hong Kong. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

  20. Poisson-Corrector Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

    Sep 14, 2026Yuchen Xin, Zhihua ZhangLangevin DynamicsLipschitz Continuity

    School of Mathematical Sciences, Peking University

  21. Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

    Sep 14, 2026Weiming Ou, Xiao WangLog-Concave DistributionsOptimal Sample Complexity

    Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics

  22. When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence

    Sep 11, 2026Zichen Wang, Haoyang Hong, Huazheng WangContextual Bandit FrameworkKullback-Leibler Regularization

    Department of ECE and CSL, University of Illinois Urbana-Champaign · School of Electrical Engineering and Computer Science, Oregon State University

  23. Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning

    Sep 11, 2026Shaddin Dughmi, Alireza F. PourSemi-Supervised LearningOptimal Sample Complexity

    University of Southern California · University of Waterloo

  24. Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

    Sep 9, 2026Ashwin Nayak, Xingyu ZhouQubitOptimal Sample Complexity

    Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo. · Department of Computer Science, University of British Columbia.

  25. Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

    Sep 8, 2026Ivan Lau, Jonathan ScarlettOptimal Sample ComplexityMinimax Rate

    National University of Singapore

  26. Pooling and Drift in Delayed Bandits

    Sep 1, 2026Melika BaghiStochastic Multi-Armed BanditsMinimax

    Georgia Institute of Technology

  27. Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

    Aug 13, 2026Yuchen Xin, Zhihua ZhangLangevin DynamicsLipschitz Continuity

    School of Mathematical Sciences, Peking University

  28. Fast Length-Squared Sampling for Positive-Semidefinite Matrices

    Aug 12, 2026Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco +1MatrixLow-Rank Structure

    University of Massachusetts Amherst · University of California Berkeley

  29. Improving TensorSketch Using Complex Random Variables

    Aug 11, 2026Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap +1Optimal Sample ComplexityKernel Method

    Department of Computer Science and Engineering, IIT Hyderabad, India · Department of Mathematics and Statistics, Bucknell University, USA

  30. Halpern Iteration Achieves O~(ε−1/p)\tilde{\mathcal{O}}(ε^{-1/p}) ppth-Order Oracle Complexity for Monotone Variational Inequalities

    Aug 9, 2026Lesi Chen, Xinliang Zhang, Hengyu Wang +3Monotone Variational InequalitiesFirst Order Oracle Complexity

    1IIIS, Tsinghua University · Apex Intelligence · School of Mathematical Sciences, Tongji University +2

  31. The Sample Complexity of Policy Learning with Mu-Resets

    Aug 7, 2026Gene LiOptimal Sample ComplexitySample Complexity

  32. An Optimal Agnostic PAC Algorithm

    Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyOptimal Sample ComplexitySample Complexity

    Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley

  33. Optimal Rates for Learning with Monotone Adversaries

    Aug 6, 2026Anay MehrotraOptimal Sample ComplexityEmpirical Risk Minimization

    Stanford University

  34. The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

    Aug 5, 2026Elad Aigner-Horev, Daniel Rosenberg, Roi WeissDistributionally-Robust OptimizationOptimal Sample Complexity

    School of Computer Science and AI Ariel University 40800 Ariel, Israel

  35. Sample Complexity of Multicalibration for Multilevel Properties

    Aug 4, 2026Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev +1Optimal Sample ComplexitySample Complexity

    Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · 2Amazon · Department of Statistics, University of California, Davis

  36. The Condition-Number Barrier in Sparse Least Squares

    Aug 3, 2026Honghao Lin, Vahab Mirrokni, David P. WoodruffConvex OptimizationLeast Squares

    Google Research, Carnegie Mellon University / Texas A&M University. · Google Research. · Google Research and Carnegie Mellon University.

  37. Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

    Aug 3, 2026Jiachen Hu, Han ZhongOptimal Sample ComplexityMean

    Shanghai University of Finance and Economics · Shanghai Jiao Tong University

  38. Wasserstein mixing time of the unadjusted Langevin algorithm

    Aug 3, 2026Francesco Pedrotti, Peter A. WhalleyLangevin DynamicsWasserstein Distance

    ETH Zürich

  39. Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification

    Jul 31, 2026Anders Jonsson, Emilie Kaufmann, Gianmarco Tedeschi +1Hierarchical Reinforcement LearningOptimal Sample Complexity

    Department of Engineering Universitat Pompeu Fabra · Univ. Lille, CNRS, Inria Centrale Lille, UMR 9189-CRIStAL · Dept. Electronics, Information, and Bioengineering Politecnico di Milano

  40. Fast Rates for Swap-Agnostic Learning of Proper Losses

    Jul 30, 2026Princewill OkoroaforLearning-Augmented AlgorithmsOptimal Sample Complexity

    Harvard University

  41. Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

    Jul 30, 2026Naman Saxena, Mudit Gaur, Vaneet AggarwalHierarchical Reinforcement LearningEntropy Regularized Reinforcement Learning

    Purdue University West Lafayette, IN 47907

  42. Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection

    Jul 30, 2026Arunan JOptimal Sample ComplexityEmpirical Risk Minimization

    Independent Researcher, Chennai, India.

  43. Field Codes for Distributed Coupling Samplers and Certified Empirical Transport

    Jul 29, 2026Hung Mai, Hai Nguyen, Luong Doan +4Optimal Transport ApproachAccelerated Sampling

    1B0Labs, N2TP Technology · 3Nanyang Technological University · 4Phenikaa University, Vietnam

  44. Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

    Jul 28, 2026Zhaojun PengStochastic Convex OptimizationConvex Optimization

    School of Computer Science Nanjing University of Information Science and Technology

  45. Lloyd's KK-Means Clustering Algorithm Is Frank-Wolfe in Disguise

    Jul 28, 2026Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-JulienK-MeansConvex Optimization

    Department of Mathematics & Statistics and School of Data Science Old Dominion University Norfolk, VA 23529, USA · Information Systems & Analytics Department Miami University Oxford, OH 45056, USA · Canada CIFAR AI Chair Department of Computer Science and Operations Research & Mila Université de Montréal Montréal (QC) Canada

  46. Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set

    Jul 26, 2026Heyang Zhao, Tianyuan Jin, Weixin Wang +3Stochastic Multi-Armed BanditsVariance Reduction

    Department of Computer Science, University of California, Los Angeles · Department of Electrical and Computer Engineering, National University of Singapore · Department of Biostatistics & Bioinformatics, Duke University +2

  47. Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue

    Jul 24, 2026Rohan Chauhan, Ioannis PanageasOptimal Sample ComplexitySpectral Norm

    University of California, Irvine

  48. Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs

    Jul 24, 2026Akira KitaokaLinear ProgrammingOptimal Sample Complexity

  49. The Tractability Landscape of Sampling with Inexact Scores

    Jul 21, 2026Anming Gu, Kevin Tian, Hubert Yang +1Optimal Sample ComplexityIndependent-Pool Single-Draw Oracle

    University of Texas at Austin

  50. On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

    Jul 21, 2026Jixian Liu, Ihab Tabbara, Hussein Sibai +1ReachabilityHamilton-Jacobi Reachability

    Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Computer Science, Washington University in St. Louis

  51. Tight Sample Bounds for Renyi and Min-Entropy Estimation

    Jul 18, 2026Arman Adibi, Piotr KrystaOptimal Sample Complexity

    Department of Computer Science

  52. What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

    Jul 16, 2026Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich +3SmoothnessStochastic Gradient Descent

    Department of Mathematics and Computer Science University of Basel Basel, Switzerland 4001 · Simons Institute for the Theory of Computing, Berkeley · Department of Data Science New Jersey Institute of Technology Newark, NJ, USA 07102

  53. Beyond the d2.5d^{2.5}-mixing bound for Dikin walks on polytopes

    Jul 15, 2026Yunbum KookPolytopesOptimal Sample Complexity

    Georgia Tech

  54. From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

    Jul 13, 2026Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau +1Transformer ArchitecturesLearnability

    Mila & Universit´e de Montr´eal · University of Oxford · Saarland University

  55. Near-Optimal Learning of Gaussian Sobolev Operators

    Jul 8, 2026Ben Adcock, Michael Griebel, Gregor MaierProbabilistic Operator LearningLogarithmic Sobolev Inequalities

    Department of Mathematics, Simon Fraser University, Burnaby BC, Canada · Institute for Numerical Simulation, University of Bonn, Bonn, Germany · Fraunhofer Institute for Algorithms and Scientific Computing (SCAI), Sankt Augustin, Germany

  56. Distributed Sketching on Data Partitions for OLS Regression

    Jul 8, 2026Luyuan Yang, Brayden Garner, Shayan Shafaei +1Least SquaresExponential Family

    a School of Computer Science, University of Oklahoma, U.S.

  57. Any-Dimensional Learning by Sampling

    Jul 8, 2026Eitan Levin, Venkat ChandrasekaranOptimal Sample ComplexityModel Size

    Department of Statistics University of Chicago Chicago, IL 60637 · Department of Computing and Mathematical Sciences Department of Electrical Engineering California Institute of Technology Pasadena, CA 91125

  58. The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

    Jul 8, 2026Zhiyuan LiOptimal Sample ComplexitySample Complexity

    Toyota Technological Institute at Chicago

  59. Fast determinantal sampling on general spaces and diffusion geometry

    Jul 7, 2026Hoang-Son Tran, Pranav Gupta, Subhroshekhar GhoshDeterminantal Point ProcessOptimal Sample Complexity

    Department of Mathematics National University of Singapore

  60. Sensitivity Sampling with Predictions for k-Means Clustering

    Jul 6, 2026Cristian Boldrin, Fabio VandinK-MeansClustering

    University of Padova, Padova, Italy