論文の概要: Weighted least-squares approximation with determinantal point processes and generalized volume sampling
- arxiv url: http://arxiv.org/abs/2312.14057v3
- Date: Thu, 21 Mar 2024 08:29:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-22 19:27:29.670069
- Title: Weighted least-squares approximation with determinantal point processes and generalized volume sampling
- Title（参考訳）: 行列点過程と一般化体積サンプリングによる重み付き最小二乗近似
- Authors: Anthony Nouy, Bertrand Michel,
- Abstract要約: 与えられた$m$-次元空間$V_m$の要素によって、函数を$L2$から近似する問題を考える。
近似は、ほぼ確実に$H$-normで測定された最高の近似誤差によって境界づけられていることを示す。
- 参考スコア（独自算出の注目度）: 33.33724208084121
- 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$-次元空間 $V_m$, ある特徴写像 $\varphi$, 関数のランダム点 $x_1,\dots,x_n$ における評価を用いて, 関数を$L^2$ から所与の$m$次元空間 $V_m$ の要素で近似する問題を考える。
独立分布点と同一分布点を用いた最適重み付き最小二乗に関するいくつかの結果をリコールした後、投射決定点過程(DPP)または体積サンプリングを用いて重み付き最小二乗を考える。
これらの分布は、選択された特徴の多様性を促進する点間の依存を導入し、$\varphi(x_i)$である。
まず, サンプル数$n = O(m\log(m))$, つまり, 期待値$L^2$の誤差は, $L^2$の最良の近似誤差の一定倍に制限される。
さらに、函数があるノルムベクトル空間$H$が$L^2$に連続的に埋め込まれていることを仮定すると、近似が$H$-ノルムで測定された最高の近似誤差によってほぼ確実に有界であることが証明される。
これは、$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) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。