Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice
This work addresses foundational theoretical limits in online learning, specifically for researchers in machine learning theory, by establishing precise regret bounds that are asymptotically optimal.
The paper tackles the problem of deriving non-asymptotic lower bounds for the maximum of independent Gaussian variables and symmetric random walks, recovering optimal leading constants, and applies this to provide an asymptotically optimal non-asymptotic lower bound on the minimax regret in online learning with expert advice.
We prove non-asymptotic lower bounds on the expectation of the maximum of $d$ independent Gaussian variables and the expectation of the maximum of $d$ independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (asymptotically optimal) non-asymptotic lower bound on the minimax regret of online learning with expert advice.