講演者一覧

• 平原秀一 （国立情報学研究所 情報学プリンシプル系）

• 西山颯大　（東京大学 総合文化研究科）

• 高邉賢史 （東京科学大学 情報理工学院）

• 高橋昂 （東京大学 知の物理学研究センター）

• 高橋惇 （東京大学 物性研究所）

• 白石直人 （東京大学 総合文化研究科）

• 清水伸高 （東京科学大学 工学院）

• 今泉允聡 （東京大学 総合文化研究科 / 理化学研究所 AIPセンター）

プログラム

• １０：３０〜１０：３５ オープニング

セッション1

• １０：３５〜１１：０５ 高邉賢史 "サンプリングと学習（と統計力学）"

• １１：０５〜１１：３５ 髙橋昂 "双線型回帰における交互最適化法の巨視的解析"
  
  

• １１：３５〜１３：１５ お昼ごはん 🍛

セッション2

• １３：１５〜１３：４５ 清水伸高 "埋め込みクリーク問題に見る計算限界と統計限界のギャップ"

• １３：４５〜１４：１５ 平原秀一 "行列積アルゴリズムの誤り訂正"

• １４：１５〜１４：４５ 休憩 ☕

セッション3

• １４：４５〜１５：１５ 白石直人 "計算困難な具体的インスタンスの決定論的構成に向けて"

• １５：１５〜１５：４５ 高橋惇 "ハミルトニアン計算複雑性における量子モンテカルロ法"

• １５：４５〜１６：０５ 休憩 ☕

セッション4

• １６：０５〜１６：３５ 西山颯大 "動的平均場理論による最適化アルゴリズムの典型挙動解析"

• １６：３５〜１７：０５ 今泉允聡 "計算学習理論によるニューラルネットワーク解析"
  
  

• １７：０５〜 クロージング・懇談会

アブストラクト

高邉賢史 "サンプリングと学習（と統計力学）"

• 本講演ではマルコフ連鎖モンテカルロ法や粒子型変分推論といったサンプリング手法やその学習について紹介します．また統計力学的な観点に基づいたサンプリングの学習に関する我々の研究も紹介する予定です．

髙橋昂 "双線型回帰における交互最適化法の巨視的解析"

• 交互最適化法とは、一部の変数を固定して残りの変数に対しての最適化を行う操作を繰り返す、汎用的な最適化手法の一つである。特に、行列分解など、全体として非凸な最適化問題であっても、変数の一部を固定すると残りの変数に対する最適化が凸になるような場合などによく用いられている。ただし、このような場合に交互最適化法が有益な解に収束する保証はない。
  そこで本発表では、双線型回帰問題に対する交互最適化法について、統計力学のレプリカ法を用いて、データ数とパラメータ次元が比例的に発散する極限でその最適化ダイナミクスを特徴づけた結果について報告する。
  余裕があれば、この解析で用いた枠組みを断熱的なアニーリング過程へと応用する方針についても議論を行う。

清水伸高 "埋め込みクリーク問題に見る計算限界と統計限界のギャップ"

• 多くの統計的推定・検出問題においては、十分なデータが与えられれば真の構造やパラメータを正確に推定することが統計的には可能である。しかし、そのような原理的な可能性と、実際に効率的なアルゴリズムを構成できるかどうかの間には、しばしば隔たりが存在する。この隔たりは、計算限界と統計限界（computational-statistical gap）の不一致として現れる。
  本講演では、この隔たりを具体的に理解するための例として、分野で中心的な役割を果たす埋め込みクリーク問題を取り上げる。埋め込みクリーク問題では、ランダムグラフ中に埋め込まれた大きさ k の完全グラフを検出することを考える。統計的には k が十分大きければ検出可能である一方で、効率的なアルゴリズムでは検出が困難であると信じられている領域が存在する。本講演では、講演者の最近の成果である [Hirahara, Shimizu, STOC24] の結果を交え、このギャップの構造や応用などについて解説する。

平原秀一 "行列積アルゴリズムの誤り訂正" 

• ランダムな行列に対して行列積を（期待値の意味で）たった1%の要素で正しく計算できる効率的なアルゴリズムがあるとき、全ての行列で全てのエントリを正しく計算する効率的なアルゴリズムに変換できることを示す。本発表はSTOC 2025およびICALP 2025で発表した清水信高氏との共著論文に基づく。

白石直人 "計算困難な具体的インスタンスの決定論的構成に向けて"

• 情報統計力学のアプローチによる計算困難性の議論では、SATやグラフ彩色などの問題について「ランダムなインスタンスのほとんどについて、効率的に解けない」というタイプの議論がなされる。しかしこの方法だと、確率的に生成したインスタンスの大半は計算困難かもしれないが、具体的にどのインスタンスが計算困難なのかは分からない。決定論的に与えられる計算困難なインスタンスが存在すれば、計算困難性を深く理解できるだろう。そこで本講演では、最大独立集合問題を題材に、決定論的な計算困難インスタンスの構成を模索する。

高橋惇 "ハミルトニアン計算複雑性における量子モンテカルロ法"

• ハミルトニアン複雑性は、多体物理系の基底エネルギーを求める問題を最適化問題とみなしてその計算複雑性を問うことによって、統計物理と計算量理論を最も直接的に橋渡しする設定の一つであると言える。
  この文脈の主要な結果の一つにCubitt-Montanaro (2016) の二体相互作用ハミルトニアンの "tetrachotomy" と言える、P、NP完全、StoqMA完全、QMA完全への一般分類が挙げられるが、この設定はハミルトニアンに負の係数を許し、物理で言うところの「フラストレーションを必ず入れられる」設定であった。フラストレーションを入れられない、つまり正の係数のみを考える設定は物理的にも最適化問題としても自然な制約だと言えるが、この場合の計算複雑性や効率的なアルゴリズムに関しては基本的な問いすら未解決である。
  最近、計算物理の文脈で重宝されてきた「量子モンテカルロ法」がMCMCとしてfast-mixingであり、それゆえ一部の上記tetrachotomyでQMA完全な二体ハミルトニアンの非フラストレートな場合ではBPPに落ちることが証明できた。発表では主に、これらの結果の物理的理解との関係性、及び証明のアイディア(JerrumとSinclairによるcanonical path法)について解説する予定である。

西山颯大 "動的平均場理論による最適化アルゴリズムの典型挙動解析"

• 動的平均場理論 (Dynamical Mean-Field Theory; DMFT) は，高次元のランダムなダイナミクスの典型的・巨視的な挙動を低次元の微分方程式形により特徴づける手法である．統計物理学で発達したこの手法は，近年，機械学習理論において，勾配降下法などの最適化アルゴリズムの典型挙動解析に応用されている．この発表では，DMFTと機械学習理論に関する最近の研究をいくつか紹介する．また，関連する話題として，近似メッセージ伝搬法 (Approximate Message Passing; AMP) や，アルゴリズムの平均時計算量解析などについても時間があれば触れる．

今泉允聡 "計算学習理論によるニューラルネットワーク解析"

• 本講演では、計算学習理論を用いたニューラルネットワークのサンプル複雑性の議論を紹介します。

世話人

• 高橋昂（東京大学）

• 今泉允聡（東京大学・理化学研究所・京都大学）

主催

• JST 創発的研究支援事業「深層学習の原理記述に向けた構造汎化理論スキームの開発」