論文の概要: 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} である。
関連論文リスト
- Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳(メタデータ) (2023-11-21T18:50:38Z) - 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) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Analysis of One-Hidden-Layer Neural Networks via the Resolvent Method [0.0]
ランダムニューラルネットワークによって動機づけられた確率行列 $M = Y Yast$ と $Y = f(WX)$ を考える。
制限スペクトル分布のStieltjes変換は、いくつかの誤差項まで準自己整合方程式を満たすことを証明している。
さらに、前回の結果を加法バイアス $Y=f(WX+B)$ の場合に拡張し、$B$ は独立なランク1のガウス確率行列である。
論文 参考訳(メタデータ) (2021-05-11T15:17:39Z) - 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) - Convergence and Sample Complexity of SGD in GANs [15.25030172685628]
SGDによるGAN(Generative Adversarial Networks)のトレーニングにおける収束保証を提供する。
我々は,非線形アクティベーション機能を持つ1層ジェネレータネットワークによってモデル化されたターゲット分布の学習を検討する。
この結果は、ReLUを含む幅広い非線形アクティベーション関数 $phi$ に適用され、切り離された統計との接続によって実現される。
論文 参考訳(メタデータ) (2020-12-01T18:50:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。