资源受限 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)$

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

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

\mathcal{A} \subseteq \mathcal{B} \subseteq \mathcal{V},\ F(\mathcal{A}) \leq F(\mathcal{B}).

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

将 NAS 映射到次模框架

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

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

F(\mathcal{A}) \leq F(\mathcal{B}) \text{ for any } \mathcal{A} \subseteq \mathcal{B} \subseteq \mathcal{V}.

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

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

Lemma 1. For any selected blocks $\mathcal{A} \subseteq \mathcal{B} \subseteq \mathcal{V}$ and block $v \in \mathcal{V} \setminus \mathcal{B}$ , it holds that:

\begin{aligned} F(\mathcal{A}) &\geq 0 \\ F(\mathcal{A} \cup \{v\}) - F(\mathcal{A}) &\geq 0 \\ F(\mathcal{A} \cup \{v\}) - F(\mathcal{A}) &\geq F(\mathcal{B} \cup \{v\}) - F(\mathcal{B}) \end{aligned}

这个定理说明了两件事：

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

贪心算法及其近似保证

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

Algorithm 1: Cost-Effective Greedy CNN Search (CEG)

function CEG(V, F, B, c(·))
    S ← argmax_{v ∈ V} F(v) / c(v)
    while c(S) ≤ B do
        v* = argmax_{v ∈ V \ S} (F(S ∪ {v}) − F(S)) / c(v)
        S ← S ∪ {v*}
    end while
    return S
end function

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

进一步节省计算量

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

Algorithm 2: Lazy Cost-Effective Greedy Search

function LAZY-CEG(V, F, B_p, B_m, c(·))
    S ← ∅
    PriorityQueue Q ← PriorityQueue()
    for all v ∈ V do                                  ▷ First iteration
        if Param(v) ≤ B_p AND MAdds(v) ≤ B_m then
            Q.push({v, F(v) / c(v)})
        end if
    end for
    S ← S ∪ {Q.pop()}
    while ∃ v ∈ Q : Param(S ∪ {v}) ≤ B_p AND MAdds(S ∪ {v}) ≤ B_m do   ▷ Lazy update
        v* ← Q.pop()
        if v* ∈ V \ S then
            if (F(S ∪ {v*}) − F(S)) / c(v*) ≥ (F(S ∪ {Q.top()}) − F(S)) / c(v) then
                S ← S ∪ {v*}
            else
                Q.push({v*, (F(S ∪ {v*}) − F(S)) / c(v*)})
            end if
        end if
    end while
    return S
end function

Algorithm 3: Resource Constrained Architecture Search (RCAS)

function RCAS(V, F, B_p, B_m)
    S̃_UC  ← LAZY-CEG(V, F, B_p, B_m, const(·))
    S̃_APR ← LAZY-CEG(V, F, B_p, B_m, Param(·))
    S̃_AMR ← LAZY-CEG(V, F, B_p, B_m, MAdds(·))
    return argmax{S̃_UC, S̃_APR, S̃_AMR}
end function

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

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

论文笔记
NAS
优化算法

2019 · 04 · 10