arXiv:2410.02476cs.LGmath.OC2024-10被引 6

新算法实现无投影在线凸优化,突破旧方法对病态集的性能瓶颈。

Online Convex Optimization with a Separation Oracle

  • 基于分离预言机设计无投影算法,每轮仅需常数次调用
  • 达到最优 $ ilde{O}( oot dT)$ 的损失界,与病态因子 $κ$ 无关
  • 适用于高维、病态可行域场景,适合追求高效在线学习的研究者

本文提出一种新型无投影在线凸优化(OCO)算法,其后悔界在基于分离预言机的方法中达到最优。现有基于Frank-Wolfe的无投影方法后悔界为 $O(T^{3/4})$,近期分离基方法可达到 $O(κ oot T)$,其中 $κ$ 为可行集的非球性(包含球与被含球半径比)。然而,对于病态集合,$κ$ 可任意大,导致性能下降。本文算法实现 $ ilde{O}( oot dT + κd)$ 后悔界,每轮仅需 $ ilde{O}(1)$ 次分离预言机调用。关键优势在于主项 $ ilde{O}( oot dT)$ 与 $κ$ 无关,克服了以往方法局限。此外,分析还简化并复现了 $O(κ oot T)$ 后悔界,改进了无投影在线指数凹优化的界限。针对受限随机凸优化,获得 $ ilde{O}(σ/ oot T + κd/T)$ 的收敛率,同样只需每迭代 $ ilde{O}(1)$ 次预言机调用。

原文摘要 · Abstract (English)

In this paper, we introduce a new projection-free algorithm for Online Convex Optimization (OCO) with a state-of-the-art regret guarantee among separation-based algorithms. Existing projection-free methods based on the classical Frank-Wolfe algorithm achieve a suboptimal regret bound of $O(T^{3/4})$, while more recent separation-based approaches guarantee a regret bound of $O(κ\sqrt{T})$, where $κ$ denotes the asphericity of the feasible set, defined as the ratio of the radii of the containing and contained balls. However, for ill-conditioned sets, $κ$ can be arbitrarily large, potentially leading to poor performance. Our algorithm achieves a regret bound of $\widetilde{O}(\sqrt{dT} + κd)$, while requiring only $\widetilde{O}(1)$ calls to a separation oracle per round. Crucially, the main term in the bound, $\widetilde{O}(\sqrt{d T})$, is independent of $κ$, addressing the limitations of previous methods. Additionally, as a by-product of our analysis, we recover the $O(κ\sqrt{T})$ regret bound of existing OCO algorithms with a more straightforward analysis and improve the regret bound for projection-free online exp-concave optimization. Finally, for constrained stochastic convex optimization, we achieve a state-of-the-art convergence rate of $\widetilde{O}(σ/\sqrt{T} + κd/T)$, where $σ$ represents the noise in the stochastic gradients, while requiring only $\widetilde{O}(1)$ calls to a separation oracle per iteration.

在线优化无投影分离预言机后悔界

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。