論文の概要: Scalable Second-order Riemannian Optimization for $K$-means Clustering

• arxiv url: http://arxiv.org/abs/2509.21675v1
• Date: Thu, 25 Sep 2025 22:49:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.066957
• Title: Scalable Second-order Riemannian Optimization for $K$-means Clustering
• Title（参考訳）: K$-meansクラスタリングのためのスケーラブルな2階リーマン最適化
• Authors: Peng Xu, Chun-Ying Hou, Xiaohui Chen, Richard Y. Zhang,
• Abstract要約: K$-meansクラスタリング問題をサブ多様体として新たに定式化する。 K$-平均多様体を積多様体に分解することにより、ニュートン部分確率がどのように解けるかを示す。 実験の結果,提案手法は最先端の1次負の非負の非負の分解法よりもはるかに高速に収束することがわかった。
• 参考スコア（独自算出の注目度）: 22.839486642997187
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering is a hard discrete optimization problem. Nonconvex approaches such as low-rank semidefinite programming (SDP) have recently demonstrated promising statistical and local algorithmic guarantees for cluster recovery. Due to the combinatorial structure of the $K$-means clustering problem, current relaxation algorithms struggle to balance their constraint feasibility and objective optimality, presenting tremendous challenges in computing the second-order critical points with rigorous guarantees. In this paper, we provide a new formulation of the $K$-means problem as a smooth unconstrained optimization over a submanifold and characterize its Riemannian structures to allow it to be solved using a second-order cubic-regularized Riemannian Newton algorithm. By factorizing the $K$-means manifold into a product manifold, we show how each Newton subproblem can be solved in linear time. Our numerical experiments show that the proposed method converges significantly faster than the state-of-the-art first-order nonnegative low-rank factorization method, while achieving similarly optimal statistical accuracy.
• Abstract（参考訳）: クラスタリングは難しい個別の最適化問題です。 SDP(low-rank semidefinite programming)のような非凸法は、最近、クラスタ回復のための有望な統計的および局所的なアルゴリズム保証を実証している。 K$-meansクラスタリング問題の組合せ構造のため、現在の緩和アルゴリズムは制約実現可能性と目的最適性のバランスをとるのに苦労し、厳密な保証を伴う2階臨界点の計算において大きな課題を提示している。 本稿では,K$-means問題を,部分多様体上の滑らかな非制約最適化として新たに定式化し,そのリーマン構造を特徴付けることにより,二階立方正則リーマンニュートンアルゴリズムを用いて解けるようにする。 K$-平均多様体を積多様体に分解することにより、各ニュートン部分プロブレムが線型時間でどのように解けるかを示す。 数値実験により,提案手法は最先端の1次非負の低ランク分解法よりもはるかに高速に収束し,同様に最適な統計的精度が得られた。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [64.99236464953032]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Alternating Iteratively Reweighted $\ell_1$ and Subspace Newton Algorithms for Nonconvex Sparse Optimization [11.56128809794923]
  本稿では,可微分損失関数と非滑らか正規化関数の和を最小化する新しいハイブリッドアルゴリズムを提案する。 臨界点へのグローバル収束を証明し、適切な条件下では、アルゴリズムが既存の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2024-07-24T12:15:59Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization [3.867143522757309]
  この研究は、制約集合が多様体構造を意味するような制約付き大規模非制約最適化に関するものである。 本稿では,収束性の向上と計算コストの削減を目的とした2階サドル最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-22T00:37:44Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。