COMP SCI 726: Nonlinear Optimization I (Fall 2020)
Class is also listed as ISYE 726/MATH 726/STAT 726.
Instructor: Jelena Diakonikolas
Email: jelena at cs dot wisc dot edu
Office hours: Monday morning (9-10am) and after class (4-5pm), or by appointment. All office hours will be held online on BBC Ultra.
Communication policy: I try to respond to all emails, but during the semester my email load may become too high, in which case I may miss responding to some emails. If your question is urgent and I do not respond promptly, please send me a reminder. For all non-urgent class-related questions, please use the class Piazza (accessible from Canvas) and/or one of the office hours slots.
Teaching Assistant: Cheuk Yin (Eric) Lin
Email: clin353 at wisc dot edu
Office hours: TBD. Held remotely.
Graders: Abhirav Gholba and Seyed Sadeghi
Email: abhirav dot gholba at wisc dot edu
Class Schedule
This class meets online using BB Collaborate Ultra, accessible from the class Canvas page.
The class is scheduled for Mon-Wed-Fri 2.30-3.45pm (75 min). Fri is a supplementary slot and it will be used sparingly; in most of the weeks we will meet only on Mon and Wed. When the Fri slot is used, the students will be notified in advance.
We may have additional 1-2 lectures to cover more advanced topics that are optional and will not be part of the final examination or homework assignments (to be discussed in class and decided based on interest).
General Course Information
Prerequisites
Most of the class is theoretical and assumes mathematical maturity: you need to be comfortable with reading, understanding, and writing proofs. Basic background in linear algebra, real analysis, and probability is expected.
Some of the homework problems will require coding in either Matlab or Python, and basic knowledge of either of these two is expected.
Textbook
We will use the following textbook for some of the topics:
J. Nocedal and S. J. Wright, Numerical Optimization, Second Edition, Springer, 2006.Other resources
For the topics not covered by the textbook additional lecture materials will be shared on Canvas.
Additional books and resources that you may find useful:
- Y. Nesterov, Lectures on Convex Optimization, Springer, 2018.
- A. Beck, First-order Methods in Optimization. Vol. 25. SIAM, 2017.
- S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
- R.T. Rockafellar, R. J-B Wets, Variational Analysis, Springer, 1998.
- D. P. Bertsekas, with A. Nedic and A. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, 2003.
- Dmitriy Drusvyatskiy's course notes on convex analysis and optimization, 2019.
Course Outline
This class focuses on foundations of iterative (first- and second-order) optimization algorithms. In particular, the focus is on understanding and rigorously characterizing when, why, and how well different optimization methods work. The coding assignments are used for illustrating the performance of different optimization methods on some characteristic examples. While we will occasionally mention some interesting applications, this class does not focus on applications or modeling. For these two topics, students may consider CS 524 and different machine learning classes.
This is a tentative list of topics that will be covered in class. Most of the topics listed here will be covered, and some other topics may be added.
- Introduction: general continuous optimization background; convex sets; convex functions; convergence rates.
- Background on smooth unconstrained optimization: Taylor theorem and optimality conditions.
- First-order methods: gradient descent for convex and nonconvex optimization, line search methods, projected gradient descent, mirror descent, Nesterov acceleration for convex optimization, conjugate gradients, conditional gradients (Frank-Wolfe methods), basic coordinate descent, stochastic gradient descent.
- Second-order methods: Newton method, trust-region Newton, inexact Newton methods and Newton-CG, cubic regularization, quasi-Newton methods (DFP, BFGS, SR-1, general Broyden class), limited-memory quasi-Newton (L-BFGS).
Course Load/Assessment
This is a graduate-level class that teaches fundamentals of nonlinear optimization, and, as such, will have a high load, requiring strong commitment to mastering the material. Your focus should not be on the grade -- it should be on learning. The instructor's point of view is that if you go through the class without feeling challenged at all, then you are working below your potential. However, if the class becomes overwhelming and is causing you distress, you are encouraged to come talk to us, and we will look into possible accommodations.
All grades will be posted on Canvas. The information provided here is tentative and is subject to change.
Homework: There will be 5-6 homework assignments, accounting for ~30% of the grade. You may discuss problems with other students, but you need to declare it on your homework submission. Any discussion can be verbal only: you are required to work out and write the solutions on your own. Submitting someone else's work as your own constitutes academic misconduct. Academic honesty is taken very seriously in this class, and any breach of it will be treated according to the University Policy.
Homework assignments and solutions will be posted on Canvas.
Midterm: Date and Time: TBD. Held online. Accounts for ~30% of the grade.
Final: Scheduled for 12/16/2020 2.45-4.45pm. Held online. Accounts for ~40% of the grade.
Academic Policies
Academic Integrity
By enrolling in this course, each student assumes the responsibilities of an active participant in UW-Madison’s community of scholars in which everyone’s academic work and behavior are held to the highest academic integrity standards. Academic misconduct compromises the integrity of the university. Cheating, fabrication, plagiarism, unauthorized collaboration, and helping others commit these acts are examples of academic misconduct, which can result in disciplinary action. This includes but is not limited to failure on the assignment/course, disciplinary probation, or suspension. Substantial or repeated cases of misconduct will be forwarded to the Office of Student Conduct & Community Standards for additional review. [link]
Disability Accomodation
The University of Wisconsin-Madison supports the right of all enrolled students to a full and equal educational opportunity. The Americans with Disabilities Act (ADA), Wisconsin State Statute (36.12), and UW-Madison policy (Faculty Document 1071) require that students with disabilities be reasonably accommodated in instruction and campus life. Reasonable accommodations for students with disabilities is a shared faculty and student responsibility. Students are expected to inform faculty [me] of their need for instructional accommodations by the end of the third week of the semester, or as soon as possible after a disability has been incurred or recognized. Faculty [I], will work either directly with the student [you] or in coordination with the McBurney Center to identify and provide reasonable instructional accommodations. Disability information, including instructional accommodations as part of a student's educational record, is confidential and protected under FERPA. [link]
Institutional Statement on Diversity
Diversity is a source of strength, creativity, and innovation for UW-Madison. We value the contributions of each person and respect the profound ways their identity, culture, background, experience, status, abilities, and opinion enrich the university community. We commit ourselves to the pursuit of excellence in teaching, research, outreach, and diversity as inextricably linked goals.
The University of Wisconsin-Madison fulfills its public mission by creating a welcoming and inclusive community for people from every background – people who as students, faculty, and staff serve Wisconsin and the world. [link]