CMPUT 676: Optimization and Decision-Making under Uncertainty

Fall 2022

Instructor: Xiaoqi Tan ($ \textsf{xiaoqi.tan@ualberta.ca} $)
Location & Time: CAB 369, MW 2:00pm – 3:20pm
Office hour: After class or by appointment
Slack workplace: Join the ODMU@UofA slack workspace with your $\textsf{@ualberta.ca}$ email for online discussions about course-related questions, or topics in the general field of Optimization & Decision-Making under Uncertainty.

Course Overview

Many real-world problems involve making decisions, over a period of time, in the presence of different forms of uncertainty. These challenges arise in Internet advertising, energy sustainability, transportation, financial trading, healthcare, and a wide range of problems in artificial intelligence and machine learning. In different application scenarios, these specific decision problems might look different at first glance; however, the models and algorithms needed to address them are often similar.

In this research-oriented course, we will review recent developments and discuss open directions in the general field of decision-making under uncertainty via several modern optimization lenses. We will start by giving a brief introduction to convex optimization. Topics in this part include basic concepts of convex sets and convex functions, canonical convex problems, Lagrange multipliers, duality theory, KKT optimality conditions, and standard convex optimization algorithms. After that, we will discuss models and algorithms to handle different forms of uncertainty in optimization and decision-making. Major topics to be covered include: i) Online algorithms and Online optimization; ii) Stochastic optimization, learning, and approximation; and iii) Algorithmic game theory + Mechanism design. These topics are highly interdisciplinary – they have strong ties to various disciplines such as theoretical computer science, artificial intelligence, machine learning, economics, operations research, statistics, and control. The course is theoretical in nature, but most problems considered will be motivated and illustrated by practical examples.

Course Objectives

1. Understand the basics of optimization theory, algorithms, and applications.

2. Understand how to build rigorous mathematical models and develop efficient algorithms, with provable guarantees, for optimization and decision-making under different forms of uncertainty.

3. Be well prepared to conduct research in areas such as i) online optimization, learning, and decision-making; ii) stochastic optimization, learning, and approximation; and iii) algorithmic game theory, mechanism design, and auctions.

Course Policies

Textbook: This course does not require any textbook. There will be references (e.g., lecture slides, notes, papers, and/or book chapters) suggested for each lecture.

Prerequisites: You should know material in standard UG courses in calculus, linear algebra, probability, and algorithms very well. Having some optimization background will be a bonus.

Grading: Participation (10%); Assignment (20%); Project: Proposal (20%) + Presentation (20%) + Report (30%).

Assignment: The assignment includes two parts. Part I consists of questions that everyone must answer with rigorous proofs (no programming required). In Part II, there are some open-ended questions. You are free to pick any one from the list. Solving these questions will need some mathematical derivations, and you may also find it necessary to write some code to demonstrate some numerical results. There is no designated programming language, but you are recommended to use Python if you can. The submission of your solution includes a written report and a link to the code (e.g., a repository in GitHub).

Project: You are expected to complete a research-flavored project which includes a proposal, an in-class presentation, and a written report.

• Proposal: You need to selected two papers that are related to this course, and prepare a one-page review of the main idea, methodologies, and key results of the papers selected, and another one-page proposal of what could be improved, what could be done differently, and/or other new discoveries. Your paper review and proposal will be evaluated by using a scoring grid relative to the following criteria: i) depth, rigor, and thoroughness of the review, ii) clarity and merit of the proposal, and iii) coherence between the review and the proposal. Please note that the one-page proposal is proportionally more important, and hence the name “Proposal” rather than “Paper Review”.
• Presentation: You will give a presentation in class – based on your paper review and proposal. Your presentation will be evaluated by using a scoring grid relative to the following criteria: i) clarity of the content (e.g., structure of the slides), ii) clarity of the presentation, and iii) effectiveness of addressing possible questions. These three criteria are equally important in evaluating your presentation.
• Report: This is a research-oriented graduate course, and it is up to you to decide what your final report is about – proof of a new theorem, a new implementation, or a new survey – but it must be related to your proposal, your presentation, and of course, the topics covered by this course. Your final report will be evaluated by using a scoring grid relative to the following criteria: i) novelty, ii) consistency to the proposal and presentation, and iii) relevance to this course. Please note that novelty does not necessarily mean novel research results: you will be awarded bonus marks if you make novel research discoveries that are relevant to this course, but they are not necessary to get full marks in the project. For more details, please refer to our project guidlines.

For each evaluation criteria, a score will be assigned between 1 and 5 (i.e., 1: very low, 2: low, 3: medium, 4: high, 5: very high). When preparing your proposal and report, you are highly recommended to use Latex (template here).

Course Schedule