Tools for sparse Bayesian deep learning
Yves Atchadé
Boston University

joint work with:
Liwei Wang, Boston University

Introduction
1. deep learning (DL) models have tremendous approximation
power. But estimation (training) requires lot of data.
2. In data-poor areas, domain knowledge and sparsity may help.

3. The talk discusses two ideas towards that goal: Cyclical
MCMC and asynchronous MCMC.

Cyclical MCMC
Asynchronous MCMC
Experimentation with deep learning models

1.2

Cyclical MCMC

0.0

0.2

0.4

0.6

0.8

1.0

beta=1
beta=0.1
beta=0.01-3-2-10

123x

1. ’Annealing’ / ’tempering’. Let E : X → R with minimum set
M. Setπt (x) ∝ exp (−βt E(x)) , βt > 0.
2. As βt ↑ ∞, πt (·) ≈ π∞ (·) = |·∩M||M| .

Cyclical MCMC

1. Combined with the Metropolis algorithm and we get
Simulated Annealing (SA)

2. For well-designed nonhom. Markov chain {Xt , t ≥ 0} withkernels {Pt , t ≥ 0} with πt Pt = πt , and well-chosen sequence
βt ,P(Xt ∈ ·) − πt (·) ≈ 0.

Cyclical MCMC1. It became quickly clear to the MCMC pioneers that the idea
behind SA can be used also to sample from a distribution ofinterest π by annealing up to 1.
2. Led to parallel tempering (PT) that targetsπ̄(x1 , . . . , xK ) ∝KY

π(xk )βk .

k=1

3. And simulated tempering (ST) that targets
π(k, x) ∝ exp (−βk E(x)) /ck .

Cyclical MCMC

1. Unlike SA which remains a mysterious metaheuristics withsome theoretical backing, PT and ST benefits from the rigorof MC theory.
2. However these algorithm come with a higher computational
price. Costly to use for DL.
3. With Cyclical MCMC, we go back to the original SAframework.

Cyclical MCMC
1. Let β : [0, 1] → R such that β0 = β1 = 1, βt ↘↗.
1

0.8

0.6

0.4

0.2

00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

2. We extend t 7→ βt to R → R by periodic extension.
3. Let π(x) ∝ e −E(x) a density of interest. For k ≥ 0, we defineπk (x) ∝ exp −β(k/L) E(x) .
4. Cyclical: πk+jL = πk .

Cyclical MCMC

1. Let Pk be a Markov kernel with invariant distribution πk .
2. The Cyclical MCMC sampler is a nonhomog. Markov chain{Xk , k ≥ 0} with sequence of transition kernels {Pk , k ≥ 1}.
3. We collect samples at times jL, j = 0, 1, . . ..

Cyclical MCMC
1. The Cyclical MCMC sampler is a nonhomog. Markov chain{Xk , k ≥ 0} with sequence of transition kernels {Pk , k ≥ 1}.
2. By periodicity, its can also be viewed as a homogeneous MC{XjL , j ≥ 0} with transition kernelP1 × · · · × PL .
3. Intuition: for well-chosen β, K has very good mixing: for1 ≤ ℓ ≤ L:
{P1 × · · · × Pℓ } (x, ·) − πℓ (·) ≈ 0.
4. Existing results towards that includes Holley & Stroock(1991), Douc et al. (2004), Narayanan & Rakhlin (2017),Andrieu et al. (2018).
5. Computationally the algorithm is very efficient.

Cyclical MCMC: illustration
1.

25

1 Xπ(x) =N (x|µi , Σ).
25i=1

2. We compare MaLa, cyclical MaLa, SGLD, cyclical SGLD.
3. 150,000 total iterations split into 300 cycles. Collect samples
at end of cycles.
samplerSDMALA
29.52 ± 6.89

cMALA
4.75 ± 0.54

ULA
29.11 ± 7.44

cULA
4.57 ± 0.34

Table: standard deviation of number of samples in each modeCyclical MCMC: illustration
cyclical MALA
4

3

322

1

10yy

MALA
40-1-1-2-2-3-3-4-4-4-20

2

4-4-2x
50

2

424x

sgld

cyclical sgld
432yy

100-1-2-3-4-5-50x

5-4-20x

Figure: scatter plots of different method in 25 gaussian mixtures

Cyclical MCMC

1. On-going work. The cosine cycles works well. But cycle
lengths requires careful tuning.
2. We need more theory.

Cyclical MCMC
Asynchronous MCMC
Experimentation with deep learning models

Asynchronous MCMC for Bayesian sparse deep learning▶ The Gibbs sampler is a hallmark of MCMC methods.
▶ A density π(x1 , x2 ) on X = X1 × X2 .
▶ Let π1 (·|x2 ) and π2 (·|x1 ) the two conditional distributions.

