1

深層学習の数理鈴木大慈
東京大学大学院情報理工学系研究科数理情報学専攻
理研AIP

2023年(令和5年)7月18日
東北大学集中講義

鈴木大慈

2

所属
➢ 東京大学大学院情報理工学系研究科数理情報学専攻・准教授➢ 東大次世代知能科学研究センター研究部門研究者（研究知能部門）➢ 理化学研究所 革新知能統合研究センター 深層学習理論チーム チームリーダー

専門

鈴木大慈
情報理工学系研究科➢ 機械学習，数理統計学，統計的学習理論

主な研究内容スパース推定➢ 深層学習を含む様々な学習機構について理論的側面から研究を進めています．学習理論を通じて各種学習手法の汎化性能や学習アルゴ
リズムの収束性能を解明し複雑な学習過程の本質への理解を深め，理論をもとに新しい機械学習手法の構築や応用への還元を行っています．また，確率的最適化などの方法により大規模かつ複雑な機械
学習問題を効率的に解く手法の開発も行っています．

著書/授賞➢『確率的最適化（機械学習プロフェッショナルシリーズ）』講談社，2015年
8月8日．
➢金森敬文，鈴木大慈，竹内一郎，佐藤一誠：『機械学習のための連続最適化(機械学習プロフェッショナルシリーズ)』講談社，2016年12月7日.
➢文部科学大臣表彰・若手科学者賞「深層学習の原理解明に向けた統計的学習理論の研究」．文部科学省，2020年4月7日．
➢第11回日本統計学会研究業績賞 (2017年度)．2017年9月5日.
➢Satoshi Hayakawa and Taiji Suzuki:日本神経回路学会論文賞．日本神経回路学会，2021年9月23日．
➢日本応用数理学会，ベストオーサー賞（論文部門）．2019年9月4日．

応用

http://ibis.t.u-tokyo.ac.jp/suzuki/
taiji@mist.i.u-tokyo.ac.jp

関連する機械学習理論

特徴抽出

深層学習の理論
確率論
幾何学

数学

最適化理論

関数解析

数理統計

解釈可能性：
説明可能性，データの可視化，メンテナ
ンスの容易化
各種テクニックの解析：
アーキテクチャの解析，損失関数の設計，最適化技法の解析
深層学習の原理解明：「表現理論」「汎化誤差理論」「最適化理論」

研究室URLとメール連絡先
➢
➢

カーネル法

基礎

学習の本質解明：“良い”学習手法の特徴付け，統一理論，
深層学習を優越する方法論の提唱

深層学習の広がり

3

Large language model
Learning efficiency
of few shot learning

