Class Schedule Listing |
Fall 2025 Semester
Sep 14, 2026 |
|
 |
||
| Special Topics in Theoretical Computer Science - 20859 - CS 7880 - 01 | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Course title: From Convex Analysis to Learning, Prediction, and Elicitation
Description: This special topics course introduces the basics of convex analysis and explores its wide-ranging applications across optimization, machine learning, computational economics, and complexity theory. We begin with the geometrically intuitive yet remarkably powerful hyperplane separation theorem, using it to derive the well-known and widely-used minimax theorems and Lagrange duality. We show how concepts from convex analysis (such as convex conjugation and the Fenchel-Young divergence) illuminate the algorithmic ideas behind the mirror descent framework, which encompasses the celebrated multiplicative weights algorithm as a special case and gives constructive proofs of the minimax and duality theorems. We discuss a broad spectrum of applications of mirror descent—boosting, no-regret online learning, online calibration, Blackwell’s approachability, regularity lemma, multicalibration, omniprediction, pseudo-entropy characterizations—spanning areas from learning, probabilistic forecasting, uncertainty quantification, differential privacy and algorithmic fairness to pseudorandomness, complexity theory and game theory. We also discuss the fundamental role of convex analysis in economics theory, particularly in the study of proper scoring rules and property elicitation. In the final part of the course, students will lead discussions on research topics in computer science, statistics, and economics that use convex analysis. These may include algorithms with predictions, multi-distribution learning, Blackwell's informativeness theorem, isotonic regression, generalized linear models, single-index models, dense model theorem, metric entropy duality, and more.
Prerequisites: No formal prerequisites. Interest in machine learning, computational economics, optimization algorithms, or pseudorandomness is preferred.
Workload: 2-3 homework assignments with about 3 questions each. One group presentation surveying a related research topic. There may be optional exercises for interested students.
Associated Term: Fall 2025 Semester Registration Dates: Apr 01, 2025 to Sep 16, 2025 Levels: Graduate Attributes: GSCS Computer & Info Science, Topics Course Boston Campus Lecture Schedule Type Traditional Instructional Method 4.000 Credits View Catalog Entry
|
| Return to Previous |
|
