# 凸最適化 ## 定義 凸最適化とは、目的関数 $f(x)$ と不等式制約 $g_i(x)\le0$ がいずれも凸関数、等式制約 $h_j(x)=0$ が凸集合であるような制約付き最小化問題 $\min_x f(x)$ s.t. $g_i(x)\le0\ (i=1,\dots,m),\ h_j(x)=0\ (j=1,\dots,n)$ を指す。凸集合とは任意の2点 $x,y$ を結ぶ線分 $\theta x+(1-\theta)y\ (0\le\theta\le1)$ が集合内に収まる集合であり、凸関数とは任意の2点を結ぶ直線がグラフより上にある($f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)$、Jensenの不等式)関数である。微分可能な関数では1次条件 $f(y)\ge f(x)+\nabla_xf(x)^\top(y-x)$、2階微分可能なら海森行列(Hessian)の半正定値性が凸性の判定条件になる。凸最適化問題では**強双対性**(ラグランジュ主問題と双対問題の最適値が一致する)が成り立ち、局所最小値がすべて大域最小値になる。線形計画(目的・制約とも線形)と二次計画(目的が正定値2次形式、制約がアフィン)は凸最適化の代表的な特殊ケースであり、いずれもラグランジュ乗数を用いて解析的に双対問題を導出できる。ルジャンドル・フェンシェル変換(凸共役)$f^*(s)=\sup_x(\langle s,x\rangle-f(x))$ は、凸性・微分可能性を仮定しない一般的な双対化の手段であり、ラグランジュ双対と関連しつつ独立に双対問題を導出できる。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] §7.2, §7.3) ## 横断的知見 - **第12章(サポートベクターマシン)は、本conceptの二次計画・ラグランジュ双対の一般論を、SVMという具体的な二次計画問題に適用する実例を与える**: 第7章はラグランジュ双対性を「目的関数・不等式制約がいずれも凸」という抽象的な条件で導入するのに対し、第12章§12.3.1はソフトマージンSVMの主問題(式12.26、目的関数 $\frac12\|w\|^2+C\sum\xi_n$、制約 $y_n(\langle w,x_n\rangle+b)\ge1-\xi_n$)にラグランジュ乗数 $\alpha_n,\gamma_n$ を割り当ててラグランジアンを構成し、主変数 $w,b,\xi$ に関する偏微分をゼロと置くことで具体的な双対問題(式12.41: $\min_\alpha\frac12\sum_{i,j}y_iy_j\alpha_i\alpha_j\langle x_i,x_j\rangle-\sum_i\alpha_i$ s.t. $\sum_iy_i\alpha_i=0,0\le\alpha_i\le C$)を導出する。この手順は第7章§7.2の一般的なラグランジュ双対の処方箋(ラグランジアン構成→主変数で偏微分→ゼロ点を代入して主変数を消去)をそのままなぞっており、SVMの箱型制約 $0\le\alpha_i\le C$ は不等式制約のラグランジュ乗数の非負性条件から機械的に導かれる。さらに双対問題が主変数 $w$ を含まず例同士の内積 $\langle x_i,x_j\rangle$ のみに依存する形になる点(第7章のQP標準形には現れない、SVM双対に特有の構造)が、続くカーネル置換(カーネルトリック)を可能にする([[カーネル法]]参照)。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] §7.2, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]] §12.3.1, §12.4) - **第12章は、双対SVMの箱型制約 $0\le\alpha_i\le C$ が凸包(convex hull)間の最短距離問題としても導出できることを示し、単一のラグランジュ双対に対して幾何的な別証明が存在する例を与える**: 第7章はラグランジュ双対を代数的な操作(偏微分・ゼロ点代入)として導入するのみだが、第12章§12.3.2は同じ双対問題を「正例の凸包と負例の凸包の間の最短距離を与える差ベクトル $w=c-d$ を求める」という純粋に幾何的な問題として独立に再導出し、両者が同一の解を持つことを示す(Bennett and Bredensteiner, 2000a)。これは凸最適化の双対問題が代数的導出と幾何的導出という異なる経路から同じ解に到達しうることを具体例で裏付ける。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] §7.2, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]] §12.3.2) - **『ディープラーニングを支える技術』は、凸最適化を持つか否かをニューラルネットワークが長年軽視された歴史的理由として位置づける**: 本ページの2ソース(Mathematics for Machine Learning第7章・第12章)は凸最適化の数学的構造(強双対性・大域最適性の保証)を内在的に解説するのに対し、[[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 1 ディープラーニングと人工知能]]は1990年代に台頭した単純ベイズ法・最大エントロピー法・ロジスティック回帰・アダブースト・サポートベクトルマシン・条件付き確率場といった機械学習手法の多くが凸最適化問題を扱っており最適化(学習)や最適解への収束保証ができたのに対し、ニューラルネットワークが扱う最適化問題は非凸で学習ができることすら理論的保証がなかったため、性能面の制約(データ・計算資源の不足)と並んで長らく軽視される一因になったと述べる。凸最適化の理論的性質(局所最小値が大域最小値に一致する)そのものではなく、「この性質を持つか持たないかが、ある手法が研究コミュニティで信頼されるかどうかを左右した」という科学史的な意味づけを与える点で、本ページの数学的定義に歴史的な文脈を補う。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] §7.2, [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 1 ディープラーニングと人工知能]] §1.2) - **ch.2は、同書ch.1が示す「凸最適化の有無が研究コミュニティの評価を左右した」という歴史的視点とは別に、なぜ0/1損失という自然な損失関数が凸最適化に向かないのかを実装レベルで説明し、サロゲート損失関数(クロスエントロピー損失)を経由して間接的に凸最適化へ接続する具体的な機序を補う**: ch.1(既にこのページに反映済み)は凸最適化の有無を研究史の文脈で位置づけるにとどまるが、[[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6は、分類が正しければ0・間違っていれば1を返す0/1損失関数が「凸関数ではないという問題」を持ち、モデルが線形であっても損失関数が非凸だと全体の目的関数も非凸になり収束の速さ・解の最適性の判定などのメリットが失われると具体的に述べる(コラム「なぜ0/1損失関数は『学習』に使われないのか」)。この非凸性への対処として、0/1損失を上から滑らかな凸関数で抑えたサロゲート損失関数(クロスエントロピー損失等)を使うことが、勾配降下法による学習を可能にすると説明する。これは本ページがMML第7章・第12章から得た「凸最適化であれば強双対性・大域最適性が保証される」という一般論に対し、「そもそもなぜ自然な損失関数(0/1損失)が凸でないのか」「凸な代替(サロゲート損失)へどう置き換えるのか」という、凸最適化の枠組みに載せる前段階の設計判断を補う。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] §7.2, [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.6) - **『ディープラーニングを支える技術〈2〉』第1章は、ニューラルネットワークの目的関数が全体では凸でなくても「現在の値と最適解の間」だけ凸性が成り立つ Star-convex Path という局所的・部分的な凸性を持つことを示し、大域的凸性(第7章・第12章・前書第1章が扱う意味での凸最適化)を持たない問題でも勾配降下法が成功しうる中間的な説明を補う**: 本ページがこれまで扱ってきた凸最適化は目的関数全体が凸であることを前提とするが(強双対性・大域最適性の保証はこの前提に依存する)、[[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]] §1.1は、ニューラルネットワークの目的関数が多くの場合「Star-convex Path」(目的関数全体では凸性を満たさないが、現在の値と最適解との間にだけ凸性が成り立つ経路)を持つことが実験的にわかっていると述べる。これは全体凸性のオール・オア・ナッシングな二分法(凸か非凸か)ではなく、「初期値から最適解までの経路上でのみ凸性が成り立つ」という部分的・条件付きの凸性の概念を導入するものであり、前書第1章(§1.2)が述べた「凸最適化を持つか否かが研究コミュニティの信頼を左右した」という歴史的文脈に対し、非凸問題でも一定の構造さえあれば勾配法が機能しうるという理論的な橋渡しを与える。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] §7.2, [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 1 ディープラーニングと人工知能]] §1.2, [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]] §1.1) - **続編第1章は、低ランク行列補間・線形ニューラルネットワークという「非凸だが極小解=最適解」という特殊クラスの実例を示し、本ページが扱う凸最適化(大域最適性が構造的に保証される問題)と、非凸ながら実質的に同じ性質を持つ問題との境界を具体的に埋める**: 低ランク行列を使った行列要素補間問題や、非線形活性化関数を使わない線形ニューラルネットワークでは、目的関数がパラメータについて非凸でありながら、すべての極小解が最適解になることが証明されている(Ge et al. 2016; Kawaguchi 2016)。これは凸性という構造的性質を持たなくても「極小解=最適解」という凸最適化の帰結の一つ(局所最小値が大域最小値に一致する)だけを別の理由(パラメータ空間の対称性など)で満たす問題クラスが存在することを示し、本ページの定義(凸性→大域最適性の保証)と対をなす反例的な補足になる。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] §7.2, [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]] §1.1) ## 未解決の問い - 強双対性が成り立つための十分条件として本章はSlaterの制約想定に触れていない。KKT条件やSlater条件など、強双対性の厳密な成立条件を扱う文献との突き合わせが必要。 - 凸共役(ルジャンドル・フェンシェル変換)とラグランジュ双対はどちらも双対問題を導くが、両者が一致する条件・使い分けの実務的基準は何か(本章はExample 7.9で両者の関係を示すのみで、一般的な同値性は論じていない)。 - 深層学習の目的関数の多くは非凸だが、本章の凸最適化の道具(強双対性・大域最適性の保証)がどこまで局所的な議論(鞍点回避、初期値依存性の緩和など)に転用できるかは本章の範囲外。 - ニューラルネットワークが学習できることの理論的保証は2019年頃になって登場してきたと『ディープラーニングを支える技術』第1章の脚注が述べるが、この保証の具体的な内容(非凸最適化のどのクラスに対する保証か)は同章の範囲外である。強双対性・KKT条件など本ページが扱う凸最適化の道具とどう接続する(または接続しない)理論なのか、該当する一次文献を追って確認したい。 - Star-convex Path(続編第1章)が成り立つための十分条件(ネットワーク幅・深さ・活性化関数との関係)は何か。本ページが扱う「凸集合・凸関数の定義から強双対性を導く」という厳密な理論的枠組みとStar-convex性がどう接続するか(Star-convex性から何らかの双対性・最適性保証が導けるか)は続編第1章・本ページのいずれの範囲外であり、Zhou et al. (2019) など一次文献の確認が必要。 ## 関連 - ソース: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 7 Continuous Optimization]] / [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]](二次計画・ラグランジュ双対をSVMに具体的に適用する実例) / [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 1 ディープラーニングと人工知能]](凸最適化の有無がニューラルネットワークの評価を左右した歴史的経緯) / [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]](0/1損失の非凸性とサロゲート損失関数による回避) / [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 1 ディープラーニングの最適化]](Star-convex Path・特殊クラスでの極小解=最適解という非凸問題の部分的な凸性) - 実体: [[Mathematics for Machine Learning]] - 関連概念: [[サポートベクターマシン]](第7章の凸最適化・ラグランジュ双対を応用する具体例) / [[カーネル法]](双対SVMが内積のみに依存する構造からカーネル置換が可能になる) / [[損失関数]](サロゲート損失関数による凸化) / [[勾配降下法]](非凸最適化問題での勾配降下法の収束を条件数・Star-convex Pathの観点から扱う) ## 出典 - Deisenroth, M. P., Faisal, A. A., Ong, C. S., *Mathematics for Machine Learning*, Cambridge University Press, 2020, Chapter 7, §7.2-7.3; Chapter 12, §12.3.1-§12.3.2. - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第1章 §1.2; 第2章 §2.6. - 岡野原大輔, 『ディープラーニングを支える技術〈2〉 ニューラルネットワーク最大の謎』, 技術評論社, 2022, 第1章, §1.1.