Forgetting-Factor Regrets for Online Convex Optimization

• 成果类型: Article
• 署名作者: Liu, Yuhang; Zhao, Wenxiao; Yin, George
• 署名单位: Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; University of Connecticut
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3340120
• 发表日期: 2024
• 页码: 5034-5048
• 关键词: Prediction algorithms; optimization; linear programming; Heuristic algorithms; Convex functions; Target tracking; Loss measurement; Forgetting-factor regret; iterative optimization algorithm; online convex optimization

摘要

This article develops a class of novel algo-rithms for online convex optimization. The key constructis a forgetting-factor regret. It introduces weights to theobjective functions at each time instanttand allows theweights of the past objective functions decaying to zero.We establish the forgetting-factor regret bounds of clas-sical algorithms including online gradient descent algo-rithms, online gradient-free algorithms, and online Frank-Wolfe algorithms. In addition, the article introduces onlinegradient descent algorithm with a forgetting factor, andanalyze its performance under the new regret. Sufficientconditions are obtained to guarantee the bounds of theforgetting-factor regret of the above algorithms being of theorder o(1), which guarantees the tracking performance forminimizers of time-varying objective functions. Finally, ourresults are tested through numerical demonstration