論文の概要: Lower Bounds for Time-Varying Kernelized Bandits

• arxiv url: http://arxiv.org/abs/2410.16692v1
• Date: Tue, 22 Oct 2024 04:45:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:29:40.366891
• Title: Lower Bounds for Time-Varying Kernelized Bandits
• Title（参考訳）: 時間変化型カーネル化バンドの低境界
• Authors: Xu Cai, Jonathan Scarlett,
• Abstract要約: ノイズの多い観測によるブラックボックス関数の最適化は、広く応用される基本的な問題である。 特定のアプリケーションに不可欠な非定常シナリオについて検討するが、現時点では十分に理解されていない。 $ell_infty$-norm変異の下では、我々の境界は最先端の上限に近いことが分かる。
• 参考スコア（独自算出の注目度）: 43.62161925881489
• License:
• Abstract: The optimization of black-box functions with noisy observations is a fundamental problem with widespread applications, and has been widely studied under the assumption that the function lies in a reproducing kernel Hilbert space (RKHS). This problem has been studied extensively in the stationary setting, and near-optimal regret bounds are known via developments in both upper and lower bounds. In this paper, we consider non-stationary scenarios, which are crucial for certain applications but are currently less well-understood. Specifically, we provide the first algorithm-independent lower bounds, where the time variations are subject satisfying a total variation budget according to some function norm. Under $\ell_{\infty}$-norm variations, our bounds are found to be close to the state-of-the-art upper bound (Hong \emph{et al.}, 2023). Under RKHS norm variations, the upper and lower bounds are still reasonably close but with more of a gap, raising the interesting open question of whether non-minor improvements in the upper bound are possible.
• Abstract（参考訳）: ノイズの多い観測を伴うブラックボックス関数の最適化は、広く応用される基本的な問題であり、この関数は再生カーネルヒルベルト空間(RKHS)にあるという仮定の下で広く研究されている。 この問題は定常条件下で広範囲に研究され、上界と下界の両方の発達を通じて、ほぼ最適の後悔境界が知られている。 本稿では,特定のアプリケーションに不可欠な非定常シナリオについて考察する。 具体的には、ある関数規範に従って、時間変動が全変動予算を満たすような、アルゴリズムに依存しない最初の下界を提供する。 $\ell_{\infty}$-normの変分の下で、我々の境界は最先端の上限に近い(Hong \emph{et al }, 2023)。 RKHSのノルム変動の下では、上界と下界はいまだに十分近いが、よりギャップがあるため、上界の非マイナーな改善が可能かどうかという興味深いオープンな疑問が提起される。

関連論文リスト

• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• Adaptation to Misspecified Kernel Regularity in Kernelised Bandits [27.912690223941386]
  翻訳不変核の正則性に対する適応性について検討する。 規則性が異なる一対のRKHSにおいて、最適な累積後悔を同時に達成することは不可能である。 連続武器付き帯域における適応性の統計的困難さを3つの基本型関数空間で結合する。
  論文  参考訳（メタデータ） (2023-04-26T21:12:45Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration [33.247600151322466]
  我々は、滑らかな凸関数の標準設定において、AdaGradとその変種についてより深く理解する。 まず、制約のない問題に対して、バニラ AdaGrad の収束率を明示的に拘束する新しい手法を示す。 第二に、平均的な反復ではなく、最後の反復の収束を示すことのできる AdaGrad の変種を提案する。
  論文  参考訳（メタデータ） (2022-09-29T14:44:40Z)
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective [49.17352150219212]
  Federated AveragingFedAvg(ローカルSGD)は、Federated Learning(FL)で最も人気のあるアルゴリズムの1つである。 微分方程式(SDE)の観点から、この量を解析する方法を示す。
  論文  参考訳（メタデータ） (2021-11-05T22:16:11Z)
• On Information Gain and Regret Bounds in Gaussian Process Bandits [8.499604625449907]
  ノイズフィードバックの観測から、高い評価と、おそらくは非シーケンシャルな目的関数$f$の最適化を考える。 カーネルのMatern族では、$gamma_T$の低い境界と、頻繁な設定での後悔が知られている。
  論文  参考訳（メタデータ） (2020-09-15T10:15:29Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Regret Bounds for Noise-Free Kernel-Based Bandits [4.924126492174802]
  カーネルベースバンディット(英: Kernel-based bandit)は、ブラックボックス最適化の問題である。 後悔に関するいくつかの上限について論じるが、いずれも最適に見えず、最適の後悔境界に関する予想を与える。
  論文  参考訳（メタデータ） (2020-02-12T17:06:14Z)

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

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