Description

Nikhil Manjrekar
Contents
1 Question 1 2
2 Question 2 3
3 Question 3 6
4 Question 4 7
5 Question 5 10
6 Question 6 11
7 Question 7 12
8 Question 8 13

1
1 Question 1
In this question, we need to prove the modularity/submodularity/super-modularity of the given functions. In each of the cases we assume two subsets A,B such that A ⊆ B, and use the following inequality for submodularity,
f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B) if A ⊆ B
and the following inqueality for super-modularity,
f(A ∪ {x}) − f(A) < f(B ∪ {x}) − f(B) if A ⊆ B
Notations : E(X,Y ) = set of edges from set X to set Y .
1. |I(V1)|, where I(V1) = set of edges with atleast one endpoint in V1, V1 ∈ V (G). – Submodular
Let there be two sets A and B such that A ⊆ B ⊆ V (G). Since, A ⊆ B, we can also say that I(A) ⊆ I(B), since if an edge e is part of I(A), it must have a vertex in A which must also be present in B. We add a vertex x ∈ V − B to both A and B. Observe that on adding x, some of the edges might already be present in the sets I(A) and I(B).
Consider the differences, |I(A ∪ {x}) − |I(A)| and |I(B ∪ {x}) − |I(B)|.
|I(A ∪ {x}) − |I(A)| = |E(x,V − A)|
|I(B ∪ {x}) − |I(B)| = |E(x,V − B)|
And since, (V − B) ⊆ (V − A), therefore E(x,V − B) ⊆ E(x,V − A). Hence we can write,

