MENU EECS 559: Optimization Methods for SIPML, Winter 2023
Course Instructor: Prof. Qing Qu
Teaching Assistant: Xiang Li, email: forkobe@umich.edu
Title: Optimization Methods for Signal & Image Processing and Machine Learning (SIPML)
Course Time: Mon/Wed 10:30 AM – 12:00 PM (Hybrid), Beyster 1670
Office Hour: Wed 1:00 PM – 2:30 PM (In-Person/Remote)
Enrollment based on the ECE override system with priority to SIPML students, a previous course taught by Prof. Jeffrey Fessler can be found here.
Prerequisite: EECS545, EECS 551 or EECS 505 (aka 598 on “Computational Data Science”) is essential
Overview: This graduate-level course introduces optimization methods that are suitable for large-scale problems arising in data science and machine learning applications. We will explore several widely used optimization algorithms for solving convex/nonconvex, and smooth/nonsmooth problems appearing in SIPML. We will study the efficacy of these methods, which include (sub)gradient methods, proximal methods, Nesterov’s accelerated methods, ADMM, quasi-Newton, trust-region, cubic regularization methods, and (some of) their stochastic variants. If time allowed, we will also introduce constraint optimization over the Riemannian manifold. In the meanwhile, we will show how these methods can be applied to concrete problems ranging from inverse problems in signal processing (e.g., sparse recovery, phase retrieval, blind deconvolution, matrix completion), unsupervised learning (e.g., dictionary learning, independent component analysis, nonnegative matrix factorization), to supervised learning (e.g., deep learning).
The course will involve extensive practical algorithm development, implementation, and investigation using MATLAB, Python, or Julia. Designing methods to be suitable for large-scale SIPML applications will be emphasized and students will be expected to learn and apply efficient coding methods.
Course Materials: slides and video will be accessed via Canvas (TBA), below are some tentative algorithms that will be covered in the course:
- 1st-order methods for smooth optimization: gradient descent, conjugate gradient, line-search method, momentum (Nesterov’s accelerated) method;
- 1st-order methods for nonsmooth optimization: subgradient method, proximal method, and its accelerated variants;
- Large-scale 1st-order optimization: ADMM, Frank-Wolfe method, and stochastic/incremental gradient methods;
- 2nd-order methods: Newton and quasi-Newton method, trust-region method, cubic regularization method, and curvilinear search method;
- Riemannian optimization (if time allowed): optimization over matrix manifolds such as the sphere, Stiefel manifold, Grassmannian manifold, etc.
Every optimization method introduced will have at least one SIPML application that we will introduce as motivation. Students will implement and test these methods on those applications.
Assessment: (i) homework assignment (bi-monthly, 40%), (ii) final (take-home) exam (40%), (iii) course project (15%) (iv) course participation (5%)
Textbook: We recommend the following books and articles, although we will not follow them closely.
- High-Dimensional Data Analysis with Low-Dimensional Models: Principles, Computation, and Applications. John Wright, Yi Ma (major reference)
- Convex Optimization, Stephen Boyd, and Lieven Vandenberghe, Cambridge University Press (2004).
- Numerical Optimization, Jorge Nocedal, and Stephen Wright, Springer (2006).
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Stephen Boyd, Neal Parikh, Eric Chu, Foundations and Trends in Machine Learning, 2011.
- Optimization Methods for Large-Scale Machine Learning, Leon Bottou, Frank Curtis, and Jorge Nocedal (2016).
- Proximal Algorithms, Neal Parikh and Stephen Boyd, Foundations and Trends in Optimization (2014).
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview, Yuejie Chi, Yue M. Lu, Yuxin Chen (2019).
- From Symmetry to Geometry: Tractable Nonconvex Problems, Yuqian Zhang, Qing Qu, John Wright (2020).
- An Introduction to Optimization on Smooth Manifolds, Nicolas Boumal (2020).
Related courses:
- EECS 600 (Function Space Methods for Systems Theory) is much more theoretical than this course because it deals with infinite-dimensional spaces whereas EECS 559 will focus completely on finite-dimensional problems. EECS 600 is far more proof oriented than this course, but there will be some proofs presented and expected in EECS 559 as well.
- IOE 410 (Advanced Optimization Methods) focuses on discrete methods and seems aimed at undergraduates.
- IOE 511/Math562 (Continuous Optimization Methods) has some overlap in terms of the optimization methods. IOE 511 uses Matlab. EECS 559 focuses on SIPML applications.
- IOE 611/Math663 (Nonlinear Programming) covers important Convex Optimization principles. It uses the CVX package in Matlab that does not scale to large problems. EECS 559 emphasizes large-scale SIPML applications.
- STAT 608 (Optimization Methods in Statistics) covers many of the same methods as EECS 559.
- EECS 556 (Image Processing) introduces some applications (e.g., image deblurring) that are considered as examples in EECS 559. So there is some overlap with EECS 556, as well as the other courses listed above, but it is fine for students to take this course and also any or all of EECS 556, EECS 600, and IOE 611.
Course Syllabus:
| Week | Time | Topic | Contents | Homework, Project & Finals |
|---|---|---|---|---|
| Week-1-1 | 1/02 | No Class | ||
| Week-1-2 | 1/04 | Introduction (Remote) | Course Logistics & Overview | |
| Week-2-1 | 1/9 | Optimization Basics | Introduction to mathematical optimization | |
| Week-2-2 | 1/11 | Optimization Basics | Sample examples & applications, mathematical background | HW1 Release |
| Week-3-1 | 1/16 | Martin Luther King Day, No Class | ||
| Week-3-2 | 1/18 | Convex Smooth | Gradient descent method, Line search | |
| Week-4-1 | 1/23 | Convex Smooth | Gradient descent method, Line search | |
| Week-4-2 | 1/25 | Convex Smooth | Nesterov’s acceleration, Newton’s Method | HW 1 Due, HW 2 Release |
| Week-5-1 | 1/30 | Convex Nonsmooth | Stochastic Gradient Descent | |
| Week-5-2 | 2/01 | Convex Nonsmooth | Intro of nonsmooth problems, subgradient methods | |
| Week-6-1 | 2/06 | Convex Nonsmooth | subgradient methods II | |
| Week-6-2 | 2/08 | Convex Nonsmooth | Smoothing & Moreau envelope | HW 2 Due, HW 3 Release |
| Week-7-1 | 2/13 | Convex Nonsmooth | Proximal gradient method | |
| Week-7-2 | 2/15 | Convex Nonsmooth | Accelerated proximal gradient & homotopy continuation | |
| Week-8-1 | 2/20 | Convex Nonsmooth | Augmented Lagrangian Method | |
| Week-8-2 | 2/22 | Convex Nonsmooth | Alternating Direction Method of Multipliers (ADMM) | HW 3 Due, HW 4 Release |
| Week-9-1 | 2/27 | Spring Break, No Class | ||
| Week-9-2 | 3/01 | Spring Break, No Class | ||
| Week-10-1 | 3/06 | Convex Optimization | Alternating Direction Method of Multipliers (ADMM) II | |
| Week-10-2 | 3/08 | Convex Optimization | Frank-Wolfe Methods | Project Proposal Due, Mar. 10th |
| Week-11-1 | 3/13 | Nonconvex Optimization | Introduction of Nonconvex Problems I | |
| Week-11-2 | 3/15 | Nonconvex Optimization | Introduction of Nonconvex Problems II | HW 4 Due, HW 5 Release |
| Week-12-1 | 3/20 | Nonconvex Optimization | Introduction of Nonconvex Problems & Trust-Region Method | |
| Week-12-2 | 3/22 | Nonconvex Optimization | Trust-Region Method I | |
| Week-13-1 | 3/27 | Nonconvex Optimization | Trust-Region Method II | |
| Week-13-2 | 3/29 | Nonconvex Optimization | Cubic Regularization Method | HW 5 Due, HW 6 Release |
| Week-14-1 | 4/03 | Riemannian Optimization | Riemannian optimization I | |
| Week-14-2 | 4/05 | Riemannian Optimization | Riemannian optimization II | |
| Week-15-1 | 4/10 | Riemannian Optimization | Riemannian optimization III | |
| Week-15-2 | 4/12 | Guest Lecture I | TBA | TBA |
| Week-16-1 | 4/17 | Guest Lecture II | TBA | TBA |
| Week-16-2 | 4/19 | Exam Preparation, No Class |