CS 726: Nonlinear Optimization I (Fall 2022)

Class is also listed as ISYE 726/MATH 726/STAT 726.

Instructor: Jelena Diakonikolas

Email: jelena at cs dot wisc dot edu

Office hours: Friday 12-2pm, or by appointment, in CS 4369.

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: Puqian Wang

Email: pwang333 at wisc dot edu

Office hours: Tuesday and Thursday 4-5pm (after class), in CS 4331.

Class Schedule

This class meets in Engineering Hall, Rm 2317.

The class is scheduled for Tue-Thu 2.30-3.45pm (75 min).

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 Python, for which basic knowledge is assumed.

Textbook

We will use the following two textbooks for some of the topics:

S. J. Wright and B. Recht, Optimization for Data Analysis, Cambridge University Press, 2022.

J. Nocedal and S. J. Wright, Numerical Optimization, Second Edition, Springer, 2006.

Other resources

For the topics not covered by the textbooks additional lecture materials will be shared on Canvas.

Additional books and resources that you may find useful:

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 and background: general continuous optimization background; p-normed real spaces; convex sets; convex functions; Lipschitz continuous and smooth functions; strongly convex functions; local error bounds; Taylor theorem; 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 ~50% 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 in class. Accounts for ~20% of the grade.

Final: Scheduled for 12/20/2021 10.05am-12.05pm. Location: TBD. Accounts for ~30% 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]