弱凸関数と可微分写像からなる合成関数の最適化のための可変平滑化法と信号処理応用

弱凸関数と可微分写像からなる合成関数の 最適化のための可変平滑化法と信号処理応⽤ 久⽶啓太 東京科学⼤学⼯学院情報通信系 2025/1/25, RAOTA@NII ※本講演は⼭⽥功⽒（東京科学⼤学）との共同研究成果に基づく．0

⾃⼰紹介 n名前：久⽶ 啓太 n出⾝：北海道札幌市 n経歴 2015年4⽉-2019年3⽉ 東京⼯業⼤学⼯学部情報⼯学科 2019年4⽉-2024年3⽉ 東京⼯業⼤学⼯学院情報通信系 ⼭⽥功研究室（学⼠・修⼠・博⼠） 2024年4⽉-現在 東京科学⼤学⼯学院情報通信系 ⼭⽥功研究室 助教 ※9⽉まで東⼯⼤ n研究トピック：信号処理・連続最適化 1/86

本発表のアウトライン 1. 導⼊ 2. 数学的準備 3. 可変平滑化法（無制約） 4. 可変平滑化法（⾮凸制約付き） 5. 近接可変平滑化法 ※未公開情報を含むため，5については⾮公開とさせていただきます 2

本発表のアウトライン 1. 導⼊ 2. 数学的準備 3. 可変平滑化法（無制約） 4. 可変平滑化法（⾮凸制約付き） 5. 近接可変平滑化法 3

信号処理は「価値のあるデータ」を抽出するための技術 ⽣のデータ 価値のあるデータ 信号処理 • 雑⾳除去 • フィルター • 次元圧縮 ⋮ 現代社会はビッグデータの活⽤によって⽀えられており、 信号処理は鍵となる基盤技術になっている 4/86

「価値のあるデータ」の抽出=数理最適化 価値のあるデータとは・・・ • 滑らか • 多くの成分値がゼロ付近に 集中している(スパース性を持つ) ⋮ 対象のデータによって 「価値」の意味が異なる 数値(実数値)で表現可能な「価値の尺度=⽬的関数!」と 「価値のあるデータが満たすべき条件=制約集合"」を適切に設計 minimize ' ( s. t. ( ∈ -(⊂ 0) !∈# 信号処理技術の発展のためには，最適化技術の発展が必要不可⽋！！ 5/86

