CMSC 764 | Advanced Numerical Optimization

This course is a detailed survey of optimization. Topics are mainly covered from a computational perspective, but theoretical issues are also addressed. 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.
Computational topics will include gradient methods, stochastic methods, Bayesian methods, splitting methods, interior point methods, linear programming, and methods for large matrices. Theoretical topics will include convex analysis, duality, rates of convergence, and advanced topics in linear algebra. Homework assignments will require both mathematical work on paper and implementation of algorithms.

The basics

Communications and questions for this course will be managed through the course slack channel. You can join the channel here.

If you have a question for the professor of the TAs I suggest you use slack rather than email to make sure it doesn’t get lost in the aether.

Most lectures will not be available in online format.

     
When: TuTh 11:00pm - 12:15pm       Where: Gannon Auditorium (Iribe)
Instructor: Tom Goldstein Office Hours: Th 12:15-1:30pm, Iribe 4212
TA: Gowthami Somepalli Office Hours: Thurs @ 10am gowthami@umd.edu
TA: Amin Ghiasi Office Hours: Fri @ 10am ghiasi@umd.edu

Exams

Exam problems will be reflective of homework problems in their style and content coverage. Problems can cover material presented in the slides, in addition to material from the homework. You are expected to understand slide material to the level of detail presented in the slides (but no more). You can be tested on the content of and solutions to homework problems.

You won’t be expected to recall complex formulas (e.g., rank-1 update formulas). But you may be expected to know how to use formulas if you are provided them

Midterm exam topics

  • Bayesian statistics, maximum likelihood, and priors
  • Norms
  • Objective functions for linear classifiers
  • Fourier transforms and convolutions
  • Continuous derivative and gradient
  • discrete gradient operator and total variation
  • chain rule / backprop / autdiff
  • quadratic forms
  • second-order taylor expansion
  • matrix factorizations
  • methods for solving linear systems (direct, iterative, randomized)
  • definition of convex sets
  • convex functions
  • epigraph
  • quasiconvexity
  • convexity preserving operations
  • differential properties of convex function
  • Lipschitz constants and strong convexity constants
  • Solutions to all homework problems up to and including homework 5.

Final exam

This exam will be on May 12 at 8am. Topics include

  • Gradient descent methods: stepsize restrictions, backtracking, and convergence rates
  • Quasi-newton methods: know the conceptual basics of how they work, and the convergence rates. You will not be asked to recite specific update formulas for BFGS or CG.
  • Duality: Be able to write the Lagrangian of a problem. Know how to find the dual of a problem by removing primal variables from the Lagrangian. Know what the conjugate function is, and how to use it to dualize a problem. Know Slater’s condition, and the difference between strong/weak duality.
  • Prox methods: Know what a proximal operator is, what it does, and how to write the prox operator of a simple function. Know how to use a characteristic function to add a constraint to a problem, and what it means to compute the prox operator of a characteristic function. Know the steps of forward-backward splitting. Know stepsize restrictions and convergence rates. Be able to write the steps of a forward-backward solver for a particular problem.
  • Lagrangian methods: be able to write the augmented Lagrangian for a problem. Be able to write the steps of an ADMM solver for a particular problem. Know the steps of PDHG. Be able to write a PDHG solver for a particular problem.
  • Stochastic methods: know the basics of how SGD and MCMC work. When would you use these methods? What sort of convergence rates do you get with them?

Things you DON’T need to know: - You don’t need to know the specific objective functions for the applications/problems given as examples in class. - You don’t need to know the specific steps of methods with “complicated” update formulas, like Nesterov’s method, Adaptive (BB) stepsize rules, BFGS, etc, although you are expected to know the differences between these methods and how they work on a conceptual level.

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.

The approximate grade breakdown of the course will be

  • 50% homework
  • 25% midterm exam
  • 25% final exam.

I reserve the right to change the relative weighting of homework/exams at any time. Furthermore, because this course has gone online, the structure of exams will be quite different than we’ve had in the past and I’m still looking into different options.

Note: This is a PhD qualifying course for computer science.

Homework

Assignments will be distributed as Jupyter notebooks using Python 3. If you’ve never used notebooks before, you can find a tutorial here. For each assignment, you’ll turn in your completed and runnable notebook. You should complete your assignments using a Python version between 3.6 and 3.9 (inclusive).

Homework will be turned in using Elms/Canvas. Follow this link to Elms, and then look for the course page after logging in.

Homework 1: Linear algebra review (Due Wed Feb 9)
Solutions

Homework 2: More linear algebra (Due Wed Feb 16)
Solutions

Homework 3: Gradients (Due Wed Feb 23)
For this assignment, you’ll need to download the notebook importer, and place it in the same folder as the notebook.
Solutions

Homework 4: PySmorch (Due Fri 4th)
Solutions

For this assignment, you’ll need this utility script.

Homework 5: Convex Functions (Due Fri March 11th)
Solutions

Homework 6: Gradient Methods and Duality (Due Mon Apr 18)
Solutions
For this assignment, you’ll need the utility script that you used for homework 4.

Homework 7: Forward-Backward Splitting (Due Mon Apr 25)
Solutions

Homework 8: ADMM (Due May 6)
Solutions

OPTIONAL Homework 9: mcmc (Due May 9)
Solutions

Lecture Slides

These slides evolve from year to year, sometimes dramatically. For this reason, slides might get updated shortly before or after a lecture.

Slides below have not been updated…
Course Overview
Linear Algebra Review
Convolutions and FFT
Optimization Problems
Machine learning basics
Calculus
Quadratic Forms
Convex Functions
Gradient Methods Neural Net Design
Quasi-Newton Methods
Duality
Proximal Methods
Lagrangian Methods
Random topics | MCMC code example
Linear Programming
Bonus lecture: generalization Semidefinite Programming
Interior Point Method

Book & Other Sources

All course materials are available for free online. Suggested reading material for various topics includes: