論文の概要: Federated Online and Bandit Convex Optimization

• arxiv url: http://arxiv.org/abs/2311.17586v1
• Date: Wed, 29 Nov 2023 12:29:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-30 21:33:04.376434
• Title: Federated Online and Bandit Convex Optimization
• Title（参考訳）: Federated Online and Bandit Convex Optimization
• Authors: Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha, Nati Sebro
• Abstract要約: 適応的相手に対する分散オンラインおよび帯域幅凸最適化の問題点について検討する。 機械がクエリポイントの1階勾配情報にアクセスできる場合、協調は有益ではないことを示す。 私たちの研究は、限られたフィードバックでフェデレートされたオンライン最適化を体系的に理解するための最初の試みです。
• 参考スコア（独自算出の注目度）: 27.565740560571292
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problems of distributed online and bandit convex optimization against an adaptive adversary. We aim to minimize the average regret on $M$ machines working in parallel over $T$ rounds with $R$ intermittent communications. Assuming the underlying cost functions are convex and can be generated adaptively, our results show that collaboration is not beneficial when the machines have access to the first-order gradient information at the queried points. This is in contrast to the case for stochastic functions, where each machine samples the cost functions from a fixed distribution. Furthermore, we delve into the more challenging setting of federated online optimization with bandit (zeroth-order) feedback, where the machines can only access values of the cost functions at the queried points. The key finding here is identifying the high-dimensional regime where collaboration is beneficial and may even lead to a linear speedup in the number of machines. We further illustrate our findings through federated adversarial linear bandits by developing novel distributed single and two-point feedback algorithms. Our work is the first attempt towards a systematic understanding of federated online optimization with limited feedback, and it attains tight regret bounds in the intermittent communication setting for both first and zeroth-order feedback. Our results thus bridge the gap between stochastic and adaptive settings in federated online optimization.
• Abstract（参考訳）: 適応的相手に対する分散オンラインおよび帯域幅凸最適化の問題点について検討する。 我々は、$M$マシンにおける平均的後悔を、$T$ラウンドと$R$断続的な通信で並列に処理することを目指している。 コスト関数が凸であり、適応的に生成できると仮定すると、機械がクエリポイントの1次勾配情報にアクセスできた場合、協調は有益ではないことを示す。 これは、各マシンが固定分布からコスト関数をサンプリングする確率関数の場合とは対照的である。 さらに、我々は、機械がクエリポイントのコスト関数の値にしかアクセスできない、帯域幅(ゼロオーダー)フィードバックによるフェデレートされたオンライン最適化のより困難な設定について調べる。 ここでの鍵となる発見は、コラボレーションが有益であり、マシン数の線形スピードアップにつながるかもしれない高次元の体制を特定することである。 さらに,新たな分散単点フィードバックアルゴリズムと2点フィードバックアルゴリズムを開発した。 我々の研究は、限定的なフィードバックでフェデレートされたオンライン最適化を体系的に理解するための最初の試みであり、一階とゼロ階の両方のフィードバックに対する断続的なコミュニケーション設定において、厳密な後悔の限界に達する。 その結果,連合オンライン最適化における確率的設定と適応的設定のギャップを埋めることができた。

関連論文リスト

• Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization [8.670873561640903]
  分散環境下での非平滑な非平滑な目的に対する(delta,,ilon$)-定常点の有限時間解析について検討する。 $Oは分散非滑らかな最適化のための最初の有限時間保証である。
  論文  参考訳（メタデータ） (2024-06-03T16:09:34Z)
• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。 我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
  論文  参考訳（メタデータ） (2024-01-04T00:57:33Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。 本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
  論文  参考訳（メタデータ） (2023-12-19T01:52:13Z)
• Communication-Efficient Federated Non-Linear Bandit Optimization [26.23638987873429]
  汎用非線形目的関数を用いた連邦帯域最適化のための新しいアルゴリズムであるFed-GO-UCBを提案する。 いくつかの軽度の条件下では、Fed-GO-UCBが累積的後悔と通信コストの両方でサブ線形レートを達成できることを厳格に証明する。
  論文  参考訳（メタデータ） (2023-11-03T03:50:31Z)
• 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)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• $P^2$ Net: Augmented Parallel-Pyramid Net for Attention Guided Pose Estimation [69.25492391672064]
  拡張ボトルネックとアテンションモジュールによる特徴改善を施したパラレルピラミドネットを提案する。 並列ピラミド構造は、ネットワークによって導入された情報損失を補うために続く。 提案手法は, MSCOCO と MPII のデータセットにおいて, 最適な性能を実現する。
  論文  参考訳（メタデータ） (2020-10-26T02:10:12Z)

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

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