# A Unified Zeroth-Order Optimization Framework via Oblivious Randomized Sketching

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2025.

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

- [Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions](https://mlsanity.com/paper/2512.16200/) (2025)
- [Optimal low-rank stochastic gradient estimation for LLM training](https://mlsanity.com/paper/2603.20632/) (2026)

## Abstract (arXiv)

We propose a new framework for analyzing zeroth-order optimization (ZOO) from the perspective of oblivious randomized sketching.In this framework, commonly used gradient estimators in ZOO-such as finite difference (FD) and random finite difference (RFD)-are unified through a general sketch-based formulation. By introducing the concept of oblivious randomized sketching, we show that properly chosen sketch matrices can significantly reduce the high variance of RFD estimates and enable high-probability convergence guarantees of ZOO, which are rarely available in existing RFD analyses. noindent We instantiate the framework on convex quadratic objectives and derive a query complexity of tildeO(tr(A)/L · L/μlogfrac1ε) to achieve a ε-suboptimal solution, where A is the Hessian, L is the largest eigenvalue of A, and μ denotes the strong convexity parameter. This complexity can be substantially smaller than the standard query complexity of cO(d· L/μ logfrac1ε) that is linearly dependent on problem dimensionality, especially when A has rapidly decaying eigenvalues. These advantages naturally extend to more general settings, including strongly convex and Hessian-aware optimization. noindent Overall, this work offers a novel sketch-based perspective on ZOO that explains why and when RFD-type methods can achieve weakly dimension-independent convergence in general smooth problems, providing both theoretical foundations and practical implications for ZOO.