Beyond Adaptive Submodularity:

Approximation Guarantees of Greedy Policy
with Adaptive Submodularity Ratio

Kaito Fujii (UTokyo)&Shinsaku Sakaue (NTT)The 36th International Conference on Machine Learning
Jun. 12, 2019

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible

2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible
Non-adaptive setting

Select a subset in advance2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible
Non-adaptive setting

Select a subset in advance2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible
Non-adaptive setting

Select a subset in advance2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible
Non-adaptive setting

Select a subset in advance2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible

Adaptive setting

Select ads one by one

2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible

Adaptive setting

Select ads one by one

2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible

Adaptive setting

Select ads one by one

2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible

Adaptive setting

Select ads one by one

2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible

Adaptive setting

Select ads one by one

2/ 8

Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible
Non-adaptive setting

Select a subset in advance

Adaptive setting

Select ads one by one

Q1 When does the greedy policy work well?

2/ 8Application: Inﬂuence maximization
Select a subset of ads to inﬂuence as many people as possible
Non-adaptive setting

Select a subset in advance

Adaptive setting

Select ads one by one

Q1 When does the greedy policy work well?
Q2 How diﬀerent are the non-adaptive and adaptive policies?

2/ 8Adaptive submodularity ratio

3/ 8

We propose a new concept called adaptive submodularity ratio
Submodularity ratio[Das–Kempe’11]

Adaptive submodularity ratio[this study]Adaptive submodularity ratio

3/ 8

We propose a new concept called adaptive submodularity ratio
submodularfunctions

Submodularity ratio[Das–Kempe’11]

Adaptive submodularity ratio[this study]Adaptive submodularity ratio

3/ 8

We propose a new concept called adaptive submodularity ratio
submodular
functions

Submodularity ratio[Das–Kempe’11]

γℓ,k = 1

arbitrary
monotonefunctions
γℓ,k = 0

Adaptive submodularity ratio[this study]Adaptive submodularity ratio3/ 8

We propose a new concept called adaptive submodularity ratio
submodularfunctions

Submodularity ratio[Das–Kempe’11]

γℓ,k = 1
adaptive
submodularfunctions[Golovin–Krause’11]

arbitrary
monotonefunctions
γℓ,k = 0

Adaptive submodularity ratio[this study]Adaptive submodularity ratio

3/ 8

We propose a new concept called adaptive submodularity ratio
submodularfunctions

Submodularity ratio[Das–Kempe’11]

arbitrary
monotonefunctions

γℓ,k = 1

γℓ,k = 0

adaptive
submodularfunctions

arbitrary
adaptivemonotonefunctions[Golovin–Krause’11]

Adaptive submodularity ratio[this study]Adaptive submodularity ratio

4/ 8

Adaptive submodularity ratio γℓ,k ∈ [0, 1] is a parameter thatmeasures the distance to adaptive submodular functions△γℓ,k =

min|ψ|≤ℓ, π∈Πk∑v∈V Pr(v ∈ E(π, Φ)|Φ ∼ ψ)∆(v|ψ)∆(π|ψ)

Adaptive submodularity ratio

4/ 8

Adaptive submodularity ratio γℓ,k ∈ [0, 1] is a parameter thatmeasures the distance to adaptive submodular functions△γℓ,k =

min|ψ|≤ℓ, π∈Πk∑v∈V Pr(v ∈ E(π, Φ)|Φ ∼ ψ)∆(v|ψ)

the expected marginal gain of policy π∆(π|ψ)

Adaptive submodularity ratio

4/ 8

Adaptive submodularity ratio γℓ,k ∈ [0, 1] is a parameter thatmeasures the distance to adaptive submodular functions
the expected marginal gain of single element v

the probability that element v is selected by policy π△γℓ,k =

min|ψ|≤ℓ, π∈Πk∑v∈V Pr(v ∈ E(π, Φ)|Φ ∼ ψ)∆(v|ψ)∆(π|ψ)

Adaptive submodularity ratio

4/ 8

Adaptive submodularity ratio γℓ,k ∈ [0, 1] is a parameter thatmeasures the distance to adaptive submodular functions△γℓ,k =

min|ψ|≤ℓ, π∈Πk∑v∈V Pr(v ∈ E(π, Φ)|Φ ∼ ψ)∆(v|ψ)∆(π|ψ)Q1 When does the greedy policy work well?

Adaptive submodularity ratio

4/ 8

Adaptive submodularity ratio γℓ,k ∈ [0, 1] is a parameter thatmeasures the distance to adaptive submodular functions△γℓ,k =

min|ψ|≤ℓ, π∈Πk∑v∈V Pr(v ∈ E(π, Φ)|Φ ∼ ψ)∆(v|ψ)∆(π|ψ)Q1 When does the greedy policy work well?
Theorem Adaptive Greedy is (1 − exp(−γk,k ))-approximation

Bounds on adaptivity gaps

5/ 8

A non-adaptive policy approximates an optimal adaptive policy
GAPk (f , p)△=An optimal
non-adaptive policy

An optimal
adaptive policy

Bounds on adaptivity gaps

5/ 8

A non-adaptive policy approximates an optimal adaptive policy
GAPk (f , p)△=

Q2 How diﬀerent are the non-adaptive and adaptive policies?
Theorem GAPk (f , p) ≥ β0,k γ0,k

△β0,k =minS⊆V : |S|≤k∑

E[f (S, Φ)]v∈S E[f ({v}, Φ)]Application: Inﬂuence maximization
Non-adaptive setting

Select a subset in advance

Adaptive setting

Select ads one by one

6/ 8

Application: Inﬂuence maximization

6/ 8

Non-adaptive setting

Select a subset in advance

Adaptive setting

Select ads one by one

Theorem γℓ,k ≥k+12k

on bipartite graphs with the triggering model

Application: Adaptive Feature Selection

7/ 8Select a subset of features to be observed precisely
Non-adaptive settingy≈

A(Φ)

w

Select a subset in advance

Adaptive setting

Observe features one by one

Application: Adaptive Feature Selection

7/ 8Select a subset of features to be observed precisely
Non-adaptive settingy≈

A(Φ)

w

Select a subset in advance

Adaptive setting

Observe features one by onemin
λmin (A(φ)S⊤ A(φ)S )Theorem γℓ,k ≥ min
φ S⊆V : |S|≤ℓ+kSummary
Adaptive Submodularity Ratio is applied toTheorem 1 Bounds on approximation ratio of Adaptive Greedy
Theorem 2 Bounds on adaptivity gaps
Application 1 Inﬂuence maximization on bipartite graphs
Application 2 Adaptive feature selection

Poster #163 at Paciﬁc Ballroom, Wen 6:30–9:00 PM8/ 8