تقرير
Optimistic Online Convex Optimization in Dynamic Environments
العنوان: | Optimistic Online Convex Optimization in Dynamic Environments |
---|---|
المؤلفون: | Meng, Qing-xin, Liu, Jian-wei |
سنة النشر: | 2022 |
المجموعة: | Computer Science Mathematics |
مصطلحات موضوعية: | Computer Science - Machine Learning, Mathematics - Optimization and Control |
الوصف: | In this paper, we study the optimistic online convex optimization problem in dynamic environments. Existing works have shown that Ader enjoys an $O\left(\sqrt{\left(1+P_T\right)T}\right)$ dynamic regret upper bound, where $T$ is the number of rounds, and $P_T$ is the path length of the reference strategy sequence. However, Ader is not environment-adaptive. Based on the fact that optimism provides a framework for implementing environment-adaptive, we replace Greedy Projection (GP) and Normalized Exponentiated Subgradient (NES) in Ader with Optimistic-GP and Optimistic-NES respectively, and name the corresponding algorithm ONES-OGP. We also extend the doubling trick to the adaptive trick, and introduce three characteristic terms naturally arise from optimism, namely $M_T$, $\widetilde{M}_T$ and $V_T+1_{L^2\rho\left(\rho+2 P_T\right)\leqslant\varrho^2 V_T}D_T$, to replace the dependence of the dynamic regret upper bound on $T$. We elaborate ONES-OGP with adaptive trick and its subgradient variation version, all of which are environment-adaptive. Comment: An early version of this manuscript can be found at https://openreview.net/forum?id=T3_cV3-zbg |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2203.14520 |
رقم الأكسشن: | edsarx.2203.14520 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |