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

• arxiv url: http://arxiv.org/abs/2510.17451v2
• Date: Thu, 23 Oct 2025 10:56:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:12.042545
• Title: The Parameterized Complexity of Computing the VC-Dimension
• Title（参考訳）: VC次元計算のパラメータ化複雑性
• Authors: Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney, Prafullkumar Tale,
• Abstract要約: VC次元(VC-dimension)は、機械学習の多くの領域の中心となる集合系(またはハイパーグラフ)のよく研究され基礎的な複雑性尺度である。 ETH(Exponential Time hypothesis)の下では,2$mathcalO(mathcalV|)$-timeアルゴリズムが厳密であることを示す。
• 参考スコア（独自算出の注目度）: 5.53479503648814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The VC-dimension is a well-studied and fundamental complexity measure 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 design a $2^{\mathcal{O}(\rm{tw}\cdot \log \rm{tw})}\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth $\rm{tw}$ (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).
• Abstract（参考訳）: VC次元(VC-dimension)は、機械学習の多くの領域の中心となる集合系(またはハイパーグラフ)のよく研究され基礎的な複雑性尺度である。 我々はVC次元計算の複雑さに関するいくつかの新しい結果を確立した。 特に、ハイパーグラフ $\mathcal{H}=(\mathcal{V},\mathcal{E})$ が与えられたとき、素の 2 つのmathcal{O}(|\mathcal{V}|)}$-time アルゴリズムは指数時間仮説(ETH)の下で漸近的に厳密であることを示す。 次に,最大次数$\mathcal{H}$でパラメータ化された場合の1ドル加法固定パラメータ近似アルゴリズムと,その次元でパラメータ化された場合の固定パラメータアルゴリズムを認め,これらが本質的にそのような利用可能な構造パラメータであることを示す。 最後に,集合系とグラフの両方のVC次元を捉えるグラフを用いて定式化された問題の一般化を考える。 我々は、任意のグラフ$G=(V,E)$ of treewidth $\rm{tw}$(これは集合系の場合、その入射グラフのツリー幅に適用される)に対して、2つの^{\mathcal{O}(\rm{tw}\cdot \log \rm{tw})}\cdot |V|$-timeアルゴリズムを設計する。 これは(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)

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

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