論文の概要: Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds

• arxiv url: http://arxiv.org/abs/2601.04907v1
• Date: Thu, 08 Jan 2026 13:05:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-09 17:01:53.209579
• Title: Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds
• Title（参考訳）: 効率的な通信による分散オンライン凸最適化:改良されたアルゴリズムと下界
• Authors: Sifan Yang, Wenhao Yang, Wei Jiang, Lijun Zhang,
• Abstract要約: 圧縮通信を用いた分散オンライン凸最適化について検討する。 本稿では,凸関数と強凸関数に対して,$tildeO(-1/2-1nsqrtT)$と$tildeO(-1-2nlnT)$の改善された後悔境界を実現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 27.851263935083736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate distributed online convex optimization with compressed communication, where $n$ learners connected by a network collaboratively minimize a sequence of global loss functions using only local information and compressed data from neighbors. Prior work has established regret bounds of $O(\max\{ω^{-2}ρ^{-4}n^{1/2},ω^{-4}ρ^{-8}\}n\sqrt{T})$ and $O(\max\{ω^{-2}ρ^{-4}n^{1/2},ω^{-4}ρ^{-8}\}n\ln{T})$ for convex and strongly convex functions, respectively, where $ω\in(0,1]$ is the compression quality factor ($ω=1$ means no compression) and $ρ<1$ is the spectral gap of the communication matrix. However, these regret bounds suffer from a \emph{quadratic} or even \emph{quartic} dependence on $ω^{-1}$. Moreover, the \emph{super-linear} dependence on $n$ is also undesirable. To overcome these limitations, we propose a novel algorithm that achieves improved regret bounds of $\tilde{O}(ω^{-1/2}ρ^{-1}n\sqrt{T})$ and $\tilde{O}(ω^{-1}ρ^{-2}n\ln{T})$ for convex and strongly convex functions, respectively. The primary idea is to design a \emph{two-level blocking update framework} incorporating two novel ingredients: an online gossip strategy and an error compensation scheme, which collaborate to \emph{achieve a better consensus} among learners. Furthermore, we establish the first lower bounds for this problem, justifying the optimality of our results with respect to both $ω$ and $T$. Additionally, we consider the bandit feedback scenario, and extend our method with the classic gradient estimators to enhance existing regret bounds.
• Abstract（参考訳）: ネットワークで接続された$n$の学習者は、ローカル情報と近隣住民からの圧縮データのみを用いて、グローバルな損失関数列を協調的に最小化する。 O(\max\{ω^{-2}ρ^{-4}n^{1/2},ω^{-4}ρ^{-8}\}n\sqrt{T})$ and $O(\max\{ω^{-2}ρ^{-4}n^{1/2},ω^{-4}ρ^{-8}\}n\ln{T})$ for convex and strong convex function, where $ω\in(0,1]$ is the compression quality factor$ω=1$ means compression) and $ρ<1$ is the gap of the communication matrix。 しかし、これらの後悔境界は、$ω^{-1}$に対する \emph{quadratic} あるいは \emph{quartic} の依存に悩まされる。 さらに、$n$に対する \emph{super-linear} の依存も望ましくない。 これらの制限を克服するために、凸関数と強凸関数のそれぞれに対して、$\tilde{O}(ω^{-1/2}ρ^{-1}n\sqrt{T})$と$\tilde{O}(ω^{-1}ρ^{-2}n\ln{T})$の改善された後悔境界を達成する新しいアルゴリズムを提案する。 第一の考え方は、オンラインゴシップ戦略とエラー補償スキームという2つの新しい要素を取り入れた「emph{two-level blocking update framework」を設計することである。 さらに、この問題に対する最初の下界を確立し、$ω$と$T$の両方に関して結果の最適性を正当化する。 さらに,バンディットフィードバックのシナリオを考察し,従来の勾配推定器を用いて提案手法を拡張し,既存の残差を増大させる。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
  ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。 逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。 設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
  論文  参考訳（メタデータ） (2024-06-10T17:44:11Z)
• 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)
• Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds [26.277745106128197]
  本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。 我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。 我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
  論文  参考訳（メタデータ） (2023-06-12T02:56:09Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)

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

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