学習アルゴリズムの⼤域収束性と帰納的バイアス
⼆反⽥篤史
東京⼤学 / 理研AIP / JSTさきがけ
情報論的学習理論ワークショップ（IBIS2019）
企画セッション「深層学習の理論」
2019年11⽉22⽇@ウインクあいち発表概要
深層学習に対する（確率的）勾配降下法の理論
近年の重要な進展• Over-parameterizationの役割• 帰納的バイアス
理論的困難c• ⾮凸最適化問題に対する⼤域的収束性• 最適化で得られる関数の汎化性能保証

1. 深層学習における最適化の研究課題

機械学習における最適化問題
パラメータΘ，関数𝑓#: 𝒳 → ℝ，
データとパラメータの適合度（損失関数）𝑙(𝑦, 𝑓, (𝑥))．
• ⼆乗損失𝑙 𝑦, 𝑧 = 0.5 𝑦 − 𝑧 5• ロジスティック損失 𝑙 𝑦, 𝑧 = log 1 + exp −𝑦𝑧
期待損失最⼩化

真に解きたい問題．

min 𝔼 𝑙(𝑌, 𝑓# (𝑋)#∈ℱ

経験損失最⼩化

訓練データによる近似．

K
1min G 𝑙 𝑦H , 𝑓# 𝑥H
#∈ℱ 𝑛
HIJ

+ 𝜆𝑅(Θ)4

深層ニューラルネット
𝑳-層ニューラルネット

𝑜

Θc
ℎ5c

ℎ55

ℎJ5

ℎ5d

J

Θ5
ℎJc

ℎJ5

ℎJJ

ℎJd

𝑥5

𝜎 ℎ = max 0, ℎ , 𝜎 ℎ = JXYZ[(\]) .
ℎ^ = 𝑥,ℎO = 𝜎 Θ_O ℎO\J

ΘJ
𝑥J

パラメータΘ = ΘO POIJ, ΘO ∈ ℝKQRS ×KQ ,⾮線形活性化関数𝑙 ∈ 0, … , 𝐿 ,𝑜 = 𝑓# 𝑥 = ℎP .

𝑥c

例：三層ニューラルネット

多層ニューラルネットは⾮線形関数▶ ⾮凸最適化問題

⾮凸最適化問題
⼀次の勾配法は基本的に停留点へ収束：∇#ℒ Θ∗ = 0.
極⼤解
（局所解）
最⼩解
（⼤域的最適解）

凸関数

極⼩解
（局所解）

最⼩解
（⼤域的最適解）

⾮凸関数

凸最適化では”停留点＝⼤域的最適解”
⾮凸最適化問題に対しての⼤域収束性保証は困難．
深層学習
⾼次元ニューラルネットは⾮凸だが経験的に⼤域収束する．

Landscape解析
損失関数の性質を解析（真の局所解の存在，⼤域最適解へのdescent pathの存在）

Positive

Negative

⼆乗損失の場合• 𝑚 = 1，活性化関数がシグモイド▶ 局所解の数が次元について指数的に増加．[Auer, Herbster, & Warmuth (1996)]• ReLU，期待損失，教師・⽣徒ネットワークで同じ中間ノード数(6 ≤ 𝑚 ≤ 20)▶ 多数の局所解が存在．[Safran & O. Shamir (2018)]• 𝑛 ≥ 𝑚 + 2𝑑 − 2, ReLU
▶ 最適解へのdescent pathが存在しないデータが存在（⾮ゼロ測度）[ICLR submission (2019]• Leaky ReLU，𝑚𝑑 ≥ 𝑛▶ 可微分点かつ局所解は誤差0を達成．[Soudry & Carmon (2016)]• 𝑚 ≥ 𝑛，連続な活性化関数▶ 任意の初期点から誤差0 の解へのdescent pathが存在．[Venturi, Bandeira, & Bruna (2018)]
その他，出⼒層へのskip-connectionが真の局所解を解消する事を⽰す研究．
平滑化ヒンジ [Liang, Sun, Lee, & Srikant (2018)]，交差エントロピー[Nguyen, Mukkamala, & Hein (2019)]．

Landscape解析
Landscape解析に基づく⼤域的収束性

次の性質を満たせばstrictな鞍点を回避する⼿法は⼤域収束．該当⼿法
ノイズ付き勾配法，
1. 全ての局所解は最適
負曲率⽅向の探索法
2. 全ての鞍点はstrict
これらは⼆乗活性化関数に対して⽰されているが，（⼆乗損失の場合 [Soltanolkotabi, A. Javanmard, & J. Lee]，平滑凸損失の場合 [Du & Lee (2018)]）

a. 対象の最適化法が限定的
b. 収束率を出すには更なる仮定も必要
c. ⼤域解の汎化性能も様々▶ 勾配法，確率的勾配降下法のより直接的な解析へ

学習アルゴリズムの帰納的バイアス
深層モデルでは多様な⼤域解
⼤域解の汎化性能も様々
収束先は学習の仕⽅に依存．
• 層毎のノード数• パラメータ初期化スケール• モデルのスケール• 学習アルゴリズム

左：訓練精度，右：予測精度[Luo, Xiong, Liu, & Sun (2019)]

学習法が備える帰納的バイアス
学習の条件により本質的に学習ダイナミクスと収束先が特徴付けられる．
▶ 帰納的バイアスで深層モデルを汎化させている説（陰的な正則化）
9最適化の重要な研究課題
経験的事実• 学習アルゴリズムの⼤域的収束性• 得られたパラメータの優れた汎化性
これらの現象を説明する理論を構築したい
深層学習における最適化の研究課題
1. 学習アルゴリズムの⼤域的収束性と収束率
2. 学習法依存の帰納的バイアスの解明
この⼆つの課題は⼀体となって解析される場合も多い．
最近のアプローチ：ニューラルタンジェント，Wasserstein勾配流等10

2. ⾼次元ニューラルネットに対する勾配法の⼤域的収束性と汎化性能解析（帰納的バイアス：Kernel regime）

勾配法の⼤域的収束性
2018–2019年，over-parameterizeされた深層ニューラルネットに対し勾配法の⼤域収束性が⽰された．[Allen-Zhu, Li, & Song (2019)], [Du, Lee, Li, Wang, Zhai (2019)]
表：⼤域収束の条件⽐較（ [Zou & Gu (2019)]より引⽤）

DNNの結果[Zou & Gu (2019)]

Over-parametrizeでニューラルタンジェントカーネル [Jacot, Gabriel, & Hongler (2019)] の
regimeで収束する事が重要．(帰納的バイアス：NTK regime)

勾配降下法J

経験損失最⼩化：min ℒ Θ : = K ∑KHIJ 𝑙 𝑦H , 𝑓# 𝑥H#.

勾配降下法 𝜂 > 0 : 学習率（ステップサイズ），
Θ(oXJ) = Θ(o) − 𝜂∇ℒ Θ(o) .
※ ReLUの場合はsemi-smoothnessを⽤いる．

[Allen-Zhu, Li, & Song (2019)]
勾配∇ℒ Θ(o) はℒを局所的な⼀次近似：
_
5
(o)
(o)
(o)
(o)
ℒ Θ =ℒ Θ+ ∇ℒ Θ
Θ−Θ
+𝑂 Θ−Θ
.
5

学習率が⼗分⼩さい時：ℒ Θ(oXJ) ≤ ℒ Θ o

𝜂
5
o
(o) .
− ∇ℒ Θ
≤ℒΘ
52▶ 停留点で無ければ勾配降下法で⽬的関数を減少
13ニューラルタンジェントカーネル[Jacot, Gabriel, & Hongler (2018)]

ニューラルタンジェントカーネル（NTK）は微分∇#𝑓#が定めるカーネル．
NT： ∇#𝑓#: 𝑥 ∈ ℝs → ∇#𝑓# 𝑥 ∈ ℝts ,NTK： 𝑘# 𝑥, 𝑥 v = ∇#𝑓# 𝑥 _∇#𝑓# 𝑥 v .

訓練データ 𝑥H KHIJ上のグラム⾏列：𝐾# =𝑘# 𝑥, 𝑥

v

P

=G

OIJ
P
= ∑OIJ 𝜕|Q 𝑓| 𝑥 _ 𝜕|Q 𝑓| 𝑥 v

𝑘# 𝑥H , 𝑥x

簡単な計算から関数勾配： ∇y ℒ 𝑓# = 𝜕{ 𝑙 𝑦H , 𝑓# 𝑥H
∇ℒ Θ

5
5 =

𝑘#Q 𝑥, 𝑥 v

K
H,xIJ
K

.

.

HIJ

に対し，

1
_𝐾 ∇ ℒ 𝑓 .
∇
ℒ
𝑓
# y
#
𝑛5 y #
14

ニューラルタンジェントカーネル[Jacot, Gabriel, & Hongler (2018)]

従って， 𝜆}HK 𝐾# > 0であれば⼤域解でない限り最適化が進む：
K

∇#ℒ Θ

5
5 =

1
𝜆}HK 𝐾#_∇y ℒ 𝑓# 𝐾#∇y ℒ 𝑓# ≥G 𝜕{ 𝑙 𝑦H , 𝑓# 𝑥H
5
5
𝑛
𝑛