Therefore, I(V1) is a submodular function.
2. |cut(V1)|, where cut(V1) = set of all edges with only one endpoint in V1,V1 ∈ V (G) – Submodular
Let there be two sets A and B such that A ⊆ B ⊆ V (G). When the vertex x ∈ V (G) − B in included in A, we remove all the edges cut(A) with one endpoint on x and add new edges with one endpoint x and the other endpoint in V − A − {x}. Thus,
|cut(A ∪ {x})| − |cut(A)| = |E(x,V − A − {x})| − |E(x,A)|
Same can be written for subset B. Since, (A ⊆ B) =⇒ (V − B − {x} ⊆ V − A − {x}). Therefore, E(x,V − B − {x}) ⊆ E(x,V − A − {x}) and E(x,A) ⊆ E(x,B). Thus, we can write the following inequalities,
|E(x,V − A − {x})| ≥ |E(x,V − B − {x})|
|E(x,A)| ≤ |E(x,B)|
Using the above two inequalities we can finally write
|E(x,V − A − {x})| − |E(x,A)| ≥ |E(x,V − B − {x})| − |E(x,B)|
|cut(A ∪ {x})| − |cut(A)| ≥ |cut(B ∪ {x})| − |cut(B)|
And hence, the function |cut(.)| is submodular.
3. |I(V1)| + |cut(V1)| – Submodular claim: Sum of two submodular function is also submodular, i.e.,
(f + g)(P ∪ Q) + (f + g)(P ∩ Q) ≤ (f + g)(P) + (f + g)(Q)
proof for claim: consider two submodular functions f and g. Therefore by the definition of submodularity, we have,
f(P ∪ Q) + f(P ∩ Q) ≤ f(P) + f(Q)
g(P ∪ Q) + g(P ∩ Q) ≤ g(P) + g(Q)
for some sets P and Q. Also we can write,
(f + g)(P ∪ Q) + (f + g)(P ∩ Q) = (f(P ∪ Q) + f(P ∩ Q)) + (g(P ∪ Q) + g(P ∩ Q))
≤ (f(P) + f(Q)) + (g(P) + g(Q)) (1)
≤ (f + g)(P) + (f + g)(Q)
hence claim is proved. We can use the above claim to state that, since the function |I(V1)| and |cut(V1)| are both submodular, therefore their sum is also going to be submodular.
4. |EL|,|ER| where EL(x) = set of all the vertices in VR adjacent only to vertices in X, X ∈ VL Super-modular
Consider two sets A and B such that A ⊆ B ⊆ VL. Also denote N(X) as the neighborhood of vertices in X such that N(X) ⊆ VR. Consider a vertex x ∈ VL − B. We can observe that any vertex y ∈ N(x) will not be part of set EL(A) and EL(B), otherwise it would have been against the definition of EL as x ̸∈ A,B. Thus, new elements in EL(A∪x) will include vertices that are only connected to vertex x and the vertices that are connected to only vertices in A. Same argument for B. Thus,
|EL(A ∪ x)| − |E(A)| = |EL(x)| + |Z(x,A)|
|EL(B ∪ x)| − |E(B)| = |EL(x)| + |Z(x,B)|
Here, the function Z(x,A) ⊆ VR defines the set of vertices in the neighborhood of x such that all the vertices have neigborhood in A∪x. We can also observe that, Z(x,A) ⊆ Z(x,B) because set B has more number of vertices with which vertex in VR in N(x can have edge to. Thus,
|Z(x,A)| ≤ |Z(x,B)|
=⇒ |EL(x)| + |Z(x,A)| ≤ |EL(x)| + |Z(x,B)|
=⇒ |EL(A ∪ x)| − |E(A)| ≤ |EL(B ∪ x)| − |E(B)|
Hence the above function EL is supermodular. Similar is the proof for ER
2 Question 2
Given that A,B ⊆ Ω, where Ω is the universal set. Also for the monotone submodular function f, submodular mutual information is given as,
If(A;B) = f(A) + f(B) − f(A ∪ B)
1. Expression for If(A1,A2,…Ak) =?
Observe that If(A;B) is essentially similar to applying function f on intersection of two sets (set analogy). By using inclusion exclusion principle for intersection (similar to union), we can write
n
If(A1,A2 …Ak) = Xf(Ai) − X f(Ai1 ∪ Ai2) + … + (−1)k+1f(A1 ∪ A2 ∪ A3 …Ak)
i=1 1≤i1<i2≤n
If(A1,A2 …Ak) = X (−1)|J|+1f([ Aj)
Φ̸=J⊆{1,2,…n} j∈J
2. If(A;B) ≥ 0 and If(A;B|C) ≥ 0 proof Since f is a submodular function, we can write,
f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B)
=⇒ f(A) + f(B) ≥ f(A ∪ B)
=⇒ f(A) + f(B) − f(A ∪ B) ≥ 0
=⇒ If(A;B) ≥ 0
Hence first part is proved. Using the conditional gain for monotone submodular function we have,
f(A|B) = f(A ∪ B) − f(B)
Therefore, we can write If(A;B|C) as
If(A;B|C) = f(A|C) + f(B|C) − f(A ∪ B|C) (2)
Using the conditional gain we can rewrite the above equation as,
If(A;B|C) = (f(A ∪ C) − f(C)) + (f(B ∪ C) − f(C)) − (f(A ∪ B ∪ C) − f(C))
(3)
= f(A ∪ C) + f(B ∪ C) − f(A ∪ B ∪ C) − f(C)
Again using the submodularity of function f, we can write,
f(A ∪ C) + f(B ∪ C) ≥ f(A ∪ B ∪ C) + f((A ∪ C) ∩ (B ∪ C))
(4)
≥ f(A ∪ B ∪ C) + f((A ∩ B) ∪ C)
Since f is also monotone, therefore f(Y ) ≥ f(X), if X ⊆ Y . Since, C ⊆ (A ∩ B) ∪ C, we ca write,
f(A ∪ C) + f(B ∪ C) ≥ f(A ∪ B ∪ C) + f(C)
=⇒ f(A ∪ C) + f(B ∪ C) − f(A ∪ B ∪ C) − f(C) ≥ 0
=⇒ If(A;B|C) ≥ 0
Hence proved.
3. min(f(A),f(B)) ≥ If(A;B) ≥ f(A ∩ B) proof: Using the submodularity we have,
f(A) + f(B) − f(A ∪ B) ≥ f(A ∩ B) (5)
=⇒ If(A;B) ≥ f(A ∩ B) (6)
Using the conditional gain f(A|B) = f(A ∪ B) − f(B) =⇒ f(A ∪ B) = f(B) + f(A|B). Thus we can write,
If(A;B) = f(A) + f(B) − (f(B) + f(A|B))
(7)
= f(A) − f(A|B)
Similarly, f(A ∪ B) = f(A) + f(B|A) and therefore above equation can also be written as If(A;B) = f(B)−f(B|A). Since, f is monotone and submodular, therefore, f(B|A) and f(A|B) ≥ 0. Therefore, we have If(A;B) ≤ f(A) and If(A;B) ≤ f(B). Combining both the results, we have,
If(A;B) ≤ min(f(A),f(B)) (8)
Using inequality 6 and 8 we can write the required results.
Clarification: f(A|B) ≥ 0 because, f(A ∪ B) ≥ f(B) =⇒ f(A|B) ≥ 0 by monotonicity.
4. min(f(A|C),f(B|C)) ≥ If(A;B|C) ≥ f(A ∩ B|C)
proof: In order to prove this, we can simply use the result from previous part, but in order to do that we to show that the function g(A) = f(A|C) is also submodular for fixed set C. By monotonicty of f, we can write
f(A ∪ C) ≥ f(C) =⇒ f(A|C) ≥ 0 =⇒ g(A) ≥ 0
Further note that, in g(A) = f(A ∪ C) − f(C), f(A ∪ C) is submodular because of the conditioning property that union with fixed set is also submodular. Also since, C is fixed, f(C) will also be fixed. Hence, the function g(A) is also submodular. Therefore, g(A) has similar properties has f(A), therefore, results for previous part can be rewritten as,
min(g(A),g(B)) ≥ If(A;B|C) ≥ g(A ∩ B)
5. f(A) − Pj∈A−B f(A;B) ≤ If(A;B) ≤ f(A) − Pj∈A−B f(j|Ω − j) ≤ f(A)
Proof: Let’s start with the lower bound first. Using second order partial derivatives (class slides) we have, f(i|X ∪ j) ≤ f(i|X)
for some sets X,i,j. We can use this in our proof. So, let’s assume that A − B = {a1,a2,…,ak}. Then, we can have, f(a1|B) ≥ f({a1}|B) = f({a1} ∪ B) − f(B) f(a2|B) ≥ f({a2}|B ∪ {a1}) = f({a2} ∪ {a1} ∪ B) − f({a1} ∪ B)
… (9)
f(ak|B) ≥ f({ak}|B ∪ {ak−1} ∪ …{a1}) = f({ak} ∪ {ak−1}…{a1} ∪ B) − f({ak−1}…{a1} ∪ B) Summing up on both the sides of the inequality we will have,
k
X
f({ai}|B) ≥ f({ak} ∪ {ak−1}…{a1} ∪ B) − f(B)
i=1
Observe that the quantity {ak} ∪ {ak−1}…{a1} ∪ B = A ∪ B, Hence, (10)
(11)
Also it is known that If(A;B) = f(A) − f(A|B) =⇒ f(A|B) = f(A) − If(A;B). we can use this in the above inequality as,

(12) k
=⇒ If(A;B) ≥ f(A) − Xf({ai}|B)
i=1
Now, for the upper bound, observe that B ∪ {ak−1} ∪ {ak−2}… ∪ {a1} ⊆ Ω {ak} (Taking advantage of notation in the upper bound to be proved since ak is present in neither of the sets). From sets on inequalities in 13 we can have
f(a1|B) ≥ f({a1}|B) ≥ f({a1}|Ω {a1}) f(a2|B) ≥ f({a2}|B ∪ {a1}) ≥ f({a2}|Ω {a2})
… (13)
f(ak|B) ≥ f({ak}|B ∪ {ak−1} ∪ …{a1}) ≥ f({ak}|Ω {ak})
Summing up all the inequalities we will have,
k k X X
f({ai}|B) ≥ f(A|B) ≥ f({ai}|Ω {ai}) (14)
i=1 i=1
Using the right inequality and f(A|B) = f(A) − If(A;B), we will have,
k
f(A) − Xf({ai}|Ω {ai} ≥ If(A;B)
i=1
3 Question 3
1. Given that y = [y1 y2 …yn]T,a = [β0,β1]T,B = [1 x1;1 x2;…;1 xn] and g(x) = diag(w1(x),w2(x),…,wn(x)) Thus,

also g(x)(y − Ba) will be given as,

hence we can observe that the product (y − Ba)Tg(x)(y − Ba) gives the equation for the minimization as given in question
2. In order to find βˆ0 and βˆ1 we need to differentiate the formulation we obtained above wrt a = [β0 β1]T.
We will use the following property,
∂xTAx T T
= x (A + A)
∂x
Therefore, we have,
∂(y − Ba)Tg(x)(y − Ba) T ∗ g(x))∂(y − Ba)
= (y − Ba) (2
∂a ∂a
= −2(y − Ba)Tg(x)B
for minima, above differential will be 0, thus,
yTg(x)B − aTBTg(x)B = 0
aT = yTg(x)B(BTg(x)B)−1
=⇒
Observe that BTg(x)B will be square invertible matrix. Also we can write fˆ(x) = ˆaT[1 x]T, thus,

fˆ(x) = yTh(x)
=⇒
where h which is n × 1 dimensional column vector and its each element is
hi(x) which is a scalar. Therefore, we can write the above equation as

4 Question 4
1. Part1

Figure 1: Ground-Set, Rep-Set and Representative Subset chosen using Facility
Location, Graph Cut with λ = −3,0,3 in the order and Disparity Sum Function

Figure 2: Ground-Set, Rep-Set and Representative Subset chosen using Facility
Location, Graph Cut with λ = −3,0,3 in the order and Disparity Sum Function

Figure 3: Representative Subset chosen using Disparity Min function
2. Part 2

Figure 4: Ground-Set, Query-Set for three query sets is represented above. The first two query sets had multiple queries (2) while last one had only single query
5 Question 5
For the given prox function, for different range of values of )) which we are
trying to minimise will be given as,
(15)
The above function is calculated on certain values of x.
1. Case 1: When 0 ≤ z ≤ θ
In this case, )). One can see that if 0 ≤ x ≤ θ, then clearly fx(z) minimizes to , since h(x) = 0 in this range of x. Also for x = z in this range, fx(z) = 0. Therefore, x = z,0 ≤ z ≤ θ
2. Case 2: When z ≥ θ
In this case if 0 ≤ x ≤ θ, then ). Also observe that the norm in the function will only be minimised for x = θ. But for + 100) which can only be minimized for x = z in this range. But if we see both the values collectively, then the function will

