Universal set families for maximizing submodular & XOS

Universal set families for maximizing submodular & XOS

Introduction

Imagine you’re trying to maximize a score over all subsets of items—except you’re only allowed to “look up” the score for a carefully chosen list of subsets. No adaptivity, no feedback loops, no second chances. Just one universal family of sets, queried once, and you hope that for any objective function in a broad class, one of those queried sets lands close to the best possible value.

That’s exactly the game studied in new research by Chandra Chekuri, Richard Ueltzen, and Jan Vondrak, in the paper “Universal set families for maximization of nonnegative submodular and XOS functions” (arXiv link). The authors ask whether there exists a small, predetermined family of subsets—a set system (\mathcal F \subseteq 2^{[n]})—such that for every nonnegative submodular (and also certain XOS) set function (f), the maximum of (f(S)) over (S \in \mathcal F) is always a constant-factor approximation to (\max_{T \subseteq [n]} f(T)).

The headline is subtle but powerful: the answer depends on which function class you allow. For general nonnegative submodular functions, the paper builds universal families of size about (\Theta(\log n / \log\log n)) in approximation terms (with explicit constructions), and proves that even “good-looking” randomness like pairwise independence can fail. For a related class—absolute XOS—the story becomes much tighter: the paper gives matching upper and lower bounds (up to constants), including constructions of polynomial-size universal families and impossibility results for smaller ones.

Why This Matters

This is relevant right now because a lot of modern optimization pipelines are increasingly constrained by query cost and parallelism. Think: evaluating a candidate solution might mean running an expensive simulation, querying an external service, or triggering a costly offline job. In those settings, you often can’t adaptively choose the next queries based on results—you need a fixed batch. So the adaptivity question becomes: “Can I precompute a menu of options that will still contain something good no matter what the underlying scoring rule is?”

The paper’s model is a clean abstraction of that: you only get value-oracle access to (f(S)), and you’re restricted to a universal family of subsets. If you can get even a constant approximation with non-adaptive queries, then you’ve essentially solved a “robust batch optimization” problem for that class of objective functions.

Where it connects to prior AI optimization work: there’s been a big push toward approximation and surrogate objectives—use structure (like submodularity) to avoid brute-force search. But many of those algorithms assume either monotonicity, adaptivity, or richer access than a plain value oracle. This paper goes after a harsher constraint: no adaptivity at all—and still asks for worst-case guarantees.

Most importantly, it shows something counterintuitive: even if a distribution over subsets is uniformly pairwise independent (a common “nice randomness” property), that does not automatically translate into constant-factor performance for submodular maximization. So if your instinct is “just sample like a randomized rounding scheme,” the paper is a warning label: for universal (worst-case) guarantees, naive independence properties won’t save you.

Main Content Sections

From “rounds of queries” to one fixed batch of subsets

Submodular maximization is one of the central pillars in discrete optimization. The reason is that submodularity captures diminishing returns, which models real-world “coverage”-type objectives and also shows up in graph cuts, influence, sensing, and more.

In this paper, the computational model is very direct: you have an (f(S)) oracle that tells you the value of the objective for subset (S\subseteq [n]). Your job is to approximate:
[
\max_{T \subseteq [n]} f(T)
]
using only evaluations at sets you query.

The adaptivity angle: previous work asked how many rounds of parallel queries you need, where the next batch can depend on what you learned before. With adaptivity you can do better; without it, you’re forced to choose a single predetermined family (\mathcal Fn) and then take:
[
\max{S \in \mathcal F_n} f(S).
]

A classical result (in a different model) says: a random uniform set often gives a constant factor in expectation. Concretely, the paper invokes a lemma (from earlier work) that for uniformly random (R\subseteq [n]),
[
\mathbb{E}[f(R)] \ge \frac{1}{4}\max_{S\subseteq [n]} f(S)
]
for the nonnegative submodular setting they consider. So if you were allowed to sample randomly and keep trying until you’re happy, you could succeed with high probability after polynomial sampling.

But the universal-family restriction is harsher: you need a certificate-free guarantee. In other words, you want a deterministic or fixed-batch selection (\mathcal F_n) such that for every function (f) in the class, the best value on that batch is always a constant fraction of the global maximum.

This turns the problem into a combinatorial design question: build a family (\mathcal F_n) that is “rich enough” to hit a near-optimal solution for every possible submodular function.

Comparison: what’s known vs. what this paper targets

Here’s the landscape in the paper’s framing (not exhaustive, but useful to pin down the contrast):

This paper focuses squarely on the last row.

How submodular functions get reduced to “submodular connectivity” to build universal families

A clever move in the paper is reducing the general nonnegative submodular maximization problem to a restricted but more structured class. The core object becomes a submodular connectivity function: a nonnegative, symmetric, normalized submodular function with (f(\emptyset)=0).

Given an arbitrary nonnegative submodular function (f), the authors define a “symmetrized” version (on the same ground set):
[
f^{\text{sym}}(A) = f(A)+f(V\setminus A)-f(V)-f(\emptyset).
]
This new function is:
- submodular,
- symmetric ((f^{\text{sym}}(A)=f^{\text{sym}}(V\setminus A))),
- nonnegative, and
- has the right normalization property to fit the connectivity framework.

Why do this? Because the universal family design reduces to controlling values on sets that arise from the family via closure operations (union, intersection, complement) applied in a structured algebraic way.

In the paper, this shows up as: if you can guarantee approximation for connectivity functions, you can get an approximation for general nonnegative submodular functions by paying a constant-factor penalty (the paper tracks this carefully and ends up with a constant like (2) and then another (2), yielding a (2^2) type loss in the reduction).

The “separation” intuition: why pairs matter

A key structural requirement appears early and then becomes a recurring theme: for meaningful approximation, the family must separate elements. Informally, for the Max Cut-style submodular examples, if two items (i\neq j) are never distinguishable by any set in (\mathcal F), then a cut-like function can “hide” its maximum outside your queried sets.

The authors formalize this with constructions where each pair is separated by at least one set in the family. That becomes necessary (even for specific cut functions), and it also becomes the engine behind their explicit designs.

Coordinate-aligned layers: a simple universal family that yields a logarithmic approximation

Let’s talk constructions. The paper first gives a very clean, almost “geometric” family.

Assume (n = 2^d) (or pad with dummy elements if needed). View the ground set (V) as the vertices of a (d)-dimensional hypercube (V={0,1}^d). For each coordinate (i\in[d]), define the set:
[
Hi = {x\in{0,1}^d : xi = 0}.
]
Then the family (\mathcal Fn) is simply ({H1,\dots,Hd}), of size (\le \lceil \log2 n\rceil).

This sounds tiny—just “coordinate halfspaces.” But the paper shows that if you take any nonnegative symmetric submodular connectivity function (f), there is always a set in this family whose value is within a logarithmic factor of the optimum. Concretely, they show a family of size at most (\lceil \log_2 n\rceil) gives approximation factor:
- (O(\log n)) style (the paper expresses this as a tight logarithmic factor for this specific type of family).

They also show this is essentially tight for that particular construction, using a hypercube cut example: the optimum cut scales like (d2^{d-1}), while the best coordinate-aligned cut only achieves about (2^{d-1}) times a smaller dimension contribution.

Why this works despite seeming “too simple”

The heart of the proof relies on an algebraic closure argument: take the initial family sets and repeatedly apply union/intersection/complement. This creates a sigma-algebra-like collection of sets, and submodularity lets you bound the value of any set in that closure by combinations of values on the generators. Since for the hypercube coordinate halfspaces the closure becomes the entire powerset in the relevant sense, you can argue that some generator must already capture a large fraction of the optimum.

That proof strategy is one of the paper’s motifs: start with a separating family, show it generates enough structure, and then use submodularity to propagate value bounds back to the generators.

Improving the trade-off with unions of parallel layers (subpolynomial family size)

Want better approximation? Increase the family a bit. The paper develops a second construction that uses more structured “partitions” rather than just single halfspaces.

Instead of splitting the cube with one coordinate threshold (like (x_i=0)), they partition coordinates into (r) levels and consider the sigma-algebras induced by these partitions. Then they take unions over different coordinates.

The result is a family (\mathcal F_n) with size roughly (n^{o(1)}) (subpolynomial), achieving an approximation factor:
[
O!\left(\frac{\log n}{\log\log n}\right).
]
More generally, they introduce a tunable parameter (\alpha) that trades off:
- family size (from subpolynomial up to quasipolynomial),
- approximation factor (improves when the family grows).

