論文の概要: Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity

• arxiv url: http://arxiv.org/abs/2607.20393v2
• Date: Sat, 25 Jul 2026 05:20:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 12:52:43.707859
• Title: Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
• Title（参考訳）: 最大内積類似性の単ベクトル埋め込みに対する近似次元下界
• Abstract要約: シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
• 参考スコア（独自算出の注目度）: 75.14269295861845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity, whereas single-vector embeddings use ordinary inner products. For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP). In our setting, MUVERA gives dimension $m^{O(1/ε^2)}$ [DHJ+24], whereas the previous lower bound $(ε^2m)^{Ω(1/ε)}$ [Jay26] left a gap between $1/ε$ and $1/ε^2$ in the exponent of $m$. We nearly close this gap. For every fixed $δ\in(0,1)$, there are constants $A_δ,c_δ>0$ such that, for all sufficiently small $ε>0$ and every $m\ge(1/ε)^{A_δ}$, there exist unit query vectors and document point clouds of at most $m$ unit vectors for which every single-vector approximation of all pairwise MAX-IP values to additive error $ε$ has dimension \[ D \ge m^{c_δ/ε^{2-2δ}}. \] This holds even for fully data-dependent representations chosen after seeing the dataset. It also applies to Chamfer because all queries are singletons. Since $δ$ can be arbitrarily small, the exponent approaches the $O(1/ε^2)$ dependence of the upper bound. The proof combines Sherstov's pattern matrix method with polynomial-size, constant-width DNF formulas computing functions of approximate degree $Ω(k^{1-δ})$. Uniform-width padding and a block encoding create an $Ω(ε)$ gap. A dummy coordinate then equalizes all false inputs, yielding a unit-sphere MAX-IP matrix that is an exact two-valued affine image of the DNF pattern matrix with gap at least $8ε$. This allows the approximate-rank bound to apply. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.
• Abstract（参考訳）: マルチベクター埋め込みは、ポイントクラウド単位でアイテムを表現し、クエリとドキュメントポイントクラウドをChamferの類似性を使って比較する。 シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 我々の設定では、MUVERA は次元 $m^{O(1/ε^2)}$ [DHJ+24] を与えるが、以前の下界 $(ε^2m)^{Ω(1/ε)}$ [Jay26] は$m$の指数で $1/ε$ と $1/ε^2$ の差を残している。 私たちはこのギャップをほぼ埋めた。 すべての固定された$δ\in(0,1)$に対して、すべての定数 $A_δ,c_δ>0$ が存在し、十分小さい$ε>0$ とすべての $m\ge(1/ε)^{A_δ}$ に対して、最小の$m$単位ベクトルの単位クエリベクトルとドキュメントポイントクラウドが存在し、すべてのペアワイズMAX-IP値を加法誤差 $ε$ は次元 \[D \ge m^{c_δ/ε^{2-2δ}} を持つ。 これは、データセットを見た後に選択された完全なデータ依存表現でさえ保持します。 すべてのクエリがシングルトンであるため、Chamferにも適用される。 δ$は任意に小さくできるので、指数は上界の$O(1/ε^2)$依存に近づく。 この証明はシェルストフのパターン行列法と多項式サイズで定数幅のDNF公式を組み合わせることで、近似次数$Ω(k^{1-δ})$の計算関数を計算する。 均一幅のパディングとブロック符号化は$Ω(ε)$ギャップを生成する。 ダミー座標は、すべての偽入力を等しくし、DNFパターン行列の正確な2値アフィン像である単位球MAX-IP行列を少なくとも8ε$で生成する。 これにより、近似ランク境界が適用できる。 この証明は、Google社内で開発された完全に自動化されたジェミニベースのエージェントシステムを用いて最初に得られた。 著者らは証明を検証し、提示の明確さのために編集した。

関連論文リスト

• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$を符号、空間性、正方性制限なしで証明する。 純粋な$varepsilon$-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差の両方が$(varepsilon-2log3(n+1))$である。
  論文  参考訳（メタデータ） (2026-07-30T14:41:34Z)
• Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings [5.90432887297327]
  MV埋め込みは1つのベクトル埋め込みで概略表現できない類似性を表現できることを示す。 固定表現サイズでは、複数ベクトル埋め込みは1つのベクトル埋め込みでほぼ表現できない類似性を表現することができる。
  論文  参考訳（メタデータ） (2026-06-22T15:22:05Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。 我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
  論文  参考訳（メタデータ） (2026-05-22T12:22:20Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• On the Intrinsic Dimensions of Data in Kernel Learning [1.675218291152252]
  ラプラスカーネルのようなカーネルの場合、実効次元$d_K$はミンコフスキー次元$d_$よりもかなり小さく、正則領域で証明可能であることを示す。 以上の結果から,Laplaceカーネルのようなカーネルの場合,実効次元$d_K$は,通常のドメインに有するMinkowski次元$d_$よりも著しく小さいことが分かる。
  論文  参考訳（メタデータ） (2026-01-22T17:32:24Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• Sparsifying Suprema of Gaussian Processes [3.898355636811022]
  中心ガウス過程の上限に対して次元非依存的なスパーシフィケーション結果を与える。 任意のノルム$nu(x)$ on $mathbbRn$が与えられたとき、$x$から$O_varepsilon(1)$方向への投影のみに依存する別のノルム$psi(x)$が存在することを示す。
  論文  参考訳（メタデータ） (2024-11-22T01:43:58Z)
• 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)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。 1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
  論文  参考訳（メタデータ） (2024-06-04T15:50:42Z)
• 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)
• Dimension-Independent Kernel ε-Covers [8.234735564035567]
  カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。 カーネルレンジ空間に対して$varepsilon$-coverという概念を導入する。
  論文  参考訳（メタデータ） (2023-06-28T19:19:33Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• A closer look at the approximation capabilities of neural networks [6.09170287691728]
  1つの隠れた層を持つフィードフォワードニューラルネットワークは、任意の連続関数$f$を任意の近似しきい値$varepsilon$に近似することができる。 この均一な近似特性は、重量に強い条件が課せられているにもかかわらず、依然として維持されていることを示す。
  論文  参考訳（メタデータ） (2020-02-16T04:58:43Z)

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

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