論文の概要: Spectral DPPs via NEPv: A Scalable Continuous Relaxation of Determinantal MAP for Diversity-Aware Data Selection

• arxiv url: http://arxiv.org/abs/2606.19411v1
• Date: Wed, 17 Jun 2026 15:40:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-19 18:23:39.453082
• Title: Spectral DPPs via NEPv: A Scalable Continuous Relaxation of Determinantal MAP for Diversity-Aware Data Selection
• Title（参考訳）: NEPvによるスペクトルDPP: 多様性を考慮したデータ選択のための決定型MAPのスケーラブルな連続緩和
• Authors: Richard Yi Da Xu,
• Abstract要約: 大量の候補から小さな、多様性のある、高品質なサブセットを選択することは、現代の機械学習において、繰り返されるプリミティブである。 本稿では、緩和、解法、スケーリング分析に焦点をあて、完全な実データベンチマークを計画的な実証研究に残す。
• 参考スコア（独自算出の注目度）: 6.555429729518591
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Selecting a small, diverse, high-quality subset from a massive pool of candidates is a recurring primitive in modern machine learning -- data curation and coreset selection for training and fine-tuning large models, active-learning batch acquisition, prompt and exemplar selection for in-context learning, retrieval diversification, and experimental design. Determinantal Point Processes (\DPP s) give a principled, well-calibrated notion of diversity for this task, but their \emph{MAP} objective -- pick a size-$k$ subset $S$ maximizing $\logdet(L_S)$ -- is NP-hard, and the standard greedy and sampling algorithms scale superlinearly in the ground-set size $n$. This cost is prohibitive precisely in the data-centric regime where diversity matters most, where $n$ ranges over millions to billions of candidate examples, features, or embeddings. We recast \DPP-MAP as a continuous optimization problem over the Stiefel manifold, and show that its first-order optimality conditions form a \emph{Nonlinear Eigenvalue Problem with eigenvector dependency} (\NEPv) of a previously unstudied form. This \NEPv\ admits a self-consistent field (\SCF) iteration with a spectral-gap-based local contraction guarantee, giving a principled iterative solver where the diversity objective drives an eigenvector-dependent operator. The resulting algorithm, \OurMethod, requires only matrix-vector products with the kernel and runs in time $O\!\big((ndk+nk^2)\,t\big)$ for a small number of iterations $t$, scaling near-linearly in $n$ and integrating directly with low-rank and feature-map kernels common in ML. This paper focuses on the relaxation, solver, and scaling analysis; full real-data benchmarking is left to a planned empirical study.
• Abstract（参考訳）: 大量の候補から小さな、多種多様な高品質なサブセットを選択することは、現代の機械学習において、繰り返し発生するプリミティブである -- トレーニングと微調整のためのデータキュレーションとコアセットの選択、アクティブラーニングバッチ取得、コンテキスト内学習のためのプロンプトとエスペクティブの選択、検索の多様化、実験設計。 決定点過程 (Determinantal Point Processs, DPP s) は、このタスクの多様性の原理的、よく校正された概念を与えるが、それらの \emph{MAP} の目的 -- サイズ-$k$サブセットを選択し、$S$ maximizing $\logdet(L_S)$ -- はNPハードであり、標準グリーディとサンプリングアルゴリズムは、基底セットサイズ$n$で超直線的にスケールする。 このコストは、多様性が最も重要となるデータ中心の体制において、正確には禁じられている。 我々は、スティーフェル多様体上の連続最適化問題として \DPP-MAP を再検討し、その一階最適条件が、未研究形式の固有ベクトル依存性を持つ \emph{Nonlinear Eigenvalue problem} (\NEPv) を形成することを示す。 この \NEPv\ はスペクトルギャップに基づく局所収縮を保証する自己整合体 (\SCF) の反復を認め、多様性目的が固有ベクトル依存作用素を駆動する原理的反復解法を与える。 結果のアルゴリズムである‘OurMethod’は、カーネルを持つマトリックスベクター製品のみを必要とし、時間で$O\! 少数のイテレーションに対して$t$、$n$でほぼ直線的にスケーリングし、MLで一般的なローランクおよびフィーチャーマップカーネルと直接統合する。 本稿では、緩和、解法、スケーリング分析に焦点をあて、完全な実データベンチマークを計画的な実証研究に残す。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project [12.874219128885064]
  本稿では,線形システムを解くための近似的,分散的,高速化されたスケッチ・アンド・プロジェクトアルゴリズム(texttADASAP$)を提案する。 決定点過程の理論を用いて、スケッチ・アンド・プロジェクションによって誘導される後進平均が、真の後進平均に急速に収束することを示す。 $texttADASAP$は$>3 cdot 108$のデータセットにスケールする。
  論文  参考訳（メタデータ） (2025-05-19T20:46:26Z)
• GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility [16.843606527688326]
  単調な部分モジュラーユーティリティ(textsfMDMS$)を用いた最大分数分散と呼ばれる新しい部分集合選択問題について検討する。 計量空間内の点の集合が与えられた場合、$textsfMDMS$の目標は、濃度制約の対象である$f(S) = g(S) + lambda cdot texttdiv(S)$を最大化することである。 ImageNet上のシングルショットデータサンプリングタスクに対して、texttGIST$が最先端のベンチマークより優れていることを示す。
  論文  参考訳（メタデータ） (2024-05-29T04:39:24Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。 既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。 そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-30T16:40:44Z)
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes [29.56615511158156]
  我々は新しいNDPPカーネル分解を導入することで,空間と時間要件を線形に$M$で学習するアルゴリズムを開発した。 また, 線形複雑度NDPP最大値推定アルゴリズムを新たに開発したカーネルだけでなく, 先行処理にも適用する。
  論文  参考訳（メタデータ） (2020-06-17T13:42:09Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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