論文の概要: Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming
- arxiv url: http://arxiv.org/abs/2310.19068v1
- Date: Sun, 29 Oct 2023 16:46:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 14:23:39.644670
- Title: Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming
- Title（参考訳）: スパース辞書学習のためのスケッチアルゴリズム:PTASとターンスタイルストリーミング
- Authors: Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda
- Abstract要約: 本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
- 参考スコア（独自算出の注目度）: 48.18845814885398
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sketching algorithms have recently proven to be a powerful approach both for
designing low-space streaming algorithms as well as fast polynomial time
approximation schemes (PTAS). In this work, we develop new techniques to extend
the applicability of sketching-based approaches to the sparse dictionary
learning and the Euclidean $k$-means clustering problems. In particular, we
initiate the study of the challenging setting where the dictionary/clustering
assignment for each of the $n$ input points must be output, which has
surprisingly received little attention in prior work. On the fast algorithms
front, we obtain a new approach for designing PTAS's for the $k$-means
clustering problem, which generalizes to the first PTAS for the sparse
dictionary learning problem. On the streaming algorithms front, we obtain new
upper bounds and lower bounds for dictionary learning and $k$-means clustering.
In particular, given a design matrix $\mathbf A\in\mathbb R^{n\times d}$ in a
turnstile stream, we show an $\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space
upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde
O(n/\epsilon^2 + dk/\epsilon)$ space upper bound for $k$-means clustering, as
well as an $\tilde O(n)$ space upper bound for $k$-means clustering on random
order row insertion streams with a natural "bounded sensitivity" assumption. On
the lower bounds side, we obtain a general $\tilde\Omega(n/\epsilon +
dk/\epsilon)$ lower bound for $k$-means clustering, as well as an
$\tilde\Omega(n/\epsilon^2)$ lower bound for algorithms which can estimate the
cost of a single fixed set of candidate centers.
- Abstract（参考訳）: スケッチアルゴリズムは、低空間ストリーミングアルゴリズムの設計と高速多項式時間近似スキーム(ptas)の両方において強力なアプローチであることが最近証明されている。
本研究では,スパース辞書学習とEuclidean $k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高める新しい手法を開発した。
特に、$n$の入力ポイントごとに辞書/クラスタリングの代入を出力する必要があるという難易度設定の研究を開始し、それ以前の作業では驚くほど注目されなかった。
高速アルゴリズムの分野では、$k$-meansクラスタリング問題に対してPTASを設計する新しいアプローチが得られ、これはスパース辞書学習問題に対する最初のPTASに一般化される。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
特に、設計行列 $\mathbf A\in\mathbb R^{n\times d}$ がターンタイルストリームで与えられると、$\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde O(n/\epsilon^2 + dk/\epsilon)$ space upper bound for $k$-means clustering と $\tilde O(n)$ space upper bound for $k$-means clustering on a random order row insert stream with a natural "bounded sensitivity" assumption。
下限側では、k$-meansクラスタリングのための一般的な$\tilde\omega(n/\epsilon + dk/\epsilon)$下限と、1つの固定された候補センターのコストを推定できるアルゴリズムに対して$\tilde\omega(n/\epsilon^2)$下限を得る。
関連論文リスト
- 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) - 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 Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - 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) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。