論文の概要: 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(またはボリュームサンプリング)の独立した繰り返しを用いて、すなわちボリュームサンプリングと同様の誤差境界を出力する代替戦略を提案するが、実際にはサンプル数ははるかに少ない。 数値実験は、異なる戦略のパフォーマンスを例証する。

関連論文リスト

• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。 広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
  論文  参考訳（メタデータ） (2025-02-10T06:54:16Z)
• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。 最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
  論文  参考訳（メタデータ） (2025-01-09T18:31:35Z)
• Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions [9.48556659249574]
  固定次元の複雑なサンプリングアルゴリズムを提案する。 我々は,提案アルゴリズムが予測される$epsilon$誤差を$KL$ばらつきで達成することを証明する。 応用として、$L$-log-smooth分布からサンプリングする問題に対する指数関数的複雑性の改善を導出する。
  論文  参考訳（メタデータ） (2024-12-31T17:51:39Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。