1

無限次元勾配ランジュバン動力学による深層学習の最適化理論と汎化誤差解析
鈴木大慈
東京大学/ 理研AIP(深層学習理論チーム)

2020年9月4日@九州大学統計科学セミナー

2

導入：問題意識Deep Learning Model
Image

3

Alex-net [Krizhevsky, Sutskever + Hinton, 2012]-Cat (y=1)-Dog(y=2)• Stacking layers yields a complicated function.
• Universal approximator.

Details of each layer

Affine transform＋
activation function

Activation function• ReLU (Rectified Linear Unit)

万能近似能力(十分広い横幅のNNであらゆる関数が近似できる)• Sigmoid function4

カーネル法5• 万能近似能力のある手法．
• 2000年～2010年ほどで流行．
• ILSVRCでも使われていた．
第1層目を固定した横幅無限の2層ニューラルネットワーク(線形推定量と呼ばれるクラス)
似た手法• スプライン法• 局所多項式回帰• シリーズ推定量• 第一層目固定• 無限個の素子

x

y
…

…

学習

固定

カーネル法

再生核ヒルベルト空間の理論
非線形写像

問題意識
• [理論] 万能近似能力という意味では浅層で十分．
• [実際] 実際は多層を使うことが多い．
→ この差はどう埋める？
カーネル法
浅層

→ 推定能力を比べる．

多層ニューラルネット
深層学習

6

なぜ深層学習が良いのか？

7• 真の関数𝑓𝑓 ∘ の形状によって深層が有利になる

縮小ランク回帰
特徴空間の次元が低い状況は深層学習が得意

区分滑らかな関数[Imaizumi&Fukumizu, 2019]

不連続な関数の推定は深層学習が得意

Besov空間[Suzuki, 2019]

滑らかさが非一様な関数の推定は深層学習が得意

低次元データ[Schmidt-Hieber, 2019] [Nakada&Imaizumi,
2019][Chen et al., 2019][Suzuki&Nitanda, 2019]

データが低次元部分空間上に分布していたら深層学習が有利

カーネル

推定精度

深層

例 (1): 低次元データ構造[Suzuki&Nitanda, 2019]

関数値が変化する方向関数値
ほぼ一定

𝑠𝑠1 , 𝑠𝑠2 , 𝑠𝑠3 : smoothness

推定精度

深層学習

(non-smooth) 𝑠𝑠1 , 𝑠𝑠2 ≪ 𝑠𝑠3 (smooth)

浅い学習（次元の呪い）8数学的に一般化

9「滑らかさの非一様性」「不連続性」「データの低次元性」
凸結合を取って崩れる性質をもった関数の学習は深層学習が強い→ 様々な性質を“凸性”で統一的に説明
例：ジャンプが３か所の区分定数関数

0.5x

0.5x

深層:1/𝑛𝑛, カーネル: 1/ 𝑛𝑛=+
ジャンプ3か所

ジャンプ3か所

ジャンプ6か所→ さらには「スパース推定」という観点からも説明できる．
[Satoshi Hayakawa and Taiji Suzuki: On the minimax optimality and superiority of deep neural network
learning over sparse parameter spaces. arXiv:1905.09195.]線形推定量の最悪誤差
線形推定量：
例: カーネルリッジ回帰10と書ける任意の推定量(“浅い”学習法とみなす)

さらに条件を仮定すれば「Q-hull」まで拡張できる．
[Hayakawa&Suzuki: 2019][Donoho & Johnstone, 1994]

数学的一般化
区分滑らかな関数

11

Besov空間

縮小ランク回帰
変動指数
Besov空間

非凸性
スパース性

低次元データ12• これら統計理論は「最適化」を考慮していない．
• 「非凸性」から逃れようとすると深層学習の本
当の良さが分からなくなる．
凸性

非凸性

統計理論
最適化理論

本研究の目標深層学習における非凸性を保ちつつ「最適化」と「統計理論」
を結びつける．

既存研究との関係

