Sparse Bayesian learning

Overview

Sparse Bayesian learning gives each weight its own prior variance and lets the data decide how large that variance should be. A weight whose variance shrinks towards zero is effectively removed from the model. The paper frames architecture search as this kind of sparse learning over an over-parameterised network, where each candidate operation on an edge is one weight [arxiv:1905.04919 §3] 1905.04919 §5.1.

The prior is hierarchical. Each variance has a Gamma hyper-prior, which yields a Student-t marginal and favours sparsity. The paper sets the hyper-prior parameters to zero, which makes them flat 1905.04919 §5.1. The variance of an edge is also tied to the switches of the edges that feed into the same node, so a node whose inputs are switched off also weakens the variance of the edges it would feed 1905.04919 §4.1 1905.04919 eq. 6.

Pruning uses the posterior variance, not the weight magnitude. The paper states that magnitude depends on weight scale and on the architecture choice, which is why it prefers the variance-based rule 1905.04919 §1 1905.04919 §2. A Laplace approximation with a Hessian term gives the posterior update 1905.04919 §5.2.

Variants

Cell-based architecture search (BayesNAS)

Sparse Bayesian learning over the operations of a cell. The search trains an over-parameterised network for a short time, updates the variances once per iteration, and prunes edges whose variance is at most 1/(2\pi e) 1905.04919 §5.3 1905.04919 alg. 1. The reported CIFAR-10 test error is 2.81% for the variant with \lambda_w = 0.005, with cutout and an author-reported search cost of 0.2 GPU days 1905.04919 tab. 1. Card: BayesNAS: A Bayesian Approach for Neural Architecture Search.

Proxy and proxyless search

Proxy search ties switches and re-weighting coefficients within a group of identical cells, so the search is on a smaller network that is then transferred 1905.04919 app. S1.3. Proxyless search runs the same procedure on each cell separately, using a PyramidNet backbone with a tree cell of nine paths 1905.04919 §6.2. The paper reports 2.41% CIFAR-10 test error for the proxyless variant with a reported search cost of 0.1 GPU days 1905.04919 tab. 1. These are author-reported numbers.

Structural compression of trained networks

The same machinery prunes groups of weights in a trained network: shape-wise, row-wise, column-wise or filter-wise groups, using a re-weighted group Lasso 1905.04919 app. S2 1905.04919 app. S2.1. The paper reports results for LeNet-300-100, LeNet-5 and ResNet-18 that trade a small error increase for fewer FLOPs in the MNIST cases 1905.04919 app. S2.2. The MNIST and CIFAR-10 results report no spread across runs.

When to use which

Implementation sketch

Adapted from the search loop in the paper. Variants differ in how switches are tied (cell-based vs proxy), in the Hessian approximation, and in whether the loop is over architecture weights or over the groups of a trained network.

# Sparse Bayesian search over one over-parameterised network  [alg. 1]
# Initialise architecture weights, variances and l1 weights to 1  [alg. 1]
arch, gamma, omega = ones(n), ones(n), ones(n)
for t in range(1, T + 1):
    # Train weights on the re-weighted loss; schedule not stated  [§5.3]
    net, arch = sgd_step(data, net, arch, lambda_w * omega)
    # Hessian of each architecture weight, from cached feature maps  [app. S3]
    hess = architecture_hessian(net, arch, data)
    # Posterior variance, using the previous gamma  [alg. 1]
    post = 1 / (1 / gamma + hess)
    # Re-weighting coefficient for the next l1 step  [alg. 1]
    omega = sqrt(gamma - post) / gamma
    # Switch of each architecture weight  [alg. 1]
    switch = abs(arch / omega)
    # Variance from the predecessor switches and the own switch  [eq. 6] [§4.1]
    gamma = 1 / (1 / pred_sum(switch) + 1 / switch)
# Keep edges whose entropy is positive  [§5.3]
keep = gamma > 1 / (2 * pi * e)

Notes: the number of iterations T is not stated for the CIFAR-10 search 1905.04919 §5.3. The paper does not say which Hessian approximation the experiments use 1905.04919 app. S3.1 1905.04919 app. S3.2.

Contradictions

Only one card covers this slug, so there are no disagreements between papers. Within BayesNAS, the reported numbers are inconsistent in three places, and each side is cited:

• Search cost: 0.2 GPU days in the abstract and 1905.04919 tab. 1, against "about 3 hours on a single GPU" in 1905.04919 §6.1.
• Search batch size: 18 in the main text 1905.04919 §6.1, 16 in the appendix 1905.04919 app. S4.1.
• Exact FC-layer Hessian cost: the formula gives about 8.03 M operations for n = m = 100, while the text states 107.97 M 1905.04919 app. S3.1.

Papers

• BayesNAS: A Bayesian Approach for Neural Architecture Search: applies sparse Bayesian learning with a hierarchical ARD-style prior to one-shot architecture search and structural compression.