become 100). Therefore, we again have two cases:-
, then

Intersecting the above interval with range of z in this case, we have

x = θ, if θ ≤ z ≤ p200γ + θ
(b) fx(z) = 100, then

Therefore, for this case we have,
x = z, if p200γ + θ ≤ z
3. Case 3: When z ≤ 0
This case is similar to case 2, only difference being that as case 2. Therefore again we will have two cases

100) with same logic , then

Intersecting the above interval with range of z in this case, we have
x = 0, if − p200γ ≤ z ≤ 0
(b) fx(z) = 100, then

Also intersecting with the interval of this case we will have,

=⇒ z ≤ −p200γ
Therefore, for this case we have,

x = z, if z ≤ −p200γ
Therefore, combining results of all the three cases, we will have,

6 Question 6
Projected Gradient Descent algorithm is given as follows,
xt+1 = xt − αt∇f(xt)
xt+1 = PC(xt+1)
We are given the following optimization problem,
minf(x) x∈R subject to x ≤ r and x ≥ l
where
Since the function to be minimized is convex function in Pc(x), therefore, we can use the KKT conditions to solve the problem, which are given as,
1.
2.
3.
4.
5. λ2(x − r) = 0
6. λ1 ≥ 0
7. λ2 ≥ 0
Above all the conditons imply optimality at the l ≤ x ≤ r Solving the first condition we will get,
(x − z) − λ1 + λ2 = 0 (16)
x = z + λ1 − λ2 (17)
Now we will consider two cases,
1. Case 1: When l < x < r,
In this case, the condition 2 and 4 above will imply, λ1 = 0 and λ2 = 0. So by using equation 21, we will have x = z. For this to hold z must lie in interval (l,r).
2. Case 2: If the first case doesn’t hold then only two options we have are x = l or x = r, If x = l, then λ2 = 0 according to condition 5 and x = z + λ1 − λ2 =⇒ z = l − λ1 + λ2 =⇒ z ≤ l. Similarly, for the case x = r
Therefore, the above solution can be summarized as,
 l z ≤ l

