CMSC764 / AMSC604 - Spring 2017
This is a detailed survey of optimization from both a computational and theoretical perspective. Special emphasis will be put on scalable methods with applications in machine learning, model fitting, and image processing. There are no formal pre-requisites for this course, however students should have a strong background in applied mathematics (especially linear algebra) and computer programming.
Theoretical topics will include convex analysis, duality, rates of convergence, and advanced topics in linear algebra. Computational topics will include gradient methods, splitting methods, interior point methods, linear programming, and methods for large matrices. Homework assignments will require both mathematical work on paper and implementation of algorithms.
|When: TuTh 11:00am - 12:15pm||Where: CSI 3120|
|Instructor: Tom Goldstein||Office Hours: Th 1-2pm, AVW π 3141|
|TA: Hao Li||Office Hours: Mon 10-12, AVW 4431|
Final Exam: Sat, May 13 @ 8am (tentative)
Coursework & grading
Homework will be assigned approximately once per week. Homework assignments will consist of both programming exercises and theoretical problem sets. Programming assignments will be cumulative - you will need the results of early assignments to complete assignments that are given later in the course. The completed homework assignments you turn in must represent your own work.
You may complete your assignments in either Matlab or Python 2.7. Other languages (including Python 3+) will not be allowed. When programming assignments are given, you will be required to prepare a short pdf document containing outputs from your code, and this pdf will be turned in with your code.
The approximate grade breakdown of the course will be
- 50% homework
- 25% midterm exam
- 25% final exam.
Note: This is a PhD qualifying course for computer science.
Homework will be turned in using Elms/Canvas. Follow this link to Elms, and then look for the course page after logging in. I recommend generating your pdf using latex. Have a look at these example solutions, and the corresponding latex source.
Homework 1: linear algebra basics (Due Feb 7)
Homework 5: numerical linear algebra (Due Mar 8)
Homework 6: convex functions (Due Mar 14)
Homework 7: gradient methods (Due April 14)
Homework 8: duality (Due April 26)
Homework 9: prox methods (Due May 3)
Homework 10: ADMM (Due May 10)
Linear Algebra Review
TV, FFT, and Calculus
Random topics | MCMC code example
Book & Other Sources
All course materials are available for free online. Suggested reading material for various topics includes:
- Derivatives and gradients: Convex Optimization by Boyd and Vandenberghe, Appendix A
- Numerical Linear Algebra: Numerical Linear Algebra by Trefethen and Bau
- L1 models and sparsity: Sparse modeling for Image and Vision Processing
- Convex functions and gradient methods: Convex Optimization by Boyd and Vandenberghe
- Convergence rates for gradient methods: Optimal Rates in Convex Optimization
- Proximal methods: A Field Guide to Forward-Backward Splitting
- ADMM: Fast Alternating Direction Optimization Methods
- Consensus ADMM: Distributed Optimization and Statistical Learning
- Unwrapped ADMM: Unwrapping ADMM
- PDHG: Adaptive Primal-Dual Hybrid Gradient Methods
- SGD: Incremental Gradient, Subgradient, and Proximal Methods
- SGD convergence rates: Stochastic Gradient Descent for Non-Smooth Optimization
- Monte-Carlo: An Introduction to MCMC for Machine Learning
- Barrier Methods: Convex Optimization by Boyd and Vandenberghe, chapter 11
- Primal-Dual Interior Point Methods: Nocedal and Wright, chapter 14
- Semi-definite programming: Vandenbergh and Boyd
- Metric learning: Distance Metric Learning for LMNN