Online Learning With Non-convex Losses: New Condition To Achieve Small Dynamic Regret

Abstract

In this paper, we consider the challenging problem of online learning with non-convex time varying objectives/loss functions. We show that a simple Online gradient descent (OGD) algorithm achieves a dynamic regret comparable to the strongly convex setting provided a new condition that we propose is satisfied within a ball centered at the initialization and radius ρ. Our condition depends on gradients, loss functions, ρ, and the variation that measures the rate at which the function changes over time thereby capturing the online nature of the problem. Assuming that the condition is satisfied, we show that OGD achieves a dynamic regret that scales linearly with the variation. We corroborate our theoretical findings through experiments.