5

HIJ

関数勾配ノルム ▶ ⼤域的最適解でなければ⾮ゼロ⼆乗損失の場合： ∇#ℒ Θ

5~•€• ‚ƒ
5
（パラメータ依存のPL-不等式）
ℒ
Θ
5 ≥
„
K

学習中の正定値性を担保するには？
▶ 適切な設定下でのニューラルネットのOver-parameterization
15

NTKによる⼤域収束性の基本戦略
NTKによる⼤域収束性を⽰す基本ステップ

1. 初期点でのNTKの正定値性：𝐾#(…) ≽ 𝜆𝐼 ≻ 0,
2. 最適化中NTKの変化が⼩さい： 𝐾#(…) ∼ 𝐾# Š .
NTK regime：最適化中，上記性質が保たれる帰納的バイアスにある設定．
※ ⼆乗損失の場合▶ NTK regimeでは勾配法は線形収束（指数収束）：
𝜂
1
5
(^)
(oXJ)
o
o
ℒ Θ
≤ℒ Θ
− ∇#ℒ Θ
≤
1
−
𝜂𝜆
𝐾
5
2
2𝑛 }HK #ℒ Θ(o)

線形収束性

16

NTK regimeの意味• 正定値カーネル𝑘: 𝒳×𝒳 → ℝに付随するRKHSでの勾配降下法：
RKHSでの勾配 𝑇• ∇y ℒ 𝑓 𝑋

