論文の概要: Hutch++: Optimal Stochastic Trace Estimation

• arxiv url: http://arxiv.org/abs/2010.09649v5
• Date: Fri, 11 Jun 2021 01:33:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 23:26:18.417788
• Title: Hutch++: Optimal Stochastic Trace Estimation
• Title（参考訳）: Hutch++: 最適な確率的トレース推定
• Authors: Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff
• Abstract要約: 我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
• 参考スコア（独自算出の注目度）: 75.45968495410048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of estimating the trace of a matrix $A$ that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a $(1 \pm \epsilon)$ approximation to $tr(A)$ for any positive semidefinite (PSD) $A$ using just $O(1/\epsilon)$ matrix-vector products. This improves on the ubiquitous Hutchinson's estimator, which requires $O(1/\epsilon^2)$ matrix-vector products. Our approach is based on a simple technique for reducing the variance of Hutchinson's estimator using a low-rank approximation step, and is easy to implement and analyze. Moreover, we prove that, up to a logarithmic factor, the complexity of Hutch++ is optimal amongst all matrix-vector query algorithms, even when queries can be chosen adaptively. We show that it significantly outperforms Hutchinson's method in experiments. While our theory mainly requires $A$ to be positive semidefinite, we provide generalized guarantees for general square matrices, and show empirical gains in such applications.
• Abstract（参考訳）: 行列ベクトル乗算を通してのみアクセス可能な行列$A$のトレースを推定する問題について検討する。 我々は,任意の正半定値(PSD)$A$に対して,たったの$O(1/\epsilon)$行列ベクトル積を用いて,$(1 \pm \epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムHutch++を導入する。 これによりユビキタスハッチンソンの推定値が向上し、O(1/\epsilon^2)$行列ベクトル積が要求される。 本手法は,hatchinsonの推定値のばらつきを低位近似ステップを用いて低減する簡単な手法に基づいており,実装および解析が容易である。 さらに, 対数係数において, Hutch++の複雑性は, クエリを適応的に選択しても, すべての行列ベクトルクエリアルゴリズムにおいて最適であることを示す。 実験ではハッチンソン法を著しく上回る結果を得た。 我々の理論は正の半定義であるために主に$a$を必要とするが、一般的な正方行列に対する一般化された保証を提供し、そのような応用において経験的成果を示す。

関連論文リスト

• Optimal Quantization for Matrix Multiplication [35.007966885532724]
  我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• 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)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat\'ern Correlations [23.560067934682294]
  マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。 提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
  論文  参考訳（メタデータ） (2022-03-07T03:30:35Z)
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy [33.72108955447222]
  最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。 そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。 我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
  論文  参考訳（メタデータ） (2021-12-27T14:59:52Z)
• Efficient Matrix-Free Approximations of Second-Order Information, with Applications to Pruning and Optimization [16.96639526117016]
  Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。 これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
  論文  参考訳（メタデータ） (2021-07-07T17:01:34Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)

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

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