論文の概要: Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

• arxiv url: http://arxiv.org/abs/2609.30477v1
• Date: Thu, 24 Sep 2026 19:16:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.115791
• Title: Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering
• Title（参考訳）: 厳密なSSEクラスタリングのためのスケジュール制約付きサブセット動的プログラミング
• Abstract要約: 我々は、データ由来の幾何グラフを用いて、正確なサブセットの動的プログラムをプリコンディションする。 残集合の反復最小化は固定(K) またはペナル化 SSE であり、各残集合の連結成分に対する正確な分解である。 本稿では,スキャフォールドプレコンディショニングを用いて,分割マージ提案の効率を向上させる方法について述べる。
• 参考スコア（独自算出の注目度）: 1.76179873429447
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Exact Euclidean \(K\)-means partitions \(n\) observations into \(K\) unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-\(K\) or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed \(K\) and dimension, under compact ball support and density bounds, retaining \(q=O(\log n)\) nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an \(O(\log n/n)\) fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.
• Abstract（参考訳）: Exact Euclidean \(K\)-means partitions \(n\) observed into \(K\) unlabelled cluster, but unrestricted search is generally index。 結果として、接続された頂点部分集合のみがクラスタとして認識され、SSE(sum-of-squared-errors)損失は変わらない。 残集合の反復最小化は固定-\(K\) またはペナル化された SSE であり、残集合の各連結成分に対する正確な分解である。 私たちが研究する中心的な問題は、制限のない最適性を維持しながら、どの程度の計算支援を除去できるかである。 グラフインクルージョンはモノトーンのカバレッジとサポート関係を与え、ボトルネックしきい値はネストされた階層の最初のカバーグラフを特定する。 固定された \(K\) と次元に対して、コンパクトなボール支持と密度境界の下では、観測当たりの近辺である \(q=O(\log n)\) は、完全グラフエッジの \(O(\log n/n)\) 分数を用いて、確率が 1 に比例する経験的 SSE 最適化を保存する。 不均等な重みと共分散を持つTrncated Gaussianmixsはこれらの条件を満たす。 私たちの提供する速度は、多項式最適化の複雑さを暗示する結果よりも、十分上界である。 目的整合合成および全データ比較は、カバレッジ、圧縮、参照ラベルの合意を評価する。 二次的な応用として,未制限混合後部を保存した分割マージ提案の効率向上のために,提案した足場プレコンディショニングを活用する方法について述べる。

関連論文リスト

• Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA [3.7768601360100647]
  仮定から強制可能な性質へ分割性を変換する適応分解フレームワークであるFrozenLGPを紹介する。 FrozenLGPは、高結合性インスタンス上での標準分割およびコンカヤベースラインの4.6%と比較して100%の分解カバレッジを実現している。
  論文  参考訳（メタデータ） (2026-07-09T06:19:12Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。 適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-03-29T17:59:10Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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