論文の概要: Monte Carlo is a good sampling strategy for polynomial approximation in
high dimensions
- arxiv url: http://arxiv.org/abs/2208.09045v3
- Date: Sun, 5 Nov 2023 20:58:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 01:41:40.171876
- Title: Monte Carlo is a good sampling strategy for polynomial approximation in
high dimensions
- Title（参考訳）: モンテカルロは高次元多項式近似のよいサンプリング戦略である
- Authors: Ben Adcock and Simone Brugiapaglia
- Abstract要約: 本稿では,代数を用いた限定標本からの滑らかな高次元関数の近似について検討する。
モンテカルロサンプリングは、次元の呪いに屈しないよう、そのような用途で使われるのが一般的である。
誤差が $m/log(m)$ で高速に減衰するモンテカルロのサンプルから最小二乗近似が存在することを示す。
- 参考スコア（独自算出の注目度）: 1.4141453107129398
- 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, some of those
arising from parametric modelling and computational uncertainty quantification.
It is common to use Monte Carlo sampling in such applications, so as not to
succumb to the curse of dimensionality. However, it is well known that such a
strategy is theoretically suboptimal. Specifically, there are many polynomial
spaces of dimension $n$ for which the sample complexity scales
log-quadratically, i.e., like $c \cdot n^2 \cdot \log(n)$ as $n \rightarrow
\infty$. This well-documented phenomenon has led to a concerted effort over the
last decade to design improved, and moreover, near-optimal strategies, whose
sample complexities scale log-linearly, or even linearly in $n$. In this work
we demonstrate that Monte Carlo is actually a perfectly good strategy in high
dimensions, despite its apparent suboptimality. We first document this
phenomenon empirically via a systematic set of numerical experiments. Next, we
present a theoretical analysis that rigorously justifies this fact in the case
of holomorphic functions of infinitely-many variables. We show that there is a
least-squares approximation based on $m$ Monte Carlo 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 subspace 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.
- Abstract（参考訳）: 本稿では,多項式を用いた限定標本からの滑らかな高次元関数の近似について述べる。
このタスクは、計算科学と工学における多くの応用の中心であり、特にパラメトリックモデリングと計算の不確実性定量化から生じるものの一部である。
このような応用ではモンテカルロサンプリングを用いるのが一般的であり、次元の呪いに屈しない。
しかし、そのような戦略が理論的に最適でないことはよく知られている。
特に、サンプル複雑性が対数的にスケールする次元 $n$ の多項式空間、すなわち $c \cdot n^2 \cdot \log が存在する。
(n)$ as $n \rightarrow \infty$。
この十分に文書化された現象は、過去10年間にわたって改良された設計に尽力し、さらに、サンプルの複雑さが対数的に、あるいは直線的にn$でスケールする、最適化に近い戦略を生み出した。
この研究で、モンテカルロは明らかな準最適性にもかかわらず、実際には高次元において完全に良い戦略であることを示した。
この現象を系統的な数値実験を通して経験的に記述した。
次に、無限多変数の正則函数の場合、この事実を厳密に正当化する理論解析を提案する。
誤差が$m/\logで代数的に高速に崩壊するモンテカルロサンプルをベースとした最小二乗近似が存在することを示す。
(m)$, 最高の$n$項多項式近似の値と同じレートである。
この結果は非構成的であり、近似を実行する適切な多項式部分空間の知識を前提としている。
次に、より大きい多対数因子を除いて、同じ速度を達成する圧縮センシングに基づくスキームを提案する。
このスキームは実用的であり、数値的にはよく知られた適応最小二乗スキームよりも優れている。
関連論文リスト
- 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) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。