SPSAをゼロから理解する

はじめに

記事の作成には、論文をソースとしてChatGPTを補助的に利用しています。内容については論文を参照しながら確認していますが、もし誤り等があればご指摘いただけると助かります。

SPSA は何のために生まれたのか

SPSA は、多変数の最適化問題を解くために提案された手法である。対象は「スカラー値の損失関数 $L(u)$ を、$p$ 次元のパラメータベクトル $u$ に関して最小化する問題」としている。さらに重要なのは、損失関数の値は測れるが、勾配 $\partial L / \partial u$ は直接は使えないという前提である。測定値にはノイズがあってもよい。

ここで問題になるのは、現実の最適化では「勾配をそのまま計算できる」とは限らないことだ。適応制御、統計的同定、モンテカルロ最適化、画像処理、ニューラルネットワーク学習などを例に挙げると、システムの入出力関係を完全に知っていないために勾配が作れない、あるいは作れても高コストだと説明できる。つまり SPSA は、勾配が自然には手に入らないブラックボックス的な状況に対する解として出てきた。

従来法：有限差分法（FDSA）は何をしているのか

SPSA を理解するには、まず 有限差分法（FDSA） をはっきり理解する必要がある。FDSA は「各成分を1つずつ摂動させて、損失関数の差から勾配を近似する方法」である。

勾配ベクトルは

$$
g(u)=\frac{\partial L}{\partial u}
$$

であり、その $i$ 成分は偏微分

$$
\frac{\partial L}{\partial u_i}
$$
である。FDSA では、この $i$ 成分を数値的に

$$
\hat{g}_{ki}(\hat{u}_k)=
\frac{
y(\hat{u}_k + c_k e_i)-y(\hat{u}_k-c_k e_i)
}{
2c_k
}
$$

のように近似する。ここで $e_i$ は、$i$ 番目だけ 1 で他が 0 の単位ベクトルである。つまり、$u_i$ の方向だけを + と - に少し動かし、その差を見る。

この式の意味はかなり直感的で、要するに

• $u_1$ 方向の傾きを知りたければ $u_1$ だけを動かす
• $u_2$ 方向の傾きを知りたければ $u_2$ だけを動かす
• これを $p$ 個の成分すべてについてやる

ということになる。

したがって、各成分ごとに 2 回の損失評価が必要になる。成分が $p$ 個あれば、必要な評価回数は

$$
2p
$$

回である。FDSA は 1 回の反復ごとに、次元 $p$ に比例して損失関数評価回数が増える。

なぜ FDSA ではつらいのか

FDSA の問題は、高次元になるととにかく高コストになることだ。SPSA と FDSA の最大の違いは、FDSA の評価回数は $p$ に比例して増えるが、SPSA は 2 回で済むという点である。

もしパラメータが 100 次元なら、FDSA は 200 回の損失評価が必要になる。
もし 1000 次元なら、2000 回必要になる。

損失関数の 1 回の評価が安ければまだよいが、量子回路、シミュレーション、実験系、ニューラルネットワーク制御のように、1回評価するだけでも重い場合には、このコストが現実的でなくなる。

実例として、ニューラルネットワーク制御の問題で $p=412$ のケースがある。このとき FDSA は 1 反復あたり 824 回の損失評価を必要とする一方、SPSA は 2 回だけで、しかも反復回数あたりの精度はかなり近い。SPSA は 160 回の損失評価で済んだのに対し、FDSA は 65,920 回だったとされる。

ここが SPSA 誕生の本当の動機である。
「各方向を1個ずつ測るのは高次元では重すぎる。では、全部を同時に動かしてしまえないか？」
この発想が SPSA の出発点である。

SPSAのアイデア

SPSA は Simultaneous Perturbation Stochastic Approximation の略で、日本語で言えば「同時摂動による確率近似」くらいの意味になる。

FDSA が各成分を1つずつ摂動するのに対して、SPSA は 全成分を同時にランダムに摂動する。SPSA の勾配近似は

$$
\hat g_{ki}(\hat u_k) =
\frac{y(\hat u_k + c_k \Delta_k) - y(\hat u_k - c_k \Delta_k)}
{2 c_k \Delta_{ki}}
$$

と与えられている。ここで $\Delta_k=(\Delta_{k1},\dots,\Delta_{kp})^T$ は、各成分がランダムな摂動ベクトルである。

この式を見て最初に驚くのは、分子がすべての成分で共通だという点だ。つまり、損失関数の評価は

$$
y(\hat{u}_k+c_k\Delta_k),\quad y(\hat{u}_k-c_k\Delta_k)
$$

の 2 回だけでよい。各成分ごとに別々の評価をする必要がない。これが SPSA の革命的なところである。SPSA は問題の次元に関係なく、勾配近似に必要な損失測定が 2 回だけで済むことが「本質的特徴」である。

