DSC 243 – Advanced Optimization

Instructor: Dmitriy Drusvyatskiy

Lectures: MWF 10:00–10:50 AM in PCYNH 121

Office Hour: Monday 11:00 AM in HDSI 330

Table of contents

• Course summary
• Pre-requisites
• Notes
• Course outline
• Grading policy
• Textbooks and references

Course summary

This course develops the foundations of the modern optimization methods that form the backbone of machine learning and AI. Building on the prerequisite introductory course in optimization (DSC 211), it takes the convex quadratic optimization problem as its central object of study. Optimization of quadratics is the most fundamental problem in numerical optimization, yet many of the phenomena for this particular problem class have direct analogues for highly nonlinear and complex models (e.g. deep learning). Since the objective is quadratic, we can develop sharp intuition for the design, analysis, and practical behavior of algorithms using only basic linear-algebraic tools. We will study both worst-case convergence rates—depending only on extremal eigenvalues—and more refined guarantees that account for the interaction between initialization and the shape of the entire spectrum, covering gradient descent, Chebyshev acceleration, conjugate gradients, stochastic gradient methods, lower bounds, and the high-dimensional limits that connect these ideas to large-scale machine learning. The emphasis throughout is on gaining both theoretical insight and algorithmic intuition—understanding why methods work, how to choose between them, and how they scale to real-world settings.

Pre-requisites

• Introductory course on optimization (DSC 211 or equivalent)
• Comfort with advanced linear algebra and multivariate calculus

Notes

The notes for the course are being developed. Here is the latest draft: notes.

Course outline

Grading policy

All grades will be based on homework sets, which will be due roughly every two weeks.

Canvas

I will use Canvas only for communicating by email with the class. All course material will appear on this webpage.

Textbooks and references

This course is largely self-contained with no required textbook. Specific results are cited inline in the lecture notes; the sources below are background and follow-up reading, grouped by the topics they support.

First-order and stochastic optimization (gradient descent, acceleration, SGD).

• A. Beck. Introduction to Nonlinear Optimization – Theory, Algorithms and Applications. SIAM, 2014.
• S. Bubeck. Convex Optimization: Algorithms and Complexity. 2015.
• J. Duchi. Introductory Lectures on Stochastic Convex Optimization. 2016.
• G. Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer, 2020.
• Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2004.
• B. Recht and S. J. Wright. Optimization for Modern Data Analysis. Cambridge University Press, 2022.
• A. Sidford. Optimization Algorithms.

Krylov subspace methods and conjugate gradients.

• A. Greenbaum. Iterative Methods for Solving Linear Systems. SIAM, 1997.
• Y. Saad. Iterative Methods for Sparse Linear Systems. 2nd ed., SIAM, 2003.

Spectral structure, inverse problems, and random matrices.

• Z. Bai and J. W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. 2nd ed., Springer, 2010.
• H. W. Engl, M. Hanke, and A. Neubauer. Regularization of Inverse Problems. Kluwer, 1996.
• T. Tao. Topics in Random Matrix Theory. Graduate Studies in Mathematics, vol. 132, American Mathematical Society, 2012.
• R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018.

High-dimensional limits of SGD.

• E. Paquette. High-dimensional limits of stochastic gradient descent. Lecture notes, Lehigh University, 2023.