使用网格搜索进行超参数调整的计算复杂度是多少？

Question

如果我有许多超参数要调优，每个超参数都可以表示为任意长度的向量，例如神经元数量= [4, 8, 16]，学习率= [0.1, 0.01, 0.001, 0.0001]，那么全网格搜索的计算复杂度是多少？

要调优的不同超参数的数量是否为多项式？

Answer 1

全网格搜索将考虑所有可能的笛卡尔乘积。

假设你有长度为n1, n2, ..., nk的k列表，那么它就是n1 x n2 x ... x nk。

因此，是的，它是多项式的。

Answer 2

不，它是指数级的，因为网格搜索是蛮力的(参见polynomial time)。

如果你有长度为n₁, …, nₖ的k列表，其中min(n₁, …, nₖ) = a > 1然后是T(k) = n₁ × n₂ × … × nₖ ∈ Ω(aᵏ)。