Conceptstatistical-computational gap / 统计计算鸿沟
Statistical-Computational Gap
A concept in machine learning and statistics describing the inherent tension between statistical efficiency (sample complexity) and computational efficiency (runtime) within the same problem—specifically, the difficulty of simultaneously achieving optimal sample complexity and polynomial-time computational complexity.
Timeline (last 90 days)
Oct 5
High-dimensional structure learning of Gaussian DAGs faces a statistical-computational gap: methods with sharp sample complexity rely on computationally expensive subset searches and require a pre-specified in-degree upper bound, while polynomial-time algorithms exhibit comparatively inferior sample complexity.
Unverified50%