Upgrade to Pro — share decks privately, control downloads, hide ads and more …

深層学習理論のフロンティア (2023)

深層学習理論のフロンティア (2023)

近年の深層学習理論の発展を概観

Taiji Suzuki

June 18, 2023
Tweet

More Decks by Taiji Suzuki

Other Decks in Science

Transcript

  1. 鈴木大慈 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日. 研究室URLとメール連絡先 ➢ http://ibis.t.u-tokyo.ac.jp/suzuki/ ➢ [email protected]
  2. 深層学習の広がり 3 AlphaGo/Zero Image recognition [Silver et al. (Google Deep

    Mind): Mastering the game of Go with deep neural networks and tree search, Nature, 529, 484— 489, 2016] [He, Gkioxari, Dollár, Girshick: Mask R-CNN, ICCV2017] [Brown et al. “Language Models are Few-Shot Learners”, NeurIPS2020] [Alammar: How GPT3 Works - Visualizations and Animations, https://jalammar.github.io/how-gpt3-works- visualizations-animations/] Performance of few-shot learning against model size Learning efficiency of few shot learning Large language model Generative models (diffusion models) Jason Allen "Théâtre D'opéra Spatial“ generated by Midjourney. Colorado State Fair’s fine art competition, 1st prize in digital art category [ChatGPT. OpenAI2022] [Ho, Jain, Abbeel: Denoising Diffusion Probabilistic Models. 2020] Stable diffusion, 2022. 様々なタスクで高い精度 なぜ?
  3. 解決すべき問題点 なぜ深層学習はうまくいくのか? • 「◦◦法が良い」という様々な仮説の氾濫. • 世界的課題 4 “錬金術”という批判 学会の問題意識 民間の問題意識

    Ali Rahimi’s talk at NIPS2017 (test of time award). “Random features for large-scale kernel methods.” • 中で何が行われているか分か らないものは用いたくない. • 企業の説明責任.深層学習の ホワイトボックス化. • 原理解明 • どうすれば“良い”学習が実現できるか?→新手法の開発 理論の必要性
  4. スケーリング則 8 Reducible loss [Kaplan et al.: Scaling Laws for

    Neural Language Models, 2020] [Henighan et al.: Scaling Laws for Autoregressive Generative Modeling, 2020] モデルサイズ固定 (基本的に訓練データサイズと思ってよい) [Brown et al.: Language Models are Few-Shot Learners, 2020] (GPT-3モデルの解析) log(予測精度)=−𝛼 log 𝑛 + log(𝐶)
  5. 基本的考え方 • スケーリング則は古典的な学習理論でも現れる. 9 真のモデル log 予測誤差 = − 𝑎

    1+𝑎 log 𝑛 + log(𝐶) バイアス バリアンス 予測誤差 観測データ: 正則化学習法 (カーネル法) 最適なモデルサイズ 学習モデル ただし を用いて 𝑀 𝑀−𝑎 (正規直交系 in L2) バリアンス=モデルの次元/n バイアス=切り捨てた係数の二乗和
  6. 10 log 予測誤差 = − 𝑎 1+𝑎 log 𝑛 +

    log(𝐶) log(𝒏) log(予測誤差) モデルサイズM固定の予測誤差 最適なモデルサイズの予測誤差
  7. カーネル法の学習理論 • Caponnetto and De Vito. Optimal Rates for the

    Regularized Least- Squares 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 and Infinitely Wide Neural Networks. arXiv:2006.13198. 11
  8. 教師あり学習 13 -猫 (y=1) -犬 (y=2) -人間 (y=3) 画像 学習:「関数」をデータに当てはめる

    モデル:関数の集合(例:深層NNの表せる関数の集合) ベ ク ト ル ベ ク ト ル
  9. 表現能力「万能近似能力」 理論的にはデータが無限にあり,素子数が無限 にあるニューラルネットワークを用いればどん な問題でも学習できる. 14 二層ニューラルネットワークは どんな関数も任意の精度で近似できる. 「関数近似理論」 [Hecht-Nielsen,1987][Cybenko,1989] 年

    基底関数 空間 1987 Hecht-Nielsen 対象毎に構成 𝐶(𝑅𝑑) 1988 Gallant & White Cos 𝐿2 (𝐾) Irie & Miyake integrable 𝐿2 (𝑅𝑑) 1989 Carroll & Dickinson Continuous sigmoidal 𝐿2 (𝐾) Cybenko Continuous sigmoidal 𝐶(𝐾) Funahashi Monotone & bounded 𝐶(𝐾) 1993 Mhaskar + Micchelli Polynomial growth 𝐶(𝐾) 2015 Sonoda + Murata Unbounded, admissible 𝐿1 (𝑅𝑑)/𝐿2 (𝑅𝑑)
  10. 深層学習との違い • 線形モデル 16 • カーネルモデル • 深層モデル 非線形化 可変基底化

    学習可能 固定 学習可能 学習可能 学習可能 固定 問題意識 • 基底を学習可能にすることで何が良くなるか? • 逆に過学習を起こさないか? • 最適化可能か?
  11. 深層学習の統計理論 17 深層学習が浅い学習法を予測誤差に関して優越することを証明 [統計的学習理論] 浅層 深層学習 大きく変動する方向と そうでない方向が混在 [Suzuki, 2019]

    [Suzuki&Nitanda, 2019] 変動が大きい (滑らかでない) 滑らか 特に「複雑な」関数は深層学習 の方が優位であることを証明. [適応的学習] 大きく変動する方向と そうでない方向が混在 典 型 例
  12. 典型的な例 18 滑らかな部分と そうでない部分が混在 変動が大きい (滑らかでない) 滑らか 大きく変動する方向と そうでない方向が混在 Besov空間

    [Suzuki, 2019] [Schmidt-Hieber, 2019] [Nakada&Imaizumi, 2019][Chen et al., 2019][Suzuki&Nitanda, 2019] [Imaizumi&Fukumizu, 2019]
  13. 仮定 𝑓∘ ∈ 𝐵𝑝,𝑞 𝑠 ( 0,1 𝑑): 真が“Besov空間”に入っている. 「浅い」学習との比較

    23 ≫ (𝑛: sample size,𝑝: uniformity of smoothness,𝑠: smoothness) カーネルリッジ回帰等: 線形推定量 (非適応的手法) 深層学習 • 深層学習は場所によって解像度を変える適応力がある →学習効率が良い • 浅い学習方法にはそのような適応力がない. →学習効率が悪い ミニマックス最適性の意味で理論上これ以上改善 できない精度を達成できている. 平均二乗誤差 E መ 𝑓 − 𝑓∗ 2 がサンプルサイズが増えるにつれ減少するレート [Suzuki, ICLR2019] 一様な解像度 適応的解像度 最適ではない 最適 • Wavelet shrinkageより弱い条件 • 基底を用意せず最適化するだけでOK
  14. 線形推定量 24 例 • Kernel ridge estimator • Sieve estimator

    • Nadaraya-Watson estimator • k-NN estimator 線形推定量: 観測値𝑌 = 𝑦𝑖 𝑖=1 𝑛 に対して線形な推定量. 線形 Kernel ridge regression: “浅い” 学習法 正則化付き最小二乗推定量 (特徴マップ) 固定 学習可能 固定 グラム行列 (カーネル関数) (see also [Imaizumi&Fukumizu, 2019])
  15. Besov空間とスパース性との関係 25 𝑘 = 0 𝑘 = 1 𝑘 =

    2 𝑘 = 3 解像度 𝑗 = 1 𝑗 = 1 𝑗 = 2 𝑗 = 1 𝑗 = 2 𝑗 = 3 𝑗 = 4 𝛼0,1 𝛼1,1 𝛼1,2 𝛼2,1 𝛼2,4 𝛼2,3 𝛼2,2 空間的な滑らかさの 非一様性 小さな𝑝 = スパースな係数 (0 < 𝑝) Wavelet基底による展開 (informal) 高周波 低周波 場所によって滑らかさが違うのでウェーブ レット基底のスパースな線形結合が有効 Wavelet基底
  16. Besov空間とスパース性との関係 26 𝑘 = 0 𝑘 = 1 𝑘 =

    2 𝑘 = 3 解像度 𝑗 = 1 𝑗 = 1 𝑗 = 2 𝑗 = 1 𝑗 = 2 𝑗 = 3 𝑗 = 4 𝛼0,1 𝛼1,1 𝛼1,2 𝛼2,1 𝛼2,4 𝛼2,3 𝛼2,2 空間的な滑らかさの 非一様性 小さな𝑝 = スパースな係数 (0 < 𝑝) Wavelet基底による展開 (informal) 高周波 低周波 場所によって滑らかさが違うのでウェーブ レット基底のスパースな線形結合が有効 Wavelet基底 Wavelet-shrinkage
  17. スパース推定との繋がり 27 1990 2000 2010 2011 2019 2012 ビッグデータ ブーム

    ILSVRC Supervision優勝 第三次AIブーム - 深層学習 - 産業応用 Wavelet shrinkage Lasso 1995 スパース推定の流行 圧縮センシング • Donoho • Candes&Tao 2006 機械学習の興隆 深層学習の理論 ➢ 適応的推定理論 ➢ Besov空間を用いた解析
  18. 他にも様々な理論が • 真の関数𝑓∘の形状によって深層が有利になる 28 深 層 カ ー ネ ル

    縮小ランク回帰 特徴空間の次元 が低い状況は深 層学習が得意 区分滑らかな関数 不連続な関数の 推定は深層学習 が得意 Besov空間 滑らかさが非一 様な関数の推定 は深層学習が得 意 低次元データ データが低次元 部分空間上に分 布していたら深 層学習が有利 [Suzuki, 2019] [Schmidt-Hieber, 2019] [Nakada&Imaizumi, 2019][Chen et al., 2019][Suzuki&Nitanda, 2019] [Imaizumi&Fukumizu, 2019] 推 定 精 度
  19. 数学的に一般化 29 [Satoshi Hayakawa and Taiji Suzuki: On the minimax

    optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, Vol.123, pp. 343—361, 2020] 「滑らかさの非一様性」「不連続性」「データの低次元性」 凸結合を取って崩れる性質をもった関数の学習は深層学習が強い → 様々な性質を“凸性”で統一的に説明できる 例:ジャンプが3か所の区分定数関数 + = 0.5x 0.5x ジャンプ3か所 ジャンプ3か所 ジャンプ6か所 → 「スパース性」と「非凸性」 深層:𝟏/𝒏 カーネル: 𝟏/ 𝒏 𝒏倍の違い 参考
  20. 線形推定量の最悪誤差 30 [Hayakawa&Suzuki: 2019] [Donoho & Johnstone, 1994] さらに条件を仮定すれば「Q-hull」まで拡張できる. 線形推定量:

    と書ける任意の推定量 例: カーネルリッジ回帰 (“浅い”学習法とみなす) • 凸包を取って大きく膨らむような 関数クラスにおいては深層NNを 使うメリットがある. • 特徴量(基底関数)を適応的に作る ことで,ターゲットを「狙い撃 ち」して近似. • 一方,線形推定量は広めにモデル を取って「待ち構えて」いる必要 がある. 参考
  21. 数学的一般化 31 縮小ランク回帰 区分滑らかな関数 Besov空間 低次元データ 非凸性 スパース性 変動指数 Besov空間

    適応的推定法 • (勾配)ブースティング • スパース推定 • 深層学習 参考
  22. アプローチ (1): 多様体回帰 34 • 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). -dim -dim MNIST: 784 dim/ 13.4 intrinsic-dim [Facco et al. 2017] データが低次元多様体*に分布していれば次元の呪いを回避できる! * Nakada&Imaizumi (2019) では非滑らかな低次元構造も許容 (Hausdorff次元が小さい)
  23. アプローチ (2): 関数の平滑性の非等方性35 不変な方向 変化する方向 𝑠1 , 𝑠2 , 𝑠3

    : 滑らかさ (非平滑) 𝑠1 , 𝑠2 ≪ 𝑠3 (平滑) • 真の関数の滑らかさが方向に依存 • 多様体に直交する方向にはほぼ定数 (滑らかさ大) データが低次元多様体からはみ出る場合: [Suzuki&Nitanda: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. NeurIPS2021.] → 中間層で「重要な方向」を取り出すことで次元の呪いを回避.
  24. (超)高次元入力NNの学習理論 36 不変な方向 変化する方向 𝑠1 , 𝑠2 , 𝑠3 :

    滑らかさ • 真の関数が方向によって異なる滑らかさを持つ状況では DNNは重要な方向を見つけ,次元の呪いを回避する. • 一方で,浅い学習法は次元の呪いを受ける. Hayakawa and Suzuki: Neural Networks 2020, 日本神経回路学会論文賞. 関連研究: - 教師生徒設定における大域的最適化と次元の 呪いの回避 - 深層学習の浅層学習への優位性: Suzuki and Akiyama: ICLR2021, spotlight. : 非等方的Besov空間 (𝐵𝑝,𝑞 𝑠(ℓ) ). 真の関数のモデル: 非等方的Besov空間の元の合成関数 ➢ 滑らかさが方向によって異なる関数空間 ➢ 合成することで様々な形状を実現 (例:多様体上の関数: 一層目で座標を抽出,二層目がその座標上の関数) Def. (非等方的Besov空間) 真の関数の滑らかさが方向によって大きく 異なる状況で,ほとんどの方向に対して滑 らかならば次元の呪いを回避できる. → 「非等方的Besov空間」を用いた理論. Suzuki&Nitanda: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. NeurIPS2021, spotlight.
  25. (超)高次元入力NNの学習理論 37 不変な方向 変化する方向 𝑠1 , 𝑠2 , 𝑠3 :

    滑らかさ • 真の関数が方向によって異なる滑らかさを持つ状況では DNNは重要な方向を見つけ,次元の呪いを回避する. • 一方で,浅い学習法は次元の呪いを受ける. Suzuki&Nitanda: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. NeurIPS2021, spotlight. Hayakawa and Suzuki: Neural Networks 2020, 日本神経回路学会論文賞. 関連研究: - 教師生徒設定における大域的最適化と次元の 呪いの回避 - 深層学習の浅層学習への優位性: Suzuki and Akiyama: ICLR2021, spotlight. : 非等方的Besov空間 (𝐵𝑝,𝑞 𝑠(ℓ) ). 真の関数のモデル: 非等方的Besov空間の元の合成関数 ➢ 滑らかさが方向によって異なる関数空間 ➢ 合成することで様々な形状を実現 (例:多様体上の関数: 一層目で座標を抽出,二層目がその座標上の関数) Def. (非等方的Besov空間) 真の関数の滑らかさが方向によって大きく 異なる状況で,ほとんどの方向に対して滑 らかならば次元の呪いを回避できる. → 「非等方的Besov空間」を用いた理論. 直感
  26. 推定誤差の評価 38 深層 (次元の呪いを受ける) 浅層 • 特徴抽出能力の重要性を理論的に正当化 • 浅い学習方法は一番滑らかでない方向の滑らかさ (𝒔𝟏

    )が支配的で,次元の呪いを受ける. • 証明には「凸法の議論」を用いる. 主結果 (最小二乗推定量) ※今回は最適化手法に関しては議論せず,最適化はできるものと仮定する. , Let 各方向への滑らかさの調和平均が収束レートを決める. 例: 𝑯 = 𝟏の時 浅い学習方法との比較 (informal): 少ない数の方向において𝒔𝒊 が小さく (滑らかでない),その他の方向には𝒔𝒊 が大きい(滑らか)であるとき,次元 の呪いを回避できる.
  27. 無限次元入力NN 39 典型的なノンパラメトリック回帰のバウンド: 無限次元入力 (画像,音声信号, 自然言語,...) 画像データ 関数データ 無限 (高)

    次元データ 出力 (実数) • 音声 • 文章 … (𝑠: 真の関数の滑らかさ, 𝑑: 入力の次元) 次元の呪い 我々の貢献: 無限次元入力に対する深層学習の統計理論を構築 異方的平滑性: 真の関数が座標軸方向によって異なる滑らかさを持つ. • 次元に依存しないバウンド (有限次元の拡張) を導出 • 畳み込みNNによる特徴量の抽出 [Ramsay, J., Hooker, Giles, & Graves, Spencer. (2009). Functional data analysis with R and MATLAB (Use R!). Dordrecht: Springer.] [Okumoto&Suzuki: Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness. ICLR2022.]
  28. (𝑌𝑡 ∼ 𝑋 𝑇−𝑡 ) 拡散モデルの統計理論 40 Stable diffusion, 2022.

    Forward process Backward process どちらも(ほぼ)ミニマックス最適 [Yang & Barron, 1999; Niles-Weed & Berthet, 2022]. 経験スコアマッチング推定量: (for any 𝛿 > 0). 定理 Let ෠ 𝑌 be the r.v. generated by the backward process w.r.t. Ƹ 𝑠, then (Estimator for 𝑊1 distance requires some modification) (𝑠: 密度関数の滑らかさ) [Kazusato Oko, Shunta Akiyama, Taiji Suzuki: Diffusion Models are Minimax Optimal Distribution Estimators. ICML2023]
  29. Transformerの推定理論 41 定理 (推定誤差) ➢ 入力が無限次元でも多項式オーダーの収束レート. (ほぼミニマックス最適) ⋯ 𝑥−1 𝑥0

    𝑥1 𝑥2 ⋯ ⋯ 𝑌−1 𝑌0 𝑌1 𝑌2 ⋯ ⋮ ⋮ ⋮ ⋮ Self-attention FNN Transformerの性質 • かなり広いトークン幅から重要な トークンを選べる. → 次元の呪い? • 入力に依存して重要なトークンを 選択できる. → 次元の呪いを回避! [Shokichi Takakura, Taiji Suzuki: Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input. ICML2023] 入力に依存して重要なトークンを切り替 えることで,関数を「切り替えている」.
  30. 過学習 45 「なんでも表現できる方法」が最適とは限らない 少しのノイズにも鋭敏に反応してしまう 過学習 適切な学習 説明力が高すぎる (複雑すぎる) 説明力が適切 良い学習結果

    悪い学習結果 学習に用いるデータには誤りも含まれる 過小学習 説明力が低すぎる 悪い学習結果 一見当てはまりが良いので危険
  31. 深層ニューラルネットの冗長性 48 パラメータ数 ≫ データサイズ 数十億 数百万 数十万 ≫ 実質的自由度

    [仮説] 見かけの大きさ (パラメータ数) よりも 実質的な大きさ (自由度) はかなり小さいはず. “実質的自由度”を調べる研究: • ノルム型バウンド • 圧縮型バウンド 「Overparametrization」 パラメータサイズがデータサイズを超えている状況 での汎化性能を説明したい. 「実質的自由度」として何が適切かを見つけることが理論上問題になる.
  32. 圧縮型バウンド 50 [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 of large compressible deep neural network, ICLR2020] [Suzuki et al.: Spectral pruning: Compressing deep neural networks via spectral analysis and its generalization error. IJCAI-PRICAI 2020] 元サイズ 圧縮可能 サイズ 大 小 実質的自由度 元のサイズ [実験的観察] 実際に学習した ネットワークは圧縮しやすい. すぐ減衰 すぐ減衰 •中間層の分散共分散行列の固有値分布 •中間層の重み行列の特異値分布 が速く減衰するなら圧縮しやすい. 重み行列の特異値 分散共分散行列の固有値 分散共分散行列も重み行列も 特異値が速く減衰 →小さい統計的自由度 (AIC, Mallows’ Cp) カーネル法の理論 (そもそもカーネルは無限次元モデル) (次ページに詳細)
  33. 分散共分散行列と重み行列の低ランク性 51 • 近似的に低ランクな重み行列と分散共分散行列: ➢ 定理 (Suzuki, Abe, Nishimura, ICLR2020)

    ➢ where . + Other boundedness condition. VC-次元によるバウンドより大きく改善: 特異値が早く減衰 横幅の二乗
  34. ニューラルネットワークの圧縮 52 VGG-16ネットワークの圧縮 提案手法: 従来手法より良い精度 94%の圧縮 (精度変わらず) ResNet-50ネットワークの圧縮 約半分に圧縮しても精度落ちず 圧縮

    • メモリ消費量を減少 • 予測にかかる計算量を減少 → 小型デバイスでの作動に有利 (自動運転など) [Suzuki, Abe, Murata, Horiuchi, Ito, Wachi, Hirai, Yukishima, Nishimura: Spectral- Pruning: Compressing deep neural network via spectral analysis, 2018]
  35. 転移学習のネットワーク構造決定 • ある閾値以上の固有値をカウント (e.g., 10−3) . → 縮小したネットワークのサイズとして使う. • その後,スクラッチから学習

    (𝒮) もしくはImageNet事前学習モデルをファイン チューニングする (ℐ). 53 Network size determination alg. [Dillard, Shinya, Suzuki: Domain Adaptation Regularization for Spectral Pruning. BMVC2020]
  36. BigNAS 54 [Yu et al.: BigNAS: Scaling Up Neural Architecture

    Search with Big Single-Stage Models. ECCV2020] • 学習後のネットワークが圧縮できるように学習 • 大きなネットワークから小さなネットワークを 生成できる • EfficientNetを上回る効率性を実現 圧縮できるように学習するとスクラッチ学習より 性能が向上することもある. (理論と関係あるNAS手法) 参考
  37. 実際の例 57 [Mei and Montanari. "The generalization error of random

    features regression: Precise asymptotics and double descent curve." arXiv preprint arXiv:1908.05355 (2019)] 2-layer neural network [Xu and Hsu: On the number of variables to use in principal component regression. NeurIPS2019.] Principal component regression (いくつの主成分を用いたか) Populationの分散共分散を知っているとして, その主成分を利用 (いくつのニューロンを用いたか) Sample size = # of features Sample size = # of features
  38. 典型的なアプローチ (抜粋) • ランダム行列理論 ➢ 𝑑/𝑛 → 𝛾 > 0という漸近的設定で,厳密なリスクの導出

    ➢ Marchenko–Pastur則, Stieltjes変換 58 • 集中不等式による評価 ➢ 有限サンプルサイズにおける予測誤差の上界評価 (𝑛 < ∞) ➢ 収束レートが評価できる. (𝑛 → ∞を取る前の振る舞いを評価) ◼ 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 and double 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.
  39. 悪性過学習 (モデルの説明力が中 途半端なので,無理 してノイズも説明) True func. 直感 59 訓練データ 𝑥𝑖

    (𝑖 = 1, … , 𝑛) 𝑥 (テスト時の入力) d-次元空間 • 過剰パラメータ化されたモデルは “スパイク” 成分を持つ. • スパイク成分がノイズを説明. • 大まかな関数形はモデルの主成分が説明. • 「スパイク成分」とは ほぼ直交. • 直交するには高次元性 が必要. • 高次元空間で2つのラ ンダムベクトルはほぼ 直交. [Belkin, Rakhlin&Tsybakov: Does data interpolation contradict statistical optimality? AISTATS2019]
  40. 前処理付き勾配法 60 Preconditioned Gradient Descent 𝑃 = 𝐼: Gradient descent

    (GD) 𝑃 = Σ𝑥 −1: Natural Gradient descent (NGD) (interpolation) 𝑑 ≫ 𝑛: overparameterized regime Q: 𝑃によって予測性能がどのように影響受けるか? (真の分布で期待値取ったFisher情報行列) Amari, Ba, Grosse, Li, Nitanda, Suzuki, Wu, Xu: When Does Preconditioning Help or Hurt Generalization? ICLR2021.
  41. 最適な前処理行列 61 Bias-variance分解 1. バリアンス: 2. バイアス: (Fisher情報行列) がバリアンスを最小化. NGDがバリアンスの意味で最適.

    No free-lunch: 事前に最適なPは決定できない: • 真が等方的分布 Σ𝛽∗ = 𝐼に従っていればGDが良い. • 真が非等方的分布Σ𝛽∗ = Σ𝑥 −1に従っていればNGDが良い. (ベイズの設定: 𝛽∗の実現値に関する予測誤差 の期待値を比較 E 𝛽∗𝛽∗T = Σ𝛽∗) 定理 (informal) GDとNGDの中間が良い [Amari, Ba, Grosse, Li, Nitanda, Suzuki, Wu, Xu: When Does Preconditioning Help or Hurt Generalization? ICLR2021] Τ 𝑑 𝑛 → 𝛾 > 1 (𝑛 → ∞)の極限における予測誤差の漸近値を厳密に導出
  42. より詳細な結果 62 (A2) Σ𝑋𝑃 : = 𝑃1/2Σ𝑃1/2のスペクトル分布が𝐻𝑋𝑃 に弱収束すると仮定. • 𝒎(𝒛)

    を自己整合条件を 満たす関数とする: → 1 𝑛 𝑋𝑃𝑋⊤のスペクトルの漸近分布を表現. 1. バリアンス: 2. バイアス: (A3) 𝑃とΣが同じ固有ベクトル𝑈を共有. ただし,(𝑒𝑥 , 𝑒𝜃 , 𝑒𝑥𝑝 )は Σ, Σ𝑋𝑃 , diag(𝑈⊤Σ𝛽∗𝑈)の固有値で 𝑣𝑥 , 𝑣𝜃 , 𝑣𝑥𝑝 に弱収束す るものとする.
  43. Loss landscape • 横幅の広いNNの訓練誤差には孤立した局所最 適解がない.(局所最適解は大域的最適解とつ ながっている) 67 [Venturi, Bandeira, Bruna:

    Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes. JMLR, 20:1-34, 2019.] 定理 𝑛個の訓練データ 𝑥𝑖 , 𝑦𝑖 𝑖=1 𝑛 が与えられているとする.損失関数ℓは凸関 数とする. 任意の連続な活性化関数について,横幅がデータサイズより広い (𝑀 ≥ 𝑛)二層NN𝑓 𝑎,𝑊 (𝑥) = σ𝑚=1 𝑀 𝑎𝑚 𝜂(𝑤𝑚 ⊤𝑥)に対する訓練誤差 ෠ 𝐿 𝑎, 𝑊 = 1 𝑛 σ𝑖=1 𝑛 ℓ(𝑦𝑖 , 𝑓𝑎,𝑊 (𝑥𝑖 ))の任意のレベルセットの弧状連結成分 は大域的最適解を含む.言い換えると,任意の局所最適解は大域的最 適解である. こうはならない こうなる (つながっていない) ※とはいえ,勾配法で大域的最適解に到達可能かは別問題.
  44. オーバーパラメトライゼーション 横幅が広いと局所最適解が大域的最適解になる. 68 • 二種類の解析手法 ➢ Neural Tangent Kernel (NTK)

    ➢ Mean-field analysis (平均場解析) … 狭い横幅 広い横幅 自由度が高いので,目的関数を減少さ せる方向が見つけやすい. 0 0
  45. 二つのスケーリング • Neural Tangent Kernelのregime (lazy learning ) ➢ 𝑎𝑗

    = O(1/ 𝑀) • 平均場解析のregime ➢ 𝑎𝑗 = Ο(1/𝑀) 69 初期化のスケーリングによって,初期値と比 べて学習によって動く大きさの割合が変わる. → 学習のダイナミクス,汎化性能に影響 [Nitanda & Suzuki (2017), Chizat & Bach (2018), Mei, Montanari, & Nguyen (2018)] [Jacot+ 2018][Du+ 2019][Arora+ 2019] (解析の難しさも違う) (Xavier initialization/He initialization)
  46. (参考) 初期化スケールと学習率の取り方 • ABCパラメトライゼーション [Yang&Hu, 2021] 70 (1) パラメータ設定 (𝑤𝑙が学習パラメータ)

    (2) 初期化法 (3) 学習率のスケール 𝑛:横幅 A B C (適切なスケーリング) [Yang&Hu: Tensor Programs IV: Feature Learning in Infinite-Width Neural Networks. ICML2021.] (Neural tangent) (平均場)
  47. 71 [Yang et al.:Tensor Programs V: Tuning Large Neural Networks

    via Zero-Shot Hyperparameter Transfer. arXiv:2203.03466] 小さいモデルのハイパーパラメータを大きなモデルに転用できる. GPTの学習に利用.数億円の学習コストを抑えられる.
  48. Neural Tangent Kernel 72 初期値のスケールが大きいので,初期値周りの 線形近似でデータにフィットできてしまう. Neural Tangent Kernel [Jacot,

    Gabriel, & Hongler (2019)] 最適化のダイナミクスや汎化性能などは, NTKをカーネル関数とするカーネル法としてとらえられる. → 勾配法で大域的最適解に到達可能 カーネル関数は特徴写像の内積 特徴写像とみなせる テイラー展開 各ニューロンの微分で得られる 特徴写像の内積を全ニューロンで平均 (線形モデル) 重要
  49. Neural Tangent Kernelの理論 73 ニューラルネットワークの最適化は非凸最適化 → 横幅の広いネットワークは「凸」的になり大域的最適解へ収束 (NTKの理論) 以下を理論的に示した: •

    確率的最適化により最適な推定レートを達成可能. • ネットワーク固有の周波数成分のスペクトルが学習効率を決める. 高周波成分 低周波成分 低周波成分が最初に補足 される.その後,高周波 成分が徐々に補足される. Nitanda&Suzuki: Fast Convergence Rates of Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime, ICLR2021 (oral). Outstanding paper award. 8 papers out of 860 accepted papers and 2997 submitted papers. NTKのスペクトル 𝑘−𝛽 横幅𝑀 → ∞で0に収束する項 速い学習レート(𝑂(1/ 𝑇)より速い) → Minimax最適レート 𝛽: NTK (Neural Tangent Kernel) の固有値の減衰レート 𝑟: 真の関数の“複雑さ” (RKHSと の相対的な位置関係) 目的関数: 期待損失 初期値からのずれ モデル: (一層目と二層目を学習) 𝑌 = 𝑓∗ 𝑋 + 𝜖 (ノイズありの観測) • 目的関数をオンライン型 の確率的最適化で最適化 • 𝑇は更新回数=観測した データ数 全投稿の0.27%
  50. NTKの陰的正則化 74 See Cho&Saul (2009), Xie,Liang&Song (2017), Back (2017), Bietti&Marial

    (2019) for inductive bias. 固有値減少の数値実験による検証 Low frequency components High frequency components • 𝑌𝑘,𝑗 : spherical harmonics functions with degree 𝑘. • 𝜇𝑘 ∼ 𝑘−𝑑. . ReLU, 𝑎, 𝑤 ∼ 𝑁 0, 𝐼 : • 理論
  51. 二層NNのNTKはmultiple kernel 75 仮定: 𝑓∗ is in RKHS w.r.t. NTK

    for the 2nd layer. 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に対してよりロバストになる. 一層目のNTK 二層目のNTK 一層目と二層目のカーネルの和:multiple kernel
  52. 高次元極限におけるニューラルネットワークの 勾配法による特徴学習の解析 77 [Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki,

    Zhichao Wang, Denny Wu, Greg Yang: High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation. NeurIPS2022.]
  53. • (NTKを超えて)勾配法によって特徴量がどう学習 されるか? → 色々な研究がある. • NTK近似が成り立たない領域では非線形性が強く なり,最適化のダイナミクスの解析が難しくなる. • 最近では妥協点として,勾配法の最初の段階(1ス

    テップ or 少数ステップ)でどのような特徴量が 獲得できるかを解析する研究が複数なされている. • 少数ステップで得られる情報は限られているが,それで も予測性能の改善が示せる. • 今はより非線形性の強い特徴量学習のダイナミクスの解 析が進んでいる. 78 ※ 計算量をあまり気にしなければ勾配ランジュバン動力学を用いた学習の解析は 完全に非線形な特徴学習をとらえられる.
  54. 勾配法とKernel alignment 79 問:勾配法で𝑊を更新することで,データに合った特徴量を獲得できるか? 答:NTK近似が成り立つ領域からはみ出るくらい大きなステップサイズを用い れば,一回の更新で意味のある特徴量の方向を得ることができる. → カーネルAlignment,特徴量学習. 𝒏, 𝒅,

    𝑵 → ∞の極限を考え,勾配法1回の更新後の予測誤差を評価してみる. ➢ 𝜂 = 𝑁: 大きなステップサイズを用いると,ランダム特徴モ デルによるリッジ回帰を優越する. ➢ 𝜂 = 1: 中間的なステップサイズでは横幅無限大のランダム特 徴リッジ回帰を優越しないが初期値𝑊は優越. ➢ 𝜂 = 𝑜(1): 小さなステップサイズでは初期値𝑊と同じ予測誤差 (NTK-regime).特徴学習の効果なし. 点: 実測値 実線: 理論値 [Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, Greg Yang: High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation. NeurIPS2022.] ランダム行列理論 + 特徴量の中心極限定理 → 厳密なリスクの評価 (二重降下の理論)
  55. 勾配法による更新 80 •一層目のパラメータ𝑊の更新: 1. 特に,勾配法の“1ステップ更新“ に注目: ✓ 二層目のパラメータ𝑎は最適化の途中で固定. ✓ あくまで𝑊の特徴学習のダイナミクスに注目.

    ➢ 𝑊1 (1回更新後) は,初期値𝑊0 より真の関数𝑓∗に「相関してい る」と考えらえれる.→より良い予測誤差. ෤ 𝑥𝑖 , ෤ 𝑦𝑖 𝑖=1 𝑛 : i.i.d. copy of 𝑥𝑖 , 𝑦𝑖 𝑖=1 𝑛 2. その後,二層目はリッジ回帰で推定:
  56. 最初の勾配ステップはほぼランクが1 • 勾配𝐺𝑡 は,ランク1行列で近似できる. ⇒ 𝑊1 のスペクトル分布に「スパイク」が現れる! 81 (𝜎′の非線形性より,一般的には低ランクにならない.しかし高次元だと低ランクになる) 定理

    (勾配のランク1近似) with high probability for sufficiently large 𝑛, 𝑑, 𝑁. (ランク1行列)とすれば,以下を得る: 𝑊1 = 𝑊0 + 𝜂 × (rank one matrix). ⇒ ステップサイズ𝜂が大きいと,スパイクが支配的. Spike (Gordon-Slepian ineq.; Hanson-Wright inequ) (活性化関数の1 次成分と2次成分) に注意. MP則 (初期解)
  57. 初期値のCKからの改善 83 • 𝜂 = Θ(1) (中間的な大きさのステップサイズ): • 1ステップのGDは必ず精度を改善させる. •

    しかし,どんなに更新しても真の関数の線形成分以外は取り出せない: • 𝜂 = Θ( 𝑁) (大きな学習率): (モデルのズレを表す量) Τ 𝑛 𝑑 → 𝜓1 , Τ 𝑁 𝑑 → 𝜓2 (𝑅𝑊 (𝜆) is the ridge regression estimator using 𝑊 for the first layer.) 学習率を大きくすることで,精度を大きく改善できる (𝜏∗ ≪ 𝑃>1 𝑓∗ 2の状況で). ※バイアス項を振りなおせば𝜏∗ = 0とできる. Maximal update parameterization (𝜇P) [Yang and Hu, 2020] として知られている. • 𝜏∗ = 0 if 𝜎 = 𝜎∗ = erf. • 𝜏∗ ≪1 if 𝜎 = 𝜎∗ = tanh. 線形な領域 非線形領域 を仮定 (𝑃>1 は𝐿2空間内で線形関数に直交する成分を取り出す作用素) [高次元ゆえの現象,予測誤差を一定以 上減らせない]
  58. 実験との整合性 84 もし𝜎 = 𝜎∗ = erf なら,𝜏∗ = 0.

    特に,𝑅𝑊1 𝜆 = Θ 𝜓1 −1 = Θ 𝑑/𝑛 である. Predictive risk of ridge regression on CK obtained by one step GD (empirical simulation, 𝑑 = 1024): brighter color represents larger step size scaled as 𝜂 = 𝑁𝛼 for 𝛼 ∈ [0,1/2]. We chose 𝜎 = 𝜎∗ = erf, 𝜓2 = 2, 𝜆 = 10−3, and 𝜎𝜖 = 0.1. Corollary Large step size Θ(𝑑/𝑛)で減少 Small step size 小さなステッ プサイズでは, このラインを 越えられない. (ランダム特徴 モデルの限界)
  59. Sharp minima vs flat minima 87 SGDは「フラットな局所最適解」に落ちやすい→良い汎化性能を示す という説 ≅正規分布 →

    ランダムウォークはフラットな領域に とどまりやすい •「フラット」という概念は座標系の取り 方によるから意味がないという批判. (Dinh et al., 2017) •PAC-Bayesによる解析 (Dziugaite, Roy, 2017) Keskar, Mudigere, Nocedal, Smelyanskiy, Tang (2017): On large-batch training for deep learning: generalization gap and sharp minima.
  60. 89 Gaussian noise Gradient descent 勾配ランジュバン動力学 • • (連続時間) (離散時間)

    適当な条件のもと,大域的最適解への収束が保証されている.
  61. 2層NNのGLDによる最適化 90 例: 𝑀 → ∞ 多粒子化(平均場): 𝑀 → ∞,

    𝑡 → ∞の極限で粒子𝜃𝑗 の分布𝜇𝑡 は以下の分布に収束: 重要:分布𝝁に対しては凸関数!(if 損失が凸) 定理 (Hu, Ren, Šiška, and Szpruch, 2021; Mei, Montanari, and Nguye, 2018) … ニューロンが沢山あると普通のGLDの理論が適用できない. しかし,平均場ランジュバン動力学の理論により理論保証ができる. (逆にニューロン数無限大の極限を考えると理論保証可能になる) エントロピー
  62. MF-LDの収束 91 近接点更新解: 𝑝𝜇𝑡 が一様に対数ソボレフ不等式 (定数𝛼)を満たすとすると, 定理 (Entropy sandwich) [Nitanda,

    Wu, Suzuki (AISTATS2022)][Chizat (2022)] (c.f., Mirror descent, exponentiated gradient) (線形収束!) 損失を線形化して得られる解 目的関数 平均場ランジュバン動力学: (わかりにくいが単純に各ニューロンを勾配法で動かして微小ノイズを加えていることに対応) ただし, (損失関数+正則化)
  63. 応用例 92 • 平均場二層ニューラルネットワーク Example: 目的関数 𝜇で微分 • MMD最小化によるノンパラメトリック密度推定 𝑘:

    正定値カーネル : 経験分布 (訓練データ) ➢ ➢ ➢ • ベイズ事後分布の変分推論 𝑀 → ∞
  64. 研究の流れ 94 平均場NNの線形収束 連続時間・無限粒子 [Nitanda, Wu, Suzuki (AISTATS2022)] [Chizat (2022)]

    • PDA法 [Nitanda, Wu, Suzuki: NeurIPS2021] • P-SDCA法 [Oko, Suzuki, Wu, Nitanda: ICLR2022] • 無限次元拡張 [Nishikawa, Suzuki, Nitanda: NeurIPS2022] 時間・空間離散化:「二重ループの手法」 空間離散化・連続時間: 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) 時間・空間離散化・確率的勾配: 「一重ループの手法」 難しい:Propagation of chaos (McKean, Kac,…, 60年代より)
  65. 離散時間・有限横幅の手法 95 𝑞に関する線形汎関数で近似 (勾配を用いる) 近似 (線形近似; ഥ 𝒈(𝒕)は基本的に勾配) 解: →

    この分布からは以下の勾配ランジュバン動力学 を用いてサンプリング可能: 時間離散化 ഥ 𝒈(𝒕)の決定に双対平均化法のルールを用いる 具体形が得られる. 粒子双対平均化法 (Particle Dual Averaging; PDA) 粒子確率的双対座標上昇法 (Particle Stochastic Dual Coordinate Ascent; P-SDCA) 1. 外側ループ: 2. 内側ループ: 計算量解析: (GLDによる) ⇒合計: 𝑶(𝝐−𝟑)の勾配アップデートで十分. ➢ 初の多項式オーダー最適化手法 主問題 双対問題 = by Fenchelの双対定理 ただし • 双対変数の座標をランダムに選択し, その座標に関して最適化. →確率的双対座標上昇法 計算量解析: 双対ギャップ𝝐𝑷 を達成するのに必要な外側ループ数: ➢ 指数オーダーでの収束を達成 ➢ サンプルサイズ𝑛への依存を緩和 [Nitanda, Wu, Suzuki: NeurIPS2021] [Oko, Suzuki, Wu, Nitanda: ICLR2022]
  66. Kernel alignment 96 一層目: 特徴抽出 カーネルalignment: 一層目で抽出された特徴量が教師信 号(y)とどれだけ相関しているか? → 高いほど特徴量が真の関数の成分

    を多く含んでいる. 一層目ほぼ固定 前ページの方法で学習 一層目も学習することで真の関数に より適合した特徴量が学習できている. 固有値の分布:
  67. 研究の流れ 97 平均場NNの線形収束 連続時間・無限粒子 [Nitanda, Wu, Suzuki (AISTATS2022)] [Chizat (2022)]

    • PDA法 [Nitanda, Wu, Suzuki: NeurIPS2021] • P-SDCA法 [Oko, Suzuki, Wu, Nitanda: ICLR2022] • 無限次元拡張 [Nishikawa, Suzuki, Nitanda: NeurIPS2022] 時間・空間離散化:「二重ループの手法」 空間離散化・連続時間: Uniform-in-time propagation of chaos - Super対数Sobolev不等式 [Suzuki, Nitanda, Wu (ICLR2023)] - Leave-one-out型評価 [Chen, Ren, Wang (arXiv2022)] 時間・空間離散化・確率的勾配: 「一重ループの手法」 難しい:Propagation of chaos (McKean, Kac,…, 60年代より) Suzuki, Wu, Nitanda (arXiv:2306.07221)
  68. 一重ループの方法 98 • 時間離散化: 𝑋𝑡 → 𝑋 𝑘 (𝑖) •

    空間離散化: 𝑁粒子で近似 ( ො 𝜇𝑘 ) [もっとも難しい] • 確率的勾配: 勾配計算を軽量化 ただし かつ (確率的勾配) (空間離散化) (時間離散化)
  69. 収束解析 99 時間 離散化 空間 離散化 確率的 勾配 損失関数の凸性と平滑性の仮定のもと, 𝑝𝜇

    は対数Sobolev不等式を定数𝛼で満たすとする. 定理 (1ステップ更新の減少) : proximal Gibbs measure 既存研究では粒子数は時間に対して指数関数的に依存 [Mei et al., 2018; Javanmard et al., 2019; De Bortoli et al., 2020] 1. 𝐹: 𝒫 → ℝ is convex and has a form of 𝐹 𝜇 = 𝐿 𝜇 + 𝜆1 𝔼𝜇 𝑥 2 . 2. (smoothness) ∇𝛿𝐿 𝜇 𝛿𝜇 𝑥 −∇𝛿𝐿 𝜈 𝛿𝜇 𝑦 ≤ 𝐶(𝑊2 𝜇, 𝜈 + 𝑥 − 𝑦 ) and (boundedness) ∇𝛿𝐿 𝜇 𝛿𝜇 𝑥 ≤ 𝑅. Assumption:
  70. Uniform log-Sobolev inequality 100 𝑋 𝑘 (1) 𝑋 𝑘 (2)

    𝑋 𝑘 (𝑁) 𝒳𝑘 = 𝑋 𝑘 𝑖 𝑖=1 𝑁 ∼ 𝜇 𝑘 𝑁 : Joint distribution of 𝑁 particles. Potential of the joint distribution 𝝁 𝒌 (𝑵) on ℝ𝒅×𝑵 : where (Fisher divergence) where ➢ The finite particle dynamics is the Wasserstein gradient flow that minimizes (Approximate) Uniform log-Sobolev inequality [Chen et al. 2022] Recall [Chen, Ren, Wang. Uniform-in-time propagation of chaos for mean field langevin dynamics. For any 𝑵,
  71. Log Sobolev for Lipschitz cont obj101 Proximal Gibbs measure: Assumption:

    1. Holley—Strook argument: 2. Lipschitz perturbation argument + Miclo’s trick: 𝜇 satisfies the LSI if there exits 𝛼 > 0 such that for any 𝜙 s.t. 𝜇 𝜙2 = 1, it holds that ⇒ ⇒ (Lipschitz continuous) [Bakry & Emery, 1985; Holley & Stroock, 1987] [Cattiaux & Guillin, 2022; Bardet et al., 2018] (New)
  72. 確率的勾配の計算量 102 時間 離散化 空間 離散化 確率的 勾配 SGD-MFLD: (有限和),

    (確率的勾配) 更新回数のバウンド: (Mini-batch size = 𝐵) to achieve 𝜖 + 𝑂(1/(𝜆2 𝛼𝑁)) accuracy. By setting , the iteration complexity becomes ➢ 𝐵 = 𝑛 ∧ 1/(𝜆2 𝛼𝜖) is the optimal mini-batch size. → 𝑘 = 𝑂 Τ log 𝜖−1 𝜖 .
  73. 分散縮小勾配法 103 SVRG-MFLD: 時間 離散化 空間 離散化 確率的 勾配の誤差 (分散縮小勾配)

    ( ሶ 𝑋は𝑚回に一回更新) 線形GLDの既存解析 [Kinoshita, Suzuki: NeurIPS2022] の非線 形への拡張/改善 (有限和), 更新回数: 総勾配計算回数: ただし𝐵 = 𝑚 = 𝑛1/3. 𝑛 in Kinoshita&Suzuki (2022)
  74. 統計的性質 • ℓ𝑖 : ロジスティック損失 • ℎ𝑧 𝑥 = ത

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

    𝑅 ⋅ [tanh 𝑥1 , 𝑧 + 𝑥2 + 𝑥3 ]/2 105 • 𝑘-スパースパリティ問題 ➢ 𝑋 ∼ Unif( −1,1 𝑑) (up to freedom of rotation) ➢ 𝑌 = 𝑋𝑖1 𝑋𝑖2 … 𝑋𝑖𝑘 for 𝑖𝑗 ∈ 𝑑 with 𝑖𝑗 ≠ 𝑖𝑙 . Q: この問題設定でカーネル法を上回る? A: Yes. 特徴学習によって次元への 依存性が改善されている. [Suzuki, Wu, Oko, Nitanda: Feature learning via mean-field Langevin dynamics: classifying sparse parities and beyond. 2023]