論文の概要: Weighted least-squares approximation with determinantal point processes
and generalized volume sampling
- arxiv url: http://arxiv.org/abs/2312.14057v1
- Date: Thu, 21 Dec 2023 17:34:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 13:54:23.373308
- 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(またはボリュームサンプリング)の独立した繰り返しを用いて、すなわちボリュームサンプリングと同様の誤差境界を出力する代替戦略を提案するが、実際にはサンプル数ははるかに少ない。
数値実験は、異なる戦略のパフォーマンスを例証する。
関連論文リスト
- Better Locally Private Sparse Estimation Given Multiple Samples Per User [2.9562742331218725]
ユーザレベルの局所微分プライベートスパース線形回帰について検討する。
我々は、$n$のユーザがそれぞれ$m$のサンプルを提供していれば、$d$の線形依存を排除できることを示した。
本稿では,まず候補変数を選択し,次に狭義の低次元空間で推定を行うフレームワークを提案する。
論文 参考訳（メタデータ） (2024-08-08T08:47:20Z) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。