論文の概要: Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time
- arxiv url: http://arxiv.org/abs/2311.01435v1
- Date: Thu, 2 Nov 2023 17:51:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-03 12:23:27.194053
- Title: Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time
- Title（参考訳）: 対比モーメント:多項式時間における教師なし半空間学習
- Authors: Xinyuan Cao, Santosh S. Vempala
- Abstract要約: 所望のテレビ距離内において,$d$次元空間にマージンを持つ高次元半空間を学習するためのガウス時間アルゴリズムを提案する。
我々のアルゴリズムはラベルを必要とせず、隠れたハーフスペースのユニークな(そして効率的な)識別性を確立する。
超ポリノミカルな既存のモーメントバウンド保証の代わりに、トータル変分(TV)距離に基づくポリタイム保証を提供することにより、この問題を改善する。
- 参考スコア（独自算出の注目度）: 8.419603619167813
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a polynomial-time algorithm for learning high-dimensional halfspaces
with margins in $d$-dimensional space to within desired TV distance when the
ambient distribution is an unknown affine transformation of the $d$-fold
product of an (unknown) symmetric one-dimensional logconcave distribution, and
the halfspace is introduced by deleting at least an $\epsilon$ fraction of the
data in one of the component distributions. Notably, our algorithm does not
need labels and establishes the unique (and efficient) identifiability of the
hidden halfspace under this distributional assumption. The sample and time
complexity of the algorithm are polynomial in the dimension and $1/\epsilon$.
The algorithm uses only the first two moments of suitable re-weightings of the
empirical distribution, which we call contrastive moments; its analysis uses
classical facts about generalized Dirichlet polynomials and relies crucially on
a new monotonicity property of the moment ratio of truncations of logconcave
distributions. Such algorithms, based only on first and second moments were
suggested in earlier work, but hitherto eluded rigorous guarantees.
Prior work addressed the special case when the underlying distribution is
Gaussian via Non-Gaussian Component Analysis. We improve on this by providing
polytime guarantees based on Total Variation (TV) distance, in place of
existing moment-bound guarantees that can be super-polynomial. Our work is also
the first to go beyond Gaussians in this setting.
- Abstract（参考訳）: 本研究では,(未知)対称一次元対数凸分布のd$-fold積の未知アフィン変換であるとき,d$次元空間のマージンが所望のテレビ距離内にある高次元のハーフスペースを学習するための多項式時間アルゴリズムを与え,そのハーフスペースは,少なくとも$\epsilon$の分数を1つの成分分布から削除することにより導入する。
特に,本アルゴリズムはラベルを必要とせず,この分布仮定の下で隠れた半空間のユニークな(かつ効率的な)識別性を確立する。
アルゴリズムのサンプルと時間の複雑さは、次元の多項式と1/\epsilon$である。
このアルゴリズムは、我々がコントラストモーメントと呼ぶ経験的分布の適切な再重み付けの最初の2つのモーメントのみを使用し、解析は一般化されたディリクレ多項式に関する古典的な事実を使用し、ログコンケーブ分布の切り欠きのモーメント比の新たな単調性に大きく依存する。
このようなアルゴリズムは、初期の研究で第1と第2の瞬間のみに基づいて提案されたが、ヒッヘルトは厳密な保証を免れた。
以前の研究は、基礎となる分布がガウス成分分析(英語版)によるガウス分布である特別なケースに対処した。
我々は、超多項化可能な既存のモーメントバウンド保証の代わりに、全変動(tv)距離に基づくポリタイム保証を提供することにより、これを改善する。
私たちの作品は、この設定でガウシアンを超えた最初の作品です。
関連論文リスト
- Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。
我々は、下層の混合成分について分離を前提としない。
我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-29T17:30:36Z) - Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
離散化マルコフ過程に基づく$mu_phi $の線形汎函数の2つの推定器を検討する。
誤差境界は、本質的に定義されたランゲヴィン拡散の離散化を用いてサンプリングと推定のために導出される。
論文 参考訳（メタデータ） (2023-12-22T18:01:11Z) - Robust Estimation for Nonparametric Families via Generative Adversarial
Networks [92.64483100338724]
我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。
我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。
技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
論文 参考訳（メタデータ） (2022-02-02T20:11:33Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin
Algorithm [11.80267432402723]
ログ凹型確率分布に対するサンプリングの課題を考察する。
対象の分布は、ワッサーシュタイン空間上で定義されるクルバック・リーバーの発散の最小値と見なすことができる。
ポテンシャルが強い凸であれば、PSGLA の複雑さは 2-ワッサーシュタイン距離の点で$O (1/varepsilon2)$である。
論文 参考訳（メタデータ） (2020-06-16T15:57:09Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。
この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
論文 参考訳（メタデータ） (2020-05-06T17:24:27Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。