スパース信号処理 ‒ 画像雑⾳除去を例に 画像は256×256個の画素で構成される． 0から255の値で各画素の濃淡を表す． 元信号&⋆ ∈ ( ≡ ℝ"#$×"#$ （推定対象: 旧東⼯⼤本館前の桜） 観測信号+ ∈ ( （雑⾳あり） 6/86

スパース信号処理 ‒ 画像雑⾳除去を例に 滑らかな画像では， 隣接画素との濃淡の差は ⼤きくない 元信号&⋆ ∈ ( ≡ ℝ"#$×"#$ （推定対象: 旧東⼯⼤本館前の桜） ,(&⋆ )のほとんどの成分は0 （=,(&⋆ )はスパース） , &⋆ ∈ - ≡ ℝ"##×"#$ *: , → . ,(+)はスパースでない 縦⽅向の隣接画素 の差分を出⼒ 観測信号+ ∈ ( （雑⾳あり） , + ∈- 元信号&⋆ ∈ (のスパース表現1 &⋆ ∈ 2を活⽤して観測信号+ ∈ (から推定 7/86

スパース信号処理 ‒ 画像雑⾳除去を例に 元信号&⋆ ∈ (のスパース表現, &⋆ ∈ -を活⽤して観測信号+ ∈ (から推定 推定信号&と観測信号+の「近さ」を測る． （元信号&⋆ は観測信号+からそれほど離れていないはず） 1 Find 3 ∈ argmin 9−3 (+<∘* 3 $∈ &,()) !"#×!"# 2 ⋆ 推定信号& ∈ ℝ"#$×"#$に対する制約集合 [0,255]の値を取る256×256個の 画素からなる画像 ⽬的関数 （価値の尺度） 推定信号&の隣接画素の差分ベクトル ,(&) ∈ ℝ"##×"#$の「スパース性」を測る． 6: ℝ"##×"#$ → ℝ: スパース性評価関数 （スパースな場合に出⼒値が⼩さくなる関数） ※ *($)のスパース性だけ促進してしまうと， 全画素が同⼀値を取る画像が最適解となる． スパース性評価関数<はどのように選べばよいのか？ 8/86

スパース性評価関数!の例
（１次元の場合）

ℓ! 擬似ノルム:⾮零成分数を数え上げる不連続関数

• スパース性（⾮零成分数が少ない性質）
の理想的な評価尺度
• 最適化が難しい
ℓ&ノルム: ℓ'擬似ノルムの最良近似凸関数
• 凸最適化の枠組みで扱える
• ℓ( との乖離が⼤きい

原点では微分不可

Minimax Concave Penalty (MCP)
Smoothly Clipped Absolute Deviation (SCAD)
• ℓ( との乖離が⼩さい連続な弱凸関数
（⾮凸な関数だが，性質の良い関数）

実⽤的に⽤いられる多くのスパース性評価関数は微分不可な弱凸関数として表現できる[CG’14]．
[Z’10] C.-H. Zhang, “Nearly unbiased variable selec>on under minimax concave penalty,” Ann. Stat., 2010.
[FL’01] J. Fan and R. Li, “Variable selec>on via nonconcave penalized likelihood and its oracle proper>es,” J. Am. Stat. Assoc., 2001.
[CG’14] L. Chen and Y. Gu, “The convergence guarantees of a non-convex approach for sparse recovery,” IEEE Trans. Signal Process., 2014.

9/86

本講演で扱う基本的な最適化問題
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 '

(♣),

"∈$(⊂')

(-と.はユークリッド空間)

1.

S ⊂ (は⾮空な閉集合（凸の場合と⾮凸の場合も考えていく）

2.

ℎ: ( → ℝは連続微分可能，勾配∇ℎ: ( → (はS上でLipschitz連続

3.

"#$

∃0∇& > 0, ∀$' , $( ∈ 4 s. t. ∇ℎ $' − ∇ℎ $(

≤ 0∇& $' − $(

W: - → ℝはLipschitz連続(微分可能とは限らない)なX(> 0)-弱凸関数
（※多くのスパース性評価関数は,の例となっている）

4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞
先ほどの画像雑⾳除去問題「Find &⋆⋆ ∈

&
argmin
"
)∈ ',"## !"#×!"#

"#$

)
(

< + || ⋅ ||( は凸関数

+ − & " + 6 ∘ , & 」は

(♣)の特別な場合に相当 4 ≔ 0,255 (*+×(*+, ℎ ≔ '( C − $ (, < ≔ D, *: 隣接画素との差分を出⼒
10/86

最適化問題(♣)の応⽤例
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 '
(-と.はユークリッド空間)

1.

"∈$(⊂')

(♣),

S ⊂ (は⾮空な閉集合（凸と⾮凸の場合を考えていく）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX(> 0)-弱凸関数
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞
*が線形写像の場合
画像雑⾳除去[BH’14]，ロバスト主成分分析[CLMW’11]，低ランクテンソル補完[GRY’11]…

*が⾮線形写像の場合
ロバスト位相復元[DR’18]，ロバスト低ランク⾏列補完[CCD+’21]，スパーススペクトルクラスタリング[LYL’16]…
[BH’14] R. I. Bot¸ and C. Hendrich, “Convergence analysis for a primal-dual monotone + skew spliGng algorithm with applicaHons to total variaHon minimizaHon,” J. Math. Imaging Vision, 2014.
[CLMW’11] E. J. Candès, X. Li, Y. Ma, and J. Wright, “Robust principal component analysis?,” J. ACM, 2011.
[GRY’11] S. Gandy, B. Recht, and I. Yamada, “Tensor compleHon and low-n-rank tensor recovery via convex opHmizaHon,” Inverse Problems, 2011.
[DR’18J. C. Duchi and F. Ruan, “Solving (most) of a set of quadraHc equaliHes: composite opHmizaHon for robust phase retrieval,” InformaHon and Inference: A Journal of the IMA, 2018.
[CCD+’21] V. Charisopoulos, Y. Chen, D. Davis, M. D ı́ az, L. Ding, and D. Drusvyatskiy, “Low-rank matrix recovery with composite opHmizaHon: Good condiHoning and rapid convergence,”
FoundaHons of ComputaHonal MathemaHcs, 2021.
[LYL’16] C. Lu, S. Yan, and Z. Lin, “Convex sparse spectral clustering: Single-view to mulH-view,” IEEE Trans. Image Process., 2016.

11/86

本研究の動機
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 '
(-と.はユークリッド空間)

1.

"∈$(⊂')

(♣),

S ⊂ (は⾮空な閉集合（凸と⾮凸の場合を考えていく）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX(> 0)-弱凸関数
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞

最適化問題(♣)に対する「効率的」な最適化アルゴリズムは実現できないか？
• 内部反復アルゴリズムが必要ないアルゴリズムの実現を⽬指す
• ⾮平滑⾮凸関数W ∘ ,の扱い⽅（可変平滑化）が鍵
12/86

本発表のアウトライン 1. 導⼊ 2. 数学的準備 3. 可変平滑化法（無制約） 4. 可変平滑化法（⾮凸制約付き） 5. 近接可変平滑化法 13

凸関数の劣微分=凸関数の微分の⼀般化
関数b: ( → ℝ ∪ +∞ に対して，
bは真(proper)

ABC

dom b ≔ & ∈ ( b & < +∞ ≠ ∅

bは下半連続(lower semicontinuous)
ABC

bは凸

m
∀m
& ∈ (, ∀ &D F
DE& ⊂ ( with lim &D = &

ABC

D→F

∀&&, &" ∈ (, ∀e ∈ 0,1

m
lim inf b &D ≥ b &
D→F

b e&& + 1 − e &" ≤ eb && + 1 − e b &"

m, b &
m における『接線』の傾きpの集合」
真凸関数bの劣微分ob(m
&) =「bのグラフの &

@ ≔B
>? 3

C∈,

@ − C, 3 − 3
@ ≥0 ,
∀3 ∈ , ? 3 − ? 3
∅,

m = {∇b &
m }．
真凸関数bがm
&で微分可能ならば，ob &
凸関数の劣微分は，微分の⼀般化となっている．
[RW’10] R. Rockafellar and R. J.-B. Wets, Varia%onal Analysis, Springer Verlag, 3rd edi>on, 2010.

3 ∈ dom ?
3 ∉ dom ?
F($)

E + G, $ − $
E
F $
E, F $
E
$

14/86

凸関数のFermatルール
関数b: ( → ℝ ∪ +∞ に対して，
bは真(proper)

ABC

dom b ≔ & ∈ ( b & < +∞ ≠ ∅

bは下半連続(lower semicontinuous)
ABC

bは凸

m
∀m
& ∈ (, ∀ &D F
DE& ⊂ ( with lim &D = &

ABC

D→F

∀&&, &" ∈ (, ∀e ∈ 0,1

m
lim inf b &D ≥ b &
D→F

b e&& + 1 − e &" ≤ eb && + 1 − e b &"

m, b &
m における『接線』の傾きpの集合」
真凸関数bの劣微分ob(m
&) =「bのグラフの &

@ ≔B
>? 3

C∈,

@ − C, 3 − 3
@ ≥0 ,
∀3 ∈ , ? 3 − ? 3
∅,

Fermatルール [RW’10, Thm. 10.1]

真凸関数b: ( → ℝ ∪ +∞ に対して，

3⋆⋆ ∈ argmin ? 3 ⇔ K ∈ >? 3⋆⋆
$∈-

[RW’10] R. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Verlag, 3rd edition, 2010.

3 ∈ dom ?
3 ∉ dom ?
F($)

E + G, $ − $
E
F $
E, F $
E
$

15/86

⾮凸関数の劣微分とは？ ⾮凸な真関数?: , → ℝ ∪ {+∞}に対して， 凸関数の劣微分は微分の⼀般化になっていない． m ≔s ob & p∈( m − p, & − & m ≥0 , ∀& ∈ ( b & − b & ∅, & ∈ dom b & ∉ dom b E' + ∇F $ E' , $ − $ E' F $ E' , F $ E' $ • 微分可能な点m &&でも， m& = ∅ ≠ ∇b & m& となる． ob & • m" , b & m" を通るどんな直線を考えても， & 関数b(&)の値を上回る& ∈ (が存在する． m" = ∅） （つまりob & F($) 16/86

⾮凸関数の劣微分とは？ ⾮凸な真関数?: , → ℝ ∪ {+∞}に対して， 凸関数の劣微分は微分の⼀般化になっていない． m ≔s ob & p∈( m − p, & − & m ≥0 , ∀& ∈ ( b & − b & ∅, & ∈ dom b & ∉ dom b • 微分可能な点m &&でも， m& = ∅ ≠ ∇b & m& となる． ob & • m" , b & m" を通るどんな直線を考えても， & 関数b(&)の値を上回る& ∈ (が存在する． m" = ∅） （つまりob & F($) E( , F $ E( $ E( + G, $ − $ E( F $ ⾮凸関数に対しても「劣微分」に相当する概念が欲しい！ 17/86

⾮凸関数の劣微分の概念は複数提案されている 例えば， • Fréchet (regular) 劣微分 • Limiting (general) 劣微分 • Clarke劣微分 ⋮ ⼀般に，「Fréchet劣微分⊂Limiting劣微分⊂Clarke劣微分」[RW’10, Thm. 8.6 and 8(32)]． 凸関数の場合は， 「凸劣微分=Fréchet劣微分=Limiting劣微分=Clarke劣微分」. 本発表で検討する関数の場合は，「Fréchet劣微分=Limiting劣微分=Clarke劣微分」． 時間の都合上，Fréchet劣微分のみ簡単にご紹介します． [RW’10] R. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Verlag, 3rd edition, 2010. 18/86

Fréchet (regular) 劣微分 [RW’10, Def. 8.3 (a)]
b: ( → ℝ ∪ {+∞}: 真（⾮凸）関数，m
& ∈ dom b
y &
m ≔ p ∈ ( sup
ob
HI'

m − p, & − &
m
b & −b &
m||
||& − &
'J )KL
) JH
inf

• Fréchet微分（勾配）の⾃然な⼀般化である．
L K Q,)KL
P ) KP )
)
y &
m = p
lim
= 0 ⇒ ob
L ∋)→L
M∖ )
)

y &
m ≔ ∅)
(m
& ∉ dom bの場合はob
≥0

E − G, $ − $
E
F $ −F $
lim inf
-∖ 0
/ ∋0→/
0
E||
||$ − $

||)KL
)||

m ≔ p ∈ (で与えられる）
（勾配は∇b &
y &
m は，ざっくり⾔うと，
• p ∈ ob
「m
&の近傍で凸劣微分の不等式」を満たす．
凸劣微分は関数bの⼤域的な性質を表す．
E = G∈\F $

E − G, $ − $
E ≥0
∀$ ∈ - F $ − F $

[RW’10] R. Rockafellar and R. J.-B. Wets, Varia%onal Analysis, Springer Verlag, 3rd edi>on, 2010.

19/86

Fréchet (regular) 劣微分 [RW’10, Def. 8.3 (a)]
b: ( → ℝ ∪ {+∞}: 真（⾮凸）関数，m
& ∈ dom b
y &
m ≔ p ∈ ( sup
ob
HI'

y &
m ≔ ∅)
(m
& ∉ dom bの場合はob

m − p, & − &
m
b & −b &
m||
||& − &
'J )KL
) JH
inf

• Fréchet微分（勾配）の⾃然な⼀般化である．
L K Q,)KL
P ) KP )
)
y &
m = p
lim
= 0 ⇒ ob
L ∋)→L
M∖ )
)

||)KL
)||

m ≔ p ∈ (で与えられる）
（勾配は∇b &

E − G, $ − $
E
F $ −F $
lim inf
-∖ 0
/ ∋0→/
0
E||
||$ − $
F($)

y &
m は，ざっくり⾔うと，
• p ∈ ob
「m
&の近傍で凸関数の劣微分の不等式」を満たす．
凸劣微分は関数bの⼤域的な性質を表す．
E = G∈\F $

≥0

E, F $
E
$

E + F(E
G, $ − $
$)

E − G, $ − $
E ≥0
∀$ ∈ - F $ − F $

[RW’10] R. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Verlag, 3rd edition, 2010.

m
&

20/86

Fréchet (regular) 劣微分 [RW’10, Def. 8.3 (a)]
b: ( → ℝ ∪ {+∞}: 真（⾮凸）関数，m
& ∈ dom b
y &
m ≔ p ∈ ( sup
ob
HI'

y &
m ≔ ∅)
(m
& ∉ dom bの場合はob

m − p, & − &
m
b & −b &
m||
||& − &
'J )KL
) JH
inf

• Fréchet微分（勾配）の⾃然な⼀般化である．
L K Q,)KL
P ) KP )
)
y &
m = p
lim
= 0 ⇒ ob
L ∋)→L
M∖ )
)

≥0

E − G, $ − $
E
F $ −F $
lim inf
-∖ 0
/ ∋0→/
0
E||
||$ − $

||)KL
)||

F($)

m ≔ p ∈ (で与えられる）
（勾配は∇b &
y &
m は，ざっくり⾔うと，
• p ∈ ob
「m
&の近傍で凸関数の劣微分の不等式」を満たす．

E, F $
E
$

凸劣微分は関数bの⼤域的な性質を表す．
E = G∈\F $

E + F(E
G, $ − $
$)

E − G, $ − $
E ≥0
∀$ ∈ - F $ − F $

[RW’10] R. Rockafellar and R. J.-B. Wets, Varia%onal Analysis, Springer Verlag, 3rd edi>on, 2010.

m−|
&

m
&

m+|
&

21/86

Fréchet (regular) 劣微分 b: ( → ℝ ∪ {+∞}: 真（⾮凸）関数，m & ∈ dom b y & m ≔ p ∈ ( sup ob HI' y & m ≔ ∅) (m & ∉ dom bの場合はob m − p, & − & m b & −b & m|| ||& − & 'J )KL ) JH inf • Fréchet微分（勾配）の⾃然な⼀般化である． L K Q,)KL P ) KP ) ) y & m = p lim = 0 ⇒ ob L ∋)→L M∖ ) ) ≥0 E − G, $ − $ E F $ −F $ lim inf -∖ 0 / ∋0→/ 0 E|| ||$ − $ ||)KL )|| F($) m ≔ p ∈ (で与えられる） （勾配は∇b & y & m は，ざっくり⾔うと， • p ∈ ob 「m &の近傍で凸関数の劣微分の不等式」を満たす． E, F $ E $ 凸劣微分は関数bの⼤域的な性質を表す． E = G∈\F $ E + F(E G, $ − $ $) E − G, $ − $ E ≥0 ∀$ ∈ - F $ − F $ m−| & m & m+| & 22/86

Fréchet劣微分を⽤いた場合のFermatルール
Fermatルール（⾮凸の場合） [RW’10, Thm. 10.1]

真（⾮凸）関数b: ( → ℝ ∪ +∞ に対して，

R 3⋆⋆
3 は?の局所最適解 ⇒ K ∈ >?
⋆⋆

（逆は成⽴するとは限らない）
1次の最適性（の必要）条件

&⋆⋆ のある近傍} ⊂ (が存在して，b &⋆⋆ ≤ b & (∀& ∈ })

「Find 3⋆⋆ ∈ argmin ℎ + X ∘ * 3 =: S(3)」の現実的な⽬標
$∈b ⊂-

1次の最適性条件を満たす「停留点」の探索

Find '⋆ ∈ ? such that A ∈ CB D + E$ '⋆
argmin S 3 = argmin S + Ub

$∈b ⊂-

$∈-

[RW’10] R. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Verlag, 3rd edition, 2010.

0
@ ≔B
3 , Ub 3
+∞

@∈V
3
@∉V
3
23/86

「数学的準備」のまとめ
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 ' =: D(') (♣),
(-と.はユークリッド空間)

1.

"∈$ ⊂'

