論文の概要: Analyzing and improving a classical Betti number estimation algorithm

• arxiv url: http://arxiv.org/abs/2509.16171v1
• Date: Fri, 19 Sep 2025 17:29:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-22 18:18:11.255775
• Title: Analyzing and improving a classical Betti number estimation algorithm
• Title（参考訳）: 古典ベッチ数推定アルゴリズムの解析と改善
• Authors: Julien Sorci,
• Abstract要約: 任意の単純複素体の正規化ベッチ数を推定するための古典的アルゴリズムを提案した。 モンテカルロ構造に類似した量子アルゴリズムによって動機付けされ、サンプルの複雑さが向上し、この古典的なアルゴリズムのサンプルの複雑さをより詳細に分析する。 特定のモデルに対して、我々の改善は、ほとんど常にサンプルの複雑さを減らし、また、両方のアルゴリズムのサンプルの複雑さが指数関数的である別のレギュレーションを生成することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, a classical algorithm for estimating the normalized Betti number of an arbitrary simplicial complex was proposed. Motivated by a quantum algorithm with a similar Monte Carlo structure and improved sample complexity, we give a more in-depth analysis of the sample complexity of this classical algorithm. To this end, we present bounds for the variance of the estimators used in the classical algorithm and show that the variance depends on certain combinatorial properties of the underlying simplicial complex. This new analysis leads us to propose an improvement to the classical algorithm which makes the "easy cases easier'', in that it reduces the sample complexity for simplicial complexes where the variance is sufficiently small. We show the effectiveness and limitations of these classical algorithms by considering Erd\H{o}s-Renyi random graph models to demonstrate the existence of "easy" and "hard" cases. Namely, we show that for certain models our improvement almost always leads to a reduced sample complexity, and also produce separate regimes where the sample complexity for both algorithms is exponential.
• Abstract（参考訳）: 近年,任意の単純複素数の正規化ベッチ数を推定する古典的アルゴリズムが提案されている。 モンテカルロ構造に類似した量子アルゴリズムによって動機付けされ、サンプルの複雑さが向上し、この古典的なアルゴリズムのサンプルの複雑さをより詳細に分析する。 この目的のために、古典的アルゴリズムで用いられる推定子の分散に対する境界を示し、その分散が基礎となる単純複素体のある種の組合せの性質に依存することを示す。 この新たな分析により, 分散が十分小さい単純錯体のサンプル複雑性を低減し, 「容易なケース」 を実現する古典的アルゴリズムの改良が提案される。 Erd\H{o}s-Renyiランダムグラフモデルを用いて、これらの古典的アルゴリズムの有効性と限界を示し、"easy" および "hard" ケースの存在を実証する。 すなわち、特定のモデルに対して、我々の改善は、ほとんど常にサンプルの複雑さを減らし、また、両方のアルゴリズムのサンプルの複雑さが指数関数的である別のレギュレーションを生成することを示す。

関連論文リスト

• Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes [6.713479655907349]
  クリプト錯体上のベッチ数推定(BNE)のための量子および古典モンテカルロアルゴリズムが最近提案されている。 我々はこれらのアルゴリズムをレビューし、新しいモジュラーフレームワーク内で共通のモンテカルロ構造を強調した。 異なるモジュールを再結合することにより、サンプルの複雑さに指数関数的に改善された依存を持つ新しい量子アルゴリズムを作成する。
  論文  参考訳（メタデータ） (2024-08-29T22:35:50Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Iterative regularization for low complexity regularizers [18.87017835436693]
  反復正則化は、最適化アルゴリズムの暗黙のバイアスを利用して不正な問題を正則化する。 非滑らかかつ非凸な関数によって記述されるバイアスを処理できる最初の反復正則化手法を提案し,研究する。
  論文  参考訳（メタデータ） (2022-02-01T14:09:00Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。 我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
  論文  参考訳（メタデータ） (2021-10-03T05:38:49Z)
• On the Cryptographic Hardness of Learning Single Periodic Neurons [42.86685497609574]
  ノイズの存在下での等方性ガウス分布より単一ニューロンを学習する際の暗号的難易度を簡易に低減することを示す。 提案アルゴリズムは勾配ベースや逆SQ-timeアルゴリズムではなく,LLL(Lenstra-LenstraLov'asz)格子に基づく。
  論文  参考訳（メタデータ） (2021-06-20T20:03:52Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Rejection sampling from shape-constrained distributions in sublinear time [14.18847457501901]
  離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。 本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T01:00:42Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)

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

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