論文の概要: Computational lower bounds in latent models: clustering, sparse-clustering, biclustering

• arxiv url: http://arxiv.org/abs/2506.13647v1
• Date: Mon, 16 Jun 2025 16:08:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:48.90847
• Title: Computational lower bounds in latent models: clustering, sparse-clustering, biclustering
• Title（参考訳）: 潜在モデルにおける計算的下界:クラスタリング、スパースクラスタリング、ビクラスタリング
• Authors: Bertrand Even, Christophe Giraud, Nicolas Verzelen,
• Abstract要約: スパースPCA、植込みクラスタリング、クラスタリングのような多くの高次元問題において、複雑性のある最もよく知られたアルゴリズムは、計算制約のないアルゴリズムで証明可能な統計的性能に到達できない。 この観測により、いくつかの問題に対して、計算の制約なしに達成可能な最高の統計性能と、多時間アルゴリズムで達成可能な最高の性能とのギャップが生じるという予想が生まれた。 ポリ時間で達成可能な最高の性能を評価するための強力なアプローチは、低次傾斜角で達成可能な最高の性能を調べることである。
• 参考スコア（独自算出の注目度）: 32.472822302123234
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In many high-dimensional problems, like sparse-PCA, planted clique, or clustering, the best known algorithms with polynomial time complexity fail to reach the statistical performance provably achievable by algorithms free of computational constraints. This observation has given rise to the conjecture of the existence, for some problems, of gaps -- so called statistical-computational gaps -- between the best possible statistical performance achievable without computational constraints, and the best performance achievable with poly-time algorithms. A powerful approach to assess the best performance achievable in poly-time is to investigate the best performance achievable by polynomials with low-degree. We build on the seminal paper of Schramm and Wein (2022) and propose a new scheme to derive lower bounds on the performance of low-degree polynomials in some latent space models. By better leveraging the latent structures, we obtain new and sharper results, with simplified proofs. We then instantiate our scheme to provide computational lower bounds for the problems of clustering, sparse clustering, and biclustering. We also prove matching upper-bounds and some additional statistical results, in order to provide a comprehensive description of the statistical-computational gaps occurring in these three problems.
• Abstract（参考訳）: スパースPCA、植込みclique、クラスタリングのような多くの高次元問題において、多項式時間の複雑さを持つ最もよく知られたアルゴリズムは、計算制約のないアルゴリズムで証明可能な統計的性能に到達できない。 この観察により、計算の制約なしに達成可能な最高の統計性能と、多時間アルゴリズムで達成可能な最高の性能の間のギャップ(いわゆる統計計算的ギャップ)の存在の予想が導かれた。 ポリ時間で達成可能な最高の性能を評価するための強力なアプローチは、低次多項式で達成可能な最高の性能を調べることである。 我々は、Schramm and Wein (2022) のセミナー論文の上に構築し、いくつかの潜在空間モデルにおける低次多項式の性能に対する下界を導出する新しいスキームを提案する。 潜伏構造をよりよく活用することにより、より簡単な証明で、より新しい、よりシャープな結果が得られる。 次に,クラスタリング,スパースクラスタリング,ビクラスタリングといった問題に対して,計算能力の低いバウンダリを提供する手法をインスタンス化する。 また,これらの3つの問題における統計的-計算的ギャップの包括的記述を提供するために,上界と追加の統計的結果の一致を証明した。

関連論文リスト

• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
  標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。 私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
  論文  参考訳（メタデータ） (2020-11-12T18:58:51Z)
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
  我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。 テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。 提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
  論文  参考訳（メタデータ） (2020-09-13T22:55:18Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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