# Accelerated Zero-Order SGD Method for Solving the Black Box Optimization Problem under "Overparametrization" Condition

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2023.

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

- [KerZOO: Kernel Function Informed Zeroth-Order Optimization for Accurate and Accelerated LLM Fine-Tuning](https://mlsanity.com/paper/2505.18886/) (2025)
- [Accelerated zero-order SGD under high-order smoothness and overparameterized regime](https://mlsanity.com/paper/2411.13999/) (2024)
- [Towards Fast LLM Fine-tuning through Zeroth-Order Optimization with Projected Gradient-Aligned Perturbations](https://mlsanity.com/paper/2510.18228/) (2025)
- [Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity](https://mlsanity.com/paper/2605.31346/) (2026)

## Abstract (arXiv)

This paper is devoted to solving a convex stochastic optimization problem in a overparameterization setup for the case where the original gradient computation is not available, but an objective function value can be computed. For this class of problems we provide a novel gradient-free algorithm, whose creation approach is based on applying a gradient approximation with l2 randomization instead of a gradient oracle in the biased Accelerated SGD algorithm, which generalizes the convergence results of the AC-SA algorithm to the case where the gradient oracle returns a noisy (inexact) objective function value. We also perform a detailed analysis to find the maximum admissible level of adversarial noise at which we can guarantee to achieve the desired accuracy. We verify the theoretical results of convergence using a model example.