大域的最適性を保証する理論的枠組み

13

理論的枠組み横幅 (次元)汎化性能

多層Neural Tangent Kernel

無限へ漸近

△

平均場解析

本質的にカーネル法/Early stopping必要

無限へ漸近

△

△

(既存の)
有限次元Langevin動力学

有限 (低次元)

汎化ギャップは保証あり/大きいモデルはNG

△

本研究

有限/無限
汎化ギャップ/余剰誤
統一的な枠組み 差ともに保証〇• 深層NNモデルの非凸性を失わず最適化したい．
• モデルサイズをサンプルサイズに依存させたくない．

 無限次元Langevin動力学
本研究
 汎化性能保証[Muzellec, Sato, Massias & Suzuki: Dimension-free convergence rates for gradient Langevindynamics in RKHS. arXiv:2003.00306][Suzuki: Generalization bound of globally optimal non-convex neural network training:
Transportation map estimation by infinite dimensional Langevin dynamics. arXiv:2007.05824]

深層学習の“学習”14

深層ニューラルネットワークをデー
タにフィットさせるとは？

𝑊𝑊: パラメータ

𝑖𝑖番目のデータで正解していれば小さく，間違っていれば大きく損失関数：データへの当てはまり度合い
損失関数最小化(Wは数十億次元)
通常，(確率的)勾配降下法で最適化

最適値

問題点

15

目的関数が非凸関数
凸関数

深層学習の損失関数?

局所最適解＝大域的最適解

局所最適解

大域的最適解

局所最適解や鞍点にはまる可能性あり“狭い”ネットワークの学習はNP-完全:••

Judd (1988), Neural Network Design and the Complexity of Learning.
Blum&Rivest (1992), Training a 3-node neural network is NP-complete.

勾配法

固定

ℓ𝑖𝑖 : 損失関数

16

最適化

• 回帰: 二乗損失 (ℓ𝑖𝑖 (𝑓𝑓𝑊𝑊 (𝑥𝑥𝑖𝑖 )) = 𝑦𝑦𝑖𝑖 − 𝑓𝑓𝑤𝑤 𝑥𝑥𝑖𝑖 )• 判別: 凸代理損失 (e.g., ロジスティック, 平滑化ヒンジ, ...)

勾配降下法:
確率的勾配降下法:2

オーバーパラメトライゼーション

横幅が広いと局所最適解が大域的最適解になる．
狭い横幅

…
0
広い横幅

自由度が上がるため，初期値から最適解(完全フィット)へ到達しやすい．

• 二種類の解析手法

0 Neural Tangent Kernel
 Mean-field analysis (平均場解析)

17

二つのスケーリング
固定

18

最適化

• Neural Tangent Kernelのregime (lazy learning )[Jacot+ 2018][Du+ 2019][Arora+ 2019] 𝑎𝑎𝑗𝑗 = O(1/ 𝑀𝑀)• 平均場解析のregime[Nitanda & Suzuki (2017), Chizat & Bach 𝑎𝑎𝑗𝑗 = Ο(1/𝑀𝑀)(2018), Mei, Montanari, & Nguyen (2018)]※NTKの1/ 𝑀𝑀自体はそこまで本質ではない，1/𝑀𝑀より大きいことが重要．

初期化のスケーリングによって，初期値と比
べて学習によって動く大きさの割合が変わる．
→ 学習のダイナミクス，汎化性能に影響（解析の難しさも違う）

NTK

19

初期値のスケールが大きいので，初期値周りの線形近似でデータにフィットできてしまう．

初期値
モデルの集合Optimization in NTK regime20

以下のように初期化する:• 𝑎𝑎𝑗𝑗 ∼ (±1)

1(+, − is generated evenly)𝑀𝑀• 𝑤𝑤𝑗𝑗 ∼ 𝑁𝑁(0, 𝐼𝐼)

Theorem [Arora et al., 2019]

