Task Complexity, Interactive

← text notes · Achille, Paolini, Mbeng & Soatto, The Information Complexity of Learning Tasks, their Structure and their Distance. Six widgets. Each one recomputes, in your browser, the same formulas as the scripts in code/.

1. The structure function of random labels

N labels drawn uniformly from |Y| classes. S(t) is the lowest loss reachable with a model of complexity at most t nats. No model can go below the line N ln|Y| − t, since L + K ≥ C(D) ≈ N ln|Y|. The paper's Example 3.5 reaches the line by memorising ⌊t / ln|Y|⌋ points. That works when an oracle numbers the inputs. Without one, the model must also be told which inputs it memorised: ln C(N, m) more nats. Searching over 2^t random labelings reaches the line in the large-deviation limit. The right panel adds βt, and its minimum is what the Lagrangian C_β selects.

Things to try. At β < 1 every scheme that tracks the line prefers to memorise everything; at β > 1 the constant model (t = 0) wins; at β = 1 it is a tie, decided by the O(1) terms. That tie is Proposition 3.6's β* = 1 for random labels. It is also why Theorem 4.4 needs β ≥ 1 on noisy labels: below 1, the optimal model memorises the noise. The oracle-free memoriser (orange) never gets close to the line in the middle. How close it gets at the end depends on |Y|: with more classes, the label bits dominate the cost of naming the points.

2. A double well: the β-minimiser jumps

One weight w with pre-distribution P = N(0, 3²) and post-distribution Q = N(µ, σ²); N = 50. The loss per sample has a wide shallow basin at w = 1 and a narrow deep one at w = 3.5. For each β the page minimises C_β = N·E_Q[loss] + β·KL(Q‖P) over a grid of (µ, σ). Right: the structure function S(t) = min {N·E_Q loss : KL ≤ t}, its convex hull, and the line of slope −β that touches it at the optimum. Anneal starts from the global optimum at β = 20 and lowers β to the slider's value, taking ε-local steps (the best grid point within distance ε in (µ, σ)) until they stop moving.

Things to try. Drag β slowly downwards from about 6. Near β ≈ 4.5 the optimum leaves the wide basin for the narrow one in one jump, and its information jumps from about 1.2 to 4.6 nats. The tangent line touches the hull at two points at that moment. Now set β = 0.5 and press anneal with ε = 1: the local steps stay in the wide basin. Raise ε until annealing finds the narrow well; it needs a step as large as the jump. Make the narrow well shallower or wider and the red band shrinks. Once it vanishes, S(t) is convex, and annealing works with any ε (Proposition 6.4).

3. Information per weight direction

With P = N(0, λ²I) and the optimal Gaussian Q, each eigen-direction of the Hessian H = N·F carries ½ g(s) nats, where s = λ²h/β and g(s) = log(1+s) − s/(1+s). A flat direction (h = 0) carries nothing. Theorem 5.4 keeps only the large-s form ½(log s − 1). Summed, that is ½ log|F| + ½ k log λ² plus a "O(1)" of ½ k log(N/β) − k/2. The spectrum here has k = 40 directions, with per-sample Fisher eigenvalues j^−α, and the last few set to exactly zero.

Things to try. With any flat direction, the theorem's ½ log|F| is −∞, while the exact information is finite. Set flat directions to 0 and raise λ: the exact total and the theorem's formula plus the hidden term converge. The hidden term alone is then often larger than ½ log|F|. Move β by a decade: the hidden term changes by ½ k ln 10 ≈ 46 nats here, with the Hessian untouched. Figure 2 sweeps β over three decades.

4. Figure 1, taken apart

The paper's estimated distance matrix, transcribed: entry (row j, column i) is d(task i → task j). If the optimal solutions are unique, Definition 6.1 gives d(i→j) − d(j→i) = I_j − I_i: the antisymmetric part must be a difference of one number per task. The page fits that number, c_i = mean over j of [d(j→i) − d(i→j)], and shows what is left.

Things to try. Switch to residual: every cell is below 0.01, the size of the rounding. The asymmetry of the whole matrix is fixed by eight numbers. Symmetric part is where similarity would live, d(i→j) + d(j→i) = 2I_ij − I_i − I_j. It is negative for (natural, artificial): by these estimates, the union of the two halves of CIFAR-100 needs less information than either half. Hover a cell for its triangle-inequality slack.

5. The task distance, solved exactly

Linear-Gaussian regression with k inputs and three weight blocks: shared w_s, and one block per task. Task i predicts x·(w_s + w_i), and the index in D₁ ⊔ D₂ picks the block. P = N(0, λ²I), noise variance 1, and population design X^⊤X = N·I. The optimal Q is the posterior, so the information is exact: I = ‖µ‖²/(2λ²) + ½ Σ g(λ²h/β). The first term depends on the labels. The second, the log-det term, depends only on which directions the data curve and how many samples do it. Task 1's true weights are u₁ = e₁, and task 2's are u₂ = r(cos θ e₁ + sin θ e₂).

Things to try. Press copy: a task is tens of nats from itself, not O(1) as Lemma 4.2 has it for the Kolmogorov version. The union turns on a new block of k curved directions, and each costs about ½ log N. Raise N₂ with the copy still in place: the "same" task moves further away. Sweep θ from 0 to 180°: the distance moves by a fraction of a nat, all of it in the blue part. Set r ≠ 1: d(1→2) − d(2→1) equals I₂ − I₁ exactly.

6. The PAC-Bayes bound against β and λ

Theorem 5.5 (McAllester): for β > ½ and a loss in [0, 1], L_test(Q) ≤ [L̂(Q) + β(KL(Q‖P) + ln 1/δ)/N] / (1 − 1/(2β)). For a loss bounded by L_max, the condition becomes β > L_max/2. Left: the multiplier 1/(1 − L_max/(2β)), with the band where Figure 2's transitions happen. Right: the bound against the prior width λ. The KL at the optimal Gaussian Q uses the spectrum of widget 3 (k = 40 directions, α = 2, no flat ones), with ‖w*‖² = k and a fixed training Gibbs error of 0.15.

Things to try. With cross-entropy clipped at ln 10, the bound needs β > 1.15, far to the right of every transition in Figure 2. On the right, the bound has a best λ. As λ → ∞, the limit Theorem 5.4 is stated in, the KL grows like ½ log λ² per curved direction, so the bound grows without limit. At N = 500 it is vacuous by λ = 10⁸. Raise N and it takes longer, but it always gets there.