Regret bounds for online variationalinference
Pierre Alquier

ACML – Nagoya, Nov. 18, 2019

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceCo-authors
Badr-Eddine
Chérief-Abdellatif

Emtiyaz Khan

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

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference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 online variational inference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 online variational inference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.

12

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 online variational inference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.
First step : simplified versions.
Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference

The sequential prediction problem
Sequential prediction problem

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference

The sequential prediction problem
Sequential prediction problem
11x1 given

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference

The sequential prediction problem
Sequential prediction problem
11
2x1 given
predict y1 : ŷ1

Pierre Alquier, RIKEN AIP

Regret bounds for 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 online variational inference

The sequential prediction problem
Sequential prediction problem
1

3x1 given
predict y1 : ŷ1
y1 is revealed

1x2 given

122

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference

The sequential prediction problem
Sequential prediction problem
1123

2

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

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference

The sequential prediction problem
Sequential prediction problem
1

12
3

2

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

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceThe sequential prediction problem
Sequential prediction problem
1

12
3

2

3x2 given
predict y2 : ŷ2y2 revealed

1x3 given

12

3x1 given
predict y1 : ŷ1
y1 is revealed

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference

The sequential prediction problem
Sequential prediction problem
1

12
3

2

1
2
3

3

1
2x1 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 online variational inference

The sequential prediction problem
Sequential prediction problem
11232

1233

12
34

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 online variational inference

The sequential prediction problem
Sequential prediction problem
1

12
3

2

12
3

3

123

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 online variational inference

The sequential prediction problem
Sequential prediction problem
1

12321
233

1
23

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 online variational inference

The sequential prediction problem
Sequential prediction problem
112321233

123

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. KeepTX`(ŷt , yt )t=1

as small as possible.

...

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceOnline gradient algorithm (OGA)
Given
a set of predictors {fθ , θ ∈ Θ ⊂ Rd }, e.g fθ (x) = hθ, xi,
an initial guess θ1 ,ŷt = fθt (xt ) and θt+1 = θt − η∇θ `(fθt (xt ), yt ).

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceOnline gradient algorithm (OGA)
Given
a set of predictors {fθ , θ ∈ Θ ⊂ Rd }, e.g fθ (x) = hθ, xi,
an initial guess θ1 ,ŷt = fθt (xt ) and θt+1 = θt − η∇θ `t (θt ).

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceOnline gradient algorithm (OGA)
Given
a set of predictors {fθ , θ ∈ Θ ⊂ Rd }, e.g fθ (x) = hθ, xi,an initial guess θ1 ,ŷt = fθt (xt ) and θt+1 = θt − η∇θ `t (θt ).
Note that θt+1 can be obtained by :(* t+)
Xkθ − θ1 k2
1minθ,∇θ `s (θs ) +,θ2η
s=1)
(DE kθ − θ k2t2.
minθ, ∇θ `t (θt ) +θ2η

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceBayesian learning and variational inference (VI)
πt+1 (θ) := π(θ|x1 , y1 , . . . , xt , yt ) ∝ exp −ηtX!
`s (θ) π(θ).

s=1Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference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

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference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 :πt+1 (θ) ∝ exp (−η`t (θ)) πt (θ).
Q1 : can we similarly define a sequential update for avariational approximation ?
Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceRegret bounds for Bayesian inference
Theorem (classical result)
Under the assumption that the loss is bounded by B, theBayesian update leads toT
XEθ∼πt [`t (θ)]
t=1

≤ infq( TXηB 2 TKL(q, π)Eθ∼q [`t (θ)] ++8η
t=1

Pierre Alquier, RIKEN AIP)

Regret bounds for online variational inference.

Regret bounds for Bayesian inference
Theorem (classical result)
Under the assumption that the loss is bounded by B, theBayesian update leads toTX
Eθ∼πt [`t (θ)]
t=1

≤ infq( TXηB 2 TKL(q, π)Eθ∼q [`t (θ)] ++8η
t=1