J K= K ∑HIJ 𝑘 𝑥H , 𝑋 ∇y ℒ(𝑓)(𝑥H )により以下の更新

𝑓 (oXJ) = 𝑓 (o) − 𝜂𝑇• ∇y ℒ 𝑓 (o) .
• ⼩さな学習率での勾配法 Θ(oXJ) = Θ(o) − 𝜂∇#ℒ Θo は次の関数更新を誘導：
𝑓#(Š‘S) ≅ 𝑓#(Š) − 𝜂𝑇• (Š) ∇y ℒ 𝑓#(Š) .
ƒ▶ NTK regimeでは初期カーネル 𝑘#(…) に付随するRKHSでの勾配法を近似．
RKHSでの勾配法が帰納的バイアスで早期終了による汎化も期待される．

⼆層ニューラルネット
NTK regimeへの切替は⼆層の場合が本質的で良く研究されている．
}
s , 𝑎 ∈ {−𝛼, 𝛼} ,パラメータ: ΘJ = 𝑏” }
,
Θ
=
𝑎
𝑏
∈
ℝ
5
”
”
”
”IJ
”IJ

𝛼: 初期化スケール,}𝑓# 𝑥 = G𝑎” 初期化時の制約𝑎” 𝜎 𝑏”_𝑥 .

”IJ

𝑜
𝑎” }
”IJ

ℎJ

ℎ5

ℎc
𝑏” }
”IJ

𝑥J

𝑥5

𝑥c

⼊⼒層パラメータについて⾮凸最適化で⼤域収束性の保証は⼀般に困難
適切な設定でのOver-parameterizationで
NTK regimeになることを⽰す．
[Du, Zhai, Poczos, & Singh (2019)]

18

