6.1 The Separation Lattice

Figure 6.1 displays all 13 edges as a single diagram. Dashed red arrows denote does_not_imply edges: the source does not entail the target, and the label names the witness. Solid blue arrows denote strictly_stronger edges: the source strictly contains the target as a special case, with the witness demonstrating the gap.

The first observation is structural: the lattice is sparse. Thirteen edges connect concepts drawn from six paradigms and a dozen complexity measures. Most paradigm pairs are simply incomparable, they neither imply nor contradict each other, because they operate on different mathematical objects. The sparsity is itself informative: learning theory is not a linear hierarchy from weak to strong, but a partially ordered collection of largely independent formalisms.

\begin{tikzpicture} [
node distance=1.8cm and 2.4cm,
concept/.style={
rectangle, rounded corners=3pt, draw, thick,
fill=layergray, font=\small\sffamily,
minimum width=2.2cm, minimum height=0.7cm,
align=center
},
dni/.style={-{Stealth[length=5pt]}, dashed, thmred, thick},
ss/.style={-{Stealth[length=5pt]}, defblue, thick},
witness/.style={font=\tiny\itshape, text=notegray, align=center}
]

%, Nodes,
\node[concept] (ul) {Universal\\Learning};
\node[concept, below left=2.0cm and 1.2cm of ul] (ol) {Online\\Learning};
\node[concept, below right=2.0cm and 1.2cm of ul] (pac) {PAC\\Learning};
\node[concept, right=2.8cm of pac] (exact) {Exact\\Learning};
\node[concept, below=1.8cm of ol] (mb) {Mistake\\Bounded};
\node[concept, below=1.8cm of pac] (ex) {Ex-\\Learning};
\node[concept, below=1.8cm of ex] (fin) {FIN-\\Learning};

\node[concept, left=2.5cm of ol] (vc) {VC\\Dimension};
\node[concept, below=1.8cm of vc] (sq) {SQ\\Dimension};
\node[concept, below left=1.8cm and 0.0cm of vc] (comp) {Comput.\\Hardness};

\node[concept, right=2.8cm of exact] (nd) {Natarajan\\Dimension};
\node[concept, above=1.8cm of nd] (ds) {DS\\Dimension};

\node[concept, below=1.8cm of mb] (ft) {Fundamental\\Theorem};
\node[concept, right=2.8cm of ft] (stab) {Algorithmic\\Stability};

\node[concept, below left=1.4cm and 0.5cm of pac] (pi) {Proper/Improper\\Separation};
\node[concept, below right=1.8cm and 0.0cm of exact] (uc) {Unlabeled\\Compression};
\node[concept, below=1.5cm of uc] (cs) {Compression\\Scheme};

%, does_not_imply edges (dashed red),
\draw[dni] (pac) -- node[witness, above, sloped] {thresholds} (mb);
\draw[dni] (nd) -- node[witness, above, sloped] {$d_N{=}1$, not learnable} (pac);
\draw[dni] (pac) -- node[witness, above, sloped] {approx.\ vs.\ exact} (exact);
\draw[dni] (vc) -- node[witness, left, pos=0.4] {crypto} (comp);
\draw[dni] (vc) -- node[witness, left] {parities} (sq);
\draw[dni] (ex) -- node[witness, above, sloped] {$\VC = \infty$} (pac);
\draw[dni] (pi) -- node[witness, below, sloped] {3-DNF} (pac);
\draw[dni] (uc) -- node[witness, right, pos=0.4] {P\'alv\"olgyi--Tardos} (cs);
\draw[dni] (ft) -- node[witness, above, sloped] {beyond binary} (stab);

%, strictly_stronger edges (solid blue),
\draw[ss] (ul) -- node[witness, above left, sloped] {removes uniformity} (pac);
\draw[ss] (ol) -- node[witness, above, sloped] {$\Ldim \Rightarrow \VC$} (pac);
\draw[ss] (ex) -- node[witness, right] {unbounded mind changes} (fin);
\draw[ss] (ds) -- node[witness, right] {pseudo-manifold} (nd);

\end{tikzpicture} — Figure 6.1 The separation lattice. Dashed red: does_not_imply (9 edges). Solid blue: strictly_stronger (4 edges). Each label names the witness.