PC(z) = z l < z < r
r z ≥ r
In short this can be written as, PC(z) = min(max(z,l),r). Hence the complete optimization step can be given as, xt+1 = min(max(z,xt+1),r)
7 Question 7
We can write If(A;B;C) as,
If(A;B;C) = f(A) + f(B) + f(C) − f(A ∪ B) − f(A ∪ C) − f(B ∪ C) + f(A ∪ B ∪ C)
= If(A;B) + If(C;B) − f(B) − f(A ∪ C) + f(A ∪ B ∪ C)
= If(A;B) + If(C;B) − If(A ∪ C;B)
We can see that if function, If(X;B) is submodular for a fixed set B then, we can write,
If(A;B) + If(C;B) ≥ If(A ∪ C;B) + If(A ∩ C;B)
=⇒ If(A;B) + If(C;B) − If(A ∪ C;B) ≥ If(A ∩ C;B)
=⇒ If(A;B;C) ≥ If(A ∩ C;B)
Since, If(X;B) ≥ 0 because of submodularity, thus
=⇒ If(A;B;C) ≥ 0
Similarly, we can see that if If(X;B) is supermodular for fixed set B. Then, we can write,
If(A;B) + If(C;B) ≤ If(A ∪ C;B) + If(A ∩ C;B)
=⇒ If(A;B) + If(C;B) − If(A ∪ C;B) ≤ If(A ∩ C;B)
Since, If(X;B) ≤ 0 because of submodularity, thus
=⇒ If(A;B;C) ≤ 0
8 Question 8
False, it is not true for all k. We saw in the above example in question 2, that it is true for k=2. However, consider the following monotone submodular function, we do not have the inequality to be satisfied:
f(A) = min(|A|,6)
Clearly, f(A) is monotonic, as well as submodular. We now consider the 5-way mutual information given by,
If(A,B,C,D,E)
let A,B,C,D,E be the disjoint sets such that |A| = |B| = |C| = |D| = 2,|E| = 1. RHS is given by minf(A),f(B),f(C),f(D),f(E) = 1.
If term has 5 ( + 1) terms involving singletons: ) terms like terms like ) terms like f(A ∪ B ∪ C ∪ D) and 1 ( ) term f(A ∪ B ∪ C ∪ D ∪ E).
Thus
If(A;B;C;D;E) = (4(2) + 1) − (6(4) + 4(3)) + (4(6) + 6(5)) − (1(6) + 4(6)) + 6 = 3 ≥ 1 = minf(A),f(B),f(C),f(D),f(E) = 1.
Hence, this is against the given statement. Therefore, the given relation does not hold for all the values of k.