論文の概要: Sharper Guarantees for Misspecified Kernelized Bandit Optimization
- arxiv url: http://arxiv.org/abs/2605.05967v1
- Date: Thu, 07 May 2026 10:12:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-08 22:27:11.690583
- Title: Sharper Guarantees for Misspecified Kernelized Bandit Optimization
- Title（参考訳）: 並列化帯域最適化におけるシャーパー保証
- Authors: Davide Maran, Csaba Szepesvári,
- Abstract要約: 大規模なカーネルでは、不特定値の増幅は対数的あるいは多対数的成長に還元できることを示す。
オフライン設定では、不特定項がスペクトルルベーグ定数によって支配される高確率単純回帰境界を最初に証明する。
オンライン設定では、ドメイン分割アルゴリズムを変更して、緩やかな局所化された固有デカイ仮定の下で、$widetildemathcal O(sqrt_n n+nvarepsilon)$の累積後悔境界を証明する。
- 参考スコア（独自算出の注目度）: 34.863425530383545
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Existing guarantees for misspecified kernelized bandit optimization pay for misspecification through kernel complexity: in generic offline bounds, the misspecification level $\varepsilon$ is multiplied by $\sqrt{d_\mathrm{eff}}$, where $d_\mathrm{eff}$ is the kernel effective dimension, while in online regret bounds, the corresponding penalty is $\sqrt{γ_n}\,n\varepsilon$, where $γ_n$ is the maximum information gain after $n$ rounds of interaction. In this work, we show that, for a large class of kernels, the misspecification amplification can be reduced to logarithmic or polylogarithmic growth. In the offline setting, we first prove high-probability simple-regret bounds whose misspecification term is governed by a spectral Lebesgue constant. This yields logarithmic amplification for one-dimensional monotone spectra and polylogarithmic amplification for multivariate Fourier-diagonal product kernels. In the online setting, we modify a domain-splitting algorithm and prove a cumulative regret bound of $\widetilde{\mathcal O}(\sqrt{γ_n n}+n\varepsilon)$ under mild localized eigendecay assumptions, removing the extra $\sqrt{γ_n}$ factor from the misspecification term. The common principle is localization: spectral localization controls the Lebesgue constant of the offline approximation operator, while domain splitting implements the spatial analogue of this mechanism in the online setting, preventing local misspecification errors from being amplified globally.
- Abstract（参考訳）: 一般的なオフライン境界では、誤特定レベル$\varepsilon$は$\sqrt{d_\mathrm{eff}}$で乗算され、$d_\mathrm{eff}$はカーネル有効次元であり、オンラインの後悔境界では、対応するペナルティは$\sqrt{γ_n}\,n\varepsilon$である。
本研究は,大規模なカーネルに対して,不特定値の増幅を対数的あるいは多対数的成長に還元できることを示す。
オフライン設定では、不特定項がスペクトルルベーグ定数によって支配される高確率単純回帰境界を最初に証明する。
これにより、1次元単調スペクトルに対する対数増幅と多変量フーリエ対角積核に対する多対数増幅が得られる。
オンライン設定では、ドメイン分割アルゴリズムを変更し、$\widetilde{\mathcal O}(\sqrt{γ_n n}+n\varepsilon)$の累積後悔境界を証明する。
スペクトルローカライゼーションはオフライン近似演算子のルベーグ定数を制御するが、ドメイン分割は、このメカニズムの空間的類似をオンライン設定で実装し、局所的不特定誤差がグローバルに増幅されるのを防ぐ。
関連論文リスト
- Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy [13.264499801590583]
mathbbRn 倍 n$ の対称行列 $A と任意の対称摂動 E$ に対して、新しい高確率スペクトル-ノルム摂動境界を導入する。
穏やかな固有ギャップとノルム条件の下では、我々の境界は$|(A + E)_p - A_p|$に対して鋭い推定値を得るが、最大で$sqrtn$となる。
応用として,PCAの実用性保証の改善を導出し,文献の未解決問題を解消する。
論文 参考訳（メタデータ） (2025-10-29T16:36:00Z) - Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
コンテキストによるカーネルの帯域幅の問題について考察する。
基礎となる報酬関数は、既知の再生ケルネルヒルベルト空間に属する。
我々は、$widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)の最先端の累積後悔を実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-18T03:54:49Z) - Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [21.64772960240025]
問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。
私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
論文 参考訳（メタデータ） (2024-08-20T01:24:54Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。
本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
論文 参考訳（メタデータ） (2023-10-02T19:59:39Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。