首个无需参数的随机对抗优化算法，自动适应未知问题规模。
Parameter-free Algorithms for the Stochastically Extended Adversarial Model
- 用乐观牛顿步思想设计自适应算法，无需预知域直径和损失函数光滑性。
- 在未知参数下仍保持近似最优后悔界，依赖累积随机方差与对抗变化量。
- 适合实际应用中参数未知的在线优化场景，如自适应控制与强化学习。
我们提出了首个针对随机扩展对抗模型（SEA）的无参数算法，该框架连接了对抗性与随机性在线凸优化。现有方法需预先知道问题参数，如定义域直径 $D$ 和损失函数的 Lipschitz 常数 $G$，限制了实用性。本文通过引入乐观在线牛顿步（OONS）算法，构建无需这些参数的方法。首先，在域直径未知但 Lipschitz 常数已知时，提出一种比较器自适应算法，期望后悔界为 $ ilde{O}ig( orm{u}_2^2 + orm{u}_2( extstyle rac{1}{2} ext{σ}^2_{1:T} + extstyle rac{1}{2} Σ^2_{1:T})ig)$，其中 $u$ 为比较向量，$σ^2_{1:T}$ 与 $Σ^2_{1:T}$ 分别表示累计随机方差与累计对抗变化量。随后推广至 $D$ 与 $G$ 均未知的通用情形，获得比较器与 Lipschitz 自适应算法。值得注意的是，后悔界对 $σ^2_{1:T}$ 与 $Σ^2_{1:T}$ 的依赖形式一致，证明了所提方法在参数未知下的有效性。
原文摘要 · Abstract (English)
We develop the first parameter-free algorithms for the Stochastically Extended Adversarial (SEA) model, a framework that bridges adversarial and stochastic online convex optimization. Existing approaches for the SEA model require prior knowledge of problem-specific parameters, such as the diameter of the domain $D$ and the Lipschitz constant of the loss functions $G$, which limits their practical applicability. Addressing this, we develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters. We first establish a comparator-adaptive algorithm for the scenario with unknown domain diameter but known Lipschitz constant, achieving an expected regret bound of $\tilde{O}\big(\|u\|_2^2 + \|u\|_2(\sqrt{σ^2_{1:T}} + \sqrt{Σ^2_{1:T}})\big)$, where $u$ is the comparator vector and $σ^2_{1:T}$ and $Σ^2_{1:T}$ represent the cumulative stochastic variance and cumulative adversarial variation, respectively. We then extend this to the more general setting where both $D$ and $G$ are unknown, attaining the comparator- and Lipschitz-adaptive algorithm. Notably, the regret bound exhibits the same dependence on $σ^2_{1:T}$ and $Σ^2_{1:T}$, demonstrating the efficacy of our proposed methods even when both parameters are unknown in the SEA model.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。