論文の概要: Beyond Moments: Robustly Learning Affine Transformations with
Asymptotically Optimal Error
- arxiv url: http://arxiv.org/abs/2302.12289v1
- Date: Thu, 23 Feb 2023 19:13:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 15:38:34.361596
- Title: Beyond Moments: Robustly Learning Affine Transformations with
Asymptotically Optimal Error
- Title（参考訳）: Beyond Moments: 漸近的に最適なエラーでアフィン変換をロバストに学習する
- Authors: He Jia, Pravesh K . Kothari, Santosh S. Vempala
- Abstract要約: サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。
本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
- 参考スコア（独自算出の注目度）: 8.615625517708324
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a polynomial-time algorithm for robustly learning an unknown
affine transformation of the standard hypercube from samples, an important and
well-studied setting for independent component analysis (ICA). Specifically,
given an $\epsilon$-corrupted sample from a distribution $D$ obtained by
applying an unknown affine transformation $x \rightarrow Ax+s$ to the uniform
distribution on a $d$-dimensional hypercube $[-1,1]^d$, our algorithm
constructs $\hat{A}, \hat{s}$ such that the total variation distance of the
distribution $\hat{D}$ from $D$ is $O(\epsilon)$ using poly$(d)$ time and
samples. Total variation distance is the information-theoretically strongest
possible notion of distance in our setting and our recovery guarantees in this
distance are optimal up to the absolute constant factor multiplying $\epsilon$.
In particular, if the columns of $A$ are normalized to be unit length, our
total variation distance guarantee implies a bound on the sum of the $\ell_2$
distances between the column vectors of $A$ and $A'$, $\sum_{i =1}^d
\|a_i-\hat{a}_i\|_2 = O(\epsilon)$. In contrast, the strongest known prior
results only yield a $\epsilon^{O(1)}$ (relative) bound on the distance between
individual $a_i$'s and their estimates and translate into an $O(d\epsilon)$
bound on the total variation distance. Our key innovation is a new approach to
ICA (even to outlier-free ICA) that circumvents the difficulties in the
classical method of moments and instead relies on a new geometric certificate
of correctness of an affine transformation. Our algorithm is based on a new
method that iteratively improves an estimate of the unknown affine
transformation whenever the requirements of the certificate are not met.
- Abstract（参考訳）: 本稿では,標準ハイパーキューブの未知のアフィン変換をロバストに学習するための多項式時間アルゴリズムを提案する。
具体的には、未知のアフィン変換 $x \rightarrow Ax+s$ を $d$-dimensional hypercube $[-1,1]^d$ 上の一様分布に適用して得た分布 $D$ から得られた$\epsilon$ のサンプルを与えられた場合、我々のアルゴリズムは、分布の総変動距離が$D$ から$D$ までの$\hat{D}$ がpoly$(d)$時間とサンプルを用いて$O(\epsilon)$ となるように$\hat{A}, \hat{s}$ を構築する。
全変動距離は、我々の設定における情報理論上最も強い距離の概念であり、この距離における我々の回復保証は、$\epsilon$を乗じる絶対定数まで最適である。
特に、$a$ の列が単位長に正規化されている場合、全変動距離保証は、$a$ と $a'$、$\sum_{i =1}^d \|a_i-\hat{a}_i\|_2 = o(\epsilon)$ の列ベクトル間の$\ell_2$ 距離の和の境界を意味する。
対照的に、最も強い既知の先行結果は、個々の$a_i$sとそれらの推定値の間の距離で有界な$\epsilon^{O(1)}$(相対)しか得られず、全変動距離で有界な$O(d\epsilon)$に変換される。
我々の重要な革新はICAに対する新しいアプローチであり、これは古典的なモーメントの方法の難しさを回避し、代わりにアフィン変換の正しさを示す新しい幾何学的証明に依存する。
本アルゴリズムは,証明書の要件が満たされない場合に未知のアフィン変換の推定を反復的に改善する新しい手法に基づいている。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - List-Decodable Covariance Estimation [1.9290392443571387]
共分散推定アルゴリズムを初めて提案する。
この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
論文 参考訳（メタデータ） (2022-06-22T09:38:06Z) - Adversarially Robust Learning with Tolerance [8.658596218544774]
本稿では,距離摂動集合に対する寛容逆PAC学習の問題点について考察する。
自然摂動・平滑アルゴリズムの変種であるPACは、$gamma$-tolerant adversarial setにおいて、VC次元が$v$の任意の仮説クラス$mathcalH$を学習する。
また,2次元に線形依存したサンプル境界を求める学習手法を提案する。
論文 参考訳（メタデータ） (2022-03-02T03:50:16Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - 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) - Efficient Distance Approximation for Structured High-Dimensional
Distributions via Learning [31.552581550603005]
構成された高次元分布のいくつかのクラスに対する効率的な距離近似アルゴリズムを設計する。
我々の結果は、これらのよく研究された問題に対する最初の効率的な距離近似アルゴリズムである。
論文 参考訳（メタデータ） (2020-02-13T07:42:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。