Chapter 49: Combinatorics in Algorithms, Learning and Optimization

How does a family's combinatorial dimension control learnability?

A binary hypothesis is a function $h:X\to\{0,1\}$, or equivalently the subset on which it predicts one. Given a family $\mathcal H$, its trace on a finite set $S\subseteq X$ is $\{h^{-1}(1)\cap S:h\in\mathcal H\}$. The family shatters $S$ when its trace contains all $2^{\lvert S\rvert}$ subsets. Its VC dimension is the largest shattered-set size, or infinity if no finite bound exists.

Take the ordered domain $X=\{1,2,3,4\}$ and the five prefix hypotheses $h_j(x)=\mathbf1\{x\le j\}$ for $j=0,\ldots,4$. Their full-domain labels are $0000,1000,1100,1110,1111$. A singleton can receive either label, but two ordered points cannot receive labels $0,1$: a prefix containing the later point must contain the earlier one. Thus the VC dimension is exactly one. On $m$ distinct ordered points, unrestricted real thresholds realize only $m+1$ label patterns rather than $2^m$.

Why does this matter for learning? Suppose examples are drawn independently from a fixed distribution on $X$, labels come from a target $h^{\ast}\in\mathcal H$, and a learner returns a hypothesis consistent with all $m$ examples. If a fixed hypothesis has true error greater than $\varepsilon$, it survives all examples with probability at most $(1-\varepsilon)^m\le e^{-m\varepsilon}$. For the five-hypothesis family, a union bound gives

$$\Pr\bigl(\text{some consistent hypothesis has error greater than }\varepsilon\bigr)\le5e^{-m\varepsilon}.$$

For $\varepsilon=1/10$ and $\delta=1/20$, $m=47$ suffices because $5e^{-47/10}\lt1/20$. This is a complete finite-family, realizable learning bound. It requires independent examples, an unchanged distribution, and a target in the class. It does not apply automatically to noisy labels, adaptive bandit observations, or a class selected after inspecting the sample.

Combinatorial dimension controls the number of possible label patterns; it does not by itself make empirical optimization easy. Nor does small prediction error guarantee that a learned scheduling or coverage heuristic returns feasible or near-optimal solutions. The final investigation treats those as separate proof obligations.

This definition, the prefix example, and the union-bound proof are the chapter foundation. The numbered sections are optional research extensions. Earlier connections are extremal sets, the probabilistic method, combinatorial algorithms, optimization, and approximate counting.

49.1 VC dimension and combinatorial learning theory

Optional extension; not required to complete the chapter foundation.

Define the growth function $\Pi_{\mathcal H}(m)$ as the largest number of distinct prediction vectors produced on $m$ domain points. Repeated points cannot increase the maximum. This is the combinatorial invariant used to count possible restrictions of a hypothesis class before a probability bound is applied.

For binary classification, let $L(h)=\Pr(h(X)\ne Y)$ and $\widehat L_m(h)=m^{-1}\sum_i\mathbf1\{h(X_i)\ne Y_i\}$. These are true and empirical zero-one risks. Uniform convergence controls all $h$ simultaneously; an empirical minimizer can then be compared with a population minimizer. The specifically combinatorial ingredient is the number of distinct restrictions, not the total number of parameter vectors in a neural-network implementation.

Solved example. The five prefix hypotheses shatter each singleton. On any two distinct points $a\lt b$, the traces are $00,10,11$, with $01$ absent. Their VC dimension is one, and on the full four-point domain their growth is five. A family with the same cardinality need not have the same traces on every subset; counting five hypotheses is an upper bound, whereas tracing their restrictions identifies their combinatorial structure.

The foundational established uniform-convergence theory is Vapnik and Chervonenkis. Proof scope: the finite-class realizable guarantee has been proved in the foundation. General measurable infinite-class learning theorems require uniform convergence and suitable measurability hypotheses; those are not inferred solely from this four-point table. The computations here are all in a finite domain, avoiding such measurability issues.

