修士論文 要旨

非凸近接 Newton 法の大域計算量および局所収束性の解析
数理情報学専攻 48226208
指導教員

逸見榛一
武田 朗子 教授

表 1: 提案手法と既存の近接 Newton 法の比較

1 はじめに計算量保証目的関数が，微分可能な関数と凸関数の和で表される非凸非平滑最適化問題には様々な工学的応用が存在

近接 Newton 法

大域する．損失関数と非平滑な正則化項の和の最適化問題[3]

O(ε−2 )という数理モデル化は，least absolute shrinkage and[2]

selection operator (LASSO) をはじめとして，機械学[4]

習，統計，画像・信号処理などの分野にでも広く用いら

オラクル

局所

∇2 f · v

∇2 f
3
3>1>1

提案手法

O(ε−2(1+ρ))

1+ρρÕ(ε− 2 )れている．
このような構造を持つ問題に対する最適化手法として，近接勾配法の枠組で最適な大域計算量を達成する手法や，近接 Newton 法の枠組で超 1 次以上の局所収束3 提案手法性を持つ手法などが提案されてきた．しかしながら，一前章の背景を踏まえ，本研究では非凸な f に対して，般的な仮定のもとで，大域的な計算量保証と超 1 次以上大域計算量及び局所収束性の保証を同時に持つ，新たなの局所収束性の両方を満たすアルゴリズムは知られて近接 Newton 法を提案した．その概略を Algorithm 1にいなかった．

示す．アルゴリズム中の G は gradient mapping を表

本論文では，正則化付きの近接 Newton 法を提案し，し，非平滑な関数の勾配に対応する概念である．

主に平滑項の勾配の Lipschitz 連続性と局所的な凸性，既存の手法に対する大きな改善点として， [5] の近接そして目的関数の metrical subregularity という比較的Newton 法で用いられていた正則化項を非凸の場合への弱い仮定のもとで，Õ εの反復計算量と局所拡張，大域計算量と局所収束性の両方を同時に保証する的な超 1 次収束性を達成できることを示した．ただし，ための直線探索の条件の設定，そして，子問題の近似のρ ∈ [0, 1] は大域と局所の収束性のトレードオフを示す十分条件の設定と，その反復計算量の保証を行った．

−2(1+ρ)

なお，最小固有値計算と理論保証で用いる子問題のアルゴリズムのパラメータである．
また，本手法では，古典的な勾配・Hesse 行列オラク解法 [1] については，Hesse 行列を直接評価することなルの評価回数だけでなく，子問題の解法まで含めた反復く，Hesse 行列・ベクトル積を利用するのみで実装可能計算量の保証も与えている．提案手法で用いる子問題であり，大規模な問題に対して適用可能である．既存のの解法では，Lipschitz 定数の自動推定と Hesse 行列・近接 Newton 法との比較を表 1に示した．

ベクトル積の利用による Hesse 評価の代替を行うため，提案手法は事前情報の少ない問題や，大規模な問題に対4 大域計算量
大域計算量の保証のため，以降では ∇f は Lipschitz

して適用できる実用的な手法である．

連続であることを仮定する．また，2 構造を持つ非凸非平滑最適化問題
関数 f : Rn → (−∞, ∞] は 2 階連続微分可能，関数

g : Rn → (−∞, ∞] は閉真凸関数として，最適化問題

ω(x) := min ∥∇f (x) + p∥ ≤ εp∈∂gを満たす点を ε-停留点 x と呼び，この x 点を得るために必要な f の関数値，勾配，そして Hesse 行列またはminn F (x) := f (x) + g(x)x∈R(1)を考える．このような構造を持つ最適化問題は，機械学

Hesse 行列・ベクトル積の評価回数に対する理論保証を行った．まず，提案手法の反復計算量保証を与える．

習・統計のスパース推定や，画像・信号処理におけるノ定理 1. 提案手法はそれぞれ O ε−2(1+ρ) 回の f の勾イズの除去等の応用が知られている．また，g を標示関配，Hesse 行列評価と，O ε−2(1+ρ) log ε−1 回の関数数にとることで，凸最適化問題にも帰着する．

値評価で ε-停留点を出力する．

非凸近接 Newton 法の大域計算量および局所収束性の解析 (逸見榛一)

Algorithm 1 提案手法（概略）107

F (xk )

1: l ← 0
2: for k = 0, 1, . . . do
3:4:

λk ← | min λmin (∇2 f (xk )), 0 |nρoµk ← min µ, c GLf (xk )7:

