論文の概要: Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel

• arxiv url: http://arxiv.org/abs/2202.02031v4
• Date: Sun, 30 Apr 2023 22:10:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 20:16:00.523255
• Title: Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel
• Title（参考訳）: テンソル製品の複雑-リアルスケッチとポリノミアルカーネルへの応用
• Authors: Jonas Wacker, Ruben Ohana, Maurizio Filippone
• Abstract要約: p$ベクトルの積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。 本稿では、実乱射影を複素射影に置き換える、よく知られたスケッチの単純な複素対Real (CtR) 修正を提案する。 本手法は,文献の他のランダム化近似と比較して,精度と速度の面で最先端の性能を達成することを示す。
• 参考スコア（独自算出の注目度）: 15.535749953841274
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized sketches of a tensor product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. Commonly used approaches avoid computing the high-dimensional tensor product explicitly, resulting in a suboptimal dependence of $\mathcal{O}(3^p)$ in the embedding dimension. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones, incurring a lower $\mathcal{O}(2^p)$ factor in the embedding dimension. The output of our sketches is real-valued, which renders their downstream use straightforward. In particular, we apply our sketches to $p$-fold self-tensored inputs corresponding to the feature maps of the polynomial kernel. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.
• Abstract（参考訳）: p$ベクトルのテンソル積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。 一般的に用いられるアプローチは、高次元テンソル積を明示的に計算することを避け、埋め込み次元において$\mathcal{O}(3^p)$の最適部分依存をもたらす。 実ランダム射影を複素射影に置き換え、埋め込み次元におけるより低い$\mathcal{o}(2^p)$因子を伴って、よく知られたスケッチの単純な複素対実(ctr)修正を提案する。 私たちのスケッチの出力は実価値があり、下流での使用が簡単になります。 特に、このスケッチを多項式カーネルの特徴写像に対応する$p$-foldの自己拡張入力に適用する。 本手法は,文献の他のランダム化近似と比較して,精度と速度の点で最先端の性能を実現する。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• SketchINR: A First Look into Sketches as Implicit Neural Representations [120.4152701687737]
  暗黙的ニューラルモデルを用いてベクトルスケッチの表現を前進させるSketchINRを提案する。 可変長ベクトルスケッチは、時間とストロークの関数として下層の形状を暗黙的に符号化する固定次元の潜時空間に圧縮される。 初めてSketchINRは、ストロークの数と複雑さの点で、さまざまな抽象化でスケッチを再現する人間の能力をエミュレートする。
  論文  参考訳（メタデータ） (2024-03-14T12:49:29Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs [22.925108493465363]
  平均化によるデータ分布のガウシアン化のためのアルゴリズムフレームワークを提供する。 我々は、ガウス以下のランダムな設計とほとんど区別できないデータスケッチを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2022-06-21T12:16:45Z)
• Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs [2.737640280995564]
  我々はネットワーク埋め込みを用いてテンソルネットワーク構造入力の次元的低減を行う。 このような埋め込みを用いて、入力データを効率的にスケッチするアルゴリズムを提供する。 列車のラウンドリングのための既存のアルゴリズムの最適性を示す。
  論文  参考訳（メタデータ） (2022-05-26T05:27:31Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Hashing embeddings of optimal dimension, with applications to linear least squares [1.2891210250935143]
  スケッチの射影次元$m$で最適である$sgeq 1$のスケッチ行列に対して、サブスペース埋め込み特性を提示する。 これらの結果をLinear Least Squares (LLS) の特殊なケースに適用し,これらの問題に対する汎用ソフトウェアパッケージであるSki-LLSを開発する。
  論文  参考訳（メタデータ） (2021-05-25T10:35:13Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
  本稿では, 高速で, 距離保存可能なバイナリ埋め込みアルゴリズムを提案し, データセット $mathcalTsubseteqmathbbRn$ を立方体 $pm 1m$ のバイナリシーケンスに変換する。 我々の手法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
  論文  参考訳（メタデータ） (2020-10-01T22:41:41Z)

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

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