大学院
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2026年10月16日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2026年10月16日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
数理情報学特別講義III（オンライン学習理論）
オンライン学習理論
Theory of Online Learning
This course provides a systematic study of the theoretical foundations
of online learning. Online learning addresses sequential decision-making
problems in which data arrives one instance at a time, with no
distributional assumptions on the data. Even in worst-case (adversarial)
environments, algorithms can be designed whose cumulative performance is
competitive with the best fixed strategy chosen in hindsight.
The course covers major topics including Online Convex Optimization (OCO),
Prediction with Expert Advice, Follow the Regularized Leader (FTRL),
Online Mirror Descent (OMD), Adversarial Multi-Armed Bandits, and
Learning in Games. For each topic, we discuss algorithm design principles,
regret analysis techniques, and the geometric principle of choosing the
right regularizer, with detailed proofs.
By the end of the course, students will be able to:
- Precisely formulate online learning problems and explain the concept of regret
- Derive and analyze various algorithms within the unified FTRL/OMD framework
- Understand and apply the principle of matching the regularizer to the problem geometry
- Extend the framework to bandit settings and understand connections to game theory
of online learning. Online learning addresses sequential decision-making
problems in which data arrives one instance at a time, with no
distributional assumptions on the data. Even in worst-case (adversarial)
environments, algorithms can be designed whose cumulative performance is
competitive with the best fixed strategy chosen in hindsight.
The course covers major topics including Online Convex Optimization (OCO),
Prediction with Expert Advice, Follow the Regularized Leader (FTRL),
Online Mirror Descent (OMD), Adversarial Multi-Armed Bandits, and
Learning in Games. For each topic, we discuss algorithm design principles,
regret analysis techniques, and the geometric principle of choosing the
right regularizer, with detailed proofs.
By the end of the course, students will be able to:
- Precisely formulate online learning problems and explain the concept of regret
- Derive and analyze various algorithms within the unified FTRL/OMD framework
- Understand and apply the principle of matching the regularizer to the problem geometry
- Extend the framework to bandit settings and understand connections to game theory
時間割／共通科目コード
コース名
教員
学期
時限
4820-1016
GIF-MA6603L3
数理情報学特別講義III（オンライン学習理論）
伊藤 伸志
火曜3限
マイリストに追加
マイリストから削除
講義使用言語
英語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
情報理工学系研究科
授業計画
Lecture 1: Introduction to Online Learning
- Formulation of sequential decision-making, definition of regret
- Motivating examples (spam filtering, portfolio selection, etc.)
Lecture 2: Online Convex Optimization and Online Gradient Descent (OGD)
- The online convex optimization framework
- Derivation of OGD and proof of O(sqrt(T)) regret
Lecture 3: Prediction with Expert Advice
- Formulation of the prediction with expert advice problem
- The Halving algorithm, Weighted Majority, and Hedge algorithm
- Adversary models (oblivious, adaptive, stochastic)
Lecture 4: Follow the Regularized Leader (FTRL)
- Follow the Leader (FTL) and its failure modes
- The FTRL unified framework: recovering OGD and Hedge
Lecture 5: Bregman Divergences and FTL Stability Analysis
- Definition and properties of Bregman divergences
- The FTL Lemma (stability decomposition with negative Bregman term)
Lecture 6: FTRL Regret Analysis and Online Mirror Descent
- Completing-the-square analysis of stability vs. curvature
- Equivalence of OMD and FTRL, time-varying regularization
- The geometric principle of choosing the right regularizer
Lecture 7: Exploiting Curvature (1): Strongly Convex Losses
- O(log T) regret for strongly convex losses
- Derivation of logarithmic regret via FTRL
Lecture 8: Exploiting Curvature (2): Exp-Concave Losses and Online Newton Step
- Definition and properties of exp-concavity
- The Online Newton Step (ONS) algorithm
Lecture 9: Adversarial Multi-Armed Bandits (1)
- Formulation of the bandit setting (partial observation)
- Importance-weighted estimators and the EXP3 algorithm
Lecture 10: Adversarial Multi-Armed Bandits (2)
- Regret analysis of EXP3
- Lower bounds and minimax optimality
Lecture 11: Best of Both Worlds and Learning in Games
- Algorithms that adapt to both stochastic and adversarial environments
- No-regret dynamics and applications to game theory
Lecture 12: Student Presentations (1)
- Student talks based on literature surveys, followed by discussion
Lecture 13: Student Presentations (2)
- Student talks based on literature surveys, followed by discussion
授業の方法
The course is delivered primarily through lectures, with detailed
exposition of theorem proofs via board work or slides. Concrete examples
and intuitive explanations are provided alongside formal statements to
facilitate understanding of the theory.
成績評価方法
Homework assignments: 50%
- Two to three problem sets will be assigned throughout the semester.
- Problems focus on theoretical aspects of algorithm design and analysis.
Literature survey and presentation: 50%
- Each student selects a research paper related to online learning and
conducts a literature survey.
- Presentations are given in Lectures 12--13, followed by Q&A and discussion.
Note: The grading policy above is tentative and may be revised depending on the number of enrolled students.
履修上の注意
Prerequisites:
- Linear algebra (vector spaces, norms, inner products)
- Analysis (convex functions, differentiation, Taylor expansion)
- Basic probability theory (expectation, concentration inequalities)
- Familiarity with convex optimization is desirable but not required