𝑀𝑀 = Ω(𝑛𝑛2 log(𝑛𝑛)/𝜆𝜆min )とすれば, 勾配法によって大域的最適解へ線形収束し，その汎化誤差は 𝒚𝒚⊤ 𝐾𝐾𝑊𝑊 (0) −1 𝒚𝒚⁄𝑛𝑛 で抑えられる．

See also[Du et al., 2018; Allen-Zhu, Li & Song, 2018; Li & Liang, 2018]• 訓練誤差0の解に線形収束する.
• 汎化誤差も一応抑えられている.

• 横幅𝑴𝑴はサンプルサイズ𝒏𝒏に応じて無限大へ飛ぶ必要がある．
• カーネル法の枠組みを抜け出せていない．
• データに完全にフィットさせてしまうので過学習の可能性あり.

Beyond kernel

21

問題点：NTKは解析がしやすいが，結局カーネル法の範疇なので深層学習の“良さ”が現れない．
 NTKをはみ出す理論の試みがいくつかなされている．
（今後発展が予想される）• Allen-Zhu&Li (2019,2020)

Allen-Zhu&Li: What Can ResNet Learn Efficiently, Going Beyond Kernels? NIPS2019.
Allen-Zhu&Li: Backward Feature Correction: How Deep Learning Performs Deep
Learning. arXiv:2001.04413.

(ResNet型ネットワークでカーネルを優越する状況)• Li, Ma&Zhang (2019)

Li, Ma&Zhang: Learning Over-Parametrized Two-Layer ReLU Neural Networks
beyond NTK. arXiv:2007.04596.

(テンソル分解の理論で深層学習がカーネルを優越することを示した)• Bai&Lee (2020)

Bai&Lee: Beyond Linearization: On Quadratic and Higher-Order Approximation ofWide Neural Networks. ICLR2020.

(二次のテイラー展開まで使う)

平均場解析

22• ニューラルネットワークの最適化をパラメータの分布最適化としてみなす．
𝑀𝑀 → ∞(𝑎𝑎, 𝑤𝑤)に関する確率密度𝜌𝜌による平均とみなせる:

𝑓𝑓の最適化 ⇔ 𝜌𝜌の最適化

連続方程式

Wasserstein勾配流[Atsushi Nitanda and Taiji Suzuki: Stochastic Particle Gradient Descent for Infinite Ensembles. arXiv:1712.05438.](各粒子は勾配降下
方向へ移動)

粒子勾配降下法
1つの粒子

23• 各ニューロンのパラメータを一つの粒子とみなす．
• 各粒子が誤差を減らす方向に動くことで分布が最適化される．

(分布)

データへの当てはまりを良くする方向に変化(各粒子の移動方向：勾配方向)

M個の粒子が移動[Nitanda&Suzuki, 2017]

𝑀𝑀 → ∞の極限で，最適解への収束が成り立つ場合がある．
[Nitanda&Suzuki, 2017][Chizat&Bach, 2018][Chizat, 2019]

ノイズありのダイナミクス:
McKean-Vlasov過程
やはり横幅𝑀𝑀→∞である必要がある[Mei, Montanari&Nguyen, 2018]

McKean-Vlasov過程• ノイズありダイナミクス

参考24(distribution)

Model:(movement ofeach particle)

ダイナミクス (McKean-Vlasov過程):

Fokker-Planck方程式:••

𝑋𝑋𝑡𝑡 の値だけでなく分布にも依存

収束解析: Mei, Montanari&Nguyen, 2018; Rotskoff &Vanden-Eijnden, 2018.
最適制御理論: Weinan et al., 2019; Tzen&Raginsky, 2020; Lu et al., 2020.

離散化

参考

時空間離散化:(i.i.d., standard Gaussian)

Pros: 定常分布への収束が保証されている.
Cons:

