論文の概要: Compressed Empirical Measures (in finite dimensions)
- arxiv url: http://arxiv.org/abs/2204.08847v3
- Date: Tue, 27 Aug 2024 18:32:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-30 19:54:50.080325
- Title: Compressed Empirical Measures (in finite dimensions)
- Title(参考訳): 圧縮経験的測度(有限次元)
- Authors: Steffen Grünewälder,
- Abstract要約: 有限次元再生核ヒルベルト空間(RKHS)の文脈における経験的尺度の圧縮手法について検討する。
そのようなコアセットがどれほど大きいかを制御する重要な量は、経験的凸集合に含まれる経験的測度の周りにある最大の球の大きさである。
- 参考スコア(独自算出の注目度): 4.73194777046253
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study approaches for compressing the empirical measure in the context of finite dimensional reproducing kernel Hilbert spaces (RKHSs). In this context, the empirical measure is contained within a natural convex set and can be approximated using convex optimization methods. Such an approximation gives rise to a coreset of data points. A key quantity that controls how large such a coreset has to be is the size of the largest ball around the empirical measure that is contained within the empirical convex set. The bulk of our work is concerned with deriving high probability lower bounds on the size of such a ball under various conditions and in various settings: we show how conditions on the density of the data and the kernel function can be used to infer such lower bounds; we further develop an approach that uses a lower bound on the smallest eigenvalue of a covariance operator to provide lower bounds on the size of such a ball; we extend the approach to approximate covariance operators and we show how it can be used in the context of kernel ridge regression. We also derive compression guarantees when standard algorithms like the conditional gradient method are used and we discuss variations of such algorithms to improve the runtime of these standard algorithms. We conclude with a construction of an infinite dimensional RKHS for which the compression is poor, highlighting some of the difficulties one faces when trying to move to infinite dimensional RKHSs.
- Abstract(参考訳): 有限次元再生カーネルヒルベルト空間(RKHS)の文脈における経験的尺度の圧縮手法について検討する。
この文脈では、経験的測度は自然凸集合の中に含まれ、凸最適化法を用いて近似することができる。
このような近似は、データポイントのコアセットを引き起こす。
そのようなコアセットがどれほど大きいかを制御する重要な量は、経験的凸集合に含まれる経験的測度の周りにある最大の球の大きさである。
研究の大部分は, 様々な条件下で, 様々な条件下で, ボールの大きさに対する高い確率的下界を導出することに関するものである: データ密度とカーネル関数の条件が, それらの下界を推測するためにどのように使用できるかを示す; さらに, 共分散作用素の最小固有値に対する下界を用いて, ボールの大きさに対する下界を与えるアプローチを開発する; 近似共分散演算子へのアプローチを拡張し, カーネルリッジ回帰の文脈でどのように使用できるかを示す。
また,条件勾配法のような標準アルゴリズムを用いた場合の圧縮保証を導出し,これらの標準アルゴリズムのランタイムを改善するために,そのようなアルゴリズムのバリエーションについて議論する。
無限次元のRKHSの構成は圧縮が貧弱であり、無限次元のRKHSに移動しようとする際に直面する困難を浮き彫りにする。
関連論文リスト
- Sampling in Constrained Domains with Orthogonal-Space Variational
Gradient Descent [13.724361914659438]
多様体上のサンプリングのための直交空間勾配流(O-Gradient)を設計した新しい変分フレームワークを提案する。
我々は、O-Gradient が目標制約分布に収束し、弱条件下では、$widetildeO (1/textthe number of iterations)$$で収束することを証明した。
論文 参考訳(メタデータ) (2022-10-12T17:51:13Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Nystr\"om Kernel Mean Embeddings [92.10208929236826]
Nystr"om法に基づく効率的な近似手法を提案する。
サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。
本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
論文 参考訳(メタデータ) (2022-01-31T08:26:06Z) - Manifold Hypothesis in Data Analysis: Double Geometrically-Probabilistic
Approach to Manifold Dimension Estimation [92.81218653234669]
本稿では, 多様体仮説の検証と基礎となる多様体次元推定に対する新しいアプローチを提案する。
我々の幾何学的手法はミンコフスキー次元計算のためのよく知られたボックスカウントアルゴリズムのスパースデータの修正である。
実データセットの実験では、2つの手法の組み合わせに基づく提案されたアプローチが強力で効果的であることが示されている。
論文 参考訳(メタデータ) (2021-07-08T15:35:54Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳(メタデータ) (2021-06-04T16:37:19Z) - Cyclic Coordinate Dual Averaging with Extrapolation [22.234715500748074]
単調作用素を用いた変分不等式(VI)問題の一般クラスに適用可能な新しいブロック座標法を提案する。
得られた収束境界は、全勾配法の最適収束境界と一致する。
座標ブロックが$m$の場合、我々の境界における勾配リプシッツ定数は、従来のユークリッドのリプシッツ定数と比較して$sqrtm$よりも大きくなることはない。
論文 参考訳(メタデータ) (2021-02-26T00:28:58Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
論文 参考訳(メタデータ) (2020-02-21T00:43:06Z) - RFN: A Random-Feature Based Newton Method for Empirical Risk
Minimization in Reproducing Kernel Hilbert Spaces [14.924672048447334]
大規模な有限サム問題はニュートン法の効率的な変種を用いて解くことができ、ヘッセンはデータのサブサンプルによって近似される。
本稿では,このような問題に対して,ニュートン法を高速化するためにカーネル近似を自然に利用できることを考察する。
局所超線型収束と大域線形収束を両立させる新しい2次アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-12T01:14:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。