Generalized Bayes update
Online variational inference

Regret bounds for generalized Bayes
updates
Pierre AlquierAI seminar series – UCL AI Centre – May 19, 2021

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
11

x1 given

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
11
2

x1 given
predict y1 : ŷ1

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

x1 given
predict y1 : ŷ1
y1 is revealed

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
13

x1 given
predict y1 : ŷ1
y1 is revealed

1x2 given

1
2

2

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

1
2

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

1
2
3

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

3

x2 given
predict y2 : ŷ2y2 revealed

1x3 given

1
2

3

x1 given
predict y1 : ŷ1
y1 is revealed

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

1
2
3

3

1
2

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

1
2
3

3

1
2
3

4

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3
y3 revealed...

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

1
2
3

3

1
2
3

4

x1 given
predict y1 : ŷ1
y1 is revealed

Objective :x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3
y3 revealed...

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

1
2
3

3

1
2
3

4

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed

Objective : make sure that
we learn to predict well assoon as possible.

x3 given
predict y3 : ŷ3
y3 revealed...

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The sequential prediction problem
Sequential prediction problem
1

1
2
3

2

1
2
3

3

1
2
3

4

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3
y3 revealed

Objective : make sure that
we learn to predict well assoon as possible. KeepT
X`(ŷt , yt )t=1

as small as possible.

...

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

1st approach : “follow the regularized leader”
set of predictors : {fθ , θ ∈ Θ}.
`t (θ) := `(fθ (xt ), yt )).

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

1st approach : “follow the regularized leader”
set of predictors : {fθ , θ ∈ Θ}.
`t (θ) := `(fθ (xt ), yt )).
Follow The Regularized Leader – FTRL
( t−1
)
X
pen(θ)
θt := arg min`s (θ) +.
ηθ
s=1

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

1st approach : “follow the regularized leader”
set of predictors : {fθ , θ ∈ Θ}.
`t (θ) := `(fθ (xt ), yt )).
Follow The Regularized Leader – FTRL
( t−1
)
X
pen(θ)
θt := arg min`s (θ) +.
ηθ
s=1
Quadratic penalty + linearization :
)
( t−1
2
X
kθk
θt := arg min.
hθ, ∇`s (θs )i +2ηθ
s=1
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

1st approach : “follow the regularized leader”
set of predictors : {fθ , θ ∈ Θ}.
`t (θ) := `(fθ (xt ), yt )).
Follow The Regularized Leader – FTRL
( t−1
)
X
pen(θ)
θt := arg min`s (θ) +.
ηθ
s=1
Differentiate : blablablablablablabla
0=

t−1
X

∇`s (θs ) +s=1

Pierre Alquier, RIKEN AIPθt.
η

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

1st approach : “follow the regularized leader”
set of predictors : {fθ , θ ∈ Θ}.
`t (θ) := `(fθ (xt ), yt )).
Follow The Regularized Leader – FTRL
( t−1
)
X
pen(θ)
θt := arg min`s (θ) +.
ηθ
s=1

Online Gradient Algorithm – OGA
θt := θt−1 − η∇`t−1 (θt−1 ).
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Theoretical properties of FTRL & OGA

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

2nd approach : (generalized) Bayes

Generalized Bayes, multiplicative
weights, Exponential Weight
Aggregation (EWA)...
EWA"ρt (θ) ∝ exp −η

t−1
X

#
`s (θ) π(θ)

s=1Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

2nd approach : (generalized) Bayes

Generalized Bayes, multiplicative
weights, Exponential Weight
Aggregation (EWA)...
EWA"ρt (θ) ∝ exp −η

t−1
X

#
`s (θ) π(θ)

s=1Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

EWA as FTRL
It is known thatρt = arg min






t−1
X

Eθ∼ρ [`s (θ)] +{z }ρ∈P(Θ)  s=1 |


=:Ls (ρ)

KL(ρkπ) 
η
{z

|
=:

.



}

pen(ρ) η

That is, EWA is a special case of FTRL.



dρ
Eθ∼ρ log dπ(θ) if ρ  πKL(ρkπ) =+∞ otherwise.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

1st objective

We will study a more general version of FTRL on ρ :
( t−1
)
X
D(ρkπ),
ρt = arg minEθ∼ρ [`s (θ)] +ηρ∈P(Θ)
s=1
for more general divergences D.
P. Alquier. Non-exponentially Weighted Aggregation : Regret Bounds for Unbounded Loss
Functions. Accepted for ICML 2021.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