Empirical distribution[Mei, Montanari&Nguyen, 2018][Tzen&Raginsky, 2020]• “横幅”𝑴𝑴は𝐞𝐞𝐞𝐞𝐞𝐞(𝑻𝑻)である必要がある． 時刻T，収束を保証するには
横幅は十分多くする必要あり(有限粒子数では収束保証されず)．
• ガウス雑音 𝝃𝝃𝒕𝒕 (𝒅𝒅𝑩𝑩𝒕𝒕 ) は各粒子ごとに独立同一に添加.
 粒子間の相関・滑らかさは考慮されていない．実際のDNNでは位置が近い粒子には値が似たノイズ．
• 𝜌𝜌𝑡𝑡 は絶対連続 (有限横幅のNNは対象外)

25

26

Langevin動力学

Sharp minima vs flat minima

27

SGDは「フラットな局所最適解」に落ちやすい→良い汎化性能を示すという説

Keskar, Mudigere, Nocedal, Smelyanskiy, Tang (2017):
On large-batch training for deep learning: generalization gap and sharp minima.

≅正規分布→ ランダムウォークはフラットな領域にとどまりやすい•「フラット」という概念は座標系の取り方によるから意味がないという批判．
(Dinh et al., 2017)•PAC-Bayesによる解析 (Dziugaite, Roy,2017)

ノイズによる平滑化効果

28smoothing[Kleinberg, Li, and Yuan, ICML2018]

確率的勾配を用いる ⇒ 解にノイズを乗せている⇒ 目的関数の平滑化

ノイズを加えて平滑化した目的関数

を最適化．

GLD/SGLD

29• Stochastic Gradient Langevin Dynamics (SGLD)(非凸)𝛽𝛽: 逆温度(勾配Langevin動力学)

定常分布：
離散化

[Gelfand and Mitter (1991); Borkar andMitter (1999); Welling and Teh (2011)]

GLD:(Euler-Maruyama近似)

SGLD:
確率的勾配

30

Gaussian noise
Gradient descent収束定理 (有限次元)• 𝑓𝑓𝑖𝑖 : 有界，Lipschitz連続，滑らかな勾配• 散逸条件:(+ その他細かい条件)

Thm [Raginsky, Rakhlin and Telgarsky, COLT2017]

次元𝑑𝑑に指数的に依存!
• 𝜆𝜆∗ はスペクトルギャップと言われる量．
→ 次元dや逆温度パラメータβに対して指数関数的に依存．
• 逆温度パラメータが十分大きくて，更新を十分な回数回せば最適解付近に近づける．
• Xu et al. (NeurIPS2018) は収束レートを改善しているが，証明にいくつかの間違いあり．

31

32

散逸条件

33

Infinite dim non-convex optimization
by Langevin dynamics
Joint work with Boris Muzellec (CREST, ENSAE,), Kanji Sato (U-Tokyo),
Mathurin Massias (INRIA).

[Boris Muzellec, Kanji Sato, Mathurin Massias, Taiji Suzuki: Dimension-freeconvergence rates for gradient Langevin dynamics in RKHS. arXiv:2003.00306.]

無限次元への拡張

34[Muzellec, Sato, Massias, Suzuki, arXiv:2003.00306][Suzuki, arXiv:2007.05824]

正則化

Ex.
• ℋ: 𝐿𝐿2 (𝜌𝜌)• ℋ𝐾𝐾 : 再生核ヒルベルト空間 (e.g. Sobolev空間)

最適解

暗黙の仮定: 大域的最適解はℋ𝐾𝐾 で十分に近似できる.

E.g., Bayesian optimization on infinite dimensional space[Zimmermann and Toussaint. Bayesian functional optimization. AAAI, 2018][Vellanki, Rana, Gupta, de Celis Leal, Sutti, Height, and Venkatesh: Bayesian functional optimisation
with shape prior. AAAI, 2019]

動機: NNの学習35• 2層ニューラルネットワーク

Idea: 分布の学習 → 輸送写像の学習“Lift”

以前の表記

36• 𝜌𝜌0 が有限サポートの離散測度なら有限横幅のニューラルネットワー
クが扱える．しかも，横幅はサンプルサイズによらない．
 NTKや平均場解析と大きく異なる．
 有限横幅/無限横幅を統一的に扱える．