帰納的バイアス
⼆層ニューラルネットでは以下の要因で帰納的バイアスが切り替わる：
層の固定の仕⽅，パラメータの初期化スケール，モデルの出⼒スケール• ⼊⼒層のみ学習• 𝛼 = 1/𝑚: Mean field regime [Chizat & Bach (2018)], [Mei, Montanari, & Nguyen (2018)]
𝑚 → ∞ での帰納的バイアスはワッサースタイン勾配流 [Nitanda & Suzuki 2017]• 𝛼 = 1/ 𝑚: NTK regime [Du, Zhai, Poczos, & Singh (2019)]
𝑚 → ∞ での帰納的バイアスは𝒌𝚯𝟏 に付随するRKHSでの勾配法• 出⼒層のみ学習
ランダム特徴によるNTK regime
帰納的バイアスは𝒌𝚯𝟐 に付随するRKHSでの勾配法• 両層を同時学習 [E, Ma, & Wu (2019)]
両層が定めるNTK regime，帰納的バイアスは𝒌𝚯𝟏 + 𝒌𝚯𝟐 に付随するRKHSでの勾配法
⼗分⼤きな𝑚に対し，𝛼が⼩さいと𝒌𝚯𝟐 が⽀配的，𝛼が⼤きいと𝒌𝚯𝟏 が⽀配的
パラメータの初期化スケールで⽀配的層が切り替わる

収束解析（⼊⼒層の学習）_
⼆層NN: 𝑓# 𝑥 = ∑}”IJ 𝑎” 𝜎 𝑏” 𝑥 , 𝑎” ∼ 𝑈

−

J
J
,
} }

𝐻J£: = 𝔼¤ 𝜎 v 𝑏 ¥ 𝑥H 𝜎 v 𝑏 ¥ 𝑥x 𝑥H_𝑥x. （𝑎” は学習中固定）K
H,xIJ= lim 𝐾# … .
}→£S※ 𝔼¤ は𝑏を初期化する分布による期待値．

[Du, Zhai, Poczos, & Singh (2019)]の改良版

定理 [Wu, Du, & Ward (2019)] 𝑥 5 = 1, 𝑦 = 𝑂 1 , 𝜆J : = 𝜆}HK 𝐻J£ > 0 とする．
ハイパーパラメータを以下のように設定：𝑛§1
𝑚 = Ω d c ,𝜂 = Θ, 𝑇 = 𝑂©
£
𝐻 5
𝜆J 𝛿

𝐻£ 5
1
log
𝜆J
𝜖

▶ 勾配法𝑇-反復で𝜖-誤差解を達成： ℒ Θ o

線形収束性

≤ 𝜖.

.

汎化誤差バウンドも導出可能 [Arora, Du, Hu, & Wang (2019)]：1 − 𝛿以上の確率で，𝔼«,¬ 𝑙 𝑌, 𝑓#- 𝑋≤

2𝑦 _ 𝐻£ \J 𝑦+𝑂𝑛

※ 但し，ハイパーパラメータは[Wu, Du, & Ward (2019)]と異なる．

1
𝑛
log
𝑛
𝜆J 𝛿

,

1
𝑛
𝑇≥Ω
log
𝜂𝜆J
𝛿

.

収束解析（両層の学習）_
⼆層NN: 𝑓# 𝑥 = ∑}”IJ 𝑎” 𝜎 𝑏” 𝑥 , 𝑎” ∼ 𝑈 −𝛼, 𝛼 ,
s# Š
勾配流：
so

= −∇ℒ Θ o .
𝐻£ ≔ 𝛼 5 𝐻J£ + 𝐻5£,
𝐻J£: =（𝛼は固定値とする）

1= lim 5 𝐾# … ,H,xIJ}→£ 𝛼 𝑚S
1
K
= lim 𝐾# … .
H,xIJ
}→£ 𝑚
„

𝔼¤ 𝜎 v 𝑏 ¥ 𝑥H 𝜎 v 𝑏 ¥ 𝑥x 𝑥H_𝑥x

𝐻5£: = 𝔼¤ 𝜎 𝑏 ¥ 𝑥H 𝜎 𝑏 ¥ 𝑥xK

定理 [E, Ma, & Wu(2019)] 𝑥 5 = 1, 𝑦 = 𝑂 1 , 𝜆J : = 𝜆}HK 𝐻J£ > 0, 𝜆5 : = 𝜆}HK 𝐻5£ > 0,
ノード数𝑚を次のように設定：𝑚 = Ω

K¯
K„
log
° ~S ∧~„ ²°▶ 勾配流で⽬的関数は指数的収束：ℒ Θo≤ exp −.

※ 両層の学習により𝑚が𝛼に⾮依存．

𝑚 5𝛼 𝜆J + 𝜆5 𝑡 ℒ Θ ^ .
𝑛𝛼が⼤きいと⼊⼒層， 𝛼が⼩さいと出⼒層の学習が⽀配的となる．

3. 識別問題での⼆層ニューラルネットの
勾配降下法