Algorithm (Gibbs Sampler)(k)(k)

1. At the k-th iteration, given X (k) = (X1 , X2 ) = (x1 , x2 ).
1.1 Draw X̄1 ∼ π1 (·|x2 ), and then draw X̄2 ∼ π2 (·|X̄1 ).

2. Set X (k+1) = (X̄1 , X̄2 ).

▶ Asynchronous Gibbs sampler is a modification of the Gibbs
sampler where new random draws are not automaticallybroadcast.

Asynchronous MCMC for Bayesian sparse deep learning▶ Asynchronous MCMC was first introduced to the best of myknowledge in the 80’s in the CS community as a way of
speeding up simulated annealing.
▶ Resurfaced again recently in machine learning
1. Smola and Narayanamurthy (2010) An architecture for parallel
topic models. Proc. VLDB Endow.
2. De Sa et al. (2016) Ensuring rapid mixing and low bias forasynchronous gibbs sampling. ICML 2016 - Volume 48.
3. Terenin and Xing (2018). Technique for proving Asynchronous
convergence results for MCMC. NIPS 2017.

Asynchronous MCMC for Bayesian sparse deep learning▶ Asynch. Gibbs sampling does not maintain the correct
invariant distribution.
▶ For a ∈ [0, 1], suppose that X = {0, 1} × {0, 1}, andπ(0, 0) = 0, π(0, 1) = π(1, 0) =0100(1-a)/2

1−a,2π(1, 1) = a.

1
(1 − a)/2a▶ If X̃ (k) = (1, 1),
P X

(k+1)

= (0, 0)|X(k)  1 − a 2
= (1, 1) =,1+awhich will produce a biased sampling asymptotically.

Asynchronous MCMC for Bayesian sparse deep learninga = 0.1
0.45

a = 0.8
0.9

0.4

0.8

0.35

0.7
0.3
0.6
0.25
0.5
0.2
0.4
0.15

0.3

0.1

0.2

0.05

0.1

00
(0,0)

(0,1)

(1,0)

(1,1)

(0,0)

(0,1)

(1,0)

(1,1)

Figure: Gibbs sampler versus asynchronous Gibbs sampler for a = 0.8 anda = 0.1.

▶ The bias is essentially∥π1|2 (·|1) − π1|2 (·|0)∥tv = (1 − a)/(1 + a).
▶ De Sa et al. (2016) formalized this using Dobrushin
coefficient.

Asynchronous MCMC for Bayesian sparse deep learning▶ Suppose we have a log-likelihood functionℓ(θ) = ℓ(θ, D) =nXfθ (zi ), θ ∈ Rp .

i=1

▶ We use a spike and slab prior for θ: for u > 1,0 < ρ1 < ρ0 < ∞:
N(0, ρ1−1 )dind−uδj ∼ Ber(p ), θj |δ = θj |δj ∼N(0, ρ0−1 )if δj = 1
if δj = 0

Asynchronous MCMC for Bayesian sparse deep learning

The posterior distribution can be written asΠ(δ, θ|D) ∝ r −∥δ∥0 ρρ1
ρ10pu
exp − ∥θ − θδ ∥22 − ∥θδ ∥22 + ℓ(θδ )ρ022▶ Asynchronous MCMC algorithm for Π:
1. fix δ and update θ (using SGLD or standard MCMC update);
2. fix θ and update J components of δ (using asynchronousGibbs).

Asynchronous MCMC for Bayesian sparse deep learning
Why should asynchronous update work here?
▶ We haveΠj (δj |δ−j , θ, D) ∼ Ber(qj ),where qj is driven mainly by u log(p) and the log-likelihood
ratioℓ(θδ(j,0) ) − ℓ(θδ(j,1) ) ≈ −θj ∇j ℓ(θδ(j,0) ) −θj22(2)∇jj ℓ(θ̄).

▶ To illustrate, assume logistic regression.
∇j ℓ(θ) =n X
Yi −i=1− (θj − θ⋆j )e ⟨θ,xi ⟩1 + e ⟨θ,xi ⟩nXi=1xij =Di (θ̄)x2ii −n XYi −i=1X
k̸=j(θk − θ⋆k )e ⟨θ⋆ ,xi ⟩1 + e ⟨θ⋆ ,xi ⟩nXi=1xijDi (θ̄)xij xik .

Asynchronous MCMC for Bayesian sparse deep learning

Algorithm (Asynch. Sparse SGLD (AS-SGLD))
1. fix δ and update θ (using Stochastic Gradient Langevindynamics – SGLD);
2. Given θ, select J components, for ϑ, and computeG = ∇ℓ(θϑ ). Draw independentlyδJk ∼ Ber(qJk ), qJk =e a0 (θJk )1 + a (θ ) e −θJk GJk
e 1 Jk!−1.

