Submodular Maximization Algorithms Overview
Deterministic and Combinatorial
Algorithms for Submodular Maximization
Moran Feldman
The Open University of Israel
Motivation: Adding Dessert
•
Ground set
N
of elements (dishes).
•
Valuation function
f
: 2
N
ℝ (a value for each meal).
•
Submodularity:
f
(
A
+
u
) –
f
(
A
) ≥
f
(
B
+
u
) –
f
(
B
)
∀
A
B
N
,
u
B
.
Alternative Definition
f
(
A
) +
f
(
B
) ≥
f
(
A
B
) +
f
(
A
B
)
∀
A
,
B
N.
Another Example
3
Submodular Optimization
Submodular functions can be found in:
•
Combinatorics
•
Machine Learning
4
•
Image Processing
•
Algorithmic Game Theory
•
Motivates the optimization of submodular functions subject
to various constraints.
Generalizes classical problems (two examples soon).
Many practical applications.
•
In this talk, we only consider submodular maximization.
Instance:
a directed graph G = (
V, E
) with capacities
c
e
0 on
the arcs.
Objective:
find a cut (
S
,
V
\
S
) with a maximum capacity.
Instance:
a directed graph G = (
V, E
) with capacities
c
e
0 on
the arcs.
Objective:
find a cut (
S
,
V
\
S
) with a maximum capacity. In
other words, find a set
S
V
maximizing the function
Example 1: Max DiCut
5
f
(
S
) = 4
Observation
•
f
(
S
) is a non-negative
submodular function.
•
Special case of unconstrained
maximization of such functions.
Example 2: Max
k
-Cover
Instance:
elements
E
= {e
1
,
e
2
, …,
e
n
} and sets
s
1
,
s
2
, …,
s
m
E
.
Objective:
find
k
sets covering as many different elements as
possible.
Instance:
elements
E
= {e
1
,
e
2
, …,
e
n
} and sets
s
1
,
s
2
, …,
s
m
E
.
Objective:
find
k
sets covering as many different elements as
possible. In other words, find a collection
S
{s
1
,
s
2
, …,
s
m
} of
size at most
k
maximizing
6
Observation
•
f
(
S
) is a non-negative monotone
submodular function.
•
Special case of maximization of
such functions subject to a
cardinality constraint.
A set function
f
: 2
N
ℝ is
monotone if
f
(
A
) ≤
f
(
B
) for every
A
B
N
.
Continuous Relaxations
7
•
Sumodular maximization problems are discrete.
•
Nevertheless, many state of the art algorithms for it make use
of a continuous relaxation (the multilinear relaxation).
Similar to the standard technique of
solving an LP relaxation and rounding.
The Multilinear Relaxation
max
F
(
x
)
s.t.
x
P
[0, 1]
N
The constraints remain linear.
•
The objective is replaced with
its multilinear extension.
•
Defined as the expected value
of the original objective over
some distribution.
Issues with this Approach
8
•
(Approximately) solving the multilinear relaxation requires us
to repeatedly evaluate the multilinear extension.
•
Each evaluation is done by randomly sampling from the
distribution used to define this extension.
Tends to be quite slow
Inherently randomized
(often undesirable)
We want
Combinatorial
algorithms
We want
Deterministic
algorithms
Additional Randomized Algorithms
9
•
For simple enough constraints, good (and simple)
combinatorial algorithms are known.
For example, a cardinality constraint.
Tend to be
deterministic
for monotone objectives.
Usually
randomized
for
non-monotone objectives.
•
Even for simple constraints, if the objective function is non-
monotone than finding good
deterministic
algorithms is
(partially) open
.
Objectives Summary
10
Summary of what we are looking for
For simple constraints with
non-monotone objectives
For more involved constraints
with monotone objectives
We
have
good randomized
combinatorial algorithms
We
have
good continuous
algorithms
We
want
good
deterministic algorithms
We
want
good combinatorial
and/or deterministic algorithms
•
Partially answered
•
First result we will see
•
Recent results make first baby steps
•
Second result we will see
The Profile of the Algorithms
12
•
Works in iterations.
•
In every iteration:
Starts with some state
S
.
Randomly switches to a new state from a set
N
(
S
).
For every
S’
N
(
S
), l
et
p
(
S
,
S’
) be the probability that the
algorithm switches from
S
to
S’
.
•
The analysis works whenever the probabilities
p
(
S
,
S’
) obey
k
linear constraints that might depend on
S
, where
k
is
polynomial:
Derandomization – Naïve Attempt
13
Idea
Explicitly store the distribution over the current state of the
algorithm.
(
S
0
,
1)
(
S
1
,
p
)
(
S
2
, 1 -
p
)
(
S
3
,
q
1
)
(
S
6
,
q
4
)
(
S
4
,
q
2
)
(
S
5
,
q
3
)
•
The number of states can increase
exponentially with the iterations.
Strategy
[Buchbinder and F 16]
14
S
S
1
S
3
p
(
S
,
S
1
)
•
The state
S
i
gets to the distribution of the next iteration
only if
p
(
S
,
S
i
) > 0.
•
We want probabilities that:
obey the constraints.
are mostly zeros.
S
2
p
(
S
,
S
2
)
p
(
S
,
S
3
)
Expectation to the Rescue
15
The analysis of the algorithm works when:
(
D
is the current distribution).
•
Often it is enough for the constraints to hold in
expectation over
D.
Some Justifications
We now require the analysis to work
only for the expected output set.
Can often follow from the linearity of
the expectation.
Finding a good solution
Has a solution (the probabilities
used by the original algorithm).
Bounded.
A basic feasible solution contains at most one non-zero
variable for every constraint:
•
One non-zero variable for every current state.
•
k
additional non-zero variables.
16
So the algorithm is…
17
Deterministic Algorithm
•
Explicitly stores a distribution over states.
•
In every iteration:
Uses the previous LP to calculate the probabilities to
move from one state to another.
Calculates the distribution for the next iteration based
on these probabilities.
Performance
•
The analysis of the original (randomized) algorithm still
works.
•
The size of the distribution grows linearly in
k
– polynomial
time algorithm.
Sometimes the LP can be replaced by a
combinatorial algorithm, so the resulting
algorithm remains combinatorial.
History and Results
18
Unconstrained Submodular Maximization
•
Best randomized algorithm: 0.5 [Buchbinder et al. 12]
•
Inapproximability: 0.5 [Feige et al. 07]
•
Previously best det. algorithm: 0.4 [Dobzinski and Mor 15]
•
New deterministic algorithm: 0.5 [Buchbinder and F 16]
Maximization subject to a Cardinality Constraint
•
Best randomized algorithm: 0.385 [Buchbinder and F 16]
•
Inapproximability: 0.491 [Oveis Gharan and Vondrak 11]
•
Previously best det. algorithm: 0.25 [Lee et al. 10]
•
New det. algorithm: 0.367 (
e
-1
) [Buchbinder and F 16]
Known Results (Baby Steps)
20
Local search techniques are the state of the art for some
classes of constraints (due to poor rounding options):
•
Intersection of
k
matroids [Lee et al. 10]
•
k
-exchange systems [F, Naor, Schwartz and Ward 11]
•
Intersection of
k
matroids + a knapsack [Sarpatwar et al. 17]
Maximizing a monotone submodular function subject to a
constant number of packing and covering constraints:
•
Optimal (1 – 1/
e
)-approximation through the multilinear
relaxation. [Kulik et al. 16, Mizrachi et al. 18]
•
Constant deterministic approximation (at most 1/
e
) for
special cases. [Mizrachi et al. 18]
Known Results (cont.)
21
Maximizing a monotone submodular function subject to a
matroid constraint.
•
Optimal (1 - 1/
e
)-approximation through the multilinear
relaxation. [Calinescu et al. 11]
•
Well known ½-approximation by the (deterministic) greedy
algorithm. [Nemhauser and Wolsey 78]
Applying greedy in a random order yields:
•
0.505-approximation for submodular
welfare. [
Korula et al. 15]
•
0.509-approximation for partition
matroids [Buchbinder et al. 18].
Recent result
[Buchbinder et al. 18]
•
0.5008-approximation using a
deterministic combinatorial
algorithm.
Can be understood as
an online algorithm
Analysis Intuition
22
Greedy Algorithm
•
Scan the right vertices in some
order (let’s say from top to
bottom) and connect every
vertex to a free neighbor (if
available).
Performance
•
Achieves ½-approximation.
•
Worst case performance only
when the free neighbor is below
the considered vertex.
Analysis Intuition (cont.)
23
How the worst case looks like?
Unlikely to be
matched
(Relatively) large matching
(Relatively) large matching
Contradiction
Open Problems
24
•
Improving the approximation ratios of deterministic and
combinatorial algorithms for involved constraints.
•
Making the existing deterministic algorithms for simple
constraints faster.
•
Proving a separation between the abilities of randomized
and deterministic algorithms.
This article discusses deterministic and combinatorial algorithms for submodular maximization, focusing on their applications in various fields such as combinatorics, machine learning, image processing, and algorithmic game theory. It covers key concepts like submodularity, examples of submodular optimization problems, and the use of continuous relaxations in solving such problems. The content includes visual aids to illustrate the discussed concepts and algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Deterministic and Combinatorial Algorithms for Submodular Maximization Moran Feldman The Open University of Israel
Motivation: Adding Dessert Meal 1 Meal 2 Alternative Definition f(A) + f(B) f(A B) + f(A B) A, B N. Ground set N of elements (dishes). Valuation function f : 2N (a value for each meal). Submodularity: f(A + u) f(A) f(B + u) f(B) A B N, u B.
Another Example 7 11 0 6 8 10 5 4 -8 0 5 N 3
Submodular Optimization Submodular functions can be found in: Combinatorics Machine Learning Image Processing Algorithmic Game Theory Motivates the optimization of submodular functions subject to various constraints. Generalizes classical problems (two examples soon). Many practical applications. In this talk, we only consider submodular maximization. 4
Example 1: Max DiCut Instance: a directed graph G = (V, E) with capacities ce 0 on the arcs. the arcs. Instance: a directed graph G = (V, E) with capacities ce 0 on Objective: find a cut (S, V \ S) with a maximum capacity. Objective: find a cut (S, V \ S) with a maximum capacity. In other words, find a set S V maximizing the function ( ) S f = uc v , u S v S f(S) = 4 Observation f(S) is a non-negative submodular function. Special case of unconstrained maximization of such functions. 5
Example 2: Max k-Cover Instance: elements E = {e1, e2, , en} and sets s1, s2, , sm E. Instance: elements E = {e1, e2, , en} and sets s1, s2, , sm E. Objective: find k sets covering as many different elements as possible. possible. In other words, find a collection S {s1, s2, , sm} of size at most k maximizing ( ) S f Objective: find k sets covering as many different elements as A set function f: 2N is monotone if f(A) f(B) for every A B N. = s i s S i Observation f(S) is a non-negative monotone submodular function. Special case of maximization of such functions subject to a cardinality constraint. s2 s3 s1 s4 s5 6
Continuous Relaxations Sumodular maximization problems are discrete. Nevertheless, many state of the art algorithms for it make use of a continuous relaxation (the multilinear relaxation). The objective is replaced with its multilinear extension. Defined as the expected value of the original objective over some distribution. Similar to the standard technique of solving an LP relaxation and rounding. The Multilinear Relaxation max F(x) x P [0, 1]N s.t. The constraints remain linear. 7
Issues with this Approach (Approximately) solving the multilinear relaxation requires us to repeatedly evaluate the multilinear extension. Each evaluation is done by randomly sampling from the distribution used to define this extension. Inherently randomized (often undesirable) Tends to be quite slow We want Deterministic algorithms We want Combinatorial algorithms 8
Additional Randomized Algorithms For simple enough constraints, good (and simple) combinatorial algorithms are known. For example, a cardinality constraint. Tend to be deterministic for monotone objectives. Usually randomized for non-monotone objectives. Even for simple constraints, if the objective function is non- monotone than finding good deterministic algorithms is (partially) open. 9
Objectives Summary Summary of what we are looking for For simple constraints with non-monotone objectives For more involved constraints with monotone objectives Partially answered First result we will see Second result we will see Recent results make first baby steps We have good randomized combinatorial algorithms We have good continuous algorithms We want good deterministic algorithms We want good combinatorial and/or deterministic algorithms 10
Derandomizing Already Combinatorial Algorithms
The Profile of the Algorithms Works in iterations. In every iteration: Starts with some state S. Randomly switches to a new state from a set N(S). For every S N(S), let p(S, S ) be the probability that the algorithm switches from S to S . The analysis works whenever the probabilities p(S, S ) obey k linear constraints that might depend on S, where k is polynomial: ( ) ( ( ) S p S S a S N S i , , ) ( ) S 1 , S c S i k i 12
Derandomization Nave Attempt Idea Explicitly store the distribution over the current state of the algorithm. The initial state (S0, 1) The number of states can increase exponentially with the iterations. (S1, p) (S2, 1 - p) (S6, q4) (S3, q1) (S4, q2) (S5, q3) 13
Strategy [Buchbinder and F 16] S p(S, S2) p(S, S3) p(S, S1) S1 S2 S3 The state Si gets to the distribution of the next iteration only if p(S, Si) > 0. We want probabilities that: obey the constraints. are mostly zeros. 14
Expectation to the Rescue The analysis of the algorithm works when: ( ) ( ) ( ) ( ) ( ) , p S S the expectation. Some Justifications ( ) ( ) S We now require the analysis to work only for the expected output set. Can often follow from the linearity of D D , , ,1 a S S p S S c S S i k i i N S = D D , 1 p S S S S N S ( ) D D 0 , S S N S ( (D D is the current distribution). Often it is enough for the constraints to hold in expectation over D. D. ( ) ( ) ( ) ( ) ( ) , p S S ( ) ( ) , , 1 E a S S p S S E c S i k D D D D ~ ~ S i S i S p S S N S = D D , 1 S S N S ( ) D D 0 , S S N S 15
Finding a good solution Has a solution (the probabilities used by the original algorithm). Bounded. ( ) ( ) ( ) , , 1 E a S S p S S E c S i k ( ) , D D D D ~ ~ S i S i S N S ( ) = D D 1 p S S S ( ) S N S ( ) ( ) D D , 0 , p S S S S N S A basic feasible solution contains at most one non-zero variable for every constraint: One non-zero variable for every current state. k additional non-zero variables. 16
So the algorithm is Deterministic Algorithm Explicitly stores a distribution over states. In every iteration: Uses the previous LP to calculate the probabilities to move from one state to another. Calculates the distribution for the next iteration based on these probabilities. Sometimes the LP can be replaced by a combinatorial algorithm, so the resulting algorithm remains combinatorial. Performance The analysis of the original (randomized) algorithm still works. The size of the distribution grows linearly in k polynomial time algorithm. 17
History and Results Unconstrained Submodular Maximization Best randomized algorithm: 0.5 [Buchbinder et al. 12] Inapproximability: 0.5 [Feige et al. 07] Previously best det. algorithm: 0.4 [Dobzinski and Mor 15] New deterministic algorithm: 0.5 [Buchbinder and F 16] Maximization subject to a Cardinality Constraint Best randomized algorithm: 0.385 [Buchbinder and F 16] Inapproximability: 0.491 [Oveis Gharan and Vondrak 11] Previously best det. algorithm: 0.25 [Lee et al. 10] New det. algorithm: 0.367 (e-1) [Buchbinder and F 16] 18
Combinatorial and Deterministic Algorithms for Involved Constraints
Known Results (Baby Steps) Local search techniques are the state of the art for some classes of constraints (due to poor rounding options): Intersection of k matroids [Lee et al. 10] k-exchange systems [F, Naor, Schwartz and Ward 11] Intersection of k matroids + a knapsack [Sarpatwar et al. 17] Maximizing a monotone submodular function subject to a constant number of packing and covering constraints: Optimal (1 1/e)-approximation through the multilinear relaxation. [Kulik et al. 16, Mizrachi et al. 18] Constant deterministic approximation (at most 1/e) for special cases. [Mizrachi et al. 18] 20
Known Results (cont.) Maximizing a monotone submodular function subject to a matroid constraint. Optimal (1 - 1/e)-approximation through the multilinear relaxation. [Calinescu et al. 11] Well known -approximation by the (deterministic) greedy algorithm. [Nemhauser and Wolsey 78] an online algorithm Can be understood as Recent result [Buchbinder et al. 18] 0.5008-approximation using a deterministic combinatorial algorithm. Applying greedy in a random order yields: 0.505-approximation for submodular welfare. [Korula et al. 15] 0.509-approximation for partition matroids [Buchbinder et al. 18]. 21
Analysis Intuition Greedy Algorithm Scan the right vertices in some order (let s say from top to bottom) and connect every vertex to a free neighbor (if available). Performance Achieves -approximation. Worst case performance only when the free neighbor is below the considered vertex. 22
Analysis Intuition (cont.) How the worst case looks like? Unlikely to be matched Contradiction Highly likely to be matched Unlikely to be matched 23
Open Problems Improving the approximation ratios of deterministic and combinatorial algorithms for involved constraints. Making the existing deterministic algorithms for simple constraints faster. Proving a separation between the abilities of randomized and deterministic algorithms. 24