斜め方向に動かすとはどういうことか

直感的に言えば、FDSA は

• $u_1$ 方向を測る
• $u_2$ 方向を測る
• $u_3$ 方向を測る
• …

というように、軸方向を順に調べる手法である。

それに対して SPSA は、たとえば

$$
\Delta_k=(1,-1,1,-1,\dots)
$$

のようなランダムベクトルを作り、

$$
\hat{u}_k+c_k\Delta_k,\quad \hat{u}_k-c_k\Delta_k
$$

という 斜め方向の2点 だけを評価する。
このとき、損失の変化量には各方向の勾配情報が全部混ざって入る。SPSA は、その混ざった情報を $\Delta_{ki}$ で割ることで、各成分の勾配を推定する。

FDSA は低ノイズ下ではほぼ最急降下方向に進むが、SPSA はランダムな方向に少し「ぶれ」ながら進む。しかし、そのぶれは反復を重ねると平均化され、最終的には FDSA と同程度の精度で解に近づくというのが本質である。

SPSA の更新式

SPSA 全体は、一般的な確率近似の再帰式

$$
\hat{u}_{k+1}=\hat{u}_k-a_k\hat{g}_k(\hat{u}_k)
$$

という形をしている。つまり、勾配ベクトル $\hat{g}_k$ を近似して、それを使ってパラメータを更新する。

ここで重要なのは、

• $\hat{g}_k$ は真の勾配ではなく、2回の損失評価から作った推定値
• $a_k$ は、更新幅を表す ゲイン列
• $c_k$ は、どれだけ離れた点で損失を測るかを表す 摂動幅

という点である。

SPSA の具体的なアルゴリズムの流れ

SPSA の1反復を順番に書くとこうなる。

Step 1. 初期化と係数設定

まず反復番号 $k=1$ とし、初期値 $\hat{u}_1$ を決める。あわせて、ゲイン列に使う係数

$$
a,\ c,\ A,\ \alpha,\ \gamma
$$

を設定する。

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

Step 2. 同時摂動ベクトル $\Delta_k$ を生成

$p$ 次元ベクトル $\Delta_k$ をランダムに作る。各成分 $\Delta_{ki}$ は独立に生成する。各成分が独立な 対称 Bernoulli $\pm1$ 分布をとるのが簡単で理論的にも有効である。

Step 3. 2点で損失を評価

次の2点で損失を測る。

$$
y(\hat{u}_k+c_k\Delta_k),\qquad y(\hat{u}_k-c_k\Delta_k)
$$

ここで使う評価は 2回だけ。これが SPSA の最重要ポイントである。

Step 4. 勾配を近似

各成分について

$$
\hat g_{ki} =
\frac{y(\hat u_k + c_k \Delta_k) - y(\hat u_k - c_k \Delta_k)}
{2 c_k \Delta_{ki}}
$$

を計算する。分子は共通なので、2回の評価から $p$ 次元全部の勾配近似が得られる。

Step 5. パラメータ更新

推定勾配を使って

$$
\hat{u}_{k+1}=\hat{u}_k-a_k\hat{g}_k
$$

と更新する。

Step 6. 繰り返し

収束するまで反復する。連続する反復でほとんど変化がなくなったときや、最大反復回数に達したときを終了の目安としている。

8. ハイパーパラメータは何をしているのか

SPSA を実際に使ううえで大切なのが、各パラメータの意味である。ここは論文の式に沿って整理すると混乱しにくい。

• $a_k$：更新の大きさ

$$
a_k=\frac{a}{(A+k)^\alpha}
$$

これは、勾配推定を使ってどれだけパラメータを動かすかを決める量である。

• $a$：全体のスケール
• $A$：初期の更新を安定させるための定数
• $\alpha$：反復が進むにつれて更新をどのくらい減らすかを決める指数

$a_k$ が大きすぎると更新が荒くなり、発散や振動の原因になる。小さすぎると動きが鈍くなる。ゲイン列の選び方は性能にとって極めて重要である。

• $c_k$：摂動の大きさ

$$
c_k=\frac{c}{k^\gamma}
$$

これは、現在の点からどれだけ離れた位置で損失を測るかを決める。

• $c$：初期の摂動幅
• $\gamma$：反復が進むにつれて摂動幅をどのくらい小さくするか

$c_k$ が大きすぎると、勾配の局所情報というより広い範囲の差を見てしまう。小さすぎると、ノイズに埋もれて差分が不安定になる。だから $c_k$ も重要である。

• $\Delta_k$：ランダム方向

$\Delta_k$ は、全成分を同時にどう動かすかを決めるランダムベクトルである。理論条件として

