A Unified Zeroth-Order Optimization Framework via Oblivious Randomized Sketching

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.