CMPUT 676: Optimization and Decision-Making under Uncertainty

Fall 2024

Instructor: Xiaoqi Tan (xiaoqi.tan$\textsf{@}$ualberta.ca)
Location & Time: GSB 7-11, MW 12:00 PM – 1:20 PM
Office hour: After class or by appointment

Course Overview

Many real-world problems involve making decisions over time in the presence of various forms of uncertainty. These challenges arise in fields such as Internet advertising, energy sustainability, transportation, financial trading, healthcare, and a wide range of problems in artificial intelligence and machine learning. Although these specific decision problems may initially appear different in various application scenarios, 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 through several modern optimization lenses. We will begin with a brief introduction to convex optimization, covering basic concepts of convex sets and convex functions, canonical convex problems, Lagrange multipliers, duality theory, KKT optimality conditions, and standard convex optimization algorithms. Following this, we will explore models and algorithms designed to handle different forms of uncertainty in optimization and decision-making. Major topics include: i) online optimization and competitive analysis; ii) stochastic optimization, learning, and approximation; and iii) algorithmic game theory and mechanism design. These topics are highly interdisciplinary, with strong connections to theoretical computer science, artificial intelligence, machine learning, economics, operations research, statistics, and control. While the course is theoretical in nature, most problems discussed will be motivated and illustrated by practical examples.

Notes: We welcome high level undergrads to audit or take the course (subject to administrative approval).

Course Project

The main assignment of this course is to complete a course project which includes a proposal (20%), an in-class presentation (30%), and a final report (50%).

Proposal (20%): You need to select 1-2 papers from this list and prepare a one-page review (covering the main idea, methodologies, and key results of the selected papers) and a separate one-page proposal (containing potentially multiple ideas, such as improvements, alternative approaches, or new discoveries). Your paper review and proposal will be evaluated using a scoring grid based on 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, which is why the task is titled “Proposal” rather than “Paper Review.”

Presentation (30%): You will give an in-class presentation based on your paper review and proposal. Your presentation will be evaluated using a scoring grid based on the following criteria: i) clarity of the content (e.g., structure of the slides), ii) clarity of the presentation, and iii) effectiveness in addressing questions. These three criteria are equally important in evaluating your presentation.

Final Report (50%): You are expected to complete this course with an 8-10 page final report. As a research-oriented graduate course, it is up to you to decide the focus of your final report—whether it be a proof of a new theorem, a new implementation, or a new survey—but it must be related to your proposal. Your final report will be evaluated using a scoring grid based on the following criteria: i) novelty, ii) consistency with the proposal and presentation, and iii) relevance to this course. Please note that novelty does not necessarily mean novel research results. While you will receive bonus marks for making novel research discoveries relevant to this course, they are not required to receive full marks on the project.

Course Schedule and Readings