Skip to yearly menu bar Skip to main content


Online Convex Optimization with Unconstrained Domains and Losses

Ashok Cutkosky · Kwabena A Boahen

Area 5+6+7+8 #76

Keywords: [ Stochastic Methods ] [ Convex Optimization ] [ Online Learning ]


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.

Live content is unavailable. Log in and register to view live content