Theoretical Computer Science for ML

Complexity, hardness, and approximation set what learning can guarantee, so theory draws the boundary efficient algorithms cannot cross.

Easy problems sit inside the efficient boundary while hard learning tasks lie outside, and approximation plus sketching recover useful ground near the edge

Why Does This Exist?

ML practice optimizes without asking what is optimizable: gradient methods attack objectives whose exact minimization is NP-hard, and nobody blinks. Theoretical computer science for ML draws the map so that confidence lands in the right place: which learning tasks admit efficient exact algorithms, which are hard even approximately, and which surrender to approximation, sketching, or cryptographic assumptions. The children each own one region: complexity classes for P and NP, hardness of learning for proper versus improper barriers, cryptographic assumptions for average-case hardness, approximation for guarantees on hard objectives, and sketching for sublinear data. Runtime counting for accelerators is complexity for ML.

The one idea you need first

A reduction converts problem A into problem B efficiently, so B is at least as hard as A: an efficient solver for B would solve A too. Hardness flows along reductions; algorithms must route around where reductions point.

Think of It Like This

A harbor chart with reefs and channels

Sailors chart reefs (provably hard zones), channels (efficient routes), and tidal shortcuts (approximations that work when exact passage is blocked). Nobody sails by staring at one reef; they read the whole chart, then pick a route whose guarantees match the cargo.

TCS is that chart for learning tasks. Complexity classes mark the reefs, reductions draw the currents connecting them, approximation marks the channels that admit heavy cargo with slight delay, and sketching marks the shallow passages for light boats. Practice sails daily; theory keeps the chart honest.

How It Actually Works

Complexity sorts decision problems: P (efficiently solvable), NP (efficiently checkable), NP-complete (hardest in NP, all equivalent via reductions). Learning hardness asks about concept classes: properly learning parities with noise is as hard as decoding random linear codes; improperly, richer hypotheses sometimes bypass the barrier. Cryptography bases average-case hardness on assumptions (factoring, LWE) that learning lower bounds inherit. Approximation guarantees near-optimal values on NP-hard objectives (a $1 - 1/e$ share for submodular maximization). Sketching compresses data to sublinear summaries with $(1 \pm \epsilon)$ geometry preserved.

Worked example

Imagine selecting $k = 10$ training points from $n = 10{,}000$ to maximize a submodular coverage score. Exact search over $\binom{10000}{10} \approx 2.7 \times 10^{33}$ subsets is hopeless (NP-hard). Greedy adding (best marginal gain each step) guarantees $1 - 1/e \approx 0.63$ of optimum: if the optimum covers $900$ concepts, greedy covers at least $567$ . A CountSketch of width $2{,}000$ estimates all point norms within $10\%$ to drive the greedy picks in one pass. Three regions of the map combine on one task: hardness says exact is out, approximation guarantees the greedy share, sketching fits the data in memory.

Code

1def greedy_cover(values: list[float], k: int) -> tuple[list[int], float]:2    picked, total = [], 0.03    remaining = set(range(len(values)))4    for _ in range(k):5        nxt = max(remaining, key=lambda i: values[i])  # best marginal gain6        picked.append(nxt)7        total += values[nxt]8        remaining.discard(nxt)9    return picked, round(total, 1)10
11
12vals = [90.0, 85.0, 80.0, 20.0, 15.0]13print(greedy_cover(vals, 2))  # -> ([0, 1], 175.0)

Top- $2$ picks total $175$ : the greedy share on a tiny instance where the $0.63$ guarantee is overkill but visible.

Watch Out For

Reading worst-case hardness as typical-case impossibility

NP-hardness constrains the worst input; real data (clustered, smooth, margin-separated) often admits fast exact or near-exact methods. Teams that abandon principled optimization on hardness slogans alone leave guaranteed performance unclaimed. Check average-case and structured-input results before switching to heuristics.

Assuming approximation ratios transfer across objectives

The $0.63$ submodular guarantee evaporates for non-submodular scores (diversity with repulsion, supermodular coverage): greedy can score arbitrarily badly there. Verify submodularity (diminishing returns) on your objective before quoting the ratio.

The Quick Version

TCS maps efficient, hard, approximable, and sketchable learning tasks on one chart.
Reductions transfer hardness; algorithms route around the reef lines.
Greedy submodular selection guarantees $0.63$ of optimum: $567$ of $900$ concepts in the example.
Sketching compresses the $10{,}000$ -point search to a $2{,}000$ -wide summary within $10\%$ .
Worst-case hardness rarely bars structured real data; check average-case results.
Approximation ratios need their structural premise (submodularity) verified per objective.