Fugu-MT 論文翻訳(概要): Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means

論文の概要: Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means

arxiv url: http://arxiv.org/abs/2407.11217v1
Date: Mon, 15 Jul 2024 20:04:06 GMT
ステータス: 翻訳完了
システム内更新日: 2024-07-17 19:21:30.806715
Title: Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means
Title（参考訳）: ほぼ線形時間近似アルゴリズムによるユークリッド$k$-medianと$k$-means
Authors: Max Dupré la Tour, David Saulpic,
Abstract要約: Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
参考スコア（独自算出の注目度）: 4.271492285528115
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Clustering is one of the staples of data analysis and unsupervised learning. As such, clustering algorithms are often used on massive data sets, and they need to be extremely fast. We focus on the Euclidean $k$-median and $k$-means problems, two of the standard ways to model the task of clustering. For these, the go-to algorithm is $k$-means++, which yields an $O(\log k)$-approximation in time $\tilde O(nkd)$. While it is possible to improve either the approximation factor [Lattanzi and Sohler, ICML19] or the running time [Cohen-Addad et al., NeurIPS 20], it is unknown how precise a linear-time algorithm can be. In this paper, we almost answer this question by presenting an almost linear-time algorithm to compute a constant-factor approximation.
Abstract（参考訳）: クラスタリングは、データ分析と教師なし学習の基礎の1つである。そのため、クラスタリングアルゴリズムは大規模なデータセットでよく使われ、非常に高速である必要がある。 Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。これらの場合、go-toアルゴリズムは$k$-means++で、$O(\log k)$-approximation in time $\tilde O(nkd)$である。近似係数 [Lattanzi and Sohler, ICML19] やランニング時間 [Cohen-Addad et al , NeurIPS 20] を改善することができるが、線形時間アルゴリズムがどの程度正確かは分かっていない。本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。

関連論文リスト

A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning [4.10375234787249]
教師なし学習問題に対する効率的なアルゴリズム設計のための枠組みを提案する。我々のフレームワークは,雑音の存在下で演算回路を学習するメタアルゴリズムに基づいている。
論文参考訳（メタデータ） (2023-11-13T12:26:25Z)
Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文参考訳（メタデータ） (2023-10-25T16:37:45Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文参考訳（メタデータ） (2023-06-05T12:22:46Z)
Dual Algorithmic Reasoning [9.701208207491879]
本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
論文参考訳（メタデータ） (2023-02-09T08:46:23Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
A Faster $k$-means++ Algorithm [11.428775569173638]
ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
論文参考訳（メタデータ） (2022-11-28T08:17:12Z)
Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文参考訳（メタデータ） (2021-11-09T02:33:36Z)
Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families [12.936601424755944]
DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。 DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
論文参考訳（メタデータ） (2021-10-10T06:37:51Z)
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文参考訳（メタデータ） (2021-09-29T16:25:02Z)
Algorithm Selection on a Meta Level [58.720142291102135]
本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
論文参考訳（メタデータ） (2021-07-20T11:23:21Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文参考訳（メタデータ） (2021-06-10T09:29:05Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。両レベル最適化のための2つの新しいアルゴリズムを提案する。両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文参考訳（メタデータ） (2021-06-08T21:05:30Z)
Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。クエリを少なくすることで、問題の解決が容易になる。
論文参考訳（メタデータ） (2021-06-04T02:32:26Z)
Identifying Co-Adaptation of Algorithmic and Implementational Innovations in Deep Reinforcement Learning: A Taxonomy and Case Study of Inference-based Algorithms [15.338931971492288]
我々は、アルゴリズムの革新と実装決定を分離するために、一連の推論に基づくアクター批判アルゴリズムに焦点を当てる。実装の詳細がアルゴリズムの選択に一致すると、パフォーマンスが大幅に低下します。結果は、どの実装の詳細がアルゴリズムと共適応され、共進化しているかを示す。
論文参考訳（メタデータ） (2021-03-31T17:55:20Z)
Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文参考訳（メタデータ） (2020-12-04T15:46:30Z)
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)
Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文参考訳（メタデータ） (2020-08-29T14:58:26Z)
Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文参考訳（メタデータ） (2020-08-18T16:22:06Z)

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