論文の概要: Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings

• arxiv url: http://arxiv.org/abs/2510.22186v1
• Date: Sat, 25 Oct 2025 06:44:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 15:28:14.902495
• Title: Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings
• Title（参考訳）: Sorting-based Permutation-Invariant Embeddings の定量的境界
• Authors: Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, Radu Balan,
• Abstract要約: ソートに基づく$beta_mathbf A : mathbb Rn times d to mathbb Rn times D$, $mathbf X mapto downarrow(mathbf X mathbf A)$, $downarrow$は行列の列のソートを表す。
• 参考スコア（独自算出の注目度）: 13.307069556587471
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the sorting-based embedding $\beta_{\mathbf A} : \mathbb R^{n \times d} \to \mathbb R^{n \times D}$, $\mathbf X \mapsto {\downarrow}(\mathbf X \mathbf A)$, where $\downarrow$ denotes column wise sorting of matrices. Such embeddings arise in graph deep learning where outputs should be invariant to permutations of graph nodes. Previous work showed that for large enough $D$ and appropriate $\mathbf A$, the mapping $\beta_{\mathbf A}$ is injective, and moreover satisfies a bi-Lipschitz condition. However, two gaps remain: firstly, the optimal size $D$ required for injectivity is not yet known, and secondly, no estimates of the bi-Lipschitz constants of the mapping are known. In this paper, we make substantial progress in addressing both of these gaps. Regarding the first gap, we improve upon the best known upper bounds for the embedding dimension $D$ necessary for injectivity, and also provide a lower bound on the minimal injectivity dimension. Regarding the second gap, we construct matrices $\mathbf A$, so that the bi-Lipschitz distortion of $\beta_{\mathbf A} $ depends quadratically on $n$, and is completely independent of $d$. We also show that the distortion of $\beta_{\mathbf A}$ is necessarily at least in $\Omega(\sqrt{n})$. Finally, we provide similar results for variants of $\beta_{\mathbf A}$ obtained by applying linear projections to reduce the output dimension of $\beta_{\mathbf A}$.
• Abstract（参考訳）: ソートに基づく埋め込み $\beta_{\mathbf A} : \mathbb R^{n \times d} \to \mathbb R^{n \times D}$, $\mathbf X \mapsto {\downarrow}(\mathbf X \mathbf A)$ について検討する。 このような埋め込みは、グラフノードの置換に出力が不変であるべきグラフ深層学習において生じる。 以前の研究は、十分に大きな$D$と適切な$\mathbf A$に対して、写像 $\beta_{\mathbf A}$ は単射であり、さらにビ・リプシッツ条件を満たすことを示した。 しかし、2つのギャップは残る: 第一に、射影性に必要な最適サイズ$D$がまだ分かっておらず、第二に、写像のバイ・リプシッツ定数の見積もりは知られていない。 本稿では,これらのギャップに対処する上で,大きな進歩をもたらす。 最初のギャップについては、注入性に必要な埋め込み次元$D$に対する最もよく知られた上界を改善し、最小の射影性次元に対する下界を与える。 第二のギャップに関して、行列 $\mathbf A$ を構成するので、$\beta_{\mathbf A} $ のバイ・リプシッツ歪みは $n$ に二次的に依存し、$d$ から完全に独立である。 また、$\beta_{\mathbf A}$ の歪みは、少なくとも $\Omega(\sqrt{n})$ の場合である。 最後に、線形射影を適用して得られる$\beta_{\mathbf A}$の変種に対して同様の結果を与え、出力次元を$\beta_{\mathbf A}$とする。

関連論文リスト

• Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model [5.101318208537081]
  線形系を解くための準線形時間アルゴリズムについて研究し、$Sz = b$, ここでは$S$は対角的に支配的な行列である。 任意の$u in [n]$に対して、加算誤差のある$z_u$ of $z*_u$を返します。 また、一致する下界を証明し、$S_max$ に対する線型依存が最適であることを示す。
  論文  参考訳（メタデータ） (2025-09-16T14:13:31Z)
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors [47.927989749887864]
  我々は、$s$sparseベクトルの最低ケース次元削減を超越して研究する。 任意の集合 $X$ of $s$-sparse vectors in $mathbbRO(s2)$ に対して、$mathbbRO(s2)$ への線型写像が存在し、任意の $ell_p$ ノルムにおいて$X$の99%のベクトルのノルムを正確に保存する。 我々は、$f$の非線形性と$の非負性の両方を示す。
  論文  参考訳（メタデータ） (2025-02-27T08:17:47Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)

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

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