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

Abstract

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.

Cited by in corpus (6)

• MaxUp: A Simple Way to Improve Generalization of Neural Network Training
• Online Learning of Network Bottlenecks via Minimax Paths
• New Potential-Based Bounds for Prediction with Expert Advice
• Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers
• Online Learning with Optimism and Delay