在时变损失函数下的嵌套演化可行集凸优化（CONES）

arXiv cs.LG 论文
convex-optimization online-algorithms regret-minimization nested-feasible-sets time-varying-loss proximal-algorithm

摘要

本文将CONES扩展到时变损失函数，展示了在凸优化中使用投影近端算法时遗憾和移动成本的界限。

arXiv:2609.11207v1 公告类型：新 摘要：嵌套演化可行集凸优化（CONES）在\cite{CONESVaze}中被引入，其中目标函数 \(f\) 保持不变，但可行区域随时间演化为嵌套序列 \(S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T\). 在线算法的目标是最小化相对于事后静态最优基准的遗憾和总移动成本 $M_\cA(T)$，同时确保始终可行。CONES 是对著名的 \emph{嵌套凸体追逐}（NCBC）的优化导向推广。在本文中，我们将 CONES 扩展以允许损失函数 $f_t'$s 也随时间变化。当所有损失函数都是凸的，我们展示投影近端算法在时间范围 $T$ 内，对于任意 \(\beta \in [0,1)\)，分别实现 $O(T^{1-\beta})$ 的遗憾和 $O(T^\beta)$ 的移动成本。我们还展示任何具有 $O(T^\beta)$ 遗憾的 {\it 弱自适应} 在线算法，其移动成本为 $\Omega\left(T^{\frac{1-\beta}{2}}\right)$，对于任意 \(\beta \in [0,1)\)。当所有损失函数都是强凸的，我们展示投影近端算法同时实现 $O(1)$ 的遗憾和 $O(\log T)$ 的移动成本。为此补充，我们展示任何具有亚线性 {\it 任意时} 遗憾的在线算法，其移动成本为 $\Omega\left(\log T\right)$。
查看原文
查看缓存全文

缓存时间: 2026/09/11 08:32 

# 时变损失函数下的嵌套演化可行集凸优化（CONES）
来源：https://arxiv.org/abs/2609.11207
查看PDF（https://arxiv.org/pdf/2609.11207）HTML（实验性）（https://arxiv.org/html/2609.11207v1）

> 摘要：嵌套演化可行集凸优化（CONES）由 \\cite{CONESVaze} 提出，其中目标函数 \\(f\\) 保持固定，但可行区域随时间以嵌套序列 \\(S_1 \\supseteq S_2 \\supseteq \\cdots \\supseteq S_T\\) 演化。在线算法的目标是同时最小化相对于后见静态最优基准的遗憾，并控制总移动成本 $M_\\mathcal{A}(T)$，同时确保所有时刻的可行性。CONES 是著名的 *嵌套凸体追逐*（NCBC）在优化方向上的推广。本文中，我们将 CONES 扩展为允许损失函数 $f_t$ 也随时间变化。当所有损失函数均为凸函数时，我们证明投影近端算法能在时间范围 $T$ 内，对任意 $\\beta \\in [0,1)$，分别实现 $O(T^{1-\\beta})$ 的遗憾和 $O(T^\\beta)$ 的同时移动成本。我们还证明，任何具有 $O(T^\\beta)$ 遗憾的*弱自适应*在线算法，其移动成本为 $\\Omega\\left(T^{\\frac{1-\\beta}{2}}\\right)$（对任意 $\\beta \\in [0,1)$）。当所有损失函数为强凸时，我们证明投影近端算法同时实现了 $O(1)$ 的遗憾和 $O(\\log T)$ 的移动成本。为补充此结论，我们证明任何具有亚线性*随时*遗憾的在线算法，其移动成本为 $\\Omega\\left(\\log T\\right)$。

## 投稿历史

来自：Rahul Vaze \[[查看邮件 (https://arxiv.org/show-email/db8087f8/2609.11207)\] **\[v1\]**2026年9月10日 星期四 08:13:27 UTC（22 KB）

相似文章

在线局部化共形预测

arXiv cs.LG

本文提出了在线局部化共形预测（OLCP），旨在解决在线学习和时间序列设置中的协变量异质性问题。文章引入了用于带宽选择的 OLCP-Hedge 算法，并证明与现有基线相比，该方法在获得更窄预测集的同时，仍能保持有效的长期覆盖率。