Fugu-MT 論文翻訳(概要): Parameter-free Algorithms for the Stochastically Extended Adversarial Model

論文の概要: Parameter-free Algorithms for the Stochastically Extended Adversarial Model

arxiv url: http://arxiv.org/abs/2510.04685v1
Date: Mon, 06 Oct 2025 10:53:37 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-07 16:52:59.81059
Title: Parameter-free Algorithms for the Stochastically Extended Adversarial Model
Title（参考訳）: 確率拡張逆数モデルに対するパラメータフリーアルゴリズム
Authors: Shuche Wang, Adarsh Barik, Peng Zhao, Vincent Y. F. Tan,
Abstract要約: 拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
参考スコア（独自算出の注目度）: 59.81852138768642
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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{\sigma^2_{1:T}} + \sqrt{\Sigma^2_{1:T}})\big)$, where $u$ is the comparator vector and $\sigma^2_{1:T}$ and $\Sigma^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 $\sigma^2_{1:T}$ and $\Sigma^2_{1:T}$, demonstrating the efficacy of our proposed methods even when both parameters are unknown in the SEA model.
Abstract（参考訳）: 本研究では, 確率的オンライン凸最適化を橋渡しするフレームワークであるStochastically Extended Adversarial (SEA) モデルのための最初のパラメータフリーアルゴリズムを開発する。既存のSEAモデルのアプローチでは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識が必要である。そこで我々は,パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。まず、未知のドメイン直径を持つシナリオに対するコンパレータ適応アルゴリズムを確立するが、リプシッツ定数である$\tilde{O}\big(\|u\|_2^2 + \|u\|_2(\sqrt{\sigma^2_{1:T}})\big)$, $u$はコンパレータベクトル、$\sigma^2_{1:T}$と$\Sigma^2_{1:T}$はそれぞれ累積確率分散と累積逆変分を表す。次にこれをより一般的な設定に拡張し、$D$と$G$の両方が未知となり、コンパレータとリプシッツ適応アルゴリズムが成立する。特に、後悔境界は$\sigma^2_{1:T}$と$\Sigma^2_{1:T}$に同じ依存を示し、SEAモデルで両方のパラメータが未知であっても提案手法の有効性を示す。

論文の概要: Parameter-free Algorithms for the Stochastically Extended Adversarial Model

関連論文リスト