様々なタスクで高い精度
なぜ？
AlphaGo/Zero[Alammar: How GPT3 Works - Visualizations andAnimations,
https://jalammar.github.io/how-gpt3-worksvisualizations-animations/]

Performance of few-shotlearning against model size

[ChatGPT. OpenAI2022][Brown et al. “Language Models are Few-Shot Learners”, NeurIPS2020]

Generative models (diffusion models)[Silver et al. (Google Deep Mind): Mastering the game of Gowith deep neural networks and tree search, Nature, 529, 484—
489, 2016][Ho, Jain, Abbeel: Denoising Diffusion Probabilistic Models. 2020]

Image recognition[He, Gkioxari, Dollár, Girshick: Mask R-CNN, ICCV2017]

Stable diffusion,
2022.

Jason Allen "Théâtre D'opéra
Spatial“ generated by Midjourney. Colorado
State Fair’s fine art competition, 1st prize indigital art category

解決すべき問題点
なぜ深層学習はうまくいくのか？
• 「○○法が良い」という様々な仮説の氾濫．
• 世界的課題• 原理解明• どうすれば“良い”学習が実現できるか？→新手法の開発
学会の問題意識民間の問題意識• 中で何が行われているか分からないものは用いたくない．
• 企業の説明責任．深層学習のホワイトボックス化．

Ali Rahimi’s talk at NIPS2017 (test of time award).
“Random features for large-scale kernel methods.”“錬金術”という批判

理論の必要性4深層学習(AI)の研究
応用

応用：AI手法の各種問題への応用

5

物理の対応物
半導体，新材料の開発

画像生成，パターン認識，たんぱく質構造予測

方法論：各種機械学習手法の開発
損失関数の設計，正則化法の開発，学習アルゴリズムの開発

各種方法論の定式化，学習アルゴリズムの開発

理論：統計的学習理論，最適化理論
深層学習の理論，収束レート解析，最適化アルゴリズム

基礎

素粒子論など各種機械学習手法の原理解明，最適性の理論的保証，
我々の得意分野
アルゴリズムの数理研究

深層学習の理論概観

6

応用

解釈可能性：
説明可能性，データの可視化，メンテナン
スの容易化

各種テクニックの解析：
アーキテクチャの解析，損失関数の設計，最適化技法の解析理論を通して深層学習の不可思議な挙動を理解したい．
➢ 説明責任➢ 可能性と限界の把握➢ 学習手法設計の指針

応用から基礎まで
深層学習の原理解明：
広い範囲に“理論”
表現理論，汎化誤差理論，最適化の収束理は遍在する．
論
学習の本質解明：“良い”学習手法の特徴付け，統一理論，
深層学習を優越する方法論の提唱
基礎

今日の範囲

数学の役割7

物理学• 相対性理論• 量子力学

現象

数学

機械学習（情報学）

数学者・物理学者も参入
•
•
•
•

深層学習

• リーマン幾何• 関数解析

確率論
• 統計学
関数解析
• 最適化理論
Wasserstein幾何 • 数値計算
熱拡散方程式数学

NNの構造8

画像-猫 (y=1)-犬 (y=2)-人間 (y=3)

ベ
ク
ト
ル

ベ
ク
ト
ル

学習：「関数」をデータに当てはめる
モデル：関数の集合（例：深層NNの表せる関数の集合）

各層の詳細アフィン変換＋活性化関数

活性化関数• ReLU (Rectified Linear Unit)• シグモイド関数

9訓練誤差と汎化誤差
パラメータ
損失関数

10

：ネットワークの構造を表す変数：パラメータ がデータをどれだけ説明しているか

予測誤差：損失の期待値

本当に最小化したいもの．

訓練誤差：有限個のデータで代用

代わりに最小化するもの．
(訓練データはテストデータと同じ分布に従っていると仮定)

この二つには大きなギャップがある．
[過学習]※クラスタリング等，教師なし学習も尤度を使ってこのように書ける．

学習理論の設定

11• 汎化ギャップ(汎化誤差)と余剰誤差
Generalization gap

Excess risk

汎化誤差:
余剰誤差:
もしくは

汎化誤差

最適化誤差

汎化誤差2

モデルバイアス𝐿 𝜃መ − 𝐿∗ = 𝐿 𝜃መ − 𝐿෠ 𝜃መ + 𝐿෠ 𝜃መ − 𝐿෠ 𝜃 ∗ + 𝐿෠ 𝜃 ∗ − 𝐿 𝜃 ∗ + 𝐿 𝜃 ∗ − 𝐿∗

学習機の複雑さと学習能力

12• No free lunch theorem「あらゆる問題で最高の性能を出す汎用的学習機は実現不可能であり，ある問題に特殊化された手法に勝てない」
予測誤差ある問題に特化した方法

平均

汎用的な方法問題

学習手法は「どこかを“贔屓”する必要がある」→ モデリングの重要性 (オッカムの剃刀)
DLも例外ではない: CNN, Transformer, ResNet, …
William of Ockham：1285-1347．スコラ学の神学者，哲学者．
No free lunch theorem: [D.H.Wolpert and W.G. Macready: 1995,1997][Y.C. Ho and D.L. Pepyne: 2002]

13「なんでもできる手法は個別問題で負ける」「必要以上に複雑なモデルを当てはめると失敗する」（注：すでに学習済みのモデルに関する話ではない．大量のデータで学習した汎用モデルが個別問題でも勝つことはある．あくまでゼ
ロ知識の状態から学習を始めた場合の精度比較である．）

14

モデル２

モデル１

推定量A

推定量B

真の関数
各推定量は対応するモデル内に値を取るし，正則化や事前分布の影響でモデル内でも取りやすい値と取りにくい値がある．
→ そういった場所を贔屓しているということ．

リスクの概念15• 真によらず常に予測誤差を最小化する推定量は存在しない．

「汎化誤差を最小化する」みたいな
文言はそれ自体厳密な意味はない．

➢「最適」な推定量をどう特徴づけるか？
：真の分布のモデル：訓練データ：真の分布
推定量「真の分布のモデル」は本当に実際のデータ生成過程がそのモデルに入っている必要はなく仮想的なもので良い．
あくまで，その推定量がどの設定で最適であるかを特徴づけるための仮想的モデルと考えてよい．

◼ ミニマックス最適性（最悪誤差が最小）◼ 許容性

෨
つぎのような𝜃が存在しない:（一様に改善されることはない）◼ ベイズ最適性
ベイズリスク𝜋0 : 事前分布
መを最小にする推定法𝜃.
(→ ベイズ推定量)（事前分布で重みづけたリスクを最小化）

16

深層学習の理論理論的課題
表現能力
どれだけ難しい問題まで学習できるようになるか？
汎化能力
有限個のデータで学習した時，どれだけ正しく初見のデータを正解できるようになるか？
最適化能力
最適な重みを高速に計算機で求めることが可能か？

17

18

余剰誤差

スケーリング則[Kaplan et al.: Scaling Laws for Neural Language Models, 2020]
モデルサイズ固定（基本的に訓練データサイズと思ってよい）

Reducible loss

[Henighan et al.: Scaling Laws for Autoregressive Generative Modeling, 2020]

log(予測精度)=−𝛼 log 𝑛 + log(𝐶)[Brown et al.: Language Models are Few-Shot Learners, 2020] (GPT-3モデルの解析)

19

基本的考え方20• スケーリング則は古典的な学習理論でも現れる．
(正規直交系 in L2)

真のモデル

ただし
を用いて

観測データ：

学習モデル

正則化学習法 (カーネル法)

バリアンス バイアス

予測誤差

最適なモデルサイズ𝑀𝑎log 予測誤差 = − 1+𝑎log 𝑛 + log(𝐶)𝑀−𝑎バリアンス=モデルの次元/nバイアス=切り捨てた係数の二乗和

21

最適なモデルサイズの予測誤差
𝑎log 予測誤差 = − 1+𝑎log 𝑛 + log(𝐶)log(予測誤差)

モデルサイズM固定の予測誤差

log(𝒏)

22

カーネル法の学習理論• Caponnetto and De Vito. Optimal Rates for the Regularized LeastSquares Algorithm. Foundations of Computational Mathematics,
volume 7, pp.331–368 (2007).
• Steinwart and Christmann. Support Vector Machines. 2008.
関連する最近の論文• Mei, Misiakiewicz, Montanari. Generalization error of random
features and kernel methods: hypercontractivity and kernel matrix
concentration. arXiv:2101.10588.
• Bordelon, Canatar, Pehlevan. Spectrum Dependent Learning
Curves in Kernel Regression and Wide Neural Networks.
arXiv:2002.02561.
• Canatar, Bordelon, Pehlevan. Spectral Bias and Task-Model
Alignment Explain Generalization in Kernel Regression andInfinitely Wide Neural Networks. arXiv:2006.13198.

深層学習との違い

23

非線形化

• 線形モデル可変基底化• カーネルモデル

固定

固定

学習可能

学習可能

学習可能

• 深層モデル

学習可能

深層学習との違い

24

非線形化

• 線形モデル可変基底化• カーネルモデル

問題意識
固定
固定 学習可能基底を学習可能にすることで何が良くなるか？
•• 深層モデル• 逆に過学習を起こさないか？
• 最適化可能か？
学習可能

学習可能

学習可能

参考資料
Deep learning theory lecture notesby Matus Telgarsky• https://mjt.cs.illinois.edu/dlt/
その他，学習理論の教科書

25

26

第1部
深層学習の表現能力

表現能力「万能近似能力」
二層ニューラルネットワークはどんな関数も任意の精度で近似できる．

理論的にはデータが無限にあり，素子数が無限にあるニューラルネットワークを用いればどんな問題でも学習できる．
[Hecht-Nielsen,1987][Cybenko,1989]「関数近似理論」
年

基底関数

空間

1987

Hecht-Nielsen

対象毎に構成𝐶(𝑅 𝑑 )

1988

Gallant & White

Cos

𝐿2 (𝐾)

Irie & Miyake

integrable

𝐿2 (𝑅 𝑑 )Carroll & Dickinson

Continuous sigmoidal

𝐿2 (𝐾)

CybenkoContinuous sigmoidal

𝐶(𝐾)Funahashi

Monotone & bounded

𝐶(𝐾)

1993

Mhaskar + Micchelli

Polynomial growth

𝐶(𝐾)

2015

Sonoda + Murata

Unbounded, admissible

1989

𝐿1 (𝑅 𝑑 )/𝐿2 (𝑅 𝑑 )27関数近似の様子

28

関数近似の様子

ReLU活性化関数

29

関数近似の様子

30

関数近似の様子

31

関数近似の様子

32…

連続関数の近似• Cybenkoの理論[Cybenko: Approximation by superpositions of a sigmoidal function.
Mathematics of control, signals and systems, 2(4): 303-314, 1989]

定義
活性化関数𝜂がシグモイド的 ⇔定理
活性化関数𝜂が連続なシグモイド的関数なら，任意の𝑓 ∈ 𝐶( 0,1 𝑑 )と，任意の𝜖 > 0に対して，ある𝑔 𝑥 = σ𝑁𝑖=1 𝛼𝑖 𝜂 𝑎𝑖 𝑥𝑖 + 𝑏𝑖 が存在して，

とできる．

33

証明の直感的概略• シグモイド型の関数に対し，が成り立つ．つまり，スケールを適切に選べば，階段関数をいくらでもよく近似できる．

• 階段関数を近似できれば，それらを足し引きすることで，cos 𝛼 ⊤ 𝑥 + 𝛽 や sin 𝛼 ⊤ 𝑥 + 𝛽 をいくらでもよく近似できる．
• cos, sinが実現できるならFourier(逆)変換もできる．

• 任意の連続関数が近似できる．

34

積分表現 (Ridgelet変換)

35• Fourier変換• Ridgelet変換[Wikipedia,フーリエ変換]

NNはFourier変換におけるsin,cosの代わりに非線形ノードの足し合わせで関数を表現．

ウェーブレット変換 + ラドン変換
ある𝜓: ℝ → ℝが以下の「許容条件」を満たすとする：
෠ 𝜂はFourie変換)(𝜓,ො(Ridgelet変換)(双対Ridgelet変換)

定理(再構成定理)CTスキャンカーネル法36• 浅い手法の代表格．
• これも万能近似能力がある．
第1層目を固定した横幅無限の2層ニューラルネットワーク
似た手法• スプライン法• 局所多項式回帰• シリーズ推定量(線形推定量と呼ばれるクラス)• 第一層目固定• 無限個の素子

…

…

学習

固定
：カーネル関数

線形判別機(カーネル法)

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

深層NNとカーネル関数

37

深層NNは「カーネル関数をデータに合わせて学習する方法」と言える

෡ℓ に対応した再生核ヒルベルト空間𝒌(より正確には同じ を与える の中でを取る)これまででわかったこと• [理論] 万能近似能力という意味では浅層で十分．
• [実際] 実際は多層を使うことが多い．
→ この差はどう埋める？
カーネル法
浅層

多層ニューラルネット
深層学習→ 「表現力」を比べてみる．

38

(1)ランダム特徴量の近似能力

39

ランダム特徴：これは近似対象に合わせて自由に設定

ランダムに生成(球面上の一様分布) (固定)疑問：ある対象の関数𝑓 ∗ を近似するのに必要なランダム特徴量の数𝑀はどれくらい？

実は，一つのニューロンを近似するのにも𝑀 = exp Ω(𝑑) 必要．(次元の呪い)
つまり，ランダムに特徴量を生成する方法は非常に効率が悪い．
深層学習のように第一層目のパラメータも学習した方が効率的．

※ ランダム特徴量の方法は，カーネルの低ランク近似法とみなせる． (特徴学習の必要性)

定理 (Yehudai and Shamir 2019)あるであるためには，が存在して，が必要．

[Yehudai and Shamir. On the power and limitations of random features for understanding neural networks.
NeurIPS2019.]

(2-a) Barron classとランダム特徴量• 𝜋で決まる再生核ヒルベルト空間：

ただし（実際，これは再生核をとするRKHSになっている．）• 𝑀個のランダム特徴量で張られるモデル：

ランダムに生成して固定(近似対象によって変えない)定理 (Barron classの近似定理; E, Ma, Wu, 2019)

ある確率測度𝜋が存在して，その𝜋によって決まる再生核ヒルベルト空間の元𝑓 ∈ ℋ𝜋 ( 𝑓 ℋ𝜋 ≤ 1) を適切に取ってくると，以下が成り立つ:

次元の呪い(誤差𝜖を達成するには𝑀 = 𝜖 −Ω(𝑑) 必要)[E, Ma, Wu: A Comparative Analysis of Optimization and Generalization Properties of Two-layer Neural Network
and Random Feature Models Under Gradient Descent Dynamics. arXiv:1904.04326, 2019]40

(2-b) NNによる次元の呪いの解消

41

一方で，近似対象の関数𝑓に対して，適切に一層目のパ𝑀
ラメータ 𝑢𝑗 𝑗=1 を設定すると，次元の呪いを回避できる．
これも動かせる：NNの集合NNによって関数近似の効率が改善されている．
−1/𝑑
−1

𝑀

(一層目固定)⇒ 𝑀(一層目可変)直感：ランダム特徴量だと(d-1)次元単位球面全体を覆うのに，1/𝜖 𝑑 個のニューロンが必要．
[E, Ma, Wu: A Comparative Analysis of Optimization and Generalization Properties of Two-layer Neural Network
and Random Feature Models Under Gradient Descent Dynamics. arXiv:1904.04326, 2019]

多層化による表現力の増大

42

参考

深さに対して指数関数的に“表現力”が上がる．
• 超平面アレンジメント [Montufar et al., 2014]
空間の領域分割数• 多項式展開，テンソル解析 [Cohen et al., 2016; Cohen & Shashua, 2016]
単項式の次数• 代数トポロジー [Bianchini & Scarselli, 2014]
ベッチ数(Pfaffian)• リーマン幾何 + 平均場理論 [Poole et al., 2016]
埋め込み曲率

特に，対称性の高い関数の近似は深層NNが有利ℎ(𝑥)ℎ ∘ ℎ(𝑥)ℎ ∘ ℎ ∘ ℎ(𝑥)

多層が得する例 (1): 領域分割数43

参考NNの“表現力”：領域を何個の多面体に分けられるか？
• 層の数に対して表現力は指数的に上がる．
𝐿：層の数• 中間層のユニット数 (横幅) に対しては多項式的． 𝑛：中間層の横幅
𝑛0 ：入力の次元

折り紙のイメージ
Montufar, Guido F., et al. "On the number of linear regions of deep neural networks." 2014.

多層が得する例 (2): 対称な関数

参考

44

深層NNは特徴量を適切に抽出することで次元の呪いを回避できる．

はBessel関数を元に構成

三層 (中間層二層)：O(poly(𝑑𝑥 ))ノードで十分
二層 (中間層一層)：Ω(exp(𝑑𝑥 ))ノードが必要 (次元の呪い)
三層

まず二乗和𝑥12 + ⋯ + 𝑥𝑑2𝑥を作ってからgを作用．
𝑔
𝑥32

𝑥22

𝑥3 𝑥2 𝑥1

(中間層で座標軸方向だけを見ればよい)
𝑥12

二層(Eldan&Shamir, 2016)

全方向をケアする必要がある（座標軸方向だけではダメ）多層が得する例 (3): 区分線形関数の表現

45•

任意の区分線形関数(R𝑑 → R)は深さ log 2 (𝑑 + 1) のReLU-DNNで表現可能

参考• ある横幅𝑤，縦幅𝑘のReLU-DNNが存在して，それを縦幅𝑘’(< 𝑘)のネットワークで表現するには横幅𝑘 ′ 𝑤 𝑘/𝑘′ − 1が必要．
深

𝑘

浅

等価な関数
を浅いNNで表現𝑘’(Arora et al., 2018)

大きな横幅が必要

やはり層の深さに対し指数関数的に表現力が増加
上記のネットワークの例

多層が得する例 (4): 有理関数の近似

46

参考• 有理関数をReLU-DNNで近似: 𝒓次多項式
をReLU-DNNで近似したい

あるReLU-DNN が存在してノード数と近似誤差が次のように抑えられる：
ノード数

近似誤差

• ReLU-DNNを有理関数で近似-層で各層のノード数 の任意のReLU-DNN に対しては，次数と近似誤差が以下で抑えられる有理関数𝑝/𝑞が存在：
次数（分母qと分子pの次数の最大値）

近似誤差

深さに対して指数的に増大• ReLU-DNNを多項式で近似：の次数が必要→有理関数に比べて表現力が低い

多層が得する例 (4): 有理関数の近似

47

参考• 有理関数をReLU-DNNで近似: 𝒓次多項式
をReLU-DNNで近似したい

あるReLU-DNN が存在してノード数と近似誤差が次のように抑えられる：
ノード数

近似誤差

• ReLU-DNNを有理関数で近似-層で各層のノード数 の任意のReLU-DNN に対しては，次数と近似誤差が以下で抑えられる有理関数𝑝/𝑞が存在：
次数（分母qと分子pの次数の最大値）

近似誤差

深さに対して指数的に増大• ReLU-DNNを多項式で近似：の次数が必要→有理関数に比べて表現力が低い

48

深層学習の適応的推定能力-ノンパラメトリック回帰理論-

問題意識

49

ニューラルネットワークは「なぜ良いのか？」
カーネル法(線形モデル)

深層モデル

学習可能

学習可能

固定

学習可能

解析対象

• 統計的効率性• 最適化の効率性(トレードオフの関係)• 深層とカーネル法の性能を理論的に比較• 深層学習の最適化を理論的に解析➢ 深層学習の「適応能力」は本質的
カーネル法

適応能力とは？
• 代表的な適応的推定法：スパース推定
やりたいこと：入出力関係を表す関数𝑦 = 𝑓(𝑥) を推定したい．
➢ 事前にたくさんの基底を用意➢ それらの線形結合で真の関数を表現➢ 基底は冗長性があるように用意しておき，データに合わせて必要な基底のみ選択して使う．
→スパース推定➢ データに合わせて基底を選ぶので適応的と言う．
𝛽1 𝛽2 𝛽3 𝛽4 𝛽 𝛽𝑝5𝛽2 = 0𝛽4 = 0𝛽5 = 0多くの係数が0⇒ スパース

スパース推定の恩恵➢ 推定精度が上がる．
➢ 解釈性が向上する．

50

51

David Donoho

Gauss prize (2018)
Sparse estimation,
wavelet-shrinkage,compressive sensing，...

Robert Tibshirani

Lasso (1996)→ L1正則化によるスパース推定

Wavelet shrinkage (Donoho&Johnstone, 1992)→ Besov空間，スパース推定の適応能力

深層学習との関係

52• スパース推定：
基底を沢山用意してその中から選択．
• 深層学習：基底を事前に用意せず，データに合わせて構築．

基底関数

非適応的手法：➢ データによらず全部使う：リッジ回帰
適応的手法：➢ 沢山の候補の中から選ぶ：スパース推定➢ データに合わせて構築：深層学習

中間層で基底を構成

適応的推定能力

典型的な例[Imaizumi&Fukumizu, 2019][Suzuki, 2019]

滑らかな部分とそうでない部分が混在

滑らか

変動が大きい(滑らかでない)

Besov空間[Schmidt-Hieber, 2019] [Nakada&Imaizumi,
2019][Chen et al., 2019][Suzuki&Nitanda, 2019]

大きく変動する方向とそうでない方向が混在

53

直感的説明非滑らか滑らか• ガウスカーネルを用いた関数近似 (カーネル法・非適応的)

同じ幅の基底の線形結合 → 効率悪い

• NNによる関数近似

場所によって解像度(幅)の違う基底を生成可能 → 効率良い54

統計的推定理論による比較

55

深層 vs 浅層 の統計理論→「関数近似精度/推定精度」を比べてみる．
「多層」による特徴抽出と推定精度
ノンパラメトリック回帰の設定
𝜉𝑖 ∼ 𝑁 0, 𝜎 2 は観測誤差推定誤差 (平均二乗誤差):※実はこれは二乗損失の平均余剰誤差になっている．

Hölder, Sobolev, Besov空間

直観的意味

56

滑らかさ

空間的一様性

空間的非一様性

0

滑らかさの度合いBesov空間とスパース性との関係
Wavelet基底

解像度

𝛼0,1

𝑘=0
𝑘=1

低周波

𝑘=2

𝑗=1
𝛼1,1
𝑗=1
𝛼2,1 𝛼2,2
𝑗=1

𝑗=2

𝛼1,2
𝑗=2
𝛼2,3 𝛼2,4
𝑗=3

𝑗=4

𝑘=3
高周波

場所によって滑らかさが違うのでウェーブ
レット基底のスパースな線形結合が有効(0 < 𝑝)(informal)

Wavelet基底による展開

小さな𝑝 = スパースな係数

空間的な滑らかさの非一様性

57

Besov空間とスパース性との関係
Wavelet基底

解像度

𝛼0,1

𝑘=0
𝑘=1

低周波

𝑘=2

𝑗=1
𝛼1,1
𝑗=1
𝛼2,1 𝛼2,2
𝑗=1

𝑗=2

𝛼1,2
𝑗=2
𝛼2,3 𝛼2,4
𝑗=3

𝑗=4

𝑘=3
高周波

場所によって滑らかさが違うのでウェーブ
レット基底のスパースな線形結合が有効(0 < 𝑝)(informal)

Wavelet基底による展開

小さな𝑝 = スパースな係数

Wavelet-shrinkage

空間的な滑らかさの
非一様性

58

59

𝐿𝑝 ノルムのボール

「浅い」学習との比較

60• 深層学習は場所によって解像度を変える適応力がある→学習効率が良い• 浅い学習は様々な関数を表現できる基底をあらかじめ十分用意して“待ち構える”必要がある．
→学習効率が悪い𝑠
仮定 𝑓 ∘ ∈ 𝐵𝑝,𝑞
( 0,1 𝑑 ): 真が“Besov空間”に入っている．

線形推定量 (非適応的手法)[Suzuki, ICLR2019]

深層学習

カーネルリッジ回帰等：≫
最適ではない最適(𝑛: sample size，𝑝: uniformity of smoothness，𝑠: smoothness)
一様な解像度
平均二乗誤差 E 𝑓መ − 𝑓 ∗2

適応的解像度がサンプルサイズが増えるにつれ減少するレート

ミニマックス最適性の意味で理論上これ以上改善 • Wavelet shrinkageより弱い条件• 基底を用意せず最適化するだけでOKできない精度を達成できている．

線形推定量“浅い” 学習法
Kernel ridge regression:

61
学習可能

正則化付き最小二乗推定量
固定(特徴マップ)固定

グラム行列 (カーネル関数)(see also [Imaizumi&Fukumizu, 2019])

線形推定量: 観測値𝑌 = 𝑦𝑖 𝑛𝑖=1 に対して線形な推定量.

例

線形

•
•
•
•

Kernel ridge estimator
Sieve estimator
Nadaraya-Watson estimator
k-NN estimator証明: (0) ノーテーション

•
•
•
•

縦幅：
横幅：
枝の数：
各パラメータの上限：• 活性化関数はReLUを仮定

62の深層NNモデルの集合

証明: (1) 近似誤差の評価

63• 0 < 𝑝, 𝑞, 𝑟 ≤ ∞と0 < 𝑠 < ∞が以下を満たすとする:(𝐿𝑟 -可積分性)•を𝑠 < min{𝑚, 𝑚 − 1 + 1/𝑝}を満たす整数とする．

深層ニューラルネットワークの近似誤差ある自然数 と用いて深さ , 横幅 , 枝の数 , ノルム上界 を以下のように定める：

すると，深層NNは以下の誤差でBesov空間の元を近似できる：

大体パラメータ数

Pinkus (1999), Mhaskar (1996): 𝑝 = 𝑟かつ1 ≤ 𝑝, ReLU活性化関数ではない．
Petrushev (1998): 𝑝 = 𝑟 = 2, ReLU活性化関数ではない (𝑠 ≤ 𝑘 + 1 + (𝑑 − 1)/2)．

証明: (1) 近似誤差の評価の導出

64• Step 1: Besov空間の基底展開∵ B-Splineによる適応的近似[DeVore & Popov, 1988; Dung, 2011]⋅ 𝐿𝑟 ≤ 𝑁 −𝑠/𝑑

• Step 2: 各基底をDNNで近似.
: DNNによる近似.
: 線形結合• Step 3: 二つの評価を統合≤ O(𝑒 −𝐿 )≤ 𝑁 −𝑠/𝑑証明: (2) バイアス-バリアンス分解

65（局所Rademacher complexityを用いて証明）
古典的なノンパラ回帰の方法でOK．DNNに関する評価は[Schmidt-Hieber, 2019; Hayakawa&Suzuki,2020]

深さ

横幅

スパース性
(非零パラメータ数)

各パラメータの絶対値の上界なら⇒ バイアスとバリアンスのトレードオフをバランスすればよい．

証明: (3) 推定精度の導出

66• 最小二乗解 (訓練誤差最小化)

ただし，(clipping)．

定理 (推定精度)
,

かつ

のとき，

とすることで，
3

𝑝 = 𝑞 = ∞のとき，Schmidt-Hieber (2017) に帰着．

スパース推定との繋がり

67

深層学習の理論➢ 適応的推定理論➢ Besov空間を用いた解析

Wavelet shrinkage
圧縮センシング• Donoho• Candes&Tao

Lasso

第三次AIブーム- 深層学習- 産業応用ビッグデータブーム
スパース推定の流行
機械学習の興隆

1990

1995

2000 2006 2010

ILSVRC
Supervision優勝

2011

2012

2019

他にも様々な理論が68• 真の関数𝑓 ∘ の形状によって深層が有利になる
縮小ランク回帰
特徴空間の次元が低い状況は深層学習が得意

深
層
カ
ー
ネ
ル

区分滑らかな関数

Besov空間

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

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

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

データが低次元部分空間上に分布していたら深層学習が有利推定精度数学的に一般化

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

0.5x

深層:𝟏/𝒏カーネル: 𝟏/ 𝒏

𝒏倍の違い

0.5x

=

+
ジャンプ3か所

ジャンプ3か所

ジャンプ6か所→ 「スパース性」と「非凸性」[Satoshi Hayakawa and Taiji Suzuki: On the minimax optimality and superiority of deep neuralnetwork learning over sparse parameter spaces. Neural Networks, Vol.123, pp. 343—361, 2020]線形推定量の最悪誤差
線形推定量：
例: カーネルリッジ回帰70と書ける任意の推定量(“浅い”学習法とみなす)• 凸包を取って大きく膨らむような
関数クラスにおいては深層NNを使うメリットがある．
• 特徴量(基底関数)を適応的に作ることで，ターゲットを「狙い撃ち」して近似．
• 一方，線形推定量は広めにモデルを取って「待ち構えて」いる必要がある．

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

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

71

Besov空間

縮小ランク回帰

変動指数
Besov空間

非凸性
スパース性

低次元データ

適応的推定法• (勾配)ブースティング• スパース推定• 深層学習典型的な例
滑らかな部分とそうでない部分が混在

滑らか

変動が大きい(滑らかでない)

Besov空間

大きく変動する方向とそうでない方向が混在72

高次元データの特徴抽出

73

深層ニューラルネットは特徴抽出に長けている．
➢ 合成関数を推定できる．
(合成される各関数ℎℓ が“単純”であれば層に分割することで得をする)

特徴抽出（無駄な情報を削除）

典型例• ガウスカーネルを用いた関数近似
変動する方向を特定できない→次元の呪い• NNによる関数近似
変動する方向を表す特徴量を中間層で抽出→次元の呪いを回避

次元の呪い推定誤差のバウンド：

近似誤差のバウンド:→ 次元の呪い74

アプローチ (1): 多様体回帰
-dim

75

-dim

MNIST: 784 dim/13.4 intrinsic-dim[Facco et al. 2017]• Classic nonparametric method: Bickel & Li (2007); Yang & Tokdar (2015);
Yang & Dunson (2016).
• Deep learning: Nakada & Imaizumi (2019); Schmidt-Hieber (2019);
Bauer & Kohler (2019); Chen et al. (2019a,b); Liu et al. (2021).

データが低次元多様体*に分布していれば次元の呪いを回避できる！
* Nakada&Imaizumi (2019) では非滑らかな低次元構造も許容 (Hausdorff次元が小さい)アプローチ (2): 関数の平滑性の非等方性

76[Suzuki&Nitanda: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic
Besov space. NeurIPS2021.]

不変な方向

変化する方向𝑠1 , 𝑠2 , 𝑠3 : 滑らかさ
(非平滑) 𝑠1 , 𝑠2 ≪ 𝑠3 (平滑)データが低次元多様体からはみ出る場合：• 真の関数の滑らかさが方向に依存．
• 多様体に直交する方向にはほぼ定数 (滑らかさ大)(超)高次元入力NNの学習理論

77

Suzuki&Nitanda: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space.
NeurIPS2021, spotlight.

••

真の関数が方向によって異なる滑らかさを持つ状況では
DNNは重要な方向を見つけ，次元の呪いを回避する．
一方で，浅い学習法は次元の呪いを受ける．

関連研究：- 教師生徒設定における大域的最適化と次元の呪いの回避
Suzuki and Akiyama: ICLR2021, spotlight.

- 深層学習の浅層学習への優位性:

Hayakawa and Suzuki: Neural Networks 2020,
日本神経回路学会論文賞．

𝑠1 , 𝑠2 , 𝑠3 : 滑らかさ

不変な方向
変化する方向真の関数の滑らかさが方向によって大きく異なる
状況滑らかでない方向が少なければ次元の呪いを回避できる．
→ 「非等方的Besov空間」を用いた理論．
Def. (非等方的Besov空間)

真の関数のモデル：
非等方的Besov空間の元の合成関数𝑠: 非等方的Besov空間 (𝐵𝑝,𝑞).
(ℓ)➢ 滑らかさが方向によって異なる関数空間➢ 合成することで様々な形状を実現(例：多様体上の関数: 一層目で座標を抽出，二層目がその座標上の関数)

(超)高次元入力NNの学習理論

78

Suzuki&Nitanda: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space.
NeurIPS2021, spotlight.

••

真の関数が方向によって異なる滑らかさを持つ状況では
DNNは重要な方向を見つけ，次元の呪いを回避する．
一方で，浅い学習法は次元の呪いを受ける．

関連研究：- 教師生徒設定における大域的最適化と次元の呪いの回避
Suzuki and Akiyama: ICLR2021, spotlight.

- 深層学習の浅層学習への優位性:

Hayakawa and Suzuki: Neural Networks 2020,
日本神経回路学会論文賞．

𝑠1 , 𝑠2 , 𝑠3 : 滑らかさ

不変な方向
変化する方向真の関数の滑らかさが方向によって大きく異なる
状況滑らかでない方向が少なければ次元の呪いを回避できる．
→ 「非等方的Besov空間」を用いた理論．

真の関数のモデル：
非等方的Besov空間の元の合成関数

Def. (非等方的Besov空間)

直感𝑠: 非等方的Besov空間 (𝐵𝑝,𝑞).
(ℓ)➢ 滑らかさが方向によって異なる関数空間➢ 合成することで様々な形状を実現(例：多様体上の関数: 一層目で座標を抽出，二層目がその座標上の関数)

推定誤差の評価

79(最小二乗推定量)※今回は最適化手法に関しては議論せず，最適化はできるものと仮定する．

主結果
Let

,

各方向への滑らかさの調和平均が収束レートを決める．

例: 𝑯 = 𝟏の時

浅い学習方法との比較 (informal)：
深層

浅層（次元の呪いを受ける）

少ない数の方向において𝑠𝑖 が小さく(滑らかでない)，その他の方向には𝑠𝑖が大きい(滑らか)であるとき，次元の呪いを回避できる．

• 特徴抽出能力の重要性を理論的に正当化• 浅い学習方法は一番滑らかでない方向の滑らかさ(𝒔𝟏 )が支配的で，次元の呪いを受ける．
• 証明には「凸法の議論」を用いる．

線形推定量との比較 (より正確なステートメント)

80(s.t. 𝑊𝑥 + 𝑏 ∈ 0,1 𝐷 for any 𝑥 ∈ 0,1 𝑑 )𝑓 ∘ は𝐷-次元部分空間にのみ依存(非適応的)

線形推定量

深層

≪
(𝑛

−

2𝑠
2𝑠+1 when 𝐷 = 1)

深層にすることで次元の呪いを回避できている．

𝑐 = 1 if 𝐷 < 𝑑/2, 𝑐 = 0 if 𝐷 ≥ 𝑑/2.

(𝑛

2𝑠+𝑑

−2𝑠+2𝑑when 𝐷 = 1 and 𝑝 = 1)

無限次元入力NN
無限次元入力(画像，音声信号, 自然言語,...)
無限 (高) 次元データ
画像データ
関数データ

81

[Okumoto&Suzuki: Learnability of
convolutional neural networks for infinite
dimensional input via mixed and anisotropic
smoothness. ICLR2022.]

• 音声
• 文章

…
[Ramsay, J., Hooker, Giles, & Graves, Spencer. (2009). Functional data analysis with R and MATLAB (Use R!).
Dordrecht: Springer.]

さきほどの議論は入力の有限次元性を使っていた．
→ 実は無限次元まで拡張できる．
無限次元入力に対する深層学習の統計理論• 次元に依存しないバウンド (有限次元の拡張)• 畳み込みNNによる特徴量の抽出

出力
(実数)

拡散モデルの統計理論

82[Kazusato Oko, Shunta Akiyama, Taiji Suzuki: Diffusion Models are Minimax Optimal Distribution Estimators. ICML2023]
Forward process

Backward process
Stable diffusion, 2022.

経験スコアマッチング推定量:定理(𝑌𝑡 ∼ 𝑋𝑇−𝑡 )Let 𝑌෠ be the r.v. generated by the backward process w.r.t. 𝑠,Ƹ then(𝑠: 密度関数の滑らかさ)(for any 𝛿 > 0).

どちらも（ほぼ）ミニマックス最適 [Yang & Barron, 1999; Niles-Weed &Berthet, 2022].

(Estimator for 𝑊1 distance requires some modification)

Transformerの推定理論

83[Shokichi Takakura, Taiji Suzuki: Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions
with Infinite Dimensional Input. ICML2023]

Transformerの性質• かなり広いトークン幅から重要なトークンを選べる．
→ 次元の呪い？
• 入力に依存して重要なトークンを選択できる．
→ 次元の呪いを回避！
入力に依存して重要なトークンを切り替えることで，関数を「切り替えている」．

⋯

𝑌−1

𝑌0

⋮

⋮

𝑌1
⋮

𝑌2
⋮

⋯

Self-attention

FNN

⋯ 𝑥−1

𝑥0

𝑥1

𝑥2

⋯

定理 (推定誤差)(ほぼミニマックス最適)➢ 入力が無限次元でも多項式オーダーの収束レート.

収束レートに関する注意84

注意： 収束レートが速いからといって，その手法が常に良いとは限らない．
推定誤差
深層学習

浅い学習

このサンプルサイズ
では手法青が良い．

このサンプルサイズ
では手法赤が良い．

サンプル
サイズ

85

第2部
深層学習の汎化誤差-Overparametrization-

86• これまでの議論は，実は問題に合わせて「適切なサイズのネットワーク」を用いた場合の議論であった．
• 実際は，かなりサイズの大きなネットワークを用いる．
→

Overparameterization(過剰パラメータ化)

過学習

87

「なんでも表現できる方法」が最適とは限らない
少しのノイズにも鋭敏に反応してしまう
悪い学習結果良い学習結果悪い学習結果

過小学習

適切な学習

過学習

説明力が低すぎる

説明力が適切学習に用いるデータには誤りも含まれる

説明力が高すぎる（複雑すぎる）
一見当てはまりが良いので危険通常の学習理論

88

モデル ℱ: 𝑑-次元パラメータ𝑛: データサイズ

予測誤差 =

𝑑𝑛+

Variance(近似誤差)

inf
′

𝑓 ∈ℱ

𝑓 − 𝑓 ′ 2𝐿2(𝑃𝑋 )Bias

データサイズ (n) ≪ パラメータ数 (d)の場合，通常の学習理論をナイーブに当てはめると失敗する．
※カーネル法のような無限次元モデルもバイアスバリアンス分解で説明できるので，あくまで「ナイーブに」当てはめた場合
の話．

予測誤差

バリアンス
バイアス

ニューラルネットワークでは？
過小学習

適切な学習

過学習

89

従来の学習理論

90

適切な学習
実際は...

[Neyshabur et al., ICLR2019]

ネットワークのサイズを大きくしても過学習しない
データサイズ：120万
モデルパラメータサイズ：10億[Xu et al., 2018]

深層ニューラルネットの冗長性「Overparametrization」
パラメータサイズがデータサイズを超えている状況
での汎化性能を説明したい．

パラメータ数 ≫ データサイズ ≫ 実質的自由度
数十億

数百万

数十万

[仮説] 見かけの大きさ (パラメータ数) よりも実質的な大きさ (自由度) はかなり小さいはず．

“実質的自由度”を調べる研究：• ノルム型バウンド• 圧縮型バウンド「実質的自由度」として何が適切かを見つけることが理論上問題になる．

91

Uniform bound92Uniform bound“運良くデータに強く当てはまる”場所があるかもしれない．
→ 過学習

93

Uniform bound94

Uniform bound

過学習する場所がないことを保証するために一様なバウンドが必要

Uniform bound

モデルの「複雑さ」がバウンドに影響する→ 複雑すぎないことを保証する必要がある．

Rademacher
complexity

Dudley integral（covering num.）深層学習の汎化誤差バウンド (抜粋)
ノルム型バウンドNaïve bound

圧縮型バウンド

95Naïve bound (VC-次元)?
VC-次元 [Harvey et al.2017]☹ パラメータ数 σ𝐿ℓ=1 𝑚ℓ 𝑚ℓ+1 がそのままバウンドに現れてしまう．
☹ パラメータ数≫データサイズの状況を説明できていない．

96

どうやって改善するか？

ℱ: ネットワーク全体
෠ 学習済みモデルが入りℱ:

97

うるネットワークの集合𝑓መ ∈ ℱ෠෠※ ℱはℱよりもはるかに小さいと考えられる．
“典型的な学習済みネットワーク”の集合を解析する．

ノルム型バウンド

98

NN model:• Bartlett et al. (2017): Spectrally-normalized margin bound(最大特異値)➢ ς𝐿ℓ=1 𝑅ℓ,2 は中間層から最終層にどう誤差が伝搬するかを表すリプシッツ定数．
➢ 𝑅ℓ,2→1 /𝑅ℓ,2 は行列𝑊 (ℓ) のスパース性を表す．もし𝑊 (ℓ) が小さなノルムの行をたくさん含むなら，この値は小さくなる．

☺ 横幅に依存しない → 過剰パラメータ化されたネットワークにも使える!
[P. L. Bartlett, D. J. Foster, and M. J. Telgarsky. Spectrally-normalized margin bounds for neural networks. In Advancesin Neural Information Processing Systems, pp. 6241–6250, 2017]

ノルム型バウンド (2)99

NN model:• Neyshabur et al. (2017): PAC-Bayes bound(maximum singular value): Frobenius norm
(smaller than 𝑅ℓ,2→1 )➢ 𝑅ℓ,2→1 の代わりに𝑅ℓ,𝐹 (which is smaller) 出ている．
➢ その代わり，横幅𝑚ℓ も出てきている．
➢ 重み行列がスパースではない状況では，こちらの方がタイト．

[B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro. A PAC-Bayesian approach to spectrallynormalized margin bounds for neural networks. ICLR2018.]• Golowich et al. (2018)➢ 完全にFrobeniusノルムだけで特徴づけられている．
➢ 横幅が出てこない．
[N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. COLT2018, pp. 297–299.]

批判
ノルム型バウンドは大きすぎる．

[Nagarajan and Kolter: Uniform convergence may be unable to explain generalization in deep learning.
NeurIPS2019]

実験結果：訓練データサイズが増えるほどバウンドが大きくなる.
• これはリプシッツ定数 (ς𝐿ℓ=1 𝑊ℓ 2 = ς𝐿ℓ=1 𝑅ℓ,2 ) が大きくなることによる．
• この量はよりデータ依存な量に置換できる (Wei&Ma (2019), Arora et al.
(2018))．→ かなりタイトになる．

100

データ依存なリプシッツ定数𝑥𝜙(𝑥)𝜅: 「データ依存な」リプシッツ連続性:
𝜙 𝑥 − 𝜙(𝑥′) ≤ 𝜅 𝑥 − 𝑥′for any training data point 𝑥 and its neighborhood point 𝑥′.

(informal)[Wei and Ma: Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz
Augmentation. NeurIPS 2019]➢ このバウンドは先ほどのバウンドよりかなりタイトになる．

101

圧縮型バウンド•中間層の分散共分散行列の固有値分布•中間層の重み行列の特異値分布が速く減衰するなら圧縮しやすい．
分散共分散行列の固有値

重み行列の特異値

すぐ減衰

102

[実験的観察] 実際に学習した
ネットワークは圧縮しやすい．
元サイズ

圧縮可能
サイズ

すぐ減衰
大

分散共分散行列も重み行列も特異値が速く減衰→小さい統計的自由度

小

元のサイズ

(AIC, Mallows’ Cp)

実質的自由度カーネル法の理論(次ページに詳細)(そもそもカーネルは無限次元モデル)[Suzuki: Fast generalization error bound of deep learning from a kernel perspective. AISTATS2018][Li, Sun, Liu, Suzuki and Huang: Understanding of Generalization in Deep Learning via Tensor Methods. AISTATS2020][Suzuki, Abe, Nishimura: Compression based bound for non-compressed network: unified generalization error analysis oflarge compressible deep neural network, ICLR2020][Suzuki et al.: Spectral pruning: Compressing deep neural networks via spectral analysis and its generalization error.
IJCAI-PRICAI 2020]

中間層の実質的自由度

103

参考

𝐹ℓ 𝑥 ∈ ℝ𝑚ℓ : 中間層の特徴量 (𝑚ℓ 次元)(𝐼 = {2,3})

𝐹ℓ,𝐼 𝑥 ∈ ℝ|𝐼| : 部分ベクトル𝐹ℓ,𝐼

対応する共分散行列: Σℓ ≔ 𝔼[𝐹ℓ 𝐹ℓ⊤ ]

固有値

(ℓ)
その固有値: 𝜇𝑗 (𝑗 = 1, … , 𝑚ℓ )𝑚ℓ#𝑁ℓ (𝜆)

𝜆

統計的自由度:定理 (Bach, 2017)

任意の𝜆 > 0に対して，𝑚ℓ# = Ω(𝑁ℓ 𝜆 log(𝑁ℓ (𝜆)))個の特徴量の集合𝐼መℓ ⊂ 𝑚ℓ ( 𝐼መℓ = 𝑚ℓ# )が存在して，(𝐼መℓ に対応した部分ベクトル)

つまり，中間層を大体𝑚ℓ# 個の特徴量で代替できる．

分散共分散行列と重み行列の低ランク性

104• 近似的に低ランクな重み行列と分散共分散行列:➢

特異値が早く減衰➢+ Other boundedness condition.

定理 (Suzuki, Abe, Nishimura, ICLR2020)

where

.

VC-次元によるバウンドより大きく改善:
横幅の二乗

BigNAS105[Yu et al.: BigNAS: Scaling Up Neural Architecture Search with Big Single-Stage Models. ECCV2020](理論と関係あるNAS手法)• 学習後のネットワークが圧縮できるように学習• 大きなネットワークから小さなネットワークを生成できる• EfficientNetを上回る効率性を実現

圧縮できるように学習するとスクラッチ学習より性能が向上することもある．

106Overparametrizeされたネットワークの統計学

Double-descent (二重降下)𝑛 ≫ 𝑑: 普通の設定

107

𝑑 ≫ 𝑛: 過剰パラメータ化の設定[Belkin et al.: Reconciling modern machine learning practice and the bias-variance trade-off. 2018]• モデルがある複雑度 (サンプルサイズ) を超えた後，第二の降下が起きる．
• モデルサイズがデータより多いと推定量のバリアンスがむしろ減る．
※設定によるので注意が必要．

実際の例
Principal component regression

Sample size = # of features(いくつの主成分を用いたか)Populationの分散共分散を知っているとして，その主成分を利用

108

2-layer neural network

Sample size = # of features(いくつのニューロンを用いたか)[Xu and Hsu: On the number of variables to use in principal component regression. NeurIPS2019.][Mei and Montanari. "The generalization error of random features regression: Precise asymptotics and double descentcurve." arXiv preprint arXiv:1908.05355 (2019)]

典型的なアプローチ (抜粋)• ランダム行列理論➢ 𝑑/𝑛 → 𝛾 > 0という漸近的設定で，厳密なリスクの導出➢ Marchenko–Pastur則， Stieltjes変換◼
◼
◼

Dobriban&Wager: High-dimensional asymptotics of prediction: Ridge regression and classification. The
Annals of Statistics, 46(1):247–279, 2018.
Hastie et al.: Surprises in High-Dimensional Ridgeless Least Squares Interpolation, arXiv:1903.08560.
Song&Montanari. The generalization error of random features regression: Precise asymptotics anddouble descent curve. Communications on Pure and Applied Mathematics. arXiv:1908.05355 (2019).

• 集中不等式による評価➢ 有限サンプルサイズにおける予測誤差の上界評価 (𝑛 < ∞)➢ 収束レートが評価できる. (𝑛 → ∞を取る前の振る舞いを評価)◼
◼
◼

Belkin, Rakhlin&Tsybakov: Does data interpolation contradict statistical optimality? AISTATS2019.
Bartlett, Long, Lugosi&Tsigler: Benign Overfitting in Linear Regression. PNAS, 117(48):30063-30070, 2020.
Liang&Rakhlin: Just interpolate: Kernel “Ridgeless” regression can generalize. The Annals of Statistics,
48(3):1329–1347, 2020.

• CGMT (Convex Gaussian min-max Theorem)◼
◼

Thrampoulidis, Oymak & Hassibi: Regularized linear regression: A precise analysis of the estimation error. COLT2015.
Thrampoulidis, Abbasi & Hassibi: Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions
on Information Theory, vol. 64, no. 8, pp. 5592–5628, 2018.

109

直感

110

[Belkin, Rakhlin&Tsybakov: Does data interpolation contradict statistical optimality? AISTATS2019]• 過剰パラメータ化されたモデルは “スパイク” 成分を持つ．
• スパイク成分がノイズを説明．
• 大まかな関数形はモデルの主成分が説明．
d-次元空間True func.

訓練データ 𝑥𝑖 (𝑖 = 1, … , 𝑛)•••𝑥 (テスト時の入力)「スパイク成分」とはほぼ直交．
直交するには高次元性が必要．
高次元空間で2つのランダムベクトルはほぼ
直交．

悪性過学習
(モデルの説明力が中途半端なので，無理してノイズも説明)

線形モデル: 分散共分散行列での直感

111

Eigenvalues of Σ𝑋 (spectrum)
無情報な部分は小さい方が良い (真のシグナルの情報は取り出したい)．
一方で，小さすぎるとノイズを説明できない．

情報のある部分:
真のシグナルを説明

無情報な部分:ノイズを説明※サンプルサイズに応じてどこから無情報になるかは変わる．あくまで「そのサンプルサイズの解像度では無情報に見える」ということ．

シグナル/ノイズ分解

Signal part

Noisy part112

問題設定: 補間推定量
overparameterization• 最小ノルム補間推定量 (Minimum-norm interpolator):
過学習しているものの中で一番単純な推定量: interpolation• 予測誤差 (predictive risk, excess risk):

Ridge regression113一様バウンドではダメ

114[Yang, Bai, Mei: Exact Gap between Generalization Error and Uniform Convergence in Random
Feature Models. ICML2021.][Bartlett&Long, JMLR, 22(204):1−15, 2021]も参照

𝛼 = 1.5
一様バウンド1
一様バウンド2最小ノルム解のリスク

以下の量の𝑛, 𝑁, 𝑑 → ∞の極限を取る．ただし，𝑁Τ𝑑 → ∞, 𝑛Τ𝑑 → 𝜓2 ．
一様バウンド1 (Aに最小ノルム解のノルムx𝛼を代入)

経験誤差=0とは限らない解の中で一様バウンドを取る．

一様バウンド2 (Aに最小ノルム解のノルムx𝛼を代入)

経験誤差=0の中で一様バウンドを取る．𝛼 > 1の時は最小ノルム解以外も含まれる．

ランダム特徴モデル
N:特徴数, d:入力の次元, n:サンプルサイズ

115

ランダム行列のアプローチ

ランダム行列理論による漸近解析•

116

Hastie et al.: Surprises in High-Dimensional Ridgeless Least Squares Interpolation, Ann.
Statist. 50(2): 949--986.

: 最小ノルム補間推定量

proportional limit 𝑛, 𝑑 → ∞, 𝑑Τ𝑛 → 𝛾における漸近リスク

Theorem(proportional limit)𝑛, 𝑑 → ∞かつ 𝑑ൗ𝑛 → 𝛾 ∈ 0, ∞の極限で期待予測誤差は以下の値に概収束する:

Bias

Variance

Numerical Experiment

117

117

Bias = ||𝛽∗ ||2 , Variance = 0.
※ここでは𝛽መ = 0である．これをもって「推定している」とは言いにくいので注意．

(𝑑ൗ𝑛)

Bias

Variance前処理付き勾配法

118

Amari, Ba, Grosse, Li, Nitanda, Suzuki, Wu, Xu: When Does Preconditioning Help or Hurt Generalization? ICLR2021.

𝑑 ≫ 𝑛: overparameterized regime(interpolation)

Q: 𝑃によって予測性能がどのように影響受けるか？

Preconditioned Gradient Descent

𝑃 = 𝐼: Gradient descent (GD)𝑃 = Σ𝑥−1 : Natural Gradient descent (NGD)(真の分布で期待値取ったFisher情報行列)

最適な前処理行列

119

Bias-variance分解定理 (informal)[Amari, Ba, Grosse, Li, Nitanda, Suzuki, Wu, Xu: When Does Preconditioning Help or
Hurt Generalization? ICLR2021]

𝑑Τ𝑛 → 𝛾 > 1 (𝑛 → ∞)の極限における予測誤差の漸近値を厳密に導出

1. バリアンス:(Fisher情報行列) がバリアンスを最小化．
NGDがバリアンスの意味で最適．
2. バイアス:
No free-lunch: 事前に最適なPは決定できない:(dが増えるほどバリアンスが減る)• 真が等方的分布 Σ𝛽∗ = 𝐼に従っていればGDが良い.
• 真が非等方的分布Σ𝛽∗ = Σ𝑥−1 に従っていればNGDが良い．
(ベイズの設定: 𝛽 ∗ の実現値に関する予測誤差の期待値を比較 E 𝛽∗ 𝛽∗T = Σ𝛽∗ )GDとNGDの中間が良い

より詳細な結果(A2) Σ𝑋𝑃 : = 𝑃1/2 Σ𝑃1/2 のスペクトル分布が𝐻𝑋𝑃 に弱収束すると仮定.
• 𝒎(𝒛) を自己整合条件を満たす関数とする:→ 𝑛1 𝑋𝑃𝑋 ⊤のスペクトルの漸近分布を表現.

1. バリアンス:(A3) 𝑃とΣが同じ固有ベクトル𝑈を共有．
2. バイアス:

ただし，(𝑒𝑥 , 𝑒𝜃 , 𝑒𝑥𝑝 )は Σ, Σ𝑋𝑃 , diag(𝑈 ⊤ Σ𝛽∗ 𝑈)の固有値で 𝑣𝑥 , 𝑣𝜃 , 𝑣𝑥𝑝 に弱収束す
るものとする.

120

Experiments
Bias:
NGD

GD
GD

Bias/Variance trade-off:

NGD

121

122

第3部
深層学習の最適化-非凸性の影響-深層学習の“学習”123

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

𝑊: パラメータ

𝑖番目のデータで正解していれば小さく，間違っていれば大きく損失関数：データへの当てはまり度合い

損失関数最小化(Wは数十億次元)
通常，確率的勾配降下法で最適化

最適値

勾配降下法−𝛻𝑊 𝐿(𝑊 𝑡−1 )𝑊 𝑡−1

𝑊 𝑡 = 𝑊 𝑡−1 − 𝜂𝛻𝑊 𝐿(𝑊 𝑡−1 )

124

問題点

125

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

深層学習の損失関数?

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

局所最適解

大域的最適解

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

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

局所最適性
深層学習の目的関数は非凸
局所的最適解
大域的最適解• 線形深層NNの局所的最適解は全て大域的最適解：
Kawaguchi, 2016; Lu&Kawaguchi, 2017.

※ただし対象は線形NNのみ．
→ 臨界点が大域的最適解であることの条件も出されている(Yun, Sra&Jadbabaie, 2018)• 低ランク行列補完の局所的最適解は全て大域的最適解：
Ge, Lee&Ma, 2016; Bhojanapalli, Neyshabur&Srebro, 2016.

126

Loss landscape127• 横幅の広いNNの訓練誤差には孤立した局所最適解がない．（局所最適解は大域的最適解とつながっている） ※とはいえ，勾配法で大域的最適解に到達可能かは別問題．
定理

𝑛個の訓練データ 𝑥𝑖 , 𝑦𝑖 𝑛𝑖=1 が与えられているとする．損失関数ℓは凸関数とする．
任意の連続な活性化関数について，横幅がデータサイズより広い⊤（𝑀 ≥ 𝑛）二層NN𝑓 𝑎,𝑊 (𝑥) = σ𝑀
𝑚=1 𝑎𝑚 𝜂(𝑤𝑚 𝑥)に対する訓練誤差
𝐿෠ 𝑎, 𝑊 = 𝑛1 σ𝑛𝑖=1 ℓ(𝑦𝑖 , 𝑓 𝑎,𝑊 (𝑥𝑖 ))の任意のレベルセットの弧状連結
成分は大域的最適解を含む．言い換えると，任意の局所最適解は大域的最適解である．

[Venturi, Bandeira, Bruna: Spurious Valleys in One-hidden-layer Neural Network Optimization Landscape
JMLR, 20:1-34, 2019.]

こうはならない(つながっていない)

こうなるオーバーパラメトライゼーション
横幅が広いと局所最適解が大域的最適解になる．
狭い横幅

…
0
広い横幅

自由度が高いので，目的関数を減少させる方向が見つけやすい．

0• 二種類の解析手法➢ Neural Tangent Kernel (NTK)➢ Mean-field analysis (平均場解析)

128

二つのスケーリング

129• Neural Tangent Kernelのregime (lazy learning )[Jacot+ 2018][Du+ 2019][Arora+ 2019]➢ 𝑎𝑗 = O(1/ 𝑀)(Xavier initialization/He initialization)• 平均場解析の設定 (mean field)[Nitanda & Suzuki (2017), Chizat & Bach➢ 𝑎𝑗 = Ο(1/𝑀)(2018), Mei, Montanari, & Nguyen (2018)]

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

変数のスケールと特徴学習

130

NTK: Large scale initialization → features are (almost) freezed.

二層NNにおける一層目のパラメータの軌跡[Ba et al., 2022]

Mean field: Small scale initialization → features need to move significantly.

(参考) 初期化スケールと学習率の取り方

131• ABCパラメトライゼーション [Yang&Hu, 2021]
𝑛:横幅(1) パラメータ設定

A(𝑤 𝑙 が学習パラメータ)(2) 初期化法(3) 学習率のスケール

BC(適切なスケーリング)[Yang&Hu: Tensor Programs IV: Feature Learning in Infinite-Width Neural Networks. ICML2021.]

132[Yang et al.:Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer. arXiv:2203.03466]

小さいモデルのハイパーパラメータを大きなモデルに転用できる．
GPTの学習に利用．数億円の学習コストを抑えられる．

Neural Tangent Kernel

133[Jacot, Gabriel, & Hongler (2019)]

テイラー展開重要

特徴写像とみなせる(線形モデル)

初期値のスケールが大きいので，初期値周りの線形近似でデータにフィットできてしまう．
カーネル関数は特徴写像の内積

Neural Tangent Kernel

各ニューロンの微分で得られる
特徴写像の内積を全ニューロンで平均最適化のダイナミクスや汎化性能などは，
NTKをカーネル関数とするカーネル法としてとらえられる．

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

1(+, − is generated evenly)𝑀• 𝑤𝑗 ∼ 𝑁(0, 𝐼)
Theorem [Arora et al., 2019]𝑀 = Ω(𝑛2 log(𝑛)/𝜆min )とすれば, 勾配法によって大域的最適解へ線形収束し，その汎化誤差は 𝒚⊤ 𝐾𝑊(0) −1 𝒚ൗ𝑛 で 抑えられる．
exp(−𝑐𝑡)で収束

See also[Du et al., 2018; Allen-Zhu, Li & Song, 2018; Li & Liang, 2018]• 訓練誤差0の解に線形収束する.
• 汎化誤差も一応抑えられている.
• データに完全にフィットさせてしまうので過学習の可能性あり.
• Early stoppingや正則化を入れれば過学習を防げる．(次ページ)

NTKの収束定理の導出

135

連続時間ダイナミクスを考える．
• 𝒂𝒋 は固定• 𝒘𝒋 を学習

Model：[Jacot, Gabriel&Hongler, NeurIPS2018](Gradient descent, GD)

(勾配法に
よる更新)

O(1/𝑀)：
特徴写像の内積の平均
residual(関数勾配)𝑘𝑊 (𝑥, 𝑥𝑖 )Neural Tangent Kernel

目的関数の減少速度

参考

136

(𝐾𝑊 )𝑖,𝑗(𝜆min : グラム行列の最小固有値)

Fact[Du et al., 2018; Allen-Zhu, Li & Song, 2018]• ランダム初期化しておけば, 𝐾𝑊 (0) ≻ 𝜖𝐼 が高確率で成立．
• 最適化の最中に最小固有値は正のまま (≥ 𝜖/2).
線形収束 (exp(−𝝀min 𝒕))

Spectral bias
• 最適化の観点からはoverparameterizationは有用に見える.
• 汎化誤差はどうであろうか?
NTKの固有値分布𝑛 × 𝑛グラム行列の最小固有値 (𝜆min )𝑛• グラム行列の最小固有値は小さい (1/poly(𝑛)).
• 固有値の減少レートは多項式オーダー (理論+実験).
→ Spectral bias: 汎化の意味では好ましい.

137

Kernelによる平滑化という視点

138• Frechet 微分 in 𝐿2 (𝑃𝑛 ): 𝛻𝑓 𝐿෠ (𝑓)• 平滑化積分作用素:• NTKにおける勾配は関数勾配を平滑化したもの:
勾配を平滑化！

(導出は前のページ参照「NTKの収束定理の導出」)

𝑘𝑊 が高周波成分に小さな固有値を持てば，𝑇𝑘𝑊 は平滑化作用素として働く→ 帰納的バイアス (inductive bias).

NTK regimeでのSGD
モデル:

目的関数:

(We train both of first and second layers)

期待損失

初期値からのずれ

𝑌 = 𝑓 ∗ 𝑋 + 𝜖 (ノイズありの観測)
Averaged Stochastic Gradient Descent

𝑗

参考

139

NTKにおける余剰誤差の速い収束

140[Nitanda&Suzuki: Fast Convergence Rates of Averaged Stochastic Gradient Descent
under Neural Tangent Kernel Regime, 2020.]

仮定：真の関数がNTKの作るRKHSに入っているとする．

NTK設定で適切な正則化を入れたSGDは“速い学習レート”を達成できる．
→ NTKによるsmoothingのおかげ.
Thm (速い収束レート)
𝑓𝑇 : 𝑇回更新後の解𝑀 → ∞で0に収束する項
2𝑟𝛽−2𝑟𝛽+1NTKの固有値の減衰レート

NTKのスペクトル𝑗 −𝛽
速い学習レート(𝑂(1/ 𝑇)より速い)→𝑇
はミニマックス最適レート.
(各種パラメータの意味は次ページに詳細)

仮定

参考

2層NNのNTK:

横幅無限における積分作用素:
population

スペクトル分解:,仮定• 𝑓 ∗ (𝑥) = E[𝑌|𝑋 = 𝑥] が次のように書ける:

𝑇𝑘𝑟∞ ℎ = 𝑓 ∗真の関数の平滑性

for ℎ ∈ 𝐿2 (𝑃𝑋 ), and 𝑟 ∈ [1/2,1].

• 固有値減衰条件:
𝜇𝑗 = O 𝑗 −𝛽 .

カーネル関数の“複雑さ”

カーネルリッジ回帰の解析における標準的な仮定; see, e.g., Dieuleveut et al.
(2016); Caponnetto and De Vito (2007) (rの条件はやや強め).

141

142

NTKの固有値固有関数分解
𝜙𝑚 ∞𝑚=1 : 固有関数. 𝐿2 (𝑃𝑋 )内の正規直交基底．

NTKの固有値分布

実際のNTKの固有値は多項式オーダーで減衰する．
[Bietti&Mairal (2019); Cao et al. (2019);
Ronen et al. (2019)]

低周波成分

低周波成分が最初に補足される．
その後，高周波成分が徐々に補
足される．

高周波成分

NTKの陰的正則化

参考

143

固有値減少の数値実験による検証

High frequency components

Low frequency components
理論
ReLU, 𝑎, 𝑤 ∼ 𝑁 0, 𝐼 :• 𝑌𝑘,𝑗 : spherical harmonics functions
with degree 𝑘.
• 𝜇𝑘 ∼ 𝑘 −𝑑 .
•.

See Cho&Saul (2009), Xie,Liang&Song (2017), Back (2017), Bietti&Marial (2019) for inductive bias.

二層NNのNTKはmultiple kernel 参考

144

二層目のNTK

仮定: 𝑓 ∗ is in
RKHS w.r.t. NTK
for the 2nd layer.

一層目のNTK

一層目と二層目のカーネルの和：multiple kernel

RKHS w.r.t. NTK
for the 1st layer.

RKHS w.r.t. NTK
for the both layer.

• 二層NNのNTKによる学習は，multiple kernel learningの効果がある．
• 多層NNを用いることはモデルmisspecificationに対してよりロバストになる．

Beyond kernel

145

問題点：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 of Wide
Neural Networks. ICLR2020.

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

146

2層NNの特徴学習のダイナミクス解析

147• (NTKを超えて)勾配法によって特徴量がどう学習
されるか？
→ 色々な研究がある．
• NTK近似が成り立たない領域では非線形性が強くなり，最適化のダイナミクスの解析が難しくなる．
• 最近では妥協点として，勾配法の最初の段階（1ス
テップ or 少数ステップ）でどのような特徴量が獲得できるかを解析する研究が複数なされている．
• 少数ステップで得られる情報は限られているが，それでも予測性能の改善が示せる．
• 今後はより非線形性の強い特徴量学習のダイナミクスの解析が進むと思われる．
※ 計算量をあまり気にしなければ勾配ランジュバン動力学を用いた学習の解析は完全に非線形な特徴学習をとらえられる．

勾配法とKernel alignment

148

問：勾配法で𝑊を更新することで，データに合った特徴量を獲得できるか？
答：NTK近似が成り立つ領域からはみ出るくらい大きなステップサイズを用いれば，一回の更新で意味のある特徴量の方向を得ることができる．
→ カーネルAlignment，特徴量学習．

𝒏, 𝒅, 𝑵 → ∞の極限を考え，勾配法１回の更新後の予測誤差を評価してみる．
➢ 𝜂 = 𝑁のように大きな更新を用いると，任意の線形モ
デルによるリッジ回帰を優越する．
➢ 𝜂 = 1では最適なリッジ回帰を優越しないが初期値𝑊は優越．
➢ 𝜂 = 𝑜(1)では初期値𝑊と同じ予測誤差 (NTK-regime)．
Gaussian equivalence property + Random matrix theory→ Exact risk evaluation.

点: 実測値
実線: 理論値

勾配法とKernel alignment

149

関連研究

150

The first few step of GD with large learning rate canextract informative features.

• Staircase function [Abbe et al., NeurIPS2021; Abbe et al., arXiv2202.08658]
Small number of gradient descent can extract
nonlinear features to estimate “staircase” function.
The trained features for GD can outperform random
feature model.

• Benign overfitting with feature learning[Cao et al., arXiv:2202.06526; Frei et al., arXiv:2202.05928]

Gradient descent in two-layer NN can yield benign
overfitting and achieves almost the Bayes error in binaryclassification.

問題設定

151

観測モデル:

where 𝑥𝑖 ∼ 𝑁 0, 𝐼 , 𝜖𝑖 ∼ 𝑁(0,1), and 𝑥𝑖 ∈ 𝐑𝑑 .
➢ 平均場スケールの2-層NNを学習：

平均場レジーム O(1/𝑁)(∵ 𝑎𝑖 = 𝑂𝑝 (1/ 𝑁))

where 𝑎𝑖 ∼ 𝑁(0,1/𝑁) and 𝑊𝑖𝑗 ∼ 𝑁(0,1/𝑑).
var

経験リスク:

var

予測リスク:

問: 勾配法による特徴学習で予測誤差を改善できるか?
真の関数がシングルインデックスモデルで書ける状況を解析:

勾配法

152

• 一層目のパラメータ𝑊の更新:✓ 二層目のパラメータ𝑎は最適化の途中で固定．
✓ あくまで𝑊の特徴学習のダイナミクスに注目.

1. 特に，勾配法の“１ステップ更新“ に注目:
2. その後，二層目はリッジ回帰で推定:
𝑥෤𝑖 , 𝑦෤𝑖 𝑛𝑖=1 : i.i.d. copyof 𝑥𝑖 , 𝑦𝑖 𝑛𝑖=1

➢ 𝑊1 (1回更新後) は，初期値𝑊0 より真の関数𝑓 ∗ に「相関している」と考えらえれる．→より良い予測誤差．

仮定

153

1. Proportional limit: 𝑛, 𝑑, 𝑁 → ∞ and 𝑛Τ𝑑 → 𝜓1 , 𝑁Τ𝑑 → 𝜓2 . e.g., tanh
2. 活性化関数の性質:
1. 𝜎 は有界，max{ 𝜎 ′ ∞ , 𝜎 ′′ ∞ , 𝜎 ′′′ ∞ } ≤ 𝐶 < ∞.
2. E 𝜎 𝑧 = 0, E 𝑧𝜎 𝑧 ≠ 0 for 𝑧 ∼ 𝑁(0,1). (ちょっと強い条件)
3. 教師の条件: 𝑓 ∗ はリプシッツ連続で 𝑓 ∗ 𝐿2(𝑃𝑋 ) = Θ𝑑 (1).
𝑊の勾配法における軌跡 (𝑑 = 2).
𝑓 ∗ は二つのReLUニューロンの和.

1. 平均場設定では，各ニューロンは初期値から多きく動いて目標となる真の関数の方
向 (黒い破線; 二つのニューロン) を向く.
2. NTKのスケールでは，一層目のパラメー
タはほとんど動かず特徴学習ができていな
い．

See also Akiyama&Suzuki (2021), Chizat (2019).

ランダム特徴量

154

ランダム特徴量 (特徴量の学習無し)• Conjugate kernel at initialization:• NTK (Neural tangent kernel):

正確な漸近解析がかなり研究されている (e.g., [Louart, Liao,and Couillet, 2018; Mei andMontanari, 2019])

RF ∈ {CK,NTK}学習されたカーネル (１ステップGD):
よくわかってない𝑥෤𝑖 , 𝑦෤𝑖 𝑛𝑖=1 : i.i.d. copyof 𝑥𝑖 , 𝑦𝑖 𝑛𝑖=1

RFの限界155[El Karoui (2010); Ghorbani et al. (2019); Hu and Lu (2020); ...]

定理 (RFの予測誤差の下限)

ただし，𝑃≤1 は線形関数がなす空間への𝐿2 𝑃𝑋 -空間内での射影．
Remark: 同じことが “回転不変カーネル”でもなりたつ [El Karoui (2010)].

• 高次元かつ 𝑑Τ𝑛 = 𝑂(1)の状況では，ランダム特徴量を使っている限り真の関数𝑓 ∗ の線形要素しか取り出せない.
• 𝑓 ∗ の非線形性が強ければ，精度が出せない．

(𝑛 = 𝑑 𝑘+1−𝜖 なら𝑘次多項式まで出てくる [Ghorbani et al. 2021; Mei et al. 2021])

これは，高次元設定では以下のような中心極限定理が成り立つからである:[Gaussian等価性]
後のスライドを参照

最初の勾配ステップはほぼランクが１156• 勾配𝐺𝑡 は，ランク１行列で近似できる．
⇒ 𝑊1 のスペクトル分布に「スパイク」が現れる！
(𝜎′の非線形性より，一般的には低ランクにならない．しかし高次元だと低ランクになる)(Gordon-Slepian ineq.; Hanson-Wright inequ)

定理 (勾配のランク１近似)に注意．
(活性化関数の１
次成分と2次成分)(ランク1行列)とすれば，以下を得る:

with high probability for sufficiently large 𝑛, 𝑑, 𝑁.

𝑊1 = 𝑊0 + 𝜂 × (rank one matrix).
⇒ ステップサイズ𝜂が大きいと，スパイクが支配的.

MP則
(初期解)

Spike

Alignment with the Target Function

157

𝑓 ∗ can be decomposed into first order

参考higher order

where

.

Define 𝜇ҧ ≔ lim 𝑓 ∗ 𝐿2(𝑃𝑋) , and𝑑→∞𝑛Τ → 𝜓 , 𝑁Τ → 𝜓12𝑑𝑑Theorem (Alignment to the target function)
Suppose that 𝜂 = Θ(1) and 𝜎1 (𝑊1 ) is the largest singular value of 𝑊1 and 𝑢1 isthe corresponding left singular vector, then
1/4

(large step size):

1/4(small step size):(i) 𝜃1 > 𝜓2(ii) 𝜃1 < 𝜓2

In both cases, we haveAlignment with the Target Function158

𝑓 ∗ can be decomposed into first order

参考higher order

where

.

Define 𝜇ҧ ≔ lim 𝑓 ∗ 𝐿2(𝑃𝑋) , and𝑑→∞𝑛Τ → 𝜓 , 𝑁Τ → 𝜓12𝑑𝑑Theorem (Alignment to the target function)Phasetransition
for theleading
Suppose that 𝜂 = Θ(1) and 𝜎1 (𝑊1 ) is the largest
singularvalueof 𝑊
1 and 𝑢1 isthe corresponding left singular vector, then singular value: i.e., under sufficiently
1/4(i) 𝜃1 > 𝜓2 (large step size):

1/4(ii) 𝜃1 < 𝜓2(small step size):

In both cases, we havelarge step size, the “spike” in theweight matrix aligns with the leading
term of the true function.

The “alignment” becomes more significant
as we (i) increase the step size; (ii) use
more data (i.e., larger 𝜓1 )Non-leading singular vectors are nearorthogonal to the linear part of the true
function in the high dimensional setting.

𝑾𝟏 のスペクトル分布のスパイク

159

𝑾𝟎 のスペクトル: MP則(一回の更新で変わらず)

𝑓 ∗ の第一線形成分へのalignment(特徴学習)

Gaussian Equivalence Property

160• 𝑡ステップ目のconjugate kernel :• Gaussian等価なモデル:

線形成分+ガウス雑音(非線形部分はガウス雑音になってしまう)𝑥෤𝑖 , 𝑦෤𝑖 𝑛𝑖=1 : i.i.d. copyof 𝑥𝑖 , 𝑦𝑖 𝑛𝑖=1
where F ∈ {CK, GE}.

初期解に関する解析は[Hu and Lu, 2020]

定理 (Gaussian等価性)
𝜂 = Θ(1)として，とする．すると，有界な𝑡に対する最初の𝑡ステップでは以下が成り立つ:

𝑖 の全成分が満• これは特徴量の空間における“中心極限定理”と言える．(L2正則化によって𝑎
遍なく小さくなるので)• 非線形部分はi.i.d.ガウス雑音のようにふるまう (非線形項の情報は消える).
• 小さなステップサイズで定数回勾配法で更新しても限界がある．

数値実験との整合性

161

1. GETは初期解(ランダム特徴量)だけでなく，学習したモデルでも成り立つ．
2. GETを使うことで，ランダム行列の理論から予測誤差を厳密に計算可能．
(なぜならカーネル関数が“線形化”されているので).

Solid line: GEから理論的予測.
Dots: 計算機によるシミュレーション.

𝜂 = Θ(1)を用いて学習した特徴量を用いたリッジ回帰の予測誤差より大きなステップサイズでより多くのステップを費やした方がより良い精度→ 特徴学習が予測誤差を改善している！

初期値のCKからの改善

162(𝑅𝑊 (𝜆) is the ridge regression estimator using 𝑊 for the first layer.)• 𝜂 = Θ(1) (中間的な大きさのステップサイズ):
線形な領域• 1ステップのGDは必ず精度を改善させる．
• しかし，大きく改善させることはない．なぜなら• 𝜂 = Θ( 𝑁) (大きな学習率):．
を仮定

Maximal update parameterization (𝜇P) [Yang and Hu, 2020]
として知られている．

••(モデルのズレを表す量)𝜏 ∗ = 0 if 𝜎 = 𝜎 ∗ = erf.
𝜏 ∗ ≪1 if 𝜎 = 𝜎 ∗ = tanh.
𝑛Τ → 𝜓 , 𝑁Τ → 𝜓
1
2
𝑑
𝑑

非線形領域
学習率を大きくすることで，精度を大きく改善できる(𝜏 ∗ ≪ 𝑃>1 𝑓 ∗ 2 の状況で). ※バイアス項を振りなおせば𝜏 ∗ = 0とできる．

考察
Corollary163

もし𝜎 = 𝜎 ∗ = erf なら，𝜏 ∗ = 0.
特に，𝑅𝑊1 𝜆 = Θ 𝜓1−1 = Θ 𝑑/𝑛 である．

Small step size

Large step size

Θ(𝑑/𝑛)で減少

Predictive risk of ridge regression on CK obtained by one step GD (empiricalsimulation, 𝑑 = 1024): brighter color represents larger step size scaled as 𝜂 =𝑁 𝛼 for 𝛼 ∈ [0,1/2]. We chose 𝜎 = 𝜎 ∗ = erf, 𝜓2 = 2, 𝜆 = 10−3 , and 𝜎𝜖 = 0.1.

機械学習の注意点

164

Learning = Fitting a model to the training data

Find a model that fits the data well by minimizing a loss function.

〇 Good pred.
True func.

ML is intended to obtain good prediction.
➢ Lower classification error.
➢ Better recommendation.

Black-box model

They do not findcausality but correlation.

Better prediction ≠ Better interpretability/explainability:➢ How is a particular answer produced?
➢ Is the output produced by a correct reasoning?

× Bad pred. (overfit)
True func.

Learning a Shortcut

165

ML models sometimes find a “shortcut” that lowers the training error but
yields an unreasonable decision rule.

• Medical image recognition:

Marker marked by doctors produces unintentional bias.
Marker[Winkler et al., Association
Between Surgical Skin Markings in
Dermoscopic Images andDiagnostic Performance of a
Deep Learning Convolutional
Neural Network for Melanoma
Recognition. JAMA dermatology,155(10):1135–1141, 2019]

Camera, lighting conditions,skin-colors also produce bias.

• General object recognition:
A specific object is linked tothe background color.
➢ ML model recognizes via
the BG-color.
➢ It fails if BG-color changes.
[Nanxuan Zhao, Zhirong Wu, Rynson W. H. Lau, and Stephen Lin. Distilling localization for
self-supervised representation learning. arXiv: 2004.06638, 2020]

Interpretability is necessary for high-risk stakes problems.
➢ E.g., cancer diagnosis.

Social issue: Hallucination• Hallucination

166

A confident response by an AI that does not seem tobe justified by its training data.
The situation could get worse
because it is estimated that 33–46%
of crowd workers use LLMs.
→ AI would be trained by AI
Wrong author information generated data.

[Veselovsky et al: Artificial Artificial Artificial Intelligence:
Crowd Workers Widely Use Large Language Models for Text
Production Tasks. arXiv:2306.07899]• Ethical issue
Galactica: LLM by Meta trained mainly by scientificpapers and documents. (published on 15th/Nov/2022)➢ Produced several hallucination including
vicious racist responses backed up by nonexisting references.
➢ Was closed to public in 3 days.
[Taylor et al: Galactica: A Large Language Model for Science. 2022]

Ethical issues• Gender bias in natural language processing

167
Different results fromdifferent random seeds

Semantic textual similarity (STS) taskMore biased

Are the results affected by the gender ratio of
the occupations?
➢ Random seed to fine tune the BERT model
largely affected the result.
➢ It is difficult to detect from the predictive
accuracy.
[D'Amour et al. (Google), Underspecification Presents Challenges for Credibility in Modern Machine Learning. JMLR,
23(226):1−61, 2022]• Copyright issue
Article 30-4 of the Copyright Law in Japan permits the use of a
copyrighted work for training ML models, but it does not include any
procedure for gaining permission in advance from copyright holders.
["Copyrighted Works Get Flimsy Protection from AI Under Japanese Law," The Yomiuri Shimbun, published on April 29, 2023]➢ Japanese government announced that that necessary measures will be established by summarizing
the issues such as cases in which learning of copyrighted works by AI constitutes an infringement.
「知的財産推進計画2023」

G7: Hiroshima AI process

168• Agreed to establish Hiroshima AI process.
• They are determined to work together and withothers to “advance international discussions on
inclusive artificial intelligence (AI) governanceand interoperability to achieve our common
vision and goal of trustworthy AI, in line with ourshared democratic values.”[HP of Ministry of Foreign Affairs of Japan.
https://www.mofa.go.jp/ecm/ec/page1e_000673.html][Cabinet Office report: G7 Hiroshima Summit (Session 1 (Working Lunch) "Toward an International Society of Cooperation,
Not Division and Conflict/World Economy" Summary)][内閣府資料: G7広島サミット（セッション１（ワーキング・ランチ）「分断と対立ではなく協調の国際社会へ／世界経済」概要）]

The G7 Digital and Technology Ministers' Meeting was held in Takasaki City, Gunma
Prefecture, prior to the G7 Summit, and adopted a joint statement that included thepromotion of the development of "human-centered and reliable artificial intelligence (AI).
1. Facilitation of Cross-Border Data Flows and Data Free Flow with Trust.
2. Secure and Resilient Digital Infrastructure:
1. reinforce democratic values
2. respect for human rights and fundamental
4. Innovating the Economic Society and Enhancing theEmerging Technologies.
freedoms
5. Promoting Responsible AI and AI Governance. 3. collective efforts to promote interoperability
between AI governance frameworks
6. Competition Policy on Digital Market.
4. enabling environment for AI innovation globally
3. Internet Governance.

まとめ

169

• 深層学習はなぜうまくいくのか？[世界的課題]• 数学による深層学習の原理究明➢ 「表現能力」，「汎化能力」，「最適化」

学習

スパース推定カーネル法

特徴抽出

テンソル分解深層学習の理論
Besov空間数学

関数近似理論

連続方程式 Wasserstein幾何

確率集中不等式
確率過程

理論により深層学習を“謎の技術”から“制御可能な技術”へ
深層学習を超える方法論の構築へ170

ノイズあり勾配法と大域的最適性(参考資料：最終日に説明予定)

Sharp minima vs flat minima

171

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)

ノイズによる平滑化効果

172

smoothing[Kleinberg, Li, and Yuan, ICML2018]

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

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

関連研究: Graduated optimization• Graduated non-convexity
Blake and Zisserman: Visual reconstruction, volume 2. MIT press Cambridge, 1987.

• Gaussian kernelとの畳み込み
Z. Wu. The effective energy transformation scheme as a special
continuation approach to global optimization with application tomolecular conformation. SIAM Journal on Optimization, 6(3):748-768,
1996.

• Graduated optimization
Hazan, Levy, and Shalev-Shwartz: On graduated optimization forstochastic non-convex problems. International conference on
machine learning, pp. 1833-1841, 2016.

𝜎-nice性の導入．多項式オーダーでの収束．

𝐿෠ 𝛿 𝑥 = E𝑢∼𝑈(B(R𝑑)) [𝐿(𝑥 + 𝛿𝑢)]Survey:Mobahi and Fisher III. On the link between gaussian homotopy
continuation and convex envelopes. Energy Minimization
Methods in Computer Vision and Pattern Recognition, pp. 43-56,
2015.

173

GLD/SGLD

174• 確率的勾配ランジュバン動力学

Stochastic Gradient Langevin Dynamics (SGLD)(非凸)
𝛽: 逆温度パラメータ(勾配ランジュバン動力学)
定常分布：
時間離散化

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

GLD:(Euler-Maruyama scheme)

SGLD:

確率的勾配

175

Gaussian noise

Gradient descent定常分布

適当な条件のもとGLDの定常分布は以下で与えられる:➢ 𝛽が大きければ，定常分布は最適解周りに集中する．
➢ 定常分布からのサンプリングにも使える (というかこっちが本来の目的)．

176

対数ソボレフ不等式と幾何的エルゴード性

177

定常分布

例：
• 二次関数+有界関数• Weak Morse型関数

対数ソボレフ不等式 (𝝅∞ の性質):
任意の(𝜋∞ に対して絶対連続な)確率分布

に対し，

KL-div

幾何的エルゴード性

Fisher-div

𝜌𝑡 : 𝑋𝑡 の周辺分布

定常分布へKL-divergenceの意味で指数オーダーの収束[Bakry, Gentil, and Ledoux: Analysis and Geometry of Markov Diffusion Operators. Springer, 2014. Th. 5.2.1]

対数ソボレフ不等式の十分条件

178

Bounded perturbation lemma:[R. Holley and D. Stroock. Logarithmic sobolev inequalities and stochastic Ising models. Journal of statistical physics, 46(56):1159–1194, 1987.]

強凸な場合:

𝐿(𝑥) が𝜇-強凸 ⇒[Bakry and Émery, 1985]• 散逸的 (dissipative):• 平滑性:[Raginsky, Rakhlin and Telgarsky, 2017]離散時間ダイナミクスの収束レート

179

過程: 𝐿 は𝑀-平滑:定理[Vempala and Wibisono, 2019]

定理 (informal)
散逸性と平滑性の条件のもと (and other technical condition),

幾何的エルゴード性

時間離散化の誤差

where 𝑐, 𝑐𝐶𝐿𝑆,𝛽,𝑑 > 0 are constants.

𝐸𝜋∞ 𝐿 𝑋

− 𝐿(𝑋 ∗ )定常分布が最適解まわりにどれだけ集中しているか[Raginsky, Rakhlin and Telgarsky, 2017; Xu, Chen, Zou, and Gu, 2018; Erdogdu, Mackey and Shamir, 2018]• 逆温度パラメータ𝛽が十分大きければ，目的関数が非凸でも最適解の近くに到達できる．
• ただし，一般には対数ソボレフ不等式は𝛽に指数的に依存することに注意．
（そうでない場合もある：強凸目的関数，Weak Morse関数）

References

180• 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
➢ Log-Sobolev inequality: Vempala and Wibisono, 2019.

• Infinite dimensional Langevin dynamics:➢ Continuous time:• Existence & Uniqueness of invariant measure: Da Prato andZabczyk,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.

181

GLDによるNNの最適化

二層NNの最適化

182

観測モデル:

where.

教師生徒設定 with ReLU活性化関数:
Teacher

Student (overparameterization)• 教師と生徒で同じサイズとする. (おそらく緩和可能)• 生徒は教師を多項式時間で推定できるか？

勾配ランジュバン動力学による最適化

183

L2-正則化あり経験損失関数:

L2-正則化ReLUではL2-正則化はスパース正則化 (L1-正則化) でもある．
二段階最適化(1) 探索フェーズ: GLD

ガウスノイズ(2) 収束フェーズ: ノイズ無し・正則化なしの勾配法

収束の様子

184

探索フェーズ:最適解近傍への収束

ニューロン２ニューロン１

収束フェーズ:ニューロン３

目的関数値

最適解まわりでは大体強凸→ 普通の勾配法で線形収束
二段階の収束フェーズ：実験的にも観測されている (Hidden progress)

収束解析

185

[Akiyama and Suzuki: Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its
Superiority to Kernel Methods. arXiv:2205.14818]➢➢➢∘ )のm番目の特異値は𝜎𝑊 ∘ = (𝑤1∘ , … , 𝑤𝑚
min で下から抑えられる．

定理 (informal)(𝑚, 𝑑, 𝜎min 固定の元で)適当な定数時間𝐾1 が存在して，Phase 1 (大域的探索フェーズ): しばらく探索すると期待損失をある閾値以下まで減らせる (真に近くなる)

𝑅 Θ 𝐾1≤ 𝜖0

Phase 2 (収束フェーズ): 大域的最適解へ線形収束

𝑅෠0 Θ 𝑘− 𝑅෠0 Θ∗ ≤ 𝑐1 exp(−𝑐2 (𝑘 − 𝐾1 )).

数値実験：二段階の学習ダイナミクス
探索フェーズ収束フェーズ186

予測誤差の比較• 前ページのアルゴリズムで最適化して得られた解Θ𝑘• 線形推定量の予測誤差の下限:

線形推定量は次元の呪いを受ける→ 特徴量も学習することで改善

187

Related work
Non-overparameterized setting:• [Li & Yuan, 2017] showed global convergence under 𝑀 = 𝑚
and a special network structure (ResNet like structure).
• [Zhong et al., 2017] showed local convergence under 𝑀 = 𝑚,i.e., they showed convergence when the initial solution isclose to the true parameter.
Overparameterized setting:• [Li, Ma & Zhang, 2020] showed global convergence of GD foran overparameterized setting 𝑀 > 𝑚.

True network

where 𝑄 is a small constant.

➢ Tensor decomposition technique is used.
➢ The true network has a special structure.
➢ The convergence is not exactly shown (it converges as 𝑑 → ∞).

• [Chizat, 2019]: Convergence to sparse solution with sparse reg.
➢ BLASSO [De Castro & Gamboa, 2012]

2-homogeneous activation + NDSC condition
ReLU

Guarantee ← [Akiyama&Suzuki, 2021]

188

189

2層NNの学習・粒子勾配法(参考資料：最終日に説明予定)

190• 前のスライドでは横幅が小さいNNの最適化を考えた．
• 実際は過剰パラメータ化した横幅が広いNNを使うことが多い (表現力を上げるため)．
• 先のGLDの収束レートには次元が現れるので，そのままでは使えない．
(実際，次元に指数関数的に依存する)→ 平均場ランジュバン動力学

2層NNのGLDによる最適化

191

例:

ニューロンが沢山あると普通のGLDの理論が適用できない．
しかし，平均場ランジュバン動力学の理論により理論保証ができる．
(逆にニューロン数無限大の極限を考えると理論保証可能になる)多粒子化（平均場）：
𝑀→∞…

定理 (Hu, Ren, Šiška, and Szpruch, 2021; Mei, Montanari, and Nguye, 2018)

𝑀 → ∞, 𝑡 → ∞の極限で粒子𝜃𝑗 の分布𝜇𝑡 は以下の分布に収束:
エントロピー

重要：分布𝝁に対しては凸関数！(if 損失が凸)MF-LDの収束
目的関数

192

（損失関数+正則化）

平均場ランジュバン動力学:(わかりにくいが単純に各ニューロンを勾配法で動かして微小ノイズを加えていることに対応)

近接点更新解:(c.f., Mirror descent, exponentiated gradient)
損失を線形化して得られる解定理 (Entropy sandwich)[Nitanda, Wu, Suzuki (AISTATS2022)][Chizat (2022)]

𝑝𝜇𝑡 が一様に対数ソボレフ不等式 (定数𝛼)を満たすとすると，（線形収束！）
ただし，

応用例• 平均場二層ニューラルネットワーク

𝑀→∞

Example:

目的関数
𝜇で微分

• MMD最小化によるノンパラメトリック密度推定➢
𝑘: 正定値カーネル➢: 経験分布 (訓練データ)• ベイズ事後分布の変分推論

193➢

難しさ: McKean-Vlasov過程

194• 粒子間相互作用のある確率微分方程式はMcKean-Vlasov過程として知られている． (McKean, Kac,…, 60年代)• 離散時間・有限粒子での収束を示す際にはPropagation of chaosの評価が難しい．(粒子を増やすことでそれぞれがあたかも独立に振る舞う現象)

Propagation of chaos

一つの粒子の微小な変化が他の粒子に伝播して増幅される可能性がある．

𝑡=1

𝑡=2

𝑡=3

𝑡=4

研究の流れ平均場NNの線形収束
連続時間・無限粒子[Nitanda, Wu, Suzuki(AISTATS2022)][Chizat (2022)]

195

時間・空間離散化：「二重ループの手法」• PDA法 [Nitanda, Wu, Suzuki: NeurIPS2021]• P-SDCA法 [Oko, Suzuki, Wu, Nitanda:
ICLR2022]• 無限次元拡張 [Nishikawa, Suzuki, Nitanda:
NeurIPS2022]

難しい：Propagation of chaos(McKean, Kac,…, 60年代より)
空間離散化・連続時間:
Uniform-in-time propagation of chaos- Super対数Sobolev不等式[Suzuki, Nitanda, Wu (ICLR2023)]- Leave-one-out型評価[Chen, Ren, Wang (arXiv2022)]

時間・空間離散化・確率的勾配：「一重ループの手法」

Suzuki, Wu, Nitanda(arXiv:2306.07221)

離散時間・有限横幅の手法

196

粒子双対平均化法

粒子確率的双対座標上昇法(Particle Dual Averaging; PDA)(Particle Stochastic Dual Coordinate Ascent; P-SDCA)[Nitanda, Wu, Suzuki: NeurIPS2021][Oko, Suzuki, Wu, Nitanda: ICLR2022]

主問題

ഥ (𝒕) の決定に双対平均化法のルールを用いる
𝒈

解:

時間離散化

計算量解析：

ただし•双対変数の座標をランダムに選択し，その座標に関して最適化．
→確率的双対座標上昇法

計算量解析：
双対ギャップ𝝐𝑷 を達成するのに必要な外側ループ数：(GLDによる)⇒合計: 𝑶(𝝐−𝟑 )の勾配アップデートで十分．

➢

by Fenchelの双対定理

双対問題

具体形が得られる．

→ この分布からは以下の勾配ランジュバン動力学を用いてサンプリング可能:

1. 外側ループ:
2. 内側ループ:=𝑞に関する線形汎関数で近似 (勾配を用いる)
ഥ (𝒕)は基本的に勾配)(線形近似; 𝒈近似

初の多項式オーダー最適化手法➢➢

指数オーダーでの収束を達成
サンプルサイズ𝑛への依存を緩和Kernel alignment
前ページの方法で学習

一層目：
特徴抽出
カーネルalignment:

一層目で抽出された特徴量が教師信号(y)とどれだけ相関しているか？
→ 高いほど特徴量が真の関数の成分を多く含んでいる．

固有値の分布：一層目ほぼ固定

一層目も学習することで真の関数により適合した特徴量が学習できている．

197

研究の流れ平均場NNの線形収束
連続時間・無限粒子[Nitanda, Wu, Suzuki(AISTATS2022)][Chizat (2022)]

198

時間・空間離散化：「二重ループの手法」• PDA法 [Nitanda, Wu, Suzuki: NeurIPS2021]• P-SDCA法 [Oko, Suzuki, Wu, Nitanda:
ICLR2022]• 無限次元拡張 [Nishikawa, Suzuki, Nitanda:
NeurIPS2022]

難しい：Propagation of chaos(McKean, Kac,…, 60年代より)
空間離散化・連続時間:
Uniform-in-time propagation of chaos- Super対数Sobolev不等式[Suzuki, Nitanda, Wu (ICLR2023)]- Leave-one-out型評価[Chen, Ren, Wang (arXiv2022)]

時間・空間離散化・確率的勾配：「一重ループの手法」

Suzuki, Wu, Nitanda(arXiv:2306.07221)

一重ループの方法(時間離散化)

かつ

ただし(確率的勾配)(空間離散化)(𝑖)• 時間離散化: 𝑋𝑡 → 𝑋𝑘
• 空間離散化: 𝑁粒子で近似 (𝜇ො𝑘 ) [もっとも難しい]• 確率的勾配: 勾配計算を軽量化

199

収束解析
: proximal Gibbs measure
定理 (１ステップ更新の減少)

𝑝𝜇 は対数Sobolev不等式を定数𝛼で満たすとする.
損失関数の凸性と平滑性の仮定のもと，

時間
離散化

確率的
勾配

空間
離散化

既存研究では粒子数は時間に対して指数関数的に依存[Mei et al., 2018; Javanmard et al., 2019; De Bortoli et al., 2020]
Assumption: 1. 𝐹: 𝒫 → ℝ is convex and has a form of 𝐹 𝜇 = 𝐿 𝜇 + 𝜆1 𝔼𝜇 𝑥 2 .
2. (smoothness)∇(boundedness)

𝛿𝐿 𝜇
𝛿𝜇

∇

𝑥 −∇

𝛿𝐿 𝜇
𝛿𝜇

𝑥

𝛿𝐿 𝜈
𝛿𝜇

𝑦

≤ 𝑅.

≤ 𝐶(𝑊2 𝜇, 𝜈 + 𝑥 − 𝑦 ) and200

確率的勾配の計算量

201

SGD-MFLD:(有限和),(確率的勾配)(Mini-batch size = 𝐵)

更新回数のバウンド:
By setting
the iteration complexity becomes

時間
離散化

空間
離散化

確率的
勾配

,

to achieve 𝜖 + 𝑂(1/(𝜆2 𝛼𝑁)) accuracy.
➢ 𝐵 = 𝑛 ∧ 1/(𝜆2 𝛼𝜖) is the optimal mini-batch size. → 𝑘 = 𝑂 log 𝜖 −1 Τ𝜖 .

分散縮小勾配法

202

SVRG-MFLD:(有限和),(分散縮小勾配)ሶ(𝑋は𝑚回に一回更新)

時間
離散化

空間
離散化

確率的
勾配の誤差

線形GLDの既存解析[Kinoshita, Suzuki:
NeurIPS2022] の非線形への拡張/改善

更新回数：
ただし𝐵 = 𝑚 = 𝑛1/3 .

総勾配計算回数：

𝑛 in Kinoshita&Suzuki(2022)

統計的性質• ℓ𝑖 : ロジスティック損失• ℎ𝑧 𝑥 = 𝑅ത ⋅ [tanh 𝑥1 , 𝑧 + 𝑥2 + 𝑥3 ]/2• 𝑘-スパースパリティ問題➢ 𝑋 ∼ Unif( −1,1 𝑑 ) (up to freedom of rotation)➢ 𝑌 = 𝑋𝑖1 𝑋𝑖2 … 𝑋𝑖𝑘 for 𝑖𝑗 ∈ 𝑑 with 𝑖𝑗 ≠ 𝑖𝑙 .
Q: この問題設定でカーネル法を上回る？
A: Yes.
[Suzuki, Wu, Oko, Nitanda: Feature learning via mean-field Langevindynamics: classifying sparse parities and beyond. 2023]

203

統計的性質204• ℓ𝑖 : ロジスティック損失• ℎ𝑧 𝑥 = 𝑅ത ⋅ [tanh 𝑥1 , 𝑧 + 𝑥2 + 𝑥3 ]/2• 𝑘-スパースパリティ問題➢ 𝑋 ∼ Unif( −1,1 𝑑 ) (up to freedom of rotation)➢ 𝑌 = 𝑋𝑖1 𝑋𝑖2 … 𝑋𝑖𝑘 for 𝑖𝑗 ∈ 𝑑 with 𝑖𝑗 ≠ 𝑖𝑙 .
Q: この問題設定でカーネル法を上回る？
A: Yes.
[Suzuki, Wu, Oko, Nitanda: Feature learning via mean-field Langevindynamics: classifying sparse parities and beyond. 2023]

特徴学習によって次元への依存性が改善されている．