2021 Faculty Courses School of Computing Department of Mathematical and Computing Science Graduate major in Mathematical and Computing Science
Topics on Mathematical and Computing Science C
- Academic unit or major
- Graduate major in Mathematical and Computing Science
- Instructor(s)
- Hanna Sumita / Yasushi Kawase / Shinji Ito / Kei Takemura
- Class Format
- Lecture
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - Intensive
- Class
- -
- Course Code
- MCS.T512
- Number of credits
- 200
- Course offered
- 2021
- Offered quarter
- 2Q
- Syllabus updated
- Jul 10, 2025
- Language
- Japanese
Syllabus
Course overview and goals
This course offers basic knowledge on “online optimization” and advanced topics. The classes are given by three lecturers. The standard optimization problems assume that all the input data is given in advance, which is sometimes hard to satisfy in practice. On the other hand, in “online” optimization problems, a part of input data is given one by one. This course explains various models, typical problems, and algorithms with analysis techniques. The first half part of this course deals with competitive ratio analysis, and the latter focuses on regret analysis.
The aim of this course is to provide the concept of online optimization and basic theory, which are nowadays necessary in the real world. Recently online optimization has been attracting attention not only in optimization theory but also machine learning and artificial intelligence. The theory and algorithms are applied to make better services in practice.
The schedule of this course is irregular. The details are announced during the first class.
- 1st : June 11, period 5-6
- 2-13th : Every Tuesday from June 15, periods 5-6 & 7-8
- 14th : July 27, period 5-6
Course description and aims
The goal of this course is the following.
1) Students can show typical online optimization problems and explain the models.
2) Students can explain the notion of competitive ratio and a fundamental example of competitive ratio analysis.
3) Students can explain the notion of regret and a fundamental example of regret analysis.
Student learning outcomes
実務経験と講義内容との関連 (又は実践的教育内容)
The lecturers have been working for research on online optimization as their business.
Keywords
online optimization, competitive ratio, regret, game, machine learning
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
In each class, we focus on a specific topic by a standard type of lecture.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Introduction | Get the overall gist of this course |
| Class 2 | Competitive analysis of deterministic algorithms (1/2) | |
| Class 3 | Competitive analysis of deterministic algorithms (2/2) | |
| Class 4 | Competitive analysis of randomized algorithms (1/2) | |
| Class 5 | Competitive analysis of randomized algorithms (2/2) | |
| Class 6 | Secretary problem | |
| Class 7 | Prophet inequality | Midterm report |
| Class 8 | Expert problem (1/2): greedy algorithm and regret | |
| Class 9 | Expert problem (2/2): multiplicative weight update method and regret analysis | |
| Class 10 | Online convex optimization | |
| Class 11 | Multi-armed bandit problem (1/2): adversarial model | |
| Class 12 | Multi-armed bandit problem (2/2): stochastic model | |
| Class 13 | Linear bandit problem | Final report |
| Class 14 | Review and exercise |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class.
They should do so by referring to textbooks and other course material.
Textbook(s)
We do not assign textbooks.
Reference books, course materials, etc.
We will upload course materials. Reference books will be introduced in classes.
Evaluation methods and criteria
Students are assessed by the midterm and final reports.
Related courses
- MCS.T302 ： Mathematical Optimization
- MCS.T322 ： Combinatorial Algorithms
- MCS.T405 ： Theory of Algorithms
Prerequisites
It is desirable to have basic knowledge of mathematics and undergraduate level of optimization theory.