論文の概要: Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret

• arxiv url: http://arxiv.org/abs/2409.15680v1
• Date: Tue, 24 Sep 2024 02:37:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-26 11:19:39.656068
• Title: Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret
• Title（参考訳）: 動的レグレットによる一点残差フィードバックを用いた分散オンライン帯域非凸最適化
• Authors: Youqing Hua, Shuai Liu, Yiguang Hong, Karl Henrik Johansson, Guangchen Wang,
• Abstract要約: 本稿では,非損失関数を用いた分散オンライン帯域最適化問題について検討する。 プレイヤーは敵を選択し、そのプレイヤーに任意の非線形損失関数を割り当てる。 予想されるアルゴリズムの後悔は、2点偏差を用いた既存のアルゴリズムに匹敵する。
• 参考スコア（独自算出の注目度）: 10.700891331004799
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers the distributed online bandit optimization problem with nonconvex loss functions over a time-varying digraph. This problem can be viewed as a repeated game between a group of online players and an adversary. At each round, each player selects a decision from the constraint set, and then the adversary assigns an arbitrary, possibly nonconvex, loss function to this player. Only the loss value at the current round, rather than the entire loss function or any other information (e.g. gradient), is privately revealed to the player. Players aim to minimize a sequence of global loss functions, which are the sum of local losses. We observe that traditional multi-point bandit algorithms are unsuitable for online optimization, where the data for the loss function are not all a priori, while the one-point bandit algorithms suffer from poor regret guarantees. To address these issues, we propose a novel one-point residual feedback distributed online algorithm. This algorithm estimates the gradient using residuals from two points, effectively reducing the regret bound while maintaining $\mathcal{O}(1)$ sampling complexity per iteration. We employ a rigorous metric, dynamic regret, to evaluate the algorithm's performance. By appropriately selecting the step size and smoothing parameters, we demonstrate that the expected dynamic regret of our algorithm is comparable to existing algorithms that use two-point feedback, provided the deviation in the objective function sequence and the path length of the minimization grows sublinearly. Finally, we validate the effectiveness of the proposed algorithm through numerical simulations.
• Abstract（参考訳）: 本稿では,非凸損失関数を用いた分散オンライン帯域最適化問題について検討する。 この問題は、オンラインプレーヤーのグループと敵との繰り返しゲームと見なすことができる。 各ラウンドにおいて、各プレイヤーは制約セットから決定を選択し、敵は任意の非凸な損失関数をこのプレイヤーに割り当てる。 損失関数全体や他の情報(例えば勾配)ではなく、現在のラウンドでの損失値のみをプレイヤーにプライベートに開示する。 プレイヤーは、局所的な損失の和であるグローバルな損失関数の列を最小化することを目指している。 従来のマルチポイントバンディットアルゴリズムはオンライン最適化には適さないが、損失関数のデータはすべて先入観ではなく、一方、ワンポイントバンディットアルゴリズムは残念な保証に苦しむ。 これらの問題に対処するために,オンライン一点残差フィードバック分散アルゴリズムを提案する。 このアルゴリズムは、2つの点からの残差を用いて勾配を推定し、反復ごとに$\mathcal{O}(1)$のサンプリング複雑性を維持しながら、後悔の限界を効果的に低減する。 我々はアルゴリズムの性能を評価するために厳密な計量、動的後悔を用いる。 ステップサイズとスムーズなパラメータを適切に選択することにより、目的関数列のずれや最小化の経路長がサブリニアに増加することを条件として、2点フィードバックを用いた既存のアルゴリズムに匹敵する性能が期待できることを示す。 最後に,提案アルゴリズムの有効性を数値シミュレーションにより検証する。

関連論文リスト

• Second Order Methods for Bandit Optimization and Control [34.51425758864638]
  我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。 また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
  論文  参考訳（メタデータ） (2024-02-14T04:03:38Z)
• On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization [17.412117389855222]
  提案するアルゴリズムは,現在の動作の周囲に適度に選択された集合上の射影勾配勾配を追従する。 動的後悔と制約違反の両方が、連続する最適動作間の距離の和であるパス長によって順序的に束縛されていることを示す。
  論文  参考訳（メタデータ） (2023-01-24T04:22:13Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Persistent Reductions in Regularized Loss Minimization for Variable Selection [3.3504365823045035]
  広い種類の損失関数に対して、係数がゼロであることが保証される部分集合を効率的に同定できることが示される。 我々は、超高次元問題に適用できるように、既存のレイアルゴリズムを極端線識別に使用し、保証アルゴリズムを適用させる。
  論文  参考訳（メタデータ） (2020-11-30T04:59:44Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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