2nd objective

EWA is often non feasible in practice. We will thus modify it :we will constrain ρt to belong to a feasible set of probability
distributions (e.g. : Gaussian).

B.-E. Chérief-Abdellatif, P. Alquier, M. E. Khan (2019). A regret bound for online variational
inference. 11th Asian Conference on Machine Learning (ACML).

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Co-authors
Badr-Eddine
Chérief-Abdellatif

Emtiyaz Khan

Approximate Bayesian Inference teamhttps : //team − approx − bayes.github.io/

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

1

Generalized Bayes update
Formula for the posterior : non-exponential weights
Regret bound2

Online variational inference
The algorithms : SVA and SVB
Regret bounds

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret bound1

Generalized Bayes update
Formula for the posterior : non-exponential weights
Regret bound2

Online variational inference
The algorithms : SVA and SVB
Regret bounds

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundReminderρt = arg minρ∈P(Θ)( t−1X

Dφ (ρkπ)Eθ∼ρ [`s (θ)] +η
s=1

Pierre Alquier, RIKEN AIP),

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundReminderρt = arg min

( t−1
X

Dφ (ρkπ)Eθ∼ρ [`s (θ)] +η
s=1ρ∈P(Θ)

)
,

where

Dφ (ρkπ) = dρ 
Eθ∼π φ dπ(θ) if ρ  π+∞ otherwise,and φ : R+ → R ∪ {+∞} with :φ convex,
φ(1) = 0,
inf x≥0 φ(x) > −∞.
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundDifferential of the convex conjugate
Assume that φ is differentiable, strictly convex. Putφ(x) if x ≥ 0,
φ̃(x) =+∞ if x < 0.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundDifferential of the convex conjugate
Assume that φ is differentiable, strictly convex. Putφ(x) if x ≥ 0,
φ̃(x) =+∞ if x < 0.
Thenφ̃∗ = sup[xy − φ̃(x)] = sup[xy − φ(x)]
x≥0

x∈R

is differentiable and for any y ∈ R,∇φ̃∗ (y ) = arg max {xy − φ(x)} .
x≥0

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundFormula for ρt
Assume moreover that φ̃∗ (λ − a) − λ → ∞ when λ → ∞, for
any a ≥ 0. Then :
!
)
(Z
t−1
X
∗
`s (θ) π(dθ) − λλt = arg minφ̃ λ − ηλ∈R

s=1exists, andρt (dθ) = ∇φ̃∗ λt − η

t−1
X

!
`s (θ) π(dθ).

s=1Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe classical example : KL and exponential weights
φ(x) = x log(x),Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe classical example : KL and exponential weights
φ(x) = x log(x),φ̃∗ (y ) = exp(y − 1),

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe classical example : KL and exponential weights
φ(x) = x log(x),φ̃∗ (y ) = exp(y − 1),∇φ̃∗ (y ) = exp(y − 1),

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe classical example : KL and exponential weights
φ(x) = x log(x),φ̃∗ (y ) = exp(y − 1),∇φ̃∗ (y ) = exp(y − 1),"ρt (dθ) = exp λt − η

t−1
X

#
`s (θ) − 1 π(dθ).

s=1Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe classical example : KL and exponential weights
φ(x) = x log(x),φ̃∗ (y ) = exp(y − 1),∇φ̃∗ (y ) = exp(y − 1),"ρt (dθ) = exp λt − η

t−1
X

#
`s (θ) − 1 π(dθ).

s=1

h P
i
t−1
exp −η s=1`s (θ) π(dθ)
h Piρt (dθ) = R.
exp −η t−1
`
(ϑ)
π(dϑ)
s=1 s

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe χ2 divergence

φ(x) = x 2 − 1,

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe χ2 divergence

φ(x) = x 2 − 1,φ̃∗ (y ) = (y 2 /4)1{y ≥0} ,Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe χ2 divergence

φ(x) = x 2 − 1,φ̃∗ (y ) = (y 2 /4)1{y ≥0} ,∇φ̃∗ (y ) = (y /2)+ ,Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundThe χ2 divergence

φ(x) = x 2 − 1,φ̃∗ (y ) = (y 2 /4)1{y ≥0} ,∇φ̃∗ (y ) = (y /2)+ ,"ρt (dθ) =λt − η

Pierre Alquier, RIKEN AIP

Pt−1

s=1 `s (θ)2#π(dθ).
+

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundSome references
the formula was known for a finite Θ :M. D. Reid, R. M. Frongillo, R. C. Williamson, N. Mehta (2015). Generalized mixability via
entropic duality. COLT.
the proof for the general case relies on :R. Agrawal, T. Horel (2020). Optimal bounds between f -divergences and integral probability
metrics. ICML.
comparable PAC-Bayes bounds (no online update) :P. Alquier and B. Guedj (2018). Simpler PAC-Bayesian bounds for hostile data. Machine Learning.
defense of the generalized Bayes update :J. Knoblauch, J. Jewson, T. Damoulas (2019). Generalized variational inference : Threearguments for deriving new posteriors.. Preprint arXiv.
more : see the paper.
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundGeneral regret boundAssume there is a norm k · k such that

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundGeneral regret boundAssume there is a norm k · k such thatρ 7→ Eθ∼ρ [`t (θ)] is L-Lipschitz w.r.t k · k,

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundGeneral regret boundAssume there is a norm k · k such thatρ 7→ Eθ∼ρ [`t (θ)] is L-Lipschitz w.r.t k · k,
ρ 7→ Dφ (ρkπ) is α-strongly convex w.r.t k · k.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundGeneral regret boundAssume there is a norm k · k such thatρ 7→ Eθ∼ρ [`t (θ)] is L-Lipschitz w.r.t k · k,
ρ 7→ Dφ (ρkπ) is α-strongly convex w.r.t k · k.
TheoremTX
t=1