利点• 初期分布𝜌𝜌0 が離散有限なら有限横幅のニューラルネットワークになっている．
 平均場やNTKと大きく異なる．
• 初期分布𝜌𝜌0 が連続なら無限横幅も扱える．
→ 有限横幅/無限横幅を統一的に扱える.
最適化の方策:

平滑化

1.
2.

雑音は“関数”𝑊𝑊に足される．
正則化により滑らかになる．

• 平滑化と合わせて粒子間の相関を表現できる.

37

ResNet38

Residual block

ℎ𝑗𝑗

𝐹𝐹𝑗𝑗

+

Residual block
Training deep net can also be formulated as transportation map optimization.

2層NNの学習: 直接表現

NTKと違い，𝑎𝑎𝑗𝑗 はデータサイズにも横幅にも依存させずスケー
ルを固定できる.
(TNKは𝑎𝑎𝑗𝑗 = 1/ 𝑀𝑀とする)

39

Transportation map learning

40• Wasserstein metric

𝑌𝑌
Monge version:

𝜄𝜄𝑌𝑌

𝜋𝜋

𝜄𝜄𝑋𝑋

𝑋𝑋

Other examples

41• Bayesian optimization on infinite dimensional space[Zimmermann and Toussaint. Bayesian functional optimization. AAAI, 2018][Vellanki, Rana, Gupta, de Celis Leal, Sutti, Height, and Venkatesh: Bayesian functional optimisation
with shape prior. AAAI, 2019]• Tensor decomposition on RKHS

[M. Signoretto, L. De Lathauwer, and J. A. Suykens. Learning tensors in reproducing kernel Hilbert spaces
with multilinear spectral penalties. arXiv preprint arXiv:1310.4977, 2013][T. Suzuki, H. Kanagawa, H. Kobayashi, N. Shimizu, and Y. Tagami. Minimax optimal alternating
minimization for kernel nonparametric tensor learning. In Advances in Neural Information Processing
Systems 29, pages 3783–3791. 2016]• Robust classification[H. Masnadi-Shirazi and N. Vasconcelos. On the design of loss functions for classification: theory,robustness to outliers, and savageboost. In Advances in Neural Information Processing Systems 21, pages
1049–1056. 2009.]

無限次元ランジュバン動力学

42: RKHS with kernel 𝐾𝐾.

ノルム: For
Cylindrical Brownian motion:
時間離散化:(準陰的Eulerスキーム), we letwhere.

Galerkin近似 & 確率的勾配• スペクトラルGalerkin近似:

無限次元ダイナミクスは実際は計算できない.
→ 𝑁𝑁-次元空間で近似.

• 確率的勾配の利用:

43

定常分布

44

(Hilbert空間上のガウス過程)と解釈しても良い．

（無限次元）勾配ランジュバン動力学の定常分布はガウス過程事前分布を用いたベイズ事後分布に対応する．
→ 過学習を防ぎ汎化する [Suzuki, arXiv:2007.05824]

無限次元の設定

45

ヒルベルト空間

RKHS構造仮定 (固有値の減少)(あまり本質的ではない．𝜇𝜇𝑘𝑘 ∼ 𝑘𝑘 −𝑝𝑝 (𝑝𝑝 > 1) としても良い．)

Related work
• Finite dimensional Langevin dynamics:

 Convergence in low (convex case): Dalalyan and Tsybakov, 2012;
Dalalyan, 2016; Durmus and Moulines, 2015, ..
 Non-convex Optimization: Raginsky et al., 2017; Xu et al., 2018;
Erdogdu, Mackey and Shamir, 2018, .....

• Infinite dimensional Langevin dynamics:
 Continuous time:• Existence & Uniqueness of invariant measure: Da Prato and Zabczyk,1992;
