A Modern Introduction to Online Learning IV: Every Deterministic Online Linear Optimization Algorithm Has Regret at Least √2·LD√T/4Textbook
Online learning studies decisions made before their costs are known. An algorithm selects a point, observes a loss, and repeats. Regret compares its accumulated loss with the loss of one fixed point chosen after the sequence is known. Upper bounds show what a particular algorithm can guarantee; a lower bound shows what every algorithm must sometimes suffer.…