論文の概要: Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach

• arxiv url: http://arxiv.org/abs/2402.02114v1
• Date: Sat, 3 Feb 2024 10:43:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-06 22:03:50.842726
• Title: Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach
• Title（参考訳）: 分散オンライン最適化における遅延フィードバック処理 : プロジェクションフリーアプローチ
• Authors: Tuan-Anh Nguyen, Nguyen Kim Thang, Denis Trystram
• Abstract要約: 大量のデータが局所的に連続的に生成されるように、エッジでの学習はますます重要になっている。 本稿では,B が遅延の和である O(sqrtB) の後悔境界を達成するために慎重に設計された,集中的および分散的設定のための2つのプロジェクションフリーアルゴリズムを提案する。 本研究では,実世界の問題において,既存の問題と比較することにより,アルゴリズムの性能を実験的に検証する。
• 参考スコア（独自算出の注目度）: 1.9797215742507548
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning at the edges has become increasingly important as large quantities of data are continually generated locally. Among others, this paradigm requires algorithms that are simple (so that they can be executed by local devices), robust (again uncertainty as data are continually generated), and reliable in a distributed manner under network issues, especially delays. In this study, we investigate the problem of online convex optimization under adversarial delayed feedback. We propose two projection-free algorithms for centralised and distributed settings in which they are carefully designed to achieve a regret bound of O(\sqrt{B}) where B is the sum of delay, which is optimal for the OCO problem in the delay setting while still being projection-free. We provide an extensive theoretical study and experimentally validate the performance of our algorithms by comparing them with existing ones on real-world problems.
• Abstract（参考訳）: 大量のデータがローカルに継続的に生成されるため、エッジでの学習はますます重要になっている。 このパラダイムでは、単純なアルゴリズム(ローカルデバイスで実行できるように)、堅牢な(データが継続的に生成されるような不確実性)、ネットワーク問題、特に遅延の下で分散的な方法で信頼性を必要とする。 本研究では,逆の遅延フィードバックによるオンライン凸最適化の問題について検討する。 そこで我々は,B が遅延の和である O(\sqrt{B}) の後悔境界を達成するために慎重に設計された,集中型および分散型設定のための2つのプロジェクションフリーアルゴリズムを提案し,これはまだプロジェクションフリーでありながら,遅延設定における OCO 問題に最適である。 我々は,実世界の問題に対して既存のアルゴリズムと比較し,アルゴリズムの性能を実験的に検証した。

関連論文リスト

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks [8.860889476382594]
  時間変化ネットワークによる分散最適化は、機械学習の新たなパラダイムである。 大規模な深層トレーニングでは通信オーバーヘッドが大幅に削減され、特にノードの移動時の無線シナリオでは堅牢になる。
  論文  参考訳（メタデータ） (2022-11-01T15:37:54Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Revisiting State Augmentation methods for Reinforcement Learning with Stochastic Delays [10.484851004093919]
  本稿では,遅延を伴うマルコフ決定過程(MDP)の概念を正式に述べる。 遅延MDPは、コスト構造が大幅に単純化された(遅延なしで)等価な標準MDPに変換可能であることを示す。 この等価性を利用して、モデルフリーな遅延分解RLフレームワークを導出し、このフレームワーク上に構築された単純なRLアルゴリズムでさえ、動作や観測の遅延を伴う環境におけるほぼ最適報酬を達成することを示す。
  論文  参考訳（メタデータ） (2021-08-17T10:45:55Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach [6.187780920448871]
  非同期アルゴリズムを解析するための新しい連続時間フレームワークを提案する。 我々は,スムーズな凸関数と強い凸関数の和を最小化するために,完全に非同期な分散アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-06-07T13:09:25Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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