論文の概要: Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature
- arxiv url: http://arxiv.org/abs/2202.10615v1
- Date: Tue, 22 Feb 2022 01:49:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 15:38:22.688998
- Title: Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature
- Title（参考訳）: ノイズカーネルに基づくベイズ二次数の順序最適誤差境界
- Authors: Xu Cai, Chi Thanh Lam, and Jonathan Scarlett
- Abstract要約: 我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。
ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
- 参考スコア（独自算出の注目度）: 42.129843613950285
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the sample complexity of {\em noisy Bayesian
quadrature} (BQ), in which we seek to approximate an integral based on noisy
black-box queries to the underlying function. We consider functions in a {\em
Reproducing Kernel Hilbert Space} (RKHS) with the Mat\'ern-$\nu$ kernel,
focusing on combinations of the parameter $\nu$ and dimension $d$ such that the
RKHS is equivalent to a Sobolev class. In this setting, we provide
near-matching upper and lower bounds on the best possible average error.
Specifically, we find that when the black-box queries are subject to Gaussian
noise having variance $\sigma^2$, any algorithm making at most $T$ queries
(even with adaptive sampling) must incur a mean absolute error of
$\Omega(T^{-\frac{\nu}{d}-1} + \sigma T^{-\frac{1}{2}})$, and there exists a
non-adaptive algorithm attaining an error of at most $O(T^{-\frac{\nu}{d}-1} +
\sigma T^{-\frac{1}{2}})$. Hence, the bounds are order-optimal, and establish
that there is no adaptivity gap in terms of scaling laws.
- Abstract（参考訳）: 本稿では,ノイズの大きいベイズ二次関数(bq)のサンプル複雑性について検討し,ノイズの多いブラックボックスクエリに基づく積分を基礎関数に近似する。
我々は、RKHS がソボレフ類と同値であるようなパラメータ $\nu$ と dimension $d$ の組み合わせに焦点を当て、Mat\'ern-$\nu$ カーネルを持つ {\displaystyle {\em Reproduction Kernel Hilbert Space} (RKHS) 内の函数を考える。
この設定では、最良平均誤差に対して、ほぼ一致する上限と下限を提供する。
具体的には、ブラックボックスのクエリが分散$\sigma^2$を持つガウスノイズの対象となる場合、最大$t$のクエリ(適応サンプリングであっても)を行うアルゴリズムは$\omega(t^{-\frac{\nu}{d}-1} + \sigma t^{-\frac{1}{2}})$の平均絶対誤差を負わなければならず、最大$o(t^{-\frac{\nu}{d}-1} + \sigma t^{-\frac{1}{2}})$ の誤差を達成する非適応的アルゴリズムが存在する。
したがって、境界は順序最適であり、スケーリング法則の点において適応性ギャップがないことを示す。
関連論文リスト
- Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。
R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
論文 参考訳（メタデータ） (2024-07-17T19:20:08Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。
Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文 参考訳（メタデータ） (2020-01-25T14:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。