論文の概要: Optimal Regret for Communication-Efficient Decentralized Online Learning

• arxiv url: http://arxiv.org/abs/2610.38334v1
• Date: Wed, 28 Oct 2026 06:33:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.377868
• Title: Optimal Regret for Communication-Efficient Decentralized Online Learning
• Title（参考訳）: コミュニケーション効率の良い分散オンライン学習のための最適レグレット
• Abstract要約: 我々は,凸・凸損失関数に対して,$widetilde O(-1/2n-1/4sqrtT)$と$widetilde O(-1n-1/2ln T)$の最適後悔境界を実現するオンラインアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 39.626196251145736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $ρ\in(0,1)$ is the spectral gap of the communication matrix and $ω\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $ρ^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ for convex and strongly convex loss functions, respectively. Up to logarithmic factors in $n$ and $ρ^{-1}$, these results match the lower bounds in terms of $T$, $n$, $ρ$, and $ω$.
• Abstract（参考訳）: 本稿では,ネットワーク上の学習者に対して,ローカルな損失と近隣住民からのメッセージのみに基づいて,グローバルな損失関数の列を最小化する,圧縮通信を用いた分散オンライン凸最適化について検討する。 この問題に対する最もよく知られている後悔境界は、それぞれ凸函数と強い凸損失関数に対して$O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$と$O(ω^{-1}nρ^{-2}\ln n\ln T)$であり、$ρ\in(0,1)$は通信行列のスペクトルギャップであり、$ω\in(0,1]$は圧縮品質係数である。 対応する下界の$Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$と$Ω(ω^{-1}nρ^{-1/2}\ln T)$と比較すると、これらの上界は$ρ^{-1}$に依存する多項式ギャップを示す。 これらのギャップを埋めるために、我々はまず、オンライン圧縮戦略とチェビシェフ再帰を組み合わせたAscent-gossipを開発し、既存の圧縮ゴシップ法よりも高速なコンセンサス率を得る。 さらに, Ascent-gossip を用いて, 凸および凸損失関数に対して, $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ と $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ の最適後悔境界を達成するオンラインアルゴリズムを提案する。 対数係数が$n$と$ρ^{-1}$のとき、これらの結果は$T$、$n$、$ρ$、$ω$という条件で下界と一致する。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds [27.851263935083736]
  圧縮通信を用いた分散オンライン凸最適化について検討する。 本稿では,凸関数と強凸関数に対して,$tildeO(-1/2-1nsqrtT)$と$tildeO(-1-2nlnT)$の改善された後悔境界を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-01-08T13:05:36Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。