mlsanityData to 14 Oct 2026

Asymptotic Optimality in Stochastic Optimization

arXiv 1612.05612 ↗First posted 16 Dec 2016math.ST math.OC stat.MLcited by 38

Not on the map. Why?

Abstract (arXiv)

We study local complexity measures for stochastic convex optimization problems, providing a local minimax theory analogous to that of H'ajek and Le Cam for classical statistical problems. We give complementary optimality results, developing fully online methods that adaptively achieve optimal convergence guarantees. Our results provide function-specific lower bounds and convergence results that make precise a correspondence between statistical difficulty and the geometric notion of tilt-stability from optimization. As part of this development, we show how variants of Nesterov's dual averaging---a stochastic gradient-based procedure---guarantee finite time identification of constraints in optimization problems, while stochastic gradient procedures fail. Additionally, we highlight a gap between problems with linear and nonlinear constraints: standard stochastic-gradient-based procedures are suboptimal even for the simplest nonlinear constraints, necessitating the development of asymptotically optimal Riemannian stochastic gradient methods.

Key facts. Cited by 38 papers in the map (data through 14 Oct 2026). First posted on arXiv 16 Dec 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 6; 2023: 9; 2024: 5; 2025: 7; 2026: 2.

38 papers.

Sort:

  1. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 35
  2. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  3. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 20
  4. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 20
  5. 2023Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspectivecited by 20
  6. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 17
  7. 2021Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methodscited by 14
  8. 2023Asymptotic normality and optimality in nonsmooth stochastic approximationcited by 14
  9. 2022Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimalitycited by 12
  10. 2022Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programmingcited by 10
  11. 2024High Confidence Level Inference is Almost Free using Parallel Stochastic Optimizationcited by 10
  12. 2022Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descentcited by 8
26 more
  1. 2021Training Structured Neural Networks Through Manifold Identification and Variance Reductioncited by 7
  2. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  3. 2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
  4. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 6
  5. 2023A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Propertiescited by 5
  6. 2021Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimizationcited by 4
  7. 2023Fairness Uncertainty Quantification: How certain are you that the model is fair?cited by 4
  8. 2023Optimizer's Information Criterion: Dissecting and Correcting Bias in Data-Driven Optimizationcited by 4
  9. 2024Resampling methods for private statistical inferencecited by 4
  10. 2025Online Covariance Estimation in Nonsmooth Stochastic Approximationcited by 4
  11. 2025Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequencescited by 4
  12. 2025The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspectivecited by 3
  13. 2025Stochastic Optimization with Optimal Importance Samplingcited by 2
  14. 2025Statistical Inference for Online Algorithmscited by 2
  15. 2021On Misspecification in Prediction Problems and Robustness via Improper Learningcited by 1
  16. 2021Learning Curves for SGD on Structured Featurescited by 1
  17. 2022Data-Driven Influence Functions for Optimization-Based Causal Inferencecited by 1
  18. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  19. 2024Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysiscited by 1
  20. 2024The radius of statistical efficiencycited by 1
  21. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  22. 2022Exponential Concentration in Stochastic Approximationcited by 0
  23. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
  24. 2025Online Statistical Inference of Constrained Stochastic Optimization via Random Scalingcited by 0
  25. 2026A lift for input-convex neural net trainingcited by 0
  26. 2026A stochastic subgradient method with optimal failure exponentcited by 0