Exercise. What is the VC dimension of all subsets of a three-element domain? Hint: all eight labelings are available. Solution: it is three: the whole domain is shattered, and no larger domain subset exists. Its growth on those points is eight, unlike the four prefix patterns on three ordered points.

49.2 Sauer–Shelah lemma and sample complexity

Optional extension; not required to complete the chapter foundation.

The established Sauer–Shelah lemma states that if a set family has VC dimension at most $d$, then

$$\Pi_{\mathcal H}(m)\le\sum_{i=0}^{\min(d,m)}\binom mi.$$

For $1\le d\le m$, the sum is at most $(em/d)^d$. A primary source is Sauer's On the Density of Families of Sets90019-2).

Proof. Restrict to an $m$-point domain and split traces according to whether they contain the last point. Let $\mathcal A$ be the union of the resulting traces on the other $m-1$ points and $\mathcal B$ their intersection. Then $\lvert\mathcal H\rvert=\lvert\mathcal A\rvert+\lvert\mathcal B\rvert$. The union has VC dimension at most $d$, while the intersection has dimension at most $d-1$: a set shattered by both sides would be shattered together with the last point in the original family. Induct and use Pascal's identity. The base $d=0$ permits at most one trace; if $d\ge m$, the trivial bound $2^m$ applies. This proves the combinatorial bound.

For independent labeled examples and a finite hypothesis class, a conservative established VC deviation bound is

$$\Pr\left(\sup_{h\in\mathcal H}\lvert L(h)-\widehat L_m(h)\rvert\gt\varepsilon\right)\le8\Pi_{\mathcal H}(2m)e^{-m\varepsilon^2/32}.$$

The right side may exceed one, in which case it is uninformative. Proof sketch and omitted prerequisites: introduce an independent ghost sample, symmetrize by random swaps, and union-bound over the restricted label vectors on the combined sample. The constant-tracking symmetrization proof is omitted; the bound is deliberately conservative, not a sharp sample-complexity assertion. The primary uniform-convergence framework is Vapnik–Chervonenkis. Inserting Sauer's bound gives a sufficient explicit inequality on $m$; do not substitute the faster realizable $1/\varepsilon$ dependence for a noisy uniform-deviation guarantee.

Exercise. How many traces does a dimension-two class have on five points at most? Hint: sum the first three binomial coefficients. Solution: at most $1+5+10=16$, compared with $32$ possible binary vectors. This is a universal upper bound, not a claim that every dimension-two class realizes sixteen traces.

49.3 Rademacher complexity and combinatorial bounds

Optional extension; not required to complete the chapter foundation.

For sample points $x_1,\ldots,x_m$, define the empirical Rademacher complexity of a real-valued function class by

$$\widehat{\mathfrak R}_m(\mathcal H)=\mathbb E_\sigma\left[\sup_{h\in\mathcal H}\frac1m\sum_{i=1}^m\sigma_i h(x_i)\right],$$

where the signs $\sigma_i$ are independent uniform $\pm1$. This convention has no extra factor two and no absolute value inside the supremum. It measures how well the class can align with random signs on this sample.

If the restricted prediction vectors form a finite set $V\subseteq[0,1]^m$, an established finite-class bound is $\widehat{\mathfrak R}_m\le\sqrt{2\log\lvert V\rvert/m}$. Proof mechanism: exponential-moment control for sign sums, a log-sum-exp bound over $V$, and optimization over its exponential parameter. The full moment proof is omitted. Sauer's bound supplies $\lvert V\rvert\le\Pi_{\mathcal H}(m)$ for binary classes. Primary risk-bound treatment: Bartlett and Mendelson.

Solved example. On three increasing points use prediction vectors $000,100,110,111$. For a sign vector, the maximum numerator is the largest prefix sum, including the empty sum zero. Across the eight sign vectors these maxima are $3,2,1,1,1,0,0,0$, totaling eight. Therefore $\widehat{\mathfrak R}_3=8/(8\cdot3)=1/3$. The SVG displays every dot product, making the supremum and expectation auditable.

