論文の概要: On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples

• arxiv url: http://arxiv.org/abs/2203.13908v2
• Date: Mon, 6 Nov 2023 21:03:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 23:07:56.975873
• Title: On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples
• Title（参考訳）: 有限標本から高次元ヒルベルト値関数への近近近多項式近似の効率的な計算アルゴリズムについて
• Authors: Ben Adcock, Simone Brugiapaglia, Nick Dexter, Sebastian Moraga
• Abstract要約: スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。 本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
• 参考スコア（独自算出の注目度）: 1.0650780147044159
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse polynomial approximation has become indispensable for approximating smooth, high- or infinite-dimensional functions from limited samples. This is a key task in computational science and engineering, e.g., surrogate modelling in uncertainty quantification where the function is the solution map of a parametric or stochastic differential equation (DE). Yet, sparse polynomial approximation lacks a complete theory. On the one hand, there is a well-developed theory of best $s$-term polynomial approximation, which asserts exponential or algebraic rates of convergence for holomorphic functions. On the other, there are increasingly mature methods such as (weighted) $\ell^1$-minimization for computing such approximations. While the sample complexity of these methods has been analyzed with compressed sensing, whether they achieve best $s$-term approximation rates is not fully understood. Furthermore, these methods are not algorithms per se, as they involve exact minimizers of nonlinear optimization problems. This paper closes these gaps. Specifically, we consider the following question: are there robust, efficient algorithms for computing approximations to finite- or infinite-dimensional, holomorphic and Hilbert-valued functions from limited samples that achieve best $s$-term rates? We answer this affirmatively by introducing algorithms and theoretical guarantees that assert exponential or algebraic rates of convergence, along with robustness to sampling, algorithmic, and physical discretization errors. We tackle both scalar- and Hilbert-valued functions, this being key to parametric or stochastic DEs. Our results involve significant developments of existing techniques, including a novel restarted primal-dual iteration for solving weighted $\ell^1$-minimization problems in Hilbert spaces. Our theory is supplemented by numerical experiments demonstrating the efficacy of these algorithms.
• Abstract（参考訳）: スパース多項式近似は、限られたサンプルから滑らかで高次元あるいは無限次元の関数を近似するのに不可欠である。 これは計算科学や工学における重要なタスクであり、例えば、関数がパラメトリックあるいは確率微分方程式(DE)の解写像である不確実量化における代理モデリングである。 しかし、スパース多項式近似は完全な理論を欠いている。 一方で、正則函数に対する指数的あるいは代数的収束率を主張する最良の$s$項多項式近似の理論が発達している。 一方、そのような近似を計算するための(重み付けされた)$\ell^1$-minimizationのような成熟した方法がある。 これらの手法のサンプルの複雑さは, 圧縮センシングを用いて解析されているが, 最高の$s$-term近似値が得られるかどうかは完全には分かっていない。 さらに、これらの手法は非線形最適化問題の最小化を含むため、それぞれアルゴリズムではない。 この論文はこれらのギャップを閉じる。 具体的には, 有限次元, 無限次元, 正則関数, ヒルベルト値関数に対する近似を, 最高の$s$-term レートで計算する堅牢で効率的なアルゴリズムが存在するか? 我々は, 指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証を導入し, サンプリング, アルゴリズム的, 物理的離散化誤差に対するロバスト性を導入することで, 肯定的に答える。 我々はスカラー関数とヒルベルト値関数の両方に取り組み、これはパラメトリックあるいは確率的Dsの鍵となる。 本研究は,ヒルベルト空間における重み付き$\ell^1$-minimization問題の解法を再開した原始双対反復を含む既存手法の大幅な発展を含む。 これらのアルゴリズムの有効性を示す数値実験により,本理論を補足する。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
  コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。 数値実験では, 既存の再起動バージョンよりも改善が見られた。
  論文  参考訳（メタデータ） (2021-08-10T07:15:07Z)
• A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
  計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。 予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
  論文  参考訳（メタデータ） (2021-06-22T07:24:17Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。 また、単一または2つのミニバッチ誘導体でも機能する。
  論文  参考訳（メタデータ） (2020-06-27T03:05:18Z)
• 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)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)

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

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