Online Convex Optimization with Unconstrained Domains and Losses

We prove a lower bound showing an exponential separation between the regret of existing algorithms that require a known bound on the loss functions and any algorithm that does not require such knowledge.