論文の概要: Impossibility of latent inner product recovery via rate distortion

• arxiv url: http://arxiv.org/abs/2407.11932v1
• Date: Tue, 16 Jul 2024 17:23:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-17 13:34:07.250304
• Title: Impossibility of latent inner product recovery via rate distortion
• Title（参考訳）: 速度歪みによる潜伏内積回収の不可能性
• Authors: Cheng Mao, Shenduo Zhang,
• Abstract要約: d gtrsim n h(p)$ ここで、$h(p)$ が二元エントロピー函数であれば、内部積を回復することは不可能である。 この証明は、確立された速度歪曲理論に従う。
• 参考スコア（独自算出の注目度）: 1.1510009152620668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this largely expository note, we present an impossibility result for inner product recovery in a random geometric graph or latent space model using the rate-distortion theory. More precisely, suppose that we observe a graph $A$ on $n$ vertices with average edge density $p$ generated from Gaussian or spherical latent locations $z_1, \dots, z_n \in \mathbb{R}^d$ associated with the $n$ vertices. It is of interest to estimate the inner products $\langle z_i, z_j \rangle$ which represent the geometry of the latent points. We prove that it is impossible to recover the inner products if $d \gtrsim n h(p)$ where $h(p)$ is the binary entropy function. This matches the condition required for positive results on inner product recovery in the literature. The proof follows the well-established rate-distortion theory with the main technical ingredient being a lower bound on the rate-distortion function of the Wishart distribution which is interesting in its own right.
• Abstract（参考訳）: この概略例では、速度歪み理論を用いたランダムな幾何グラフや潜在空間モデルにおいて、内積回復の不可能な結果を示す。 より正確には、あるグラフ $A$ on $n$ vertices が、平均エッジ密度 $p$ がガウスまたは球面潜在位置 $z_1, \dots, z_n \in \mathbb{R}^d$ から生成されることを仮定する。 内積 $\langle z_i, z_j \rangle$ は潜在点の幾何学を表す。 d \gtrsim n h(p)$ ここで$h(p)$が二項エントロピー函数であれば、内部積を回復することは不可能である。 これは文献の内積回復における正の結果に必要な条件と一致する。 この証明は、ウィッシュアート分布の速度ゆがみ関数の低い境界となる主技術成分を持つ、確立された速度ゆがみ理論に従う。

関連論文リスト

• On a Neural Implementation of Brenier's Polar Factorization [24.48716080522871]
  1991年、ブレニエは正方行列の極分解を任意のベクトル場 $F:mathbbRdright mathbbRdarrow に PSD $times$ Unitary として分解する定理を証明した。 本稿では,偏波分解定理の実践的実装を提案し,機械学習における可能性を探る。
  論文  参考訳（メタデータ） (2024-03-05T15:59:54Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。 本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
  論文  参考訳（メタデータ） (2023-06-26T17:13:31Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。 近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。 副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
  論文  参考訳（メタデータ） (2022-02-22T04:14:45Z)
• Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings [9.066817876491053]
  我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。 幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。 提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。 我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
  論文  参考訳（メタデータ） (2022-02-07T14:43:35Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Random Geometric Graphs on Euclidean Balls [2.28438857884398]
  ノード $i$ がユークリッド単位球上のランダム潜在点 $X_i$ に関連付けられたランダムグラフに対する潜在空間モデルを考える。 特定のリンク関数に対して、ここで考慮されたモデルは、パワーロー型の分布を持つ尾を持つ次数分布を持つグラフを生成する。
  論文  参考訳（メタデータ） (2020-10-26T17:21:57Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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