研究概要
識別問題に対する⼆層ニューラルネットの勾配降下法の収束解析• 仮定
NTによるデータの識別可能性(NTKの正定値性より弱い条件)• 結果
現実的なサイズ𝑚 ≪ 𝑛の2層NNに対し勾配法の⼤域収束性と汎化性を⽰す．
Non over-parameterizationに対する収束保証．
回帰での既存研究では𝑚 ≫ 𝑛であった (e.g., 𝑚 = Ω(𝑛§)).
下記プレプリントの改良結果を紹介．
A. Nitanda & T. Suzuki. Refined Generalization Analysis of Gradient Descent for Over-parameterized Twolayer Neural Networks with Smooth Activations on Classification Problems. arXiv, 2019a.
23

2層NNによるロジスティック回帰• データ: 𝒳 ⊂ ℝs , 𝒴 = {−1,1}, 𝒳×𝒴上の真の分布𝜈,
訓練データ 𝑥H , 𝑦H KHIJ ∼ 𝜈 K : i.i.d. サンプル．
_ 𝑥 , 𝑎 ∈ −1,1 ,• モデル: 𝑓# 𝑥 = ∑}𝑎𝜎𝑏
（⼊⼒層のみ学習）””””IJ• 損失関数: 𝑙 𝑧, 𝑦 = log 1 + exp −𝑦𝑧 .
⼆値識別の⽬標は期待識別誤差 ℙ «,¬ ~» sgn(𝑓 𝑋 ) ≠ 𝑌 の最⼩化．
ロジスティック回帰では以下の近似問題で代⽤．
ロジスティック回帰

ロジスティック損失による経験損失最⼩化

K
1min ℒ Θ : = G 𝑙 𝑦H , 𝑓# 𝑥H
#S
𝑛
HIJ

.
24

回帰問題とNTKの正定値性
⽬的関数の減少の条件：∇y ℒ 𝑓# _𝐾#∇y ℒ 𝑓# > 0• NTKのグラム⾏列の正定値性は関数勾配∇y ℒ(𝑓#)の⽅向に必要．
• ⼆乗損失では∇y ℒ 𝑓# は任意の⽅向を向き得る:
K∇y ℒ 𝑓# = 𝑦H − 𝑓# 𝑥H HIJ.
▶ グラム⾏列の正定値性を課す理由．

𝑓# (𝑋JK )𝑓#¾ (𝑋JK )𝐾#の正定値性で関数はラベルに勾配法で接近（関数とラベルの位置関係に依らない）

𝑌JK
𝑋JK = 𝑥H KHIJ , 𝑌JK = 𝑦H KHIJ

25

ロジスティック回帰とNTK
⽬的関数の減少の条件：∇y ℒ 𝑓# _𝐾#∇y ℒ 𝑓# > 0

ロジスティック回帰の関数勾配:∇y ℒ 𝑓# = −𝑦H

exp −𝑦H 𝑓# 𝑥H
1 + exp −𝑦H 𝑓# 𝑥H▶ ラベルが張る錐上での正定性で⼗分．

𝑓#¾ (𝑋JK )𝑓# (𝑋JK )

𝑌JK

K

.
HIJ

0,1 -値

