Forgetting-Factor Regrets for Online Convex Optimization

This paper develops a class of novel algorithms for online convex optimization. The key construct is a forgetting-factor regret. It introduces weights to the objective functions at each time instant <tex-math notation="LaTeX">t</tex-math> and allows the weights of the past objective functions decaying to zero. We establish the forgetting-factor regret bounds of classical algorithms including online gradient descent algorithms, online gradient-free algorithms, and online Frank-Wolfe algorithms. In addition, the paper introduces online gradient descent algorithm with a forgetting factor, and analyze its performance under the new regret. Sufficient conditions are obtained to guarantee the bounds of the forgetting-factor regret of the above algorithms being of the order <tex-math notation="LaTeX">o(1)</tex-math> , which guarantees the tracking performance for minimizers of time-varying objective functions. Finally, our results are tested through numerical demonstration.