if F (xk + dk ), ∥GL (xk + dk )∥ が十分減少 then

9:
10:
11:

10−110−3103

10−5Proximal Gradient
Proximal Newton ρ = 0
Proximal Newton ρ = 0.5
Proximal Newton ρ = 11006:

8:101104101q̃ (d) := ∇f (x )
mind q̃ k (d) + g(x + d) の近似解 d を計算

5:

103

105102k ⊤d + 12 ∥d∥2∇2 f (xk )+(λk +µk )Ikkk

10kGηk (xk )kInput : x0 ∈ Rn , µ, c > 0, ρ ∈ [0, 1], 0 < θ, σ, γ < 1105

6tk ← 1, lk+1 ← k + 1

050

100k150

Proximal Gradient
Proximal Newton ρ = 0
Proximal Newton ρ = 0.5
Proximal Newton ρ = 110−710−9200050100k150200

図 1: 横軸に提案手法の反復，縦軸に関数値 F (xk )（左）と gradient mapping のノルム ∥GL (xk )∥（右）をプロットしたもの．

else
直線探索により tk を決定

xk+1 ← (1 − tk )xk + tk x̂k6 数値実験

この計算量保証は，2 次法の反復計算量保証では一般的な方法であるが，子問題の解法の計算量を含まないことに留意する必要がある．本提案手法では，子問題の解法に対しても計算量解析を行なっており，次の全体反復計算量の保証を示した．
定理 2. 提案手法はそれぞれ O ε−2(1+ρ)− ρ2の Hesse 行列・ベクトル積の評価，O ε配評価，O ε−2(1+ρ)

log ε−1log ε−2(1+ρ)−1

平滑項として Rosenbrock 関数：1X100(xi+1 − x2i )2 + (xi − 1)22 i=1n−1

f (x) :=非平滑項として ℓ1 ノルム g := λ∥x∥1 を用いて数値実験を行い，提案手法と近接勾配法の比較を行った

回回の勾回の関数値評価で ε-停留点を出力する．
ここで，提案手法中の子問題の解法を用いることで，f の Hesse 行列を直接評価する代わりに Hesse 行列・ベクトル積の評価回数に対して計算量が保証される．また，Algorithm 1 中では省略したが， 同時に Lipschitz

結果を図 1に示す．なお，n = 106 , λ = 10−6 とし，ρ = 0, 0.5, 1 の各設定で提案手法を実行した．
提案手法（橙，緑，赤．それぞれ ρ = 0, 0.5, 1 に対応）
は，近接勾配法（青）より少ない反復計算量でより精度の高い ε-停留点を出力することがわかる．また，ρ に対する挙動の変化として，ρ = 0 の場合にはじめは速い収束を見せるものの，停留点の近傍では ρ > 0 の設定よりも遅くなり，理論保証通りの振る舞いを確認できる．

定数が自動推定される．

参考文献

5 局所収束性[1] A. d’Aspremont, D. Scieur, and A. Taylor. Acceleration methods. Foundations and Trends® in Optimization, 5(1-2):1–245, 2021.
[2] C. Kanzow and T. Lechner. Globalized inexact proximal Newton-type methods for nonconvex composite
functions. Computational Optimization and Applications, 78(2):377–410, 2021.
[3] C.-p. Lee and S. J. Wright.
Inexact successive
quadratic approximation for regularized optimization.
Computational Optimization and Applications, 72(3):641–674, 2019.
[4] S. Nakayama, Y. Narushima, and H. Yabe. Inexact proximal DC Newton-type method for nonconvex composite functions. Computational Optimization
and Applications, 2023.
[5] B. S. Mordukhovich, X. Yuan, S. Zeng, and J. Zhang.
A globally convergent proximal Newton-type methodin nonsmooth convex optimization. MathematicalProgramming, 198(1):899–936, 2023.

局所収束性の保証のための仮定として，以降では停留点の近傍で，f は凸かつ ∇2 f (x) は Lipschitz 連続であるとする．また，さらに ∇f + ∂g が metricallysubregular であるという仮定を置く．この仮定は，非平滑関数に対して強凸性を弱めた概念であり，g ≡ 0 の場合は error bound 条件に帰着される．上記の仮定のもとで，提案手法は次の局所収束性を満たす．
定理 3. 提案手法の生成する点列 {xk } に対して，あるK ∈ N, C ∈ Rn が存在して，任意の K ≥ K に対してdist(xk+1 , X ∗ ) < C dist(xk , X ∗ )1+ρが成り立つ．