論文の概要: On computing and the complexity of computing higher-order $U$-statistics, exactly

• arxiv url: http://arxiv.org/abs/2508.12627v1
• Date: Mon, 18 Aug 2025 05:01:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-19 14:49:10.973964
• Title: On computing and the complexity of computing higher-order $U$-statistics, exactly
• Title（参考訳）: 計算と高次計算の複雑さ、正確には$U$-statisticsについて
• Authors: Xingyu Chen, Ruiqi Zhang, Lin Liu,
• Abstract要約: 高次の$U$-statisticsは統計学、機械学習、コンピュータサイエンスなどの分野に多い。 広く見られるにもかかわらず、その計算複雑性に関する包括的な研究は驚くほど不足している。
• 参考スコア（独自算出の注目度）: 30.842935323383816
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Higher-order $U$-statistics abound in fields such as statistics, machine learning, and computer science, but are known to be highly time-consuming to compute in practice. Despite their widespread appearance, a comprehensive study of their computational complexity is surprisingly lacking. This paper aims to fill that gap by presenting several results related to the computational aspect of $U$-statistics. First, we derive a useful decomposition from an $m$-th order $U$-statistic to a linear combination of $V$-statistics with orders not exceeding $m$, which are generally more feasible to compute. Second, we explore the connection between exactly computing $V$-statistics and Einstein summation, a tool often used in computational mathematics, quantum computing, and quantum information sciences for accelerating tensor computations. Third, we provide an optimistic estimate of the time complexity for exactly computing $U$-statistics, based on the treewidth of a particular graph associated with the $U$-statistic kernel. The above ingredients lead to a new, much more runtime-efficient algorithm of exactly computing general higher-order $U$-statistics. We also wrap our new algorithm into an open-source Python package called $\texttt{u-stats}$. We demonstrate via three statistical applications that $\texttt{u-stats}$ achieves impressive runtime performance compared to existing benchmarks. This paper aspires to achieve two goals: (1) to capture the interest of researchers in both statistics and other related areas further to advance the algorithmic development of $U$-statistics, and (2) to offer the package $\texttt{u-stats}$ as a valuable tool for practitioners, making the implementation of methods based on higher-order $U$-statistics a more delightful experience.
• Abstract（参考訳）: 高次の$U$-statisticsは統計学、機械学習、計算機科学などの分野に多いが、実際に計算するのに非常に時間がかかることが知られている。 広く見られるにもかかわらず、その計算複雑性に関する包括的な研究は驚くほど不足している。 本稿では,$U$-statisticsの計算的側面に関連するいくつかの結果を提示することにより,そのギャップを埋めることを目的とする。 まず、$m$-thの$U$-statisticから$V$-statisticsと$m$を超えない順序の線形結合への有用な分解を導出する。 第二に、計算数学、量子コンピューティング、テンソル計算を高速化するための量子情報科学でよく使われるツールである、Einstein summationと$V$-statisticsの正確な関係について検討する。 第3に、$U$-statisticsを正確に計算する際の時間複雑性を、$U$-statistic kernelに関連する特定のグラフのツリー幅に基づいて楽観的に推定する。 上記の要素は、より正確に計算可能なより高次の$U$-statisticsという新しい、より実行効率の高いアルゴリズムに繋がる。 また、新しいアルゴリズムを$\texttt{u-stats}$というオープンソースのPythonパッケージにラップします。 我々は、$\texttt{u-stats}$という3つの統計アプリケーションを通して、既存のベンチマークと比較して、印象的な実行時パフォーマンスを実現しています。 本論文は,(1)U$-statisticsのアルゴリズム開発を進めるために,統計学および関連分野の研究者の関心を集めること,(2)実践者にとって価値のあるツールとして$\texttt{u-stats}$を提供すること,そして,高次の$U$-statisticsに基づく手法の実装をより楽しい体験にすること,の2つの目標を達成することを目的としている。

関連論文リスト

• Approximate Top-$k$ for Increased Parallelism [1.2557921586915128]
  そこで本研究では,バケット付き近似式をk$のアルゴリズムで評価する。 上位$が正確であるという要件を緩和することで、バケット付きアルゴリズムは利用可能な並列性を劇的に向上させることができる。 PyTorch用の高速なバケット付きトップ$実装もリリースしています。
  論文  参考訳（メタデータ） (2024-12-05T17:17:28Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy [33.72108955447222]
  最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。 そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。 我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
  論文  参考訳（メタデータ） (2021-12-27T14:59:52Z)
• Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
  我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。 結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
  論文  参考訳（メタデータ） (2021-10-08T08:22:05Z)
• 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 estimation of sparse topic models [3.308743964406688]
  本稿では、要素的にスパースである可能性のある$A$の推定について検討し、$K$のトピックの数は不明である。 我々は、そのような$A$を推定するための新しいミニマックスローバウンドを導出し、そのリカバリのための新しい計算効率の良いアルゴリズムを提案する。 我々の推定値は、未知の$A$に適応し、我々の分析は、任意の有限$n$、$p$、$K$および文書長に対して有効である。
  論文  参考訳（メタデータ） (2020-01-22T03:19:50Z)

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

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