S ⊂ (は⾮空な閉集合（凸の場合と⾮凸の場合も考えていく）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞

最適化問題(♣)の現実的な⽬標＝Find 3⋆ ∈ , such that K ∈ >R S + Ub 3⋆
⾮凸関数の劣微分・最適性条件に関する参考⽂献
•
•
•

R. Rockafellar and R. J.-B. Wets, Varia%onal Analysis, Springer Verlag, 3rd ediEon, 2010. (有限次元)
B. S. Mordukhovich, Varia%onal Analysis and Generalized Differen%a%on I: Basic Theory, Springer, 2006. (無限次元)
J. Li, A. M. C. So, and W. K. Ma, “Understanding noEons of staEonarity in nonsmooth opEmizaEon: A guided tour of
various construcEons of subdifferenEal for nonsmooth funcEons,” IEEE Signal Processing Magazine, 2020.
(信号処理の研究者向けのレビュー論⽂). 24/86

本発表のアウトライン 1. 導⼊ 2. 数学的準備 3. 可変平滑化法（無制約） K. Kume and I. Yamada, “A variable smoothing for nonconvexly constrained nonsmooth optimization with application to sparse spectral clustering,” IEEE ICASSP, 2024. K. Kume and I. Yamada, “A variable smoothing for weakly convex composite minimization with nonconvex constraint,” arXiv:2412.04225, 2024. 4. 可変平滑化法（⾮凸制約付き） 5. 近接可変平滑化法 25

無制約⾮平滑⾮凸最適化問題
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 '
(-と.はユークリッド空間)

1.
2.
3.
4.

"∈'

(♠),

ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (は(上でLipschitz連続
W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
,: ( → -は連続微分可能な写像(線形写像とは限らない)
inf ℎ + W ∘ , & & ∈ ( > −∞

R 3⋆
最適化問題(♠)の現実的な⽬標＝Find 3⋆ ∈ , such that K ∈ >S

26/86

最適化問題(♠)に対する従来法
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 '
(-と.はユークリッド空間)

1.
2.
3.
4.

"∈'

(♠),

ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
,: ( → -は連続微分可能な写像(線形写像とは限らない)
inf ℎ + W ∘ , & & ∈ ( > −∞

ℎ, W:凸関数， ,: 線形写像

Proximal splitting method, e.g., [BC’17] [CKCH’23]

<の近接写像（後述）を利⽤する凸最適化アルゴリズム．

W:弱凸関数，,: ⾮線形写像 Proximal linear method, e.g., [LW’16] [DC’19]
各反復で部分問題を解くための内部反復アルゴリズムが必要となる．

W:凸関数，

,: ⾮線形写像 Subgradient method, e.g., [ZZZ’23]

内部反復アルゴリズムは不要だが，収束は遅い傾向にある．

（ステップサイズ列の単調減少性が主な原因）

[BC’17] H. H. Bauschke and P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, Springer, 2nd ed., 2017.
[CKCH’23] L. Condat, D. Kitahara, A. Contreras, and A. Hirabayashi, “Proximal splitting algorithms for convex optimization: a tour of recent advances, with new twists,” SIAM Review, 2023.
[LW’16] A. S. Lewis and S. J. Wright, “A proximal method for composite minimization,” Math. Program., 2016.
[DC’19] D. Drusvyatskiy and C. Paquette, “Efficiency of minimizing compositions of convex functions and smooth maps,” Math. Program., 2019.
[ZZZ’23] D. Zhu, L. Zhao, and S. Zhang, “A unified analysis for the subgradient methods minimizing composite nonconvex, nonsmooth and non-Lipschitz functions,” arXiv (2308.16362), 2023.

27/86

最適化問題(♠)の難しさ=4 ∘ 6の⾮平滑性
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 '
(-と.はユークリッド空間)

1.
2.
3.
4.

"∈'

(♠),

ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
,: ( → -は連続微分可能な写像(線形写像とは限らない)
inf ℎ + W ∘ , & & ∈ ( > −∞

X ∘ *の⾮平滑性が，最適化問題(♠)に対する
「効率的」なアルゴリズムの設計を困難にしている．
≈

1. 内部反復アルゴリズム
が不要
2. ステップサイズ列の単調減少性

本研究の着眼点

X ∘ *の微分可能な代理関数を⽤いる（＝平滑化する）ことで，
「効率的」なアルゴリズムの設計が可能となるのでは？

28/86

/ ∘ 1の平滑化の鍵：/の近接写像とMoreau envelope
定義
X-弱凸関数W: - → ℝについて，インデックス ∈ (0, X K&)のWの近接写像と
Moreau envelopeは，それぞれ次のように定義される:
1
proxTU : - → -: ÅÄ ↦ argmin W Å +
Å − ÅÄ "
2
V∈W
1
1
"
T W: - → ℝ: Å
"
Ä ↦ min W Å +
Å − ÅÄ
= W proxTU ÅÄ +
proxTU ÅÄ − ÅÄ
V∈W
2
2
&
K&
( ∈ 0, X の場合，W +
⋅ −ÄÅ "は強凸となるため，最適解は⼀意に存在する)
"T

d ∈ (0, e 3' )の場合の 4 <の性質（例えば[BW’21]）

• lim T W ÅÄ = W(ÄÅ) （ T WはWへ各点収束する）
T→'

WがÑU -Lipschitz連続ならば，
&
• T W ÅÄ ≤ W ÅÄ ≤ T W ÅÄ + " Ñ"U （ T WはWへ⼀様収束することがわかる）
•

T% W Å
Ä

& T KT

≤ T! W ÅÄ ≤ T% W ÅÄ + " %T ! &Ñ"U (0 < " < & < X K&)
!

[BW’21] A. Böhm and S. J. Wright, “Variable smoothing for weakly convex composite functions,” Journal of Optimization Theory and Applications, 2021.

29/86

/ ∘ 1の平滑化の鍵：/の近接写像とMoreau envelope
定義
X-弱凸関数W: - → ℝについて，インデックス ∈ (0, X K&)のWの近接写像と
Moreau envelopeは，それぞれ次のように定義される:
1
proxTU : - → -: ÅÄ ↦ argmin W Å +
Å − ÅÄ "
2
V∈W
1
1
"
T W: - → ℝ: Å
"
Ä ↦ min W Å +
Å − ÅÄ
= W proxTU ÅÄ +
proxTU ÅÄ − ÅÄ
V∈W
2
2
&
K&
( ∈ 0, X の場合，W +
⋅ −ÄÅ "は強凸となるため，最適解は⼀意に存在する)
"T

d ∈ (0, e 3' )の場合の 4 <の性質（例えば[BW’21]）

•
•

T Wは連続微分可能

XAKYZ[\&'
T
∇ W=
はmax
T

K&,

&
-Lipschitz連続
&K]T

proxTU の計算が容易であれば， T Wと∇T Wの計算も容易である．
多くのスパース性評価関数ÖのÜáàâ ^_は容易に計算できることが知られている．

[BW’21] A. Böhm and S. J. Wright, “Variable smoothing for weakly convex composite func>ons,” Journal of Op>miza>on Theory and Applica>ons, 2021.

30/86

! " 4の計算が容易な弱凸関数4: 8 ≔ ℝ → ℝの例 ag ℓf ノルム: ba f ≔ ∑i ghf b （凸関数） d > 0, ba ∈ . i 第ä成分のみ1のã次元単位ベクトル proxj‖⋅‖% ba = h sign ba g max ba g − d, 0 ig ghf （1次元の場合のMoreau envelope） 31/86

! " 4の計算が容易な弱凸関数4: 8 ≔ ℝ → ℝの例 Minimax Concave Penalty (MCP): Xlmn : ba ↦ ∑i ghf （å K&-弱凸関数） ∈ 0, å K& , ÅÄ ∈ - a proxTU()* ÅÄ = ç sign ÅÄ ` min `E& ba g − o ba g max (å > 0) ÅÄ ` − , 0 , ÅÄ `  1− å é` （1次元の場合のMoreau envelope （å = 2）） p −5 p = p( p − 2q q 2 p ≤q p >q 32/86

! ℎ + 4 ∘ 6のℎ + 4 ∘ 6に対するgradient consistency 定理 ê T ≔ ℎ + T W ∘ ,  ∈ 0, X K& は連続微分可能であり， ∇r 4 $ の 0, e 3' ∋ d ↘ 0， ê ≔ ℎ + W ∘ ,に対してgradient consistency[C’12]を持つ: - ∋ $ → $Eにおけるouter limit m∈( & K& with  ↘ 0, ∃ D F ⊂ 0, X D DE& y m = p∈( oê & T+ & m ∃ &D F ⊂ ( with lim & = & s. t. p = lim ∇ê D D DE& D→F D→F 系 K& D F ⊂ 0, X DE& y & m í ì, oê m ∈ (に対して， ↘ 0と，収束列 &D F DE& ⊂ ( → & ≔ inf さらに， lim inf ∇ê T+ &D D→F ì−p y & m p ∈ oê ≤ lim inf ∇ê T+ &D . D→F y & m ∋ ì，つまり，m = 0ならばoê &はêの停留点である． [C’12] X. Chen, “Smoothing methods for nonsmooth, nonconvex minimization,” Math. Program., 2012. 33/86

!

ℎ + 4 ∘ 6のℎ + 4 ∘ 6に対するgradient consistency
定理

ê T ≔ ℎ + T W ∘ ,  ∈ 0, X K& は連続微分可能であり， ∇r 4 $ の 0, e 3' ∋ d ↘ 0，
ê ≔ ℎ + W ∘ ,に対してgradient consistency[C’12]を持つ: - ∋ $ → $Eにおけるouter limit
F
F
K&
K&
∃ ∃D F
⊂
⊂
0,
X
0,
X
with
,
∃

&
↘
0,⊂ (
D DE&
DD DE&
DE&
y (&
y p&
m∈( &
m oê
m =oê
m ∈≔
&
∈
( p ∈ (F
m =&Dlim
m&Ds., t.pp== lim
∃ &D DE&s. ⊂
t. 
(D with
↘ 0, lim
&
=&
lim∇ê
∇êTT++ &&DD
D→F D→F

D→F
D→F

Wが凸の場合， ê T のêに対するgradient consistencyは知られていた（例えば[BH’17]）．
•
•

[BH’17]では，Attouchの定理[RW’10, Thm. 12.35]が活⽤されており，
<の凸性が証明の鍵となっていた（本研究では，異なる証明法を採っている）．
[BH’17]では，Moreau envelopeを特別な例に含む⼀般のinfimal convolution型の平滑化
r 4 ≔ ℎ + < ⊡ v4 ∘ *のgradient consistencyが⽰されている．
, ⊡ c& ) ≔ inf , h + ic
'∈)

)−h
i

,

c )
= +∞
* →, )

c: M → ℝは微分可能な凸関数，c 0 ≤ 0， lim

[C’12] X. Chen, “Smoothing methods for nonsmooth, nonconvex minimiza>on,” Math. Program., 2012.
[BH’17] J. V. Burke and T. Hoheisel, “Epi-convergence Proper>es of Smoothing by Infimal Convolu>on,” Set-Valued Var. Anal., 2017.
[RW’10] R. Rockafellar and R. J.-B. Wets, Varia%onal Analysis, Springer Verlag, 3rd edi>on, 2010.

34/86

停留点探索問題の「平滑化を⽤いた特徴付け」 系（再掲） K& D F ⊂ 0, X DE& m ∈ (に対して， ↘ 0と，収束列 &D F DE& ⊂ ( → & y & m í ì, oê ≔ inf さらに， lim inf ∇ê T+ &D D→F ì−p y & m p ∈ oê ≤ lim inf ∇ê T+ &D . D→F y & m ∋ ì，つまり，m = 0ならばoê &はêの停留点である． r ≔ ℎ + < ∘ *の停留点探索問題 ⋆ R 3⋆ Find 3 ∈ , such that K ∈ >S 微分可能な代理関数r 4 ≔ ℎ + 4 < ∘ *を⽤いたrの停留点探索問題 a convergent sequence 3x y xhf ⊂ ,; Find zf dx y ⊂ 0, t ↘0 xhf such that lim inf ∇S j& 3x = 0 x→y 35/86

可変平滑化法 (variable smoothing)の概要 停留点探索問題 Find a convergent sequence &D F DE& ⊂ (; D F DE& ⊂ 0, X K& s. t. lim inf ∇ê T+ &D D→F ↘0 =0 可変平滑化法：時間変化する関数ê T+ の勾配降下法 w ∈ ℕ 3x{f ≔ 3x − yx ∇S j& 3x D ∈ 0, 2X K& , ñD > 0, ê T+ = ℎ + T+ W ∘ , （d6 と|6 の選び⽅については次のページから紹介する） • Wの近接写像が容易に計算できれば，可変平滑化法は各反復で， 部分問題を解くための内部反復アルゴリズムを必要としない． 「効率的」その１ • 実⽤的に⽤いられる多くの弱凸関数に対して，近接写像が閉形式で 表現できることがわかってきている（例えば，[KY’24, Sect. 2.2]参照）． [KY’24] K. Kume and I. Yamada, “A variable smoothing for weakly convex composite minimization with nonconvex constraint,” arXiv:2412.04225, 2024. 36/86

&
># #$% ⊂

0, 2A

'%

の条件

3' の条件
d6 8
67' ⊂ 0, 2e

1. lim dx = 0 （ê T のgradient consistencyを活⽤するため）
x→y
2. ∑y
xhf dx = ∞ （収束解析で必要となるため[後述]）
3. ∀w ∈ ℕ dx{f ≤ dx （D の単調減少性を保証するため）
j&
4. ∃| ≥ 1, ∀w ∈ ℕ j
≤|
&'%

（ ê T+,% (m
&) ≤ ê T+

m
&

&
+ " õÑ"U D − Ds&

3' の例
d6 8
67' ⊂ 0, 2e
% y
zf z(
•
2t w
}≥1
xhf
y
f

•

(} x{f ~Ä x{f

xhf

[H’02] H.-K. Xu, “Itera>ve algorithms for nonlinear operators,” J. Lond. Math. Soc., 2002.

の成⽴を保証するため）
• 条件1,2,4を満たす数列は
不動点理論の⽂脈でも
考察されている[H’02]．
• 実⽤的に⽤いられる D F
DE&
については後述．
37/86

ステップサイズB# の条件
仮定

ある正定数û&, û" > 0が存在して，任意のü ∈ ℕに対して，
∇ê T+ = ∇ ℎ + T+ W ∘ , は û& + û"DK& -Lipschitz連続である．
⼗分条件

Ñ∇u &+ ≔
（*が線形の場合，仮定は満たされる）

1.

sup D- "

2.

∃2./ > 0, ∀"0 , "1 ∈ '
D- "0 − D- "1 ,- ≤ 2./ "0 − "1

)∈+

|6 8
67' ⊂ 0, +∞ の条件

,- < +∞;

ある正定数ú > 0とù ∈ (0,1)が存在して，任意のü ∈ ℕに対して，
1. ñD ≥ úÑK&
∇u &+
2.

ê T+

&D − ñD ∇ê T+

&D

≤ ê T+

&D − ùñD

∇ê T+

&D

"

（Armijo条件）

; 0<:= 3;(0)
は*: - → .のGâteaux (Fréchet) 微分を表す．
:
ℝ∖ ! ∋:→!

•

D* $ : - → .: É ↦

lim

•

線形写像Ö: - → .に対して， Ö @A ≔

sup

0∈-, 0 D'

‖Ö$‖はÖの作⽤素ノルムを表す．

38/86

ステップサイズB# の例
∇r 4! の0∇E "! -Lipschitz連続性の下での |6 8
67' ⊂ 0, +∞ の条件（再掲）

ある正定数ú > 0とù ∈ (0,1)が存在して，任意のü ∈ ℕに対して，
1. ñD ≥ úÑK&
∇u &+
2.

ê T+

&D − ñD ∇ê T+

&D

≤ ê T+

&D − ùñD

∇ê T+

&D

"

（Armijo条件）

|6 8
67' ⊂ 0, +∞ の例

• ñD ≔ 2 1 − ù

ÑK&
∇u &+

" &Kv T+
=
= ¢ D
w% T+ sw!

• 直線探索法(backtracking algorithm，例えば[A’20])によるñD の推定：
ñD ≔ max ñxyxzx{| £} § ∈ ℕ ∪ 0 , ñxyxzx{| £} はArmijo条件を満たす
（|FGFHFIJ àK がArmijo条件を満たすまで，初期候補|FGFHFIJ > 0 にà ∈ 0,1 を乗じ続ける）

• •~ F
~E の単調減少性は必要ない
直線探索法を⽤いれば，
• 定数Ñ∇u &+ の知識は必要ない
[A’20] N. Andrei, Nonlinear Conjugate Gradient Methods for Unconstrained Optimization, Springer, 2020.

「効率的」その２
39/86

収束解析
仮定（再掲）

ある正定数û&, û" > 0が存在して，任意のü ∈ ℕに対して，
∇ê T+ = ∇ ℎ + T+ W ∘ , は û& + û"DK& -Lipschitz連続である．
定理
K& と ñ F ⊂ 0, +∞ の下で，任意の
上記仮定と，適切な D F
⊂
0,
2X
D DE&
DE&
初期点&& ∈ (から，可変平滑化法によって⽣成された点列 &D F
DE& ⊂ (に対して

1.

∃¶ > 0, ∀§ ∈ ℕ min ∇ê T+ &D
&ÄDÄ}

2. lim inf ∇ê T+ &D
D→F

3.

lim

É→F

&Ñ É

∇ê

T/(1)

F
ÉE&

&Ñ(É)

≤

Å

∑.
+-% T+

=0
= 0を満たす部分列 &Ñ É

F
ÉE&

に対し，

の任意の集積点はê = ℎ + W ∘ ,の停留点である．

可変平滑化法： w ∈ ℕ 3x{f ≔ 3x − yx ∇S j& 3x ,

S j& = ℎ + j& X ∘ *
40/86

&
># #$% ⊂

'%

0, 2A

代理関数列 r 4!

の選択に関する考察

8

4! < ∘ * 8 のr = ℎ + < ∘ *への収束速度
=
ℎ
+
67'
67'

sup |ê & − ê T+ & | = ¢ D
)∈M

(ü → ∞)
'
(

∵ <が0L -Lipschitz連続である場合にr 4 ãä ≤ r ãä ≤ r 4 ãä + d0(L (äã ∈ .)が成⽴
勾配列 ∇r 4!

$6

8
67'

の0への収束速度

min

&ÄÑÄD

•

∇ê T/

&Ñ

1

=¢

(ü → ∞)

∑DÑE& Ñ

sup |ê & − ê T+ & |と min ∇ê T/ &Ñ のどちらの収束速度も速いことが
&ÄÑÄD

)∈M

望まれるが，これらの収束速度はトレードオフの関係である．
•

D F
DE& =

2X K&ü

%
K3

F
DE&

は¢ D = ¢

&
∑+
/-% T/

=¢ ü

%

K3

を満たすものとして，

従来の可変平滑化法[BW’21]でも採⽤されている．
[BW’21] A. Böhm and S. J. Wright, “Variable smoothing for weakly convex composite func>ons,” Journal of Op>miza>on Theory and Applica>ons, 2021.

41/86

提案法は従来の可変平滑化法[BWʼ21]の⼀般化になっている [BW’21]: ,は全射な線形写像であると仮定． 提案法: ,は連続微分可能な⾮線形写像であると仮定． 提案法は，「*が全射でない線形写像」の場合でも適⽤できるため， 正則化項が「複数の正則化関数の和」で表現されていても適⽤できる． 弱凸関数W} : -} → ℝと線形写像,} : ( → -} (§ = 1, … ¨)に対して， • W: -&× ⋯×-á : Å&, … , Åá ↦ ∑á }E& W} Å} は弱凸関数， • ,: ( → -&× ⋯×-á : & ↦ ,& & , … , ,á & は全射でない線形写像 となる． á このとき，ç W} ∘ ,} & = W ∘ ,(&) と表現される． }E& [BW’21] A. Böhm and S. J. Wright, “Variable smoothing for weakly convex composite func>ons,” Journal of Op>miza>on Theory and Applica>ons, 2021. 42/86

「可変平滑化法（無制約）」のまとめ
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 '
(-と.はユークリッド空間)

1.
2.
3.
4.

"∈'

(♠),

ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (は(上でLipschitz連続
W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
,: ( → -は連続微分可能な写像(線形写像とは限らない)
inf ℎ + W ∘ , & & ∈ ( > −∞
j

w ∈ ℕ 3x{f ≔ 3x − yx ∇ ℎ + & X ∘ * 3x
可変平滑化法：
• ℎ + W ∘ ,の代わりに微分可能なℎ + T+ W ∘ ,を活⽤するアルゴリズム
• Wの近接写像が容易に計算できるならば，内部反復アルゴリズムが不要となる．
• 直線探索法を⽤いることで，単調減少するとは限らない ñD F
DE& を利⽤できる．

可変平滑化法(variable smoothing)に関する参考⽂献

•
•
•

R. I. Boț, and C. Hendrich, “A variable smoothing algorithm for solving convex optimization problems,” TOP, 2015.
(可変平滑化法に関する最初（と思われる）の論⽂）
A. Böhm and S. J. Wright, “Variable smoothing for weakly convex composite functions,” Journal of Optimization Theory and Applications, 2021.
([Boț-Hendrich’15]の可変平滑化法を弱凸関数最適化(♠)に拡張した論⽂．ただし．#は全射な線形写像に限定されている)
KY, “A variable smoothing for weakly convex composite minimization with nonconvex constraint,” arXiv:2412.04225, 2024. (提案法)
43/86

本発表のアウトライン 1. 導⼊ 2. 数学的準備 3. 可変平滑化法（無制約） 4. 可変平滑化法（⾮凸制約付き） K. Kume and I. Yamada, “A variable smoothing for nonconvexly constrained nonsmooth optimization with application to sparse spectral clustering,” IEEE ICASSP, 2024. K. Kume and I. Yamada, “A variable smoothing for weakly convex composite minimization with nonconvex constraint,” arXiv:2412.04225, 2024. 5. 近接可変平滑化法 44

⾮凸制約付き⾮平滑⾮凸最適化問題
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 ' =: D(') (♣),
(-と.はユークリッド空間)

1.

"∈$ ⊂'

S ⊂ (は⾮空な閉⾮凸集合，「滑らかな集合」（例：多様体．後述）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞

最適化問題(♣)の現実的な⽬標＝Find 3⋆ ∈ , such that K ∈ >R S + Ub 3⋆
L ≔â
à- )

0
+∞

L∈ä
)
L∉ä
)

45/86

Hが多様体の場合の最適化問題(♣)に対する従来法
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 ' =: D(') (♣),
(-と.はユークリッド空間)

1.

"∈$ ⊂'

S ⊂ (は⾮空な閉⾮凸集合で，「滑らかな集合」（例：多様体．後述）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞
<:凸関数，
<:凸関数，

*: 線形写像
*: ⾮線形写像

Proximal gradient-type method, e.g., [CMSZ’20]
Proximal linear method, e.g., [WLC+’22]
各反復で部分問題を解くための内部反復アルゴリズムが必要となる．

<:弱凸関数，*: 線形写像

Subgradient method, e.g., [LCD+’21]

内部反復アルゴリズムは不要だが，収束は遅い傾向にある．

<:弱凸関数，*: 全射線形写像 Variable smoothing [ZWJK’23] （<が凸の場合，*の全射性は不要[BR’23]）
[CMSZ’20] S. Chen, S. Ma, A.M.C. So, T. Zhang, “Proximal gradient method for nonsmooth optimization over the Stiefel manifold,” SIAM J. Optim., 2020.
[WLC+’22] Z. Wang, B. Liu, S. Chen, S. Ma, L. Xue, H. Zhao, “A manifold proximal linear method for sparse spectral clustering with application to single-cell RNA sequencing data analysis,” INFORMS J. on Optim., 2022.
[LCD+’21] X. Li, S. Chen, Z. Deng, Q. Qu, Z. Zhu, A.M.C. So, “Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods,” SIAM J. Optim., 2021.
[ZWJK’23] Z. Peng, W. Wu, J. Hu, and K. Deng, “Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Euclidean space,” Appl. Math. Optim., 2023.
[BR’23] A. Beck, and I. Rosset, “A dynamic smoothing technique for a class of nonsmooth optimization problems on manifolds,” SIAM J. Optim., 2023.

46/86

最適化問題(♣)の難しさ=制約集合Cの扱い
Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 ' =: D(') (♣),
(-と.はユークリッド空間)

1.

"∈$ ⊂'

S ⊂ (は⾮空な閉⾮凸集合で，「滑らかな集合」（例：多様体．後述）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞

X ∘ *の⾮平滑性だけでなく，制約制約Vの扱いが最適化問題(♣)に対する
「効率的」なアルゴリズムの設計を困難にしている．
≈
本研究の着眼点

1. 内部反復アルゴリズム
2. ステップサイズ列の単調減少性

が不要

制約集合Vの「パラメータ表現」を考えることで，
無制約な最適化問題に帰着できるのでは？

47/86

制約集合のパラメータ表現と例 定義 ê ë ≔ ê C ∈ - C ∈ ë = 4が成⽴ ⾮空集合S ⊂ (はパラメータ表現可能である． ユークリッド空間Æ上で定義された連続微分可能な全射Ø: Æ → Sが存在する． ABC （ØをSのパラメータ表現と呼ぶ） パラメータ表現可能な集合の例 • (の線形部分空間ℒ ⊂ ( ℒへの直交射影⾏列±: ( → ℒはℒのパラメータ表現 ± ∘ ± = ±, ±å = ± • 単位円周上の集合≤ ≔ & = ≥&, ≥" å ∈ ℝ" & = Ø: ℝ → ≤: å ↦ cos å , sin å å は≤のパラメータ表現 ≥&" + ≥"" = 1 • Stiefel多様体¥µ ∂, ã ≔ ∑ ∈ ℝa×ç ∑å ∑ = ∏ç ∂ ≤ ã Cayley型変換[YE’03][G’13] [KY’21] [KY‘22]（後述）は¥µ(∂, ã)のパラメータ表現 [YE’03] I. Yamada and T. Ezaki, “An orthogonal matrix optimization by dual Cayley parametrization technique,” ICA, 2003. [G’13] J. Gallier, “Remarks on the Cayley representation of orthogonal matrices and on perturbing the diagonal of a matrix to make it invertible,” arXiv:math/0606320v2, 2013. [KY’21] K. Kume, and I. Yamada, “A global Cayley parametrization of Stiefel manifold for direct utilization of optimization mechanisms over vector spaces,” IEEE ICASSP, 2021. [KY’22] K .Kume, and I. Yamada, “Generalized left-localized Cayley parametrization for optimization with orthogonality constraints,” Optimization, 2022. 48/86

パラメータ表現D: E → Cを⽤いた問題の書き換え 元の最適化問題(♣) Find '⋆⋆ ∈ argmin ℎ + / ∘ 1 ' =: D(') (♣) "∈$ ⊂' Vのパラメータ表現~:  → V（連続微分可能な全射） パラメータ表現された最適化問題(♣M ) Find I⋆⋆ ∈ argmin ℎ + / ∘ 1 ∘ J I :∈; (♣< ) 最適化問題(♣é )は無制約の⾮平滑⾮凸最適化問題となる． 最適化問題(♣é )の停留点は可変平滑化法で探索できそう！ 可変平滑化法？： w ∈ ℕ 9x{f ≔ 9x − yx ∇(ℎ ∘ ~ + j& X ∘ * ∘ ~) 9x 49/86

２つの最適化問題の停留点の関係は？ 元の最適化問題(♣)の停留点$⋆ ∈ -の条件 ⋆ H F ∈ I ℎ + 4 ∘ 6 + J( K パラメータ表現された最適化問題(♣M )の停留点C⋆ ∈ ëの条件 F ∈ IH ℎ + 4 ∘ 6 ∘ D L⋆ 疑問 '⋆ = J I⋆ ∈ Kの下で，停留点条件は等価な条件か？ K ∈ >R ℎ + X ∘ * + Ub 3⋆ ⇔ K ∈ >R ℎ + X ∘ * ∘ ~ 9⋆ ? KとJの特定の条件下では，等価になる！ 50/86

⾮凸集合のregular normal cone（法錐）[RWʼ10, Def. 6.3] S ⊂ (: ⾮空集合，m &∈S ºè & m ≔ ∅) (m & ∉ Sの場合はã Rb 3 Äb 3 @ ≔ >U @ = C ∈ , inf Å íì& ê ) L = Q∈M ëí @ C, 3 − 3 sup @|| &î $zE $ îí,$∈b ||3 − 3 L − Q, ) − ) L í ) −í ) ≥0 L|| ||) − ) / ∋*→/ )∖ * * lim inf • 凸集合Sの法錐ãè (m &)の⾃然な⼀般化である． @ ≔ C∈, Åb 3 ∀3 ∈ , ≤0 E G, $ − $ lim sup E|| / ∋0→/ O∖ 0 0 ||$ − $ @ ≤0 C, 3 − 3 ºè & EとGのなす⾓は鈍⾓ $−$ m は，ざっくり⾔うと， • p∈ã 「m &の近傍で法錐の不等式」を満たす． [RW’10] R. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Verlag, 3rd edition, 2010. 51/86

⾮凸集合のregular normal cone（法錐）[RWʼ10, Def. 6.3] ºè & m ≔ ∅) (m & ∉ Sの場合はã S ⊂ (: ⾮空集合，m &∈S Rb 3 Äb 3 @ ≔ >U @ = C ∈ , inf Å íì& ê ) L = Q∈M ëí @ C, 3 − 3 sup @|| &î $zE $ îí,$∈b ||3 − 3 L − Q, ) − ) L í ) −í ) ≥0 L|| ||) − ) / ∋*→/ )∖ * * lim inf • 凸集合Sの法錐ãè (m &)の⾃然な⼀般化である． @ ≔ C∈, Åb 3 ∀3 ∈ , ≤0 E G, $ − $ lim sup E|| / ∋0→/ O∖ 0 0 ||$ − $ @ ≤0 C, 3 − 3 ºè & EとGのなす⾓は鈍⾓ $−$ m は，ざっくり⾔うと， • p∈ã 「m &の近傍で法錐の不等式」を満たす． ºè & m = ì ã ºè & m = ãè (m ã &) º m ãè & ºè & m ã m & & S （凸集合） m & （曲線・多様体） S m & [RW’10] R. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Verlag, 3rd edition, 2010. S （⾮凸集合） m & （⾮凸集合） S 52/86

L$ ' の連続性 Clarke regularity=集合の「滑らかさ」=M ⇔ （局所）閉集合S(⊂ ()はm & ∈ SにおいてClarke regularである[RW’10, Def. 1,*3/ * ． ï- 6.3] L = Q ∈ M lim sup ñ ) ≤0 def *3/ * *→/ * ºè & ºè &D s. t. p m = p m ∈ ( ∃ &D F m, ∃pD ∈ ã m = lim pD ã DE& ⊂ S with lim &D = & D→F Q456 ∈ ñ- )456 ºè & m∈ã m p ï- )4 Q4 ∈ ñ ⋯ m & ⋯ （凸集合） ⋯ ⋯ ⋯ )456 )4 Sはm &においてClarke regularでない． ⋯ Sはm &においてClarke regularである． ºè & m m p ∈ ã º m ∈ ãè & m p S ï- )456 Q456 ∈ ñ m & ï- )4 Q4 ∈ ñ S m & )456 ï D→F )456 )4 （曲線・多様体） ï- )456 Q456 ∈ ñ ï- )4 Q4 ∈ ñ )4 S ºè & m∉ã m = ì p ï- )456 Q456 ∈ ñ ï- )4 Q4 ∈ ñ ⋯ )4 )456 m⋯ & S （⾮凸集合） [RW’10] R. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer Verlag, 3rd edition, 2010. 53/86

停留点条件の等価性を保証する⼗分条件 定理 連続微分可能なØ: Æ → Sに対し，&⋆ ∈ Sと+⋆ ∈ Æが&⋆ = Ø(+⋆ )を満たすとする． SとØについて • Sは&⋆ においてClarke regular（「滑らかな集合」）， ならば ∗ ∗ ⋆ ⋆ ⋆ ºè & ⊃ Ker DØ + • ã ≔ & ∈ ( DØ + & =ì ， Øのヤコビ⾏列の転置 K ∈ >R ℎ + X ∘ * + Ub 3⋆ ⇔ K ∈ >R ℎ + X ∘ * ∘ ~ 9⋆ . • DØ +⋆ : Æ → (: æ ↦ ù û⋆ súü Kù(û⋆ ) lim はØ: Æ → (のGâteaux (Fréchet) 微分である． ú ℝ∖ ' ∋ú→' （ DØ +⋆ は線形写像） • DØ +⋆ ∗ : ( → ÆはDØ +⋆ の随伴作⽤素である． ⇔ ∀& ∈ (, ∀+ ∈ Æ +, DØ +⋆ ∗ & ⋆ + ,& = DØ + M † 54/86

停留点条件の等価性を保証する⼗分条件
系
Sはユークリッド空間(の部分多様体，Ø: Æ → Sは+⋆ ∈ Æにおいて沈め込みである
と仮定する．このとき，&⋆ ≔ Ø +⋆ ∈ Sに対し，

K ∈ >R ℎ + X ∘ * + Ub 3⋆ ⇔ K ∈ >R ℎ + X ∘ * ∘ ~ 9⋆ .
• Sは(のí < dim ( 次元部分多様体（[Boumal’23, Thm. 8.75]の定義を採⽤）
∀& ∈ S, ∃}) ⊂ (: &の開近傍, ∃¿) : }) → ℝAx° M K¢ : 連続微分可能な写像
ABC

s.t. S ∩ }) = ¿)K& ì and Rank D¿) &

= dim ( − í

（例：線形部分空間， Stiefel多様体òô ö, õ ≔ ú ∈ ℝP×Q úR ú = ûQ ）

• Ø: Æ → Sは+⋆ ∈ Æにおいて沈め込み[Tu’11, Sect. 8.8]
ABC

Gâteaux (Fréchet) 微分DØ +⋆ : Æ → ≈è &⋆ : æ ↦

ù û⋆ súü Kù(û⋆ )
lim
は全射
ú
ℝ∖ ' ∋ú→'

†O $⋆ の直交補空間）
（üO ($⋆ ): 4の$⋆ ≔ ê C⋆ における接空間= õ

[Boumal’23] N. Boumal, An introduc%on to op%miza%on on smooth manifolds, Cambridge University Press, 2023.
[Tu’11] L. W. Tu, An introduc%on to Manifolds, Springer, 2nd edi>on, 2011 （邦訳「トゥー多様体，升⽥・阿部・堀⼝訳，裳華房，2019」もある）.

55/86

閉凸集合Cは停留点条件の等価性を担保できるか？ A ．多くの閉凸集合Vに対して，等価性は担保できない． 命題(informal) ∃S ⊂ (: ⾮空な閉凸集合, ∃ê ≔ ℎ + W ∘ ,: ( → ℝ, ∃&⋆ ∈ (, ∀Ø: Æ → S: Sのパラメータ表現, ∀+⋆ ∈ Æ: Ø +⋆ = &⋆ s. t. ì ∈ o ê ∘ Ø +⋆ but ì ∉ o ê + «è &⋆ 例えば，下記の閉凸集合は上記命題のSの例となっている． • ⾮負制約 & ∈ ℝD ≥ ` ≥ 0, ä = 1,2, … , ü • （半径∆ > 0の）閉球 & ∈ ℝD & ≤ ∆ この場合，パラメータ表現を⽤いた可変平滑化法を⽤いた停留点の探索は難しいが， 後述の「近接可変平滑化法[KY’25]」を⽤いれば， 制約集合Sが閉凸集合（かつ射影計算が簡単）である場合，停留点を探索できる． [KY’25] K. Kume and I. Yamada, “A proximal variable smoothing for nonsmooth minimization involving weakly convex composite with MIMO application,” IEEE ICASSP, 2025 (to appear, arXiv:2409.10934) 56/86

パラメータ表現を⽤いた可変平滑化法 制約集合S ⊂ (とパラメータ表現Ø: Æ → Sの適切な仮定の下で， ℎ + W ∘ , ∘ Øの停留点+⋆ ∈ Æについて，Ø +⋆ ∈ S はℎ + W ∘ ,のS 上の停留点となる． パラメータ表現された最適化問題の停留点探索問題 Find 9⋆ ∈  s. t. K ∈ >R ℎ + X ∘ * ∘ ~ 9⋆ 可変平滑化法： w ∈ ℕ 9x{f ≔ 9x − yx ∇ S j& ∘ ~ dx ∈ 0, 2t zf , yx > 0, 9x S j& = ℎ + j& X ∘ * F D F DE& と ñD DE& の選び⽅については，無制約の場合の可変平滑化法と同様． 57/86

&
># #$% ⊂

0, 2A

'%

の条件（再掲）

3' の条件
d6 8
67' ⊂ 0, 2e

1. lim dx = 0 （ê T のgradient consistencyを活⽤するため）
x→y
2. ∑y
xhf dx = ∞ （収束解析で必要となるため[後述]）
3. ∀w ∈ ℕ dx{f ≤ dx （D の単調減少性を保証するため）
j&
4. ∃| ≥ 1, ∀w ∈ ℕ j ≤ |
&'%

（ ê T+,% (m
&) ≤ ê T+

m
&

&
+ " õÑ"U D − Ds&

3' の例
d6 8
67' ⊂ 0, 2e
% y
zf z(
•
2t w
}≥1
xhf
y
f

•

(} x{f ~Ä x{f

xhf

[H’02] H.-K. Xu, “Iterative algorithms for nonlinear operators,” J. Lond. Math. Soc., 2002.

の成⽴を保証するため）
• 条件1,2,4を満たす数列は
不動点理論の⽂脈でも
考察されている[H’02]．
• 実⽤的に⽤いられる D F
DE&
については後述．
58/86

ステップサイズB# のための仮定
仮定

ある正定数û&, û" > 0が存在して，任意のü ∈ ℕに対して，
∇ ê T+ ∘ Ø = ∇ ℎ + T+ W ∘ , ∘ Ø は û& + û"DK& -Lipschitz連続である．
Ñ∇(u &+ ∘ù) ≔
⼗分条件

1.
2.

sup

)∈2,34 5

D- "

,- < +∞;

3.

∃2./ > 0, ∀"0 , "1 ∈ =
D- "0 − D- "1 ,- ≤ 2./ "0 − "1 ;
sup ∇ℎ " < +∞;

4.

sup DC :

5.

)∈5

6∈7

,- < +∞;

∃2.8 > 0, ∀:0 , :1 ∈ ;
DC :0 − DC :1 ,- ≤ 2.8 :0 − :1 ;

• ,が線形写像ならば，
1と2は満たされる．

• Sが有界閉集合ならば，
1と2は満たされる．
さらに，ℎが2回連続微分可能ならば，
3も満たされる．
• Øが線形写像ならば，
4と5は満たされる

（この場合，4は-の線形部分空間となる）．
59/86

ステップサイズB# の条件
仮定

ある正定数û&, û" > 0が存在して，任意のü ∈ ℕに対して，
∇ ê T+ ∘ Ø = ∇ ℎ + T+ W ∘ , ∘ Ø は û& + û"DK& -Lipschitz連続である．
Ñ∇(u &+ ∘ù) ≔
|6 8
67' ⊂ 0, +∞ の条件

ある正定数ú > 0とù ∈ (0,1)が存在して，任意のü ∈ ℕに対して，
1. ñD ≥ úÑK&
;
∇(u &+ ∘ù)
2.

ê T+

∘Ø

+D − ñD ∇ ê T+

∘ Ø +D

≤ ê T+

∘ Ø +D − ùñD

∇(ê ∘ Ø) T+

+D
（Armijo条件）

"

60/86

ステップサイズB# の例

r 4! ∘ êの0∇(E "! ∘T) -Lipschitz連続性の下での |6 8
67' ⊂ 0, +∞ の条件（再掲）

ある正定数ú > 0とù ∈ (0,1)が存在して，任意のü ∈ ℕに対して，
1. ñD ≥ úÑK&
;
∇(u &+ ∘ù)
ê T+

2.

∘Ø

+D − ñD ∇ ê T+

∘ Ø +D

≤ ê T+

∘ Ø +D − ùñD

∇(ê T+ ∘ Ø) +

"
D

（Armijo条件）
|6 8
67' ⊂ 0, +∞ の例

•

" &Kv T+
K&
ñD ≔ 2 1 − ù Ñ∇(u &+ ∘ù) = w T sw = ¢ D
% +
!

• 直線探索法(backtracking algorithm，例えば[A’20])によるñD の推定：
ñD ≔ max ñxyxzx{| £} § ∈ ℕ ∪ 0 , ñxyxzx{| £} はArmijo条件を満たす
（|FGFHFIJ àK がArmijo条件を満たすまで ，初期候補|FGFHFIJ > 0 にà ∈ 0,1 を乗じ続ける）

• •~ F
~E の単調減少性は不要
直線探索法を⽤いれば，
• 定数Ñ∇(u &+ ∘ù) の知識は不要
[A’20] N. Andrei, Nonlinear Conjugate Gradient Methods for Unconstrained Optimization. Springer, 2020.

「効率的」その２
61/86

収束解析
仮定

ある正定数û&, û" > 0が存在して，任意のü ∈ ℕに対して，
∇ ê T+ ∘ Ø = ∇ ℎ + T+ W ∘ , ∘ Ø は û& + û"DK& -Lipschitz連続である．
定理
K& と ñ F ⊂ 0, +∞ の下で，任意の
上記仮定と，適切な D F
⊂
0,
2X
D DE&
DE&
初期点+& ∈ Æから，可変平滑化法によって⽣成された点列 +D F
DE& ⊂ Æに対して

1.

∃¶ > 0, ∀§ ∈ ℕ min ∇ ê T+ ∘ Ø +D
&ÄDÄ}

2. lim inf ∇ ê T+ ∘ Ø +D
D→F

3.

lim

É→F

+Ñ É

∇ ê
F
ÉE&

T/(1)

∘Ø

≤

Å

∑.
+-% T+

=0

+Ñ(É)

= 0を満たす部分列 +Ñ É

F
ÉE&

に対し，

の任意の集積点はê ∘ Ø = ℎ + W ∘ , ∘ Øの停留点である．

可変平滑化法： w ∈ ℕ 9x{f ≔ 9x − yx ∇ S j& ∘ ~

9x , S j & = ℎ + j & X ∘ *
62/86

応⽤例：Stiefel多様体制約付き⾮平滑最適化
Find N⋆⋆ ∈ argmin ℎ + / ∘ 1 N =: D(N) (♣),

1.
2.
3.
4.
5.

D∈EF(G,H)
¥µ ∂, ã ≔ {∑ ∈ ℝa×ç ∣ ∑å ∑ = ∏ç } ⊂ ℝa×ç : Stiefel多様体
ℎ: ℝa×ç → ℝは連続微分可能，∇ℎ: ℝa×ç → ℝa×ç は¥µ(∂, ã)上でLipschitz連続
W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
,: ℝa×ç → -は連続微分可能な写像(線形写像とは限らない)
inf ℎ + W ∘ , ∑ ∑ ∈ ¥µ(∂, ã) > −∞

応⽤例 (最近のreview paper [CMSZ’24]についても参照されたい)
• スパース主成分分析 [JTU’03]
• Sparse blind deconvolution [ZLK+’17]
• スパーススペクトルクラスタリング [LYL’16]
[CMSZ’24] S. Chen, S. Ma, A. M.-C. So, and T. Zhang, “Nonsmooth op>miza>on over the S>efel manifold and beyond: Proximal gradient method and recent variants,” SIAM Rev., 2024.
[JTU’03] I. Jolliffe, N.Trendafilov, and M. Uddin, “A modified principal component technique based on the LASSO,” Journal of Computa>onal and Graphical Sta>s>cs, 2003.
[ZLK+’17] Y. Zhang, Y. Lau, H.-W. Kuo, S. Cheung, A. Pasupathy, and J. Wright, “On the global geometry of sphere-constrained sparse blind deconvolu>on,” IEEE CVPR, 2017.
[LYL’16] C. Lu, S. Yan, Z. Lin, “Convex sparse spectral clustering: Single-view to mul>-view,” IEEE Trans. Image Process., 2016.
63/86

Stiefel多様体のパラメータ表現
⼀般化逆Cayley変換 [KY’22]

直交⾏列— ∈ ¢ ã ≔ ¥µ(ã, ã)に対して，⼀般化逆Cayley変換は以下で定義される：
å
ç×ç
Õ −Œå
zf
a×a Õ = −Õ ∈ ℝ
Φ° :  ≔
∈ℝ
→ ÖÜ á, Å ∖ âi,¢ (ä)
aKç ×ç
Œ
ì
Œ∈ℝ
ñ
K&
∏
∶ – ↦ — ∏ − – ∏ + – ∏a×ç
§7×9
ただし，“a,ç — ≔ ∑ ∈ ¥µ ∂, ã
¨7,9 ´ ≔

det ∏ç + ∑å —∏a×ç = 0

•

単位球⾯上の集合 òô(1,3)
＝ΦU3' (¶, ß)

ステレオ投影（の逆写像）は
⼀般化逆Cayley変換の特別な例
´§7×9 ≔
¶, ß ∈ ℝ = ℝ% ×{−1} ≡ ℝ%

[KY’22] K. Kume and I. Yamada, “Generalized left-localized Cayley parametrization for optimization with orthogonality constraints,” Optimization, 2022.

≔

¶, ß, −1

†
64/86

Stiefel多様体のパラメータ表現 ⼀般化逆Cayley変換 [KY’22] 直交⾏列— ∈ ¢ ã ≔ ¥µ(ã, ã)に対して，⼀般化逆Cayley変換は以下で定義される： å ç×ç Õ −Œå zf a×a Õ = −Õ ∈ ℝ Φ° :  ≔ ∈ℝ → ÖÜ á, Å ∖ âi,¢ (ä) aKç ×ç Œ ì Œ∈ℝ ñ K& ∏ ∶ – ↦ — ∏ − – ∏ + – ∏a×ç §7×9 ただし，“a,ç — ≔ ∑ ∈ ¥µ ∂, ã det ∏ç + ∑å —∏a×ç = 0 • ⼀般の¥µ(∂, ã)に対しては，“a,ç (—)は無限集合だが⋯ ∀Æ ∈ Ø∞ •, ñ , ∃ Æ4 , 4:6 ⊂ Ø∞ •, ñ ∖ ¨7,9 ´ s. t. lim Æ4 = Æ 4→, • ¥µ ∂, ã ∖ “a,ç (—)は¥µ(∂, ã)の稠密開部分集合である． ≈ 「¥µ(∂, ã)のほぼすべての点」はΦ´K&によりパラメータ表現可能 • “a,ç (—)はÆの無限遠点に相当している． Cayleyパラメータ表現法 [KY’22] Minimize ê(∑) ΦU3'でòô(ö, õ)（の稠密開部分集合）をパラメータ表現 Æ∈µú(ç,a) Minimize ê ∘ Φ´K&(–) ∂∈† [KY’22] K. Kume and I. Yamada, “Generalized lek-localized Cayley parametriza>on for op>miza>on with orthogonality constraints,” Op>miza>on, 2022. 65/86

⼀般化逆Cayley変換は有益な性質を持つパラメータ表現である

Find N⋆⋆ ∈ argmin ℎ + / ∘ 1 N =: D(N) (♣),

D∈EF(G,H)
¥µ ∂, ã ≔ {∑ ∈ ℝa×ç ∣ ∑å ∑ = ∏ç } ⊂ ℝa×ç : Stiefel多様体
ℎ: ℝa×ç → ℝは連続微分可能，∇ℎ: ℝa×ç → ℝa×ç は¥µ(∂, ã)上でLipschitz連続
W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
,: ℝa×ç → -は連続微分可能な写像(線形写像とは限らない)
inf ℎ + W ∘ , ∑ ∑ ∈ ¥µ(∂, ã) > −∞

1.
2.
3.
4.
5.
系

任意の° ∈ ® õ = òô(õ, õ)に対して，

i.

J⋆ ∈ ;とD⋆ ≔ Φ:;0 J⋆ ∈ MN O, P ∖ R<,> (S)について，以下の関係が成⽴する：
ì ∈ oy ℎ + W ∘ , ∘ Φ´K& –⋆ ⇔ ì ∈ oy ℎ + W ∘ , + «µú ç,a ∑⋆

ii.

ℎ: ℝ<×> → ℝが2回連続微分可能ならば，ある正定数X0 , X1 > 0が存在して，
任意のY ∈ (0, Z;0 )に対して ∇

ℎ + ? [ ∘ - ∘ Φ:;0 は X0 + X1 Y;0 -Lipschitz連続である．
66/86

数値実験例1：スパース主成分分析 [JTUʼ03],[CMMZʼ20] ℐ個のã次元データを並べた⾏列◊ ∈ ℝℐ×a から， ∂個のスパースな主成分ベクトルÿ&, ÿ", … , ÿç ∈ ℝa を抽出する問題 ∑のスパース性を促進する Minimize − Tr ç´ é ´ éç + è ç f (è > 0) ú∈©™(¢,i) ◊∏◊ ∈ ℝa×a のRayleigh商 （最⼤化する∑⋆⋆ ∈ ¥µ(∂, ã)は，⼤きい⽅から∂個の 固有値に対応する固有空間の正規直交基底を並べた⾏列） ℎ Ÿ ≔ −Tr(Ÿå ◊∏◊Ÿ), W ≔ e‖ ⋅ ‖&, , = Idとすることで，上の最適化問題の 停留点探索問題は ℎ + W ∘ , ∘ Φ´K&の停留点探索問題に書き換えられる． 可変平滑化法で解ける！ [JTU’03] I. Jolliffe, N.Trendafilov, and M. Uddin, “A modified principal component technique based on the LASSO,” Journal of Computa>onal and Graphical Sta>s>cs, 2003. [CMMZ’20] S. Chen, S. Ma, S., A.M.C. So, and T. Zhang, “Proximal gradient method for nonsmooth op>miza>on over the S>efel manifold,” SIAM J. Op>m., 2020. 67/86

⼩

ã

∂

⼤

⽐較⼿法
多様体制約付き最適化に拡張された
可変平滑化法 (RSmooth) [BR’23]
劣勾配法 (RSub) [LCD+’21]
近接勾配法 (ManPGAda) [CMMZ’20]
各反復で部分問題を解くために
内部反復アルゴリズムが必要

提案可変平滑化法 (VSmooth)
∂456 ≔ ∂4 − π4 ∇ (ℎ + &" , ∘ ª) ∘ Φ;36 ∂4
'
3V
3'
2e ¨

d6 ≔
|6 : 直線探索法で推定
•
•
⼤

提案法はRSmoothとRSubよりも
速い収束を達成している
öが⼩さい場合は提案法よりも
ManPGAdaの⽅が収束は速いが，
öが⼤きい場合は提案法の⽅が速い

[BR’23] A. Beck, and I. Rosset, “A dynamic smoothing technique for a class of nonsmooth op^miza^on problems on manifolds,” SIAM J. Op^m., 2023.
[LCD+’21] X. Li, S. Chen, Z. Deng, Q. Qu, Z. Zhu, and A.M.C. So, “Weakly convex op^miza^on over S^efel manifold using Riemannian subgradient-type methods,” SIAM J. Op^m., 2021.
[CMMZ’20] S. Chen, S. Ma, S., A. Man-Cho So, and T. Zhang, “Proximal gradient method for nonsmooth op^miza^on over the S^efel manifold,” SIAM J. Op^m., 2020.

数値実験例2：スパーススペクトルクラスタリング ¢ を∂個のグループに割り当てる⼿法 クラスタリング: ã個のデータ ‹Ω a ⊂ ℝ ΩE& スペクトルクラスタリング(SC) [NJWʼ01] 1. ‹Ω a ΩE& の類似度(affinity)グラフ›を⽣成する(例: kNNグラフ [AST’21]) 2. ›を∂個の連結成分(極⼤な連結部分グラフ)に分割する # 3$ # 3$ ≠のグラフラプラシアンÆ ≔ û − Ø ∞Ø ∈ ℝP×P の性質を利⽤ i. Æの固有値0の多重度が連結成分数に⼀致する． ii. 固有値0の固有ベクトルから連結成分に分割できる． ∞ ∈ ℝP×P : ≠の隣接⾏列 Ø ∈ ℝP×P : ≠の次数⾏列 分割 類似度グラフ ≠ 3つの連結成分 [NJW’01] A. Ng, M. Jordan, Y. Weiss, “On spectral clustering: Analysis and an algorithm,” NeurIPS. 2001. [AST’21] M. Alshammari, J. Stavrakakis, M. Takatsuka, “Refininga k-nearest neighbor graph for a computationally efficient spectral clustering,” Pattern Recognit., 2021. 69/86

数値実験例2：スパーススペクトルクラスタリング ¢ を∂個のグループに割り当てる⼿法 クラスタリング: ã個のデータ ‹Ω a ⊂ ℝ ΩE& スペクトルクラスタリング(SC) [NJWʼ01] 1. ‹Ω a ΩE& の類似度(affinity)グラフ›を⽣成する(例: kNNグラフ [AST’21]) 2. ›を∂個の連結成分(極⼤な連結部分グラフ)に分割する # 3$ # 3$ ≠のグラフラプラシアンÆ ≔ û − Ø ∞Ø ∈ ℝP×P の性質を利⽤ i. Æの固有値0の多重度が連結成分数に⼀致する． ii. 固有値0の固有ベクトルから連結成分に分割できる． ∞ ∈ ℝP×P : ≠の隣接⾏列 Ø ∈ ℝP×P : ≠の次数⾏列 2(a) fiの⼩さい⽅から∂個の固有値に対応する固有ベクトルの探索 Find ∑⋆ ∈ argmin Tr ∑å fi∑ Æ∈µú ç,a 2(b) ∑⋆ の各⾏ベクトルを ‹Ω a ΩE& の特徴量ベクトルとして、 k-meansアルゴリズムによりクラスタリング [NJW’01] A. Ng, M. Jordan, Y. Weiss, “On spectral clustering: Analysis and an algorithm,” NeurIPS. 2001. [AST’21] M. Alshammari, J. Stavrakakis, M. Takatsuka, “Refininga k-nearest neighbor graph for a computationally efficient spectral clustering,” Pattern Recognit., 2021. 70/86

数値実験例2：スパーススペクトルクラスタリング
¢ を∂個のグループに割り当てる⼿法
クラスタリング: ã個のデータ ‹Ω a
⊂
ℝ
ΩE&

スペクトルクラスタリング(SC) [NJWʼ01]

1. ‹Ω a
ΩE& の類似度(affinity)グラフ›を⽣成する(例: kNNグラフ [AST’21])
2. ›を∂個の連結成分(極⼤な連結部分グラフ)に分割する
理想的な状況下では「 Æ⋆ Æ⋆= がブロック対⾓、すなわちスパースである」
という先験情報を活⽤(スパースSC) [LYL’16]

2ʼ(a) Find ∑⋆ ∈ argmin Tr ∑å fi∑ + e6 ∑∑å
Æ∈µú ç,a

(æ > 0, ¿: ℝ7×7 → ℝ:スパース度を測る関数)

ℎ ± ≔ Tr ±R Ʊ , < ≔ ≤D ⋅ , * ± ≔ ±±R で置き換え，ΦU3' によるパラメータ表現を考えると⋯

2ʼʼ(a) Find –⋆ ∈ argmin ℎ + W ∘ , ∘ Φ´K&(–)
∂∈†

可変平滑化法で解ける！
[NJW’01] A. Ng, M. Jordan, Y. Weiss, “On spectral clustering: Analysis and an algorithm,” NeurIPS. 2001.
[AST’21] M. Alshammari, J. Stavrakakis, M. Takatsuka, “Refininga k-nearest neighbor graph for a computationally efficient spectral clustering,” Pattern Recognit., 2021.
[LYL’16] C. Lu, S. Yan, Z. Lin, “Convex sparse spectral clustering: Single-view to multi-view,” IEEE Trans. Image Process., 2016.

71/86

UCI Machine Learning Repositoryの実データを⽤いた性能⽐較結果 評価指標(100回平均) • NMI: Normalized Mutual Information [SG’03] • ARI: Adjusted Rand Index [HA’85] (値が1に近いほど良好なクラスタリング性能を持つことを意味する) [NJW’01] [LYL’16] 提案法 提案法: スパース性評価関数として，ℓ' ノルムと弱凸関数MC罰則関数を採⽤ MC罰則関数を採⽤した提案法の優位性が確認できる 補⾜: ℓ6 ノルムの場合，多様体制約付きに拡張されたProx-linear法[WLC+’22]（ただし，内部反復あり）で解ける [NJW’01] A. Ng, M. Jordan, Y. Weiss, “On spectral clustering: Analysis and an algorithm,” NeurIPS, 2001. [LYL’16] C. Lu, S. Yan, Z. Lin, “Convex sparse spectral clustering: Single-view to multi-view,” IEEE Trans. Image Process., 2016. [SG’03] A. Strehl, J. Ghosh, “Cluster ensembles — a knowledge reuse framework for combining multiple partitions,” J Mach. Learn. Res., 2003. [HA’85] L. Hubert, P. Arabie, “Comparing partitions,” J Classif., 1985. [WLC+’22] Z. Wang, B. Liu, S. Chen, S. Ma, L. Xue, and H. Zhao, ”A manifold proximal linear method for sparse spectral clustering with application to single-cell RNA sequencing data analysis,” 72/86 INFORMS J. on Optim., 2022.

「可変平滑化法（⾮凸制約付き）」のまとめ
Find &⋆⋆ ∈ argmin ℎ + . ∘ 0 & =: 3(&) (♣),
(-と.はユークリッド空間)

1.

"∈$ ⊂'

S ⊂ (は⾮空な閉⾮凸集合で，Clarke regular（例：多様体）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 !"# , + $% || ⋅ ||% は凸
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞
可変平滑化法： w ∈ ℕ 9x{f ≔ 9x − yx ∇

ℎ + j & X ∘ * ∘ ~ 9x

• Sのパラメータ表現Ø: Æ → Sを⽤いて，êの停留点条件とê ∘ Øの停留点条件が
等価となるための⼗分条件を導出した．
• ê ∘ Øの停留点探索問題に対する可変平滑化法の応⽤を紹介した．
制約集合のパラメータ表現に関する参考⽂献
•

E. Levin, J. Kileel, and N. Boumal, “The effect of smooth parametrizations on nonconvex optimization landscapes,” Math. Program., 2024.
(⽬的関数が微分可能な場合に，Clarke regularとは限らない制約付き最適化問題と
73/86
パラメータ表現による無制約最適化問題について，停留点条件の関係が⽰された論⽂）.

本発表のアウトライン 1. 導⼊ 2. 数学的準備 3. 可変平滑化法（無制約） 4. 可変平滑化法（⾮凸制約付き） 5. 近接可変平滑化法 K. Kume and I. Yamada, “A proximal variable smoothing for nonsmooth minimization involving weakly convex composite with MIMO application,” IEEE ICASSP, 2025 (to appear, arXiv:2409.10934) 74

本講演全体のまとめ
Find &⋆⋆ ∈ argmin ℎ + . ∘ 0 &
(-と.はユークリッド空間)

1.

"∈$(⊂')

(♣),

S ⊂ (は⾮空な閉集合（凸の場合と⾮凸の場合も考えていく）

2. ℎ: ( → ℝは連続微分可能，∇ℎ: ( → (はS上でLipschitz連続
3. W: - → ℝはLipschitz連続(微分可能とは限らない)なX-弱凸関数 345 A + 62 || ⋅ ||2は凸関数
4. ,: ( → -は連続微分可能な写像(線形写像とは限らない)
5. inf ℎ + W ∘ , & & ∈ S > −∞
• 最適化問題(♣)に対する可変平滑型アルゴリズム（可変平滑化法・
近接可変平滑化法）を紹介した．
• 可変平滑型アルゴリズムは微分可能な代理関数列 ℎ + T+ W ∘ , F
DE& を活⽤する．
その結果，内部反復が不要になり，戦略的なステップサイズの利⽤が可能となる．
• 可変平滑型アルゴリズムを信号処理に応⽤し，その優れた数値性能を確認した．
86/86