Eθ∼ρt [`t (θ)] ≤ inf( TXρ∈P(Θ)

Eθ∼ρ [`t (θ)]

t=1

)
ηL2 T
Dφ (ρkπ)++.
αηPierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundBound for EWA : the conditions
known result : KL(ρkπ) is 1-strongly convex with respect
to k · kTV ;Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundBound for EWA : the conditions
known result : KL(ρkπ) is 1-strongly convex with respect
to k · kTV ;we have :
Z
Z
Z
dρ
dρ0
0
`t (θ)ρ(dθ) − `t ρ (dθ) ≤ `t (θ)(θ) −(θ) π(dθ)
dπ
dπ
Z
dρ0
dρ
≤L
(θ) −
(θ) π(dθ)
dπ
dπ
|
{z
}
=2kρ−ρ0 kTV

on the condition that 0 ≤ `t (θ) ≤ L for any θ.
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundBound for EWA

Assume 0 ≤ `t (θ) ≤ L for any θ, t, thenTX
t=1

Eθ∼ρt [`t (θ)] ≤ inf( TXρ∈P(Θ)

Eθ∼ρ [`t (θ)]t=1)
KL(ρkπ)+ ηL2 T +.
η

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundBound for EWA

Assume 0 ≤ `t (θ) ≤ L for any θ, t, thenTX
t=1

Eθ∼ρt [`t (θ)] ≤ inf( TXρ∈P(Θ)

Eθ∼ρ [`t (θ)]t=1)
KL(ρkπ)+ ηL2 T +.
η(This is a well-known result).

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundBound with χ2 : the conditions
φ(x) = x 2 − 1 is 2-strongly convex so Dφ is 2-strongly
convex with respect to the L2 (π) norm.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundBound with χ2 : the conditions
φ(x) = x 2 − 1 is 2-strongly convex so Dφ is 2-strongly
convex with respect to the L2 (π) norm.
we have
Z
Z
Z
dρ
dρ0
0
`t (θ)ρ(dθ) − `t ρ (dθ) ≤ `t (θ)(θ) −(θ) π(dθ)
dπ
dπ
!1/2
2
Z 
0
dρ
dρ
≤L
(θ) −
(θ) π(dθ)
dπdπon the condition that

R

Pierre Alquier, RIKEN AIP`t (θ)2 π(dθ)

1/2

≤ L.

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

Formula for the posterior : non-exponential weights
Regret boundBound with χ2

AssumeTX
t=1

R`t (θ)2 π(dθ) ≤ L2 for any t, thenEθ∼ρt [`t (θ)] ≤ inf( TXρ∈P(Θ)

Eθ∼ρ [`t (θ)]

t=1

)
ηL2 T
χ2 (ρkπ)++.
2ηPierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

1

Generalized Bayes update
Formula for the posterior : non-exponential weights
Regret bound2

Online variational inference
The algorithms : SVA and SVB
Regret bounds

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Motivation
K. Osawa, S. Swaroop, A. Jain, R. Eschenhagen, R. E. Turner, R. Yokota, M. E. Khan (2019).
Practical Deep Learning with Bayesian Principles. NeurIPS.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Motivation
K. Osawa, S. Swaroop, A. Jain, R. Eschenhagen, R. E. Turner, R. Yokota, M. E. Khan (2019).
Practical Deep Learning with Bayesian Principles. NeurIPS.

1

2

3

proposes a fast algorithm
to approximate theposterior,applies it to train Deep
Neural Networks on
CIFAR-10, ImageNet ...
observation : improved
uncertainty quantification.
Picture : Roman Bachmann.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Motivation
K. Osawa, S. Swaroop, A. Jain, R. Eschenhagen, R. E. Turner, R. Yokota, M. E. Khan (2019).
Practical Deep Learning with Bayesian Principles. NeurIPS.

1

2

3

proposes a fast algorithm
to approximate theposterior,applies it to train Deep
Neural Networks on
CIFAR-10, ImageNet ...
observation : improved
uncertainty quantification.
Picture : Roman Bachmann.

Objective : provide a theoretical analysis of this algorithm.
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Sequential Variational Approximation (SVA)
We restrict ρ to belong to F = {qµ , µ ∈ M} a parametricfamily. Example : Gaussian distributions.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Sequential Variational Approximation (SVA)
We restrict ρ to belong to F = {qµ , µ ∈ M} a parametricfamily. Example : Gaussian distributions.
FTRL on this set :tµ = arg min
µ∈M

( t−1
X

Dφ (qµ , π)Eθ∼qµ [`s (θ)] +η
s=1

Pierre Alquier, RIKEN AIP).

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Sequential Variational Approximation (SVA)
We restrict ρ to belong to F = {qµ , µ ∈ M} a parametricfamily. Example : Gaussian distributions.
FTRL on this set :tµ = arg min

