Fugu-MT 論文翻訳(概要): Convergence of online $k$-means

論文の概要: Convergence of online $k$-means

arxiv url: http://arxiv.org/abs/2202.10640v1
Date: Tue, 22 Feb 2022 02:58:01 GMT
ステータス: 処理完了
システム内更新日: 2022-02-24 03:36:14.497619
Title: Convergence of online $k$-means
Title（参考訳）: オンライン$k$-meansの収束
Authors: Sanjoy Dasgupta, Gaurav Mahajan, Geelon So
Abstract要約: 我々は、分布からストリーミングデータを通して実行される$k$-meansアルゴリズムのクラスに対する収束性を証明する。分布上のオンライン$k$meansは、学習率のスケジュールとともに勾配降下と解釈できることを示す。
参考スコア（独自算出の注目度）: 11.955676707010138
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We prove asymptotic convergence for a general class of $k$-means algorithms performed over streaming data from a distribution: the centers asymptotically converge to the set of stationary points of the $k$-means cost function. To do so, we show that online $k$-means over a distribution can be interpreted as stochastic gradient descent with a stochastic learning rate schedule. Then, we prove convergence by extending techniques used in optimization literature to handle settings where center-specific learning rates may depend on the past trajectory of the centers.
Abstract（参考訳）: 我々は、分布からストリーミングデータを通して実行される$k$-meansアルゴリズムの一般クラスに対する漸近収束を証明し、その中心は、$k$-meansコスト関数の定常点集合に漸近収束する。そこで本研究では,分布上のオンライン$k$-meansを確率的勾配勾配と解釈し,確率的学習率のスケジュールを示す。次に,センター固有の学習速度がセンターの過去の軌跡に依存する可能性のある設定を扱うために,最適化文献に使用される手法を拡張して収束を証明する。

関連論文リスト

SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [37.208622097149714]
すべての$d inmathbb N$に対して、すべての中心部分ガウス分布 $mathcal D$ on $mathbb Rd$, and every even $p inmathbb N$, $d-optimal inmathbb N$, $d-optimal inmathbb N$ が成り立つような普遍定数 $C>0$ が存在することを証明している。これは、すべてのサブガウス分布がemphS-certifiably subgaussianであることを示す。
論文参考訳（メタデータ） (2024-10-28T16:36:58Z)
Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文参考訳（メタデータ） (2024-01-29T02:08:40Z)
Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文参考訳（メタデータ） (2023-05-12T03:01:41Z)
Wasserstein $K$-means for clustering probability distributions [16.153709556346417]
ユークリッド空間では、セントロイドと距離に基づくK$平均の定式化は同値である。現代の機械学習アプリケーションでは、データは確率分布として発生し、測度値のデータを扱う自然な一般化は最適な輸送距離を使用する。 SDP緩和ワッサースタイン$K$-平均は、クラスターが2ドルワッサースタイン計量の下で十分に分離されているため、正確な回復を達成することができることを示す。
論文参考訳（メタデータ） (2022-09-14T23:43:16Z)
Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文参考訳（メタデータ） (2022-04-20T07:14:21Z)
Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
論文参考訳（メタデータ） (2022-02-16T16:24:31Z)
Gradient Based Clustering [72.15857783681658]
本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
論文参考訳（メタデータ） (2022-02-01T19:31:15Z)
Improving the Transient Times for Distributed Stochastic Gradient Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。 EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文参考訳（メタデータ） (2021-05-11T08:09:31Z)
Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文参考訳（メタデータ） (2020-06-15T08:25:50Z)
On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文参考訳（メタデータ） (2020-04-09T17:54:18Z)
A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文参考訳（メタデータ） (2020-03-27T05:13:29Z)

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