Zeroth-order optimization with orthogonal random directions

David Kozak, Cesare Molinari, Lorenzo Rosasco, Luis Tenorio, Silvia VillaMath. Program 2021 · DOI · OpenReview

Abstract

We propose and analyze a randomized zeroth-order approach based on approximating the exact gradient by finite differences computed in a set of orthogonal random directions that changes with each iteration. A number of previously proposed methods are recovered as special cases including spherical smoothing, coordinate descent, as well as discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence rates under different parameter choices and assumptions. In particular, we consider convex objectives, but also possibly non-convex objectives satisfying the Polyak-Łojasiewicz (PL) condition. Theoretical results are complemented and illustrated by numerical experiments.

Introduction

In many complex domains such as reinforcement learning, robotics, and engineering simulations, optimization often occurs in a "black box" environment. In these scenarios, the analytical gradient of the objective function is unavailable, necessitating the use of zeroth-order optimization techniques. Traditional methods like discretized gradient descent or coordinate descent can be prohibitively expensive in high-dimensional spaces, where $d$ variables require $d+1$ function evaluations per step.

This paper introduces a unified framework that leverages random orthogonal subspaces to estimate gradients efficiently. By sampling a limited number of directions, the proposed method balances the cost per iteration with the progress made toward the optimum.

The Zeroth Order Stochastic Subspace Algorithm

The core of the proposed approach is the Zeroth Order Stochastic Subspace Algorithm. At each iteration $k$, the algorithm selects a random matrix $P_k$ with $\ell$ orthogonal columns, where $\ell$ is typically much smaller than the dimension $d$. A finite difference approximation is then computed within this lower-dimensional subspace.

Algorithm 1: Zeroth order stochastic subspace algorithm

As shown in Algorithm 1, the update rule $x_{k+1} = x_k - \alpha_k P_k \nabla_{(P_k, h_k)} f(x_k)$ allows for flexible exploration of the search space. This framework is significant because it unifies several existing methods:

  • Coordinate Descent: Recovered when $P_k$ is chosen from the columns of the identity matrix.
  • Spherical Smoothing: Recovered when $\ell=1$ and directions are sampled uniformly from a unit sphere.

Theoretical Convergence Analysis

A primary contribution of this work is the rigorous proof of almost sure convergence for the iterates $x_k$. Unlike many previous works that only guarantee convergence of the function value in expectation, this paper ensures that the algorithm actually reaches the minimizer.

Convergence Rates

  • Convex Objectives: By employing a vanishing discretization parameter $h_k$, the algorithm achieves a $1/k$ convergence rate for the best iterate.
  • Polyak-Łojasiewicz (PL) Condition: For functions satisfying the PL condition—a generalization of strong convexity that includes some non-convex landscapes—the algorithm achieves linear (exponential) convergence, provided the discretization parameter $h_k$ decays at a sufficient rate.

Numerical Experiments

The theoretical findings were validated through experiments on synthetic problems designed to test specific mathematical properties:

  1. Convex PL Functions: Quadratic forms $f(x) = \|Ax\|^2$ where $A$ is not full rank.
  2. Non-Convex PL Functions: Landscapes defined by $f(x) = \|Ax\|^2 + 3 \sin^2(c^\top x)$.
  3. High-Dimensional Scaling: Tests with $d=100$ demonstrated that using small subspaces ($\ell < d$) allows for more frequent updates, leading to faster progress relative to the total number of function evaluations compared to full-dimensional discretized gradient descent.

Conclusion and Future Directions

The Zeroth Order Stochastic Subspace Algorithm provides a robust and theoretically sound framework for gradient-free optimization. By demonstrating that "noisy" updates in random subspaces can outperform exact gradient approximations in high-dimensional settings, this work opens new avenues for efficient black-box optimization. Future research may extend these results to noisy oracles, incorporate adaptive line searches, or explore second-order "Quasi-Newton" variants to further accelerate convergence.

Summary updated

Abstract

We propose and analyze a randomized zeroth-order optimization method based on approximating the exact gradient by finite differences computed in a set of orthogonal random directions that changes with each iteration. A number of previously proposed methods are recovered as special cases including spherical smoothing, coordinate descent, as well as discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence rates under different parameter choices and assumptions. In particular, we consider convex objectives, but also possibly non-convex objectives satisfying the Polyak-Łojasiewicz (PL) condition. Theoretical results are complemented and illustrated by numerical experiments.
BibTeX
@inproceedings{kozak2021zeroth,
  author = {David Kozak and Cesare Molinari and Lorenzo Rosasco and Luis Tenorio and Silvia Villa},
  title = {{Zeroth-order optimization with orthogonal random directions}},
  booktitle = {Math. Program},
  year = {2021},
  doi = {10.48550/arxiv.2107.03941},
}
Figure