論文の概要: Two-Point Local Optimality in $k$-Means via Boundary-Point Screening

• arxiv url: http://arxiv.org/abs/2610.06182v1
• Date: Mon, 05 Oct 2026 12:02:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-09 18:09:51.897938
• Title: Two-Point Local Optimality in $k$-Means via Boundary-Point Screening
• Title（参考訳）: 境界点スクリーニングによる$k$-Meansの2点局所最適性
• Abstract要約: 我々は、少なくとも$r$サンプルの再割り当てが目的関数を減少させるような$r$-point局所最適性を導入する。 BPS-2PLS(Bundary-Point-Screened Two-Point Local Search)を提案する。
• 参考スコア（独自算出の注目度）: 30.362612885851444
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lloyd's algorithm and the discrete local (D-local) optimization method (Li et al., 2025) for $k$-means provide only weak local-optimality guarantees, and their solution quality remains sensitive to initialization. In this paper, we introduce $r$-point local optimality, under which no reassignment of at most $r$ samples decreases the objective function, and focus on $r=2$. The main computational obstacle is the $\mathcal{O}(n^2(k^2+d))$ cost of exhaustive two-point certification for $n$ samples in $d$ dimensions and $k$ clusters. To address this challenge, we prove that (i) every improving two-point move of a D-local optimum must involve a cluster shared by both reassignments, and (ii) only certificate-defined boundary points can participate in an improving pair. Exploiting this structure, we propose Boundary-Point-Screened Two-Point Local Search (BPS-2PLS), which terminates at a two-point local optimum. For fixed $k,d$ and nonvanishing cluster occupancy, the number $m$ of retained candidates satisfies $m=\mathcal{O}_{\mathbb{P}}(\log n)$ under i.i.d. sampling from a bounded-support distribution with bounded density or from a Gaussian mixture. Across twelve benchmarks, BPS-2PLS attains the lowest available mean WCSS on ten. In a subsampling study, screening retains 0.10% to 2.81% of samples on average at the largest tested sizes. The code is available at https://github.com/lwl-learning/BPS-2PLS.
• Abstract（参考訳）: Lloydのアルゴリズムと$k$-meansに対する離散局所(D-local)最適化法(Li et al , 2025)は、局所最適性の弱い保証しか提供せず、解の質は初期化に敏感である。 本稿では、少なくとも$r$サンプルの再割り当てが目的関数を減少させ、$r=2$にフォーカスする$r$ポイント局所最適性を導入する。 主な計算障害は$\mathcal{O}(n^2(k^2+d))$$$d$次元と$k$クラスタにおける$n$サンプルに対する徹底的な2点認証のコストである。 この課題に対処するために、私たちはそれを証明します。 i) D-局所最適化のすべての改善された2点移動は、双方の再割り当てによって共有されるクラスタを伴わなければならない。 (ii) 改善ペアに参加するのは証明書定義境界点のみである。 そこで本研究では,2点局所最適化で終了するBPS-2PLS(Bundary-Point-Screened Two-Point Local Search)を提案する。 固定$k,d$ および非消滅クラスタ占有の場合、保持候補の$m$ は $m=\mathcal{O}_{\mathbb{P}}(\log n)$ を満たす。 12のベンチマークで、BPS-2PLSは10で最低のWCSSを達成した。 サブサンプリング研究において、スクリーニングは最大テストサイズで平均して0.10%から2.81%のサンプルを保持する。 コードはhttps://github.com/lwl-learning/BPS-2PLSで公開されている。

関連論文リスト

• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
  複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。 我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。 PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
  論文  参考訳（メタデータ） (2024-11-02T02:50:12Z)
• Multiple-policy Evaluation via Density Estimation [30.914344538340412]
  本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。 低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
  論文  参考訳（メタデータ） (2024-03-29T23:55:25Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)

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

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