論文の概要: Efficient Mean Curvature Computation on High-Dimensional Data Manifolds

• arxiv url: http://arxiv.org/abs/2606.06329v1
• Date: Thu, 04 Jun 2026 16:04:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-05 22:39:44.932274
• Title: Efficient Mean Curvature Computation on High-Dimensional Data Manifolds
• Title（参考訳）: 高次元データマニフォールドにおける効率的な平均曲率計算
• Authors: Alexandre L. M. Levada,
• Abstract要約: 高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。 本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。 実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
• 参考スコア（独自算出の注目度）: 52.452902154360565
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of geometry-aware machine learning algorithms, such as the Mean Curvature Boundary Points (MCBP) method. The naive implementation of this computation, based on a local shape operator approximated from k-nearest neighbor patches, involves an explicit construction of a matrix $H$ whose trace form yields an $O(m^4)$ cost per point, rendering the approach intractable for datasets with more than a few dozen features. This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude. The first contribution is an exact algebraic identity. This identity, derived from the orthogonality of the eigenvectors of the covariance matrix and the cyclicity of the trace operator, eliminates $H$ entirely and reduces the per-point cost to $O(m^2)$ after the eigendecomposition. The second contribution addresses the remaining $O(m^3)$ bottleneck of the full eigendecomposition. Since the local covariance matrix has rank at most $k-1 \ll m$, we replace it with a truncated SVD of the $k \times m$ centered data matrix, an $O(k^2 m)$ operation, and derive an analytical approximation for the contribution of the null-space eigenvectors based on the expected value of their outer product under the Haar measure. The resulting estimator has total cost $O(k^2 m + k m p^2)$, where $p = k-1$. Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation, with negligible loss when the fast estimator is used to replace the original version. By providing a scalable and data-driven estimate of local curvature, the proposed method establishes curvature as a practical geometric feature for a broad range of machine learning tasks, from classical to modern deep learning pipelines.
• Abstract（参考訳）: 高次元データセットの各点における局所的な平均曲率の推定は、平均曲率境界点 (Mean Curvature Boundary Points, MCBP) 法のような幾何認識機械学習アルゴリズムの重要な要素である。 この計算の単純な実装は、k-ネアレスト近傍のパッチから近似された局所形状演算子に基づいており、トレースフォームが1点あたり$O(m^4)$コストとなる行列$H$を明示的に構成し、数十以上の特徴を持つデータセットに対してアプローチを引き付けることができる。 本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。 最初の寄与は、正確な代数的恒等式である。 この恒等式は、共分散行列の固有ベクトルの直交性とトレース作用素の巡回性から導かれ、全額$H$を排除し、固有分解後の点当たりのコストを$O(m^2)$に下げる。 第二の寄与は、全固有分解の残りの$O(m^3)$ボトルネックに対処する。 局所共分散行列は、最大で$k-1 \ll m$ であるから、$k \times m$ 中心データ行列の SVD と $O(k^2 m)$ 演算を置き換え、ハール測度の下での外積の期待値に基づいて、ヌル空間固有ベクトルの寄与に対する解析的近似を導出する。 得られた推定量は合計$O(k^2 m + k m p^2)$で、$p = k-1$である。 実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。 局所曲率をスケーラブルかつデータ駆動で推定することにより,従来のディープラーニングパイプラインから現代のディープラーニングパイプラインまで,幅広い機械学習タスクの実用的な幾何学的特徴として曲率を確立する。

関連論文リスト

• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。 本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
  論文  参考訳（メタデータ） (2023-06-26T17:13:31Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。 エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。 ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
  論文  参考訳（メタデータ） (2022-02-08T12:58:14Z)
• Efficient Matrix-Free Approximations of Second-Order Information, with Applications to Pruning and Optimization [16.96639526117016]
  Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。 これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
  論文  参考訳（メタデータ） (2021-07-07T17:01:34Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization [101.5159744660701]
  分散第2次最適化において、標準的な戦略は、データの小さなスケッチやバッチに基づいて、多くの局所的な見積もりを平均化することである。 本稿では,分散二階法における収束率の理論的および実証的改善を両立させるため,局所的な推定を嫌悪する新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-02T18:08:14Z)
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing [22.337756118270217]
  基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。 最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。 私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
  論文  参考訳（メタデータ） (2020-06-12T07:45:38Z)

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

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