Zeroth-Order Randomized Subspace Newton Methods

Erik Berglund, Sarit Khirirat, Xiaoyu WangICASSP 2022

Abstract

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.

Introduction

In many modern optimization scenarios, such as hyper-parameter tuning or black-box adversarial attacks on proprietary AI models, explicit gradients are unavailable. These "black-box" problems necessitate zeroth-order (ZO) optimization, which relies solely on function evaluations. The primary bottleneck for traditional ZO methods is their query complexity; gradient-based ZO approaches are typically $n$ times slower than their first-order counterparts in $n$-dimensional spaces. While second-order Newton methods offer faster convergence by utilizing Hessian information, the cost of estimating a full $n \times n$ Hessian via function evaluations is prohibitive for high-dimensional tasks. This paper introduces a method to bridge this gap by approximating Hessian information within a restricted subspace.

Methodology

The proposed Zeroth-Order Randomized Subspace Newton (ZO-RSN) method leverages two key techniques to achieve acceleration with low overhead:

  1. Random Sketching: The optimization step is restricted to a small $m$-dimensional subspace ($m \ll n$) defined by a sketching matrix $S$. This reduces the dimensionality of the second-order update.
  2. Finite Difference Projections: Instead of estimating the full gradient or Hessian, ZO-RSN uses finite differences to estimate only their projections onto the chosen subspace. This significantly reduces the number of function queries required per iteration.

For constrained optimization problems, such as adversarial attacks where perturbations must remain small, the authors developed ZO-RSN-SQP. This variant employs Sequential Quadratic Programming to handle linear constraints within the subspace framework, ensuring stability and feasibility.

Experimental Evaluation

The effectiveness of ZO-RSN-SQP was evaluated through black-box adversarial attacks on a pre-trained convolutional neural network (CNN) using the MNIST dataset. The objective was to find the minimal perturbation required to cause misclassification, using only the model's confidence scores as function evaluations.

Results

The numerical experiments compared ZO-RSN-SQP against the state-of-the-art Hessian-aware method, ZOHA-Gauss-DC. As shown in the comparative analysis below, ZO-RSN-SQP demonstrated superior performance across multiple critical metrics.

Comparison of ZO-RSN-SQP and ZOHA-Gauss-DC in black-box adversarial attacks.

Key findings include:

  • Success Rate: ZO-RSN-SQP achieved a perfect 100% success rate, outperforming the baseline's 95.33%.
  • Query Efficiency: The mean number of queries for a successful attack was significantly reduced from 4164 (baseline) to 2510 (ZO-RSN-SQP). Furthermore, the maximum number of queries required was nearly six times lower for ZO-RSN-SQP.
  • Convergence Accuracy: While the baseline showed competitive initial performance (lower median queries), ZO-RSN-SQP achieved significantly lower function value differences ($f_{est} - f^*$) as the number of queries increased, indicating superior "fine-tuning" capabilities in the late stages of optimization.

Conclusion

ZO-RSN provides a theoretically grounded and practically efficient framework for zeroth-order optimization. By focusing second-order information on a random subspace, it achieves significant speedups over gradient-only and existing Hessian-aware methods. Future work includes extending the theoretical guarantees to non-convex functions and exploring optimal strategies for choosing the subspace dimension and sketching matrices.

Summary updated

Abstract

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.
BibTeX
@inproceedings{berglund2022zeroth,
  author = {Erik Berglund and Sarit Khirirat and Xiaoyu Wang},
  title = {{Zeroth-Order Randomized Subspace Newton Methods}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
}
Figure