Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice

11/06/2015
by   Francesco Orabona, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset