Efficient Machine Learning

What is Submodularity?

▶ Submodularity is a property of set functions that captures the

concept of diminishing returns.
▶ A set function f : 2N → R, defined on subsets of a finite
ground set N, is submodular if:

f (A ∪ {x}) − f (A) ≥ f (B ∪ {x}) − f (B),

for any A ⊆ B ⊆ N and x ∈ N \ B.

▶ Key Idea: The inequality means:
▶ Adding an element x to a smaller set A yields a greater or
equal gain in f than adding it to a larger set B.
Submodular Function: Equivalent Conditions
A submodular function f : 2Ω → R, defined on the power set of a
finite set Ω, satisfies one of the following equivalent conditions:
1. Diminishing Returns Property: For X ⊆ Y ⊆ Ω and
x ∈ Ω\Y:

f (X ∪ {x}) − f (X ) ≥ f (Y ∪ {x}) − f (Y ).

2. Submodular Inequality: For S, T ⊆ Ω:

f (S) + f (T ) ≥ f (S ∪ T ) + f (S ∩ T ).

3. Pairwise Diminishing Returns: For X ⊆ Ω and distinct

x1 , x2 ∈ Ω \ X :

f (X ∪ {x1 }) + f (X ∪ {x2 }) ≥ f (X ∪ {x1 , x2 }) + f (X ).

Note: A nonnegative submodular function is subadditive, but not

all subadditive functions are submodular.
Submodularity and Concavity

▶ In some sense, submodular functions are the discrete analogue

of concave functions.
▶ A function f : R → R is concave if the derivative f ′ (x) is
non-increasing in x.
▶ A function F : {0, 1}n → R is submodular if for all i, the
discrete derivative:

∂i f (x) = f (x + ei ) − f (x),

is non-increasing in x.
▶ Furthermore, if g : R+ → R is concave, then F (A) = g (|A|) is
submodular.
Examples of Submodular Functions

▶ Coverage Function: Suppose (Ai )i∈V are measurable sets.

Then:
[
F (S) = Ai
i∈S

is submodular.
Examples of Submodular Functions

▶ Cut Functions: Given a (un)directed graph (V , E ), define

F (A) to be the total number of edges from A to V \ A. F (A)
is submodular.
▶ More generally, if d : V × V → R+ , then:
X
F (A) = d(i, j)
i∈A,j∈V \A

is submodular.
Examples of Submodular Functions

▶ Entropy: Given n random variables (Xi )i∈V , define:

F (A) = H(XA )

to be the joint entropy. Then F is submodular.

▶ Indeed, suppose A ⊂ B, k ∈ V \ B, then:

F (A∪{k})−F (A) = H(XA , Xk )−H(XA ) = H(Xk |XA ) ≥ H(Xk |XB ).

▶ Mutual Information: Mutual information is also submodular:

I (A) = F (A) + F (V \ A) − F (V ).
Definition of x(A) and Lovász Extension
▶ Definition of x(A): Given x ∈ Rn+ and A ⊆ V , define:
X
x(A) = xi = x T 1A
i∈A

where 1A ∈ Rn is the indicator vector of A.

▶ Lovász Extension: Given F : {0, 1}n → R, the Lovász

extension f : Rn → R is defined as follows:
▶ For w ∈ Rn , order wj1 ≥ wj2 ≥ · · · ≥ wjn , and define:
n
X
f (w ) = wj1 F ({j1 })+ wjk [F ({j1 , . . . , jk })−F ({j1 , . . . , jk−1 })]
k=2
n
X
= wj1 F ({j1 }) + wjk FVk−1 (jk ),
k=2

where Vk = {j1 , . . . , jk }.
▶ Intuition: The Lovász extension sums the marginal gains of F ,
weighted by the components of w .
Lovász Extension: Equivalent Definitions
The following are equivalent definitions of the Lovász Extension:
1.
n
X
f (w ) = wj1 F ({j1 }) + wjk FVk−1 (jk )
k=2
2.
n−1
X
f (w ) = (wjk − wjk+1 )F (Vk ) + wjn F (V )
k=1
3. Z ∞
f (w ) = F (w ≥ z)dz + wjn F (V )
wj n

4.
f (w ) = sup w T x
x∈P(F )

Where P(F ) = {x ∈ Rn
: ∀A ⊆ V , x(A) ≤ F (A)} is the
submodular polyhedron.
Properties of Lovász Extension

▶ f is indeed an extension of F : For A ⊆ V ,

f (1A ) = F (A).

▶ f is piecewise affine.
▶ f is convex if and only if F is submodular.
▶ If f is restricted to [0, 1]n , then f attains its minimum at the
corner:
min f (w ) = min F (x).
w ∈[0,1]n x∈{0,1}n
Minimization of Submodular Functions

▶ Suppose we want to find the minimizing set of a submodular

function. That is, we want to find:

A∗ = arg min{F (A) : A ⊆ V }.

▶ By the Lovász extension, this is equivalent to solving:

arg min{f (w ) : w ∈ [0, 1]n },

where f is the Lovász extension of F .

Theorem
f can be minimized using the Ellipsoid method in O(n8 log2 n).
Example: Clustering

▶ Suppose we want to partition V into k clusters A1 , . . . , Ak

such that:
k
X
F (A1 , . . . , Ak ) = E (Ai ),
i=1

where E is some submodular function such as entropy or a cut

function.
▶ In the special case of k = 2, we have:

F (A) = E (A) + E (V \ A),

which is symmetric and submodular. Thus, we can apply

Queyranne’s algorithm.
Theorem (Queyranne 98)

Statement
If F is a symmetric submodular function, then there is a fully
combinatorial algorithm for solving:

arg min{F (A) : A ⊆ V , 0 < |A| < n}

with runtime O(n3 ).

Example: Clustering (Greedy Splitting Algorithm)

▶ When k > 2, we can apply a greedy splitting algorithm:

1. Initially, let the partition P1 = {V }.
2. For i = 1, . . . , k − 1:
▶ For each Cj ∈ Pi :
▶ Get a partition Pij from splitting Cj into 2 using Queyranne’s
algorithm.
▶ Set Pi+1 = arg min F (Pij ).

Theorem
If P is the partition of size k from the greedy splitting algorithm,
then:  
2
F (P) ≤ 2 − F (Popt ).
k
Submodular Maximization

▶ Even though submodular functions are defined to emulate

concave functions, in practice they behave like convex ones.
Convex functions:
▶ Minimizing ⇒ polynomial time.
▶ Maximizing ⇒ NP-hard.
Submodular functions:
▶ Minimizing ⇒ polynomial time.
▶ Maximizing ⇒ NP-hard.
▶ But: All hope is not lost, as we can sometimes efficiently get
approximate guarantees!
Monotonic Functions
▶ We say that F is monotonic if A ⊆ B, then:

F (A) ≤ F (B).

Some examples include:

▶ Coverage Function: If (Ai )i∈V are measurable sets, then for
A ⊆ B ⊆ V:

[ [
F (A) = Ai ≤ Ai = F (B).
i∈A i∈B

▶ Entropy: If (Xi )i∈V are random variables and

B = A ∪ C ⊆ V , then:

F (B) = H(XA , XC ) = H(XA ) + H(XC |XA ) ≥ H(XA ) = F (A).

▶ Similarly, Information Gain is another example.

Greedy Algorithm
▶ For monotonic functions, F is clearly maximized at V . We are
interested in the constraint problem:

arg max F (A).

|A|≤k

▶ We will apply the greedy approach:

1. Initialize A0 = ∅.
2. For i = 1 to k:
▶ xi = arg maxx FAi−1 (x) = arg maxx F (Ai−1 ∪ {x}) − F (Ai−1 ).
▶ Ai = Ai−1 ∪ {xi }.

Theorem (Nemhauser et al. 78)

Given a monotonic submodular function F , then:
 
1
F (Agreedy ) ≥ 1 − max F (A) ≈ 0.63 max F (A).
e |A|≤k |A|≤k
Example: Sensor Placement Problem

▶ Goal: Deploy k sensors to monitor a spatial phenomenon by

maximizing the area covered.
▶ Key observation: Adding a sensor is more valuable when few
sensors are deployed and less valuable when many are already
placed.
▶ Total area covered by sensors is a submodular function over
sets of sensor locations.
▶ Krause and Guestrin (2007): Many utility functions in
sensor placement, such as improvement in prediction accuracy
(using probabilistic models), are submodular.
Stochastic Variant: Sensor Failures

▶ Sensors are deployed one at a time, with each sensor having a

probability of failure.
▶ Goal: Maximize the area covered by functioning sensors.
▶ Key challenge: When deploying a new sensor, consider past
sensor failures.
▶ Asadpour et al. (2008): Studied independent random
failures in sensors.
Adaptive Submodularity

▶ Adaptive Submodularity: Extends submodularity to

stochastic settings.
▶ The coverage objective in the sensor placement problem is
shown to be adaptive submodular.
▶ This allows handling general settings, such as:
▶ Failures of varying severity (beyond all-or-nothing).
▶ More complex deployment scenarios.
Adaptive Stochastic Optimization
▶ Setup:
▶ E : Finite set of items (e.g., sensor locations).
▶ ϕ : E → O: A realization mapping each item e ∈ E to a state
in O (e.g., working or failed).
▶ Φ: Random realization with prior p(ϕ) = Pr[Φ = ϕ].
▶ Sequential Process:
▶ Items e ∈ E are selected sequentially.
▶ Observations Φ(e) are revealed after each selection, informing
subsequent decisions.
▶ Partial Realizations:
▶ ψ ⊆ E × O: Observed states of selected items.
▶ Domain: dom(ψ) = {e ∈ E : e is observed}.
▶ ϕ ∼ ψ if ϕ(e) = o for all (e, o) ∈ ψ.
▶ Posterior Belief:

p(ϕ | ψ) = Pr[Φ = ϕ | Φ ∼ ψ].

Policies in Adaptive Stochastic Optimization

▶ Definition: A policy π maps partial realizations ψ to an item

e ∈ E , specifying the next item to select.
▶ Termination: The policy terminates if ψ ∈ / dom(π), where
dom(π) is the set of partial realizations where π is defined.
▶ Domain Closure: dom(π) must be closed under
subrealizations: if ψ ′ ∈ dom(π) and ψ ⊆ ψ ′ , then
ψ ∈ dom(π).
▶ Items Selected: E (π, ϕ): The set of items selected by π
under realization ϕ.
Adaptive Stochastic Maximization Problem
▶ We aim to maximize a utility function:

f : 2E × O E → R≥0 ,

which depends on the items selected and their states (e.g.,

total area covered by working sensors).
▶ Expected Utility: The expected utility of a policy π is:

favg (π) := E[f (E (π, Φ), Φ)],

where the expectation is taken with respect to p(ϕ).

▶ Objective: Find a policy π ∗ such that:

π ∗ ∈ arg max favg (π) subject to |E (π, ϕ)| ≤ k ∀ϕ,

π

where k is a budget on the number of items that can be

picked (e.g., adaptively selecting k sensor locations).
Definition: Conditional Expected Marginal Benefit
▶ Given a partial realization ψ and an item e, the conditional
expected marginal benefit of e, conditioned on having
observed ψ, is:

∆(e | ψ) := E [f (dom(ψ) ∪ {e}, Φ) − f (dom(ψ), Φ) | Φ ∼ ψ] .

▶ Similarly, the conditional expected marginal benefit of a policy

π is:

∆(π | ψ) := E [f (dom(ψ) ∪ E (π, Φ), Φ) − f (dom(ψ), Φ) | Φ ∼ ψ] .

▶ The expectation is computed with respect to

p(ϕ | ψ) = Pr[Φ = ϕ | Φ ∼ ψ].
Example (Sensor Placement):
▶ ∆(e | ψ) quantifies the expected additional area covered by
placing a sensor at location e, considering whether the sensor
will fail or not, and the area already covered by placed sensors.
Definitions: Adaptive Monotonicity and Submodularity
▶ Definition 2 (Adaptive Monotonicity): A function
f : 2E × O E → R≥0 is adaptive monotone with respect to
distribution p(ϕ) if the conditional expected marginal benefit
of any item is nonnegative. Formally, for all ψ with
Pr[Φ ∼ ψ] > 0 and all e ∈ E , we have:

∆(e | ψ) ≥ 0.

▶ Definition 3 (Adaptive Submodularity): A function

f : 2E × O E → R≥0 is adaptive submodular with respect to
distribution p(ϕ) if the conditional expected marginal benefit
of any fixed item does not increase as more items are selected
and their states are observed. Formally, for all ψ and ψ ′ such
that ψ ⊆ ψ ′ , and for all e ∈ E \ dom(ψ ′ ), we have:

∆(e | ψ) ≥ ∆(e | ψ ′ ).
Properties of Adaptive Monotone Submodular Functions

▶ Adaptive monotonicity and submodularity enjoy closure

properties similar to monotone submodular functions.
▶ If w1 , . . . , wm ≥ 0 and f1 , . . . , fm are adaptive monotone
submodular functions with respect to p(ϕ), then:
m
X
f (A, ϕ) = wi fi (A, ϕ)
i=1

is adaptive monotone submodular with respect to p(ϕ).

▶ For a fixed constant c ≥ 0 and an adaptive monotone
submodular function f , the function:

g (E , ϕ) = min(f (E , ϕ), c)

is adaptive monotone submodular.

Properties of Adaptive Monotone Submodular Functions

▶ Adaptive monotone submodularity is preserved under

restriction:
▶ If f : 2E × O E → R≥0 is adaptive monotone submodular with
respect to p(ϕ), then for any e ∈ E , the function:

g (A, ϕ) := f (A, ϕ) ∀A ⊆ E \ {e}

is also adaptive monotone submodular.

▶ Finally, for each partial realization ψ, the conditional function:

g (A, ϕ) := f (A ∪ dom(ψ), ϕ)

is adaptive monotone submodular with respect to

p(ϕ | ψ) := Pr[Φ = ϕ | Φ ∼ ψ].
The Adaptive Greedy Policy
▶ The classical non-adaptive greedy algorithm generalizes to the
adaptive greedy policy πgreedy , which myopically increases
the expected objective value at each iteration based on
current observations.
▶ Objective: For f : 2E × O E → R≥0 , given a partial
realization ψ, the policy selects the item e that maximizes the
conditional expected marginal benefit:
∆(e | ψ),
as defined in Eq. (8), conditioned on Φ ∼ ψ.
▶ Pseudocode: The pseudocode for the adaptive greedy
algorithm differs from the classic greedy algorithm
(Nemhauser et al., 1978) in how it updates the observed
states after selecting e ∗ .
▶ Termination: The algorithm continues until:
▶ The quota k is met (for coverage objectives).
▶ The objective value converges (for minimization/maximization
objectives).
Note

▶ What we saw is just a simple notion. But, we can tinker with

the definition and change it according to the problem sets, or
maybe prove better bounds on the algorithms.
▶ For example, we also have strong adaptive submodularity as
well which we won’t discuss.
▶ In a practical setting, we don’t usually pick objects one by
one, but rather in batches.
▶ For adaptive submodular functions, we have a semi-adaptive
greedy policy as well!
Adaptive Stochastic Minimum Cost Cover

Objective: To find the cheapest policy π ∗ that achieves a

specified utility quota Q, minimizing the number of items picked.
Formal Definition:
▶ Define the average cost of a policy π as:

cavg (π) := E[|E (π, Φ)|],

where |E (π, Φ)| is the number of items picked by π under

realization Φ.
▶ The goal is to find:

π ∗ ∈ arg min cavg (π) such that f (E (π, ϕ), ϕ) ≥ Q ∀ϕ.

π

Problem Name: This is called the Adaptive Stochastic

Minimum Cost Cover problem.
Semi-Adaptive Stochastic Minimum Cost Coverage

Algorithm: Semi-Adaptive Greedy Policy for Minimum Cost

Coverage
▶ Input: Ground set E , quota Q, distribution p(ϕ), function
f (·), and ϵ > 0.
1. Initialize: A ← ∅, ψ ′ ← ∅, i ← 1.
2. While f (A, ψ ′ ) < Q:
2.1 While RIG(i, ψ ′ ) ≥ (1 − ϵ):
▶ e ∗ ← arg maxe∈E \A SAV(e, i, ψ ′ ).
▶ A ← A ∪ {e ∗ }.
2.2 End while.
2.3 ψ ′′ ← query all elements in A \ dom(ψ ′ ).
2.4 ψ ′ ← ψ ′ ∪ ψ ′′ .
3. End while.
4. Return: A.
Performance of the Semi-Adaptive Greedy Policy

Theorem: Assume there exists a value η ∈ (0, Q] such that

f (ψ) > Q − η implies f (ψ) = Q for all ψ. Let π ∗ be an arbitrary
policy that achieves f (π ∗ ) = Q for all realizations ϕ. Let π denote
the semi-adaptive greedy policy (Algorithm 4). Then:

cavg (π ∗ ) + 1
   
nQ
cavg (π) ≤ log + 1.
1−ϵ η

Implications:
▶ This bounds the performance of the semi-adaptive greedy
policy relative to the optimal policy π ∗ .
▶ Demonstrates the logarithmic dependence on the ratio nQ
η ,
highlighting efficiency.
Active Learning

▶ What is Active Learning?

▶ A machine learning paradigm where the model selectively
queries the labels for the most informative data points.
▶ Why Use Active Learning?
▶ Reduces the labeling effort by focusing on uncertain or
representative samples.
▶ Efficiently builds high-performing models with fewer labeled
samples.
▶ Core Components:
▶ Uncertainty Sampling: Queries samples the model is most
uncertain about.
▶ Diversity Sampling: Ensures a diverse set of queries to cover
the feature space.
▶ Applications:
▶ Image classification, text categorization, medical diagnosis, etc.
Active Learning - Naive Bayes - Submodular optimization
▶ Problem Setup:
▶ Training set: V = {(xi , yi )}m
i=1 , where:
▶ xi ∈ X d : d-dimensional feature vector, with features from
finite set X .
▶ yi ∈ Y : Class label from finite set Y .
▶ Partition: V = V1 ∪ V2 ∪ · · · ∪ VY , where Vy contains samples
with label y .
▶ Model Parameters θ(S):
▶ Maximum Likelihood (ML) estimates:

my (S) mxj y (S)

p(y ) = , p(x j = xj | y ) = ,
|S| my (S)

where:
X X
my (S) = 1yi =y , mxj y (S) = 1x j =xj ,yi =y .
i
i∈S i∈S
Data Subset Selection Optimization Problem
▶ We have to choose S ⊆ V such that it is the most uncertain -
thus the highest entropy of x, y ∈ χd × Y there optimize the
following loss.
X
ℓNB (S) = log p(x i , y i ; θ(S)),
i∈V

d X X
X
ℓNB (S) = mxj ,y (V ) log(mxj ,y (S))
j=1 xj ∈X y ∈Y
X
−(d − 1) my (V ) log(my (S)) − |V | log |S|.
y ∈Y
▶ Optimization Problem:

max ℓNB (S).

|S|=k

The problem becomes a difference of submodular functions

(concavity of ln()) (DS optimization ).
Constraints on the Selected Set S

▶ To solve the problem using submodularity, we would want to

turn the second and third terms constant. We need the
following constraints for that.
▶ Equality Constraint:
▶ The size of S is fixed: |S| = k.
▶ Balanced Set Assumption:
▶ The set S maintains the same class distribution as the whole
dataset V .
▶ For a class y ∈ Y, the number of samples in S ∩ V y is
proportional to its frequency in V :

|V y |
|S ∩ V y | = k .
|V |
y
▶ If k |V |
|V | is not an integer, it is rounded to the nearest integer.
Final Formulation
▶ Partition Matroid:
▶ Let M(V , I ), partition matroid using the partition {V y }y ∈Y .
▶ The set of bases B(M) is:

|V y |
B(M) = {S ⊆ V : |S ∩ V y | = k , ∀y ∈ Y}.
|V |

▶ First term of LNB (S)

d X X
X
fNB (S) = mxj ,y (V ) log mxj ,y (S).
j=1 xj ∈X y ∈Y

▶ The optimization problem reduces to:

▶ Given S ∈ B(M), maximize:

max fNB (S).

S∈B(M)

▶ Can be solved efficiently with a greedy algorithm as in

Nemhauser et Al (1978)
Matryoshka Representation Learning
▶ Overview:
▶ A flexible framework for representation learning adaptable to
various setups.
▶ Produces a hierarchical representation z ∈ Rd by optimizing
over multiple nested representations.
▶ Training:
▶ Optimize the original loss L(·) for hierarchical subsets of z at
different granularities:

L(z1:d/16 ), L(z1:d/8 ), L(z1:d/4 ), . . . , L(z1:d ).

▶ Combined loss:
X
L(z) = L(z1:d/k ).
k∈1,2,4,...

▶ Key Advantages:
▶ Efficiently optimizes across O(log d) representation sizes.
▶ Enables adaptive deployment across environments and tasks.
MatFormer Structure

▶ Defines g nested Transformer blocks T1 ⊂ T2 ⊂ · · · ⊂ Tg ,

where:
▶ Parameters of Ti are contained in Ti+1 .
▶ Focuses on the Feed-Forward Network (FFN) block, which
dominates the computational cost ( 60% for LLMs and ViTs).
▶ Introduces a matryoshka nested structure with g granularities
in the hidden representation dff of the FFN.
MatFormer: Nested FFN Blocks

▶ FFN block has a single hidden layer with dff neurons.

▶ Granular structure splits neurons into subsets
m1 ≤ m2 ≤ · · · ≤ mg = dff .
▶ FFN operation at granularity Ti for input x ∈ Rdmodel :

TiFFN (x) = σ(x · W1 [0 : mi ]⊤ ) · W2 [0 : mi ],

where:
▶ W1 , W2 are weight matrices.
▶ σ: Non-linearity (e.g., GELU or squared ReLU).
Granularities and Submodels

▶ g = 4 granularities with FFN ratios {0.5, 1, 2, 4}.

▶ Nested hidden neuron sizes: {dff /8, dff /4, dff /2, dff }.
▶ MatFormer model combines these granular blocks into g
nested submodels:

M1 ⊂ M2 ⊂ · · · ⊂ Mg .

▶ Submodel Mi : Formed by stacking Ti across layers.

▶ Input and output embeddings are shared across submodels.
Training MatFormer

▶ Jointly optimizes all g nested submodels using weighted loss:

g
X
LJOINT (x, y ) = λi · L(Mi (x), y ),
i=1

where:
▶ λi > 0: Weight of the i-th submodel (default: uniform).
▶ L(·): Loss function between output and target.
▶ Optimized using stochastic gradient descent (SGD).
▶ Training can be carried out with a constant factor overhead,
with memoization optimizations.
Moving Forward

▶ We come to an impasse right now.

▶ MRL imposed structure on the Mat-Former creates a
spectrum of information across the embedding bases with
more information towards the lower bases.
▶ If we consider the set S of embedding bases
▶ The question is, can we choose an embedding with arbitrary
bases compared to the mat former imposed embeddings?
▶ Can we have a submodular function to choose such a set
maximizing a certain criterion we want?
▶ What kind of criteria can we even fit in a submodular
function?
▶ Do we have to stick with a variant of submodularity?