Definition
The multiplicative weight update method is a fundamental online learning algorithm used to make decisions in uncertain environments. It maintains a set of weights for different strategies or experts, updating them multiplicatively based on their past performance. Strategies that perform well have their weights increased, while poor performers see their weights decreased. This method is widely used in game theory, optimization, and machine learning for constructing efficient prediction algorithms with provable convergence guarantees.
Summary
An iterative algorithm that updates weights multiplicatively based on performance feedback to minimize regret.
Key Concepts
- Online learning
- Weighted majority algorithm
- Regret minimization
- Exponential weighting
Use Cases
- Portfolio optimization
- Expert advice aggregation
- Adversarial bandit problems