提出无需预知总时长的在线优化算法,实时满足约束且性能最优。
Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints
- 用时变李雅普诺夫函数追踪约束违反,替代固定函数。
- 任意时刻t下,后悔值和约束违反均为O(√t)级别。
- 适合在线学习、动态优化等需实时决策的场景。
我们提出一种即刻可用的在线算法,用于在近似满足一系列对抗性凸约束的同时,学习一序列对抗性凸代价函数。所谓‘即刻可用’指算法在任意中间时间步t均能提供非平凡性能保证,且无需预先知晓总时长T。所提算法避免使用标准的加倍技巧(doubling trick),从而克服了因多次重启导致的实际性能差的问题。核心技术是引入时变李雅普诺夫函数以追踪约束违反情况,这与以往依赖已知时长T调参的固定李雅普诺夫函数形成对比。时变函数带来新的分析挑战,因以往证明所依赖的单调性等性质不再成立。通过新分析方法,我们证明该算法在任意t≥1时,可实现O(√t)的后悔界与~O(√t)的累积约束违反界。进一步将结果扩展至动态后悔设定,所得边界自适应于比较序列的路径长度,且无需事先知道总长度。还提出一种乐观设置下的自适应算法,其性能随累积预测误差平滑变化。通过在线最短路径问题的数值实验验证了算法的实际有效性。
原文摘要 · Abstract (English)
We propose an anytime online algorithm for the problem of learning a sequence of adversarial convex cost functions while approximately satisfying another sequence of adversarial online convex constraints. A sequential algorithm is called \emph{anytime} if it provides a non-trivial performance guarantee for any intermediate timestep $t$ without requiring prior knowledge of the length of the entire time horizon $T$. Our proposed algorithm achieves optimal performance bounds without resorting to the standard doubling trick, which has poor practical performance due to multiple restarts. Our core technical contribution is the use of time-varying Lyapunov functions to keep track of constraint violations. This must be contrasted with prior works that used a fixed Lyapunov function tuned to the known horizon length $T$. The use of time-varying Lyapunov function poses unique analytical challenges as properties, such as \emph{monotonicity}, on which the prior proofs rest, no longer hold. By introducing a new analytical technique, we show that our algorithm achieves $O(\sqrt{t})$ regret and $\tilde{O}(\sqrt{t})$ cumulative constraint violation bounds for any $t\geq 1$. We extend our results to the dynamic regret setting, achieving bounds that adapt to the path length of the comparator sequence without prior knowledge of its total length. We also present an adaptive algorithm in the optimistic setting, whose performance gracefully scales with the cumulative prediction error. We demonstrate the practical utility of our algorithm through numerical experiments involving the online shortest path problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。