• 各成分が独立
• 0 を中心に対称
• 逆数モーメント $E(|\Delta_{ki}|^{-1})$ が有限

であることが挙げられている。その具体例として、対称 Bernoulli $\pm1$ が条件を満たす。逆に、一様分布や正規分布はこの条件を満たさない。

さらに、漸近的な観点から Bernoulli $\pm1$ が最適であることにも触れられている。

理論的にどこがすごいのか

SPSA の魅力は「2回で済む」というだけではない。もっと重要なのは、2回しか評価しないのに、FDSA と同程度の統計的精度を達成できるという点である。

適切な条件の下で SPSA には収束性があり、漸近正規性も成り立つ。そして FDSA との比較として、同じ平均二乗誤差の水準を達成するために必要な損失評価回数の比が

$$
\frac{\text{No. of measurements of }L(u)\text{ in SPSA}}
{\text{No. of measurements of }L(u)\text{ in FDSA}}
\to
\frac{1}{p}
$$

になる。これは、1反復あたりの $p$ 倍の節約が、そのまま全体最適化でも $p$ 倍の節約になることを意味する。

この結果を言い換えると、

properly chosen simultaneous random change in all variables provides as much information for optimization as a full set of one-at-a-time changes

つまり、全変数を同時にうまくランダムに動かした1回の情報は、各変数を1個ずつ動かした一式の情報に匹敵する、というのが SPSA の核心である。

なぜそんなことが可能なのか

SPSA のランダム方向は、1回ごとに見ると「正しい勾配方向」からずれている。しかし、そのずれはランダムであり、しかも勾配推定は ほぼ不偏（almost unbiased） であるため、反復を重ねるとその誤差が平均化される。結果として、長い目で見ると FDSA と同程度の精度で進める。

言い換えると、FDSA は「各軸方向をきっちり個別に測る」方式で、SPSA は「斜め方向に雑に見える1回の情報をたくさん集めて平均化する」方式である。前者は1回が高コスト、後者は1回が安く、その代わり確率的である。この設計思想の違いが本質である。

SPSA が向いている問題

SPSA の利点として

• 実装が簡単
• 損失の勾配が不要
• 理論と実験の両面で効率性が支持されている
• ノイズに対して頑健
• 応用範囲が広い

ことが挙げられている。さらに、連続変数問題に主として適しており、特に 損失測定にノイズが含まれる状況で有効である。

実際の応用例として、交通信号制御、兵器ターゲティング、地中物体位置推定、ニューラルネットワーク学習、制御、パターン認識などが挙げられている。

この特徴をいま風に言い換えると、SPSA は

• 勾配が直接取れない
• 1回の損失評価が高い
• 次元が高い
• ノイズがある

という環境でとても魅力的である。だから量子回路最適化や VQE とも相性が良い。

実装時に覚えておくべき最小セット

研究で SPSA を使うとき、最低限自分で言えるようにしておきたい内容は次の通り。

1. 目的
   損失関数 $L(u)$ を最小化したいが、勾配は直接使えない。

2. FDSA の問題
   各方向を1つずつ測るので、1反復に $2p$ 回の損失評価が必要。

3. SPSA の発想
   全方向を同時にランダムに動かし、2回の損失評価だけで勾配全体を推定する。

4. 中心式

$$
\hat g_{ki} =
\frac{y(\hat u_k + c_k \Delta_k) - y(\hat u_k - c_k \Delta_k)}
{2 c_k \Delta_{ki}}
$$

5． 更新式

$$
\hat{u}_{k+1}=\hat{u}_k-a_k\hat{g}_k
$$

6．ゲイン列

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

7． 摂動分布
$\Delta_{ki}$ は独立な対称 Bernoulli $\pm1$ が基本。

これが頭に入っていれば、SPSA の説明で大きく困ることはかなり減る。

一言で言うと SPSA とは何か

SPSA を一言でまとめるなら、

「高次元・ノイズあり・勾配不明な最適化問題に対して、全変数を同時にランダム摂動し、2回の損失評価だけで勾配を近似して進む確率的最適化法」

である。

FDSA のように各軸を順に測るのではなく、斜め方向の情報を確率的に使い回して、評価回数を劇的に減らす。
その代わり各反復の方向は少しぶれるが、そのぶれは反復の中で平均化される。
そして理論的にも、実用上も、FDSA に対して大きな効率上の利点がある。

参考文献

1. James C. Spall, "Implementation of the Simultaneous Perturbation Algorithm for Stochastic Optimization," Johns Hopkins APL Technical Digest, 1998.
2. James C. Spall, "An Overview of the Simultaneous Perturbation Method for Efficient Optimization," Johns Hopkins APL Technical Digest, Vol. 19, No. 4, 1998.