凸最適化と勾配法の収束保証

なぜ収束保証が要るのか

実務の学習は「とりあえず回して損失が下がるのを見る」で進みがちですが、上級者にはいつ止めるか・どれだけ反復すれば誤差が一定以下になるかを事前に見積もる根拠が要ります。凸最適化の理論は、関数の性質（凸性・平滑性）と更新式から、反復回数 k に対する誤差の上界を厳密に与えます。これが収束保証です。深層学習の損失は非凸ですが、局所的な振る舞いやサブ問題は凸近似で語れ、最適化器の挙動を理解する土台になります。基礎の更新則は 勾配降下法 を前提とします。

関数に課す4つの性質

収束率は関数のどの仮定を置くかで決まります。記号 f は最小化対象、x* を最適解とします。

L-平滑性は「勾配 ∇f が L-リプシッツ」、つまり ||∇f(x)-∇f(y)|| <= L||x-y|| を意味します。これは曲率（ヘッセ行列の最大固有値）が L 以下という上限で、二次の上界 f(y) <= f(x) + ∇f(x)·(y-x) + (L/2)||y-x||^2 を生みます。強凸性 m は逆に下界 f(y) >= f(x) + ∇f(x)·(y-x) + (m/2)||y-x||^2 を与え、曲率が m 以上であることを表します。両者で関数は上下を二次関数で挟まれます。

凸+L-平滑：O(1/k) のサブ線形収束

凸かつ L-平滑な f に、ステップ幅 η = 1/L の勾配降下 x_{k+1} = x_k - η∇f(x_k) を適用すると、関数値の誤差に次の上界が成り立ちます。

f(x_k) - f(x*) <= L * ||x_0 - x*||^2 / (2k)

誤差は 1/k で減るサブ線形収束です。これは二次上界から1反復ごとの減少量 f(x_k)-f(x_{k+1}) >= ||∇f(x_k)||^2 / (2L) を導き、凸性で telescoping（総和の打ち消し）して得られます。精度 ε を得るには O(1/ε) 反復が必要で、強凸性がないと縮小率は反復が進むほど鈍ります。

強凸+L-平滑：O(ρ^k) の線形収束

ここに強凸性 m が加わると、収束は劇的に速くなります。同じ η = 1/L で、最適解までの距離が等比数列で縮む線形収束になります。

||x_{k+1} - x*||^2 <= (1 - m/L) * ||x_k - x*||^2

縮小率 ρ = 1 - m/L で、k 反復後の誤差は ρ^k に比例します。誤差が ε になる反復数は O(κ log(1/ε)) と、log で済みます（κ は次節）。「線形」とは誤差の対数が反復に対して直線で下がる意味で、実際の収束は指数的に速い、という用語上の注意があります。

条件数κが速さを支配する

線形率を決めるのが条件数 κ = L / m（曲率の最大と最小の比）です。縮小率は次のように κ で書けます。

ρ = 1 - m/L = 1 - 1/κ

• κ が 1 に近い（等方的・球状の谷）→ ρ が 0 に近く、数反復で収束。
• κ が大きい（細長い谷）→ ρ が 1 に近く、ジグザグして極端に遅い。

これが特徴量の正規化や前処理（プレコンディショニング）が効く理由です。スケールを揃えてヘッセ行列を等方に近づけ κ を下げると、同じアルゴリズムでも反復数が桁で減ります。Adam など適応的手法が座標ごとに実効的な κ を均す効果を持つことは SGDとAdam で扱います。

Nesterov加速と一階法の下界

勾配（一階情報）だけを使う手法には、情報理論的な速度の下界が知られています。Nemirovski–Yudin の結果により、凸+L-平滑のクラスで一階法が達成できる誤差は最良でも O(1/k^2) までで、これより速くはできません。素の勾配降下 O(1/k) はこの下界に届いていません。

Nesterov の加速勾配法はこの下界を達成します。直前の更新方向を慣性として先読み点で勾配を測る、いわゆる「先読みモメンタム」を加えるだけで、追加の勾配計算なしに次を実現します。

加速の本質はκ が √κ に化けることです。強凸での実効的な反復数は O(κ log(1/ε)) から O(√κ log(1/ε)) に改善し、κ=10000 なら 100 倍の差になります。重要なのは、これがメモリやモデル容量ではなく更新の幾何だけで得られる点で、深層学習のモメンタム系最適化が経験的に速い理由の数理的な裏付けでもあります。

まとめ

凸最適化の収束保証は、関数に課す仮定（凸性・強凸性 m・L-平滑性）と更新式から、反復回数に対する誤差の上界を厳密に導きます。凸+平滑で O(1/k)、強凸を加えて線形収束 O(ρ^k)、その速さは条件数 κ=L/m が支配し、Nesterov 加速が一階法の下界 O(1/k^2) を達成して κ を √κ に改善します。非凸な深層学習でも、正規化で κ を下げ、モメンタムで加速するという実務判断は、この理論にそのまま接続します。誤差を最小化対象として定式化する出発点は 最尤推定と損失関数 を参照してください。