論文の概要: Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs
- arxiv url: http://arxiv.org/abs/2607.29245v1
- Date: Fri, 31 Jul 2026 10:18:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-03 14:29:40.691308
- Title: Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs
- Title（参考訳）: マテランおよび2乗指数RKHSにおける固定優先改善の簡易回帰率と最小値最適性
- Abstract要約: 非空コンパクト集合 $mathcal X の部分集合 Rd$ 上で、決定論的目的関数 $f$ を最小化するための期待された改善 (EI) ポリシーについて検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study the expected improvement (EI) policy for minimizing a deterministic objective function $f$ on a nonempty compact set $\mathcal X \subset\mathbb R^d$. We assume that $f$ belongs to the RKHS $\mathcal H_k$ of a continuous positive-semidefinite kernel $k$ on $\mathcal X$. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance $σ^2k$. After an initial design, the policy queries a point whose EI is at least a fixed positive fraction of its maximum. We identify the normalized posterior standard deviation at a candidate point $x$ with the norm of the corresponding innovation in the canonical feature space, namely the component of $k(x,\cdot)$ orthogonal to the span of the preceding evaluation representers. Sequential separation radii bound the ranked innovation norms along arbitrary query sequences. We estimate these radii using Gram determinants and Kolmogorov widths for subspaces of different dimensions, then combine the estimates with a one-step regret inequality to obtain finite-budget bounds for simple regret. After $N$ post-initial queries, simple regret is $O(N^{-ν/d})$ for isotropic Matérn kernels of smoothness $ν>0$. For the isotropic squared-exponential kernel, simple regret is $O(\exp[-c_1\min\{N, N^{1/d}\log(eN)\}])$ for some $c_1>0$. With exact EI maximization, it is $O(\exp[-c_2N^{1/d} \log(eN)])$ for some $c_2>0$. For every fixed $B\geq0$, these bounds are uniform over the RKHS ball of radius $B$. If $\mathcal X$ has nonempty interior and $B>0$, then, among deterministic methods whose final recommendation may be any point of $\mathcal X$, the exact EI policy is minimax-rate optimal over the RKHS ball of radius $B$ for Matérn kernels and minimax-rate optimal up to constants in the exponent for squared-exponential kernels.
- Abstract（参考訳）: 非空コンパクト集合 $\mathcal X \subset\mathbb R^d$ 上で、決定論的目的関数 $f$ を最小化するための期待された改善 (EI) ポリシーについて検討する。
f$ は RKHS $\mathcal H_k$ の連続正準有限核 $k$ on $\mathcal X$ に属すると仮定する。
関数の値は正確に観測され、EIは共分散$σ^2k$で固定されたゼロ平均ガウス過程モデルから計算される。
最初の設計の後、ポリシーは、EIがその最大値の少なくとも1つの正の分数である点を問う。
正規化後標準偏差は、標準特徴空間における対応する革新のノルム、すなわち、前の評価表現子のスパンに直交する$k(x,\cdot)$の成分により、候補点$x$で特定する。
逐次分離ラジイは任意のクエリシーケンスに沿ってランク付けされたイノベーションノルムを束縛する。
異なる次元の部分空間に対して、グラム行列式とコルモゴロフ幅を用いてこれらのラジイを推定し、その推定を1ステップの後悔不等式と組み合わせ、単純な後悔のために有限予算境界を得る。
開始後クエリの後で、単純な後悔は、滑らかな$ν>0$の等方行列核に対して$O(N^{-ν/d})$である。
等方的二進核の場合、単純な後悔は$O(\exp[-c_1\min\{N, N^{1/d}\log(eN)\}])$ for some $c_1>0$である。
正確なEI最大化では、ある$c_2>0$に対して$O(\exp[-c_2N^{1/d} \log(eN)])$である。
固定されたすべての$B\geq0$に対して、これらの境界は半径$B$のRKHS球上で一様である。
もし$\mathcal X$ が空でない内部と$B>0$ を持つなら、最終的な推奨値が$\mathcal X$ の任意の点である決定論的手法の中で、正確な EI ポリシーは、半径 $B$ の RKHS 球に対して極大であり、最小極小は、平方指数カーネルの指数における定数まで最適である。
関連論文リスト
- Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Solving Stochastic Fixed-Point Equations with High Probability [22.376855234542813]
オラクルの不動点方程式 $mathbfT(mathbfx) = mathbfx$ をノルム空間上で研究する。
本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
論文 参考訳（メタデータ） (2026-07-10T04:59:20Z) - Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals [5.7652356955571085]
i.d.ラベル付きサンプルが$mathbbRd times pm 1$上の未知の分布からサンプリングされ、$mathbbRd$がガウシアンであることを考えると、目標はターゲットクラス$mathcalF$から仮説を出力することである。
我々のアルゴリズムは、$dO(K2 log (1/)/2) + (K/)O(K) で実行されます。
論文 参考訳（メタデータ） (2026-05-26T19:07:06Z) - Minimax optimal submatrix detection: Sharp non-asymptotic rates [1.7188280334580195]
平均行列 $mathbf X$ における植木部分行列を検出する問題を考える。
2つの仮説が高い確率で識別可能であることを保証するために、$がどれほど大きいかを示すミニマックス最適化を確立する。
我々の漸近的でない上境界と下限は、これらのパラメータの任意の構成に一致する。
論文 参考訳（メタデータ） (2026-05-10T14:30:16Z) - Computational Hardness of Private Coreset [84.99100741615423]
与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。
no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。
$k$-means in the
論文 参考訳（メタデータ） (2026-02-19T15:58:49Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
この仮定は、収束とより微細な結果には必要ないことが初めて示される。
標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。
数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
論文 参考訳（メタデータ） (2024-05-28T05:11:05Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。