Learning Minimax Estimators Via Online Learning
Talkat Algorithmic Advances for Statistical Inference with Combinatorial Structure · 2021-10-11..10-15·
summary
Proposes solving the minimax estimation problem by reducing the zero‑sum game to an online learning loop that alternates a Bayes estimator best response with nature running Follow the Perturbed Leader, proving the averaged strategies form an approximate mixed Nash equilibrium with additive error alpha+beta+O(1/√T). Implements this with oracles (approximate Bayes and finite‑dimensional maximizer), yields randomized minimax estimators that beat MLE/ridge/Jain‑Stein in Gaussian sequence, linear regression and entropy tasks, but producing a deterministic minimax rule is NP‑hard.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:36Learning to Learn
- 1:34Estimators
- 5:06Minimax Statistical Estimators
- 7:09Zerosum Statistical Gain Between
- 8:15Nash Equilibrium
- 13:42Online Learning
- 16:51Mixed Nash Equilibrium
- 20:42Sublinear Regret Strategy
- 23:00Nature
- 33:03General Setups
- 39:18Minimax Optimal
- 42:51Minimax Linear
- 45:03Entropy Estimation
- 46:53Summary
- 48:47Questions
- 49:44Theorem
- 51:17Linear Regression
related talks
29mEfficient Minimax Optimal Strategies for Universal Prediction
48mOnline Adversarial Multicalibration And (Multi)Calibeating
15mFundamental Limits Of Learning In Data-Driven Problems
49mOracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning
57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max Optimization
01h 00mMin-Max Optimization from a Dynamical Systems Viewpoint
01h 17mOnline Reinforcement Learning and Regret
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control