論文の概要: Weighted least-squares approximation with determinantal point processes
and generalized volume sampling
- arxiv url: http://arxiv.org/abs/2312.14057v2
- Date: Tue, 30 Jan 2024 17:52:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-31 18:13:47.520257
- Title: Weighted least-squares approximation with determinantal point processes
and generalized volume sampling
- Title(参考訳): 行列点過程と一般化体積サンプリングによる重み付き最小二乗近似
- Authors: Anthony Nouy and Bertrand Michel
- Abstract要約: 与えられた$m$-次元空間$V_m$の要素によって、函数を$L2$から近似する問題を考える。
近似は、ほぼ確実に$H$-normで測定された最高の近似誤差によって境界づけられていることを示す。
- 参考スコア(独自算出の注目度): 37.467719211470744
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of approximating a function from $L^2$ by an element
of a given $m$-dimensional space $V_m$, associated with some feature map
$\varphi$, using evaluations of the function at random points $x_1,\dots,x_n$.
After recalling some results on optimal weighted least-squares using
independent and identically distributed points, we consider weighted
least-squares using projection determinantal point processes (DPP) or volume
sampling. These distributions introduce dependence between the points that
promotes diversity in the selected features $\varphi(x_i)$. We first provide a
generalized version of volume-rescaled sampling yielding quasi-optimality
results in expectation with a number of samples $n = O(m\log(m))$, that means
that the expected $L^2$ error is bounded by a constant times the best
approximation error in $L^2$. Also, further assuming that the function is in
some normed vector space $H$ continuously embedded in $L^2$, we further prove
that the approximation is almost surely bounded by the best approximation error
measured in the $H$-norm. This includes the cases of functions from $L^\infty$
or reproducing kernel Hilbert spaces. Finally, we present an alternative
strategy consisting in using independent repetitions of projection DPP (or
volume sampling), yielding similar error bounds as with i.i.d. or volume
sampling, but in practice with a much lower number of samples. Numerical
experiments illustrate the performance of the different strategies.
- Abstract(参考訳): 我々は、与えられた$m$-次元空間の要素による$l^2$ から関数を近似する問題を、ランダム点 $x_1,\dots,x_n$ における関数の評価を用いて、いくつかの特徴写像 $\varphi$ に関連付ける問題を考える。
独立かつ同分布の点を用いた最適重み付き最小二乗法の結果を想起した後,射影行列点過程(dpp)や体積サンプリングを用いた重み付き最小二乗法を考える。
これらの分布は、選択された特徴の多様性を促進する点間の依存を導入する。
まず, サンプル数$n = O(m\log(m))$, つまり, 期待値$L^2$の誤差は, $L^2$の最良の近似誤差の一定倍に制限される。
また、関数がノルム付きベクトル空間 $h$ で連続的に $l^2$ に埋め込まれていると仮定すると、近似が $h$-norm で測定された最良近似誤差によってほぼ確実に有界であることをさらに証明する。
これは、$L^\infty$ あるいは再生カーネルヒルベルト空間からの函数のケースを含む。
最後に、プロジェクションDPP(またはボリュームサンプリング)の独立した繰り返しを用いて、すなわちボリュームサンプリングと同様の誤差境界を出力する代替戦略を提案するが、実際にはサンプル数ははるかに少ない。
数値実験は、異なる戦略のパフォーマンスを例証する。
関連論文リスト
- Minimax Optimality of Score-based Diffusion Models: Beyond the Density
Lower Bound Assumptions [12.260288510756796]
カーネルベースのスコア推定器は$widetildeOleft(n-1 t-fracd+22(tfracd2 vee 1)rightの最適平均二乗誤差を達成する
核を用いたスコア推定器は,拡散モデルで生成した試料の分布の総変動誤差に対して,極小ガウスの下での最大平均2乗誤差を$widetildeOleft(n-1/2 t-fracd4right)$上界で達成することを示す。
論文 参考訳(メタデータ) (2024-02-23T20:51:31Z) - Transfer Operators from Batches of Unpaired Points via Entropic
Transport Kernels [3.099885205621181]
そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。
我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
論文 参考訳(メタデータ) (2024-02-13T12:52:41Z) - Convergence Rates for Non-Log-Concave Sampling and Log-Partition
Estimation [0.0]
m$timesの微分可能関数が$d$の場合、$n$(m/d)のアルゴリズムの最適レートは$n(m/d)であることが知られている。
サンプリングと計算に類似したレートが可能であり、独立レートが$d$の時間で実現可能であることを示す。
論文 参考訳(メタデータ) (2023-03-06T15:53:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳(メタデータ) (2022-03-18T18:50:52Z) - An $L^2$ Analysis of Reinforcement Learning in High Dimensions with
Kernel and Neural Network Approximation [9.088303226909277]
本稿では,カーネル法や2層ニューラルネットワークモデルを用いて関数近似を行う状況について考察する。
私たちは$tildeO(H3|mathcal A|frac14n-frac14)$を$Hn$サンプルで最適なポリシーにバインドします。
この結果はまだ有限次元の作用空間を必要とするが、誤差境界は状態空間の次元とは独立である。
論文 参考訳(メタデータ) (2021-04-15T21:59:03Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳(メタデータ) (2020-12-22T12:59:30Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。