論文の概要: Non-Gaussian Component Analysis via Lattice Basis Reduction

• arxiv url: http://arxiv.org/abs/2112.09104v1
• Date: Thu, 16 Dec 2021 18:38:02 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-17 15:14:29.000808
• Title: Non-Gaussian Component Analysis via Lattice Basis Reduction
• Title（参考訳）: 格子基底還元による非ガウス成分分析
• Authors: Ilias Diakonikolas and Daniel M. Kane
• Abstract要約: 非ガウス成分分析(NGCA)は分布学習問題である。 我々は,NGCA に対して,$A$ が離散的あるいはほぼ離散的であるような効率的なアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 56.98280399449707
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-Gaussian Component Analysis (NGCA) is the following distribution learning problem: Given i.i.d. samples from a distribution on $\mathbb{R}^d$ that is non-gaussian in a hidden direction $v$ and an independent standard Gaussian in the orthogonal directions, the goal is to approximate the hidden direction $v$. Prior work \cite{DKS17-sq} provided formal evidence for the existence of an information-computation tradeoff for NGCA under appropriate moment-matching conditions on the univariate non-gaussian distribution $A$. The latter result does not apply when the distribution $A$ is discrete. A natural question is whether information-computation tradeoffs persist in this setting. In this paper, we answer this question in the negative by obtaining a sample and computationally efficient algorithm for NGCA in the regime that $A$ is discrete or nearly discrete, in a well-defined technical sense. The key tool leveraged in our algorithm is the LLL method \cite{LLL82} for lattice basis reduction.
• Abstract（参考訳）: 非ガウス成分分析(英: non-gaussian component analysis、ngca)とは、非ガウス成分分析(英: non-gaussian component analysis、非ガウス成分分析、英: non-gaussian component analysis、ngca)とは次の分布学習問題である。 以前の研究 "cite{DKS17-sq}" は、単変量非ガウス分布$A$の適切なモーメントマッチング条件下でのNGCAの情報計算トレードオフの存在に関する公式な証拠を提供した。 後者の結果は、$a$ の分布が離散的であれば適用されない。 自然な質問は、この設定で情報計算のトレードオフが継続するかどうかである。 本稿では, NGCA に対して, A$ が離散的あるいはほぼ離散的であるという条件下でのサンプルと計算効率のよいアルゴリズムを得ることにより, 負の質問に答える。 我々のアルゴリズムで活用される重要なツールは格子基底還元のための LLL メソッド \cite{LLL82} である。

関連論文リスト

• Variable Selection in Convex Piecewise Linear Regression [5.366354612549172]
  本稿では,凸片方向線形回帰における変数選択の解としてスパース勾配を提案する。 亜ガウス雑音下でのSpGDには非漸近局所収束解析が提供される。
  論文  参考訳（メタデータ） (2024-11-04T16:19:09Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。 本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
  論文  参考訳（メタデータ） (2024-10-28T18:19:13Z)
• SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [37.208622097149714]
  すべての$d inmathbb N$に対して、すべての中心部分ガウス分布 $mathcal D$ on $mathbb Rd$, and every even $p inmathbb N$, $d-optimal inmathbb N$, $d-optimal inmathbb N$ が成り立つような普遍定数 $C>0$ が存在することを証明している。 これは、すべてのサブガウス分布がemphS-certifiably subgaussianであることを示す。
  論文  参考訳（メタデータ） (2024-10-28T16:36:58Z)
• Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time? [8.74634652691576]
  反復アルゴリズムのクラスで実現可能な分布のサブセット$mathscrF_m,alpha$について検討する。 統計物理学の非厳密な手法は、一般化されたパリの公式の言葉で$mathscrF_m,alpha$の間接的な特徴づけを与える。
  論文  参考訳（メタデータ） (2024-06-05T05:54:56Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。 この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。 我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
  論文  参考訳（メタデータ） (2023-02-21T17:52:23Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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