SPSA

Simultaneous Perturbation Stochastic Approximation。 全変数を同時にランダムに揺らし、その 2 点の差だけで勾配全体を近似する手法。 Spall が 1992 年に提案した。

何が効率的なのか#

有限差分で勾配を作ると、$p$ 次元に対して各成分ごとに 2 点、 計 $2p$ 回の評価が要る。SPSA は次元によらず 2 回で済む。

$${\hat{g}}_{k,i}({\hat{\theta }}_k)=\frac{y({\hat{\theta }}_k+c_k{\mathrm{\Delta }}_k)-y({\hat{\theta }}_k-c_k{\mathrm{\Delta }}_k)}{2c_k{\mathrm{\Delta }}_{ki}}$$

分子は全成分で共通で、分母だけが成分ごとに変わる。 1 回の摂動から全成分の推定値を取り出しているのが要点。

各成分の推定は粗いが、${\mathrm{\Delta }}_k$ を毎回引き直すため 期待値としては正しい方向を向く。反復を重ねるうちに誤差が均される。 Spall は、同じ反復回数なら有限差分と同程度の統計的精度に達することを示した。

摂動ベクトルの条件#

${\mathrm{\Delta }}_k$ の各成分は独立に引くが、逆モーメント $𝔼[|1/{\mathrm{\Delta }}_{ki}|]$ が 有限である必要がある。分母に ${\mathrm{\Delta }}_{ki}$ が来るため。

このため正規分布と一様分布は使えない。0 付近の値を取りうるので 逆モーメントが発散する。標準は対称ベルヌーイ分布（$\pm 1$ を等確率）。

ゲイン列#

$$a_k=\frac{a}{{(A+k+1)}^{\alpha }},c_k=\frac{c}{{(k+1)}^{\gamma }}$$

漸近的な最適値は $\alpha =1.0,\gamma =1/6$ だが、 有限回では減衰が速すぎて動かなくなる。実用上は $\alpha =0.602,\gamma =0.101$ が推奨される。 $c$ は測定ノイズの標準偏差と同程度、$A$ は想定反復回数の 10% 程度が目安。

量子計算での位置づけ#

VQE のパラメータ最適化で SPSA が標準的に使われるのは、この分野の制約と噛み合うため。

• パラメータシフト則で厳密な勾配を得ると $𝒪(p)$ 回の回路評価が要る。 SPSA は $𝒪(1)$
• 期待値は有限ショットの標本平均なので、そもそもノイズを前提とした手法が要る。 SPSA は確率的近似の枠組みで設計されており、ノイズがあることが前提

詳しくはSpall (1998) の実装ガイドのメモを参照。

参考文献#

• James C. Spall. Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation. IEEE Transactions on Automatic Control 37(3), 1992.（原論文） https://doi.org/10.1109/9.119632
• James C. Spall. Implementation of the Simultaneous Perturbation Algorithm for Stochastic Optimization. IEEE Transactions on Aerospace and Electronic Systems 34(3), 1998.（実装ガイド） https://doi.org/10.1109/7.705889
• James C. Spall. Introduction to Stochastic Search and Optimization. Wiley, 2003. https://doi.org/10.1002/0471722138