論文の概要: Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity

• arxiv url: http://arxiv.org/abs/2411.08773v1
• Date: Wed, 13 Nov 2024 16:58:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-14 16:11:40.845568
• Title: Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
• Title（参考訳）: ほぼ最適間隔を有する最適部分空間埋め込み
• Authors: Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong,
• Abstract要約: 曖昧な部分空間の埋め込みは、ランダムな$mtimes n$ matrix $Pi$で、その部分空間内のすべてのベクトルのノルムを1pmepsilon$ factorで保存する。 最適次元が $m=Theta(d/epsilon2)$ で、最適間隔が $tilde O (1/epsilon)$ のとき、非零エントリは $Pi$ である。
• 参考スコア（独自算出の注目度）: 3.9657575162895196
• License:
• Abstract: An oblivious subspace embedding is a random $m\times n$ matrix $\Pi$ such that, for any $d$-dimensional subspace, with high probability $\Pi$ preserves the norms of all vectors in that subspace within a $1\pm\epsilon$ factor. In this work, we give an oblivious subspace embedding with the optimal dimension $m=\Theta(d/\epsilon^2)$ that has a near-optimal sparsity of $\tilde O(1/\epsilon)$ non-zero entries per column of $\Pi$. This is the first result to nearly match the conjecture of Nelson and Nguyen [FOCS 2013] in terms of the best sparsity attainable by an optimal oblivious subspace embedding, improving on a prior bound of $\tilde O(1/\epsilon^6)$ non-zeros per column [Chenakkod et al., STOC 2024]. We further extend our approach to the non-oblivious setting, proposing a new family of Leverage Score Sparsified embeddings with Independent Columns, which yield faster runtimes for matrix approximation and regression tasks. In our analysis, we develop a new method which uses a decoupling argument together with the cumulant method for bounding the edge universality error of isotropic random matrices. To achieve near-optimal sparsity, we combine this general-purpose approach with new traces inequalities that leverage the specific structure of our subspace embedding construction.
• Abstract（参考訳）: 曖昧な部分空間の埋め込みは、ランダムな$m\times n$ matrix $\Pi$ であり、任意の$d$-次元部分空間に対して、高い確率$\Pi$ は、その部分空間内のすべてのベクトルのノルムを 1\pm\epsilon$ factor で保存する。 本研究では、最適次元 $m=\Theta(d/\epsilon^2)$ の半空間を埋め込むが、これは、$\tilde O(1/\epsilon)$ $\Pi$ のカラムあたりの 0 でないエントリがほぼ最適である。 これはネルソンとニュイエン(FOCS 2013)の予想にほぼ一致する最初の結果であり、最適な半空間の埋め込みによって達成できる最高の空間は、以前の境界である$\tilde O(1/\epsilon^6)$ non-zeros per column [Chenakkod et al , STOC 2024] で改善される。 我々はさらに、非公開設定へのアプローチを拡張し、行列近似と回帰タスクのより高速なランタイムを生成する独立カラムによるLevanage Score Sparsified埋め込みの新たなファミリーを提案する。 そこで本研究では,等方的確率行列のエッジ普遍性誤差を有界化するための累積法とともに,デカップリング引数を用いた新しい手法を開発した。 ほぼ最適間隔を達成するために、我々はこの汎用アプローチと、我々の部分空間埋め込み構造の特定の構造を利用する新しいトレース不等式を組み合わせる。

関連論文リスト

• 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)
• Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
  我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。 我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
  論文  参考訳（メタデータ） (2024-07-18T15:58:04Z)
• Optimal Matrix Sketching over Sliding Windows [38.09464189820894]
  マトリックススケッチは、mathbbRNtimes d$で行列 $boldsymbolAを近似することを目的としており、長さ$N$のベクトルストリームとmathbbRelltimes d, ell ll N$で小さなスケッチマトリックス $boldsymbolBで構成されている。 Oleftfracdvarepsilonright)$ space bound for matrix sketching over row-normalized, sequence-based sliding windows。
  論文  参考訳（メタデータ） (2024-05-13T14:38:35Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
  ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。 mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。 これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
  論文  参考訳（メタデータ） (2023-11-17T18:01:58Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。 このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
  論文  参考訳（メタデータ） (2023-03-16T15:24:29Z)
• Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
  線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。 特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。 提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
  論文  参考訳（メタデータ） (2020-11-02T14:59:39Z)
• Deep Learning Meets Projective Clustering [66.726500395069]
  NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。 計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
  論文  参考訳（メタデータ） (2020-10-08T22:47:48Z)
• Subspace approximation with outliers [6.186553186139257]
  本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。 我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
  論文  参考訳（メタデータ） (2020-06-30T07:22:33Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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