  We propose an online convex optimization algorithm (RescaledExp) that
achieves optimal regret in the unconstrained setting without prior knowledge of
any bounds on the loss functions. 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.
RescaledExp matches this lower bound asymptotically in the number of
iterations. RescaledExp is naturally hyperparameter-free and we demonstrate
empirically that it matches prior optimization algorithms that require
hyperparameter optimization.
