Tight Lower Bounds for Multiplicative Weights Algorithmic Families

DOI10.4230/LIPICS.ICALP.2017.48zbMATH Open1441.68204arXiv1607.02834OpenAlexW2467092399MaRDI QIDQ5111379FDOQ5111379

Yuval Peres, Balasubramanian Sivan, N. V. Gravin

Publication date: 27 May 2020

Abstract: 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

s q r t f r a c T l n k 2

, there by completely closing the gap between upper and lower bounds. We further show a regret lower bound of

f r a c 23 s q r t f r a c T l n k 2

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

f r a c 0.391 s q r t d e l t a

for the case of

2

experts and a lower bound of

f r a c 12 s q r t f r a c l n k 2 d e l t a

for the case of arbitrary number of experts

k

.

Full work available at URL: https://arxiv.org/abs/1607.02834

zbMATH Keywords

lower bounds multiplicative weights adversarial primitives

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (2)

This page was built for publication: Tight Lower Bounds for Multiplicative Weights Algorithmic Families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111379)