Description: The study of optimal transport problems goes back to the 1700s, and played critical in early work on linear programming in the middle of the last century. The past 20 years have seen substantial progress in the theory and application of optimal transport ideas, including Wasserstein distances, in a variety of fields including statistics, AI, mathematics, engineering, and genomics. Optimal transport builds on key ideas from probability (including the notion of coupling, widely used in the theory of Markov chains) as well as optimization (including linear programming and entropy regularization).
The course will cover and develop from first principles the basic theory of optimal transport, including Kantorovitch duality, cyclic monotonicity, Brenier’s theorem and Wasserstein spaces. We will also present and study computational techniques including entropy regularization and the Sinkhorn algorithm. As time and class interest permit, we will cover some applications of optimal transport, including multivariate quantiles and network alignment. Most topics will be self-contained.
Audience: The course should be appropriate for graduate students in STOR, Mathematics, and Biostatistics with appropriate math backgrounds (see prerequisites below).
Class meetings: Mondays and Wednesdays 1:25pm – 2:40pm in Hanes 130
Prerequisites: While we will focus on basic theory, and not strive for utmost generality, the core material of the class requires a good working knowledge of real analysis, measure theoretical probability, and at least some familiarity with theoretical statistics. Students should be familiar and comfortable with convex sets and functions, Lebesgue integration, weak convergence of probability measures, and metric spaces.
Registration: Enrollment and registration for the course is handled online. Please contact Ms. Christine Keat (crikeat@email.unc.edu) if you have questions.
Instructor: Andrew B. Nobel
Office: Hanes 308 Email: nobel@email.unc.edu
Nobel Office Hours: TBA
Protocol for lectures
- Please arrive before the beginning of the lecture and leave after the end of the lecture. If you need to arrive late or leave early, let the instructor know in advance.
- Please restrict the use of electronic devices to those needed for note taking
Sources: There is no official textbook for the course. Lectures will be based largely on the following sources (all freely available online):
“Optimal Transport and Wasserstein Distance”, lecture notes from L. Wasserman
“Optimal Mass Transport: Signal processing and machine learning applications”, by S.Kolouri et al. An overview of optimal transport and some of its applications.
“Statistical Optimal Transport”, by S. Chewi, J. Niles-Weed, and P. Rigollet
“Optimal Transport, Old and New”, by C. Villani
“Computational Optimal Transport”, by G. Peyre and M. Cuturi
“Probability in High Dimensions”, by R. van Handel. Chapter 4 of this text provides an overview of transportation based concentration inequalities
Grading: Course grades will be based on a final group presentation/report and periodic homework assignments. There will be no exams or quizzes.
Tentative Syllabus (subject and certain to change):
Introduction
- Couplings, examples and properties
- Distances between probability measures
- General Wasserstein distances
- First properties of couplings
- Existence of optimal couplings
Optimal transport in R^d
- Monge and Kantorovich optimal transport problems in R^d
- Wasserstein distances in R^d
- sub gradients of convex functions
- Brenier’s theorem
- Kantorovich duality
Estimation of Wasserstein distances
- Wasserstein law of large numbers
- rates of convergence
- lower bounds on rates
- minimax lower bound
- rates for regularized and sliced Wasserstein distances
*Estimation of transport maps
Optimal transport with entropy regularization
- motivation and derivation
- duality
- Sinkhorn algorithm
- rates for primal and dual solutions
General theory of optimal transport
- cyclical monotonicity
- c-convexity and c-transforms
- Kantorovich duality
- optimality and cyclic monotonicity
- stability of optimal transport
- compactness of optimal transport plans
More on computational optimal transport
Transport based concentration inequalities for Lipschitz functions
- subgaussian random variables
- review of Gaussian concentration and bounded difference inequalities
- transportation inequalities and tensorization
- dimension free concentration
Honor Code Policy
As a condition of joining the Carolina community, Carolina students pledge “not to lie, cheat, or steal” and to hold themselves, as members of the Carolina community, to a high standard of academic and non-academic conduct while both on and off Carolina’s campus. This commitment to academic integrity, ethical behavior, personal responsibility and civil discourse exemplifies the “Carolina Way,” and this commitment is codified in both the University’s Honor Code and in other University student conduct-related policies.
Accessibility Resources
The University of North Carolina at Chapel Hill facilitates the implementation of reasonable accommodations, including resources and services, for students with disabilities, chronic medical conditions, a temporary disability or pregnancy complications resulting in barriers to fully accessing University courses, programs and activities.
Accommodations are determined through the Office of Accessibility Resources and Service (ARS) for individuals with documented qualifying disabilities in accordance with applicable state and federal laws. See the ARS Website for contact information: https://ars.unc.edu or email ars@unc.edu.
Counseling and Psychological Resources
CAPS is strongly committed to addressing the mental health needs of a diverse student body through timely access to consultation and connection to clinically appropriate services, whether for short or long-term needs. Go to their website: https://caps.unc.edu/ or visit their facilities on the third floor of the Campus Health Services building for a walk-in evaluation to learn more.
Title IX Resources
Any student who is impacted by discrimination, harassment, interpersonal (relationship) violence, sexual violence, sexual exploitation, or stalking is encouraged to seek resources on campus or in the community. Please contact the Director of Title IX Compliance (Adrienne Allison – Adrienne.allison@unc.edu), Report and Response Coordinators in the Equal Opportunity and Compliance Office (reportandresponse@unc.edu), Counseling and Psychological Services (confidential), or the Gender Violence Services Coordinators (gvsc@unc.edu; confidential) to discuss your specific needs. Additional resources are available at safe.unc.edu.
University Attendance Policy
No right or privilege exists that permits a student to be absent from any class meetings, except for these University Approved Absences:
-
- Authorized University activities
- Disability/religious observance/pregnancy, as required by law and approved by Accessibility Resources and Service and/or the Equal Opportunity and Compliance Office (EOC)
- Significant health condition and/or personal/family emergency as approved by the Office of the Dean of Students, Gender Violence Service Coordinators, and/or the Equal Opportunity and Compliance Office (EOC).