論文の概要: Optimal sampling for least-squares approximation
- arxiv url: http://arxiv.org/abs/2409.02342v1
- Date: Wed, 4 Sep 2024 00:06:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-05 20:51:59.792070
- Title: Optimal sampling for least-squares approximation
- Title（参考訳）: 最小二乗近似のための最適サンプリング
- Authors: Ben Adcock,
- Abstract要約: ランダムサンプルから(重み付けされた)最小二乗近似の解析において、クリスティーフェル関数を重要な量として導入する。
ほぼ最適なサンプル複雑性を持つサンプリング戦略を構築するためにどのように使用できるかを示す。
- 参考スコア（独自算出の注目度）: 0.8702432681310399
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Least-squares approximation is one of the most important methods for recovering an unknown function from data. While in many applications the data is fixed, in many others there is substantial freedom to choose where to sample. In this paper, we review recent progress on optimal sampling for (weighted) least-squares approximation in arbitrary linear spaces. We introduce the Christoffel function as a key quantity in the analysis of (weighted) least-squares approximation from random samples, then show how it can be used to construct sampling strategies that possess near-optimal sample complexity: namely, the number of samples scales log-linearly in $n$, the dimension of the approximation space. We discuss a series of variations, extensions and further topics, and throughout highlight connections to approximation theory, machine learning, information-based complexity and numerical linear algebra. Finally, motivated by various contemporary applications, we consider a generalization of the classical setting where the samples need not be pointwise samples of a scalar-valued function, and the approximation space need not be linear. We show that even in this significantly more general setting suitable generalizations of the Christoffel function still determine the sample complexity. This provides a unified procedure for designing improved sampling strategies for general recovery problems. This article is largely self-contained, and intended to be accessible to nonspecialists.
- Abstract（参考訳）: 最小二乗近似は、未知の関数をデータから復元する最も重要な方法の1つである。
多くのアプリケーションではデータが固定されているが、他の多くのアプリケーションではサンプルの場所を選択する自由がある。
本稿では、任意の線型空間における(重み付けされた)最小二乗近似の最適サンプリングに関する最近の進歩について述べる。
ランダムサンプルから(重み付けされた)最小二乗近似を解析する上で重要な量としてChristoffel関数を導入し、次に、近似空間の次元である$n$で対数的にスケールするサンプルの数を、ほぼ最適サンプルの複雑性を持つサンプリング戦略を構築する方法を示す。
本稿では,一連の変分,拡張,さらに話題について論じるとともに,近似理論,機械学習,情報ベース複雑性,数値線形代数学などとの関係を概観する。
最後に、様々な現代的応用を動機として、標本がスカラー値関数の点的サンプルである必要がなく、近似空間が線型でなくてもよい古典的な設定の一般化を考える。
この非常に一般的な設定においても、クリストッフェル函数の適切な一般化が標本の複雑さを決定づけていることが示される。
これにより、一般的なリカバリ問題に対する改良されたサンプリング戦略を設計するための統一的な手順が提供される。
この記事は、主に自己完結型であり、非専門主義者にアクセスできることを意図している。
関連論文リスト
- Samplet basis pursuit: Multiresolution scattered data approximation with sparsity constraints [0.0]
我々は,$ell_1$-regularization を用いたサンプルト座標における分散データ近似について検討する。
Riesz isometry を用いて、標本を再現されたカーネルヒルベルト空間に埋め込む。
組込みサンプルベースに対してスパースな信号のクラスは、カーネル翻訳の基盤に関してスパースな信号のクラスよりもかなり大きいと論じる。
論文 参考訳（メタデータ） (2023-06-16T21:20:49Z) - CS4ML: A general framework for active learning with arbitrary data based
on Christoffel functions [0.7366405857677226]
回帰問題における能動的学習のための一般的なフレームワークを紹介する。
本フレームワークは, 有限個のサンプリング測度と任意の非線形近似空間に基づいて, ランダムサンプリングを考察する。
本稿では,能動的学習が望ましい科学計算の応用に焦点を当てる。
論文 参考訳（メタデータ） (2023-06-01T17:44:19Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - Sampling Approximately Low-Rank Ising Models: MCMC meets Variational
Methods [35.24886589614034]
一般相互作用が$J$である超キューブ上の二次定値イジングモデルを考える。
我々の一般的な結果は、低ランクのIsingモデルに対する最初のサンプリングアルゴリズムを示唆している。
論文 参考訳（メタデータ） (2022-02-17T21:43:50Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - Revisiting the Sample Complexity of Sparse Spectrum Approximation of
Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。
我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文 参考訳（メタデータ） (2020-11-17T05:41:50Z) - Pathwise Conditioning of Gaussian Processes [72.61885354624604]
ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。
この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。
条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
論文 参考訳（メタデータ） (2020-11-08T17:09:37Z) - A Multilinear Sampling Algorithm to Estimate Shapley Values [4.771833920251869]
ゲーム理論に適用したマルチ線形拡張手法に基づく新しいサンプリング手法を提案する。
本手法は任意の機械学習モデル,特に多クラス分類や回帰問題に適用可能である。
論文 参考訳（メタデータ） (2020-10-22T21:47:16Z) - Effective Proximal Methods for Non-convex Non-smooth Regularized
Learning [27.775096437736973]
独立サンプリング方式は、一般に使用されている一様サンプリング方式の性能を向上させる傾向にあることを示す。
我々の新しい分析は、サンプリングの速度が今までで最高のものより速いことも示しています。
論文 参考訳（メタデータ） (2020-09-14T16:41:32Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z) - Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
高速後部サンプリングのための簡易かつ汎用的なアプローチを提案する。
分離されたサンプルパスがガウス過程の後部を通常のコストのごく一部で正確に表現する方法を実証する。
論文 参考訳（メタデータ） (2020-02-21T14:03:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。