资源受限 NAS：用次模优化理解贪心搜索的合理性

最近读到一篇做 Mobile Setting 下 NAS 的论文，比较亮眼的地方是在 ImageNet 上只搜索了 8 天（其实也算不上特别快），但它的思路很值得借鉴——核心是把搜索问题套进了组合优化里的一个经典框架，即次模优化（Submodular Optimization）。

问题的起点：资源受限 NAS 是 NP-hard 的

作者首先指出，在给定计算量约束的前提下搜索精度最高的网络，是一个 NP-hard 问题。既然如此，就需要一个有理论保证的近似方法，而不是纯靠启发式搜索。

次模函数的基本概念

次模函数（Submodular Function）是一个集合函数，定义在一个有限集的幂集（power set）上，即从集合到实数的映射。

该函数的核心性质与边际效益有关：如果 $A$ 是 $B$ 的子集，对于任何不属于 $B$ 的元素 $x$，满足

$f(A \cup \{x\}) - f(A) \geq f(B \cup \{x\}) - f(B)$

直白地说，把同一个元素加入更小的集合时，带来的增益不小于加入更大集合时的增益——这正是边际效益递减的刻画。

当该函数还满足单调性，即集合越大、函数值越大时：

就得到了一个单调非减的次模函数。

将 NAS 映射到次模框架

论文定义了一个集合函数 $F$，将含有 $N$ 个 block 的集合的幂集映射到一个实数集上，即直接把 block 的子集映射到对应网络结构的验证集精度（val accuracy）上。

在 SGD 能找到全局最优的理想情况下，$F$ 是单调函数——加入更多 block 不会降低精度：

现实中 SGD 当然不总能找到全局最优，但经验表明，即便 $F$ 不是严格单调的，它也是非减的，因此单调性假设在实践中是合理的。

将问题进一步对应到单调次模函数的框架后，有如下定理：

这个定理说明了两件事：

1. 向任意结构中增加 block，精度一定不会下降（单调性）。
2. 在小结构上增加 block，精度提升幅度不小于在大结构上增加同一个 block（次模性）。

贪心算法及其近似保证

有了单调次模性，解法自然浮现：贪心算法。具体做法是，每次从候选集中找出「边际精度提升 / 计算代价」比值最大的 block，加入当前结构，直到触碰计算量约束为止。

由于 $F$ 是单调次模函数，经典的近似理论保证贪心策略能达到最优解的 $(1 - 1/e) \approx 63\%$ 近似比。对于一个 NP-hard 问题来说，这是一个有理论支撑的、非平凡的保证。

进一步节省计算量

朴素贪心的每步都需要重新评估所有剩余候选 block 的边际增益，代价较高。论文对算法做了进一步优化：

利用次模函数的性质，可以避免每轮都精确计算所有 block 的边际增益，从而大幅减少实际评估次数，这也是在 ImageNet 上 8 天内完成搜索的关键之一。

整体来看，把资源受限的 NAS 理解为次模函数约束最大化，不仅给贪心算法提供了理论依据，也让约束的处理更加自然——不需要手动调整惩罚权重，而是直接在组合优化框架里处理计算量限制。这个视角在 NAS 的文献里并不常见，值得记录下来。