仅用一次梯度评估，实现带切换成本的在线优化最优竞争比。
Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation
- 每次只用前一步的单次函数值和梯度信息进行决策。
- 线性切换成本下达到最优阶的竞争比，噪声下竞争比随噪声平方增长。
- 适合资源受限场景，如边缘计算或实时控制中的在线学习。
在资源受限的信息设置下研究带切换成本的在线凸优化问题：在时间t，行动x_t执行前，仅能获得上一时刻动作x_{t-1}处的单次函数值和单个梯度，且该信息来自当前代价函数f_t或最近的f_{t-1}。当切换成本为线性时，设计出在资源受限条件下具有最优阶竞争比的在线算法。当梯度信息存在噪声时，提出一个竞争比随噪声幅值平方增长的在线算法。
原文摘要 · Abstract (English)
Online convex optimization with switching cost is considered under the frugal information setting where at time $t$, before action $x_t$ is taken, only a single function evaluation and a single gradient is available at the previously chosen action $x_{t-1}$ for either the current cost function $f_t$ or the most recent cost function $f_{t-1}$. When the switching cost is linear, online algorithms with optimal order-wise competitive ratios are derived for the frugal setting. When the gradient information is noisy, an online algorithm whose competitive ratio grows quadratically with the noise magnitude is derived.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。