Maslowski, 1989; Sowers, 1992.
• Geometric ergodicity: Jacquot and Royer, 1995; Shardlow, 1999; Hairer, 2002,
Its explicit rate: Goldys and Maslowski, 2006.

 Discrete time:• Weak approximation rate of discretized scheme: Hausenblas, 2003;
Debussche, 2011; Bréhier, 2014; Bréhier and Kopec 2016.

Other topics (MCMC in Hilbert space):• preconditioned Crank–Nicolson (pCN): Hairer et al., 2014; Eberle, 2014;
Vollmer, 2015; Rudolf and Sprungk, 2018.
• Metropolis-Adjusted Langevin Algorithm (MALA): Durmus and Moulines,
2015; Beskos et al., 2017.

46

Assumption (1)47• It either holds:(強):強凸(弱)散逸条件:

Assumption (2)• Smoothness:• Strong smoothness condition:(これが無い場合はレートが遅くなる)(This is not standard, but, is satisfied in the previous examples)• Third order smoothness:48

誤差の解析
𝜋𝜋∞ :定常分布

Thm (informal)[Muzellec, Sato, Massias, Suzuki, arXiv:2003.00306 (2020)]

上記の条件のもと，次が成り立つ：(geometric ergodicity + time discretization)
ただし 𝜅𝜅 > 0 は任意の正の実数, 𝑐𝑐𝛽𝛽 =逸条件).
Remark:𝛽𝛽 (有界な勾配), 𝑐𝑐𝛽𝛽 = 1 (強散for

証明は以下の論文のテクニックを援用: Brehier 2014; Brehier&Kopec 2016;
Mattingly et al., 2002; Goldys&Maslowski, 2006.

49

誤差の解析 (2)50𝜋𝜋∞ : 定常分布
Thm (informal)[Muzellec, Sato, Massias, Suzuki, arXiv:2003.00306 (2020)]

上記の条件のもと，次が成り立つ：(geometric ergodicity+ time discretization)(bias of invariant measure)
ただし 𝜅𝜅 > 0 は任意の正の実数, 𝑐𝑐𝛽𝛽 =
逸条件).

