論文の概要: Optimal Randomized Approximations for Matrix based Renyi's Entropy
- arxiv url: http://arxiv.org/abs/2205.07426v1
- Date: Mon, 16 May 2022 02:24:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-17 14:22:40.800478
- Title: Optimal Randomized Approximations for Matrix based Renyi's Entropy
- Title（参考訳）: 行列に基づくRenyiエントロピーの最適ランダム化近似
- Authors: Yuxin Dong and Tieliang Gong and Shujian Yu and Chen Li
- Abstract要約: 整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
- 参考スコア（独自算出の注目度）: 16.651155375441796
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Matrix-based Renyi's entropy enables us to directly measure information
quantities from given data without the costly probability density estimation of
underlying distributions, thus has been widely adopted in numerous statistical
learning and inference tasks. However, exactly calculating this new information
quantity requires access to the eigenspectrum of a semi-positive definite (SPD)
matrix $A$ which grows linearly with the number of samples $n$, resulting in a
$O(n^3)$ time complexity that is prohibitive for large-scale applications. To
address this issue, this paper takes advantage of stochastic trace
approximations for matrix-based Renyi's entropy with arbitrary $\alpha \in R^+$
orders, lowering the complexity by converting the entropy approximation to a
matrix-vector multiplication problem. Specifically, we develop random
approximations for integer order $\alpha$ cases and polynomial series
approximations (Taylor and Chebyshev) for non-integer $\alpha$ cases, leading
to a $O(n^2sm)$ overall time complexity, where $s,m \ll n$ denote the number of
vector queries and the polynomial order respectively. We theoretically
establish statistical guarantees for all approximation algorithms and give
explicit order of s and m with respect to the approximation error
$\varepsilon$, showing optimal convergence rate for both parameters up to a
logarithmic factor. Large-scale simulations and real-world applications
validate the effectiveness of the developed approximations, demonstrating
remarkable speedup with negligible loss in accuracy.
- Abstract（参考訳）: 行列に基づくRenyiのエントロピーにより、基礎となる分布の確率密度を見積もることなく、与えられたデータから直接情報量を測定することができ、多くの統計的学習や推論タスクで広く採用されている。
しかし、この新たな情報量を正確に計算するには、半正定値行列(SPD)$A$の固有スペクトルへのアクセスが必要である。
そこで本稿では,任意の$\alpha \in r^+$ 順序を持つ行列系レーニーのエントロピーに対する確率的トレース近似を応用し,エントロピー近似を行列ベクトル乗算問題に変換することで複雑性を低減した。
具体的には、整数順序 $\alpha$case と多項式級数近似 (taylor と chebyshev) に対するランダム近似 (taylor と chebyshev) を非整数級数 $\alpha$case に対して開発し、全体の時間複雑性は $o(n^2sm)$ となり、ここで $s,m \ll n$ はそれぞれベクトルクエリ数と多項式次数を表す。
理論的には、全ての近似アルゴリズムに対する統計的保証を確立し、近似誤差$\varepsilon$に対してsとmの明示的な順序を与え、両パラメータの最適収束率を対数係数まで示す。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証し、無視できない精度の損失を伴う顕著なスピードアップを示す。
関連論文リスト
- Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41: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) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - 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) - Low-complexity subspace-descent over symmetric positive definite
manifold [9.346050098365648]
対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。
提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
論文 参考訳（メタデータ） (2023-05-03T11:11:46Z) - The Hypervolume Indicator Hessian Matrix: Analytical Expression,
Computational Time Complexity, and Sparsity [4.523133864190258]
本稿では,$d$次元決定空間における$n$点の(固定サイズ)集合からスカラー超体積指標値への写像のヘッセン行列の解析式を確立する。
ヘッセン行列はニュートン・ラフソン最適化法のような二階法において重要な役割を担い、局所最適集合の検証に使用できる。
論文 参考訳（メタデータ） (2022-11-08T11:24:18Z) - Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected
Error [0.3997680012976965]
目標は、最悪の予測エラーを最小限に抑える推定器を設計することである。
Chen, Valiant および Valiant は、データ値が $ell_infty$-normalized の場合、平均の推定値を計算する時間アルゴリズムが存在することを示した。
本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-12-27T18:47:25Z) - Computationally Efficient Approximations for Matrix-based Renyi's
Entropy [33.72108955447222]
最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。
そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。
我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
論文 参考訳（メタデータ） (2021-12-27T14:59:52Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。