論文の概要: Information-Theoretic Bounds for Integral Estimation
- arxiv url: http://arxiv.org/abs/2102.10199v1
- Date: Fri, 19 Feb 2021 23:07:26 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-23 14:35:48.515868
- Title: Information-Theoretic Bounds for Integral Estimation
- Title（参考訳）: 積分推定のための情報理論境界
- Authors: Donald Q. Adams and Adarsh Barik and Jean Honorio
- Abstract要約: 本稿では,定積分を推定するゼロ次オラクルモデルを考察する。
d$次元関数の積分を推定するための情報理論上の誤差は$omega (2d rd+1sqrtd/t)$である。
- 参考スコア（独自算出の注目度）: 27.243424330309608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider a zero-order stochastic oracle model of estimating
definite integrals. In this model, integral estimation methods may query an
oracle function for a fixed number of noisy values of the integrand function
and use these values to produce an estimate of the integral. We first show that
the information-theoretic error lower bound for estimating the integral of a
$d$-dimensional function over a region with $l_\infty$ radius $r$ using at most
$T$ queries to the oracle function is $\Omega(2^d r^{d+1}\sqrt{d/T})$.
Additionally, we find that the Gaussian Quadrature method under the same model
achieves a rate of $O(2^{d}r^d/\sqrt{T})$ for functions with zero fourth and
higher-order derivatives with respect to individual dimensions, and for
Gaussian oracles, this rate is tight. For functions with nonzero fourth
derivatives, the Gaussian Quadrature method achieves an upper bound which is
not tight with the information-theoretic lower bound. Therefore, it is not
minimax optimal, so there is space for the development of better integral
estimation methods for such functions.
- Abstract（参考訳）: 本稿では,定積分を推定するゼロ次確率オラクルモデルを考える。
このモデルでは、積分推定法は積分関数の定数の雑音値に対してオラクル関数を問合せし、これらの値を用いて積分を推定することができる。
まず、オラクル関数に対する少なくとも$T$クエリを用いて、$l_\infty$ radius $r$の領域上の$d$次元関数の積分を推定するための情報理論誤差の下界が$\Omega(2^d r^{d+1}\sqrt{d/T})$であることを示す。
さらに、同じモデルの下でのガウス四乗法は、個々の次元に関して4次および高階微分がゼロの関数に対して $O(2^{d}r^d/\sqrt{T})$ のレートを達成し、ガウスのオラクルの場合、このレートはタイトである。
非ゼロ四階微分を持つ函数に対しては、ガウス四階述語法は情報理論の下界と密接でない上界を達成する。
したがって、極小極小ではないため、そのような関数に対するより良い積分推定法を開発する余地がある。
関連論文リスト
- Learning a Sparse Representation of Barron Functions with the Inverse
Scale Space Flow [3.249853429482705]
L2$ 関数 $f$ が与えられたとき、逆スケール空間の流れはスパース測度 $mu$ を見つけるために使われる。
本手法の収束特性は, 理想的な設定で, 測定ノイズやサンプリングバイアスの場合に解析される。
論文 参考訳（メタデータ） (2023-12-05T11:26:02Z) - Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via
Leverage Scores Sampling [16.992480926905067]
本稿では,積分を対象確率測度に対して,積分の点的評価のみを用いて近似する問題を考察する。
本稿では,初期観測から得られる近似レバレッジスコアを用いて,$mn$サンプルのランダムな小部分集合を均一に描画するか,あるいは近似的に評価する手法を提案する。
論文 参考訳（メタデータ） (2023-11-22T17:44:18Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。
私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
論文 参考訳（メタデータ） (2020-06-12T17:25:39Z) - On Suboptimality of Least Squares with Application to Estimation of
Convex Bodies [74.39616164169131]
雑音支援関数の測定から得られる凸を次元$dgeq 6$で推定する際、最小広場の最適性に関するオープンな問題を解決した。
Least Squaresは準最適であり、$tildeTheta_d(n-2/(d-1))$であるのに対して、minimaxレートは$Theta_d(n-4/(d+3)$である。
論文 参考訳（メタデータ） (2020-06-07T05:19:00Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z) - Spectral density estimation with the Gaussian Integral Transform [91.3755431537592]
スペクトル密度作用素 $hatrho(omega)=delta(omega-hatH)$ は線形応答論において中心的な役割を果たす。
スペクトル密度を近似する近似量子アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2020-04-10T03:14:38Z) - Information-Theoretic Lower Bounds for Zero-Order Stochastic Gradient
Estimation [28.776950569604026]
ゼロ階オラクルモデルにおける任意の多次元滑らか関数の勾配を推定するために必要なサンプル数を解析する。
有界分散オラクルに対する有限差分法は、ゼロ第三高微分を持つ函数に対して$O(d4/3/sqrtT)$を持つことを示す。
論文 参考訳（メタデータ） (2020-03-31T00:11:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。