1. Frank–Wolfe が対象とする問題
Frank–Wolfe（conditional gradient）は min_{x∈D} f(x) を解く手法で、D への射影は高価だが D 上の線形最小化は容易な場合に有効です。勾配ステップ後に射影する代わりに、線形最小化オラクルで有利な極点を選び、凸結合でそこへ移動します。
重要ポイント
- FW は一般に gradient descent より優れているのではなく、可行集合の幾何構造を利用する方法です。
- simplex、ℓ1 ball、flow polytope、matroid polytope、nuclear-norm ball などが典型です。
- 疎解・低ランク解を自然に維持したい場合にも有利です。
2. なぜ射影がボトルネックになるのか
射影勾配法は y_t=x_t−η∇f(x_t) の後に min_{x∈D} ‖x−y_t‖² を解きます。box なら簡単ですが、構造化集合では射影が高価な最適化や行列分解になることがあります。FW はこれを線形最適化に置き換えます。
重要ポイント
- ℓ1 ball では射影に thresholding が必要ですが、LMO は最大絶対勾配の座標と符号を選ぶだけです。
- nuclear-norm ball では射影に大規模 SVD が必要ですが、LMO は先頭 singular vector pair だけで済みます。
3. Linear Minimization Oracle：中心となる演算
x_t で勾配は局所増加方向なので、FW は s_t=argmin_{s∈D}⟨∇f(x_t),s⟩ を解きます。これは一次近似の下で最良の可行点を選ぶ操作です。凸多面体では線形目的の最適解は通常極点にあり、s_t は atom/vertex になります。
重要ポイント
- LMO は可行集合と勾配だけに依存し、専用の組合せ最適化を利用できます。
- 確率 simplex では最小勾配成分の頂点を選びます。
- flow polytope では shortest path や min-cost flow に帰着できる場合があります。
4. 基本 Frank–Wolfe 反復
LMO で s_t を得たら d_t=s_t−x_t とし、x_{t+1}=x_t+γ_t d_t, γ_t∈[0,1] と更新します。凸結合なので可行性が自動的に保たれ、射影が不要です。
重要ポイント
- 1回の FW step で active representation に追加される atom は高々1つです。
- この増分表現により早期から疎な混合や低ランク行列を得やすくなります。
- γ_t=1 なら過去点を捨て、γ<1 なら過去 atom の重みを保持します。
5. Step size：規則か line search か
step size は新 atom へどれだけ移動するかを決めます。古典則 γ_t=2/(t+2)、1次元最適化が安ければ exact line search、あるいは smoothness 推定に基づく adaptive rule が使えます。
重要ポイント
- step が小さすぎると LMO を浪費し、大きすぎると頂点間で振動しやすくなります。
- 二次目的では line search が閉形式のスカラー解になることが多いです。
- step size は定数や実速度に影響しますが、長期挙動には集合の幾何が大きく効きます。
6. Frank–Wolfe gap：計算可能な最適性証明
FW gap は g_FW(x_t)=⟨∇f(x_t),x_t−s_t⟩ です。凸性から f(x_t)−f(x*)≤g_FW(x_t) が成り立つため、一階最適性指標かつ primal suboptimality の上界になります。LMO で s_t は既に求めるので追加コストも小さいです。
重要ポイント
- 目的値の変化が小さいだけでは最適性を保証できず、FW gap の方が意味が明確です。
- 非凸では FW gap は一階停留性の指標にはなりますが、大域 suboptimality 上界ではありません。
7. 古典 FW が O(1/t) で収束する理由
滑らかな凸関数とコンパクト凸集合では、curvature が一次近似誤差を制御します。descent lemma と LMO 性質から h_t=f(x_t)−f(x*) の再帰を得て、古典 step で O(1/t) が導かれます。ただし古典 FW は既存 atom の重みを減らしにくいため、polytope 上で一般に線形収束しません。
重要ポイント
- curvature constant C_f は目的関数の滑らかさと集合サイズを affine-invariant にまとめます。
- O(1/t) では漸近的に誤差を半分にするのに反復数を概ね倍にする必要があります。
- 実際の速度は iteration complexity だけでなく LMO と射影の1回コストで決まります。
8. Active set・疎性・zig-zag 問題
D が atoms の凸包なら x_t=Σ α_v v と表せ、S_t が active set です。疎表現を自然に得られますが、古典 FW は新 atom 方向へ進むだけで古い悪い atom を素早く削れず、境界最適点付近で zig-zag が起こります。
重要ポイント
- 補正をしなければ t 回後の表現 atom 数は高々 t+1 です。
- 疎混合、構造予測、低ランク行列構築に有利です。
- 一方、既存 atom の係数を大きく減らす必要がある場合は遅くなります。
9. Away-step・Pairwise・Fully Corrective FW
Away-step FW は新 atom へ進むだけでなく、active set 中の悪い atom から離れる方向を追加します。Pairwise FW は悪い atom から新 atom へ直接重みを移し、Fully Corrective FW は active weights を再最適化します。適切な polytope と強い条件下では線形収束が可能です。
重要ポイント
- away step の最大 step は active weight が負にならない範囲に制限されます。
- Pairwise FW は support をより直接的に入れ替えられます。
- Fully Corrective は反復数を減らせますが active-set 上の追加最適化が必要です。
10. 重要な構造化例
FW の本質は具体的 LMO で理解しやすいです。simplex では基底ベクトル、ℓ1 ball では符号付き1座標、nuclear-norm ball では先頭特異ベクトルから rank-1 行列を返します。これにより疎・低ランク構造が自然に得られます。
重要ポイント
- simplex では最小勾配成分の e_j を選びます。
- ℓ1 ball では最大絶対勾配座標 j を選びます。
- nuclear-norm ball では ∇f(X) の先頭特異ベクトルから rank-1 atom を選びます。
11. Stochastic・Block-coordinate・大規模 FW
大規模問題では full gradient や global LMO が高価になります。Stochastic FW、block-coordinate FW、lazy/cached FW などで gradient、LMO、通信、active-set のボトルネックを削減します。
重要ポイント
- approximate LMO でも誤差を制御すれば収束保証を保てます。
- LMO が agent/data block に分解できる場合 distributed FW は有効ですが通信が支配的になることがあります。
- 行列問題では randomized leading singular-vector 法で LMO を高速化できます。
12. Frank–Wolfe を使う判断基準
FW を選ぶのは、LMO が安く、射影が高価で、疎・極点表現に価値がある場合です。制約があるだけで FW を選ぶべきではありません。射影が簡単なら projected/proximal 法が速いこともあります。境界で停滞するなら away/pairwise を検討します。
重要ポイント
- objective、FW gap、LMO 時間、step size、active-set size を別々に記録します。
- gap が大きいのに objective が動かないなら step が保守的すぎる可能性があります。
- LMO が計算時間を支配するなら outer variant より oracle 改善が重要です。
- active set が大きくなりすぎる場合は corrective/drop/compression を使います。
この節の要点
このノート後には FW 更新と代表的 LMO を導出し、FW gap を停止判定に使い、O(1/t) を説明し、away/pairwise が必要な状況を判断できることを目標とします。