Online Convex Optimization with Unconstrained Domains and Losses
This work addresses a fundamental limitation in online convex optimization by enabling algorithms to operate without predefined loss bounds, which is crucial for applications where such bounds are unknown or dynamic.
The paper tackles online convex optimization with unconstrained domains and losses by proposing RescaledExp, an algorithm that achieves optimal regret without prior knowledge of loss bounds, matching a proven lower bound asymptotically and performing empirically as well as prior methods that require hyperparameter tuning.
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.