論文の概要: Algorithmic and Minimax Complexities in Kernel Bandits

• arxiv url: http://arxiv.org/abs/2606.11171v1
• Date: Tue, 09 Jun 2026 17:49:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-10 15:40:58.657432
• Title: Algorithmic and Minimax Complexities in Kernel Bandits
• Title（参考訳）: カーネル帯域におけるアルゴリズムとミニマックス複雑性
• Authors: Yunbei Xu,
• Abstract要約: ガウス過程上信頼境界(GP-UCB)と決定推定係数法(DEC)は異なる理論に属すると考えられる。 本稿では、この2つの視点を、頻繁なRKHS盗賊のための共通アルゴリズム情報言語に配置する。
• 参考スコア（独自算出の注目度）: 5.082462420126421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gaussian-process upper confidence bound (GP-UCB) and decision-estimation-coefficient (DEC) methods may appear, at first sight, to belong to different theories. This paper places the two viewpoints in a common algorithmic-information language for frequentist RKHS bandits. GP-UCB fixes an algorithmic, rather than true, Gaussian-process prior and exploits realized-trajectory complexity together with computational tractability, whereas MAMS optimizes a robust class-wide MAIR/DEC envelope. Through the unified MAIR framework and heterogeneous positive-semidefinite algorithmic priors, we generalize both the GP-UCB analysis and the MAMS algorithm, propose a safeguarded master that combines their advantages, and provide a kernel-bandit construction showing that algorithmic complexity can be more informative than class-wide minimax or DEC certificates in overparameterized models. The resulting message is that algorithmic information and class-wide minimax coefficients answer different questions and can lead to different gaps; kernel bandits provide a clean setting in which this distinction becomes mathematically visible.
• Abstract（参考訳）: ガウス過程上信頼境界(GP-UCB)と決定推定係数法(DEC)は、一見すると、異なる理論に属する可能性がある。 本稿では、この2つの視点を、頻繁なRKHS盗賊のための共通アルゴリズム情報言語に配置する。 GP-UCBは、真ではなくアルゴリズムによってガウス過程を修正し、計算的トラクタビリティとともに実現された軌道の複雑さを利用する一方、MAMSは堅牢なクラスワイドMAIR/DECエンベロープを最適化する。 GP-UCB解析とMAMSアルゴリズムの両方を一般化し、それらの利点を組み合わせた安全マスターを提案し、アルゴリズムの複雑さがオーバーパラメータ化モデルにおけるクラスワイドのミニマックスやDEC証明書よりも有益であることを示す。 結果として得られたメッセージは、アルゴリズム情報とクラス全体のミニマックス係数が異なる質問に答え、異なるギャップにつながる可能性があるということである。

関連論文リスト

• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  本研究は,情報指向サンプリング(IDS)の原理に基づくマルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。 エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。 我々は、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明する。
  論文  参考訳（メタデータ） (2024-04-30T06:48:56Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Clustering with minimum spanning trees: How good can it be? [0.6883078440438425]
  低次元分割データクラスタリングタスクにおいて、最小分散木が意味のある範囲を定量化する。 我々は、既存の最先端のMSTベースの分割スキームをレビューし、研究し、拡張し、一般化する。 全体として、Genieと情報理論の手法は、MST以外のアルゴリズムよりも優れていることが多い。
  論文  参考訳（メタデータ） (2023-03-10T03:18:03Z)
• Regularization and Optimization in Model-Based Clustering [4.096453902709292]
  k-平均アルゴリズムの変種は、本質的に同じ球面ガウスの混合と、そのような分布から大きく逸脱するデータに適合する。 一般のGMMに対してより効率的な最適化アルゴリズムを開発し、これらのアルゴリズムと正規化戦略を組み合わせ、過度な適合を避ける。 これらの結果から, GMM と k-means 法の間の現状に新たな光を当て, 一般 GMM をデータ探索に利用することが示唆された。
  論文  参考訳（メタデータ） (2023-02-05T18:22:29Z)
• Multivariate Systemic Risk Measures and Computation by Deep Learning Algorithms [63.03966552670014]
  本稿では,主観的最適度と関連するリスク割り当ての公平性に着目し,重要な理論的側面について論じる。 私たちが提供しているアルゴリズムは、予備項の学習、二重表現の最適化、およびそれに対応する公正なリスク割り当てを可能にします。
  論文  参考訳（メタデータ） (2023-02-02T22:16:49Z)
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems [2.335152769484957]
  我々は、勾配近似(PG)アプローチに基づく効率的なコンセンサスアルゴリズムの理論解析を導出し、詳述する。 提案アルゴリズムは、異常検出タスクに対する別の特別な畳み込み問題にも適用できる。
  論文  参考訳（メタデータ） (2020-11-19T20:52:48Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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