For a bounded loss class on independent examples, standard Rademacher bounds convert this kind of complexity into a uniform risk estimate. Apply them to the actual loss functions, not automatically to raw hypothesis outputs: $h(x)$ and $\mathbf1\{h(x)\ne y\}$ are different functions. The finite restriction counts are the combinatorial bridge; the risk theorem has its own sampling and probability hypotheses.

Exercise. Compute the complexity on the same three points for the singleton class containing only $111$. Hint: there is no adaptive choice inside the supremum. Solution: its expected signed sum is zero, so the complexity is zero. An absolute-value convention would give a different answer; definitions must not be mixed.

49.4 Online learning and Littlestone dimension

Optional extension; not required to complete the chapter foundation.

Online realizable learning reveals a point, asks for a prediction, then reveals a label consistent with one target hypothesis throughout the sequence. A complete binary mistake tree has domain points at its internal nodes and edge labels zero or one. It is shattered if every root-to-leaf label path is realized by a hypothesis. The Littlestone dimension is the largest possible depth. The tree points may depend on earlier labels, unlike a fixed VC-shattered set.

The established optimal deterministic realizable mistake bound equals this dimension. The standard optimal algorithm predicts the branch retaining larger Littlestone dimension; a mistake lowers the remaining dimension. Conversely, a shattered tree lets an adversary choose the opposite label while retaining a realizable path. Primary source: Littlestone's learning paper. Proof scope: this explains the mechanism; the general rank recursion and infinite-class technicalities are omitted.

Solved example. For the five prefixes on $[4]$, query point two at the root. If the label is zero, the remaining indices are $j=0,1$, and point one realizes either next label. If the label is one, the remaining indices are $j=2,3,4$, and point three also permits both labels. This shatters depth two. Depth three needs at least eight distinct hypotheses to realize its eight paths, impossible with five. Thus Littlestone dimension is two although VC dimension is one.

The halving algorithm also makes at most $\lfloor\log_2 5\rfloor=2$ mistakes here because each mistake at least halves the version space. Real thresholds on an unbounded dense ordered domain have VC dimension one but infinite Littlestone dimension: binary-search trees of arbitrary finite depth can be realized. Finite sample learnability and bounded adversarial mistakes are distinct notions.

Exercise. Why does the mistake bound need realizability? Hint: the version space must remain nonempty. Solution: if labels do not come from one fixed member, an adversary can force repeated mistakes after all hypotheses have been eliminated. A dimension bound for realizable sequences does not state a regret guarantee against arbitrary labels.

49.5 Submodular maximization

Optional extension; not required to complete the chapter foundation.

A set function $f$ is submodular when it has diminishing returns: for $S\subseteq T$ and $i\notin T$, $f(S\cup\{i\})-f(S)\ge f(T\cup\{i\})-f(T)$. Assume $f(\varnothing)=0$, nonnegativity, and monotonicity. Under a cardinality constraint $\lvert S\rvert\le k$, greedy repeatedly chooses the largest true marginal gain. The established Nemhauser–Wolsey–Fisher guarantee is

$$f(S_k)\ge\left[1-(1-1/k)^k\right]\operatorname{OPT}\ge(1-1/e)\operatorname{OPT}.$$

Complete proof mechanism. If $O$ is optimal, submodularity bounds $f(O)-f(S_t)$ by the sum of marginal gains of at most $k$ elements of $O\setminus S_t$. Greedy gains at least one-$k$th of this gap. Therefore the remaining gap contracts by $1-1/k$ at each step; iterate from $f(\varnothing)=0$. Monotonicity and the exact marginal oracle are essential.

Solved example. Let items cover resource sets $A=\{1,2,3\}$, $B=\{1,2,4\}$, and $C=\{3,5,6\}$, and let $f$ count the union. Coverage is monotone and submodular because a resource already covered cannot contribute again. With $k=2$ and lexicographic tie-breaking, greedy first selects $A$. The remaining marginal gains are one for $B$ and two for $C$, so it returns $AC$ with value five. The optimum $BC$ covers all six resources. The finite-step guarantee is $3/4$, and $5\ge(3/4)6$.

