本記事では、「Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances」という論文を簡単に紹介する。
＊本記事で使用している画像は論文中のものである。
論文要点
- 近年の非凸・非凹のmin-max問題の応用例を選択的にレビュー
- 非凸・非凹のmin-max問題の理論的・アルゴリズに関する進展を選択的にレビュー
- 未解決問題、今後の研究の方向性を共有
min-max問題の設定
まずは、min-max問題について以下にまとめる。
min-max 問題
\begin{align}&\min_{\mathbf{x}} \max_{\mathbf{y}} f(\mathbf{x}, \mathbf{y}) \\ &\mathbf{s.t.}~~~\mathbf{x} \in \mathcal{X} \subseteq \mathbb{R}^{d},~~\mathbf{y} \in \mathcal{Y} \subseteq \mathbb{R}^{b}&\end{align}
ここで、それぞれ以下のように設定する。
- \(f(\cdot, \cdot) : \mathbb{R}^{d} \times \mathbb{R}^{b} \to \mathbb{R}\)で微分可能かつLipschitz連続な勾配を持つ
- 興味がある問題は、\(\mathbf{x}\)に関して非凸で\(\mathbf{y}\)に関して非凹な関数
- \(\mathbf{x} \in \mathbb{R}^{d}\)と\(\mathbf{y} \in \mathbb{R}^{b}\)は最適化変数
- \(\mathcal{X}\)と\(\mathcal{Y}\)は実行可能領域 : 閉凸集合を仮定
上記の設定で\(\mathbf{x}\)に関して凸かつ\(\mathbf{y}\)に関して凹の場合は、様々なアルゴリズムが提案されているが、非凸のケースのmin-max問題の解くのは依然として困難である。
しかし、近年、非凸・非凹なmin-max問題は、さまざまな分野に応用されている。
具体例（詳細は、原論文参照）
- ロバスト性を持つトランシーバ設計
- Jammerが存在する状況下での情報通信
- 公平性のAI
- 機械学習のロバスト学習
- 敵対的事例
- 敵対的生成ネットワーク（GANs）
より一般的には、モデルの不確実性が存在する場合または敵対者が存在する場合に、モデルのパラメータを決定する問題は、Min-Max問題の形でモデル化することができる。この場合、\(\mathbf{y}\)は、正確に推測不可能な不確実さを表すパラメータ、または敵対的に調整されるパラメータに対応する。
この設定に対して、min-max問題の解\(\mathbf{x} = \bar{\mathbf{x}}\)は、不確実さ/敵対的なパラメータ\(\mathbf{y} \in \mathcal{Y}\)の全ての値に対してロバストな性能を持つことが期待される。
このようなロバスト性は、信号の分野では古くから重要視されている。最近は、機械学習のモデル設計において重要な役割を担っている。
non-convex min-max問題の問題点
まず、min-max問題の難しさを確認するために通常の滑らかな非凸最適化問題と比較を行う。
ここで、関数\(h\)の勾配がLipschitz連続である通常の滑らかな非凸最適化問題を考える:
$$\min_{\mathbf{z} \in \mathcal{Z}} h(\mathbf{z})$$
このような非凸最適化問題の大域的最適解を探索することは困難だが、射影勾配降下法 (Projected Gradient Descent ;PGD) 等の簡単な反復アルゴリズムを実行することで、穏やかな仮定のもとで、一次の最適性条件を満たす停留点に到達することが知られている。
PGDは、具体的には以下のようなアルゴリズムである。
$$\mathbf{z}^{t+1} = \mathcal{P}_{\mathcal{Z}}(\mathbf{z}^{t} – \alpha \nabla h(\mathbf{z}^{(t)}))$$
ここで、\(t\)は反復回数を表すインデックス、\(\mathcal{P}_{\mathcal{Z}}\)は集合\(\mathcal{Z}\)への射影, \(\alpha\)はステップサイズを表す。
非凸な最適化問題関しても、このようなアルゴリズムを使用することで、「それなりに良い解（一次最適性条件を満たすような点）」が得られることを期待できる。
しかし、一般の非凸なmin-max問題を解くために広く汎用的な最適化ツールは存在しない。また、最適性条件の概念自体も一意ではない。
そのことを説明するために、PGDをmin-max問題の設定に単純に拡張した勾配降下上昇法（gradient-descent ascent algorithm; GDA）を考える。
\begin{align} \mathbf{x}^{t+1} &= \mathcal{P}_{\mathcal{X}}(\mathbf{x}^{t} – \alpha \nabla_{\mathbf{x}} f(\mathbf{x}^{t}, \mathbf{y}^{t})) \\ \mathbf{y}^{t+1} &= \mathcal{P}_{\mathcal{Y}}(\mathbf{y}^{t} + \alpha \nabla_{\mathbf{y}} f(\mathbf{x}^{t+1}, \mathbf{y}^{t})) \end{align}
ここで、\(\mathcal{P}_{\mathcal{X}}\), \(\mathcal{P}_{\mathcal{Y}}\)はそれぞれ\(\mathcal{X}\), \(\mathcal{Y}\)への射影を表す。
このアルゴリズムはよく使用されるが、多くの実用例で失敗することが知られている。また、意味のある停留点に収束しない例を構成することは容易である。
近年の非凹凸min-max問題のアルゴリズムの選択的なレビュー
ここからは、近年開発された非凹凸min-max問題のアルゴリズムを選択的に紹介する。
しかし、これらのアルゴリズムを理解するためには、min-max問題に対する定常性や最適性条件を議論する必要があり、最初にこれらを議論する。
その後、新たなアルゴリズム開発につながるいくつかのアイデアを共有する。
min-max問題の最適性条件ついて
非凸なmin-max問題は非凸性に起因して、一般に大域解を求めることはNP困難である。そのため、この問題の主な目的は、停留点を求めることであり、そのようなアルゴリズムが発展してきた。
しかし、min-max問題に対する最適性条件は一つではなく複数考えられる。
その中でも最も一般的な二つを以下で紹介する。
ゲーム最適性条件
定常性の概念を定義するための一つの方法は、min-max問題を『ゲーム』と見なすことである。
すなわち、min-maxの順番を無視して、2人プレイヤーによる零和ゲームとして考える。2人プレイヤーによる零和ゲームでは、一方のプレイヤーは\(\min_{\mathbf{x}} f(\mathbf{x}, \mathbf{y}\)を解き、もう一方のプレイヤーは\(\max_{\mathbf{y}} f(\mathbf{x}, \mathbf{y})\)を解くことに興味がある。
しかし、目的関数の非凸性から大域的なナッシュ均衡解を求めることは困難である。そのため、それぞれの以下の一次の最適性条件を満たす点を見つけることが目的となる。
ゲーム最適性条件（Game-Stationary）
\begin{align} &\langle \nabla_{\mathbf{x}} f(\bar{\mathbf{x}}, \bar{\mathbf{y}}), \mathbf{x} – \bar{\mathbf{x}} \rangle \ge 0, \forall \mathbf{x} \in \mathcal{X} \\ &\langle \nabla_{\mathbf{y}} f(\bar{\mathbf{x}}, \bar{\mathbf{y}}), \mathbf{y} – \bar{\mathbf{y}} \rangle \le 0, \forall \mathbf{y} \in \mathcal{Y} \end{align}
この最適性条件は、「疑ナッシュ均衡」や「一次ナッシュ均衡」と呼ばれる。
さらに、固定点定理を用いることで、現実的な仮定の下でゲーム最適性条件を満たす点が存在することを示すことができる。その存在性に加えて、与えられた点がこの最適性条件を満たすか判定することが容易であり、多くの研究者がこの条件を満たす点を探索するアルゴリズム開発に注目している。
しかし、この最適性条件は、min-maxの順序関係を無視している点に注意する。Sionのmin-max定理より\(f(\mathbf{x}, \mathbf{y})\)が\(\mathbf{x}\)がコンパクトかつ凸, \(\mathbf{y}\)に関して凹かつコンパクトの場合はmin-maxの順序を交換できるが、一般的な非凸なmin-max問題は、順序交換は不可能であり、異なる解を持つ可能性がある。そのため、minとmaxの順序が重要となる応用では実用的でないことが示唆されている。
最適化最適性条件
min-maxの純アバンを考慮するため、異なる最適性条件を導入する。まず、min-max問題を以下の形式に書き換える。
$$\min_{\mathbf{x} \in \mathcal{X}} g(\mathbf{x})$$
ここで、\(\mathbf{x} \in \mathcal{X}\)のとき、\(g(\mathbf{x}) := \max_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y}) \)として、\(\mathbf{x} \notin \mathcal{X}\)のとき\(g(\mathbf{x}) = + \infty\)とする。
この観点から、最適性条件を非凸非平滑な最適化問題の一次最適性条件として定義する。
最適化最適性条件（Optimization-Stationary）
$$\mathbf{0} \in \partial g(\bar{\mathbf{x}})$$
ここで、\(\partial g(\bar{\mathbf{x}})\)はフレシェ劣微分（Frechet sub differential）で以下のように定義される。
$$\partial g(\bar{\mathbf{x}}) := \left\{\mathbf{v} \mid \lim \inf_{\mathbf{x}^{\prime} \mapsto \mathbf{x}} \frac{g(\mathbf{x}^{\prime})-g(\mathbf{x})-\langle \mathbf{v}, \mathbf{x}^{\prime} – \mathbf{x} \rangle}{\|\mathbf{x}^{\prime} – \mathbf{x}\|} \ge 0 \right\}$$
この条件の存在性も現実的な仮定（実行可能領域がコンパクトかつ\(f\)が連続のような）のもと示される。
さらに、min-max問題の大域的最適解は、ゲーム最適性条件を満たさない場合もあるが、最適化最適性条件は必ず満たされる。しかし、\(\mathbf{y}\)に関して\(f(\mathbf{x}, \mathbf{y})\)が凹かつその勾配がリプシッツ連続な場合、ゲーム定常条件と最適化定常条件が一致する。
しかし、最適化最適性条件の批判として、非凸なmin-max問題に対して、与えられた点\(\bar{\mathbf{x}}\)が、最適化最適性条件を満たしているかを確認することが計算量的に困難となることが挙げられている。
非凹凸min-max問題のアルゴリズム
ここからは、上述の最適性条件を満たすようなアルゴリズムを紹介していく。
Potential Reductionに基づく方法
min-max問題に対して、最適化定常条件で定義した関数\(g(\mathbf{x})\)は、最小化すべき自然なポテンシャルである。しかし、一次最適性条件を満たす点を標準的なアルゴリズムにより探索するためには、\(g(\mathbf{x})\)の（劣）勾配を計算する必要がある。
関数\(g(\cdot)\)を閉じた形で表すことはできないが、与えれた点で勾配を評価することは以下のDanskinの定理により可能な場合がある。
Danskinの定理
任意の\(\mathbf{x}\in\mathcal{X}\)に対して\(f(\mathbf{x}, \mathbf{y})\)は\(\mathbf{x}\)に関して微分可能とする。さらに、コンパクト集合\(\mathcal{Y}\)上で\(f(\mathbf{x}, \mathbf{y})\)は\(\mathbf{y}\)に関して強凹関数とする。
このとき、\(\mathbf{g}(\mathbf{x})\)は\(\mathbf{x}\)に関して微分可能であり、任意の\(\mathbf{x}\in\mathcal{X}\)に関して以下が成り立つ。
$$\nabla g(\mathbf{x}) = \nabla_{\mathbf{x}} f(\mathbf{x}, \mathbf{y}^{\ast}(\mathbf{x}))$$
ここで、以下のように定義した。
$$\mathbf{y}^{\ast}(\mathbf{x}) = \mathrm{argman}_{\mathbf{y}} f(\mathbf{x}, \mathbf{y})$$
この定理は、\(f(\cdot, \cdot)\)の勾配を評価することで\(g(\mathbf{x})\)の勾配が計算できることを意味している。従って、Danskinの定理が適用可能な場合、GDAアルゴリズムを改良した以下のアルゴリズムが考えられる。
\begin{align} \mathbf{y}^{t+1} &= \mathrm{argmax}_{\mathbf{y}} f(\mathbf{x}^{t}, \mathbf{y}) \\ \mathbf{x}^{t+1} &= \mathcal{P}_{\mathcal{X}}(\mathbf{x}^{t} – \alpha \nabla f(\mathbf{x}^{t}, \mathbf{y}^{t+1}) \end{align}
第二式に関しては、Danskinの定理より以下を計算するのと等価である。
$$\mathbf{x}^{t+1} = \mathcal{P}_{\mathcal{X}}(\mathbf{x}^{t} – \alpha \nabla g(\mathbf{x}^{t}))$$
問題となるのは、\(\mathbf{y}\)で厳密な最適解を求める必要がある。しかし、以下のアルゴリムを用いることで、\(\varepsilon\)の精度で定常解を探索することができる。
\begin{align} \mathrm{Find}~\mathbf{y}^{t+1}~&\mathrm{s.t.}~f(\mathbf{x}^{t}, \mathbf{y}^{t+1}) \ge \max_{\mathbf{y}} f(\mathbf{x}^{t}, \mathbf{y}) – \varepsilon \\ \mathbf{x}^{t+1} &= \mathcal{P}_{\mathcal{X}}(\mathbf{x}^{t} – \alpha \nabla f(\mathbf{x}^{t}, \mathbf{y}^{t+1}) \end{align}
さらに、\(\mathbf{y}^{t+1}\)に関して上記の探索が可能ならば、強凹性の仮定さえ緩和することができる。それ以外にも様々な手続きによりアルゴリズムの収束率を改善する研究がある。
一般に非凸なmin-max問題は、\(\mathbf{y}^{t+1}\)に関する探索は困難である。しかし、この探索が容易な関数になるように目的関数を近似することで実行可能になる可能性はある。
finite max approximationに基づく方法
関数\(f(\mathbf{x}, \mathbf{y})\)が\(\mathbf{y}\)に関して凹関数の場合は、以下の有限のmax問題を解く方法が考えられる。
$$\min_{\mathbf{x} \in \mathcal{X}} \max \{f_{1}(\mathbf{x}), \ldots, f_{n}(\mathbf{x})\}$$
この問題は以下のように書き換えることができる。
$$\min_{\mathbf{x} \in \mathcal{X}} \max_{\mathbf{y} \in \Delta} \sum_{i=1}^{n} y_{i} f_{i}(\mathbf{x})$$
ここで、\(\Delta \equiv \{\mathbf{y} \mid \mathbf{y}, \sum_{i=1}^{n} y_{i} = 1\}\)と定義した。
そして、この変形により内部最大化は、\(\mathbf{y}\)に関して凹関数となり、Danskinの定理に基づく方法が使用できる。
この考え方は、敵対的学習にも応用され既存の方法と同等、またはそれ以上の性能を見せている。
それ以外にも\(\mathbf{y}\)に間んして凹関数となるような正則化を与える方法が提案されている（WGANなど）
Inexact proximal point（IPP）method
次に、ゲーム定常条件の概念を用いたアルゴリズムを紹介する。
まず、ゲーム定常条件が以下のようにまとめられる。
$$\langle F(\bar{\mathbf{z}}, \mathbf{z} – \bar{\mathbf{z}}) \rangle \ge 0,~~\forall \mathbf{z} \in \mathcal{Z}$$
ここで、\(\mathcal{Z} := \mathcal{X} \times \mathcal{Y}\), \(\mathbf{z} = [\bar{\mathbf{x}}~~\bar{\mathbf{y}}]^{\top}\)とし、\(F(\cdot)\)を以下のように定義した。
$$F(\bar{\mathbf{z}}) := \left[\nabla_{\mathbf{x}} f(\bar{\mathbf{x}}, \bar{\mathbf{y}})~~-\nabla_{\mathbf{y}} f(\bar{\mathbf{x}}, \bar{\mathbf{y}}) \right]$$
目的関数が\(\mathbf{x}\), \(\mathbf{y}\)に関して強凸・凹ならば、\(F(\mathbf{z})\)は強単調となり、上記の条件を満たす解を勾配ベースのアルゴリズムによって得ることができる。
しかし、一般に非凸・凹の場合は、\(F(\mathbf{z})\)は強単調とはならない。そこで、\(F(\cdot)\)を強単調な写像で近似する考え方が導入された。
Inexact Proximal point（IPP） method
- \(F^{\gamma}_{\mathbf{z}^{r}}(\mathbf{z}) = F(\mathbf{z}) + \gamma^{-1} (\mathbf{z} – \mathbf{z}^{r}) \)
- \(\mathbf{z}^{r+1}\)を\(F_{\mathbf{z}^{r}}^{\gamma}(\cdot)\)の解とする
\(\gamma\)は\(F_{\mathbf{z}^{r}}^{\gamma}(\mathbf{z})\)が強単調となるように小さな値を選ぶ。さらに以下の勾配ベースのアルゴリズムと組み合わせる。
- \(\mathbf{z}^{t+1} = \mathcal{P}_{\mathcal{Z}}(\mathbf{z}^{t} – \beta F(\mathbf{z}^{t}))\)
この二重ループのプロセスは、ゲーム定常状態に到達することを保証しないが、以下のMinty 条件を満たす\(\mathbf{z}^{\ast}\)を得ることができる。
Minty Condition
$$\langle F(\mathbf{z}), \mathbf{z} – \mathbf{z}^{\ast} \rangle \ge 0,~~~\forall \mathbf{z} \in \mathcal{Z}$$
ゲーム定常状態との違いは、左辺が\(F(\bar{\mathbf{z}})\)ではなく\(F(\mathbf{z})\)となる点である。この条件は、\(\mathcal{Z}\)が凸集合の場合一致する。
しかし、この方法はpotential basedな方法に比べると多くの問題をカバーすることはできない。
また、この方法はmin-maxの順番を無視しているため、min-maxの順序が重要となる問題に敵お用することはできない。
Algorithms Using Single-Loop Update
min-max問題に対して、同時または交互に繰り返すようなアルゴリズム（single loop algorithm）は、単純な線形問題でさえ、目的関数の値が発散することがあるが、実用的には好まれる。
この問題を解決するために提案されたのが、Hybrid Block Successive Approximation（HiBSA）であり、以下のように定義される。
$$\begin{align} \mathbf{x}^{t+1} &= \mathcal{P}_{\mathcal{X}}(\mathbf{x}^{t} – \beta^{t} \nabla_{\mathbf{x}} f(\mathbf{x}^{t}, \mathbf{y}^{t}) \\ \mathbf{y}^{t+1} &= \mathcal{P}_{\mathcal{Y}}((1+ \gamma^{t} \rho) \mathbf{y}^{t} + \rho \nabla_{\mathbf{y}} f(\mathbf{x}^{t+1}, \mathbf{y}^{t}) \end{align}$$
ここで、\(\beta^{t}, \rho > 0\)で学習率に対応し、\(\gamma^{t}> 0\)は摂動パラメータを表す。
HiBSA の反復は、勾配降下と上昇のステップが交互に実行されるsingle loop アルゴリズムである。
勾配上昇下降法との重要な違いは、\(\mathbf{y}\)の更新に追加項\(\gamma^{t} \rho \mathbf{y}^{r}\)が含まれる点である。
摂動後の新しい反復\(\mathbf{y}^{r+1}\)は古い反復\(\mathbf{y}^{r}\)により近くなり、望ましい解へ収束しやすくなる。
直感的には、摂動が最終的にゼロになり、このアルゴリズムは望ましい解に収束する。
具体的には、\(f(\mathbf{x}, \mathbf{y})\)が\(\mathbf{y}\)関して強凹関数の場合場合、摂動項を削除するだけで、HiBSAはゲーム最適性条件を満たす点に収束することが示されている。
さらに、\(f(\mathbf{x}, \mathbf{y})\)が \(\mathbf{y}\)に関して凹関数の場合、\(\beta^{r} = \mathcal{O}(1/r^{1/2})\), \(\gamma^{r} = \mathcal{O}(1/r^{1/4})\)を選べば、最適性条件を満たす点に収束することが知られている。
Extension to Zeroth-order Based Algorithm
これまで、レビューしたすべてのアルゴリズムは、一次（勾配）情報を必要とする。
ここで紹介するアルゴリズムは、0次（ZO）情報のみが利用可能な場合に有益なアルゴリズムである。すなわち、与えられた点\((\mathbf{x}, \mathbf{y})\)における目的関数の値\(f(\mathbf{x}, \mathbf{y})\)を各反復毎に入手さえできれば良い。
このタイプのアルゴリズムは、攻撃者が機械学習モデルの出力のみアクセス可能な状況の敵対的攻撃に利用可能である。
ZOアルゴリズムを設計するためには、勾配\(\nabla h(\mathbf{x})\)を推定するのが一般的である。最も一般的な推定値は以下で与えられる。
$$\hat{\nabla}_{\mathbf{x}}h(\mathbf{x}) = \frac{1}{q} \sum_{i=1}^{q} \frac{d[h(\mathbf{x} + \mu \mathbf{u}_{i}) – h(\mathbf{x}]}{\mu} \mathbf{u}_{i}$$
ここで、\(\{\mathbf{u}_{i}\}_{i=1}^{q}\)は、単位球から一様に生成された確率変数である。また、\(\mu\)は平滑パラメータ（smoothing parameter）と呼ばれている。
min-max問題に対しては、この勾配推定方法を用いて、上述で紹介したHiBSA等の勾配ベースの使用する方法が提案されている。
まとめ
以下の図にMinty最適性条件、最適化最適性条件、ゲーム最適性条件の関係性をまとめる。
次に、異なるアルゴリズムの収束条件や最適化基準などの特性を以下で比較する。
最適化条件の間に同値の可能性があるにもかかわらず、「最適化基準」の列を残しているのは、これが本来アルゴリズムが設計される際の基準であるためである。
- Multi-Step GDA : ゲーム定常条件（仮定 : \(\mathbf{x}\)に関して非凸かつ\(\mathbf{y}\)に関して凹）
- CDIAG : 最適化定常状態（仮定 : \(\mathbf{x}\)に関して非凸かつ\(\mathbf{y}\)に関して凹）
- IPP : Minty定常条件 : （仮定 : \(\mathbf{x}\)に関して非凸かつ\(\mathbf{y}\)に関して非凹）
- GDA : 最適化定常状態（仮定 : \(\mathbf{x}\)に関して非凸かつ\(\mathbf{y}\)に関して凹）
- HiBSA : ゲーム定常状態（仮定 : \(\mathbf{x}\)に関して非凸かつ\(\mathbf{y}\)に関して凹）
また、以下に現段階で残された非凹凸min-max問題の課題と将来の研究の方向性をまとめる。
- より緩い仮定で収束するアルゴリズム開発 : 現代で解ける（ゲーム最適性条件または、最適化最適性条件に到達する）問題クラスは非常に限定的
- 解に十分近い領域で初期化した際に局所収束するアルゴリズム開発
- 非平滑でない場合のアルゴリズム開発（e.g. 近接勾配を使用する）
- min-max解のロバスト性を証明する理論・方法論 : min-max問題の一般的な応用は、敵対的な状況下でロバストなシステムを構築することである。しかし、min-max問題の解がロバスト性を保証するかは非自明である
- より収束率の良いアルゴリズム開発 : 勾配情報を用いた最適な収束率はまだ評価されていない
- または、へシアン等の情報を用いたより効率的なアルゴリズム開発
