# Asymptotic normality and optimality in nonsmooth stochastic approximation

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 16 Jan 2023.

## Builds on (most cited first, 7 of 7)

- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Stochastic algorithms with geometric step decay converge linearly on sharp functions](https://mlsanity.com/paper/1907.09547/) (2019)
- [Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2207.04173/) (2022)
- [Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization](https://mlsanity.com/paper/2108.11832/) (2021)
- [Generic minimizing behavior in semi-algebraic optimization](https://mlsanity.com/paper/1504.07694/) (2015)

## Built on by (most cited first, 14 of 14)

- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [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 Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines](https://mlsanity.com/paper/2407.21091/) (2024)
- [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)
- [Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression](https://mlsanity.com/paper/2302.09727/) (2023)
- [Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis](https://mlsanity.com/paper/2404.00042/) (2024)
- [The radius of statistical efficiency](https://mlsanity.com/paper/2405.09676/) (2024)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling](https://mlsanity.com/paper/2505.18327/) (2025)
- [Local linear convergence of gradient methods for overparameterized Gaussian mixtures](https://mlsanity.com/paper/2605.30936/) (2026)

## Abstract (arXiv)

In their seminal work, Polyak and Juditsky showed that stochastic approximation algorithms for solving smooth equations enjoy a central limit theorem. Moreover, it has since been argued that the asymptotic covariance of the method is best possible among any estimation procedure in a local minimax sense of H'ajek and Le Cam. A long-standing open question in this line of work is whether similar guarantees hold for important non-smooth problems, such as stochastic nonlinear programming or stochastic variational inequalities. In this work, we show that this is indeed the case.