CS 7880: Special Topics in Theoretical Computer Science

From Convex Analysis to Learning, Prediction, and Elicitation 

Fall 2025

Instructor: Lunjia Hu

Location: Shillman Hall 325

Time: Tuesdays 11:45 AM – 01:25 PM and Thursdays 02:50 PM – 04:30 PM

Workload

2-3 homework assignments with about 3 questions each. Reading and presenting classic and recent research papers. Leading and participating in research discussions. No exams.

Topics

Convex analysis basics: hyperplane separation theorem, minimax theorem, Lagrange duality

Online learning and optimization: experts problem, online convex optimization, multiplicative weights, mirror descent

Decision theory: calibration, multicalibration, omniprediction

Complexity theory: regularity lemma, pseudorandomness and pseudoentropy, hardcore lemma and dense model theorem

Economics / game theory: proper scoring rules, property elicitation

Overview

This special topics course introduces the basics of convex analysis and explores its wide-ranging applications across optimization algorithms, machine learning, computational economics, and complexity theory. We begin with the geometrically intuitive yet remarkably powerful hyperplane separation theorem, using it to establish 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 second half 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.

Notes

  • Notes 1 Hyperplane Separation Theorems
  • Notes 2 Minimax Theorems
  • Notes 3 Lagrange Duality and Slater’s Condition
  • Notes 4 No-Regret Online Learning (Experts Problem and Online Linear Optimization)
  • Notes 5 Saddle Points, KKT Conditions, and Constructive Minimax Theorem
  • Notes 6 Follow the Regularized Leader, Multiplicative Weights
  • Notes 7 Convex Conjugation and Fenchel-Young Divergence
  • Notes 8 Regularity Lemma
  • Notes 9 Blackwell Approachability and Online Calibration
  • Notes 10 Proper Scoring Rules, Revelation Principle, Generalized Linear Models
  • Notes 11 Pseudoentropy Characterizations
  • Notes 12 Gradient Boosting, AdaBoost

Homeworks

Resources

Jacob Abernethy. Prediction and Learning: It’s Only a Game

Sergiu Hart. Calibrated Forecasts: The Minimax Proof

Jacob Abernethy, Peter L. Bartlett, Elad Hazan. Blackwell Approachability and No-Regret Learning are Equivalent

Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang. Six Candidates Suffice to Win a Voter Majority

Maxwell Fishelson, Noah Golowich, Mehryar Mohri, Jon Schneider. High-Dimensional Calibration from Swap Regret

Schedule