Simultaneous perturbation stochastic approximation: towards one-measurement per iteration

Shiru Li, Yong Xia, Zi XuNumer. Algorithms 2023 · DOI

TL;DR

This paper introduces a novel variant of the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm that reduces the number of function evaluations per iteration from two to one, on average. This is achieved by cleverly reusing function evaluations across iterations, leading to significant computational savings without sacrificing convergence guarantees or asymptotic normality.

What Problem Does This Paper Address?

The Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm is a popular method for optimizing functions, especially when function evaluations are expensive or noisy. A key characteristic of SPSA is that it requires two function evaluations per iteration to estimate the gradient. While effective, this requirement can still be a bottleneck in scenarios where minimizing the number of function calls is paramount. Existing one-measurement SPSA variants, while reducing evaluations, often introduce a bias that can hinder practical performance. This paper aims to bridge this gap by developing an SPSA algorithm that achieves one function measurement per iteration on average, while maintaining strong theoretical convergence properties and avoiding the bias issues of previous one-measurement methods.

Methods

The core innovation lies in a new algorithm, termed SPSA1-A, which cleverly reuses function evaluations. The strategy is based on the observation that the sign of the estimated gradient can indicate a descent direction. SPSA1-A takes one step using two function evaluations (similar to standard SPSA) and then takes a second step in a direction determined by the sign of the previously computed gradient, requiring no additional function evaluations for this second step. This effectively means two function evaluations are performed every two iterations, achieving the desired one-measurement-per-iteration average. The paper rigorously proves the strong convergence and asymptotic normality of this new algorithm under standard assumptions for stochastic approximation methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on standard benchmark functions.

Key Insights and Ideas

  • Average-Sense One-Measurement: The paper demonstrates that it's possible to achieve the efficiency of one function evaluation per iteration on average by intelligently reusing computations, rather than strictly enforcing one evaluation per step.
  • Bias Mitigation: The proposed SPSA1-A algorithm avoids the bias issues that plagued previous one-measurement SPSA variants, leading to better practical performance and stronger theoretical guarantees.
  • Gradient Sign as Descent Indicator: The algorithm leverages the sign of the gradient estimate to guide a second, evaluation-free step, which is a key insight for reducing computational cost.
  • Theoretical Rigor: The paper provides a thorough theoretical analysis, proving strong convergence and asymptotic normality, which is crucial for establishing the reliability of the new method.

Key Results

The paper presents numerical experiments comparing SPSA1-A with standard SPSA and a prior one-measurement SPSA variant (SPSA1) on several benchmark functions (Rosenbrock, Beale, Powell singular, and a custom function). The results consistently show that:

  • SPSA1-A significantly reduces the number of functional measurements compared to SPSA, often by more than half, to achieve a similar level of accuracy.
  • SPSA1-A converges faster than SPSA in terms of function evaluations.
  • SPSA1-A outperforms SPSA1, achieving higher accuracy with fewer measurements, especially for problems requiring high precision. For instance, in Test II, SPSA1-A achieved an error of $10^{-3}$ with 144 measurements, while SPSA required 3738.

Limitations and Future Work

  • Parameter Tuning: While the paper provides parameters that work well for the tested functions, the optimal choice of parameters for SPSA1-A might still require some tuning for different problems.
  • Specific Problem Classes: The theoretical analysis and experimental validation are primarily focused on unconstrained optimization. Extending the method to constrained optimization or other problem classes could be a future direction.
  • Further Applications: The authors suggest that future work should explore more applications of the new algorithm and investigate further improvements. This could include developing adaptive versions or exploring its use in complex real-world scenarios.

Summary updated

BibTeX
@article{li2023simultaneous,
  author = {Shiru Li and Yong Xia and Zi Xu},
  title = {{Simultaneous perturbation stochastic approximation: towards one-measurement per iteration}},
  journal = {Numer. Algorithms},
  year = {2023},
  doi = {10.1007/s11075-023-01528-7},
}
Figure