論文の概要: Improving TensorSketch Using Complex Random Variables
- arxiv url: http://arxiv.org/abs/2608.10523v1
- Date: Tue, 11 Aug 2026 05:59:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-12 19:14:45.921881
- Title: Improving TensorSketch Using Complex Random Variables
- Title（参考訳）: 複雑なランダム変数を用いたテンソルスケッチの改善
- Abstract要約: textttTensorSketchciteppham2013fast,kar2012randomは、高次元カーネルのための効率的なスケッチアルゴリズムを提供する。
citekar2012random は計算コスト$O(pDd)$の密度の Johnson-Lindenstrauss (JL) 型射影を使用する。
我々は、textttTensorSketchciteppham2013fast の単純な変種を導入し、同じ分散境界の ascitepmlr-v206-wacker23a を実現する。
- 参考スコア（独自算出の注目度）: 6.602518123025796
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: \texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost $O(pDd)$, where $D$ denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}~\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$. However, the variance of both estimators grows exponentially with the polynomial degree $p$, scaling as $3^{p}/D$. Recent work by~\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to $2^{p}/D$ for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost $O(pDd)$ and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of \texttt{TensorSketch}~\citep{pham2013fast} that achieves the same variance bound as~\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.
- Abstract（参考訳）: \texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} は高次元多項式カーネルに対して効率的なスケッチアルゴリズムを提供する。
\cite{kar2012random} は、計算コスト$O(pDd)$で密度の高い Johnson-Lindenstrauss (JL) 型プロジェクションを使用し、$D$ はスケッチ次元を表すが、~\cite{pham2013fast} はスパース \texttt{CountSketch}~\citep{count_sketch} アルゴリズムを拡張し、実行時間$O\big(p(\nnz{\vec{x}} + D \log D)\big)$ で高次元のスパース入力に対するより高速なアルゴリズムを生成する。
しかし、両方の推定子の分散は多項式次数$p$で指数関数的に増加し、$3^{p}/D$にスケールする。
~\cite{pmlr-v206-wacker23a} による最近の研究は、複素数値分布を用いることで、~\cite{kar2012random} のアプローチに対して、この依存を 2^{p}/D$ に還元することを示した。
しかし、それらの手法は計算コスト$O(pDd)$の密度の高いJL型射影に依存しており、~\cite{pham2013fast} のアルゴリズムには拡張されない。
本研究では,入力スパーシティ実行時間の利点を保ちながら,同じ分散束を~\cite{pmlr-v206-wacker23a} として達成する,‘texttt{TensorSketch}~\citep{pham2013fast} の単純な変種を導入する。
合成および実世界のデータセットに対する支援実験により,本研究の結果を検証した。
関連論文リスト
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。
このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
論文 参考訳（メタデータ） (2025-10-09T09:47:40Z) - Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。
2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文 参考訳（メタデータ） (2024-10-31T13:51:59Z) - Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization [28.497079108813924]
データセットのサイズが$widetildeOmega(sqrtd/alphabeta3+d/epsilonalphabeta2)$である限り、$(alpha,beta)$-stationaryポイントを返すシングルパス$(epsilon,delta)$-DPアルゴリズムを提供する。
次に、サンプルの複雑さを$widetildeOmegaleft(d/beta2+d3/4/epsilonalphaに改善するマルチパス時間アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-08T10:15:49Z) - Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。
我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
論文 参考訳（メタデータ） (2024-07-27T08:57:04Z) - Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文 参考訳（メタデータ） (2023-02-20T18:45:24Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Private High-Dimensional Hypothesis Testing [4.133655523622441]
我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。
具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
論文 参考訳（メタデータ） (2022-03-03T06:25:48Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。