( t−1
X

µ∈M

Dφ (qµ , π)Eθ∼qµ [`s (θ)] +
η
s=1

)
.

Linearization gives :SVAµt = arg min
µ∈M

( t−1
X
s=1

Dφ (qµ , π)µ, ∇Eθ∼qµs [`s (θ)] +η

Pierre Alquier, RIKEN AIP).

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Streaming Variational Bayes (SVB)(OGA) can actually be obtained via :
)
( t−1
X
kθk2
t
s
θ := arg minhθ, ∇`s (θ )i +
2η
θ
s=1
OR


t

θ := arg minθ, ∇`t−1 (θθPierre Alquier, RIKEN AIPt−1

kθ − θt−1 k2
) +
2η



Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Streaming Variational Bayes (SVB)(OGA) can actually be obtained via :
)
( t−1
X
kθk2
t
s
θ := arg minhθ, ∇`s (θ )i +
2η
θ
s=1
OR


t

θ := arg minθ, ∇`t−1 (θθt−1kθ − θt−1 k2
) +
2η



SVB
t

µ = arg minµ∈MD

E D (q , q t−1 ) φ µ µµ, ∇Eθ∼qµt−1 [`t−1 (θ)] +.
η

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

SVA & SVB are tractable, and not equivalent
Example : Gaussian prior θ ∼ π = N (0, s 2 I ), Dφ = KL andmean-field Gaussian approximation, µ = (m, σ).
SVA : mt+1 ← mt − ηs 2 ḡmt ,σt+1 ← h (ηsgt+1 ) s,

gt+1 ← gt + ḡσt ,SVB : mt+1 ← mt − ησt2 ḡmt ,σt+1 ← σt h (ησt ḡσt )√where h(x) := 1 + x 2 − x is applied componentwise, as wellas the multiplication of two vectors, and∂Eθ∼πmt ,σt [`t (θ)],∂m∂ḡσt =
Eθ∼πmt ,σt [`t (θ)].
∂σ

ḡmt =

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVA
Two assumptions :1µ 7→ Eθ∼qµ [`t (θ)] is L-Lipschitz and convex.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVA
Two assumptions :1µ 7→ Eθ∼qµ [`t (θ)] is L-Lipschitz and convex.
Proposition
Assume θ 7→ `t (θ) is L/2-Lipschitz and convex, andµ = (m, Σ) is a location scale parameter, then : satisfied.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVA
Two assumptions :1µ 7→ Eθ∼qµ [`t (θ)] is L-Lipschitz and convex.
Proposition
Assume θ 7→ `t (θ) is L/2-Lipschitz and convex, andµ = (m, Σ) is a location scale parameter, then : satisfied.
Proof :
J. Domke (2019). Provable smoothness guarantees for black-box variational inference. NeurIPS.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVA
Two assumptions :1µ 7→ Eθ∼qµ [`t (θ)] is L-Lipschitz and convex.
Proposition
Assume θ 7→ `t (θ) is L/2-Lipschitz and convex, andµ = (m, Σ) is a location scale parameter, then : satisfied.
Proof :
J. Domke (2019). Provable smoothness guarantees for black-box variational inference. NeurIPS.

2µ 7→ Dφ (qµ , π) is α-strongly convex.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVA
Two assumptions :1µ 7→ Eθ∼qµ [`t (θ)] is L-Lipschitz and convex.
Proposition
Assume θ 7→ `t (θ) is L/2-Lipschitz and convex, andµ = (m, Σ) is a location scale parameter, then : satisfied.
Proof :
J. Domke (2019). Provable smoothness guarantees for black-box variational inference. NeurIPS.

2µ 7→ Dφ (qµ , π) is α-strongly convex.
For example true when qµ is Gaussian with µ = (m, Σ)and Dφ = KL.
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVA
Theorem
Under the previous assumptions SVA leads toTXEθ∼qµt [`t (θ)]
t=1

≤ inf

µ∈M

( T
X

Dφ (qµ , π)
ηL2 T+Eθ∼qµ [`t (θ)] +αη
t=1Pierre Alquier, RIKEN AIP)

Regret bounds for generalized Bayes updates.

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVA
Theorem
Under the previous assumptions SVA leads toTXEθ∼qµt [`t (θ)]
t=1

≤ inf

µ∈M

( T
X

Dφ (qµ , π)
ηL2 T+Eθ∼qµ [`t (θ)] +
α
η
t=1

)
.

Application to Gaussian approximation with KL :T
X
t=1

Eθ∼qµt [`t (θ)] ≤ inf
θ

T
X

p
`t (θ) + (1 + o(1))L dT log(T ).

t=1

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVB
Theorem 2
Using Gaussian approximations and Dφ = KL, assuming theloss is convex, L-Lipschitz and the parameter space bounded(diameter = D), SVB with adequate η leads to
T
T


X
X
√
`t Eθ∼qµt (θ) ≤ inf`t (θ) + DL 2T .
θ

t=1

Pierre Alquier, RIKEN AIP

t=1

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Theoretical analysis of SVB
Theorem 2
Using Gaussian approximations and Dφ = KL, assuming theloss is convex, L-Lipschitz and the parameter space bounded(diameter = D), SVB with adequate η leads to
T
T


X
X
√
`t Eθ∼qµt (θ) ≤ inf`t (θ) + DL 2T .
θ

t=1

t=1

If, moreover, the loss is H-strongly convex,
T
T


X
X
L2 (1 + log(T )).
`t Eθ∼qµt (θ) ≤ inf`t (θ) +
θ
H
t=1
t=1

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Test on a simulated dataset

Figure – Average cumulative losses on different datasets forclassification and regression tasks with OGA (yellow), OGA-EL(red), SVA (blue), SVB (purple) and NGVI (green).
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Test on the Breast dataset

Figure – Average cumulative losses on different datasets forclassification and regression tasks with OGA (yellow), OGA-EL(red), SVA (blue), SVB (purple) and NGVI (green).
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Open questions

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Open questions
1

Analysis of SVB in the general case.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Open questions
1
2

Analysis of SVB in the general case.
Analysis of the uncertainty quantification.

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Open questions
1
2
3

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 notsatisfy our convexity assumption...

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Open questions
1
2
3

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 notsatisfy our convexity assumption...
Uses exponential family approximations {qµ , µ ∈ M}
where m is the mean parameter. Denoting λ the naturalparameter (with λ = F (µ)),λt = (1 − ρ)λt−1 + ρ∇µ Eθ∼qµt−1 [`t (θ)] ,M. E. Khan, D. Nielsen (2018). Fast yet Simple Natural-Gradient Descent for Variational
Inference in Complex Models. ISITA.
Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates

Generalized Bayes update
Online variational inference

The algorithms : SVA and SVB
Regret bounds

Thank you !

Pierre Alquier, RIKEN AIP

Regret bounds for generalized Bayes updates