# Zeroth-Order Randomized Subspace Newton Methods

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2022.

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

- [Subspace-based Approximate Hessian Method for Zeroth-Order Optimization](https://mlsanity.com/paper/2507.06125/) (2025)

## Abstract (arXiv)

Zeroth-order methods have become important tools for solving problems where we have access only to function evaluations. However, the zeroth-order methods only using gradient approximations are n times slower than classical first-order methods for solving n-dimensional problems. To accelerate the convergence rate, this paper proposes the zeroth order randomized subspace Newton (ZO-RSN) method, which estimates projections of the gradient and Hessian by random sketching and finite differences. This allows us to compute the Newton step in a lower dimensional subspace, with small computational costs. We prove that ZO-RSN can attain lower iteration complexity than existing zeroth order methods for strongly convex problems. Our numerical experiments show that ZO-RSN can perform black-box attacks under a more restrictive limit on the number of function queries than the state-of-the-art Hessian-aware zeroth-order method.