提出新算法解决随时间收缩的优化问题,兼顾低损失与移动代价。
Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
- 分离损失控制与移动路径,用可重置的凸体追逐策略限制移动。
- 在二维情况下,任何随机算法的移动量至少为Ω(√log T),证明了最优时序依赖性。
- 适用于在线优化中约束集不断变化的场景,尤其适合强凸目标和线性增长情况。
我们研究两种设定下的在线优化问题:带有嵌套演变可行集的凸优化(CONES)和对抗性约束在线凸优化(COCO)。算法将损失控制与几何移动分离:约束极小值点和累积损失测试保持遗憾保证,而确定性可重置的嵌套凸体追逐器限制移动。对于在直径为D的域上具有G-利普希茨、μ-强凸目标函数的CONES,通过追踪当前可行集与自适应目标子水平集的交集实现优化。利用欧氏追逐比O(√(d log(1+d))),获得每个前缀的非正遗憾,移动代价为O(√(d log(1+d) GD log(eT)/μ)),该界可适应约束最优值的增长。在二维情况下,当其他参数固定时,所有终端期望遗憾为O(T^β)(β<1)的随机算法,在某些确定性嵌套序列上必有Ω(√log T)的期望移动量,证明了最优时序依赖性。在远离约束极小值集时呈线性增长的情况下,施泰纳点追踪可实现与T无关的移动量。对于一般凸的COCO,采用带正则化领导者重置的一步延迟追逐,可得遗憾为O(G_f D √(d log(1+d) T)),累计约束违反为O(G_g D √(d log(1+d) T));对于强凸损失,两者均为O(d log(1+d) log(eT))(其他参数固定)。这些简化将先前分析中的指数维度因子O(d^{d/2})替换为多项式维度依赖的欧氏嵌套凸体追逐。
原文摘要 · Abstract (English)
We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained online convex optimization (COCO). Our algorithms separate loss control from geometric movement: constrained minimizers and cumulative-loss tests preserve regret guarantees, while a deterministic resettable nested convex-body chaser limits movement. For CONES with a $G$-Lipschitz, $μ$-strongly convex objective on a diameter-$D$ domain, we chase intersections of the current feasible set with adaptive objective sublevel sets. Using the Euclidean chasing ratio $O(\sqrt{d\log(1+d)})$, we obtain nonpositive regret at every prefix and movement $O(\sqrt{d\log(1+d)\,GD\log(eT)/μ})$. The bound adapts to the increase in the constrained optimum value. In dimension two, with all other parameters fixed, every randomized algorithm with terminal expected regret $O(T^β)$, $β<1$, suffers $Ω(\sqrt{\log T})$ expected movement on some deterministic nested sequence, proving optimal horizon dependence. Under linear growth away from the constrained minimizer set, Steiner-point tracking yields movement independent of $T$. For general convex COCO, one-step-delayed chasing with regularized-leader resets gives regret $O(G_fD\sqrt{d\log(1+d)T})$ and cumulative constraint violation $O(G_gD\sqrt{d\log(1+d)T})$. For strongly convex losses, both are $O(d\log(1+d)\log(eT))$ when other parameters are fixed. These reductions replace the $O(d^{d/2})$ projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。