論文の概要: Is Monte Carlo a bad sampling strategy for learning smooth functions in
high dimensions?
- arxiv url: http://arxiv.org/abs/2208.09045v1
- Date: Thu, 18 Aug 2022 20:05:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-22 17:41:35.825954
- Title: Is Monte Carlo a bad sampling strategy for learning smooth functions in
high dimensions?
- Title（参考訳）: モンテカルロは高次元で滑らかな関数を学ぶのに悪いサンプリング戦略か?
- Authors: Ben Adcock and Simone Brugiapaglia
- Abstract要約: 本稿では,量子化を用いた限られた試料からの滑らかな高次元関数の近似について検討する。
モンテカルロサンプリングは、次元の呪いに屈しないよう、そのような用途で使われるのが一般的である。
MCは,高次元において完全に優れた戦略であることを示す。
- 参考スコア（独自算出の注目度）: 4.492630871726493
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper concerns the approximation of smooth, high-dimensional functions
from limited samples using polynomials. This task lies at the heart of many
applications in computational science and engineering -- notably, those arising
from parametric modelling and uncertainty quantification. It is common to use
Monte Carlo (MC) sampling in such applications, so as not to succumb to the
curse of dimensionality. However, it is well known this strategy is
theoretically suboptimal. There are many polynomial spaces of dimension $n$ for
which the sample complexity scales log-quadratically in $n$. This
well-documented phenomenon has led to a concerted effort to design improved, in
fact, near-optimal strategies, whose sample complexities scale log-linearly, or
even linearly in $n$.
Paradoxically, in this work we show that MC is actually a perfectly good
strategy in high dimensions. We first document this phenomenon via several
numerical examples. Next, we present a theoretical analysis that resolves this
paradox for holomorphic functions of infinitely-many variables. We show that
there is a least-squares scheme based on $m$ MC samples whose error decays
algebraically fast in $m/\log(m)$, with a rate that is the same as that of the
best $n$-term polynomial approximation. This result is non-constructive, since
it assumes knowledge of a suitable polynomial space in which to perform the
approximation. We next present a compressed sensing-based scheme that achieves
the same rate, except for a larger polylogarithmic factor. This scheme is
practical, and numerically it performs as well as or better than well-known
adaptive least-squares schemes.
Overall, our findings demonstrate that MC sampling is eminently suitable for
smooth function approximation when the dimension is sufficiently high. Hence
the benefits of improved sampling strategies are generically limited to
lower-dimensional settings.
- Abstract（参考訳）: 本稿では,多項式を用いた限定標本からの滑らかな高次元関数の近似について述べる。
このタスクは計算科学と工学における多くの応用の中心であり、特にパラメトリックモデリングと不確実な定量化から生じる。
このような用途ではモンテカルロ(MC)サンプリングを用いるのが一般的であり、次元の呪いに屈しない。
しかし、この戦略が理論的に最適でないことはよく知られている。
次元 $n$ の多項式空間は多数あり、サンプル複雑性は $n$ で対数的にスケールする。
このよく文書化された現象は、実のところ、サンプルの複雑さが対数的にスケールするか、あるいは$n$で線形にスケールする準最適戦略を設計するための共同努力につながった。
反対に、この研究において、MCは実際には高次元において完璧な戦略であることを示す。
最初にこの現象をいくつかの数値例を通して記述する。
次に、無限多変数の正則函数に対するこのパラドックスを解く理論解析を提案する。
m/\log(m)$ で代数的に崩壊する $m$ mc サンプルに基づく最小二乗スキームがあり、最良の $n$ 項多項式近似と同じ率である。
この結果は、近似を実行するのに適切な多項式空間の知識を仮定するため、構成的ではない。
次に、より大きい多対数因子を除いて、同じ速度を達成する圧縮センシングに基づくスキームを提案する。
このスキームは実用的であり、数値的にはよく知られた適応最小二乗スキームよりも優れている。
総じて, MCサンプリングは, 寸法が十分に高い場合にスムーズな関数近似に極めて適していることが示された。
したがって、改良されたサンプリング戦略の利点は、一般に低次元の設定に限られる。
関連論文リスト
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Exploring and Learning in Sparse Linear MDPs without Computationally
Intractable Oracles [39.10180309328293]
本稿では,特徴選択の観点から線形MDPを再考する。
我々の主な成果は、この問題に対する最初のアルゴリズムである。
コンベックスプログラミングによって効率よく計算できることを示す。
論文 参考訳（メタデータ） (2023-09-18T03:35:48Z) - Manifold Free Riemannian Optimization [4.484251538832438]
滑らかな多様体 $mathcalM$ を用いて最適化問題を解くための原理的枠組みを提案する。
代数学M におけるコスト関数 $(x_i, y_i) の雑音のないサンプル集合 mathbbR$ と多様体 $mathcalM$ の固有次元を用いる。
論文 参考訳（メタデータ） (2022-09-07T16:19:06Z) - On efficient algorithms for computing near-best polynomial
approximations to high-dimensional, Hilbert-valued functions from limited
samples [1.0650780147044159]
スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。
本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
論文 参考訳（メタデータ） (2022-03-25T20:56:07Z) - Multiscale regression on unknown manifolds [13.752772802705978]
マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。
本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。
私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
論文 参考訳（メタデータ） (2021-01-13T15:14:31Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z) - Learning Polynomials of Few Relevant Dimensions [12.122488725065388]
多項式回帰は学習と統計の基本的な原始である。
およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
論文 参考訳（メタデータ） (2020-04-28T18:00:18Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。