論文の概要: Uniform Approximations for Randomized Hadamard Transforms with
Applications
- arxiv url: http://arxiv.org/abs/2203.01599v1
- Date: Thu, 3 Mar 2022 09:56:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-04 15:23:41.135127
- Title: Uniform Approximations for Randomized Hadamard Transforms with
Applications
- Title（参考訳）: ランダム化アダマール変換の一様近似とその応用
- Authors: Yeshwanth Cherapanamjeri, Jelani Nelson
- Abstract要約: RHT(Randomized Hadamard Transforms)は、高密度な非構造的ランダム行列の計算効率の代替として登場した。
我々は、カーネル近似と距離推定という高次元状態における2つの応用の保証を改善するために、我々の不等式を利用する。
- 参考スコア（独自算出の注目度）: 8.985261743452986
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Randomized Hadamard Transforms (RHTs) have emerged as a computationally
efficient alternative to the use of dense unstructured random matrices across a
range of domains in computer science and machine learning. For several
applications such as dimensionality reduction and compressed sensing, the
theoretical guarantees for methods based on RHTs are comparable to approaches
using dense random matrices with i.i.d.\ entries. However, several such
applications are in the low-dimensional regime where the number of rows sampled
from the matrix is rather small. Prior arguments are not applicable to the
high-dimensional regime often found in machine learning applications like
kernel approximation. Given an ensemble of RHTs with Gaussian diagonals,
$\{M^i\}_{i = 1}^m$, and any $1$-Lipschitz function, $f: \mathbb{R} \to
\mathbb{R}$, we prove that the average of $f$ over the entries of $\{M^i v\}_{i
= 1}^m$ converges to its expectation uniformly over $\| v \| \leq 1$ at a rate
comparable to that obtained from using truly Gaussian matrices. We use our
inequality to then derive improved guarantees for two applications in the
high-dimensional regime: 1) kernel approximation and 2) distance estimation.
For kernel approximation, we prove the first \emph{uniform} approximation
guarantees for random features constructed through RHTs lending theoretical
justification to their empirical success while for distance estimation, our
convergence result implies data structures with improved runtime guarantees
over previous work by the authors. We believe our general inequality is likely
to find use in other applications.
- Abstract（参考訳）: RHT (Randomized Hadamard Transforms) は、コンピュータサイエンスや機械学習において、様々な領域にまたがる高密度な非構造化ランダム行列の使用に対する、計算的に効率的な代替手段として登場した。
次元減少や圧縮センシングといったいくつかの応用において、RHTsに基づく手法の理論的保証は、i.d.\エントリを持つ密度ランダム行列を用いたアプローチに匹敵する。
しかし、そのような応用のいくつかは、行列からサンプリングされた行数がかなり小さい低次元の領域にある。
事前の議論は、カーネル近似のような機械学習アプリケーションでよく見られる高次元の規則には適用できない。
ガウス対角線を持つ RHT のアンサンブルが与えられたとき、$\{M^i\}_{i = 1}^m$ および任意の$$-Lipschitz関数、$f: \mathbb{R} \to \mathbb{R}$ は、$\{M^i v\}_{i = 1}^m$ の平均が真ガウス行列を用いて得られるものと同等の速度で、その期待値に一様収束することを証明する。
我々は、高次元状態における2つの応用に対する改善された保証を導出するために、不等式を使用する。
1)カーネル近似と
2) 距離推定。
カーネル近似では、RHTによって構築されたランダムな特徴に対する最初の \emph{uniform} 近似保証を証明し、実験的な成功に理論的に正当性を与える一方で、距離推定については、著者による以前の研究よりも実行時の保証が改善されたデータ構造を示唆する。
私たちの一般的な不平等は他のアプリケーションで使われる可能性が高いと信じています。
関連論文リスト
- SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [37.208622097149714]
すべての$d inmathbb N$に対して、すべての中心部分ガウス分布 $mathcal D$ on $mathbb Rd$, and every even $p inmathbb N$, $d-optimal inmathbb N$, $d-optimal inmathbb N$ が成り立つような普遍定数 $C>0$ が存在することを証明している。
これは、すべてのサブガウス分布がemphS-certifiably subgaussianであることを示す。
論文 参考訳（メタデータ） (2024-10-28T16:36:58Z) - Universality of kernel random matrices and kernel regression in the quadratic regime [18.51014786894174]
本研究では、カーネルカーネルの回帰の研究を二次構造にまで拡張する。
我々は、元のカーネルランダム行列と二次カーネルランダム行列の差分に限定した作用素ノルム近似を確立する。
我々は、$n/d2$が非ゼロ定数に収束する二次状態におけるKRRの正確なトレーニングと一般化誤差を特徴づける。
論文 参考訳（メタデータ） (2024-08-02T07:29:49Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Low-complexity subspace-descent over symmetric positive definite
manifold [9.346050098365648]
対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。
提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
論文 参考訳（メタデータ） (2023-05-03T11:11:46Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
論文 参考訳（メタデータ） (2022-05-16T02:24:52Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。
私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
論文 参考訳（メタデータ） (2020-06-12T17:25:39Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。