論文の概要: Distribution Compression in Near-linear Time
- arxiv url: http://arxiv.org/abs/2111.07941v2
- Date: Wed, 17 Nov 2021 01:49:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-18 11:01:06.176998
- Title: Distribution Compression in Near-linear Time
- Title（参考訳）: 近線形時間における分布圧縮
- Authors: Abhishek Shetty, Raaz Dwivedi, Lester Mackey
- Abstract要約: シンニングアルゴリズムを高速化するシンプルなメタプロデューサであるCompress++を紹介する。
$sqrtn$ポイントを$mathcalO(sqrtlog n/n)$統合エラーで提供し、Monte-Carlo の最大誤差を最大化します。
- 参考スコア（独自算出の注目度）: 27.18971095426405
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In distribution compression, one aims to accurately summarize a probability
distribution $\mathbb{P}$ using a small number of representative points.
Near-optimal thinning procedures achieve this goal by sampling $n$ points from
a Markov chain and identifying $\sqrt{n}$ points with
$\widetilde{\mathcal{O}}(1/\sqrt{n})$ discrepancy to $\mathbb{P}$.
Unfortunately, these algorithms suffer from quadratic or super-quadratic
runtime in the sample size $n$. To address this deficiency, we introduce
Compress++, a simple meta-procedure for speeding up any thinning algorithm
while suffering at most a factor of $4$ in error. When combined with the
quadratic-time kernel halving and kernel thinning algorithms of Dwivedi and
Mackey (2021), Compress++ delivers $\sqrt{n}$ points with
$\mathcal{O}(\sqrt{\log n/n})$ integration error and better-than-Monte-Carlo
maximum mean discrepancy in $\mathcal{O}(n \log^3 n)$ time and $\mathcal{O}(
\sqrt{n} \log^2 n )$ space. Moreover, Compress++ enjoys the same near-linear
runtime given any quadratic-time input and reduces the runtime of
super-quadratic algorithms by a square-root factor. In our benchmarks with
high-dimensional Monte Carlo samples and Markov chains targeting challenging
differential equation posteriors, Compress++ matches or nearly matches the
accuracy of its input algorithm in orders of magnitude less time.
- Abstract（参考訳）: 分布圧縮では、少数の代表点を用いて確率分布$\mathbb{P}$を正確に要約することを目的とする。
準最適シンニング手順は、マルコフ連鎖から$n$ポイントをサンプリングし、$\widetilde{\mathcal{O}}(1/\sqrt{n})$離散性を$\mathbb{P}$とすることで、この目標を達成する。
残念ながら、これらのアルゴリズムはサンプルサイズ$n$で二次的または超二次的な実行に苦しむ。
この欠陥に対処するために、私たちはCompress++を紹介します。これは、任意のスライニングアルゴリズムを高速化するシンプルなメタプロデューサで、エラーの最大4ドルの要因に悩まされています。
Dwivedi と Mackey (2021) の二次時間カーネル半減算アルゴリズムと組み合わせると、Compress++ は $\sqrt{n}$point with $\mathcal{O}(\sqrt{\log n/n})$ Integration error and better-than-Monte-Carlo maximum mean discrepancy in $\mathcal{O}(n \log^3 n)$ time and $\mathcal{O}( \sqrt{n} \log^2 n )$ space を提供する。
さらに、Compress++は2次時間入力が与えられた場合、同じニアリニアランタイムを楽しみ、平方根係数で超2次アルゴリズムの実行時間を短縮する。
高次元モンテカルロサンプルとマルコフ連鎖を用いたベンチマークでは、コンプレックス++はその入力アルゴリズムの精度を桁違いの時間で一致させるか、ほぼ一致させる。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳（メタデータ） (2024-03-07T18:23:51Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文 参考訳（メタデータ） (2023-02-20T18:45:24Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。
PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文 参考訳（メタデータ） (2021-06-11T10:57:00Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。