Derivation of the infimum and η ∼TXt=1Eθ∼πt [`t (θ)] ≤ inf
θTX√)

T “usually” leads to`t (θ) + O(pdT log(T )).

t=1

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference.

Regret bounds for Bayesian inference
Theorem (classical result)
Under the assumption that the loss is bounded by B, theBayesian update leads toTXEθ∼πt [`t (θ)]
t=1

≤ infq( TXηB 2 TKL(q, π)Eθ∼q [`t (θ)] ++8η
t=1Derivation of the infimum and η ∼TX
t=1Eθ∼πt [`t (θ)] ≤ infθTX√)

T “usually” leads to`t (θ) + O(pdT log(T )).

t=1

Q2 : can we derive similar results for online VI ?
Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference.

Two options for online VI
Parametric VI : F = {qµ , µ ∈ M}.

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceTwo options for online VI
Parametric VI : F = {qµ , µ ∈ M}.
1Sequential Variational Approximation (SVA) :)(* t+Xkθ − θ1 k2,
θt+1 = arg minθ,∇θ `s (θs ) +2ηθs=12

Streaming Variational Bayes (SVB) :)(DE kθ − θ k2t
θt+1 = arg minθ, ∇θ `t (θt ) +,2ηθ

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceTwo options for online VI
Parametric VI : F = {qµ , µ ∈ M}.
1Sequential Variational Approximation (SVA) :)(* t+Xkθ − θ1 k2,
θt+1 = arg minθ,∇θ `s (θs ) +2ηθ
s=1(*)+tXKL(qµ , π)µt+1 = arg minµ,∇µ Eθ∼qµs [`s (θ)] +.
ηµs=12

Streaming Variational Bayes (SVB) :)(DE kθ − θ k2t
θt+1 = arg minθ, ∇θ `t (θt ) +,2ηθ

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceTwo options for online VI
Parametric VI : F = {qµ , µ ∈ M}.
1
Sequential Variational Approximation (SVA) :)(* t+Xkθ − θ1 k2,
θt+1 = arg minθ,∇θ `s (θs ) +2ηθs=1(*)+tX
KL(qµ , π)µt+1 = arg minµ,∇µ Eθ∼qµs [`s (θ)] +.
ηµs=12Streaming Variational Bayes (SVB) :)(DE kθ − θ k2t
θt+1 = arg minθ, ∇θ `t (θt ) +,2ηθDE KL(q , q ) µ µtµt+1 = arg minµ, ∇µ Eθ∼qµt [`t (θ)] +.
ηµPierre Alquier, RIKEN AIP

Regret bounds for online variational inference

SVA & SVB are tractable, and not equivalent
Example : Gaussian prior θ ∼ π = N (0, s 2 I ) and mean-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 online variational inference

Theoretical analysis of SVATheorem 1Under convexity and L-Lipschitz assumption on the loss, underα-strong convexity assumption on the KL term, SVA leads toTXEθ∼qµt [`t (θ)]
t=1

≤ infµ∈M( TX

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

Regret bounds for online variational inference.

Theoretical analysis of SVA
Theorem 1Under convexity and L-Lipschitz assumption on the loss, underα-strong convexity assumption on the KL term, SVA leads toTXEθ∼qµt [`t (θ)]
t=1

≤ infµ∈M( TX

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

Application to Gaussian approximation leads toT
Xt=1Eθ∼qµt [`t (θ)] ≤ inf
θTX`t (θ) + (1 + o(1))

t=1Pierre Alquier, RIKEN AIP

2L pdT log(T ).
αRegret bounds for online variational inference

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

Pierre Alquier, RIKEN AIP

t=1

Regret bounds for online variational inference

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

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

Pierre Alquier, RIKEN AIPRegret bounds for online variational inference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 online variational inference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 online variational inferenceOpen questions

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceOpen questions
1Analysis of SVB in the general case.

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceOpen questions
12

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

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inferenceOpen questions
12
3

Analysis of SVB in the general case.
Analysis of the uncertainty quantification.
NGVI is the next step in going closer to algorithms usedto 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 online variational inference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 usedto 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 = (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, RIKEN AIP

Regret bounds for online variational inferenceThank you !

Pierre Alquier, RIKEN AIP

Regret bounds for online variational inference