Extending Generalization Theory Towards Addressing Modern Challenges in Machine Learning
summary
Main claim: any 0/1 infinite game that violates the Minimax equality contains arbitrarily large copies of Jewish poker, i.e. arbitrarily large triangular submatrices up to row and column permutations, and conversely absence of such triangles guarantees Minimax. Proof builds bounded-size finite blocks S_i and T_j by sampling via VC theory and uniform laws of large numbers, then extracts an infinite triangular subgame using the Ramsey theorem. Conjecture: rule can be sharpened to forbid only infinite triangles.
AI-written summary · about
chapters (6)
- 0:00Introduction and context
- 4:33Defining the Minimax theorem
- 8:36The problem of infinite games
- 13:12Main theorem and obstacles
- 16:54Open questions and discussion
- 21:12Proof sketch and lemmas
related talks
25mReal Algebraic Geometry in Computational Game Theory
47mUnprovability and Other Impossibility Results in Machine Learning
20mThe Complexity of Infinite-Horizon General-Sum Stochastic Games
01h 06mLearning in Games II
44mThe State of Techniques for Solving Large Imperfect-Information Games
01h 11m(Hidden) Symmetries of Computational Problems (continued)
41mDavid Blackwell: Teacher And Colleague And A Sample Of His Work
01h 40mBoot camp on generalization theory for graph learning