論文の概要: Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
- arxiv url: http://arxiv.org/abs/2605.03346v1
- Date: Tue, 05 May 2026 04:05:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-06 19:35:43.758452
- Title: Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
- Title（参考訳）: 次元ミスマッチによる埋め込み型表現における確率的精度の低下
- Authors: Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo,
- Abstract要約: 我々は、鋭い次元精度のトレードオフを証明し、基本的な情報理論の限界を特定する。
埋め込み次元が$d$でなければ、精度は突然崩壊する。
- 参考スコア（独自算出の注目度）: 5.144873004876024
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Embedding-based representations in Euclidean space $\mathbb{R}^d$ are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that faithfully captures data relations. In this work, we prove sharp dimension--accuracy tradeoffs and identify a fundamental information-theoretic limitation: unless the embedding dimension $d$ is chosen close to the ground-truth dimension $D$, accuracy undergoes a sudden collapse. Our main result shows that this phenomenon arises even in standard contrastive learning settings, where supervision is limited to a set of $m$ anchor--positive--negative triplets $(i,j,k)$ encoding distance comparisons $\mathrm{dist}(i,j) < \mathrm{dist}(i,k)$. Specifically, given triplets realizable by an unknown ground-truth embedding in $D$ dimensions, we prove that there exists constant $c < 1$, such that \emph{every embedding of dimension at most $cD$ violates half of the triplets}, yielding accuracy as low as a trivial one-dimensional solution that ignores the input. We complement our information-theoretic bounds with strong computational hardness results: under the Unique Games Conjecture, even if the given triplets are nearly realizable in $D=1$ dimension, no polynomial-time algorithm -- \textit{regardless of its dimension} -- can achieve accuracy above the trivial $50\%$ baseline.
- Abstract（参考訳）: ユークリッド空間の埋め込みベースの表現 $\mathbb{R}^d$ は、データ関係を忠実にキャプチャする \emph{smallest dimension} を使うことが主な目的である現代の機械学習の基盤である。
本研究では, 急激な次元精度トレードオフを証明し, 基本情報理論の限界を同定する: 埋め込み次元$d$が, 接地トラス次元$D$の近傍で選択されない限り, 精度は突然崩壊する。
この現象は,標準的なコントラスト学習環境においても発生し,アンカー正負三重項$(i,j,k)$エンコーディング距離比較が$\mathrm{dist}(i,j) < \mathrm{dist}(i,k)$に制限されている。
具体的には、D$次元に未知の接地真実を埋め込むことによって実現可能な三重項が与えられたとき、ある定数$c < 1$が存在して、例えば \emph{every embedding of dimension at most $cD$は三重項の半分を侵害し、入力を無視する自明な一次元解として精度が低いことを証明している。
ユニクティック・ゲーム・コンジェクチュアでは、与えられた三重項が$D=1$次元でほぼ実現可能であるとしても、多項式時間アルゴリズム -- \textit{regardless of its dimension} は、自明な50\%$基準線を超える精度を達成することができる。
関連論文リスト
- $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval [99.8640829555514]
本稿では,最小埋め込み次元 (Minimal Embeddable Dimension, MED) で表されるベクトル空間に部分集合 (m$ element, $mchoose k$ subsets of at least $k$ element) を埋め込むために必要な最小次元について検討する。
MEDの密接な境界は理論的に導出され、$ell$メートル法、内積、コサイン類似性を含む「距離」や「類似性」の様々な概念に対して実証的に支持される。
論文 参考訳（メタデータ） (2026-01-28T18:45:43Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。
本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff [12.351756386062291]
低次元表現の学習と特徴写像の複雑性/不規則性の最小化のバランスを定式化する。
大深度の場合、ほとんどすべての隠れ表現はおよそ$R(0)(f)$次元であり、ほとんど全ての重み行列は$W_ell$が$R(0)(f)$特異値である。
興味深いことに、大きな学習率の使用は、ほぼすべての層の表現の無限深度収束を保証する注文$O(L)$ NTKを保証するために要求される。
論文 参考訳（メタデータ） (2023-05-30T13:06:26Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - Provably Approximated ICP [40.349822671753024]
そこで、emphalwaysが$p times q$で3ドルのペアからなる"witness"集合があることを証明し、新しいアライメントアルゴリズムにより、この大域的最適化に対する定数因子近似を定義する。
私たちの近似定数は、実際には1ドル近くであり、最先端のアルゴリズムよりも最大10ドル小さいです。
論文 参考訳（メタデータ） (2021-01-10T18:09:29Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
本稿では, 高速で, 距離保存可能なバイナリ埋め込みアルゴリズムを提案し, データセット $mathcalTsubseteqmathbbRn$ を立方体 $pm 1m$ のバイナリシーケンスに変換する。
我々の手法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
論文 参考訳（メタデータ） (2020-10-01T22:41:41Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。
例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
論文 参考訳（メタデータ） (2020-08-06T09:50:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。