Game-Theoretic Probability, Statistics, and Machine Learning
When: TTh 11:00a-12:15p
Where: KCEN N252
Professor: Rafael Frongillo
Syllabus: below
Assignments, grades: Canvas (coming soon)
Communication: Zulip
Schedule, papers, signups: Spreadsheet (coming soon)
Syllabus
Overview
This class will explore the mathematical foundation of game-theoretic statistics, an emerging area in modern statistics, and highlight connections to machine learning. As with the previous iteration of this course, a major theme will be the difference, if any, between performance guarantees which hold under probabilistic assumptions about the world, versus those that hold even without them (worst-case, in some sense).
The class will begin with lectures to give adequate background, and then transition to student presentations on related research papers of their choosing. Assessment will be based on participation in discussions, a final project on a topic related to the course, and occasional light problem sets on foundational concepts. Students with backgrounds outside of computer science are welcome. Students who are primarily interested in only a subset of the topics are still encouraged to enroll.
Prerequisites: I would suggest a solid background in at least one of {algorithms, machine learning, mathematical statistics}, and "mathematical maturity", meaning a grasp of proof writing and balancing intuition with formal arguments.
Materials: There are no official textbooks. Instead we will work through some notes on game-theoretic probability (a work in progress...), as well as several other books and research papers.
Tentative Schedule
The course will follow a similar set of topics and structure to a course by Aaditya Ramdas, but with more focus on related work in machine learning like online learning and calibration metrics.
A tentative plan follows:
- Week 1-2: Game-theoretic statistics: basics
- Week 3-4: Game-theoretic probability
- Week 5-6: Connections to machine learning
- Week 7-13: Paper presentations, project updates
- Week 14-16: Project presentations
Guidelines for paper presentations
When you present a paper to the class, you should prepare slides that go over the paper in detail, aiming for about 30 minutes. Here is a rough guideline that you should feel free to deviate from:
- Motivation, setting, relevant previous work. [1-5 minutes]
- Overview of main results. [2-5 minutes]
- In-depth proof sketch of one of the main results (check with me about which result to focus on). You should be able to walk through the key steps of the proof so that everyone walks away understanding exactly why the result holds, but not necessarily detailed enough that they could sit down and prove it. [10-20 minutes]
- Comments on future or subsequent work. [1-5 minutes]
You should email me your slides at least 3 days before your presentation so that I can give you feedback. (Even better to email me an outline of your slides 4+ days before, so you don't spend time on slides that I'll suggest cutting / you won't have time for!)
Final Project
For your final project, you are welcome to work alone or in groups of 2 (maybe 3 if we have enough students). The purpose of the project is to engage in research related to the topics covered in class. This could mean exploring a connection with your existing research, tackling one of the open problems discussed in class, or coming up with your own topic or question (related to class of course). The final product of the project will be a report written in the style of a scientific paper which describes the findings (see below). For students preferring a more "expository" project, where they focus on understanding existing research / material rather than trying to extend it, let me know and we can probably come up with some suitable ideas.
The following components comprise your final project grade:
-
Mini-proposal: The goal for this assignment is to give you a chance to run your project idea(s) by me to make sure it/they will fit, before you write the full 2-page proposal (below). To this end, you should give whatever details you think would be relevant. At a bare minimum though, give a paragraph or two sketching the topic, motivation, previous work, questions, and techniques (again, see below). And if you have a few potential project ideas, do the same for each.
-
Proposal: Submit a 1-to-2-page document as a group listing the group members, the topic, its motivation and relevant existing work (with citations), explicit questions that you will pursue, techniques that you think will be relevant, and a rough timeline/plan for the research. While the focus of this class is theoretical, more applied research projects may be appropriate. If you are not sure whether your topic will be acceptable, please ask me after class. If your proposal is not accepted I will ask you to revise or submit another.
-
Status report: Roughly mid-way through the project period, groups will give short presentations describing their progress. This is partly for you to receive feedback and ask for suggestions (especially if you are stuck), but also to ensure that you do not leave the project to the last minute. All students involved in the project should speak.
-
Final presentation: Same as the status report, but roughly 20-30 minutes depending on the number of projects.
-
Final write-up: The most important deliverable is the final project write-up, which should describe your findings in the style of a scientific publication, either in a journal (e.g. JMLR, Annals of Statistics, or similar) or conference (e.g. COLT) format. Take the write-up seriously, and write it as if you were actually submitting it for publication. (Indeed, some groups may end up doing so.) This means you should have a proper abstract, introduction, related work, and citations throughout, and any reader of the target journal audience should be able to follow easily. There will not be strict requirements on the length, but you should aim for a length comparable to a COLT submission, which is to say roughly 12 pages in that format, plus references and an appendix.
Resources
Hypothesis testing with e-values. Ramdas and Wang, 2024.
Glenn Shafer's book summary, 2025.
Game-theoretic statistics and safe anytime-valid inference. Ramdas, Grunwald, Vovk, Shafer, 2022.