ロジスティック回帰
1/(1 + exp −𝑓# 𝑋JK )による1[𝑌JK = 1]の回帰．
即ち，ラベルが{−∞, ∞}-値の回帰問題．
▶ 関数とラベルの位置関係が不変
NTKの正定値性は冗⻑
26

NTによる識別可能性
仮定 ∃𝜌 > 0, ∃𝑣: ℝs → 𝑣 ∈ ℝs | 𝑣 5 ≤ 1 s.t. ∀ 𝑥, 𝑦 ∈ supp 𝜈 ⊂ 𝒳×𝒴,𝔼¤ 𝑦𝜕¤ 𝜎 𝑏 _𝑥 _𝑣 𝑏

≥ 𝜌.

• 無限次元(𝑚 = +∞) NTによる識別可能性．
• NTKの正定値性より弱い条件．
• ラベルが張る錐上の正定値を誘導：_
𝑦 𝐻J£𝑦 ≥ 𝜌5 𝑦 55,(𝑦 = 𝛼H 𝑦H KHIJ, 𝛼H ≥ 0).

27

収束解析

[Nitanda & Suzuki (2019a)]定理 [Nitanda & Suzuki (2019a)] supp 𝜈 « ⊂𝑥 5 ≤ 1 , 𝜎 は𝐶 5 -級で 𝜎 v £ , 𝜎 vv £ ≤ 1．

NTの識別可能性を仮定．ハイパーパラメータを以下のいずれかに設定：
Ê 𝜖 \d ,(1) 𝑚 = Ω 𝜖 \J , 𝑇 = Ω 𝜖 \5 , 𝑛 = ΩÊ 𝜖 \c/5 , 𝑇 = Θ
Ê 𝜖 \J , 𝑛 = ΩÊ 𝜖 \5 .
(2) 𝑚 = Θ
この時，⾼確率で𝑇-反復以内𝜖-期待識別誤差を達成： ∃𝑡 ≤ 𝑇,
ℙ «,¬ ∼» 𝑌𝑓# Š 𝑋 ≤ 0 ≤ 𝜖.
関連研究と異なりnon over-parameterizationでの⼤域収束・汎化保証．
Allen-Zhu, Li, & Liang (2019)
Cao & Gu (2019a)

これらはDNNにも対応．

Cao & Gu (2019b)
Nitanda & Suzuki (2019a)28

4. カーネル法・Rich Regimes

RKHSでの確率的勾配降下法（SGD）[Nitanda & Suzuki (2019b)], [Yashima, Nitanda, & Suzuki (2019)]

出⼒層のみの学習はRKHS ℋ• での学習に対応し，多数の研究がある．
𝐿5 -ロジスティック回帰に対するSGD： 𝑔o ∈ ℋ• , 𝑥o , 𝑦o ∼ 𝜌,
𝑔oXJ = 1 − 𝜂o 𝜆 𝑔o − 𝜂o 𝜕{ 𝑙 𝑔o 𝑥o , 𝑦o 𝑘(𝑥o ,⋅).
仮定（強低ノイズ条件）∃𝛿 ∈ 0,1/2 , for 𝑋 a.e. w.r.t. 𝜌𝒳 ，
𝜌 𝑌 = 1 𝑋) − 0.5 > 𝛿.

𝜌 𝑌 = 1 𝑥)
1.0
𝛿
𝛿

0.5

ℛ 𝑔 ≔ ℙ «,¬ ∼Ï 𝑌𝑔 𝑋 ≤ 0 , ℛ∗ = min ℛ 𝑔 .
Ð

定理 [Nitanda & Suzuki (2019b)] 適当な仮定の下，∃𝑇^ , ∀𝑇 ≥ 𝑇^ に対して
1 + 2𝛿
𝔼 ℛ 𝑔¥XJ − ℛ∗ ≤ 2 exp −𝑂(𝜆5 𝑇) log 5
1 − 2𝛿

𝑌 = −1

𝒳

期待識別誤差の線形収束性• 同様の収束性はRandom Featureモデルでも成⽴ [Yashima, Nitanda, & Suzuki (2019)]• 2層NNの両層の学習でも成⽴（ongoing work）

𝑌 = +1

Particle Gradient DescentJ[Nitanda & Suzuki (2017)](^)_
⼆層NN: 𝑓# 𝑥 = } ∑}”IJ 𝜎 𝑏” 𝑥 (mean field regime, MFR), 初期化：𝑏”∼ 𝜇^ .

}
1(𝑚 → ∞)(^)_
𝑓#(…) 𝑥 = G
𝜎 𝑏” 𝑥→𝑓Ò… 𝑥 = 𝔼¤(…) ∼Ò… 𝜎 𝑏 (^)¥ 𝑥 .
𝑚
”IJ

𝜇^
(J)

𝑏”

(^)

𝑏”

パラメータΘ ^=^𝑏”

勾配法によりΘ J =

𝜇J

勾配法

}

(^)

= 𝑏” − 𝜂𝜕¤Ó ℒ Θ ^は分布𝜇^ のサンプルの集まり．

(J)

𝑏”

”IJ
}
J
𝑏”
に更新され，背後にある分布も𝜇J に更新される．
”IJ▶ (確率的)勾配法は暗に確率分布を最適化: min ℒ(𝜇)．その更新即は？
Ò▶ (Stochastic) Particle Gradient Descent輸送写像による確率測度最適化ℝs 上の輸送写像𝜙 (o) : ℝs → ℝs は分布を変形する．

[Nitanda & Suzuki (2017)]

𝜙 (o) : 輸送写像