𝛽𝛽 (有界な勾配), 𝑐𝑐𝛽𝛽 = 1 (強散Λ∗𝜂𝜂 : スペクトルギャップ，𝛽𝛽に対して指数的依存がある．

証明は以下の論文のテクニックを援用: Brehier 2014; Brehier&Kopec 2016;
Mattingly et al., 2002; Goldys&Maslowski, 2006.

• 深層学習の最適化への応用と汎化誤差解析：Suzuki, arXiv:2007.05824.

ノイズのコントロール

51• 大域的最適解を得るためには𝛽𝛽 → ∞が必要．
• スペクトルギャップは𝛽𝛽に指数的に依存．
• 大域的最適解まわりで局所的に凸になっていて，離れた場所より目的関数値が真に小さければ途中で勾配法に切り替えても良い．
• 例えば2層NNでは訓練誤差の形状が局所的に強凸になることがある [Li and Yuan, 2017][Chizat, 2019](各ニューロンが適度にばらけている場合はそうなる)

勾配法

誤差の分解52

弱収束を示す:ただし，𝜙𝜙は滑らかな関数.
• Raginsky et al. (2017),

Bréhier (2014), Bréhier and Kopec (2016):

連続時間𝑋𝑋(𝑡𝑡)遠い• Xu et al. (2018):

𝑋𝑋𝑛𝑛

離散時間

定常分布

𝑋𝑋 𝜋𝜋∞

近い𝑋𝑋𝜇𝜇𝜂𝜂

𝑥𝑥 ∗

レートが速い, 一方でより強い条件が必要(Strong smoothness)

第一項のバウンド

参考

補題 (離散時間ダイナミクスのGeometric ergodicity)

ある定常分布𝜇𝜇𝜂𝜂 がだた一つ存在して (極限分布),
geometric ergodicity (定常分布への線形収束) が成り立つ:
ただし，“スペクトルギャップ” Λ∗𝜂𝜂 は以下のように与えられる,(i) (Strict dissipative)(ii) (Bounded gradient)for• 有限次元の場合と違い，強平滑条件がないとおそらく成り立たない.
• Coupling argument: Lyapunov条件, majorization条件より(Mattingly et al. (2002)とGoldys&Maslowski (2006)のテクニックを合わせる)53

Geometric ergodicity

参考• Coupling argument

𝑋𝑋0

𝑋𝑋0′
𝑋𝑋𝑡𝑡

Prob(“couple” until time 𝑡𝑡)≥ 1 − 𝑒𝑒 −𝑐𝑐𝑐𝑐

𝑋𝑋𝑡𝑡′
𝑋𝑋𝑇𝑇

𝑋𝑋𝑇𝑇′
同じ分布に従う54Second term bound

参考𝑋𝑋𝜇𝜇𝜂𝜂 : the invariant measure of discrete time dynamics
𝑋𝑋 𝜋𝜋 : the invariant measure of continuous time dynamics(existence and uniqueness are well known)

Lemma (Discrepancy between invariant measures)

For any 0 < 𝜅𝜅 < 1/2, there exists a constant 𝐶𝐶 such that•• 𝑐𝑐𝛽𝛽 =𝛽𝛽 for bounded gradient condition, and 𝛽𝛽 = 1 otherwise• Malliavin calculus• As the step-size goes to 0, the discrete time dynamics
approaches the continuous one.
• 𝛽𝛽 affects the bound through the spectral gap Λ∗0 .

55

既存研究との違い

参考• 離散時間ダイナミクスの幾何的エルゴード性を示しているため，より速い弱収束.
Brehier 2014:※ Brehierは𝛽𝛽を考えていない．

Ours:

これは以下の追加条件による:強平滑条件(強い条件だが，機械学習応用では自然ではある)56

第二項のバウンド

参考𝑋𝑋𝜇𝜇𝜂𝜂 : 離散時間ダイナミクスの定常分布
𝑋𝑋 𝜋𝜋 : 連続時間ダイナミクスの定常分布 (存在と一意性は保証されている)

補題 (連続・離散時間ダイナミクスの定常分布の違い)

任意の0 < 𝜅𝜅 < 1/2に対し，ある定数𝐶𝐶が存在して，•• 𝑐𝑐𝛽𝛽 =𝛽𝛽 for bounded gradient condition, and 𝛽𝛽 = 1 otherwise• Malliavin解析• ステップサイズ𝜂𝜂を0に近づけると，離散時間ダイナミク
スが連続時間ダイナミクスに近づく.
• 𝛽𝛽はΛ∗0 に影響している.

57

第三項のバウンド

参考58

Lemma (最適解とベイズ推定量の差分)• ノンパラメトリックベイズの技法と似た技法を使いながら示
す．
• “Gaussian correlation inequality” を用いて𝑥𝑥のまわりの𝜋𝜋の�
大きさを評価する.

Galerkin approximation & SGLD

59

参考

• Assumption: Smoothness of L.

Thm
Under some smoothness assumption on 𝐿𝐿, we have(geometric ergodicity+ time discretization)(bias of invariant measure)
Galerkin approx.

Mini-batch sizewith high probability, where 𝜅𝜅 > 0 is an arbitrary small constant.

(c.f., Brehier 2014; Goldys&Maslowski, 2006)

有限次元バージョンとの関係

•

60

参考

large 𝑝𝑝

(我々の状況)(optimal)•𝑘𝑘(予想) see [Andersson,Kruse&Larsson, 2016] for finite time horizon.
𝒑𝒑が大きくなるほど関数クラスは“単純”になる.

有限次元の解析は𝑝𝑝 → ∞に対応 (定数を無視すれば):[Xu et al. (2018)]

𝑘𝑘Application: gradient noise convolution61

参考• Non-convex objectiveSmoothing the objective by noise convlution
Noise is determined by SGD.
Gives good generalization error
smoothing(Figure is from Kleinberg, Li, and Yuan, ICML2018)

Our proposal

Performancecomparison[Haruki, Suzuki, Hamakawa, Toda, Sakai, Ozawa, Kimura: Gradient Noise Convolution (GNC): Smoothing
Loss Function for Distributed Large-Batch SGD. arXiv:1906.10822]

62

汎化誤差解析
[Suzuki: Generalization bound of globally optimal non-convex neural network training:
Transportation map estimation by infinite dimensional Langevin dynamics.
arXiv:2007.05824]

問題設定

63
E.g.,
 二乗損失 ロジスティック損失

𝑊𝑊について非凸

汎化誤差:(汎化ギャップ)

残余誤差:
Eg. 二層ニューラルネットワークモデル:

仮定

64

• 損失関数は𝑊𝑊について“十分に滑らか”.
• 損失関数は有界:
学習の方法 (無限次元GLD):

時間の離散化

連続時間ダイナミクスの定常Gibbs分布:(擬-)Bayes事後分布

汎化誤差バウンド• PAC-Bayesによる汎化誤差バウンド
Thm (汎化誤差バウンド)

For any 𝜅𝜅 > 0,with probability 1 − 𝛿𝛿, whereΟ(1/ 𝑛𝑛)

PAC-Bayesian stability bound [Rivasplata, Kuzborskij, Szepesvári, and ShaweTaylor, 2019]65

Excess risk bound
Excess risk:

追加の仮定:•: モデルの複雑さを制御•• Bernstein条件 [Erven et al., 2015]:•• 二乗損失 (𝑠𝑠 = 1)
• ロジスティック損失 with 有界な𝑓𝑓, 𝑓𝑓 ∗ (𝑠𝑠 = 1)損失関数は対数尤度である必要はない．
真の分布が軽い裾を持っていることを仮定．

66

Fast rate: 一般形
Let

and

Thm (Fast rate: excess risk bound)67.

Proof idea

Prior mass
Concentration function:

68

Gaussian correlation inequality

69

This had been a conjecture for a long time (at least from 1972).
Royen resolved this problem in 2014 using relatively elementary tools.
••

T. Royen. A simple proof of the gaussian correlation conjecture extended to multivariate
gamma distributions. arXiv preprint arXiv:1408.1028, 2014.
R. Latała and D. Matlak. Royen’s proof of the Gaussian correlation inequality. pages 265–275. Springer International Publishing, 2017.

Fast rate: 回帰ℓ 𝑓𝑓, 𝑧𝑧 = 𝑓𝑓 𝑥𝑥 − 𝑦𝑦 2 : 二乗損損失とすることでSobolev空間のミニマックス最適レートに一致する(𝛼𝛼 = 𝛽𝛽の時).

70

判別問題における速い収束

Assumption• 強低ノイズ条件:

1
1/2

•

0

• 活性化関数はなめらか:• 真の関数はモデルに入っているとする: 𝑓𝑓 ∗ = 𝑓𝑓𝑊𝑊∗ ．
十分大きな𝑛𝑛と𝛽𝛽 ≤ 𝑛𝑛に対し，

ベイズ最適な判別機が高い確率で求まる．(𝛽𝛽は定数のままでも良い)71Summary

72

深層学習の統計理論→非凸性が重要→非凸性を残した最適化
理論．
• 無限次元Langevin動力学
 弱収束の収束速度
 正則化を入れることで無限次元での収束を保証• 無限次元Langevin動力学の汎化誤差理論

 擬-ベイズ事後分布
 汎化ギャップ
 Fast rateの導出→非凸最適化とノンパラ統計

何がまだ足りないか?
• 深層学習の適応能力 (minimax最適性).

 Hölder class [Schmidt-Hieber, 2017]
 Besov space [Suzuki, 2019][Hayakawa&Suzuki, 2019] Piece-wise smooth [Imaizumi&Fukumizu, 2018]
 Anisotropic Besov [Suzuki&Nitanda, 2019]→ 最適化理論と統計理論の融合