MA1407.000500: Mathematical Algorithms II

MA1407.000500: Mathematical Algorithms II, Fall 2025

Instructor: Dabeen Lee (27-205)
Email: dabeenl [at] snu [dot] ac [dot] kr

Optimization, the process of finding the best solution among a set of alternatives, lies at the heart of modern data-driven decision-making. This course explores the fundamental principles, algorithms, and applications of mathematical optimization, covering convex optimization, nonconvex optimization, minimax optimization, submodular optimization, online learning, and online reinforcement learning. There are no formal prerequisites, but basic knowledge of mathematical optimization and convex analysis is assumed.

Lecture notes

  1. Tue 9/02: introduction to optimization, optimization for machine learning (note)
  2. Thu 9/04: convex sets, convex functions, operations preserving convexity, first- and second-order characterizations of convex functions (note)
  3. Tue 9/09: convex optimization problems, approximate optimality and oracle complexity, classes of convex optimization problems (note)
  4. Thu 9/11: conic duality, second-order cone programming, optimality conditions for convex minimization (note)
  5. Tue 9/16: subgradients and the subgradient method, gradient descent for smooth functions (note)
  6. Thu 9/18: proximal gradient descent, proximal operators, LASSO and FISTA (note)
  7. Tue 9/23: low-rank matrix completion, low-rank approximation by the SVD, power method (note)
  8. Thu 9/25: low-rank approximation via convex relaxation, Frank-Wolfe method (note)
  9. Tue 9/30: introduction to nonconvex optimization, nonconvex function landscape, finding stationary points (note)
  10. Thu 10/02: cubic regularization, perturbed gradient descent, second-order stationary points (note)
  11. Tue 10/14: optimization with functional constraints, Nesterov's bisection method, CoMirror algorithm (note)
  12. Thu 10/16: Lagrangian duality, Fenchel duality, dual subgradient method (note)
  13. Thu 10/23: introduction to minimax optimization, zero-sum games, distributionally robust optimization (note)
  14. Tue 10/28: gradient descent ascent, extragradient method, optimistic GDA, proximal point algorithm (note)
  15. Thu 10/30: generative adversarial networks, f-GAN, Wasserstein GAN (note)
  16. Tue 11/04: sharpness-aware minimization, submodular functions, Lovász extension (note)
  17. Thu 11/06: convexity of the Lovász extension, submodular function minimization via convex optimization (note)
  18. Tue 11/11: submodular function maximization, matroid constraints (note)
  19. Thu 11/13: continuous submodular functions, max cut problem (note)
  20. Tue 11/18: SDP-based approximation algorithm for max cut, binary convex quadratic maximization (note)
  21. Thu 11/20: sequential decision making, regret minimization for online convex optimization (note)
  22. Tue 11/25: online mirror descent, bandit convex optimization (note)
  23. Thu 11/27: algorithm by Flaxman, Kalai, and McMahan, algorithm with two-point feedback (note)
  24. Tue 12/02: finite-horizon MDPs with adversarial losses, OMD-based algorithm for learning online MDPs (note)
  25. Thu 12/04: adversarial MDPs with unknown transitions, occupancy measures, confidence sets (note)
  26. Tue 12/09: online resource allocation, online dual mirror descent (note)

Assignments

  1. Assignment 1, due 10/01 (pdf)
  2. Assignment 2, due 10/14 (pdf)
  3. Assignment 3, due 11/12 (pdf)
  4. Assignment 4, due 12/09 (pdf)
  5. Assignment 5: paper review project (pdf)