Predicted scores are not necessarily true marginal gains. If every marginal prediction differs from its true value by at most $\beta$ on every query, choosing the largest predicted value yields a true gain at least the best gain minus $2\beta$. The same recurrence then gives the conservative bound $f(S_k)\ge[1-(1-1/k)^k]\operatorname{OPT}-2k\beta$. Average classification accuracy does not supply this uniform additive oracle guarantee.

Exercise. If static scores rank $A,B,C$ as $0.9,0.8,0.1$, what does top-two selection achieve? Hint: compute the union, not the sum of scores. Solution: it selects $AB$ and covers four resources, below $AC$'s five and $BC$'s six. This is a feasible toy score output, not evidence that a trained model was run or that scores are calibrated marginal estimates.

49.6 Combinatorial bandits

Optional extension; not required to complete the chapter foundation.

Let $q$ ground items have stochastic rewards in $[0,1]$, with fixed means $\mu_i$. A feasible action $S\in\mathcal A$ contains at most $k$ items and earns their sum. Semi-bandit feedback reveals each selected item's reward; bandit feedback reveals only their total. Assume reward vectors are independent and identically distributed across rounds, and each action is selected using past information before the current vector is revealed. Cross-item independence within a round is not needed for the elementary mean-confidence argument below.

Pseudo-regret is $R_T=\sum_{t=1}^T[\mu(S^{\ast})-\mu(S_t)]$, with $\mu(S)=\sum_{i\in S}\mu_i$. A confidence-based method estimates individual means and calls an exact combinatorial oracle to maximize the sum of upper confidence scores. This separates statistical learning from optimization complexity: an oracle may be efficient for some feasible families and hard for others. The established framework and sharper regret analysis are in Kveton and collaborators.

For a transparent bound, let $L=\log(2qT/\delta)$ and use radius $r_i=\sqrt{L/(2N_i)}$ after $N_i\ge1$ observations. Hoeffding and a union bound over items and all first-$s$ sample prefixes, $1\le s\le T$, guarantee $\lvert\widehat\mu_i-\mu_i\rvert\le r_i$ throughout with probability at least $1-\delta$. Exact upper-confidence optimization then gives instantaneous regret at most $2\sum_{i\in S_t}r_i$. Summing $\sum_{s=1}^n s^{-1/2}\le2\sqrt n$ and applying Cauchy–Schwarz yields

$$R_T\le qk+2\sqrt{2qkTL}$$

on that confidence event, if initialization covers every usable item in at most $q$ feasible rounds. The initial-round budget is at most $qk$. Proof scope: the elementary high-probability bound is derived here; it is not claimed optimal, and approximate or learned oracles require an additional oracle-error term. Uniform confidence over sample prefixes is what permits adaptive action choices.

Solved example. For three items, choose any pair and take means $(0.8,0.6,0.2)$. The best pair is $\{1,2\}$ with mean $1.4$. Playing $\{1,3\}$ incurs pseudo-regret $0.4$. Observing rewards $(1,0)$ for those selected items permits separate updates for items one and three; it says nothing about the unseen item two. A total reward of one alone would not reveal which selected item produced it.

Exercise. Why is the iid training bound from the foundation not a direct bandit guarantee? Hint: selected observations depend on earlier rewards. Solution: the observation distribution is action-dependent and adaptive. The prefix-uniform confidence proof and feedback model replace the fixed independent supervised sample assumption.

49.7 Streaming algorithms and combinatorial sketches

Optional extension; not required to complete the chapter foundation.

Section 38.1 in combinatorial algorithms gives optional algorithmic background. The bridge here is that a sketch compresses a large frequency vector into a few linear measurements, while collisions determine the error. A full primary treatment is Cormode and Muthukrishnan's Count-Min paper.