The construction’s punchline: you can beat the naive (O(\log n)) approximation while still keeping (\mathcal F_n) tiny compared to (2^n).

The important “don’t overpromise” lesson: pairwise independence isn’t enough

A natural thought is: maybe we can do with a more probabilistic design. Uniformly pairwise independent distributions are often a gold standard because they preserve pairwise correlations exactly like full randomness.

The paper tests this hope and gives a negative result:
- for infinitely many (n),
- they construct a uniformly pairwise independent distribution supported on a family (\mathcal F),
- and a symmetric submodular function (f) where the expectation over that distribution is far from the maximum-case expectation (and thus the universal approximation fails).

So even though pairwise independence is “good” for many random rounding arguments, it’s not a universal fix for submodular maximization.

They also note that for certain polynomially representable subclasses of submodular functions, a union-bound style argument does recover constant-factor universal families using polynomial randomness—though the family isn’t explicit.

Absolute XOS functions: polynomial universal families with matching optimal bounds

Now for the part where the story becomes much cleaner.

The paper extends beyond submodular functions to XOS (also called “fractionally subadditive”) objectives. XOS functions are maxima of additive pieces. Absolute XOS is a variant where those additive pieces are wrapped in an absolute value:
[
f(S)=\max{i} \left| \sum{j\in S} wi(j) + ci \right|.
]

Why absolute XOS matters: it generalizes important “connectivity-like” symmetric objectives and connects directly to discrepancy and approximation of signed sums.

Explicit good news: existence of polynomial-size universal families

The authors show that for every (n), there exists a universal family (\mathcal F_n) for absolute XOS functions of size (\text{poly}(n)) achieving a constant-factor approximation (with the approximation factor depending on the family size). In particular, they provide:
- an explicit construction of size (n+1) achieving (\Omega(1/\sqrt n)) approximation when the family is very small (using Hadamard bases),
- and a more sophisticated randomized net argument construction that yields polynomial-family sizes such that the approximation factor matches their lower bounds up to constants.

Tightness: discrepancy kills “too small” families

They also prove near-optimal lower bounds. The key intuition is tied to combinatorial discrepancy: if your family (\mathcal F) is too small, then there exist nontrivial signed weight assignments whose “balance” on each queried set is small—meaning absolute XOS functions built from those weights will look unimpressive on (\mathcal F) while being large elsewhere.

Spencer’s discrepancy theorem appears directly in the lower bound mechanism (in a quantitative way). This is why the absolute XOS case is especially satisfying: upper and lower bounds line up tightly, so we learn “how universal you can be” without blowing up the family.

Contrast with submodular: XOS gives tighter characterization

For submodular functions, they can show universal families with approximation roughly (O(\log n / \log\log n)) using explicit constructions, but constant approximation with polynomial families is still unclear (and pairwise independence is insufficient as a shortcut).
For absolute XOS, they essentially resolve the dependence on family size: the attainable approximation factor is characterized up to constants.

The result is a roadmap: submodularity is harder; XOS is more structured and thus more “designable” with provable tight bounds.

Key Takeaways

• Universal families are deterministic batch query strategies: pick a fixed set family (\mathcal Fn) once, then output (\max{S\in\mathcal F_n} f(S)).
• For nonnegative submodular functions, the paper gives explicit universal families:
  • size (\le \lceil \log_2 n\rceil) with logarithmic-factor approximation (coordinate halfspaces),
  • improved trade-offs using unions of parallel layers, reaching about (O(\log n/\log\log n)) approximation with families of size (n^{o(1)}).
• Pairwise independence is not enough for universal approximation of submodular maximization: the paper constructs counterexamples where pairwise-independent sampling fails badly.
• For absolute XOS functions, the situation is much more complete:
  • there exist polynomial-size universal families,
  • and the paper proves matching optimal bounds (up to constants) using discrepancy-based lower bounds.
• Practical implication: if your objective behaves like absolute XOS, you can often get strong worst-case approximation with a fixed batch of queries. If it’s truly general submodular, you should expect stronger limitations unless you allow larger families or extra structure.

If you tell me what kind of objective you have in mind (graph cut? coverage? facility location? influence?), I can translate these results into a more concrete “what family size and what approximation should you expect” estimate in plain terms.