Algorithm design has traditionally been studied from a discrete perspective. Increasingly, however, modern algorithm design has benefitted from adopting a continuous perspective and using tools developed in the study of continuous mathematics. This course provides an introduction to the continuous algorithmic toolkit. In the first part, we survey topics in optimization theory (e.g., minimax and stochastic optimization, interior-point methods, and provable methods for structured nonconvex problems). We also highlight connections to approximation theory and numerical linear algebra. In the second part, we build methods for sampling from continuous spaces, from general-purpose logconcave samplers to recent analysis techniques from stochastic differential equations and optimal transport, with applications to modern diffusion models.

Course information: Here.

Time and location: 3:30 to 5:00 PM, Tuesdays and Thursdays (GDC 6.202).

Instructor: Kevin Tian, kjtian (at) cs (dot) utexas (dot) edu.
Office hours: 3:30 to 5:00 PM, Mondays (GDC 4.720).

TA: Yusong Zhu, zhuys (at) utexas (dot) edu.
Office hours: 10:00 to 11:00 AM, Tuesdays and Thursdays (Location TBD).

Assignments (due on the specified dates at the start of class) will be posted below when they become available. Unless we have discussed and I have specified otherwise, homework is not accepted if it is not turned in by hand at the start of class, or turned in electronically on Canvas by then. Send me an email to discuss any exceptions.

Dates	Topic	Notes	Announcements
	Notation	PDF
1/13, 1/15	Convexity, logconcavity, and continuous algorithms		HW I out
1/20, 1/22	Gradient descent
1/27, 1/29	Mirror descent
2/3	Minimax optimization		HW I due, HW II out
2/5	Acceleration and high-order methods
2/10, 2/12	Matrix analysis and concentration
2/17	Polynomial approximations
2/19	Matrix multiplicative weights		HW II due, HW III out
2/24	Linear regression
2/26	Interior-point methods
3/3	Low-rank approximation
3/5	Sparse recovery
3/10	Generalized linear models
3/12	Nonconvex optimization		HW III due, HW IV out
3/17, 3/19	Spring break (no class)
3/24	Spectral graph theory
3/26, 3/31	Continuous random walks
4/2, 4/7, 4/9	Stochastic calculus		HW IV due, HW V out
4/14	Langevin algorithms
4/16	Restricted Gaussian dynamics
4/21, 4/23	Stochastic localization		HW V due

Reversible Markov Chains and Random Walks on Graphs, Aldous and Fill.
Concentration Inequalities: A Nonasymptotic Theory of Independence, Boucheron, Lugosi, and Massart.
Convex Optimization: Algorithms and Complexity, Bubeck.
Algorithms for Data Science, Chen.
Log-Concave Sampling, Chewi.
Recent Advances in Algorithmic High-Dimensional Statistics, Diakonikolas and Kane.
Lecture Notes on Statistics and Information Theory, Duchi.
Probability: Theory and Examples, Durrett.
The Algorithmic Foundations of Differential Privacy, Dwork and Roth.
Algorithms for Private Data Analysis, Kamath.
Computational Learning Theory, Kanade.
Spectral Algorithms, Kannan and Vempala.
The art and science of positive definite matrices, Lee.
Techniques in Optimization and Sampling, Lee and Vempala.
Markov Chains and Mixing Times, Levin, Peres, and Wilmer.
Robustness in Machine Learning, Li.
Algorithmic Aspects of Machine Learning, Moitra.
Interior-Point Polynomial Algorithms in Convex Programming, Nemirovski and Nesterov.
Problem Complexity and Method Efficiency in Optimization, Nemirovski and Yudin.
Lectures on Convex Optimization, Nesterov.
Stochastic Differential Equations: An Introduction with Applications, Øksendal.
Sublinear Algorithms, Price.
Faster Algorithms via Approximation Theory, Sachdeva and Vishnoi.
Expanders and Fast Graph Algorithms, Saranurak.
Online Learning and Online Convex Optimization, Shalev-Shwartz.
Optimization Algorithms, Sidford.
Spectral and Algebraic Graph Theory, Spielman.
Convex Optimization, Tibshirani.
Approximation Theory and Approximation Practice, Trefethen.
An Introduction to Matrix Concentration Inequalities, Tropp.
Algorithmic Convex Geometry, Vempala.
Dynamic Algebraic Algorithms, van den Brand.
Probability in High Dimension, van Handel.
High-Dimensional Probability: An Introduction with Applications in Data Science, Vershynin.
Optimal transport, old and new, Villani.
Algorithms for Big Data, Waingarten.
Sketching as a Tool for Numerical Linear Algebra, Woodruff.
Lecture Notes on: Information-Theoretic Methods for High-Dimensional Statistics, Wu.

Please provide feedback on lectures or notes using the provided links.