論文の概要: Streaming algorithms for robust max-min diversification
- arxiv url: http://arxiv.org/abs/2610.01456v1
- Date: Thu, 01 Oct 2026 10:51:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:24.065748
- Title: Streaming algorithms for robust max-min diversification
- Title（参考訳）: 頑健な最大分数多様化のためのストリーミングアルゴリズム
- Abstract要約: 計量空間における$n$ポイント$X$と整数$k$が与えられたとき、発散は最小対距離を最大化する$k$ポイントの$X$を選択することを目的としている。
Amagata, AAAI23] では、$z$の外れ値を含む解を除外するロバストな決定論が提案されている。
適切な不整合分離仮定に基づくコアセットに基づくストリーミングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Given a set of $n$ points $X$ in a metric space and an integer $k$, max-min diversification aims to select $k$ points of $X$ maximizing their minimum pairwise distance. This objective function is however highly vulnerable to noisy points. In[Amagata, AAAI23], a robust formulation is proposed which addresses this vulnerability by excluding solutions containing any of $z$ outliers, defined as the $z$ points in $X$ with the largest nearest-neighbor distances. That paper also presents a coreset-based streaming algorithm for the new formulation, based on a suitable inlier-outlier separation assumption. However, we identify three shortcomings in the algorithm by [Amagata, AAAI23]: its coreset construction requires an offline computation over $X$, which needs memory linear in $n$, in stark contrast with the typical goals of stream processing; the one-pass procedure used to extract the solution from the coreset may return fewer than $k$ points (hence, an unfeasible solution) because it permanently discards points too far from the current solution; and its outlier-exclusion guarantee is only probabilistic and weakens as the coreset size shrinks. In contrast, we present a deterministic coreset-based algorithm that, under a natural inlier-outlier separation assumption (similar to the one used in [Amagata, AAAI23]), returns exactly $k$ inliers which are a $(2+\varepsilon)$-approximate solution, for any $\varepsilon>0$, thus only $\varepsilon$ above the best polynomial-time sequential approximation, even without outliers. Its one-pass streaming implementation adapts obliviously to the dataset's doubling dimension $D$ and, for wide ranges of $k$, $z$, $\varepsilon$, and $D$, it uses memory independent of $n$. For sufficiently long streams, its amortized update time is proportional to the coreset size, thus also independent of $n$.
- Abstract（参考訳）: 計量空間における$n$ポイント$X$と整数$k$が与えられたとき、最大分数化は最小対距離を最大化する$X$の$k$ポイントを選択することを目的としている。
しかし、この目的関数はノイズの多い点に対して非常に脆弱である。
Amagata, AAAI23] では、最も近い近傍距離を持つ$X$の$z$ポイントとして定義される$z$アウトリエを含む解を除外することで、この脆弱性に対処する堅牢な定式化が提案されている。
また,新しい定式化のためのコアセットに基づくストリーミングアルゴリズムを提案する。
しかし,アルゴリズムの欠点は, [Amagata, AAAI23]:コアセットの構成には, ストリーム処理の典型的な目標と対照的に,$n$で線形なメモリを必要とする$X$以上のオフライン計算が必要である; コアセットから解を抽出するために使用されるワンパス手順は, 現在の解から遠すぎる点を永久に破棄するので, コアセットのサイズが小さくなるにつれて, 確率的かつ弱くなる。
対照的に、決定論的コアセットベースのアルゴリズムは、自然な不整合分離仮定(Amagata, AAAI23]に類似している)の下で、任意の$\varepsilon>0$に対して$(2+\varepsilon)$-approximateソリューションである$k$ inliersを正確に返します。
そのワンパスストリーミング実装は、データセットの倍のディメンションである$D$と、幅広い範囲の$k$、$z$、$\varepsilon$、$D$に明らかに適応します。
十分に長いストリームの場合、その償却更新時間はコアセットのサイズに比例する。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Computational Hardness of Private Coreset [84.99100741615423]
与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。
no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。
$k$-means in the
論文 参考訳（メタデータ） (2026-02-19T15:58:49Z) - Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers [9.19267739465056]
サイズ $tildeO(varepsilon-2 cdot minvarepsilon-2, d)$ if $n geq 4m$。
d = 1$ の特別な場合、最適コアセットサイズは $tildeTheta(varepsilon-1/2 + fracmn varepsilon-1)$ となる。
我々の結果は、ロバスト$(k,z)$-clusteringにまで拡張されます。
論文 参考訳（メタデータ） (2025-10-28T16:49:03Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Differentially Private Clustering in Data Streams [56.26040303056582]
私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。
当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z) - Coreset-based Strategies for Robust Center-type Problems [0.6875312133832077]
我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。
パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-02-18T10:04:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。