For an insertion-only stream, let $f_i\ge0$ be item frequencies and $N=\sum_i f_i$. A Count-Min sketch uses $d$ independent rows of pairwise-independent hashes into $w$ counters. Insertions increment one counter in each row; a query returns the minimum of its row counters. With $w=\lceil e/\varepsilon\rceil$ and $d=\lceil\log(1/\delta)\rceil$, a fixed query satisfies

$$f_i\le\widehat f_i\le f_i+\varepsilon N$$

with probability at least $1-\delta$. Expected collision noise per row is at most $N/w\le\varepsilon N/e$; Markov bounds row failure by $1/e$, and row independence makes simultaneous failure at most $e^{-d}$. This supplies a complete point-query proof. The result is additive relative to total stream mass, not a relative-error guarantee for every rare item.

Solved example. Let frequencies of $a,b,c,d$ be $(3,1,2,0)$. Use one deterministic illustrative row mapping $(a,b,c,d)$ to $(0,1,0,2)$ and another mapping them to $(0,0,1,2)$. The row counters are $(5,1,0)$ and $(4,2,0)$. Estimates are $(4,1,2,0)$, so only $a$ is overestimated, by one. These two particular hashes illustrate collision behavior; the probability theorem requires randomly chosen families with its width and row hypotheses.

Updates and queries use $O(d)$ counter operations; storage is $O(wd)$ counters, each requiring $O(\log(N+1))$ bits in this integer-frequency model, plus hash descriptions. Arbitrary negative updates invalidate the simple one-sided collision proof, and choosing queries adaptively after inspecting the sketch needs another failure analysis.

Exercise. How can a guarantee be made simultaneous for $q$ queries fixed in advance? Hint: allocate failure probability across queries. Solution: build the sketch with per-query failure at most $\delta/q$ and union-bound, increasing the row count to $\lceil\log(q/\delta)\rceil$. This does not automatically cover an adversary that adapts future inputs and queries to the hidden hash choices.

49.8 Approximation and integrality gaps

Optional extension; not required to complete the chapter foundation.

A relaxation enlarges the feasible region to make optimization easier. For a minimization problem its optimum is a lower bound on the integral optimum; for maximization it is an upper bound. A learned candidate becomes useful only after its original feasibility and objective are checked. Fractional feasibility is not integral feasibility.

Solved example. On a triangle, minimum vertex cover has integral optimum two. Its linear relaxation minimizes $x_1+x_2+x_3$ subject to $x_i+x_j\ge1$ on each edge and $x_i\ge0$. Setting all coordinates to $1/2$ gives value $3/2$, and summing the three inequalities proves no smaller value is possible. The minimization integrality gap is $2/(3/2)=4/3$.

Rounding every coordinate down gives an empty, infeasible set. Thresholding at $1/2$ selects all three vertices, a feasible cover of cost three. For any graph and any feasible fractional cover, this threshold rule covers every edge and selects at most twice the fractional objective, proving a factor-two algorithm when the relaxation is optimized. The learned score cannot replace the edge constraints in that proof.

For a minimization candidate of cost $C$ with a certified lower bound $L\gt0$, $C/L$ is a valid instance-specific approximation certificate. For a maximization candidate value $V$ and certified upper bound $U\gt0$, $V/U$ is a valid lower bound on its ratio to the optimum. These certificates require valid bounds, not a neural prediction of the optimum. They connect learning-guided search to the mathematical relaxation machinery from combinatorial optimization.

Exercise. For the coverage example, use the six-resource total as an upper bound and certify the toy top-two selection. Hint: its feasible value is four. Solution: $V/U=4/6=2/3$. Since $BC$ attains six, that is its exact ratio on this instance. It is not a uniform two-thirds guarantee for arbitrary learned scores or coverage instances.

49.9 Graph neural networks and combinatorial expressivity

Optional extension; not required to complete the chapter foundation.

