# Asymptotic Optimality in Stochastic Optimization

arXiv: https://arxiv.org/abs/1612.05612 · HTML: https://mlsanity.com/paper/1612.05612/

## Key facts

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

## Built on by (most cited first, 30 of 38)

- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspective](https://mlsanity.com/paper/2304.06833/) (2023)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods](https://mlsanity.com/paper/2102.03389/) (2021)
- [Asymptotic normality and optimality in nonsmooth stochastic approximation](https://mlsanity.com/paper/2301.06632/) (2023)
- [Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2207.04173/) (2022)
- [Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming](https://mlsanity.com/paper/2205.13687/) (2022)
- [High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization](https://mlsanity.com/paper/2401.09346/) (2024)
- [Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descent](https://mlsanity.com/paper/2212.14883/) (2022)
- [Training Structured Neural Networks Through Manifold Identification and Variance Reduction](https://mlsanity.com/paper/2112.02612/) (2021)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties](https://mlsanity.com/paper/2305.05828/) (2023)
- [Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization](https://mlsanity.com/paper/2111.15645/) (2021)
- [Fairness Uncertainty Quantification: How certain are you that the model is fair?](https://mlsanity.com/paper/2304.13950/) (2023)
- [Optimizer's Information Criterion: Dissecting and Correcting Bias in Data-Driven Optimization](https://mlsanity.com/paper/2306.10081/) (2023)
- [Resampling methods for private statistical inference](https://mlsanity.com/paper/2402.07131/) (2024)
- [Online Covariance Estimation in Nonsmooth Stochastic Approximation](https://mlsanity.com/paper/2502.05305/) (2025)
- [Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences](https://mlsanity.com/paper/2512.13123/) (2025)
- [The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective](https://mlsanity.com/paper/2510.18215/) (2025)
- [Stochastic Optimization with Optimal Importance Sampling](https://mlsanity.com/paper/2504.03560/) (2025)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [On Misspecification in Prediction Problems and Robustness via Improper Learning](https://mlsanity.com/paper/2101.05234/) (2021)
- [Learning Curves for SGD on Structured Features](https://mlsanity.com/paper/2106.02713/) (2021)
- [Data-Driven Influence Functions for Optimization-Based Causal Inference](https://mlsanity.com/paper/2208.13701/) (2022)
- [Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression](https://mlsanity.com/paper/2302.09727/) (2023)

## 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.