（即ち，変数変換で確率変数を𝜙 (o) と合成し更新）
𝜇 (o) :確率分布𝑏~𝜇 (o)𝜇 (oXJ) : 更新された分布(o)
𝜙 (o) 𝑏 ~𝜇 oXJ = 𝜙# 𝜇 (o)▶ 確率測度の最適化を輸送写像の最適化 ℒ 𝜙 = ℒ(𝜙#𝜇 (^) )に帰着．
▶ 𝐿s5 (𝜇 ^ )におけるフレシェ微分（関数勾配）∇Ö ℒ(𝜙 o )を⽤いた関数勾配法：
𝜙 (oXJ) = 𝜙 (o) − 𝜂𝑣o ∘ 𝜙 o ,𝜇 (oXJ) = 𝑖𝑑 − 𝜂𝑣o #𝜇 (o) .
(oXJ)

これはパラメータの勾配法に対応：𝑏”(∇Ö ℒ 𝜙 o

= ∃𝑣o ∘ 𝜙 o )（付随する確率測度の更新即：SPGD）
o∼ (𝑖𝑑 − 𝜂𝑣o )(𝑏” ). （𝑚 = ∞では厳密に⼀致）▶ パラメータの勾配法は輸送写像の最適化による確率測度の最適化．
SPGD法に対し輸送写像空間での局所解への収束𝑂(𝜖 \5 )も保証．[Nitanda & Suzuki (2017)]

ワッサースタイン勾配流[Nitanda & Suzuki (2017)]

勾配法は無限⼩の学習率の下では勾配流のダイナミクスに従う．
SPGD法のダイナミクスは？
▶ワッサースタイン勾配流（W勾配流）に従う： [Nitanda & Suzuki (2017)]d𝜇o = −div −𝑣o 𝜇o ,
d𝑡
𝜇^

W勾配流

d
ℒ 𝜇o = − 𝑣o 5P„ ÒŠ .
d𝑡
SPGD: 関数勾配法によるW勾配流の離散化• W勾配流の⼤域収束性は[Chizat & Bach (2018)]が証明．（即ち無限次元2-NNの勾配流）• [Nitanda & Suzuki (2017)] は収束率付きの局所収束性をSPGD（即ち離散ステップの確率的勾配降下法）に対して証明．更に改良版SPGDで有限パーティクルでの収束性も保証．

その他，ノイズ付きSGDは[Mei, Montanari, & Nguyen (2018)]が解析．

Active Regime• NTK regimeの要因：微⼩なパラメータ変化で関数を⼗分に動かせる(lazy training)．
• 出⼒層固定の2層NNの場合：𝛼 = 1/𝑚を境界に切り替わる．（MFRはNTK regimeでない）• モデル𝛼𝑓 (𝛼 > 0)：𝛼が⼤きいとkernel regime．[Chizat & Bach (2019)]
𝛼が⼩さい場合active (adaptive)なregime．
定理（Homogeneous linear modelの帰納バイアス）𝑤X, 𝑤\ ∈ ℝs , 𝛼 > 0, 𝐿 ∈ ℕ,
[Woodworth+ (2019)]𝑓Ý‘ ,ÝR 𝑥 = 𝛼 P 𝑤XP − 𝑤\P _𝑥.
𝑤X(𝑡), 𝑤\(𝑡)を⼆乗損失に対する𝑤X, 𝑤\の勾配流とし 𝛽ß 𝑡 = 𝛼 P 𝑤XP(𝑡) − 𝑤\P (𝑡) .
𝑛 ≪ 𝑑の時， 𝛽ß ∞ _𝑥H = 𝑦H , 𝑖 ∈ 1, … , 𝑛 , を満たし以下の特徴付けが成⽴：
lim 𝛽ß (∞) = 𝛽P∗S ,lim 𝛽ß (∞) = 𝛽P∗„ ，
ß→^

ß→£

ここで𝛽P∗S , 𝛽P∗„ は𝛽 _𝑥H = 𝑦H , 𝑖 ∈ 1, … , 𝑛 , の最⼩𝐿J , 𝐿5 -ノルム解．
▶𝛼 が⼩さい時，𝐿J -正則化が帰納的バイアス（active regime）
カーネル法はスパース解がある時，その性質を活かせない．

