論文の概要: Dimensionality Reduction for General KDE Mode Finding

• arxiv url: http://arxiv.org/abs/2305.18755v2
• Date: Wed, 31 May 2023 08:00:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 11:50:21.199048
• Title: Dimensionality Reduction for General KDE Mode Finding
• Title（参考訳）: 一般KDEモード探索のための次元化
• Authors: Xinyu Luo, Christopher Musco, Cas Widdershoven
• Abstract要約: 高次元確率分布のモードを$D$で見つけることは、統計学とデータ解析の基本的な問題である。 我々は、$mathitP = MathitNP$ でない限り、カーネル密度推定のモードを見つけるための時間アルゴリズムがないことを示す。
• 参考スコア（独自算出の注目度）: 12.779486428760373
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the mode of a high dimensional probability distribution $D$ is a fundamental algorithmic problem in statistics and data analysis. There has been particular interest in efficient methods for solving the problem when $D$ is represented as a mixture model or kernel density estimate, although few algorithmic results with worst-case approximation and runtime guarantees are known. In this work, we significantly generalize a result of (LeeLiMusco:2021) on mode approximation for Gaussian mixture models. We develop randomized dimensionality reduction methods for mixtures involving a broader class of kernels, including the popular logistic, sigmoid, and generalized Gaussian kernels. As in Lee et al.'s work, our dimensionality reduction results yield quasi-polynomial algorithms for mode finding with multiplicative accuracy $(1-\epsilon)$ for any $\epsilon > 0$. Moreover, when combined with gradient descent, they yield efficient practical heuristics for the problem. In addition to our positive results, we prove a hardness result for box kernels, showing that there is no polynomial time algorithm for finding the mode of a kernel density estimate, unless $\mathit{P} = \mathit{NP}$. Obtaining similar hardness results for kernels used in practice (like Gaussian or logistic kernels) is an interesting future direction.
• Abstract（参考訳）: 高次元確率分布のモードの発見 $d$ は統計学やデータ分析における基本的なアルゴリズム問題である。 d$ が混合モデルまたはカーネル密度推定として表現されるとき、この問題の効率的な解法には特に関心があるが、最悪の場合の近似と実行時の保証を伴うアルゴリズム的な結果はほとんど知られていない。 本研究では,ガウス混合モデルのモード近似における (LeeLiMusco:2021) の結果を著しく一般化する。 本研究では,一般的なロジスティック,シグモイド,一般化ガウス核を含む,幅広い種類のカーネルを含む混合系のランダム次元低減法を開発した。 Leeらの研究と同様に、我々の次元減少結果は、任意の$\epsilon > 0$に対して、乗法精度(1-\epsilon)$のモード探索のための準多項式アルゴリズムを生成する。 さらに、勾配降下と組み合わせると、この問題に対する効率的な実用的ヒューリスティックが生まれる。 正の結果に加えて、ボックスカーネルの硬度結果も証明し、$\mathit{P} = \mathit{NP}$でない限り、カーネル密度推定のモードを見つける多項式時間アルゴリズムは存在しないことを示した。 現実に使われているカーネル(ガウスやロジスティックカーネルなど)の同様のハードネス結果を得ることは、興味深い将来的な方向性である。

関連論文リスト

• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• Learning Mixtures of Gaussians Using Diffusion Models [9.118706387430883]
  テレビエラーに対して$k$ Gaussiansの混合を学習するための新しいアルゴリズムを提案する。 我々のアプローチは解析的であり、拡散モデルの枠組みに依存している。
  論文  参考訳（メタデータ） (2024-04-29T17:00:20Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。 理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。 シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
  論文  参考訳（メタデータ） (2023-06-05T21:08:34Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat\'ern Correlations [23.560067934682294]
  マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。 提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
  論文  参考訳（メタデータ） (2022-03-07T03:30:35Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning [0.0]
  ランジュバンアルゴリズムは付加ノイズを持つ手法である。 ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた 学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
  論文  参考訳（メタデータ） (2020-12-22T16:19:20Z)
• Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
  我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。 私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
  論文  参考訳（メタデータ） (2020-06-12T17:25:39Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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