2021年度学院等開講科目情報理工学院数理・計算科学系数理・計算科学コース

数理・計算科学特論C

開講元: 数理・計算科学コース
担当教員: 澄田範奈 / 河瀬康志 / 伊藤伸志 / 竹村慧
授業形態: 講義
メディア利用科目: -
曜日・時限 (講義室): 集中講義等
クラス: -
科目コード: MCS.T512
単位数: 200
開講時期: 2021年度
開講クォーター: 2Q
シラバス更新日: 2025年7月10日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

本講義は，3人の講師のオムニバス形式で「オンライン最適化」の基礎知識から研究の最前線まで広く解説する．古典的な最適化問題では入力が一度にすべて与えられるのに対して，オンライン最適化では一部の情報が逐次的に与えられる．オンライン最適化はモデルにより扱える状況や解析が様々である．講義の前半ではオンライン最適化の競合比解析，後半ではリグレット解析に焦点を当て，代表的な問題・アルゴリズム・解析手法について解説する．

近年オンライン最適化は最適化の理論のみならず機械学習や人工知能の分野でも盛んに研究が進んでおり，今ではオンライン最適化の理論とアルゴリズムは社会において必要不可欠である．本講義のねらいは社会を支えるオンライン最適化の考え方と基礎理論を学んでもらうことである．

本講義の講義予定は以下の通りである．詳細は初回に周知する．
・第1回　6月11日（金）5-6限
・第2―13回　6月15日（火）より毎週火曜，5-6, 7-8限
・第14回　7月27日（火）5-6限

到達目標

本講義の到達目標は以下である．
1) オンライン最適化の代表的な問題とモデルの分類を説明できる
2) 競合比解析の基本的な考え方と代表例を説明できる
3) リグレット解析の基本的な考え方と代表例を説明できる

実務経験のある教員等による授業科目等

実務経験と講義内容との関連 (又は実践的教育内容)

本講義の講師はこれまでに実務としてオンライン最適化に関する研究を行っている．

キーワード

オンライン最適化，競合比，リグレット，ゲーム，機械学習

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

毎回ひとつのトピックを講義形式で解説する．

授業計画・課題

	授業計画	課題
第1回	イントロダクション	オンライン最適化の概要を把握する
第2回	決定性アルゴリズムの競合比解析(1/2)
第3回	決定性アルゴリズムの競合比解析(2/2)
第4回	乱択アルゴリズムの競合比解析(1/2)
第5回	乱択アルゴリズムの競合比解析(2/2)
第6回	秘書問題
第7回	預言者の不等式	中間レポート
第8回	エキスパート問題(1/2): 貪欲アルゴリズムとリグレットの定義
第9回	エキスパート問題(2/2): 乗算型重み更新アルゴリズムとリグレット解析
第10回	オンライン凸最適化
第11回	多腕バンディット問題(1/2): 敵対的モデル
第12回	多腕バンディット問題(2/2): 確率的モデル
第13回	線形バンディット	期末レポート
第14回	復習と演習

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

特に設定しない．

参考書、講義資料等

講義資料はアップロードする．参考書は講義中に周知する．

成績評価の方法及び基準

中間レポートと期末レポートにより評価する．

履修の条件・注意事項

基本的な数学・学部レベルの最適化に関する知識があることが望ましい．