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 $\mathbf {t}$ 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 $\mathbf {o(1)}$ , which guarantees the tracking performance for minimizers of time-varying objective functions. Finally, our results are tested through numerical demonstration.