論文の概要: Introduction to Coresets: Approximated Mean
- arxiv url: http://arxiv.org/abs/2111.03046v1
- Date: Thu, 4 Nov 2021 17:49:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-05 16:16:38.444783
- Title: Introduction to Coresets: Approximated Mean
- Title（参考訳）: Coresets入門:近似平均
- Authors: Alaa Maalouf and Ibrahim Jubran and Dan Feldman
- Abstract要約: A emphstrong coreset for the mean query of a set $P$ in $mathbbRd$ is a small weighted subset $Csubseteq P$。
emphweak coreset は小さい加重部分集合$C$ of$P$ であり、平均は$P$ である。
- 参考スコア（独自算出の注目度）: 29.520871474641485
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A \emph{strong coreset} for the mean queries of a set $P$ in ${\mathbb{R}}^d$
is a small weighted subset $C\subseteq P$, which provably approximates its sum
of squared distances to any center (point) $x\in {\mathbb{R}}^d$. A \emph{weak
coreset} is (also) a small weighted subset $C$ of $P$, whose mean approximates
the mean of $P$. While computing the mean of $P$ can be easily computed in
linear time, its coreset can be used to solve harder constrained version, and
is in the heart of generalizations such as coresets for $k$-means clustering.
In this paper, we survey most of the mean coreset construction techniques, and
suggest a unified analysis methodology for providing and explaining classical
and modern results including step-by-step proofs. In particular, we collected
folklore and scattered related results, some of which are not formally stated
elsewhere. Throughout this survey, we present, explain, and prove a set of
techniques, reductions, and algorithms very widespread and crucial in this
field. However, when put to use in the (relatively simple) mean problem, such
techniques are much simpler to grasp. The survey may help guide new researchers
unfamiliar with the field, and introduce them to the very basic foundations of
coresets, through a simple, yet fundamental, problem. Experts in this area
might appreciate the unified analysis flow, and the comparison table for
existing results. Finally, to encourage and help practitioners and software
engineers, we provide full open source code for all presented algorithms.
- Abstract（参考訳）: 集合 $P$ in ${\mathbb{R}}^d$ の平均的なクエリに対する \emph{strong coreset} は小さな重み付き部分集合 $C\subseteq P$ であり、任意の中心 (point) $x\in {\mathbb{R}}^d$ への平方距離の和を確実に近似する。
emph{weak coreset} は小さな重み付き部分集合 $c$ が $p$ であり、その平均は $p$ の平均に近い。
p$の平均の計算は線形時間で容易に計算できるが、そのコアセットは制約の厳しいバージョンを解決するために使用することができ、$k$-meansクラスタリングのためのcoresetsのような一般化の中心である。
本稿では, 平均コアセット構築手法のほとんどを調査し, ステップバイステップの証明を含む古典的, 近代的な結果の提供と説明のための統一分析手法を提案する。
特に民話と散在する関連資料を収集し,その一部は他の場所では公式には述べられていない。
この調査を通じて、この分野において非常に広くかつ重要な技術、削減、アルゴリズムのセットを提示し、説明し、証明する。
しかし、(比較的単純な)平均問題で使用する場合、そのようなテクニックは理解しやすくなっている。
この調査は、新しい研究者がこの分野に慣れていないことをガイドし、単純だが基本的な問題を通じてコアセットの非常に基本的な基礎を紹介するのに役立つかもしれない。
この領域の専門家は、統一分析フローと既存の結果の比較テーブルを評価できるかもしれない。
最後に、実践者やソフトウェアエンジニアを奨励し、支援するために、提示されたすべてのアルゴリズムに完全なオープンソースコードを提供します。
関連論文リスト
- Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers [10.259254824702555]
我々は、外乱が存在する場合に、$k$-sparse Wasserstein Barycenter問題を研究する。
既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張することはできない。
本稿では,外乱問題のある$k$sparse WBに対して定数近似係数を求めるクラスタリングに基づくLP法を提案する。
論文 参考訳（メタデータ） (2024-04-20T15:01:35Z) - 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) - Manifold Free Riemannian Optimization [4.484251538832438]
滑らかな多様体 $mathcalM$ を用いて最適化問題を解くための原理的枠組みを提案する。
代数学M におけるコスト関数 $(x_i, y_i) の雑音のないサンプル集合 mathbbR$ と多様体 $mathcalM$ の固有次元を用いる。
論文 参考訳（メタデータ） (2022-09-07T16:19:06Z) - An Empirical Evaluation of $k$-Means Coresets [4.45709593827781]
利用可能な$k$-meansコアセットの品質を比較する作業はありません。
我々はコアセットの計算が困難であると主張するベンチマークを提案する。
我々は理論と実践から最もよく使われるコアセットアルゴリズムの徹底的な評価を行う。
論文 参考訳（メタデータ） (2022-07-03T06:47:53Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳（メタデータ） (2021-10-19T17:43:50Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳（メタデータ） (2020-06-25T19:59:24Z) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z) - Faster PAC Learning and Smaller Coresets via Smoothed Analysis [25.358415142404752]
PAC学習は通常、$n$アイテムから小さなサブセット(varepsilon$-sample/net)を計算することを目的としています。
スムーズな解析から着想を得て、クエリに対する強調誤差(最悪のケースではなく)を近似する自然な一般化を提案する。
論文 参考訳（メタデータ） (2020-06-09T18:25:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。