Online Convex Optimization with Unconstrained Domains and Losses
  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.
