A Regret Bound for Online
Variational InferenceBadr-Eddine Chérief-Abdellatif, Pierre Alquier, Emtiyaz KhanENSAE Paris & RIKEN AIP
B.-E. Chérief-Abdellatif and E. Khan

SVA & SVB are tractable, and not equivalent
2

Example: Gaussian prior θ ∼ π = N (0, s I ) and mean-field Gaussian
approximation, µ = (m, σ).

Approximate Bayesian Inference teamhttps : //emtiyaz.github.io/

gt+1 ← gt + ḡσt ,SVA: mt+1 ← mt − ηs 2ḡmt ,σt+1 ← h (ηsgt+1) s,SVB: mt+1 ← mt − ησt2ḡmt ,σt+1 ← σt h (ησt ḡσt )√where h(x) := 1 + x 2 − x is applied componentwise, as well as themultiplication of two vectors, and∂∂Eθ∼πmt ,σt [`t (θ)] and ḡσt =Eθ∼πmt ,σt [`t (θ)].
ḡmt =∂m∂σOnline gradient algorithm (OGA)
Theoretical analysis of SVA
Given
a set of predictors {fθ , θ ∈ Θ ⊂ Rd }, e.g fθ (x) = hθ, xi,
an initial guess θ1,),y)ŷt = fθt (xt ) and θt+1 = θt − η∇θ |`(fθt (x.
tt{z}=`t (θ)Note (*that θt+1 can be obtainedby:+)t2Xkθ − θ1k∇θ `s (θs ) +min
θ,,θ2η
s=1()
DE kθ − θ k2tmin
θ, ∇θ `t (θt ) +.
θ2η

Theorem: Under convexity and L-Lipschitz assumption on the loss, underα-strong convexity assumption on the KL term, SVA leads toTTX
X
ηL2TKL(qµ, π) Eθ∼qµt [`t (θ)] ≤ infEθ∼qµ[`t (θ)] ++.
µ∈M αη
t=1t=1Application to Gaussian approximation leads toTTXX2L pdT log(T ).
Eθ∼qµt [`t (θ)] ≤ inf`t (θ) + (1 + o(1))
θα
t=1
t=1
Theoretical analysis of SVB

Bayesian learning and variational inference (VI)

πt+1(θ) := π(θ|x1, y1, . . . , xt , yt ) ∝ exp −ηtX!
`s (θ) π(θ).

s=1

Not tractable in general, leading to variational approximations:π̃t+1(θ) = arg min KL(q, πt+1)q∈F" t#()XKL(q, π)`s (θ) += arg min Eθ∼q.
ηq∈F
s=1
Formula for the online update of πt+1:

Theorem: Using Gaussian approximations, assuming the loss is convex,
L-Lipschitz and the parameter space bounded (diameter = D), SVB withadequate η leads toTTXX√`t Eθ∼qµt (θ) ≤ inf`t (θ) + DL 2T .
θ

t=1

t=1

If, moreover, the loss is H-strongly convex,TT
2X
X
L (1 + log(T )).
`t Eθ∼qµt (θ) ≤ inf`t (θ) +θH
t=1
t=1
Test on a simulated dataset

πt+1(θ) ∝ exp (−η`t (θ)) πt (θ).
Q1: can we similarty define a sequential update for a variational
approximation?
Regret bounds for Bayesian inference
Theorem: Under the assumption that the loss is bounded by B, theBayesian update leads to
TT
X2X
ηB TKL(q, π)Eθ∼πt [`t (θ)] ≤ infEθ∼q [`t (θ)] ++.
q 
8
η
t=1
t=1
√
Derivation of the infimum and η ∼ T “usually” leads toTTX
Xp
Eθ∼πt [`t (θ)] ≤ inf`t (θ) + O( dT log(T )).
t=1

θt=1

Q2: can we derive similar results for online VI?
Two options for online VIParametric VI: F = {qµ, µ ∈ M}.
Sequential Variational Approximation (SVA):(*+)
tXKL(qµ, π)µt+1 = arg minµ,∇µEθ∼qµs [`s (θ)] +.
ηµs=1Streaming Variational Bayes (SVB):D
E KL(q , q ) µµt
µt+1 = arg minµ, ∇µEθ∼qµt [`t (θ)] +.
ηµ
http://alquier.ensae.net/

Figure: Average cumulative losses on different datasets for classification and regression
tasks with OGA (yellow), OGA-EL (red), SVA (blue), SVB (purple) and NGVI (green) forthe convex hinge loss and the squared loss functions. The black line shows the average
total cumulative loss in hindsight. We see that in most cases NGVI outperforms the otheralgorithms. The last plot (California Housing dataset) shows the consistency of ouralgorithms for a nonconvex loss L̄t .

Open questions
Analysis of SVB in the general case.
Analysis of the uncertainty quantification.
NGVI is the next step in going closer to algorithms used to train Neural Networks with Bayesian principles. But being based on a different parametrization, it does not satisfy our convexity assumption...
Uses exponential family approximations {qµ, µ ∈ M} where m is the meanparameter. Denoting λ the natural parameter (with λ = F (µ)),λt+1 = (1 − ρ)λt + ρ∇µEθ∼qµt [`t (θ)] ,M. E. Khan, D. Nielsen (2018). Fast yet Simple Natural-Gradient Descent for
Variational Inference in Complex Models. ISITA.

pierre.alquier.stat@gmail.com