論文の概要: Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures
- arxiv url: http://arxiv.org/abs/2401.02011v1
- Date: Thu, 4 Jan 2024 00:57:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-05 16:07:13.850796
- Title: Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures
- Title（参考訳）: ランダムリンク障害下における分散マルチタスクオンライン凸最適化
- Authors: Wenjing Yan and Xuanyu Cao
- Abstract要約: 我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
- 参考スコア（独自算出の注目度）: 5.513958040574729
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decentralized optimization methods often entail information exchange between
neighbors. Transmission failures can happen due to network congestion,
hardware/software issues, communication outage, and other factors. In this
paper, we investigate the random link failure problem in decentralized
multi-task online convex optimization, where agents have individual decisions
that are coupled with each other via pairwise constraints. Although widely used
in constrained optimization, conventional saddle-point algorithms are not
directly applicable here because of random packet dropping. To address this
issue, we develop a robust decentralized saddle-point algorithm against random
link failures with heterogeneous probabilities by replacing the missing
decisions of neighbors with their latest received values. Then, by judiciously
bounding the accumulated deviation stemming from this replacement, we first
establish that our algorithm achieves $\mathcal{O}(\sqrt{T})$ regret and
$\mathcal{O}(T^\frac{3}{4})$ constraint violations for the full information
scenario, where the complete information on the local cost function is revealed
to each agent at the end of each time slot. These two bounds match, in order
sense, the performance bounds of algorithms with perfect communications.
Further, we extend our algorithm and analysis to the two-point bandit feedback
scenario, where only the values of the local cost function at two random points
are disclosed to each agent sequentially. Performance bounds of the same orders
as the full information case are derived. Finally, we corroborate the efficacy
of the proposed algorithms and the analytical results through numerical
simulations.
- Abstract（参考訳）: 分散最適化手法は、しばしば隣人間の情報交換を伴う。
送信障害は、ネットワークの混雑、ハードウェア/ソフトウェアの問題、通信障害などによって起こりうる。
本稿では,分散マルチタスクオンライン凸最適化におけるランダムリンク障害問題について検討する。
制約付き最適化で広く使われているが、ランダムなパケットの落下のため、従来の鞍点アルゴリズムは直接適用できない。
この問題に対処するために、近隣住民の欠落した決定を最新の受信値に置き換えることにより、不均一な確率を持つランダムリンク障害に対する頑健な分散サドルポイントアルゴリズムを開発した。
そして,この代替から生じる累積偏差を任意に有界化することにより,各時間帯の最後に局所コスト関数の完全情報が各エージェントに明らかになるような全情報シナリオに対して,我々のアルゴリズムが $\mathcal{O}(\sqrt{T})$ regret および $\mathcal{O}(T^\frac{3}{4})$制約違反を達成できることを確認した。
これら2つの境界は、秩序ある意味では、完全な通信を持つアルゴリズムのパフォーマンス境界と一致する。
さらに,アルゴリズムと解析を2点の帯域フィードバックシナリオに拡張し,各エージェントに対して2つのランダムポイントにおける局所コスト関数の値のみを順次開示する。
フルインフォメーションケースと同じ順序のパフォーマンス境界が導出される。
最後に,提案アルゴリズムの有効性と数値シミュレーションによる解析結果について考察する。
関連論文リスト
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - Adversarially Robust Distributed Count Tracking via Partial Differential
Privacy [17.43748116766233]
分散機能監視(distributed functional monitoring)とも呼ばれる分散追跡モデルについて検討する。
このモデルは、各アイテムのストリームを受け取り、中央サーバと通信する、$k$のサイトを含む。
カウントトラッキングでは、決定論的アルゴリズムとランダム化アルゴリズムの通信に$sqrtk$ギャップがあることが知られている。
論文 参考訳（メタデータ） (2023-11-01T07:42:13Z) - Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。
この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。
本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-31T22:59:23Z) - Distributed Online Private Learning of Convex Nondecomposable Objectives [7.5585719185840485]
我々は、時間によって異なるネットワーク上でのプライバシーに関する一般的な分散制約付きオンライン学習問題に対処する。
本稿では, DPSDA-C と DPSDA-PS という2つのアルゴリズムを提案する。
理論的結果は、目的関数が凸であるときに、両方のアルゴリズムが $mathcalO( sqrtT )$ で期待される後悔の上限に達することを示している。
論文 参考訳（メタデータ） (2022-06-16T06:29:51Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。
T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
論文 参考訳（メタデータ） (2020-10-05T07:08:26Z) - A Multi-Agent Primal-Dual Strategy for Composite Optimization over
Distributed Features [52.856801164425086]
目的関数を滑らかな局所関数と凸(おそらく非滑らか)結合関数の和とするマルチエージェント共有最適化問題について検討する。
論文 参考訳（メタデータ） (2020-06-15T19:40:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。