論文の概要: Efficient quadratic entropy with distance sketches

• arxiv url: http://arxiv.org/abs/2610.11976v2
• Date: Fri, 09 Oct 2026 12:28:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.207347
• Title: Efficient quadratic entropy with distance sketches
• Title（参考訳）: 距離スケッチを用いた効率的な二次エントロピー
• Abstract要約: 任意の分布に対して2次エントロピー$pT d p$を近似するスケーラブルな方法について詳述する。 ランダムな特徴埋め込みと投影を用いて計算複雑性を劇的に改善するユークリッドおよび球面測地学のケースに焦点を当てる。
• 参考スコア（独自算出の注目度）: 1.1929584800629671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We detail scalable methods for approximating the quadratic entropy $p^T d p$ for arbitrary distributions $p$ and common distances $d$ of negative type. We focus on the Euclidean and spherical geodesic cases, which both use random feature embeddings and projections to dramatically improve computational complexity within a simple framework. Amortization of a single large matrix multiplication and control variates further enable computation at large scale with low memory and runtime in situations where $d$ is held constant while $p$ varies. We demonstrate this with a comparison against direct pair sampling and bibliometric/scientometric examples on Open Graph Benchmark datasets, revealing papers, fields, and institutions with both particularly narrow and broad interdisciplinary reach from their citations and text features alone.
• Abstract（参考訳）: 任意の分布に対して2次エントロピーを$p^T d p$で近似するスケーラブルな手法を詳述する。 単純なフレームワークにおける計算複雑性を劇的に改善するために、ランダムな特徴埋め込みとプロジェクションを使用するユークリッドおよび球面測地事件に焦点を当てる。 1つの大きな行列乗算と制御変数のアモート化により、$d$が一定であり、$p$が変動する状況下では、メモリとランタイムの少ない大規模での計算が可能になる。 我々は、Open Graph Benchmarkデータセット上で直接ペアサンプリングとバイオロメトリ/サイエントメトリックの例を比較し、特に論文、フィールド、機関の引用とテキストの特徴から、学際的な範囲が狭く広いことを明らかにした。

関連論文リスト

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Quantum Advantage via Efficient Post-processing on Qudit Classical Shadow tomography [3.040305634723913]
  計算量と記憶量の両方を削減できるquditシャドウトモグラフィーに基づく量子的アプローチを提案する。 (operatornametr(rho O)) は (textpoly(log d)) 計算で効率的に推定できる。
  論文  参考訳（メタデータ） (2024-08-29T03:56:16Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。 擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。 実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
  論文  参考訳（メタデータ） (2023-07-18T15:49:02Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  本稿では,SGDの軌道に局在する新しい被覆手法を提案する。 このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。 これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
  論文  参考訳（メタデータ） (2022-09-19T12:11:07Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
  整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。 大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
  論文  参考訳（メタデータ） (2022-05-16T02:24:52Z)
• Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel [15.535749953841274]
  p$ベクトルの積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。 本稿では、実乱射影を複素射影に置き換える、よく知られたスケッチの単純な複素対Real (CtR) 修正を提案する。 本手法は,文献の他のランダム化近似と比較して,精度と速度の面で最先端の性能を達成することを示す。
  論文  参考訳（メタデータ） (2022-02-04T09:15:43Z)

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

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