2020/06/10 by Peng Zhao, Lijun Zhang, Zhao, Peng +1 · 1 citation
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2006.05876
openalex publication_date 2020/06/10 · openalex created_date 2020/06/19 · openalex updated_date 2026/07/28
In this paper, we present an improved analysis for dynamic regret of strongly convex and smooth functions. Specifically, we investigate the Online Multiple Gradient Descent (OMGD) algorithm proposed by Zhang et al. (2017). The original analysis shows that the dynamic regret of OMGD is at most O(min\PT,ST\), where PT and ST are path-length and squared path-length that measures the cumulative movement of minimizers of the online functions. We demonstrate that by an improved analysis, the dynamic regret of OMGD can be improved to O(min\PT,ST,VT\), where VT is the function variation of the online functions. Note that the quantities of PT, ST, VT essentially reflect different aspects of environmental non-stationarity -- they are not comparable in general and are favored in different scenarios. Therefore, the dynamic regret presented in this paper actually achieves a best-of-three-worlds guarantee and is strictly tighter than previous results.