Approximate correctness for linear regressionℓ(θ) = −1∥y − X θ∥22 , θ ∈ Rp ,2σ 2

σ 2 > 0 known .

(1)

Theorem
Under classical high dim. lin. regr. assumptions and
32
3n ≳ max θ−2⋆ (1 + s⋆ ) log(p), J log(p), (log(p)) ,and u ≥ C2 (1 + s⋆ )2 , (2)E⋆(k)P(δj = 1) − Π(δj = 1|D)

maxj: δ⋆j =1≤k 10p√3 J
1−+ exp −C3 θ⋆ n + C4 J log(p) + .
10 ppwith probability at least 1 − 10/p (over the data).

Logistic regression

p = 5000, high correlation
0.9

0.9

0.8

0.8

0.7

Relative Error

Relative Error

p = 1000, high correlation
10.7
0.6
0.5

0.6
0.5
0.4

0.4

0.3

0.3

0.2
0.1

0.2
Exact

Asyn

SA-SGLDVA

S-Gibbs

Exact

Asyn

SA-SGLDVA

S-Gibbs

Figure: Relative error for logistic regression model. Based on 50
replications.

Logistic regression

p/n
Exact
Asyn
SA-SGLD
Skinny-Gibbs
VA

Complexity/iteration
O(nJ∥δ (k) ∥0 )O(n(∥δ (k) ∥0 + J))
O(B(∥δ (k) ∥0 + J))
O(n(p ∨ ∥δ (k) ∥20 ))O(B · J · p)

1000/500
5.25s
0.71s
0.24s
10.50s
4.05s

2000/1000
35.13s
2.19s
1.44s
87.27s34.42sTable: Running times to convergence

5000/2500
1360.09s
99.04s30.12s1154.40s
1243.82s

Cyclical MCMC
Asynchronous MCMC
Experimentation with deep learning models

Experimentation with deep learning models▶ Lenet-5 and a baby VGG-16 architectures.
▶ Using MNIST-FASHION and Cifar-10 datasets.
▶ The goal is to classify small images.

Experimentation with deep learning models

0.85

Accuracy 0.94
Sparsity0.92

0.84

0.90

0.45

0.88

0.40

2550

75

100u125

150

Accuracy/Sparsity of VGG on cifar10

0.75

1.00
0.99

0.70

0.98
0.97
Accuracy
Sparsity 0.96
0.95

1 - Sparsity

Accuracy

175

0.65
0.60

0.94
0.55

0.93
2550

75

100u125150

175

2000.92

200

Accuracy

0.86

1 - Sparsity

Accuracy

0.96

00.98

0.60

0.87

0.83

1.00

0.65

0.98

0.88

0

Accuracy/Sparsity of Lenet-5 on cifar10

1.00

0.96
1 - Sparsity

Accuracy/Sparsity of Lenet-5 on fashion-MNIST
0.89

0.55

Accuracy 0.94
Sparsity
0.92

0.50

0.900.88
02550

75100
u125150

1752000.86

Experimentation with deep learning models

Sparsity of each layer in Lenet-5(left) and VGG(right)
plain SA-SGLD

1.00

1.0

plain SA-SGLD

0.99
0.98

0.8

Sparsity

Sparsity

0.9

0.7

0.97
0.96
0.95

0.6

0.94
Conv1

Conv2

Dense1

Dense2

Dense3

Conv1 Conv2 Conv3 Conv4 Conv5 Conv6 Dense1 Dense2

Experimentation with deep learning models

SGD with Momentum
SGLDcSGLD
plain SA-SGLD, u = 50
SA-cSGLD, u = 50
SA-SGLD, 10 chains, u = 50

Accuracy
0.764
0.80290.80420.727
0.758
0.745

Table: VGG-6 with Cifar-10 dataset

Density1110.0047
0.00650.0058Experimentation with deep learning models

We compare
Ent pWc (·|x) , and Ent
1.0

0.8

0.8

0.6
0.4
0.2

SA-cSGLD
SGD with momentum
SGD, deep ensemble

0.0
0.0

0.5

1.0

Entropy

1.5

2.02.5pW (·|x)Π(dW |D) .

out-of-distribution predictive Entropy of cifar100 dataset

1.0

Emperical CDF

Emperical CDF

in-distribution predictive Entropy of cifar10 dataset

Z

0.6
0.40.2SA-cSGLD
SGD with momentum
SGD, deep ensemble

0.0
0.0

0.5

1.0

Entropy

1.5

2.0

2.5

Concluding thoughts▶ We have presented two approximate MCMC ideas that wehave found very useful for large scale sparse Bayesianmodeling.
▶ Particularly in low-data and noisy-data settings.
▶ More theoretical analysis is needed.
▶ In the context of DL, software and hardware to takeadvantage of sparsity is also needed.

Thanks!!