論文の概要: Algorithmic Gaussianization through Sketching: Converting Data into
Sub-gaussian Random Designs
- arxiv url: http://arxiv.org/abs/2206.10291v2
- Date: Thu, 27 Jul 2023 17:48:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-28 20:48:25.448530
- Title: Algorithmic Gaussianization through Sketching: Converting Data into
Sub-gaussian Random Designs
- Title（参考訳）: スケッチによるアルゴリズム的ガウス化:データをサブガウス的ランダムデザインに変換する
- Authors: Micha{\l} Derezi\'nski
- Abstract要約: 平均化によるデータ分布のガウシアン化のためのアルゴリズムフレームワークを提供する。
我々は、ガウス以下のランダムな設計とほとんど区別できないデータスケッチを効率的に構築できることを示す。
- 参考スコア（独自算出の注目度）: 22.925108493465363
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithmic Gaussianization is a phenomenon that can arise when using
randomized sketching or sampling methods to produce smaller representations of
large datasets: For certain tasks, these sketched representations have been
observed to exhibit many robust performance characteristics that are known to
occur when a data sample comes from a sub-gaussian random design, which is a
powerful statistical model of data distributions. However, this phenomenon has
only been studied for specific tasks and metrics, or by relying on
computationally expensive methods. We address this by providing an algorithmic
framework for gaussianizing data distributions via averaging, proving that it
is possible to efficiently construct data sketches that are nearly
indistinguishable (in terms of total variation distance) from sub-gaussian
random designs. In particular, relying on a recently introduced sketching
technique called Leverage Score Sparsified (LESS) embeddings, we show that one
can construct an $n\times d$ sketch of an $N\times d$ matrix $A$, where $n\ll
N$, that is nearly indistinguishable from a sub-gaussian design, in time
$O(\text{nnz}(A)\log N + nd^2)$, where $\text{nnz}(A)$ is the number of
non-zero entries in $A$. As a consequence, strong statistical guarantees and
precise asymptotics available for the estimators produced from sub-gaussian
designs (e.g., for least squares and Lasso regression, covariance estimation,
low-rank approximation, etc.) can be straightforwardly adapted to our sketching
framework. We illustrate this with a new approximation guarantee for sketched
least squares, among other examples.
- Abstract（参考訳）: アルゴリズムガウス化(英: Algorithmic Gaussianization)は、大規模なデータセットのより小さな表現を生成するためにランダム化されたスケッチ法やサンプリング法を用いて発生する現象である。
しかし、この現象は特定のタスクやメトリクス、あるいは計算コストの高い手法に依存することでのみ研究されてきた。
平均化によってデータ分布をガウス化するためのアルゴリズムフレームワークを提供し、サブガウスのランダム設計からほぼ区別できない(全変動距離の観点で)データスケッチを効率的に構築できることを証明した。
特に、最近紹介されたreferation score sparsified (less) embeddedsと呼ばれるスケッチ技術に依存すると、$n\times d$ sketch of an $n\times d$ matrix $a$, where $n\ll n$, is almost indistinguishable with a sub-gaussian design, in time $o(\text{nnz}(a)\log n + nd^2)$, where $\text{nnz}(a)$ is the number of non-zero entry in $a$ である。
結果として、ガウス以下の設計(例えば、最小二乗とラッソ回帰、共分散推定、低ランク近似など)から得られる推定値に対して、強い統計的保証と正確な漸近が、スケッチフレームワークに容易に適応できる。
我々はこれを、スケッチされた最小二乗に対する新しい近似保証で説明する。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Sparse Gaussian Graphical Models with Discrete Optimization:
Computational and Statistical Perspectives [8.403841349300103]
本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。
擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。
実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
論文 参考訳（メタデータ） (2023-07-18T15:49:02Z) - Sketched Gaussian Model Linear Discriminant Analysis via the Randomized
Kaczmarz Method [7.593861427248019]
超大規模データに対する二進法クラスガウスモデル線形判別分析(LDA)に対する反復的ランダム化手法であるスケッチ付き線形判別分析を提案する。
最小二乗の定式化を利用して、降下勾配の枠組みを動員する。
一定回数の反復で新しいデータに対するスケッチ付き予測を収束保証する。
論文 参考訳（メタデータ） (2022-11-10T18:29:36Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - Convergence for score-based generative modeling with polynomial
complexity [9.953088581242845]
我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。
以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。
予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
論文 参考訳（メタデータ） (2022-06-13T14:57:35Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - Estimating Stochastic Linear Combination of Non-linear Regressions
Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。
私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文 参考訳（メタデータ） (2020-10-19T07:15:38Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。