まとめ• ニューラルネットに対する勾配法の近年の研究を紹介．
• ⼆層の場合の理論が現状本質的．
• 種々の要因で帰納的バイアスの切り替えが起こる事を紹介．
NTK regime, Mean field regime, Active regime.
特にNTK regimeの理論を解説．
より最近の研究の流れ• NTK regimeの更なる研究（より詳細な解析，NTK regimeの妥当性）．
• NTK以外のregimeの研究．
Mean field regimeとHomogeneous linear modelはその成功例．
NTKより⾼次の帰納的バイアスの研究もされつつある（モデルの⼆次近似，ResNet）．

参考⽂献
1章
• P. Auer, M. Herbster, & MK. Warmuth. Exponentially many local minima for single neurons. NIPS, 1996.
• D. Soudry & Y. Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv, 2016.
• D. Soudry & E. Hoffer. Exponentially vanishing sub-optimal local minima in multilayer neural networks. arXiv, 2017.
• M. Soltanolkotabi, A. Javanmard, & J. Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.
IEEE Transactions on Information Theory, 2018.
• I. Safran & O. Shamir. Spurious local minima are common in two-layer relu neural networks. ICML, 2018.
• S. Du & J. Lee. On the power of over-parametrization in neural networks with quadratic activation. ICML, 2018.
• L. Venturi, AS. Bandeira, & J. Bruna. Spurious valleys in two-layer neural network optimization landscapes. arXiv, 2018
• S. Liang, R. Sun, J. Lee, & R. Srikant. Adding One Neuron Can Eliminate All Bad Local Minima. NeurIPS, 2018.
• Anonymous. Bounds on Over-Parameterization for Guaranteed Existence of Descent Paths in Shallow ReLU Networks. ICLR submission, 2019.
• Q. Nguyen, MC. Mukkamala, & M. Hein. On the loss landscape of a class of deep neural networks with no bad local valleys. ICLR, 2019.
• L. Luo, Y. Xiong, Y. Liu, & X. Sun. Adaptive Gradient Methods with Dynamic Bound of Learning Rate. ICLR, 2019.
2-3章• A. Jacot, F. Gabriel, & C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS, 2018.
• S. Du, X. Zhai, B. Poczos, & A. Singh. Gradient descent provably optimizes over-parameterized neural networks. ICLR, 2019.
• Z. Allen-Zhu, Y. Li, & Z. Song. A Convergence Theory for Deep Learning via Over-Parameterization. ICML, 2019.
• S. Du, J. Lee, H. Li, L. Wang, X. Zhai. Gradient Descent Finds Global Minima of Deep Neural Networks. ICML, 2019.
• D. Zou & Q. Gu. An Improved Analysis of Training Over-parameterized Deep Neural Networks. NeurIPS, 2019.
36

参考⽂献
• X. Wu, S. Du, & R. Ward. Global convergence of adaptive gradient methods for an over-parameterized neural network. arXiv, 2019.
• S. Arora, S. S. Du, W. Hu, & R. Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.
ICML, 2019.
• W. E, C. Ma, & L. Wu. A comparative analysis of the optimization and generalization property of two-layer neural network and random featuremodels under gradient descent dynamics. arXiv, 2019.
• A. Nitanda & T. Suzuki. Refined generalization analysis of gradient descent for over-parameterized two-layer neural networks with smooth
activations on classification problems. arXiv, 2019a.
• Z. Allen-Zhu, Y. Li, & Y. Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. NeurIPS, 2019.
• Y. Cao & Q. Gu. A generalization theory of gradient descent for learning over-parameterized deep relu networks. arXiv, 2019a.
• Y. Cao & Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. NeurIPS, 2019b.
4章• A. Nitanda & T. Suzuki. Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors. AISTATS, 2019b.
• S. Yashima, A. Nitanda, & T. Suzuki. Exponential Convergence Rates of Classification Errors on Learning with SGD and Random Features. arXiv,
2019.
• A. Nitanda & T. Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv, 2017.
• L. Chizat & F. Bach. On the global convergence of gradient descent for over-parameterize models using optimal transport. NeurIPS, 2018.
• S. Mei, A. Montanari, & P-M. Nguyen. A mean field view of the landscape of two-layer neural networks. PNAS. 2018.
• L. Chizat & F. Bach. On Lazy Training in Differentiable Programming. NeurIPS, 2019.
• B. Woodworth, S. Gunasekar, P. Savarese, E. Moroshko, I. Golan, J. Lee, D. Soudry, & N. Srebro. Kernel and Rich Regimes in Overparametrized
Models. arXiv, 2019.
37