A standard message-passing network updates a vertex from its previous state and a permutation-invariant aggregation of its neighbors' states, using shared update functions. Under uniform initial features, its ability to distinguish graphs is bounded by one-dimensional Weisfeiler–Lehman color refinement, or 1-WL. Color refinement repeatedly replaces a vertex color by its old color together with the multiset of neighbor colors. Established expressivity results are in Xu, Hu, Leskovec, and Jegelka.

Proof mechanism. Induct on rounds: vertices with the same refinement color have the same previous state and the same multiset of neighbor states, so a shared aggregation/update gives the same next state. With a graph readout depending only on the final vertex-state multiset, indistinguishable color histograms produce indistinguishable outputs. Proof scope: this proves the upper-bound mechanism for the specified model; the matching power of suitably injective architectures and higher-order variants is cited rather than proved.

Solved example. A six-cycle and the disjoint union of two triangles both have six vertices of degree two. With uniform initial features, every vertex sees two copies of the same state at every round in both graphs. All 1-WL histograms and standard message-passing readouts agree. Yet one graph is connected and triangle-free; the other is disconnected with two triangles. Their maximum independent-set sizes are three and two. A graph-level predictor restricted to these features and this architecture cannot assign two different exact optimum values to them.

Unique identifiers, positional features, random features, or higher-order architectures change the hypotheses; the example is not a claim about every graph-learning system. It explains a concrete combinatorial obstacle relevant to optimization labels, rather than treating expressivity as empirical test accuracy.

Exercise. What simple additional graph feature distinguishes this pair? Hint: count a small configuration. Solution: the triangle count is zero versus two. Providing it explicitly changes the input information, so it does not contradict the uniform-feature message-passing limitation.

49.10 Combinatorial optimization with learned heuristics

Optional extension; not required to complete the chapter foundation.

A learned heuristic can propose candidates, rank moves, choose branches, or estimate bounds. Each role has a different correctness obligation. Candidate proposals need feasibility verification. Branch ordering can preserve exactness if all necessary branches are eventually explored and pruning uses valid bounds. A predicted bound used for pruning needs a proof of admissibility; high empirical accuracy alone does not make it a certificate. A primary learning-guided branch-selection study is Gasse and collaborators.

Solved example. Use the three-item coverage instance from section 49.5 with budget two. Treat $(0.9,0.8,0.1)$ as illustrative model outputs, not as a claim that a model has been trained. Top-two selection returns $AB$ with value four. Enumerating all three pairs gives $f(AB)=4$, $f(AC)=5$, $f(BC)=6$. The learned candidate is feasible but suboptimal. If its score causes $C$ to be permanently discarded, the optimum is lost. If scores only order a complete enumeration, the final exact answer remains six.

A simple safeguard evaluates both the learned candidate and the true-marginal greedy candidate and returns the better feasible one. In the example it returns $AC$ with value five. In every normalized monotone submodular cardinality instance, it inherits greedy's $1-(1-1/k)^k$ guarantee regardless of the learned scores, because its verified objective cannot be smaller than greedy's. This is a complete worst-case argument, independent of prediction accuracy. It assumes the extra evaluation and greedy computation are actually performed.

To connect learning and optimization quantitatively, define a bounded loss for a fixed policy class, specify the instance distribution, and obtain a risk bound for that loss. A bound for binary item usefulness does not automatically bound optimization regret: overlapping resources, rare high-cost failures, and constraint violations alter the target quantity. Test/train separation and computational cost also remain part of a meaningful audit.

Exercise. If a learned feasible maximization candidate has value five and a valid relaxation upper bound is seven, what ratio is certified? Hint: the true optimum is at most seven. Solution: at least $5/7$. A predicted upper bound of four cannot be used: it already conflicts with the feasible value and is not an admissible certificate.

Derive a learning bound and audit a learned combinatorial heuristic

The investigation deliberately has two proof layers. The learning layer controls error for a fixed finite set system under iid realizable labels. The optimization layer verifies a candidate and an independent approximation safeguard. Connecting them means stating what each controls, rather than assuming a classification guarantee supplies an optimization ratio. A resource-selection application can use learned priorities while retaining combinatorial feasibility and fallback guarantees.