S&DS 432/632: Advanced Optimization Techniques (Spring 2025)

Course Description: This course covers fundamental optimization algorithms and their theoretical analysis, emphasizing convex optimization. Topics covered include gradient descent and acceleration; lower bounds; structured problems; Newton's method; and interior point methods. Prerequisites: Knowledge of linear algebra, such as MATH 222/225; multivariate calculus, such as MATH 120; probability, such as S&DS 241/541; optimization, such as S&DS 431/631; and comfort with proof-based exposition and problem sets.

Instructor: Sinho Chewi (sinho.chewi@yale.edu)

References

• Lecture notes.
• [B] S. Bubeck, Convex optimization: algorithms and complexity (2015).
• [N] Y. Nesterov, Lectures on convex optimization (2018).
• [NN] Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming (1994).

Schedule

The course meets on Tuesdays and Thursdays, 1–2.15 p.m., in Kline Tower 203. I will also be available for an hour after each class if you have any questions or if you would like to discuss. If these times do not work for you, or if you have any other concerns, please reach me via email.

• Jan. 14 (Tuesday): Overview of the course, preliminaries on convexity and smoothness.
• Jan. 16 (Thursday): Gradient flow.
• Jan. 21 (Tuesday): Gradient descent: smooth case.
• Jan. 23 (Thursday): Reductions and lower bounds for smooth convex optimization.
• Jan. 28 (Tuesday): Acceleration for quadratics: conjugate gradient.
• Jan. 30 (Thursday): Acceleration in continuous time.
• Feb. 4 (Tuesday): Acceleration in discrete time. Convex analysis.
• Feb. 6 (Thursday): Convex analysis and projected subgradient methods.
• Feb. 11 (Tuesday): Projected subgradient methods and cutting plane methods.
• Feb. 13 (Thursday): Lower bounds for non-smooth convex optimization.
• Feb. 18 (Tuesday): Lower bounds continued. Frank–Wolfe.
• Feb. 20 (Thursday): Proximal methods.

Assignments

Grades are based solely on six problem sets and one take-home final exam. Tentatively, the problem sets will be released on 1/21, 2/4, 2/18, 3/4, 3/25, and 4/8, and each one is due roughly two weeks after it is assigned. For each problem set, the last problem is mandatory for students taking S&DS 632, and extra credit for all other students. Each problem set is weighted equally with the final, so each count for 1/7 of the total grade.

Please feel free to work on the problem sets with others, but list your collaborators at the beginning of your submission. Solutions should be arrived at without the use of AI. Problem sets should be typed in LaTeX and submitted via Gradescope (the link can be found in Canvas).