論文の概要: John Ellipsoids via Lazy Updates

• arxiv url: http://arxiv.org/abs/2501.01801v1
• Date: Fri, 03 Jan 2025 13:17:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-06 15:10:49.242735
• Title: John Ellipsoids via Lazy Updates
• Title（参考訳）: John Ellipsoids, Lazy Updates
• Authors: David P. Woodruff, Taisuke Yasuda,
• Abstract要約: 近似したジョン楕円体を$d$次元の$n$ポイントで計算するためのより高速なアルゴリズムを与える。 精度の高いレバレッジスコアの計算を遅らせることで,このアルゴリズムを著しく高速化できることを示す。
• 参考スコア（独自算出の注目度）: 47.790126028106734
• License:
• Abstract: We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores [CCLY19]. We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas.
• Abstract（参考訳）: 近似したジョン楕円体を$d$次元の$n$ポイントで計算するためのより高速なアルゴリズムを与える。 最もよく知られた先行アルゴリズムは、点のレバレッジスコアを繰り返し計算し、これらのスコアでそれらを重み付けする[CCLY19]。 このアルゴリズムは,サンプリングを用いて高精度レバレッジスコアの計算を遅らせ,その後,高速長方行列乗算による高精度レバレッジスコアの複数バッチを計算することにより,実質的に高速化可能であることを示す。 また、同様のアイデアを用いて、ジョン・エリプシドスに対して低空間ストリーミングアルゴリズムを提供する。

関連論文リスト

• Fast John Ellipsoid Computation with Differential Privacy Optimization [34.437362489150246]
  高速なジョン楕円体計算のための微分プライベートアルゴリズムを提案する。 提案手法は, ノイズ摂動とスケッチ処理を統合し, スコアサンプリングを活用し, 効率とプライバシの両立を図る。
  論文  参考訳（メタデータ） (2024-08-12T03:47:55Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
  本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。 推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。 提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Quantum speedup of leverage score sampling and its application [0.0]
  本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。 応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-15T14:40:18Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Faster Convolution Inference Through Using Pre-Calculated Lookup Tables [0.0]
  低カーディナリティアクティベーションは、事前に計算されたルックアップテーブルから推論値を取得するアルゴリズムを、毎回計算する代わりに許可する。 このアルゴリズムには拡張があり、一部は現在使用されているアルゴリズムのそれを超える能力を提供する。
  論文  参考訳（メタデータ） (2021-04-04T20:09:20Z)

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

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