論文の概要: 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。 我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。 我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
  論文  参考訳（メタデータ） (2023-06-23T01:28:24Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• 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)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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