mlsanityData to 14 Oct 2026

Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm

arXiv 2102.05198 ↗First posted 10 Feb 2021stat.ML cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Statistical machine learning models trained with stochastic gradient algorithms are increasingly being deployed in critical scientific applications. However, computing the stochastic gradient in several such applications is highly expensive or even impossible at times. In such cases, derivative-free or zeroth-order algorithms are used. An important question which has thus far not been addressed sufficiently in the statistical machine learning literature is that of equipping stochastic zeroth-order algorithms with practical yet rigorous inferential capabilities so that we not only have point estimates or predictions but also quantify the associated uncertainty via confidence intervals or sets. Towards this, in this work, we first establish a central limit theorem for Polyak-Ruppert averaged stochastic zeroth-order gradient algorithm. We then provide online estimators of the asymptotic covariance matrix appearing in the central limit theorem, thereby providing a practical procedure for constructing asymptotically valid confidence sets (or intervals) for parameter estimation (or prediction) in the zeroth-order setting.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 36 of its 95 references that are in the map. First posted on arXiv 10 Feb 2021.

Builds on

36 of 95 references.

References · 36

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  2. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  3. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  4. 2018Black-box Adversarial Attacks with Limited Queries and Informationcited by 501
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  6. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  7. 2019Efficient Decision-based Black-box Adversarial Attacks on Face Recognitioncited by 175
  8. 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 162
  9. 2018Query-Efficient Hard-label Black-box Attack:An Optimization-based Approachcited by 130
  10. 2019Sign-OPT: A Query-Efficient Hard-label Adversarial Attackcited by 120
  11. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  12. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
24 more
  1. 2019NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networkscited by 94
  2. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
  3. 2018Risk and parameter convergence of logistic regressioncited by 85
  4. 2019ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimizationcited by 76
  5. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  6. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
  7. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  8. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 48
  9. 2019An ADMM Based Framework for AutoML Pipeline Configurationcited by 47
  10. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  11. 2020Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Samplingcited by 46
  12. 2016A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Ordercited by 44
  13. 2019Gradientless Descent: High-Dimensional Zeroth-Order Optimizationcited by 43
  14. 2016Asymptotic Optimality in Stochastic Optimizationcited by 38
  15. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 37
  16. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  17. 2018A Frank-Wolfe Framework for Efficient and Effective Adversarial Attackscited by 29
  18. 2017Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applicationscited by 22
  19. 2019On the Design of Black-box Adversarial Examples by Leveraging Gradient-free Optimization and Operator Splitting Methodcited by 21
  20. 2018Towards Gradient Free and Projection Free Stochastic Optimizationcited by 15
  21. 2020Accelerated Stochastic Gradient-free and Projection-free Methodscited by 12
  22. 2018An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimizationcited by 8
  23. 2019Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimizationcited by 6
  24. 2018Approximate Newton-based statistical inference using only stochastic gradientscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 1; 2025: 2.

6 papers.

  1. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  2. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  3. 2023Hebbian learning inspired estimation of the linear regression parameters from queriescited by 1
  4. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  5. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
  6. 2025Direct Fisher Score Estimation for Likelihood Maximizationcited by 0