# Tight Lower Bounds for Multiplicative Weights Algorithmic Families

arXiv: https://arxiv.org/abs/1607.02834 · HTML: https://mlsanity.com/paper/1607.02834/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2016.

## Built on by (most cited first, 9 of 9)

- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Efficient and Optimal Fixed-Time Regret with Two Experts](https://mlsanity.com/paper/2203.07577/) (2022)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [Numerical solution of a PDE arising from prediction with expert advice](https://mlsanity.com/paper/2406.05754/) (2024)
- [An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB](https://mlsanity.com/paper/2609.14892/) (2026)
- [A PDE approach for regret bounds under partial monitoring](https://mlsanity.com/paper/2209.01256/) (2022)
- [Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs](https://mlsanity.com/paper/2602.06545/) (2026)
- [On prediction from expert advice with more than five experts](https://mlsanity.com/paper/2610.05186/) (2026)

## Abstract (arXiv)

We study the fundamental problem of prediction with expert advice and develop regret lower bounds for a large family of algorithms for this problem. We develop simple adversarial primitives, that lend themselves to various combinations leading to sharp lower bounds for many algorithmic families. We use these primitives to show that the classic Multiplicative Weights Algorithm (MWA) has a regret of √fracT ln k2, there by completely closing the gap between upper and lower bounds. We further show a regret lower bound of frac23√fracTln k2 for a much more general family of algorithms than MWA, where the learning rate can be arbitrarily varied over time, or even picked from arbitrary distributions over time. We also use our primitives to construct adversaries in the geometric horizon setting for MWA to precisely characterize the regret at frac0.391√δ for the case of 2 experts and a lower bound of frac12√fracln k2δ for the case of arbitrary number of experts k.