Instructor: Dmitriy Drusvyatskiy
Lecture: MW 9:00-10:20 AM in a Zoom chatroom
Office hours: F 1:00-2:00 PM in a Zoom chatroom
Email: ddrusv at uw.edu
TA: Zhan Shi
Office hours: W 1:00-2:00 PM in a Zoom chatroom
Email: zhansh at uw.edu
Both the lecture and the office hours will take place through Zoom. You have a free subscription to Zoom through U. Washington. Those registered for the course will receive an email on March 25th with the instructions for how to join the Lecture and Office hours. If you are registed for the course and did not receive the email or are not registered and would like to audit, please send me an email. I am also enabling a discussion boarad for the course through Piazza. You will receive an email with instructions on how to register.
This is an introductory course in convex analysis and nonsmooth optimization. We will cover elements of convex geometry and analysis, (stochastic) first-order methods for convex optimization, introductory variational analysis, and algorithms for nonsmooth and nonconvex optimization problems.
We will primarily use the evolving course notes (written by the instructor) posted on this webpage:
Dmitriy Drusvyatskiy, "Convex Analysis and Nonsmooth Optimization." USE THIS VERSION FOR HW4
Some relevent textbooks are the following.
Convex Analysis:
First-order methods for convex optimization
Variational Analysis:
Problem sets are due every two weeks. The solutions must be written in LaTex (100% of the grade). You have to submit the HW assignments through Gradescope. Make sure to sign up for the course on the gradescope webpage using the passcode 9P8775.
You may work together on problem sets, but you must write up your own solutions. You must also cite any resources which helped you obtain your solutions.
The following is a very rough schedule for the course that will evolve as the term progresses.
Lectures 1-2: Background (Lecture 1) (Lecture 2)
Inner products and linear maps
Norms
Eigenvalue and singular value decompositions of matrices
Set operations: addition, scaling, image/preimage
Differentiability
Fundamental theorem of calculus and accuracy in approximation
Optimality conditions for smooth unconstrained minimization
Lectures 3-5: Convex Geometry (Lecture 3) (Lecture 4) (Lecture 5)
Operations preserving convexity
Convex Hull
Affine Hull and relative interior
Separation theorem
Cones and polarity
Tangent and normal cones
Lectures 6-11: Convex Analysis (Lecture 6) (Lecture 7) (Lecture 8) (Lecture 9) (Lecture 10) (Lecture 11)
Convex functions: basic operations and continuity
The Fenchel conjugate
Differential properties
Directional derivative
Monotonicity of the subdifferential
Convexity and smoothness
The optimal value function, duality, and subdifferential calculus
Moreau envelope and the proximal map
Convex functions of eigenvalues
Lectures 12-15: First-order algorithms for convex optimization (Lecture 12) (Lecture 13) (Lecture 14) (Lecture 15) (Lecture 16)
The classical viewpoint: gradient and subgradient methods
Model-based viewoint for composite minimization
Proximal gradient and acceleration
Proximal subgradient
Smoothing based mathods
Primal-dual algorithms for saddle point problems
Stochastic (sub)gradient methods
Coordinate Descent
Variance Reduction
Non-Euclidean extensions
Lectures 16-18: Introduction to variational analysis
Normal and tangent cones
Transversality
Slope, subderivatives, and the subdifferential
The descent principle and error bounds
The extremal principle
Subdifferential calculus
Metric regularity and the normal criterion
The radius of metric regularity
Tame variational analysis: desingularization and Kurdyka-Lojasiewicz (KL) inequality, chain rule along paths, and Sard's theorem.
Lectures 18-20: Algorithms for nonsmooth and nonconvex optimization
Weakly convex functions and compositional problems
Model-based algorithms as approximate proximal point methods: (stochastic) Gauss-Newton and proximal (sub)gradient methods
Iterate convergence of desent methods under KL inequality
Assymptotic convergence of the subgradient algorithm: the ODE method
the Goldstein subdifferential and random search