オンライン凸最適化の基礎とゲーム理論への応用 (IBIS 2026 チュートリアル)

第29回情報論的学習理論ワークショップ (IBIS2026) チュートリアル
https://ibisml.org/ibis2026/tutorial/#session4

Transcript

1. Slides available at https://tsuchhiii.github.io/ 1 / 50 凸最適化 基礎 理論 土屋 平 / Taira Tsuchiya 東京大学，大阪大学，理研 AIP 2026 年 10 月 26 日，IBIS 2026 @ 応用
2. 2 / 50 土屋 平 / Taira Tsuchiya 略歴 2023 年 9 月 京都大学 大学院情報学研究科 （指導教官：本多淳也 先生） 科学専攻 博士後期課程修了 2023 年 10 月 – 現在 東京大学 大学院情報理工学系研究科 数理情報学専攻 助教 2024 年 4 月 – 現在 理化学研究所 革新知能統合研究 客員研究員 2026 年 10 月 – 現在 大阪大学 大学院基礎工学研究科 (JST BOOST 「適応的 創成専攻 特任助教 凸最適化 機械学習基盤技術 展開」) 研究興味 • 機械学習 • • 関連 数理領域 学習 凸最適化 機械学習関連技術（ 問題，強化学習 ） 理論，最適化 ，
3. 凸最適化 標準的 3 / 50 ？ 凸最適化 目標：x ∗ = arg min f (x) x∈K f x 実行可能領域 K 求
4. 凸最適化 標準的 3 / 50 ？ 凸最適化 目標：x ∗ = arg min f (x) x∈K x1 f x2 x3 x 実行可能領域 K 求
5. 凸最適化 凸最適化 ≈ 標準的 4 / 50 ？ 凸最適化 逐次的 t=1 x1 実行可能領域 K x 定式化
6. 凸最適化 4 / 50 ？ 凸最適化 ≈ 標準的 凸最適化 逐次的 f1 (x1 ) f1 t=1 x1 実行可能領域 K x 定式化
7. 凸最適化 4 / 50 ？ 凸最適化 ≈ 標準的 凸最適化 逐次的 t=2 x2 実行可能領域 K x 定式化
8. 凸最適化 4 / 50 ？ 凸最適化 ≈ 標準的 凸最適化 逐次的 f2 t=2 f2 (x2 ) x2 実行可能領域 K x 定式化
9. 凸最適化 凸最適化 ≈ 標準的 4 / 50 ？ 凸最適化 逐次的 t=3 x3 実行可能領域 K x 定式化
10. 凸最適化 凸最適化 ≈ 標準的 4 / 50 ？ 凸最適化 逐次的 t=3 f3 f3 (x3 ) x3 実行可能領域 K x 定式化
11. 凸最適化 凸最適化 ≈ 標準的 4 / 50 ？ 凸最適化 逐次的 定式化 目標： T X t=1 x 実行可能領域 K ft (xt ) 小
12. 凸最適化 凸最適化 ≈ 標準的 4 / 50 ？ 凸最適化 逐次的 定式化 目標： T X ft (xt ) t=1 比 × 相手 T X t=1 x 実行可能領域 K min ft (x) x∈K 小
13. 凸最適化 凸最適化 ≈ 標準的 4 / 50 ？ 凸最適化 逐次的 定式化 目標： T X ft (xt ) t=1 比 × 相手 T X t=1 x 実行可能領域 K ◦ min x∈K min ft (x) x∈K T X t=1 ft (x) 小
14. 凸最適化 (online convex optimization) At each round t = 1, . . . , T : 1. 凸集合 K ⊂ Rd 行動 xt 選択（K : 実行可能領域） 5 / 50
15. 5 / 50 凸最適化 (online convex optimization) At each round t = 1, . . . , T : 1. 2. 環境 凸集合 K ⊂ Rd 行動 xt 選択（K : 実行可能領域） 凸損失関数 ft : K → R 決定（ Lipschitz 連続）
16. 5 / 50 凸最適化 (online convex optimization) At each round t = 1, . . . , T : 1. 2. 環境 3. 凸集合 K ⊂ Rd 行動 xt 選択（K : 実行可能領域） 凸損失関数 ft : K → R 決定（ Lipschitz 連続） 損失 ft (xt ) 被 ，gt ∈ ∂ft (xt )（ ft ） 観測
17. 5 / 50 凸最適化 (online convex optimization) At each round t = 1, . . . , T : 1. 2. 環境 3. 凸集合 K ⊂ Rd 行動 xt 選択（K : 実行可能領域） 凸損失関数 ft : K → R 決定（ Lipschitz 連続） 損失 ft (xt ) 被 ，gt ∈ ∂ft (xt )（ ft ） 観測
18. 5 / 50 凸最適化 (online convex optimization) At each round t = 1, . . . , T : 1. 2. 環境 3. 凸集合 K ⊂ Rd 行動 xt 選択（K : 実行可能領域） 凸損失関数 ft : K → R 決定（ Lipschitz 連続） 損失 ft (xt ) 目標： 被 RegT RegT = T X ，gt ∈ ∂ft (xt )（ ft ） 観測 最小化 ft (xt ) t=1 累積損失 − min x∈K 最適 T X ft (x) t=1 固定点 累積損失
19. 5 / 50 凸最適化 (online convex optimization) At each round t = 1, . . . , T : 凸集合 K ⊂ Rd 行動 xt 選択（K : 実行可能領域） 凸損失関数 ft : K → R 決定（ Lipschitz 連続） 1. 2. 環境 損失 ft (xt ) 3. 目標： 被 ，gt ∈ ∂ft (xt )（ 最小化 RegT RegT = T X − ft (xt ) t=1 累積損失 • 損失関数 ft 問題 • 標準的 ft ） 観測 gt ∈ R d 用 線形最適化 √ RegT = O( T ) min x∈K T X ft (x) t=1 最適 ft (·) = ⟨gt , ·⟩ 呼 （勾配降下法 固定点 累積損失 ， ）
20. 自然 6 / 50 疑問 Q1. 各時刻 最適解 xt∗ ∈ arg minx∈K ft (x) 例 DynamicRegT = 最小化 方 望 PT 比較 t=1 ft (xt ) − ？ PT t=1 minx∈K ft (x ) ？ • 一般 • DynamicRegT = Ω(T ) 最小化 （ 変種 同様，本 最小化 議論 還元可能 ）
21. 自然 6 / 50 疑問 Q1. 各時刻 最適解 xt∗ ∈ arg minx∈K ft (x) 例 DynamicRegT = 最小化 方 望 DynamicRegT = Ω(T ) 最小化 （ 変種 多 PT t=1 ft (xt ) − ？ PT t=1 minx∈K ft (x ) ？ • 一般 • Q2. 比較 最小化 同様，本 議論 RegT 最小化 役 機械学習 問題 関連 立 還元可能 ） ？ 凸最適化 帰着可能
22. 自然 6 / 50 疑問 Q1. 各時刻 最適解 xt∗ ∈ arg minx∈K ft (x) 例 DynamicRegT = 最小化 方 望 DynamicRegT = Ω(T ) 最小化 （ 変種 多 t=1 ft (xt ) − PT t=1 minx∈K ft (x ) 最小化 同様，本 役 機械学習 問題 関連 任意 還元可能 議論 RegT 最小化 Q3. 過去 観測 依存 • （ • • PT ？ ？ • 一般 • Q2. 比較 立 ） ？ f1 , . . . , fT 凸最適化 帰着可能 考 悲観的 ？ 解析） 考 学習器 設計 必要 応用 各問題 最適（ 存在 適応的 ） 構成可能
23. 凸最適化 機械学習基盤技術 7 / 50 広 確率的凸最適化，非凸最適化（平滑・非平滑） ▷ AdaGrad 開発，Adam(W) 解析，新 optimizer 分類問題・回帰問題 凸最適化 問題，部分観測問題 ▷ 不確実 環境下 逐次的意思決定問題 制御 ▷ 最適制御理論 他： 強化学習， 最適化 融合 最適化，逆最適化， 理論 etc . . . 考案
24. 8 / 50 応用例 1. 確率的凸最適化 凸関数 f (·, ξ) 対 ，F (w ) = Eξ [f (w , ξ)] 例. 二乗損失 用 線形回帰： f (w , (z, y ) ) = (⟨w , z⟩ − y )2 | {z } 入力 最小値 求 問題
25. 8 / 50 応用例 1. 確率的凸最適化 凸関数 f (·, ξ) 対 ，F (w ) = Eξ [f (w , ξ)] 例. 二乗損失 用 線形回帰： f (w , (z, y ) ) = (⟨w , z⟩ − y )2 | {z } 最小値 求 問題 入力 ・ 定理 対 動 変換 (Cesa-Bianchi et al., 2004) 凸最適化 ， " Eξ1 ,...,ξT F 損失関数 ft (w ) := f (w , ξt ) (ξ1 , . . . , ξT ∼ ρ) 1 X wt T T t=1 !# − F (w ∗ ) ≤ Eξ1 ,...,ξT [RegT ] . T 例．確率的勾配降下法 (Zinkevich, 2003)，AdaGrad (McMahan and Streeter, 2010; Duchi et al., 2011)
26. 8 / 50 応用例 1. 確率的凸最適化 凸関数 f (·, ξ) 対 ，F (w ) = Eξ [f (w , ξ)] 例. 二乗損失 用 線形回帰： f (w , (z, y ) ) = (⟨w , z⟩ − y )2 | {z } 最小値 求 問題 入力 ・ 定理 対 動 変換 (Cesa-Bianchi et al., 2004) 凸最適化 ， " Eξ1 ,...,ξT F 損失関数 ft (w ) := f (w , ξt ) (ξ1 , . . . , ξT ∼ ρ) 1 X wt T T t=1 !# − F (w ∗ ) ≤ Eξ1 ,...,ξT [RegT ] . T 例．確率的勾配降下法 (Zinkevich, 2003)，AdaGrad (McMahan and Streeter, 2010; Duchi et al., 2011) 証明（ 場合）．  P  Jensen P RegT T 1 ∗ f T t=1 wt − f (w ∗ ) ≤ T1 T t=1 (f (wt ) − f (w )) ≤ T .
27. 9 / 50 応用例 1. 確率的凸最適化 (cont’d) " Eξ1 ,...,ξT F 1 X wt T T !# − F (w ∗ ) ≤ t=1 直接的 適用 √ • f 凸関数：RegT = O( T ) → 収束 • f µ-強凸： RegT = O( µ1 log T ) → 収束 Eξ1 ,...,ξT [RegT ] . T √ O(1/ T ) O(log(T )/(µT )) 非最適
28. 9 / 50 応用例 1. 確率的凸最適化 (cont’d) " Eξ1 ,...,ξT F 1 X wt T T !# − F (w ∗ ) ≤ t=1 直接的 適用 √ • f 凸関数：RegT = O( T ) → 収束 • f µ-強凸： RegT = O( µ1 log T ) → 収束 適応的 • f • f • ... 凸最適化 µ-強凸 → 収束 用 O(1/(µT )) L-平滑，勾配 分散 σ 2 → 収束 Eξ1 ,...,ξT [RegT ] . T √ O(1/ T ) 非最適 O(log(T )/(µT )) 工夫 最適   O TL2 + √σ T ... 最適
29. 10 / 50 応用例 2. 非凸最適化 （非平滑 / 平滑） 非凸関数 F (w ) 停留点（勾配 大 最適化手法：t = 1, 2, . . . 1. 更新方向 xt 選 小 = 点） 求 問題 例．深層学習 学習器：t = 1, 2, . . . 1. 行動 xt 選 2. wt = wt−1 + xt 更新 2. 損失 ⟨gt , xt ⟩ 3. 確率的勾配 gt 得 3. 損失 ft (x) = ⟨gt , x⟩ 被 観測
30. 10 / 50 応用例 2. 非凸最適化 （非平滑 / 平滑） 非凸関数 F (w ) 停留点（勾配 大 最適化手法：t = 1, 2, . . . 1. 更新方向 xt 選 小 = 点） 求 問題 例．深層学習 学習器：t = 1, 2, . . . 1. 行動 xt 選 2. wt = wt−1 + xt 更新 2. 損失 ⟨gt , xt ⟩ 3. 確率的勾配 gt 得 3. 損失 ft (x) = ⟨gt , x⟩ 被 線形損失 出所：F (wt ) − F (wt−1 ) = F (wt−1 + xt ) − F (wt−1 ) ≈ ⟨gt , xt ⟩ P → 累積損失 t ⟨gt , xt ⟩ ≈ F (wT ) − F (w0 )：損失 小 F 減少 観測
31. 10 / 50 応用例 2. 非凸最適化 （非平滑 / 平滑） 非凸関数 F (w ) 停留点（勾配 大 最適化手法：t = 1, 2, . . . 1. 更新方向 xt 選 小 点） 求 問題 例．深層学習 学習器：t = 1, 2, . . . = 1. 行動 xt 選 2. wt = wt−1 + xt 更新 2. 損失 ⟨gt , xt ⟩ 3. 確率的勾配 gt 得 3. 損失 ft (x) = ⟨gt , x⟩ 被 線形損失 出所：F (wt ) − F (wt−1 ) = F (wt−1 + xt ) − F (wt−1 ) ≈ ⟨gt , xt ⟩ P → 累積損失 t ⟨gt , xt ⟩ ≈ F (wT ) − F (w0 )：損失 小 F 減少 ・非凸変換 (online-to-nonconvex conversion) (Cutkosky et al., 2023)： 小 学習器 更新方向 選 ，停留点 得 • 確率的 非平滑非凸最適化 ，初 最適 達成 • 平滑 関数 最適化 ，確率的・決定的 両方 最適 観測
32. 11 / 50 応用例 2. 非凸最適化 (cont’d) 定理 (very informal, (Cutkosky et al., 2023)) 直近 反復点 平均 w̄ 出力 E∥∇L(w̄ )∥[ρ] | {z } 非平滑非凸最適化 標準的 目標 ≲ 学習器 更新方向 E[RegT ] 1 + + T T √ 選 分散 T . ，
33. 11 / 50 応用例 2. 非凸最適化 (cont’d) 定理 (very informal, (Cutkosky et al., 2023)) 直近 反復点 平均 w̄ 出力 E∥∇L(w̄ )∥[ρ] | {z } ≲ 学習器 更新方向 E[RegT ] 1 + + T T √ 選 分散 T ， . 非平滑非凸最適化 標準的 目標 ・非凸変換 枠組 解析 最適化手法 • 付 SGD (Zhang and Cutkosky, 2024) • Schedule-free SGD (Ahn et al., 2025) • Adam (Ahn et al., 2024) • Muon with finite Newton–Schulz (Li and Tsuchiya, 2026) 新 非凸最適化 考案：弱凸関数，複合最適化，分散最適化，...
34. 応用例 3. d 台 12 / 50 問題 （ ） 1 毎回 1 台 選 2 引 ，累積損失 小 3 4
35. 応用例 3. 12 / 50 問題 d 台 （ 見 ） 損失 毎回 1 台 選 ℓt (2) = 0.8 ? 引 ，累積損失 小 ? ? 例：d = 4，At = 2 1 2 3 4 At each round t = 1, . . . , T : 1. 環境 損失 ℓt ∈ [0, 1]d 決定（ℓt (i )： i 損失） 2. 確率分布 xt ∈ ∆d （∆d ：確率単体） 選 ，xt 3. 損失 ℓt (At ) 被 ，引 損失 従 観測 At 引
36. 応用例 3. 12 / 50 問題 d 台 （ 見 ） 損失 毎回 1 台 選 ℓt (2) = 0.8 ? 引 ，累積損失 小 ? ? 例：d = 4，At = 2 1 2 3 4 At each round t = 1, . . . , T : ℓt ∈ [0, 1]d 1. 環境 損失 決定（ℓt (i )： i 損失） 2. 確率分布 xt ∈ ∆d （∆d ：確率単体） 選 ，xt 3. 損失 ℓt (At ) 目標： RegT = 被 ，引 損失 RegT 最小化 PT  E t=1 ℓt (At ) − mini∈[d] E 累積損失 最適 従 At 観測 PT 固定 t=1 ℓt (i)  累積損失 引
37. 応用例 3. 12 / 50 問題 d 台 （ 見 ） 損失 毎回 1 台 選 ℓt (2) = 0.8 ? 引 ，累積損失 小 ? ? 例：d = 4，At = 2 1 2 3 4 At each round t = 1, . . . , T : ℓt ∈ [0, 1]d 1. 環境 損失 決定（ℓt (i )： i 損失） 2. 確率分布 xt ∈ ∆d （∆d ：確率単体） 選 ，xt 3. 損失 ℓt (At ) 目標： RegT = 被 ，引 損失 RegT 最小化 PT  E t=1 ℓt (At ) − mini∈[d] E 累積損失 期待損失 ⟨ℓt , xt ⟩ → 確率単体 ∆d 上 ℓt 1 成分 見 → 適当 推定量 ℓbt 従 At 観測 PT t=1 ℓt (i)  最適 固定 累積損失 線形最適化（K = ∆d ，gt = ℓt ） gt 利用 引
38. 応用例 3. 適応的 凸最適化 依存 適応的逐次的意思決定方策 上界 1.0 0.8 0.8 0.6 0.6 `ta `ta∗ 1.0 0.4 0.4 0.2 0.2 0 20 40 0.0 0 20 t 40 t 1.0 0.8 0.6 `ta 0.0 13 / 50 問題，部分観測問題 (cont’d) 0.4 0.2 0.0 0 20 40 t 実現
39. 応用例 3. 適応的 凸最適化 依存 適応的逐次的意思決定方策 上界 1.0 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 確率的環境 20 40 0.0 敵対的環境 RegT RegT Exp3 O( T ) 0 20 t √ Exp3 O( T ) 40 t UCB O(log T ) 1.0 T 0.8 両環境最適 0.6 0.4 0.2 0.0 UCB Ω(T ) √ `ta 0 実現 両環境最適 `ta `ta∗ 1.0 0.0 13 / 50 問題，部分観測問題 (cont’d) 0 20 40 t T
40. 応用例 3. 適応的 凸最適化 依存 適応的逐次的意思決定方策 上界 1.0 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 確率的環境 20 40 0.0 敵対的環境 RegT RegT Exp3 O( T ) 0 20 t √ Exp3 O( T ) 40 t UCB O(log T ) 1.0 T 0.8 両環境最適 0.6 0.4 0.2 0.0 UCB Ω(T ) √ `ta 0 実現 両環境最適 `ta `ta∗ 1.0 0.0 13 / 50 問題，部分観測問題 (cont’d) 0 20 40 t T
41. 応用例 4. 14 / 50 強化学習 Markov 決定過程上 学習 ··· s0 ◦：状態 s ∈ S →：行動 a ∈ A （遷移確率 P At each episode t = 1, . . . , T : 1. 環境 損失関数 ℓt : S × A → [0, 1] 決定 2. 方策 πt : S → ∆(A)（状態 3. s0 πt 従 行動 行動 ，訪 確率分布） 決定 (s , a ) 損失 観測 遷移 既知）
42. 応用例 4. 14 / 50 強化学習 ℓt (s2 , a2 ) s2 Markov 決定過程上 学習 s3 s0 ℓt (s0 , a0 ) s1 ℓt (s1 , a1 ) ··· ◦：状態 s ∈ S →：行動 a ∈ A （遷移確率 P At each episode t = 1, . . . , T : 1. 環境 損失関数 ℓt : S × A → [0, 1] 決定 2. 方策 πt : S → ∆(A)（状態 3. s0 πt 従 行動 行動 ，訪 確率分布） 決定 (s , a ) 損失 観測 遷移 既知）
43. 応用例 4. 14 / 50 強化学習 ℓt (s2 , a2 ) s2 Markov 決定過程上 学習 s3 s0 ℓt (s0 , a0 ) s1 ℓt (s1 , a1 ) ◦：状態 s ∈ S →：行動 a ∈ A （遷移確率 P ··· 遷移 既知） At each episode t = 1, . . . , T : 1. 環境 損失関数 ℓt : S × A → [0, 1] 決定 2. 方策 πt : S → ∆(A)（状態 3. s0 πt 目標： 従 行動 行動 ，訪 (s , a ) Reg 最小化 " T T # X E V πt (ℓt ) − RegT = min E π t=1 累積損失 V π (ℓ)：損失 ℓ s0 方策 π 従 確率分布） 決定 最適 1 損失 " T X 観測 # V π (ℓt ) t=1 固定方策 累積損失 期待累積損失（価値関数）
44. 応用例 4. 強化学習 (cont’d) ： 2 青 線：π 線 太 = 線形最適化 帰着 ··· s0 従 経路 例 (s, a) 訪 確率 15 / 50 大域的最適化 (Zimin and Neu, 2013; Jin et al., 2020) 方策 π 決 = 各 (s , a ) 訪 確率 決 V π (ℓ) =「訪 確率 × 損失」 和（線形） →訪 確率 集合（凸多面体）上 線形最適化
45. 応用例 4. ： 2 線形最適化 帰着 ··· s0 青 線：π 線 太 = s0 従 経路 例 (s, a) 訪 確率 0.7 s 15 / 50 強化学習 (cont’d) 0.3 πt (· | s) = (0.7, 0.3) ··· 大域的最適化 (Zimin and Neu, 2013; Jin et al., 2020) 方策 π 決 = 各 (s , a ) 訪 確率 決 V π (ℓ) =「訪 確率 × 損失」 和（線形） →訪 確率 集合（凸多面体）上 線形最適化 方策最適化 (Shani et al., 2020; Luo et al., 2021) 問題 各状態 s = 行動 a，損失 = Q 関数 Qt (s , a) （Qt (s, a)：s a 後 期待累積損失） → 各状態 確率単体 ∆(A) 上 線形最適化
46. 応用例 4. ： 2 線形最適化 帰着 ··· s0 青 線：π 線 太 = s0 従 経路 例 (s, a) 訪 確率 ··· 0.7 s (s , a ) 大域的最適化 (Zimin and Neu, 2013; Jin et al., 2020) 方策 π 決 = 各 (s , a ) 訪 確率 決 V π (ℓ) =「訪 確率 × 損失」 和（線形） →訪 確率 集合（凸多面体）上 線形最適化 方策最適化 (Shani et al., 2020; Luo et al., 2021) 問題 各状態 s = 行動 a，損失 = Q 関数 Qt (s , a) （Qt (s, a)：s a 後 期待累積損失） → 各状態 確率単体 ∆(A) 上 線形最適化 0.3 πt (· | s) = (0.7, 0.3) 訪 15 / 50 強化学習 (cont’d) 損失 見 → 問題 同様 適当 推定量 利用
47. 応用例 5. 後 紹介 最適化， 理論 16 / 50
48. 17 / 50 他 応用例 • 分類問題・回帰問題 • 逆最適化 • 制御 • • 学習器 較正（ • 汎化誤差解析 • 集中不等式 • .... 最適化 ）
49. 凸最適化 広 ，近年 研究対象 （論文 確率的凸最適化，非凸最適化（平滑・非平滑） 分類問題・回帰問題 ） 18 / 50 (LT26, LTY26) (SBTO24, STSY25) 問題，部分観測問題 (ITH22, ITH22, TIH23, TIH23, HIT23, TIH23, KRTVC24, TIH24, ITH24) 凸最適化 制御 (TI24) (IT25) 逆最適化 (SBT25, STBO25) 強化学習 (TIL25, IJLMT25, LTY26, LTY26, LT26) 理論 (TIL25, ILTW25, T26, ZTI26, ITAA26, ILMTW26, T26)
50. 19 / 50 凸最適化
51. 20 / 50 凸最適化（再掲） 逐次的 凸損失関数 得 実行可能領域 行動 選択 環境下 累積損失 最小化 問題 At each round t = 1, . . . , T : 1. 2. 環境 3. 凸集合 K ⊂ Rd xt 凸損失関数 ft : K → R 損失 ft (xt ) 目標： 決定（ Lipschitz 連続） ，gt ∈ ∂ft (xt )（ 被 T X ft (xt ) − t=1 累積損失 損失関数 ft 問題 gt ∈ R d 用 線形最適化 ft ） 観測 最小化 RegT RegT = 選択（K : 実行可能領域） ft (·) = ⟨gt , ·⟩ 呼 ． min x∈K 最適 T X ft (x) t=1 固定点 累積損失 ，
52. 21 / 50 劣勾配降下法 ∥·∥:ℓ2 - ，gt ∈ ∂ft (xt ) 劣勾配降下法：学習率 η 用 xt+1 = PK (xt − ηgt ) , PK (x) = arg min∥z − x∥2 z∈K
53. 21 / 50 劣勾配降下法 ∥·∥:ℓ2 - ，gt ∈ ∂ft (xt ) 劣勾配降下法：学習率 η 用 xt+1 = PK (xt − ηgt ) , PK (x) = arg min∥z − x∥2 z∈K −ηgt xt K xt +1 = PK (xt − η gt )
54. 21 / 50 劣勾配降下法 ∥·∥:ℓ2 - ，gt ∈ ∂ft (xt ) 劣勾配降下法：学習率 η 用 xt+1 = PK (xt − ηgt ) , PK (x) = arg min∥z − x∥2 z∈K −ηgt xt +1 = PK (xt − η gt ) xt K √ 定理 η = D/(G T ) √ ，RegT = O(DG T )（D ：K 直径，∥gt ∥ ≤ G ）
55. 劣勾配降下法 解析 劣勾配降下法：xt+1 = PK (xt − ηgt ) where PK (x) = arg minz∈K ∥z − x∥2 1 step 更新 「最適解」u ∈ K 近 ？ ∥xt − u∥2 − ∥xt+1 − u∥2 > ?? 22 / 50
56. 劣勾配降下法 解析 劣勾配降下法：xt+1 = PK (xt − ηgt ) where PK (x) = arg minz∈K ∥z − x∥2 1 step 更新 「最適解」u ∈ K 近 ？ ∥xt − u∥2 − ∥xt+1 − u∥2 = ∥xt − u∥2 − ∥PK (xt − ηgt ) − u∥2 ∥PK (x) − z∥ ≤ ∥x − z∥ ∀z ∈ K ≥ ∥xt − u∥2 − ∥xt − ηgt − u∥2 = 2⟨ηgt , xt − u⟩ − η 2 ∥gt ∥2 . 22 / 50
57. 劣勾配降下法 解析 22 / 50 劣勾配降下法：xt+1 = PK (xt − ηgt ) where PK (x) = arg minz∈K ∥z − x∥2 1 step 更新 「最適解」u ∈ K 近 ？ ∥xt − u∥2 − ∥xt+1 − u∥2 = ∥xt − u∥2 − ∥PK (xt − ηgt ) − u∥2 ∥PK (x) − z∥ ≤ ∥x − z∥ ∀z ∈ K ≥ ∥xt − u∥2 − ∥xt − ηgt − u∥2 = 2⟨ηgt , xt − u⟩ − η 2 ∥gt ∥2 . 整理 ， ⟨gt , xt − u⟩ ≤ ∥xt − u∥2 − ∥xt+1 − u∥2 η + ∥gt ∥2 . 2η 2 (⋆)
58. 劣勾配降下法 22 / 50 解析 劣勾配降下法：xt+1 = PK (xt − ηgt ) where PK (x) = arg minz∈K ∥z − x∥2 1 step 「最適解」u ∈ K 更新 近 ？ ∥xt − u∥2 − ∥xt+1 − u∥2 = ∥xt − u∥2 − ∥PK (xt − ηgt ) − u∥2 ∥PK (x) − z∥ ≤ ∥x − z∥ ∀z ∈ K ≥ ∥xt − u∥2 − ∥xt − ηgt − u∥2 = 2⟨ηgt , xt − u⟩ − η 2 ∥gt ∥2 . 整理 ， ⟨gt , xt − u⟩ ≤ ∥xt − u∥2 − ∥xt+1 − u∥2 η + ∥gt ∥2 . 2η 2 (⋆) ， RegT (u) = T X t=1 (ft (xt ) − ft (u)) ft T 凸性 X ≤ t=1 T (⋆) ∥x1 − u∥2 η X ⟨gt , xt − u⟩ ≤ + ∥gt ∥2 . 2η 2 t=1
59. 劣勾配降下法 正則化 強 ::::::::::::: RegT (u) ≤ 23 / 50 解析 (cont’d) ∥x1 − u∥2 2η | {z } penalty, 正則化 強 安定性 2 + ηX ∥gt ∥2 2 t=1 | {z } :::::: 項 分解 T stability, 安定性 ：
60. 劣勾配降下法 正則化 強 ::::::::::::: ∥x1 − u∥2 2η | {z } RegT (u) ≤ penalty, 正則化 強 xt+1 = PK (xt − ηgt ) ⇐⇒ 23 / 50 解析 (cont’d) 安定性 2 + ηX ∥gt ∥2 2 t=1 | {z } :::::: 項 分解 ： T stability, 安定性   1 2 xt+1 = arg min ⟨gt , x⟩ + ∥x − xt ∥ 2η x∈K
61. 劣勾配降下法 正則化 強 ::::::::::::: 安定性 2 + ηX ∥gt ∥2 2 t=1 | {z } :::::: ∥x1 − u∥2 2η | {z } RegT (u) ≤ penalty, 正則化 強 xt+1 = PK (xt − ηgt ) ⇐⇒ η= G D √ T 項 分解 ： T stability, 安定性   1 2 xt+1 = arg min ⟨gt , x⟩ + ∥x − xt ∥ 2η x∈K D 2 ηG 2 T + 2η 2 √ → DG T . ≤ 23 / 50 解析 (cont’d) (D: K 直径，G : ft Lipschitz 定数)
62. 24 / 50 下界 √ 上界 RegT = O(DG T ) 劣勾配降下法 定理 任意 凸実行可能領域 K ，任意 f1 , . . . , fT : K → R 存在 ， √ RegT = Ω(DG T ) . （D = supx,y ∈K ∥x − y ∥，∥gt ∥ ≤ G ） 対 最適 ， 損失関数列
63. 24 / 50 下界 √ 上界 RegT = O(DG T ) 劣勾配降下法 定理 任意 凸実行可能領域 K ，任意 f1 , . . . , fT : K → R 存在 ， 対 最適 ， 損失関数列 √ RegT = Ω(DG T ) . （D = supx,y ∈K ∥x − y ∥，∥gt ∥ ≤ G ） Proof sketch. 1 次元方向当 結 （ 定数倍） 選択 還元：K 上 ℓ2 線形最適化 勾配 意味 最 離 一様 2点
64. 24 / 50 下界 √ 上界 RegT = O(DG T ) 劣勾配降下法 定理 任意 凸実行可能領域 K ，任意 f1 , . . . , fT : K → R 存在 ， 対 最適 ， 損失関数列 √ RegT = Ω(DG T ) . （D = supx,y ∈K ∥x − y ∥，∥gt ∥ ≤ G ） Proof sketch. 1 次元方向当 結 （ 定数倍） 選択 Q. 勾配 （ 還元：K 上 ℓ2 線形最適化 勾配 意味 最 離 一様 劣勾配降下法 ，勾配 ∥gt ∥2 ≤ G 問題 ∥gt ∥∞ ≤ G 問題， 問題，強化学習， 理論， 場合 対 最適 ？ 設定 対応） 2点
65. 25 / 50 Hedge ∥gt ∥∞ ≤ G ，実行可能領域 確率単体 P K = ∆d := {x ∈ Rd : x(i) ≥ 0, di=1 x(i) = 1} 学習率 η > 0 場合 特 有効 用 exp(−η Pt  s=1 gs (i)) xt+1 (i) = Pd ∝ exp Pt k=1 exp(−η s=1 gs (k)) −η t X  gs (i) s=1 行動 i 累積損失 ∀i ∈ [d]
66. 25 / 50 Hedge ∥gt ∥∞ ≤ G ，実行可能領域 確率単体 P K = ∆d := {x ∈ Rd : x(i) ≥ 0, di=1 x(i) = 1} 学習率 η > 0 場合 特 有効 用 exp(−η Pt  s=1 gs (i)) xt+1 (i) = Pd ∝ exp Pt k=1 exp(−η s=1 gs (k)) −η t X gs (i) ∀i ∈ [d] s=1 行動 i xt (i) exp(−ηgt (i)) ， xt+1 (i) = , Zt  Zt = d X k=1 累積損失 xt (k) exp(−ηgt (k))
67. 25 / 50 Hedge ∥gt ∥∞ ≤ G ，実行可能領域 確率単体 P K = ∆d := {x ∈ Rd : x(i) ≥ 0, di=1 x(i) = 1} 学習率 η > 0 場合 特 用 exp(−η Pt  s=1 gs (i)) xt+1 (i) = Pd ∝ exp Pt k=1 exp(−η s=1 gs (k)) −η t X xt (i) exp(−ηgt (i)) ， xt+1 (i) = , Zt 定理 η = Zt = 線形最適化 ft (·) = ⟨gt , ·⟩, gt ∈ [0, 1]d p log d/T  gs (i) ∀i ∈ [d] s=1 行動 i 以下， 有効 d X 累積損失 xt (k) exp(−ηgt (k)) k=1 場合 √ ，RegT = O( T log d)（最適） 考
68. Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 1 step 更新 最良 26 / 50 解析 Hedge 行動 i ∗ ∈ [d] 確率 ∗ Pd k=1 xt (k) exp(−ηgt (k)) 変化 ∗ log xt+1 (i ) − log xt (i ) ≥ ?? ？
69. Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 1 step 更新 最良 26 / 50 解析 Hedge 行動 i ∗ ∈ [d] Pd k=1 xt (k) exp(−ηgt (k)) 確率 変化 ？ ∗) ∗ )) x (i exp(−ηg (i t+1 t log xt+1 (i ∗ ) − log xt (i ∗ ) = log = log = −ηgt (i ∗ ) − log Zt xt (i ∗ ) Zt
70. Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 1 step 更新 最良 26 / 50 解析 Hedge 行動 i ∗ ∈ [d] Pd k=1 xt (k) exp(−ηgt (k)) 確率 変化 ？ ∗) ∗ )) x (i exp(−ηg (i t+1 t log xt+1 (i ∗ ) − log xt (i ∗ ) = log = log = −ηgt (i ∗ ) − log Zt xt (i ∗ ) Zt X = −ηgt (i ∗ ) − log xt (k) exp(−ηgt (k)) k
71. Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 1 step 更新 最良 26 / 50 解析 Hedge Pd k=1 xt (k) exp(−ηgt (k)) 行動 i ∗ ∈ [d] 確率 変化 ？ X xt+1 (i ∗ ) log = −ηgt (i ∗ ) − log xt (k) exp(−ηgt (k)) xt (i ∗ ) k
72. Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = Pd k=1 xt (k) exp(−ηgt (k)) 行動 i ∗ ∈ [d] 確率 変化 ？ X xt+1 (i ∗ ) log = −ηgt (i ∗ ) − log xt (k) exp(−ηgt (k)) xt (i ∗ ) k X
    ∗ 2 ≥ −ηgt (i ) − log xt (k) 1 − ηgt (k) + η 2 gt (k)2 exp(−z) ≤ 1 − z + z (z ≥ 0) 1 step 更新 最良 26 / 50 解析 Hedge k
73. Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 更新 最良 26 / 50 解析 Hedge Pd k=1 xt (k) exp(−ηgt (k)) 行動 i ∗ ∈ [d] 確率 変化 ？ X xt+1 (i ∗ ) log = −ηgt (i ∗ ) − log xt (k) exp(−ηgt (k)) xt (i ∗ ) k X
    ∗ 2 ≥ −ηgt (i ) − log xt (k) 1 − ηgt (k) + η 2 gt (k)2 exp(−z) ≤ 1 − z + z (z ≥ 0) 1 step P k k xt (k) = 1，gt (k) ∈ [0, 1] ∗ ≥ −ηgt (i ) − log 1 − η⟨gt , xt ⟩ + η 2
    
74. 26 / 50 解析 Hedge Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 更新 最良 Pd k=1 xt (k) exp(−ηgt (k)) 行動 i ∗ ∈ [d] 確率 変化 ？ X xt+1 (i ∗ ) log = −ηgt (i ∗ ) − log xt (k) exp(−ηgt (k)) xt (i ∗ ) k X
    ∗ 2 ≥ −ηgt (i ) − log xt (k) 1 − ηgt (k) + η 2 gt (k)2 exp(−z) ≤ 1 − z + z (z ≥ 0) 1 step P k k xt (k) = 1，gt (k) ∈ [0, 1] log(1 + z) ≤ z (z > −1) ∗ ≥ −ηgt (i ) − log 1 − η⟨gt , xt ⟩ + η 2 ≥ −ηgt (i ∗ ) + η⟨gt , xt ⟩ − η 2 .
    
75. 26 / 50 解析 Hedge Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 更新 最良 Pd k=1 xt (k) exp(−ηgt (k)) 行動 i ∗ ∈ [d] 確率 変化 ？ X xt+1 (i ∗ ) log = −ηgt (i ∗ ) − log xt (k) exp(−ηgt (k)) xt (i ∗ ) k X
    ∗ 2 ≥ −ηgt (i ) − log xt (k) 1 − ηgt (k) + η 2 gt (k)2 exp(−z) ≤ 1 − z + z (z ≥ 0) 1 step P k k xt (k) = 1，gt (k) ∈ [0, 1] log(1 + z) ≤ z (z > −1) 整理 ， ∗ ≥ −ηgt (i ) − log 1 − η⟨gt , xt ⟩ + η 2
    ≥ −ηgt (i ∗ ) + η⟨gt , xt ⟩ − η 2 . ⟨gt , xt ⟩ − gt (i ∗ ) ≤ xt+1 (i ∗ ) 1 log +η. η xt (i ∗ ) (⋆)
76. 26 / 50 解析 Hedge Hedge: xt+1 (i) = xt (i) exp(−ηgt (i))/Zt where Zt = 更新 最良 Pd k=1 xt (k) exp(−ηgt (k)) 行動 i ∗ ∈ [d] 確率 変化 ？ X xt+1 (i ∗ ) log = −ηgt (i ∗ ) − log xt (k) exp(−ηgt (k)) xt (i ∗ ) k X
    ∗ 2 ≥ −ηgt (i ) − log xt (k) 1 − ηgt (k) + η 2 gt (k)2 exp(−z) ≤ 1 − z + z (z ≥ 0) 1 step P k k xt (k) = 1，gt (k) ∈ [0, 1] log(1 + z) ≤ z (z > −1) 整理 ， ， ∗ ≥ −ηgt (i ) − log 1 − η⟨gt , xt ⟩ + η 2
    ≥ −ηgt (i ∗ ) + η⟨gt , xt ⟩ − η 2 . ⟨gt , xt ⟩ − gt (i ∗ ) ≤ xt+1 (i ∗ ) 1 log +η. η xt (i ∗ ) (⋆) (⋆) 1 p xT +1 (i ∗ ) log d O( T log d) . RegT ≤ log + ηT ≤ + ηT √→ ∗ η x1 (i ) η η= log d/T
77. 27 / 50 準備：Bregman 狭義凸実数値関数 ψ Bregman 誘導 : Dψ (x, y ) = ψ(x) − (ψ(y ) + ⟨∇ψ(y ), x − y ⟩) ψ(z) Dψ (x, y ) ψ(y ) + ⟨∇ψ(y ), z − y ⟩ y x z
78. 27 / 50 準備：Bregman 狭義凸実数値関数 ψ Bregman 誘導 : Dψ (x, y ) = ψ(x) − (ψ(y ) + ⟨∇ψ(y ), x − y ⟩) ψ(z) 例： 1. ψ(x) = 12 ∥x∥2 → Dψ (x, y ) = 12 ∥x − y ∥2 P 2. ψ(x) = di=1 x(i) log x(i), x ∈ ∆d (negative) Shannon → Dψ (x, y ) = d X i=1  x(i) x(i) log y (i) KL  =: KL(x, y ) Dψ (x, y ) ψ(y ) + ⟨∇ψ(y ), z − y ⟩ y x z
79. 自然 28 / 50 拡張 劣勾配降下法： xt+1 = PK (xt − η gt ) ⇐⇒ n o 1 xt+1 = arg minx∈K ⟨gt , x ⟩ + 2η ∥x − xt ∥2 ∥x1 − u ∥2 ηX + ∥gt ∥2identity matrix 2η 2 T RegT (u ) ≤ t=1
80. 自然 28 / 50 拡張 劣勾配降下法： xt+1 = PK (xt − η gt ) ⇐⇒ n o 1 xt+1 = arg minx∈K ⟨gt , x ⟩ + 2η ∥x − xt ∥2 ∥x1 − u ∥2 ηX + ∥gt ∥2identity matrix 2η 2 T RegT (u ) ≤ t=1 Hedge ：   P xt+1 (i ) ∝ exp −η ts=1 gs (i ) ⇐⇒ n o xt+1 = arg minx∈∆d ⟨gt , x ⟩ + η1 KL(x , xt ) XX X KL(ei ∗ , x1 ) log d +η x t (i )g t (i )2 = +η ∥gt ∥2(∇2 −H(xt ))−1 η η T RegT (ei ∗ ) ≲ ∀ i ∈ [d ] d t=1 i=1 T t=1 (∥x∥A = √ x ⊤ Ax)
81. 自然 28 / 50 拡張 劣勾配降下法： xt+1 = PK (xt − η gt ) ⇐⇒ n o 1 xt+1 = arg minx∈K ⟨gt , x ⟩ + 2η ∥x − xt ∥2 ∥x1 − u ∥2 ηX + ∥gt ∥2identity matrix 2η 2 T RegT (u ) ≤ t=1 ： Hedge   P xt+1 (i ) ∝ exp −η ts=1 gs (i ) ⇐⇒ n o xt+1 = arg minx∈∆d ⟨gt , x ⟩ + η1 KL(x , xt ) XX X KL(ei ∗ , x1 ) log d +η x t (i )g t (i )2 = +η ∥gt ∥2(∇2 −H(xt ))−1 η η T RegT (ei ∗ ) ≲ ∀ i ∈ [d ] d T t=1 i=1 ？？？ xt+1 = arg min ⟨gt , x ⟩ + ?? =⇒ √ t=1 ：  x∈K (∥x∥A =  1 Dψ ( x , x t ) , η Dψ (x , y ) = ψ(x ) − ψ(y ) − ⟨∇ψ(y ), x − y ⟩ ?? Dψ (u , x1 ) RegT (u ) ≤ η +η T X t=1 ∥gt ∥2(∇2 ψ(xt ))−1 x ⊤ Ax)
82. 鏡像降下法 (online mirror descent) 鏡像降下法  xt+1 = arg min η⟨gt , x ⟩ + Dψ (x , xt ) , x∈K Dψ (x , y ) = ψ(x ) − ψ(y ) − ⟨∇ψ(y ), x − y ⟩ 29 / 50
83. 鏡像降下法 (online mirror descent) 鏡像降下法  xt+1 = arg min η⟨gt , x ⟩ + Dψ (x , xt ) , Dψ (x , y ) = ψ(x ) − ψ(y ) − ⟨∇ψ(y ), x − y ⟩ x∈K 解析 流 • • Hedge 復習 劣勾配降下法：∥xt − u ∥2 − ∥xt+1 − u ∥2 > ?? ：log xt+1 (i ∗ ) − log xt (i ∗ ) = KL(ei ∗ , xt+1 ) − KL(ei ∗ , xt ) ≥ ?? 29 / 50
84. 29 / 50 鏡像降下法 (online mirror descent) 鏡像降下法  xt+1 = arg min η⟨gt , x ⟩ + Dψ (x , xt ) , Dψ (x , y ) = ψ(x ) − ψ(y ) − ⟨∇ψ(y ), x − y ⟩ x∈K 同様 改善量 Dψ (u , xt ) − Dψ (u , xt+1 ) ≥ ?? 1 RegT (u ) ≤ 評価  T  Dψ (u , x1 ) X 1 + ⟨gt , xt − xt+1 ⟩ − Dψ (xt+1 , xt ) η η t=1 Hölder, Taylor T  Dψ (u , x1 ) X 1 + ∥gt ∥(∇2 ψ(zt ))−1 ∥xt − xt+1 ∥∇2 ψ(zt ) − ∥xt − xt+1 ∥2∇2 ψ(zt ) ≤ η 2η t=1 T Dψ (u , x1 ) η X ≤ + ∥gt ∥2(∇2 ψ(zt ))−1 , η 2 | {z } | t=1 {z } penalty stability zt ∈ [xt , xt+1 ]
85. 29 / 50 鏡像降下法 (online mirror descent) 鏡像降下法  xt+1 = arg min η⟨gt , x ⟩ + Dψ (x , xt ) , Dψ (x , y ) = ψ(x ) − ψ(y ) − ⟨∇ψ(y ), x − y ⟩ x∈K 同様 改善量 Dψ (u , xt ) − Dψ (u , xt+1 ) ≥ ?? 1 RegT (u ) ≤ 評価  T  Dψ (u , x1 ) X 1 + ⟨gt , xt − xt+1 ⟩ − Dψ (xt+1 , xt ) η η t=1 Hölder, Taylor T  Dψ (u , x1 ) X 1 + ∥gt ∥(∇2 ψ(zt ))−1 ∥xt − xt+1 ∥∇2 ψ(zt ) − ∥xt − xt+1 ∥2∇2 ψ(zt ) ≤ η 2η t=1 T Dψ (u , x1 ) η X ≤ + ∥gt ∥2(∇2 ψ(zt ))−1 , η 2 | {z } | t=1 {z } penalty zt ∈ [xt , xt+1 ] stability 学習率 大 制御→ 問題 ，正則化関数 ψ（ Hessian） 理論，強化学習 有効 安定性 :::::
86. 30 / 50 前半 問題設定 逐次的 目標 凸損失関数 （ 得 環境 ，実行可能領域 点 選 問題 累積損失 − 最適 固定点 累積損失） 最小化 劣勾配降下法，Hedge （Follow-the-Regularized-Leader (FTRL) 多 → 理論 問題 ， 凸最適化 凸最適化 鏡像降下法 重要！） 帰着 最適 適応的 性能 達成 応用 損失関数 定 環境 学習 場合 ？
87. 復習： 理論 確率単体 ∆d 上 各時刻 t xt ∈ ∆ d 応用 31 / 50 使 事実 線形最適化 選 ，損失 ℓt ∈ [0, 1]d（利得 gt ∈ [0, 1]d ） 観測 ： 損失 場合 RegT = T X ⟨ℓt , xt ⟩ − min x∈∆d t=1 利得 場合 RegT = max x∈∆d Hedge xt (i) ∝ exp −η t−1 X s=1 T X ⟨gt , x⟩ − t=1 ：学習率 ! η>0 用 ℓs (i) （損失） xt (i) ∝ exp +η T X ⟨ℓt , x⟩ t=1 T X ⟨gt , xt ⟩ t=1 t−1 X s=1 ! gs (i) （利得） √ → RegT = O( T log d)（最適） ∀i ∈ [d]
88. 32 / 50 凸最適化 理論
89. 2人 和 (two-player zero-sum games) 利得行列 A ∈ [−1, 1]mx ×my 定 2人 和 x ，y 行動 数） （mx ，my ： 33 / 50
90. 2人 和 33 / 50 (two-player zero-sum games) 利得行列 A ∈ [−1, 1]mx ×my 定 2人 和 x ，y 行動 数） （mx ，my ： 1. x ，y 同時 戦略 x ∈ ∆mx ，y ∈ ∆my （∆m = {x ∈ [0, 1]m : ∥x∥1 = 1}：(m − 1) 次元 確率単体） 選択
91. 2人 和 33 / 50 (two-player zero-sum games) 利得行列 A ∈ [−1, 1]mx ×my 定 2人 和 x ，y 行動 数） （mx ，my ： 1. x ，y 同時 戦略 x ∈ ∆mx ，y ∈ ∆my （∆m = {x ∈ [0, 1]m : ∥x∥1 = 1}：(m − 1) 次元 2. x y 確率単体） 期待利得 x ⊤ Ay 得 ， 損失 x ⊤ Ay 被 （ 和） 選択
92. 2人 和 33 / 50 (two-player zero-sum games) 利得行列 A ∈ [−1, 1]mx ×my 定 2人 和 x ，y 行動 数） （mx ，my ： 1. x ，y 同時 戦略 x ∈ ∆mx ，y ∈ ∆my （∆m = {x ∈ [0, 1]m : ∥x∥1 = 1}：(m − 1) 次元 2. x y 選択 確率単体） 期待利得 x ⊤ Ay 得 ， 損失 x ⊤ Ay 被 （ 和） i ∈ [mx ] := {1, . . . , mx } 対 x = ei 戦略 x 純粋戦略 呼 ．
93. 2人 34 / 50 和 例. y 利得行列 x 0, 0 1, −1 −1, 1 −1, 1 0, 0 1, −1 1, −1 −1, 1 0, 0   0 1 −1 1 A = −1 0 1 −1 0
94. 35 / 50 Nash 均衡 Nash 均衡： ，自分 戦略 変 得 戦略 組
95. 35 / 50 Nash 均衡 Nash 均衡： ，自分 戦略 変 得 定義 行動集合 [mx ]，[my ] 上 確率分布 組 (x ∗ , y ∗ ) ，次 成 立 ： x ⊤ Ay ∗ − ε ≤ x ∗ ⊤ Ay ∗ ≤ x ∗ ⊤ Ay + ε ε=0 成立 単 Nash 均衡 呼 戦略 ε-近似 Nash 均衡 ∀x ∈ ∆mx , y ∈ ∆my . 組
96. 35 / 50 Nash 均衡 Nash 均衡： ，自分 戦略 変 得 定義 行動集合 [mx ]，[my ] 上 確率分布 組 (x ∗ , y ∗ ) ，次 成 立 ： x ⊤ Ay ∗ − ε ≤ x ∗ ⊤ Ay ∗ ≤ x ∗ ⊤ Ay + ε ε=0 成立 単 例 相手 等確率 組 ε-近似 Nash 均衡 ∀x ∈ ∆mx , y ∈ ∆my . Nash 均衡 呼 ，x = (1/3, 1/3, 1/3), y = (1/3, 1/3, 1/3) 出 戦略 ，何 出 期待利得 0 → 自分 組 変 Nash 均衡 得
97. 36 / 50 Nash 均衡？ 1. Nash 均衡 = maxx miny x ⊤ Ay 例：GAN， 最適化 解 解 一致 最適化，制約付 最適化（ 双対），...
98. 36 / 50 Nash 均衡？ 1. Nash 均衡 = maxx miny x ⊤ Ay 例：GAN， 2. 込 最適化 解 解 一致 最適化，制約付 最適化（ 戦略 得 双対），... Nash 均衡 戦略 x ∗ ，相手 何 利得 x ∗ ⊤ Ay ∗ 以上 保証（定義 右 不等式） 例： AI 近似 Nash 均衡 戦略 勝利 (Brown and Sandholm, 2018)
99. 36 / 50 Nash 均衡？ 1. Nash 均衡 = 最適化 解 maxx miny x ⊤ Ay 解 一致 最適化，制約付 最適化（ 例：GAN， 2. 込 戦略 双対），... 得 Nash 均衡 戦略 x ∗ ，相手 何 利得 x ∗ ⊤ Ay ∗ 以上 保証（定義 右 不等式） 例： AI 近似 Nash 均衡 戦略 勝利 (Brown and Sandholm, 2018) 3. 安定 状態 表 誰 自分 例： 戦略 変 ・交通・市場 状態 = 相互作用 ，複数 主体 関 帰結 予測 系 予測 制度設計 基準点
100. 36 / 50 Nash 均衡？ 1. Nash 均衡 = 最適化 解 maxx miny x ⊤ Ay 解 一致 最適化，制約付 最適化（ 例：GAN， 2. 込 戦略 双対），... 得 Nash 均衡 戦略 x ∗ ，相手 何 利得 x ∗ ⊤ Ay ∗ 以上 保証（定義 右 不等式） 例： AI 近似 Nash 均衡 戦略 勝利 (Brown and Sandholm, 2018) 3. 安定 状態 表 誰 自分 例： 戦略 変 ・交通・市場 状態 = 相互作用 ，複数 主体 関 Q. Nash 均衡 → 最小化 求 帰結 予測 系 予測 制度設計 ？ 自己対戦 基準点
101. 37 / 50 学習 (learning in games) 学習 複数 過去 観測 同一 戦略 環境 更新 相互作用 繰 返 ， 解析 分野
102. 37 / 50 学習 (learning in games) 学習 複数 過去 幅広 • 観測 同一 戦略 環境 更新 相互作用 繰 返 ， 解析 分野 応用 最適化 （例. maxx miny x ⊤ Ay ，concave–convex f • 強化学習 • AI (poker, Stratego, ...) • LLM • ... 対 maxx miny f (x, y )）
103. 2人 和 利得行列 A ∈ [−1, 1]mx ×my At each round t = 1, . . . , T : 1. 38 / 50 学習 x ，y 未知 （mx ，my ： x ，y 行動 数） （∆m = {x ∈ [0, 1]m : ∥x∥1 = 1}：(m − 1) 次元 確率単体） 戦略 x (t) ∈ ∆mx ，y (t) ∈ ∆my 選択
104. 2人 和 38 / 50 学習 利得行列 A ∈ [−1, 1]mx ×my At each round t = 1, . . . , T : 未知 （mx ，my ： x ，y 行動 数） （∆m = {x ∈ [0, 1]m : ∥x∥1 = 1}：(m − 1) 次元 確率単体） 戦略 x (t) ∈ ∆mx ，y (t) ∈ ∆my 1. x ，y 2. x 利得 ⟨x (t) , Ay (t) ⟩ = ⟨x (t) , g (t) ⟩ 得 ， y 損失 ⟨x (t) , Ay (t) ⟩ = ⟨y (t) , ℓ(t) ⟩ 被 （ 選択 和）
105. 2人 和 38 / 50 学習 利得行列 A ∈ [−1, 1]mx ×my 未知 At each round t = 1, . . . , T : （mx ，my ： 戦略 x (t) ∈ ∆mx ，y (t) ∈ ∆my x ，y 2. x 利得 ⟨x (t) , Ay (t) ⟩ = ⟨x (t) , g (t) ⟩ 得 ， y 損失 ⟨x (t) , Ay (t) ⟩ = ⟨y (t) , ℓ(t) ⟩ 被 （ g (t) = Ay (t) (gain) ， x y 期待利得 期待損失 行動 数） （∆m = {x ∈ [0, 1]m : ∥x∥1 = 1}：(m − 1) 次元 確率単体） 1. 3. x ，y ℓ(t) = A⊤ x (t) 観測 選択 和） maxx miny ⟨x, Ay ⟩
106. 2人 和 利得行列 A ∈ [−1, 1]mx ×my 未知 At each round t = 1, . . . , T : （mx ，my ： 戦略 x (t) ∈ ∆mx ，y (t) ∈ ∆my x ，y 2. x 利得 ⟨x (t) , Ay (t) ⟩ = ⟨x (t) , g (t) ⟩ 得 ， y 損失 ⟨x (t) , Ay (t) ⟩ = ⟨y (t) , ℓ(t) ⟩ 被 （ g (t) = Ay (t) (gain) ， x y 期待利得 期待損失 ，確率単体上 x ，y ℓ(t) = A⊤ x (t) 観測 選択 和） maxx miny ⟨x, Ay ⟩ 線形最適化 解 PT PT ∗ (t) (t) (t) RegT x = maxx ∗ ∈∆mx t=1 ⟨x , g ⟩ − t=1 ⟨x , g ⟩ RegT y = PT t=1 ⟨y 行動 数） （∆m = {x ∈ [0, 1]m : ∥x∥1 = 1}：(m − 1) 次元 確率単体） 1. 3. 各 38 / 50 学習 (t) , ℓ(t) ⟩ − min ∗ y ∈∆my PT t=1 ⟨y ∗ , ℓ(t) ⟩
107. 最小化 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 39 / 50
108. 最小化 39 / 50 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 証明．以下 ⟨x, AȳT ⟩ − 示 十分 T RegT x + Regy T ≤ ⟨x̄T , AȳT ⟩ ≤ ⟨x̄T , Ay ⟩ + T RegT x + Regy T ∀x ∈ ∆mx , y ∈ ∆my
109. 最小化 39 / 50 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 証明． 定義 ， X 1 X 1 ⟨x̄T , AȳT ⟩ = ⟨x̄T , Ay (t) ⟩ ≤ max ⟨x ∗ , Ay (t) ⟩ T T x∗ T T t=1 t=1
110. 最小化 39 / 50 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 証明． 定義 ， X 1 X 1 ⟨x̄T , AȳT ⟩ = ⟨x̄T , Ay (t) ⟩ ≤ max ⟨x ∗ , Ay (t) ⟩ T T x∗ T T t=1 RegTx = maxx ∗ PT ∗ (t) ⟩− t=1 ⟨x , Ay PT (t) , Ay (t) ⟩ t=1 ⟨x t=1 = 1 T T X t=1 ⟨x (t) , Ay (t) ⟩ + RegT x T
111. 最小化 39 / 50 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 証明． 定義 ， X 1 X 1 ⟨x̄T , AȳT ⟩ = ⟨x̄T , Ay (t) ⟩ ≤ max ⟨x ∗ , Ay (t) ⟩ T T x∗ T T t=1 RegTx = maxx ∗ PT ∗ (t) ⟩− t=1 ⟨x , Ay PT (t) , Ay (t) ⟩ t=1 ⟨x P P RegTy = Tt=1 ⟨y (t) , A⊤ x (t) ⟩ − miny ∗ Tt=1 ⟨y ∗ , A⊤ x (t) ⟩ t=1 = 1 T T X ⟨x (t) , Ay (t) ⟩ + t=1 RegT x T T X RegxT + RegT 1 y (t) ∗ ⟨x , Ay ⟩ + = min T y∗ T t=1
112. 最小化 39 / 50 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 証明． 定義 ， X 1 X 1 ⟨x̄T , AȳT ⟩ = ⟨x̄T , Ay (t) ⟩ ≤ max ⟨x ∗ , Ay (t) ⟩ T T x∗ T T t=1 RegTx = maxx ∗ PT ∗ (t) ⟩− t=1 ⟨x , Ay t=1 PT (t) , Ay (t) ⟩ t=1 ⟨x P P RegTy = Tt=1 ⟨y (t) , A⊤ x (t) ⟩ − miny ∗ Tt=1 ⟨y ∗ , A⊤ x (t) ⟩ = 1 T T X ⟨x (t) , Ay (t) ⟩ + t=1 RegT x T T X RegxT + RegT 1 y (t) ∗ ⟨x , Ay ⟩ + = min T y∗ T t=1 x̄T 定義 = min ⟨x̄T , Ay ∗ ⟩ + ∗ y T RegT x + Regy . T
113. 最小化 39 / 50 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 • 使 • 各 x ，y ，Nash 均衡 自分 観測 √ O(√ T ) O(1/ T ) 更新 標準的 収束 保証！ 凸最適化
114. 最小化 39 / 50 Nash 均衡 PT 1 PT (t) (t) 定理 (Freund and Schapire, 1999) 戦略 平均 x̄T = T1 t=1 x ，ȳT = T t=1 y T T 直積分布 (x̄T , ȳT ) ((Regx + Regy )/T )-近似 Nash 均衡 • 使 • 各 √ O(√ T ) O(1/ T ) x ，y ，Nash 均衡 自分 Q. 「 観測 標準的 収束 保証！ 凸最適化 更新 学習」 （↔ 一般 ， 最適 凸最適化） ？
115. 高速 40 / 50 収束 √ （g (t) = Ay (t) ，ℓ(t) = A⊤ x (t) ）： ηx , ηy ≃ 1/ T ：学習率  X    t−1 t−1 X (t) (t) x (i) ∝ exp ηx gs (i) ∀i ∈ [mx ] , y (i) ∝ exp −ηy ℓs (i) ∀i ∈ [my ] Hedge s=1 s=1 行動 i 累積利得 行動 i 累積損失 → Nash 均衡 √ e O(1/ T) 収束 / /
116. 高速 40 / 50 収束 √ （g (t) = Ay (t) ，ℓ(t) = A⊤ x (t) ）： ηx , ηy ≃ 1/ T ：学習率  X    t−1 t−1 X (t) (t) x (i) ∝ exp ηx gs (i) ∀i ∈ [mx ] , y (i) ∝ exp −ηy ℓs (i) ∀i ∈ [my ] Hedge s=1 s=1 行動 i 累積利得 行動 i 累積損失 → Nash 均衡 収束 / / (Rakhlin and Sridharan, 2013; Syrgkanis et al., 2015)： optimistic Hedge x (t) (i) ∝ exp ηx √ e O(1/ T) t−1 X s=1 !! gs (i) + gt−1 (i) , y (t) (i) ∝ exp −ηy t−1 X s=1 ℓs (i) + ℓt−1 (i) !!
117. 高速 (Rakhlin and Sridharan, 2013; Syrgkanis et al., 2015)： optimistic Hedge x (t) (i) ∝ exp ηx 40 / 50 収束 t−1 X !! gs (i) + gt−1 (i) , y (t) (i) ∝ exp −ηy s=1 !! ℓs (i) + ℓt−1 (i) s=1 定理 (Rakhlin and Sridharan, 2013) η = ηx = ηy = 1/4 従 ， → Nash 均衡 t−1 X x ，y 完全 optimistic Hedge with RegT x = O(log(mx my )) , RegT y = O(log(mx my )). e O(1/T ) 得 収束 ． 直観：相手 （勾配降下法 ） 最小化 次 戦略 y (t+1) （ 勾配 g (t+1) = Ay (t+1) ） 予測 （T 最適！） 使 ，相手
118. 証明（ optimistic Hedge 1） 標準的 解析 （細 定数 省略） 41 / 50
119. 証明（ optimistic Hedge 1） 標準的 定数 41 / 50 省略） 解析 RegT x = ∗max x ∈∆mx ≤ （細 ( T X ⟨x , g t=1 T X log mx +η η ∗ t=1 (t) ⟩− T X ) ⟨x (t) ,g (t) ⟩ t=1 1 X (t+1) ∥x − x (t) ∥21 4η T ∥g (t) − g (t−1) ∥2∞ − optimistic t=1
120. 証明（ optimistic Hedge 1） 標準的 定数 41 / 50 省略） 解析 RegT x = ∗max x ∈∆mx ≤ （細 ( T X ⟨x , g t=1 T X log mx +η η ∗ t=1 (t) ⟩− T X ) ⟨x (t) ,g (t) ⟩ t=1 1 X (t+1) ∥x − x (t) ∥21 4η T ∥g (t) − g (t−1) ∥2∞ − optimistic t=1 第2項 ∥g (t) − g (t−1) ∥2∞ = ∥A(y (t) − y (t−1) )∥2∞ = max |⟨A(k , ·), y (t) − y (t−1) ⟩|2 ≤ ∥y (t) − y (t−1) ∥21 . k∈[mx ]
121. 証明（ 1） 標準的 optimistic Hedge 定数 41 / 50 省略） 解析 RegT x = ∗max x ∈∆mx ≤ （細 ( T X ∗ ⟨x , g t=1 T X log mx +η η (t) ⟩− T X ) ⟨x (t) ,g (t) ⟩ t=1 1 X (t+1) ∥x − x (t) ∥21 4η T ∥g (t) − g (t−1) ∥2∞ − t=1 optimistic t=1 第2項 ∥g (t) − g (t−1) ∥2∞ = ∥A(y (t) − y (t−1) )∥2∞ = max |⟨A(k , ·), y (t) − y (t−1) ⟩|2 ≤ ∥y (t) − y (t−1) ∥21 . k∈[mx ] 2 不等式 合 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 η 4η T T t=1 t=1
122. 証明（ 42 / 50 2） 前 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 . η 4η T T t=1 t=1 (★-x)
123. 証明（ 42 / 50 2） 前 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 . η 4η (★-x) X (t) log my 1 X (t+1) +η ∥x − x (t−1) ∥21 − ∥y − y (t) ∥21 . η 4η (★-y) T T t=1 t=1 同様 RegT y ≤ T T t=1 t=1
124. 証明（ 42 / 50 2） 前 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 . η 4η (★-x) X (t) log my 1 X (t+1) +η ∥x − x (t−1) ∥21 − ∥y − y (t) ∥21 . η 4η (★-y) T T t=1 t=1 同様 RegT y ≤ 2 不等式 足 ， log(mx my ) T RegT + x + Regy ≤ η T T t=1 t=1   1 η− 4η | {z } =−3/4（η = 1/4 T X t=1 ） ∥x (t) − x (t−1) ∥21 + T X t=1 ! ∥y (t) − y (t−1) ∥21
125. 証明（ 42 / 50 2） 前 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 . η 4η (★-x) X (t) log my 1 X (t+1) +η ∥x − x (t−1) ∥21 − ∥y − y (t) ∥21 . η 4η (★-y) T T t=1 t=1 同様 RegT y ≤ 2 不等式 足 ， T T t=1 t=1   1 η− 4η | {z } log(mx my ) T RegT + x + Regy ≤ η T X t=1 =−3/4（η = 1/4 η = 1/4 （η − 1/(4η) < 0 ） ）， ∥x (t) − x (t−1) ∥21 + T X t=1 ! ∥y (t) − y (t−1) ∥21
126. 証明（ 42 / 50 2） 前 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 . η 4η (★-x) X (t) log my 1 X (t+1) +η ∥x − x (t−1) ∥21 − ∥y − y (t) ∥21 . η 4η (★-y) T T t=1 t=1 同様 RegT y ≤ 2 不等式 足 ， T T t=1 t=1   1 η− 4η | {z } log(mx my ) T RegT + x + Regy ≤ η T X t=1 =−3/4（η = 1/4 η = 1/4 （η − 1/(4η) < 0 ∥x (t) − x (t−1) ∥21 + T X ! ∥y (t) − y (t−1) ∥21 t=1 ） ）， T RegT x + Regy ≥ 0 注意 ，
127. 証明（ 42 / 50 2） 前 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 . η 4η (★-x) X (t) log my 1 X (t+1) +η ∥x − x (t−1) ∥21 − ∥y − y (t) ∥21 . η 4η (★-y) T T t=1 t=1 同様 RegT y ≤ 2 不等式 足 ， T T t=1 t=1   1 η− 4η | {z } log(mx my ) T RegT + x + Regy ≤ η T X t=1 =−3/4（η = 1/4 η = 1/4 （η − 1/(4η) < 0 T X t=1 ∥x (t) − x (t−1) ∥21 + t=1 − x (t−1) ∥21 + T X ! ∥y (t) − y (t−1) ∥21 t=1 ） ）， T X ∥x (t) T RegT x + Regy ≥ 0 ∥y (t) − y (t−1) ∥21 ≤ O (log(mx my )) . 注意 ，
128. 証明（ 42 / 50 2） 前 RegT x ≤ X (t) log mx 1 X (t+1) +η ∥y − y (t−1) ∥21 − ∥x − x (t) ∥21 . η 4η (★-x) X (t) log my 1 X (t+1) +η ∥x − x (t−1) ∥21 − ∥y − y (t) ∥21 . η 4η (★-y) T T t=1 t=1 同様 RegT y ≤ 不等式 2 足 ， T T t=1 t=1   1 η− 4η | {z } log(mx my ) T RegT + x + Regy ≤ η T X t=1 =−3/4（η = 1/4 η = 1/4 （η − 1/(4η) < 0 T X ∥x (t) − x (t−1) ∥21 + t=1 (★-x)，(★-y) − x (t−1) ∥21 + T X ! ∥y (t) − y (t−1) ∥21 t=1 ） ）， T X ∥x (t) T RegT x + Regy ≥ 0 注意 ， ∥y (t) − y (t−1) ∥21 ≤ O (log(mx my )) . t=1 合 T ，RegT x = O (log(mx my ))，Regy = O (log(mx my )) 得 ．
129. 最近 研究紹介 詳細：tsuchhiii.github.io/pdf/slide/20260508-umilan-riken.pdf 定理（再掲） 利得行列 A ∈ [−1, 1]mx ×my ， optimistic Hedge（with 定数学習率 ηx = ηy = 1/4） 用 O(log(mx my )/T )-近似 Nash 均衡 得 （T 良 結果 見 Q1 行動数 mx , my … 依存 最適？ x ，y ，T 43 / 50 完全 後 最適 (Daskalakis et al., 2011)）
130. 最近 研究紹介 詳細：tsuchhiii.github.io/pdf/slide/20260508-umilan-riken.pdf 定理（再掲） 利得行列 A ∈ [−1, 1]mx ×my ， optimistic Hedge（with 定数学習率 ηx = ηy = 1/4） 用 O(log(mx my )/T )-近似 Nash 均衡 得 （T 良 結果 見 Q1 行動数 mx , my Q2 相手 裏切 x ，y ，T （指定 最適？ 従 完全 後 最適 (Daskalakis et al., 2011)） … 依存 43 / 50 ）場合 ？
131. 最近 研究紹介 詳細：tsuchhiii.github.io/pdf/slide/20260508-umilan-riken.pdf 定理（再掲） 利得行列 A ∈ [−1, 1]mx ×my ， optimistic Hedge（with 定数学習率 ηx = ηy = 1/4） 用 O(log(mx my )/T )-近似 Nash 均衡 得 （T 良 結果 見 Q1 行動数 mx , my x ，y ，T 完全 後 最適 (Daskalakis et al., 2011)） … 依存 最適？ Q2 相手 裏切 （指定 Q3 利得 A ∈ [−1, 1]mx ×my 従 未知 ）場合 ？ 高速 43 / 50 収束 O(1/T ) 可能？
132. 最近 研究紹介 詳細：tsuchhiii.github.io/pdf/slide/20260508-umilan-riken.pdf 定理（再掲） 利得行列 A ∈ [−1, 1]mx ×my ， optimistic Hedge（with 定数学習率 ηx = ηy = 1/4） 用 O(log(mx my )/T )-近似 Nash 均衡 得 （T 良 結果 見 Q1 行動数 mx , my x ，y ，T 43 / 50 完全 後 最適 (Daskalakis et al., 2011)） … 依存 最適？ A. optimistic Hedge Q2 相手 裏切 A. （指定 Q3 利得 A ∈ [−1, 1]mx ×my 最適 [T., AISTATS 2026 Spotlight] 従 ）場合 ？ RegT = Ω(T ) ， 適応的学習率 相手 裏切 x 最適 適応 [T.–Ito–Luo, COLT 2025] 未知 高速 収束 O(1/T ) 可能？ A. 適応的学習率 可能 [T.–Luo–Ito, 2026]
133. 最近 研究紹介 詳細：tsuchhiii.github.io/pdf/slide/20260508-umilan-riken.pdf 定理（再掲） 利得行列 A ∈ [−1, 1]mx ×my ， optimistic Hedge（with 定数学習率 ηx = ηy = 1/4） 用 O(log(mx my )/T )-近似 Nash 均衡 得 （T 良 結果 見 Q1 行動数 mx , my x ，y ，T 43 / 50 完全 後 最適 (Daskalakis et al., 2011)） … 依存 最適？ A. optimistic Hedge Q2 相手 裏切 A. （指定 Q3 利得 A ∈ [−1, 1]mx ×my 未知 適応的 最適化 最適 [T., AISTATS 2026 Spotlight] 従 ）場合 ？ RegT = Ω(T ) ， 適応的学習率 相手 裏切 x 最適 適応 [T.–Ito–Luo, COLT 2025] 高速 収束 O(1/T ) 可能？ A. 適応的学習率 可能 [T.–Luo–Ito, 2026] 利用 肝
134. 学習 重要 紹介 （Appendix 44 / 50 話題 補足資料 ） 本 発展的 話題 2人 和 Nash 均衡 （外部） 複数人 ，一般和 粗相関均衡，相関均衡 [ ] RegT 平均反復 (x̄T , ȳT ) 収束 最終反復 (xT , yT ) [ ] [ ] 勾配 g (t) = Ay (t) ，ℓ(t) = A⊤ x (t) 標準型 （同時手番） maxx∈∆m miny ∈∆n x ⊤ Ay 観測 A(It , Jt ) 観測 展開型 （順番 収束 手番） 凹凸関数 鞍点最適化 maxx∈X miny ∈Y f (x, y )
135. 急速 45 / 50 理論的進展 例 複数人一般和 上界 n： 数，m：各 e (·)：T 以外 対数 factor O 行動数，T ： 数， 省略 文献 上界 Blum and Mansour (2007) Chen and Peng (2020) Anagnostides et al. (2022a) Anagnostides et al. (2022b) → 還元 現 最小化：行動数分 Markov 連鎖 定常分布 e (√mT log m) O e (√n m3/4 T 1/4 ) O e (nm4 log4 T ) O O (nm5/2 log T ) Hedge log-barrier → 定常分布 安定性制御 最小化 還元 安定性 制御 (Appendix 参照)
136. 急速 45 / 50 理論的進展 例 複数人一般和 上界 n： 数，m：各 e (·)：T 以外 対数 factor O 行動数，T ： 数， 省略 文献 上界 Blum and Mansour (2007) Chen and Peng (2020) Anagnostides et al. (2022a) Anagnostides et al. (2022b) Tsuchiya (2026) → 還元 現 最小化：行動数分 Markov 連鎖 定常分布 e (√mT log m) O e (√n m3/4 T 1/4 ) O e (nm4 log4 T ) O O (nm5/2 log T ) e (nm2 √log T ) O Hedge log-barrier → 定常分布 安定性制御 log-barrier → 定常分布 entropy → 学習器 最小化 還元 安定性 制御 (Appendix 参照)
137. 急速 45 / 50 理論的進展 例 複数人一般和 上界 n： 数，m：各 e (·)：T 以外 対数 factor O 行動数，T ： 数， 省略 文献 上界 Blum and Mansour (2007) Chen and Peng (2020) Anagnostides et al. (2022a) Anagnostides et al. (2022b) Tsuchiya (2026) Mai (2026) → 還元 現 最小化：行動数分 Markov 連鎖 定常分布 e (√mT log m) O e (√n m3/4 T 1/4 ) O e (nm4 log4 T ) O Hedge log-barrier → 定常分布 安定性制御 O (nm5/2 log T ) log-barrier → 定常分布 e (nm2 √log T ) O entropy → 学習器 √ e O ( n m) (T 非依存) 最小化 還元 安定性 制御 (Appendix 参照)
138. 46 / 50 前半： 凸最適化 多 → 後半： 機械学習 関連 凸最適化 問題 凸最適化 帰着 最適 適応的 性能 達成 学習 (learning in games) 適応的 可能 凸最適化 清聴 望 性質 持 学習 設計 ！
139. References I 47 / 50 Kwangjun Ahn, Gagik Magakyan, and Ashok Cutkosky (2025). “General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization”. In: Proceedings of the 42nd International Conference on Machine Learning. Vol. 267, pp. 772–795. Kwangjun Ahn et al. (2024). “Understanding Adam optimizer via online learning of updates: Adam is FTRL in disguise”. In: Proceedings of the 41st International Conference on Machine Learning. Vol. 235, pp. 619–640. Ioannis Anagnostides et al. (2022a). “Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 736–749. Ioannis Anagnostides et al. (2022b). “Uncoupled Learning Dynamics with O(log T ) Swap Regret in Multiplayer Games”. In: Advances in Neural Information Processing Systems. Vol. 35, pp. 3292–3304. Robert J. Aumann (1974). “Subjectivity and correlation in randomized strategies”. In: Journal of Mathematical Economics 1.1, pp. 67–96. James P. Bailey and Georgios Piliouras (2018). “Multiplicative Weights Update in Zero-Sum Games”. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 321–338. Avrim Blum and Yishay Mansour (2007). “From External to Internal Regret”. In: Journal of Machine Learning Research 8.47, pp. 1307–1324.
140. References II 48 / 50 Noam Brown and Tuomas Sandholm (2018). “Superhuman AI for heads-up no-limit poker: Libratus beats top professionals”. In: Science 359.6374, pp. 418–424. Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile (2004). “On the Generalization Ability of On-Line Learning Algorithms”. In: IEEE Transactions on Information Theory 50.9, pp. 2050–2057. Xi Chen and Binghui Peng (2020). “Hedging in games: Faster convergence of external and swap regrets”. In: Advances in Neural Information Processing Systems. Vol. 33, pp. 18990–18999. Ashok Cutkosky, Harsh Mehta, and Francesco Orabona (2023). “Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion”. In: Proceedings of the 40th International Conference on Machine Learning. Vol. 202, pp. 6643–6670. Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim (2011). “Near-optimal no-regret algorithms for zero-sum games”. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 235–254. John Duchi, Elad Hazan, and Yoram Singer (2011). “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization”. In: Journal of Machine Learning Research 12.61, pp. 2121–2159. Dean P. Foster and Rakesh V. Vohra (1997). “Calibrated Learning and Correlated Equilibrium”. In: Games and Economic Behavior 21.1–2, pp. 40–55.
141. References III 49 / 50 Yoav Freund and Robert E. Schapire (1999). “Adaptive Game Playing Using Multiplicative Weights”. In: Games and Economic Behavior 29.1–2, pp. 79–103. Chi Jin et al. (2020). “Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition”. In: Proceedings of the 37th International Conference on Machine Learning. Vol. 119, pp. 4860–4869. Mingyi Li and Taira Tsuchiya (2026). “Muon with Finite Newton–Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimization”. In: arXiv preprint arXiv:2608.26288. Haipeng Luo, Chen-Yu Wei, and Chung-Wei Lee (2021). “Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses”. In: Advances in Neural Information Processing Systems. Vol. 34, pp. 22931–22942. Tung Mai (2026). “Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism”. In: arXiv preprint arXiv:2609.16751. H. Brendan McMahan and Matthew J. Streeter (2010). “Adaptive Bound Optimization for Online Convex Optimization”. In: Proceedings of the 23rd Conference on Learning Theory, pp. 244–256. Sasha Rakhlin and Karthik Sridharan (2013). “Optimization, Learning, and Games with Predictable Sequences”. In: Advances in Neural Information Processing Systems. Vol. 26, pp. 3066–3074.
142. References IV 50 / 50 Lior Shani et al. (2020). “Optimistic Policy Optimization with Bandit Feedback”. In: Proceedings of the 37th International Conference on Machine Learning. Vol. 119, pp. 8604–8613. Vasilis Syrgkanis et al. (2015). “Fast Convergence of Regularized Learning in Games”. In: Advances in Neural Information Processing Systems. Vol. 28, pp. 2989–2997. Taira Tsuchiya (2026). “Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization”. In: arXiv preprint arXiv:2608.04149. Chen-Yu Wei et al. (2021). “Linear Last-iterate Convergence in Constrained Saddle-point Optimization”. In: International Conference on Learning Representations. Qinzi Zhang and Ashok Cutkosky (2024). “Random scaling and momentum for non-smooth non-convex optimization”. In: Proceedings of the 41st International Conference on Machine Learning. Vol. 235, pp. 58780–58799. Alexander Zimin and Gergely Neu (2013). “Online learning in episodic Markovian decision processes by relative entropy policy search”. In: Advances in Neural Information Processing Systems. Vol. 26, pp. 1583–1591. Martin Zinkevich (2003). “Online Convex Programming and Generalized Infinitesimal Gradient Ascent”. In: Proceedings of the 20th International Conference on Machine Learning, pp. 928–935.
143. Appendix
144. 応用例 A. 背後 分類問題・回帰問題 分布 仮定 予測問題 線形分類 • 各時刻 t 得 ⟨wt , ·⟩ 予測 • 例. xt ∈ R d yt ∈ {1, . . . , c} 線形予測器 回帰 ft (w ) = log(1 + exp(−yt ⟨w , xt ⟩)) 線形回帰 • 各時刻 t xt ∈ R d 得 • 例. ft (w ) = (⟨w , xt ⟩ − yt ) yt ∈ R 線形予測器 ⟨wt , ·⟩ 2 構造予測 • • 例. 線形分類 yt 分類，順序回帰，... 組合 構造 入 問題設定 予測
145. 応用例 B. （非確率）制御 線形動的 xt+1 = Axt + But + wt （xt ∈ X : 状態，ut ∈ U : 制御入力，wt : 外乱 ( )） At each round t = 1, . . . , T : 1. 環境 損失関数 ct : X × U → R 2. 制御入力 ut 3. 状態 xt+1 4. 損失 ct (xt , ut ) 目標： RegT = JT ({ut }t ) 累積 RegT − 決定 観測 被 最小化 min JT (u ∗ ) , ∗ 最適 決定 u 制御入力 JT ({ut }T t=1 ) = E 累積 "T −1 X t=0 • 確率制御（外乱 確率的） 制御（非常 悲観的） 中間 • 安定 過去 影響 指数的 減衰 →有限 凸最適化 還元可能 # ct (xt , ut )
146. 複数人一般和 (multiplayer general-sum games) 和 ： 利害 完全 一般和 (general-sum game)： • n ≥ 2： 数 • 各 （2 人 i ∈ [n] 対立 利害 行動集合 Ai = [mi ] 部分的 一致 効用関数 ui : A1 × · · · × An → [−1, 1] u1 (x, y ) = x ⊤ Ay ，u2 (x, y ) = −x ⊤ Ay ） 和 1. 各 i ∈ [n] 2. 各 i 戦略 xi ∈ ∆mi 選択 利得 Ea1 ∼x1 ,...,an ∼xn [ui (a1 , . . . , an )] 得
147. 一般和 例 1. 行 店 例 （男女 争 ，Bach or Stravinsky 1，2 一緒 行 ， Cake Ramen 呼 ） 2 効用関数 1  1 2 3, 2 0, 0 0, 0 2, 3 Nash 均衡：（純粋戦略）(Cake, Cake)，(Ramen, Ramen)， （混合戦略） 1 Cake 確率 3/5，Ramen 3 0  2 u2 = 0 u1 =  0 2  0 3 確率 2/5 選択
148. 一般和 例 2. 例 (cont’d) （交差点 止 進 2 STOP or GO? STOP GO 効用関数 0, 1 u1 =  1 STOP or GO? ） STOP 0, 0 GO 1, 0  0 0 1 −100   0 1 u2 = 0 −100 −100, −100 Nash 均衡：（純粋戦略）(STOP, GO)，(GO, STOP)， （混合戦略）STOP 確率 100/101，GO 確率 1/101 / 混合戦略 ，両 譲 / Nash 均衡 行動 数 多項式時間 合 利得 計算 選択 低 （ 予想 ）
149. 相関均衡 (correlated equilibrium) 相関均衡： ×ni=1 Ai 上 確率分布 ，自分 推奨 行動 置 換 定義 （相関均衡）(Aumann, 1974) 行動集合 ×ni=1 Ai 上 確率分布 σ ，任意 i ∈ [n] 任意 関数 ϕi : Ai → Ai 次 成 立 ． 得 ε-近似相関均衡 対 Ea∼σ [ui (a)] ≥ Ea∼σ [ui (ϕi (ai ), a−i )] − ε , (a−i = (a1 , . . . , ai−1 , ai+1 , . . . an ))． 相関均衡 • 表 • 例 ： (Cake, Cake)，裏 ：(STOP, GO) 1，2 両方 見 (Ramen, Ramen) (GO, STOP) 半々 投 確率 出 ， ， 信号機
150. 複数人一般和 学習 • n ≥ 2： 数 • 各 i ∈ [n ] 行動集合 Ai = [mi ] 効用関数 ui : A1 × · · · × An → [−1, 1] At each round t = 1, . . . , T : i ∈ [n] 1. 各 (t) ∈ ∆m i 戦略 xi 選択 (t) ui ∈ [−1, 1]mi 2. 各 i 効用 (t) ui (ai ) = Ea ∼x (t) [ui (ai , a−i )]（2 人 −i 3. 各 i i 観測 Ay (t) ） 和 −i (t) (t) 利得 ⟨xi , ui ⟩ 目標：{ui }i∈[n] 得 知 SwapRegT xi ,ui = maxM∈Mmi 最小化 PT PT (t) (t) t=1 ⟨xi , Mui ⟩ − Mm = {M ∈ [0, 1]m×m : M (k , ·) ∈ ∆m for k ∈ [m]}． 「xi(t) (t) (t) t=1 ⟨xi , ui ⟩ , M ⊤ xi (t) 選 ...」
151. No-swap-regret 学習 相関均衡 行動集合 ×ni=1 Ai 上 確率分布 σ ε-近似相関均衡 任意 i ∈ [n] 任意 関数 ϕi : Ai → Ai 対 ， 次 成 立 ． Ea∼σ [ui (a)] ≥ Ea∼σ [ui (ϕi (ai ), a−i )] − ε. （各 ai ∈ Ai 対 ，時間平均 相関均衡 (t) 直積分布 σ (t) = ⊗i∈[n] xi ∈ ∆(×ni=1 Ai ) Q (t) σ (t) (a1 , . . . , an ) = i∈[n] xi (ai )） P T (t) 分布 σ = T1 (maxi∈[n] SwapRegT xi ,ui /T )-近似 t=1 σ 定理 (Foster and Vohra, 1997) 時刻 t ．
152. 最小化 各 i 外部 最小化 還元 {Algi,a }a∈Ai 最小化 mi = |Ai | 個用意 At each round t = 1, . . . , T : (t) 1. 各行動 a ∈ Ai yi,a ← Algi,a (履歴) 2. (t) (t) Qi [a, :] = (yi,a )⊤ 3. Markov 連鎖 Qi(t) 4. 効用 出力 Markov 連鎖 Qi(t) ∈ [0, 1]mi ×mi 定常分布 (t) (t) (t) uei,a = xbi (a)uei 補題 (Blum and Mansour, 2007) 各 Algi,a 外部 SwapRegT xbi ,e ui ( M ) = X a∈Ai (t) 戦略 xbi 構成 設定 計算 ， (external regret) g T (M (a, ·)) Reg i,a for 和： T X (t) (t) g T (y ∗ ) = Reg ⟨y ∗ − yi,a , uei,a ⟩ . i,a t=1
153. 最終反復 (last-iterate) 平均反復 (x̄T , ȳT ) 収束 収束 Hedge：戦略 均衡 収束 (x (t) , y (t) ) y (t) • 平均反復 (x̄T , ȳT ) • 戦略 （均衡 回 収束 (x (t) , y (t) ) 均衡 y (t) x (t) x (t) 均衡 (x ∗ , y ∗ ) 均衡 (x ∗ , y ∗ ) Nash 均衡 収束 続 非収束 ） (Bailey and Piliouras, 2018) 平均反復 収束 optimistic Hedge：戦略 平均 (x̄T , ȳT ) (x (t) , y (t) ) 周 最終反復 (xT , yT ) ，最適 • 最終反復 (xT , yT ) Nash 均衡 収束 • 実用上重要（実際 使 optimistic Hedge (Wei et al., 2021) ・ ・解析 異 最後 達成 戦略）
154. 勾配 相手 （純粋戦略） 出 勾配 利得 ：相手 観測 x 手 列全体 ：出 手 1 ? 1 ? ? 1? ? ? 0 ? ? ? ? ? −1 ? ? ? ? g (t) = Ay (t) = (1, 0, −1) ：出 各 場合 利得 1 観測 手 利得（対戦結果） 問題（応用例 3） 観測 観測