論文の概要: Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications

• arxiv url: http://arxiv.org/abs/2604.09276v1
• Date: Fri, 10 Apr 2026 12:43:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-13 17:57:53.857823
• Title: Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications
• Title（参考訳）: 圧縮通信を用いた分散オンライン凸最適化:最適レグレットとその応用
• Authors: Sifan Yang, Dan-Yue Li, Lijun Zhang,
• Abstract要約: 分散オンライン凸最適化(D-OCO)は、分散シナリオをストリーミングデータでモデル化するための強力なパラダイムである。 圧縮の影響を定量化し,凸・凸損失関数の最適アルゴリズムを提案する。 提案手法は汎用性が高く,オンライン・バッチ変換によるオフライン設定にも拡張可能である。
• 参考スコア（独自算出の注目度）: 17.50108222016455
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributed online convex optimization (D-OCO) is a powerful paradigm for modeling distributed scenarios with streaming data. However, the communication cost between local learners and the central server is substantial in large-scale applications. To alleviate this bottleneck, we initiate the study of D-OCO with compressed communication. Firstly, to quantify the compression impact, we establish the $Ω(δ^{-1/2}\sqrt{T})$ and $Ω(δ^{-1}\log{T})$ lower bounds for convex and strongly convex loss functions, respectively, where $δ\in (0,1]$ is the compression ratio. Secondly, we propose an optimal algorithm, which enjoys regret bounds of $O(δ^{-1/2}\sqrt{T})$ and $O(δ^{-1} \log T)$ for convex and strongly convex loss functions, respectively. Our method incorporates the error feedback mechanism into the Follow-the-Regularized-Leader framework to address the coupling between the compression error and the projection error. Furthermore, we employ the online compression strategy to mitigate the accumulated error arising from the bidirectional compression. Our online method has great generality, and can be extended to the offline stochastic setting via online-to-batch conversion. We establish convergence rates of $O(δ^{-1/2}T^{-1/2})$ and $O(δ^{-1} T^{-1})$ for convex and strongly convex loss functions, respectively, providing the first guarantees for distributed non-smooth optimization with compressed communication and domain constraints.
• Abstract（参考訳）: 分散オンライン凸最適化(D-OCO)は、分散シナリオをストリーミングデータでモデル化するための強力なパラダイムである。 しかし、大規模アプリケーションでは、ローカル学習者と中央サーバとの間の通信コストがかなり高い。 このボトルネックを軽減するため、圧縮通信を用いたD-OCOの研究に着手する。 まず、圧縮影響を定量化するために、それぞれ凸函数と強凸損失関数の下位境界として$Ω(δ^{-1/2}\sqrt{T})$と$Ω(δ^{-1}\log{T})$を定め、ここでは$δ\in (0,1]$を圧縮比とする。 次に,凸関数と凸損失関数に対してそれぞれ$O(δ^{-1/2}\sqrt{T})$と$O(δ^{-1} \log T)$の残差を満足する最適アルゴリズムを提案する。 提案手法では,圧縮誤差と投影誤差の結合に対処するため,エラーフィードバック機構をFollow-the-Regularized-Leaderフレームワークに組み込む。 さらに、オンライン圧縮戦略を用いて、双方向圧縮による累積誤差を軽減する。 我々のオンライン手法は非常に汎用的であり、オンラインからバッチへの変換によってオフラインの確率設定に拡張できる。 我々はそれぞれ凸関数と強い凸損失関数に対して$O(δ^{-1/2}T^{-1/2})$と$O(δ^{-1}T^{-1})$の収束率を確立し、圧縮された通信とドメイン制約による分散非滑らかな最適化の最初の保証を提供する。

関連論文リスト

• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  プッシュベースの分散通信は、情報交換が非対称である可能性のある通信ネットワークの最適化を可能にする。 我々は、グラディエント・プッシュ(SGP)アルゴリズムのための統一的な一様安定性フレームワークを開発する。 重要な技術的要素は、2つの量に束縛された不均衡認識の一般化である。
  論文  参考訳（メタデータ） (2026-02-24T05:32:03Z)
• 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)
• Distribution-Aware Tensor Decomposition for Compression of Convolutional Neural Networks [4.322339935902436]
  テンソル化と低ランク表現による圧縮に焦点を当てる。 関数空間の誤差を測定するために、データインフォームドノルムを使用します。 従来の圧縮パイプラインとは異なり、データインフォームドアプローチは微調整なしで競争精度を達成できることが多い。
  論文  参考訳（メタデータ） (2025-11-06T16:15:15Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• 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)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
  圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。 原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。 underline Decentralized with compression, LEAD。
  論文  参考訳（メタデータ） (2020-07-01T04:35:00Z)

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

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