Efficient Minimax Optimal Strategies for Universal Prediction

on YouTube ↗29m

" summary

Shows when the minimax-optimal strategy is computable and what it actually is: a dynamic-program recursion yields normalized maximum likelihood as the unique optimal joint for log loss and this sequential NML is optimal exactly when the induced process is exchangeable, which is equivalent to a Bayesian rule with Jeffreys prior under asymptotic normality. For squared Euclidean loss the predictor shrinks toward the center of the minimal enclosing ball and regret depends only on its radius. For fixed‑design linear regression the minimax rule is linear using sufficient statistics with value equalizer formula sum y_t^2 x_t^T C_t x_t.

AI-written summary · about

" chapters (6)

1. 0:00Introduction to prediction
2. 4:22Outline of talk
3. 7:14Log loss and NML
4. 16:08Euclidean loss
5. 19:20Online linear regression
6. 26:31Closing and Q&A

" related talks

• 55mLearning Minimax Estimators Via Online LearningPradeep Ravikumar · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 01h 23mImplicit Regularization IINati Srebro · Deep Learning Boot Camp 2019
• 17mCodifying Data Science IntuitionRyan West · MLconf Atlanta 2017
• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 11mLinear Predictors in Reinforcement Learning: ...Andrea Zanette · Meet the Fellows Welcome Event
• 09mTowards Credible and Effective Data-Driven Decision-MakingAngela Zhou · Meet the Fellows Welcome Event
• 45mEfficient Profile Maximum Likelihood for Universal Symmetric Property EstimationMoses Charikar · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 41mTransfer learning via local convergence rates of the nonparametric least squares estimatorJohannes Schmidt-Hieber · Domain Adaptation and Related Areas 2024