論文の概要: The Parameterized Complexity of Computing the VC-Dimension

• arxiv url: http://arxiv.org/abs/2510.17451v1
• Date: Mon, 20 Oct 2025 11:36:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:39.434126
• Title: The Parameterized Complexity of Computing the VC-Dimension
• Title（参考訳）: VC次元計算のパラメータ化複雑性
• Authors: Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney, Prafullkumar Tale,
• Abstract要約: ETH(Exponential Time hypothesis)では,2$mathcalO(mathcalV|)$-timeアルゴリズムが極めて厳密であることを示す。 また、グラフを用いて定式化された問題の一般化も検討し、集合系とグラフの両方のVC次元を捉える。
• 参考スコア（独自算出の注目度）: 5.53479503648814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The VC-dimension is a fundamental and well-studied measure of the complexity of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a 1-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We show that it is fixed-parameter tractable parameterized by the treewidth of the graph (which, in the case of set systems, applies to the treewidth of its incidence graph). In contrast with closely related problems whose dependency on the treewidth is necessarily double-exponential (assuming the ETH), our algorithm has a relatively low dependency on the treewidth.
• Abstract（参考訳）: VC次元(VC-dimension)は、機械学習の多くの領域の中心となる集合系(またはハイパーグラフ)の複雑さの、基礎的でよく研究された尺度である。 我々はVC次元計算の複雑さに関するいくつかの新しい結果を確立した。 特に、ハイパーグラフ $\mathcal{H}=(\mathcal{V},\mathcal{E})$ が与えられたとき、素の 2 つのmathcal{O}(|\mathcal{V}|)}$-time アルゴリズムは指数時間仮説(ETH)の下で漸近的に厳密であることを示す。 次に,最大次数$\mathcal{H}$でパラメータ化された場合の1-加法的固定パラメータ近似アルゴリズムと,その次元でパラメータ化された場合の固定パラメータアルゴリズムを認め,これらが本質的にそのような利用可能な構造パラメータであることを示す。 最後に,集合系とグラフの両方のVC次元を捉えるグラフを用いて定式化された問題の一般化を考える。 グラフのツリー幅(集合系の場合、その入射グラフのツリー幅に適用される)によってパラメータ化されることが示される。 木幅への依存が(ETHを仮定すると)必然的に二重指数である密接に関連する問題とは対照的に,本アルゴリズムは木幅への依存度が比較的低い。

関連論文リスト

• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
  論文  参考訳（メタデータ） (2025-10-09T09:47:40Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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