論文の概要: Decentralized Online Exp-Concave Optimization

• arxiv url: http://arxiv.org/abs/2610.25017v1
• Date: Sun, 18 Oct 2026 04:56:53 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 22:28:43.580117
• Title: Decentralized Online Exp-Concave Optimization
• Title（参考訳）: 分散オンラインExp-Concave最適化
• Abstract要約: 分散オンラインニュートンステップ(D-ONS) D-ONSは、オンラインニュートンステップアルゴリズムを非自明な方法でブロックし、高速化するという考え方に適応する。 我々は、ほぼ一致する$left(Nd (1-_2)-1/2,log(T/N) right) の下位境界を確立する。
• 参考スコア（独自算出の注目度）: 28.177503685940334
• License:
• Abstract: Decentralized Online Convex Optimization (D-OCO) is a fundamental framework in which a set of local agents aims to minimize a sequence of global loss functions using only local computations and communications. While recent work has established near-optimal regret guarantees for convex and strongly convex losses, the case of exp-concave losses remains an open challenge: specifically, whether logarithmic regret is achievable. In this paper, we answer this question affirmatively by proposing Decentralized Online Newton Step (D-ONS), which adapts the idea of blocking and accelerated gossip to the Online Newton Step algorithm in a non-trivial manner. Concretely, our algorithm achieves a regret bound of $O\left(Nd(1-σ_2)^{-1/2}\,\log^2(T) \right)$ where $N$ is the number of agents, $d$ is the dimension, $T$ is the horizon, and $1-σ_2$ represents the spectral gap of the network. To our knowledge, this is the first logarithmic regret bound for decentralized online exp-concave optimization. We further establish a nearly matching lower bound of $Ω\left(Nd (1-σ_2)^{-1/2}\,\log(T/N) \right)$ showing the near optimality of our upper bound. Finally, we extend our algorithm to decentralized online linear regression in which the feasible domain is unbounded and features and labels are locally observed. By gossiping covariance and label-feature statistics, we also achieve logarithmic regret.
• Abstract（参考訳）: 分散オンライン凸最適化(Decentralized Online Convex Optimization, D-OCO)は、一組のローカルエージェントが、ローカル計算と通信のみを使用して、グローバルな損失関数の列を最小化することを目的とした基本的なフレームワークである。 最近の研究は、凸と強凸の損失に対するほぼ最適の後悔の保証を確立しているが、Exp-concaveの損失のケースはオープンな課題であり、特に対数的後悔が達成可能であるかどうかである。 本稿では,D-ONS(Decentralized Online Newton Step)を提案し,非自明な方法で,オンラインニュートンステップアルゴリズムに対するゴシップをブロック・高速化する手法を提案する。 具体的には、我々のアルゴリズムは、$O\left(Nd(1-σ_2)^{-1/2}\,\log^2(T) \right)$、$N$はエージェントの数、$d$はエージェントの次元、$T$は水平、$-σ_2$はネットワークのスペクトルギャップを表す。 我々の知る限り、これは分散化されたオンラインexp-concave最適化のための最初の対数的後悔である。 さらに、$Ω\left(Nd (1-σ_2)^{-1/2}\,\log(T/N) \right)$ のほぼ一致する下界を確立し、上界のほぼ最適性を示す。 最後に、本アルゴリズムを分散化オンライン線形回帰に拡張し、実現可能な領域が非有界であり、特徴とラベルを局所的に観察する。 共分散とラベル・フィーチャー統計をGossiping Covarianceと組み合わせることで、対数的後悔も達成できる。

関連論文リスト

• Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions [9.035866986287205]
  我々は、有界曲率上での強測地学的凸(強いg-)損失に対する新しいタイプのオンライン最適化を開発する。 境界損失関数のスムーズなバージョンを設定する2つの強点帯域幅フィードバック設定の最初の解析を証明した。
  論文  参考訳（メタデータ） (2026-07-22T16:03:43Z)
• 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)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees [23.256961881716595]
  エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。 分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
  論文  参考訳（メタデータ） (2022-01-21T01:26:08Z)
• GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning [11.129095449532283]
  近年,分散1/2非堅牢性最適化が注目されている。 分散最適化アルゴリズムの設計における3つの基本的な課題は、サンプルコスト、通信、メモリ複雑さの削減である。
  論文  参考訳（メタデータ） (2021-05-04T00:44:48Z)

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

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