Second-Order Online Nonconvex Optimization

• 成果类型: Article
• 署名作者: Lesage-Landry, Antoine; Taylor, Joshua A.; Shames, Iman
• 署名单位: University of California System; University of California Berkeley; University of Melbourne; University of Toronto; University of Melbourne
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3040372
• 发表日期: 2021
• 页码: 4866-4872
• 关键词: Optimization; Heuristic algorithms; Newton method; Convex functions; Radio frequency; Prediction algorithms; mirrors; Moving target localization; Newton's method; online nonconvex; Convex Optimization; time-varying optimization

摘要

We present the online Newton's method, a single-step second-order method for online nonconvex optimization. We analyze its performance and obtain a dynamic regret bound that is linear in the cumulative variation between round optima. We show that if the variation between round optima is limited, the method leads to a constant regret bound. In the general case, the online Newton's method outperforms online convex optimization algorithms for convex functions and performs similarly to a specialized algorithm for strongly convex functions. We simulate the performance of the online Newton's method on a nonlinear, nonconvex moving target localization example and find that it outperforms a first-order approach.