learning-theory.
157 of 1538 NOTE documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| NOTE-198 v2 | Minimum Description Length Revisited | MDL, reformulated around universal distributions and luckiness functions and presentable without coding theory, extends both penalized likelihood and Bayes, and unifies methods usually seen as rival — AIC vs BIC, cross-validation vs Bayes — within one worst-case framework. | Superseded — by NOTE-760 |
| NOTE-200 v2 | Rate-distortion generalization bounds | Defining an algorithm’s compressibility in source-coding terms shows that the Xu–Raginsky mutual-information bound is really a lossless compression rate, and allowing lossy compression yields bounds via the rate-distortion dimension that stay meaningful where I(S;W) is huge. | Superseded — by NOTE-780 |
| NOTE-202 v2 | Kolmogorov’s structure functions and model selection | The structure function of a single data string determines all of its stochastic properties: within any complexity-constrained model class it picks out the best-fitting model with certainty. Every admissible shape of that function occurs for some data, and neither it nor the minimal sufficient statistic is computable. | Superseded — by NOTE-787 |
| NOTE-203 v2 | MDL induction, Bayesianism, and Kolmogorov complexity | Ideal MDL, derived from Bayes’s rule with the universal prior, coincides with Bayesian MAP selection exactly when the data are random with respect to the hypothesis and the hypothesis is random with respect to the prior (the “Fundamental Inequality”). For finite-set models it reduces to Kolmogorov’s minimal sufficient statistic, so compression is almost always the best strategy for both identifying hypotheses and predicting. | Superseded — by NOTE-801 |
| NOTE-205 v2 | Balestriero, Bottou & LeCun 2022 — regularization is class-dependent | Regularizers tuned by cross-validation for average accuracy — random-crop augmentation and even uninformed weight decay — raise mean test accuracy while sharply lowering it on particular classes (e.g. ImageNet “barn spider” 68%→46% with random crop), and this class-dependent bias carries over to transfer tasks. | Superseded — by NOTE-845 |
| NOTE-207 v2 | MDL generalization guarantees for representation learning | Generalization of representation learning is bounded not by I(X;U) but by the minimum description length of the latent variables (or predicted labels) under a symmetric prior — a multi-letter relative entropy that reflects the encoder’s structure and is non-vacuous for deterministic encoders. | Superseded — by NOTE-742 |
| NOTE-208 v2 | Sun et al. 2023 — spectral theory of novel class discovery | For novel class discovery, a spectral contrastive loss over a graph of labeled and unlabeled data (NSCL) is equivalent to factorizing its adjacency matrix, and the resulting linear-probe error on novel classes is bounded — down to zero — by how far the known classes’ feature span covers the unlabeled data’s “ignorance space”. | Superseded — by NOTE-833 |
| NOTE-210 v2 | The Conditional Entropy Bottleneck | Training a representation to minimize I(X;Z|Y) while maximizing I(Y;Z) — the Conditional Entropy Bottleneck, targeting the “Minimum Necessary Information” point I(X;Y)=I(X;Z)=I(Y;Z) — empirically improves accuracy, adversarial robustness, OoD detection and calibration and refuses to memorize random labels. | Superseded — by NOTE-754 |
| NOTE-212 v2 | Meaningful information (sophistication) | With total recursive functions as the model class, the algorithmic minimal sufficient statistic (“sophistication”) is a non-trivial measure of meaningful information. It matches the finite-set and probability-model versions up to additive terms, some objects are entirely meaningful with no residual randomness, and it is not computable. | Superseded — by NOTE-790 |
| NOTE-213 v2 | Shannon information vs Kolmogorov complexity (survey) | Shannon’s and Kolmogorov’s theories line up concept by concept (entropy vs complexity, probabilistic vs algorithmic mutual information and sufficient statistics, rate-distortion vs structure function), and in each pair the Shannon notion is, up to additive terms, the expectation of the Kolmogorov one. | Superseded — by NOTE-776 |
| NOTE-216 v2 | Variable-size compressibility generalization bounds | Letting the compression rate of an algorithm’s input data vary with the observed sample yields generalization bounds that depend on the empirical measure rather than the unknown distribution, and this single framework recovers PAC-Bayes and data-dependent intrinsic-dimension bounds as special cases. | Superseded — by NOTE-806 |
| NOTE-218 v2 | Simon et al. 2023 — stepwise nature of SSL | Joint-embedding SSL learns its embedding one dimension at a time in discrete, well-separated steps — in a linearized Barlow Twins model it provably learns the top eigenmodes of a contrastive kernel in order, so SSL is to kernel PCA what supervised learning is to kernel regression — and the same stepwise rank growth appears in ResNets trained with Barlow Twins, SimCLR and VICReg. | Superseded — by NOTE-741 |
| NOTE-221 v2 | Closeness in Distribution vs Representational Similarity | For softmax models p(y|x) ∝ exp(f(x)ᵀg(y)) under a diversity condition, the model distribution determines the embeddings and unembeddings up to an invertible linear map (f = Af′, g₀ = A⁻ᵀg′₀). The determination is not stable under KL divergence, though: two models can be ε-close in KL, even both near maximum likelihood, while their embeddings are far from linearly equivalent. | Superseded — by NOTE-738 |
| NOTE-222 v2 | Tosh et al., contrastive learning and multi-view redundancy | The logistic contrastive problem of telling a same-datum pair of views from an independent pair is solved over all functions by the pointwise mutual information f*(x,z) = log p(x,z)/(p(x)p(z)), whose exponential g* is the change of measure from p(z) to p(z|x), and linear functions of the landmark embedding (g*(x,Z_1),…,g*(x,Z_m)) are near-optimal predictors whenever the two views are redundant for the label. | Superseded — by NOTE-841 |
| NOTE-226 v2 | Kernel mean embedding of distributions (review) | Point evaluation is bounded on an RKHS, so the Riesz theorem gives the reproducing kernel k_x. Likewise, when E√k(X,X) < ∞ the expectation functional f ↦ E_P f is bounded, so Riesz gives a unique mean embedding μ_P with E_P f = ⟨f, μ_P⟩. MMD is then the RKHS distance ‖μ_P − μ_Q‖, and it separates distributions exactly when the kernel is characteristic. | Superseded — by NOTE-838 |
| NOTE-227 v2 | Spectral contrastive loss (HaoChen et al.) | Minimizing the population spectral contrastive loss L(f) = −2E[f(x)ᵀf(x⁺)] + E[(f(x)ᵀf(x⁻))²] is, up to a constant, a rank-k factorization of the normalized adjacency matrix of the augmentation graph, so its minimizers are the top-k eigenvectors (eigenfunctions, in the infinite case) of that graph up to a row scaling and an invertible linear map — neither of which changes linear-probe accuracy. | Superseded — by NOTE-740 |
| NOTE-228 v2 | Contrastive learning finds an optimal eigenbasis | The InfoNCE, NT-Logistic and spectral contrastive losses all have the same population minimizer, the positive-pair kernel K⁺(a₁,a₂) = p⁺(a₁,a₂)/(p(a₁)p(a₂)). Kernel PCA under K⁺ returns exactly the eigenfunctions of the positive-pair Markov chain, and the top-d of those span the linear-predictor subspace that minimizes worst-case approximation error over approximately view-invariant targets. | Superseded — by NOTE-751 |
| NOTE-230 v2 | A Generalized Representer Theorem | For any strictly increasing regularizer g(‖f‖) and any (even non-convex, coupled) cost on the training outputs, every RKHS minimizer of c((x_i,y_i,f(x_i))_i) + g(‖f‖) is a finite kernel expansion f = Σ α_i k(·,x_i). The proof needs only the reproducing property and orthogonal decomposition onto span{k(·,x_i)}, not the Riesz theorem. | Superseded — by NOTE-836 |
| NOTE-244 | Neural Tangent Kernel of Matrix Product States: Convergence and Applications | In the sequential infinite-bond-dimension limit, with tensor variances σ_i²/√(|α_i||α_{i+1}|) and per-tensor learning rates (|α_i||α_{i+1}|)^{-1/2}, the NTK of a periodic MPS tends to K(x,x′)=Σ_k φ(x_k)·φ(x′k) Π{l≠k} σ_l² φ(x_l)·φ(x′_l). By my reduction this is (Σ_k σ_k⁻²) times the MPS’s own GP covariance, so gradient flow is kernel regression with a fixed product kernel. The Born-machine solution P_x(t)=1/m−(1/m−P_x(0))e^{−4mKt/Z} is correct (I checked it; Z is in fact conserved). The lazy-training lemma is heuristic, the positive-definiteness “proof” shows at most semi-definiteness, several constants are off by factors of n or 2^{−n}, and there are no experiments. | Read |
| NOTE-283 | Progress measures for grokking via mechanistic interpretability | A one-layer ReLU transformer (P = 113, 30% of pairs, full-batch AdamW with λ = 1, 40k epochs) that groks modular addition implements a “Fourier multiplication” algorithm. The embedding maps a and b to cos/sin(w_k·a), cos/sin(w_k·b) at five key frequencies k ∈ {14, 35, 41, 42, 52}, with w_k = 2πk/113. Attention and MLP form cos/sin(w_k(a+b)), and the neuron-logit map W_L (≈ rank 10) reads out Σ_k α_k·cos(w_k(a+b−c)). Progress measures built from this (restricted and excluded loss) show training splits into memorisation (0–1.4k epochs), circuit formation (1.4k–9.4k) and cleanup (9.4k–14k), with the test-accuracy jump inside cleanup. | Read |
| NOTE-287 | Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets | Small decoder-only transformers (2 layers, width 128, 4 heads, ~4·10⁵ non-embedding parameters) trained on binary-operation tables over abstract symbols can reach 100% validation accuracy long after fitting the training set. In the headline run (division mod 97, 50% data, Adam with no weight decay, a budget of 10⁶ steps), training accuracy is near-perfect before 10³ steps, validation accuracy only near 10⁶, with little progress before 10⁵. The optimisation time to generalise rises steeply as the training fraction falls (on S₅ near 25–30% data, −1% data costs +40–50% median steps), and weight decay is the most data-efficient intervention tried. | Read |
| NOTE-291 | Analysis of Boolean Functions | Every f: {−1,1}ⁿ → ℝ has a unique multilinear (Fourier–Walsh) expansion f = Σ_S f̂(S)χ_S over the parities χ_S(x) = ∏{i∈S} x_i, which are an orthonormal basis (Thm 1.1, Thm 1.5) and are the characters of the group F₂ⁿ, χ_S(x+y) = χ_S(x)χ_S(y) (eq. 1.5; §3.2; §8.5). The central operators are all diagonal in this basis with eigenvalues depending only on |S|: the noise operator T_ρχ_S = ρ^{|S|}χ_S (Prop. 2.47) and the Laplacian Lχ_S = |S|χ_S (Prop. 2.37). Influence, noise stability and Arrow’s Theorem (via Stab{−1/3}) become statements about the Fourier weight at each level (Thms 2.20, 2.38, 2.49, 2.56). | Skimmed |
| NOTE-293 | An Empirical Model of Large-Batch Training | The paper derives a local model in which the loss progress one step can make at batch size B is ΔL_max/(1 + B_noise/B), with B_noise = tr(HΣ)/GᵀHG (eqs. 2.7–2.8). Averaged over a run at fixed B, the model gives the steps/examples hyperbola (S/S_min − 1)(E/E_min − 1) = 1, which defines the critical batch B_crit = E_min/S_min (eqs. 2.11–2.12). Across eight tasks, B_crit spans about six orders of magnitude (from 20 to over 10 million, §3), and the Hessian-free B_simple = tr(Σ)/|G|² tracks it to about an order of magnitude (Table 1: run-averaged B_simple/B_crit runs from 0.05 for the SVHN VAE and autoencoder to 8 for SVHN). | Read |
| NOTE-295 | Thermodynamics of Prediction | For a system driven by a stochastic signal through a fixed Markov kernel, the average work dissipated as the signal steps x_t → x_{t+1} equals, in units of k_BT, the system’s instantaneous nonpredictive information, I[s_t;x_t] − I[s_t;x_{t+1}] (Eq. 14). Summed over a protocol, this total “nostalgia” lower-bounds dissipation and excess work (Eq. 18), and it adds to Landauer’s bound: −β⟨Q⟩ ≥ I_e + I_mem − I_pred (Eq. 21). All three are averages over paths and protocols. None of them is a per-operation or per-bit floor on the cost of storing or using predictive information. | Read |
| NOTE-296 | Stochastic Thermodynamics of Learning | For a perceptron whose weights follow overdamped Langevin dynamics and whose predicted labels are fast two-state processes, the information learnt about fixed random labels is bounded by the weights’ total entropy production: Σ_μ I(σ_T^μ:σ^μ) ≤ Σ_n [ΔS(ω_n) + ΔQ_n] (Eq. 16, k_B = T = 1). This defines a learning efficiency η ≤ 1. The cost side includes the change in the weights’ own Shannon entropy, and in the paper’s toy model η → 0.99 as the heat ΔQ → 0 (slow driving). So the bound is not a heat floor of k_BT ln 2 per bit learnt. | Read |
| NOTE-298 | Opening the Black Box of Deep Neural Networks via Information | The paper studies small tanh networks (layer widths down from 12 to 2) trained by SGD on a 12-bit, O(3)-symmetric synthetic rule, with mutual information estimated by binning each neuron into 30 bins over all 4,096 inputs. It reports two phases: a short “ERM” phase of a few hundred epochs in which I(T;Y) rises, and a long “compression” phase in which I(X;T) falls. The phases coincide with a drop in per-layer gradient SNR (from high-SNR drift to low-SNR diffusion, at about 350 epochs), and the converged layers sit on the IB curve at fitted β. Everything is shown on small synthetic tasks, with the explanations argued informally. | Read |
| NOTE-300 | The information bottleneck method | The paper defines relevant information as what X tells about a second variable Y and poses the information-bottleneck problem, min over p(x̃|x) of L = I(X̃;X) − β·I(X̃;Y), under the Markov chain X̃ ← X ← Y (eq. 15). Theorem 4 gives the exact formal solution p(x̃|x) = p(x̃)/Z(x,β)·exp(−β·D_KL[p(y|x)‖p(y|x̃)]), so the KL divergence emerges as the effective distortion. Theorem 5 gives a Blahut–Arimoto-style alternating iteration that converges but, being non-convex jointly, not necessarily to a unique solution. | Read |
| NOTE-306 v3 | Information-theoretic analysis of generalization capability of learning algorithms | If the loss ℓ(w,Z) is σ-subgaussian for every w, then the expected generalisation error of any learning algorithm P_{W|S} obeys |E[L_μ(W) − L_S(W)]| ≤ √(2σ²·I(S;W)/n) (Theorem 1). This extends Russo–Zou to uncountable hypothesis spaces, and the paper adds a high-probability version, n = (8σ²/α²)(ε/β + log(2/β)) (Theorem 3). Minimising empirical risk plus I(S;W), relaxed to a KL term against a prior Q, yields exactly the Gibbs algorithm (Theorem 5). Noisy ERM and adaptive composition are analysed through the same mutual-information quantity. | Read |
| NOTE-308 | How much does your data exploration overfit? Controlling bias via information usage | Suppose an analyst reports statistic φ_T, chosen by any data-dependent rule T from m candidates each σ-sub-Gaussian. Then the selection bias obeys |E[φ_T − µ_T]| ≤ σ√(2·I(T;φ)) (Prop. 1), where “information usage” I(T;φ) ≤ H(T) ≤ log m. For argmax selection over φ ~ N(µ,I) the squared error is Θ(1 + H(T)) (Prop. 3). Adaptive analyses compose additively, with I(T_{k+1};φ) ≤ Σ_i I(Y_{T_i};φ_{T_i} | H_{i−1},T_i) (Lemma 1). Answering each query with Gaussian noise of variance σ²√j/n therefore keeps the k-th answer’s error at O(σk^{1/4}/√n) (Prop. 7). | Read |
| NOTE-317 | Grokking and Generalization Collapse: Insights from HTSR theory | A depth-3, width-200 ReLU MLP trained on 1,000 MNIST images (the Omnigrok recipe, with weights and biases scaled ×8, MSE loss, AdamW, WD = 0) for 10⁷ steps goes through three phases read off the accuracy curves. In pre-grokking (to ~10⁵ steps) training accuracy saturates while test accuracy stays low. In grokking (~10⁵–10⁶) test accuracy rises to ~0.85. In “anti-grokking” (~10⁶–10⁷) it falls to ~0.45–0.5 while training accuracy stays near 1. The average HTSR power-law exponent α of the two hidden weight matrices goes 4.0 → 2.9 → 1.1 at the phase ends (Table 1). In the collapse phase, correlation traps (outlier eigenvalues of the elementwise-shuffled weight matrix) appear. The paper’s own weight-decay control shows FC2’s α below 2, and traps in both layers, without a collapse (Fig. 6, Table 2). That undercuts its headline claim that α < 2 “invariably” heralds collapse. | Read |
| NOTE-318 | New Evidence of the Two-Phase Learning Dynamics of Neural Networks | VGG-16 and ResNet-20 on CIFAR-10 (SGD with momentum, lr 0.1, 160 epochs) are compared across pairs of training times. Before an early “inflection point” (~2,500 iterations for VGG-16, ~100–500 for ResNet-20), a tiny parameter perturbation under identical SGD noise sends the run to a different basin by the end: loss barrier up to ~2, test disagreement ~0.15–0.5. After it, the same perturbation leaves the runs linearly connected. Also after it, the empirical NTK keeps changing step to step but stays within a bounded cosine distance of any later reference kernel (the “cone effect”, e.g. S ≈ 0.05–0.1 for VGG-16 vs ≈ 0.15–0.2 from initialisation). Switching to linearised training later gives better test accuracy (VGG-16 0.13 → 0.82 as the switch moves from ≤200 to 5,000 iterations). | Read |
| NOTE-319 | How do language models learn facts? Dynamics, curricula and hallucinations | ’An 8-layer, 44M-parameter decoder-only transformer trained with AdamW on synthetic biographies (64k individuals by default) learns factual recall in three phases. It first fits the marginal attribute-value distribution, then sits on a plateau exactly at the no-knowledge baseline, then acquires individual-specific associations. Plateau end grows with population as 0.43·N^0.81 (R² = 0.998, N = 4k–256k, 5 seeds). Attention patching from post-plateau checkpoints removes the plateau, and attention from the recall position to name tokens rises through it, so the plateau is when the attention extraction circuit forms. Nothing in the three phases is a compression of input information: the last phase adds individual-specific information.‘ | Read |
| NOTE-320 v2 | On the Information Bottleneck Theory of Deep Learning | Replicating Shwartz-Ziv & Tishby with their own code, the paper shows the information-plane “compression phase” appears only for double-saturating nonlinearities measured through an imposed binning/noise model: tanh compresses, ReLU/softplus/linear do not (binning, KDE, Kraskov; SZT task and MNIST), and re-binning the same tanh run evenly in net input removes it. Compression and generalisation dissociate in all four combinations, full-batch GD compresses as much as SGD, and the drift→diffusion gradient-SNR transition occurs in networks that cannot compress (ReLU, MNIST, a 1-1-1 linear net), so it is real but unrelated to compression. | Read |
| NOTE-321 v3 | The two dragons of cognition: recursive condensation for predictive processing | A Hypothesis-and-Theory essay, the cognitive statement of Li’s structural-learning programme. Intelligence pays once for exploratory search, condenses the result into stable discrete tokens, and then navigates cheaply. The cortex and the sleep rhythms are proposed as this cycle’s implementation (gamma as the expand/contract clock, the laminar circuit, STDP, SWRs nested in Slow-4). Charitably read, Savitch stands for memoisation and Urysohn for “collapsed, separated classes admit a simple readout”. On that reading the core is a coherent restatement of amortised inference and complementary learning systems, with untested and largely non-discriminating predictions. The headline scaling law, linear cortex giving exponential reach (Theorem 2), is stated without argument, and the claim that collapse defeats the curse of dimensionality leaves the cost of learning the collapse unaddressed. | Read |
| NOTE-322 v2 | Structural Decoupling: A Scaffold-Flow Theory of Generalization and Alignment | Li’s structural learning theory (StrLT, developed in the companion arXiv 2602.07974) splits multi-regime learning into discovering contexts (the “trap”, or scaffold) and predicting within one (the “funnel”, or flow). Width is the least number of cells on which a γ-contractive, low-risk predictor suffices. It is incomparable with the per-cell VC dimension, forces an error floor when fewer than w cells are allocated, and costs Ω(w log w) samples to discover. These results hold in repaired form, and are close to definitional. The CS estimator reweights a spatial graph by prediction agreement. It is shown to count components for a given predictor, not width itself. The decoupling prescription says to train routing on structural signals, not task loss, and to freeze consolidated contexts. It is a plausible, testable design hypothesis with continual-learning precedent, but the additive Rademacher bound it is said to follow from holds for joint training too. The safety section recasts alignment as scaffold alignment by analogy, and is asserted. | Read |
| NOTE-323 | Local Urysohn Width: A Topological Complexity Measure for Classification | >- It defines local Urysohn width uw_{D₀}(P, γ): the least number of connected sets of diameter ≤ D₀, each carrying a continuous classifier correct on the margin-γ safe region it meets, needed to cover that safe region. It proves: - uw = w on a bouquet of w circles with safe balls at the antipodes, when 3γ/2 ≤ D₀ < L/2 − 3γ/4 (Thm 4.1); - uw ≥ w·m, with m = Θ(L/D₀) safe balls per loop, so uw = Ω(w·L/D₀) (Cor 5.1); - two-way non-determination with VC dimension (Thm 6.1); - an Ω(w log w) sample lower bound via label-permuted coupon collection (Thm 7.1); - uw ≥ 2β₁/Δ₀ for good, convex, bounded-adjacency covers (Thm 8.5). The proofs are correct. The obstruction is metric, as the paper concedes in Remark 8.11: patches cannot reach across the wedge point. Because Urysohn’s lemma makes local correctness automatic on any patch, the measure is a connected covering number of the safe region that does not depend on the labels. | Read |
| NOTE-324 | Structural Learning Theory: A Metric-Topology Factorization Approach | >- The formal core of Xin Li’s structural-learning programme. Width w(P; γ, δ) is the least number of open cells on each of which some predictor is γ-contractive with conditional risk ≤ δ. The paper proves that width is incomparable with the per-cell VC dimension (Thm 2.2). It shows that with K < w cells there is an n-independent error floor η(w, K), under a non-degeneracy assumption stated in the body (Thm 2.4, Assumption 2.3). Width is at least c·β₁·L/D₀ under a bounded-overlap assumption (Thm 2.5), and discovering all basins costs Ω(w log w) samples (Thm 2.6). The CS-Laplacian eigenvalue count converges uniformly to the predictor-relative count w_G(P) when n ≳ (H_G + d_X log(1/r_x) + log(1/δ′))/(r_x^{d_X} g_eff²) (Thm 3.5); no result shows that w_G equals width. There are no experiments. | Read |
| NOTE-471 | Bayesian Interpolation | Evidence ≈ best-fit likelihood × Occam factor, the ratio of posterior to prior accessible parameter volume. At the evidence maximum the regulariser’s χ² equals γ = Σ λ_a/(λ_a + α), the number of well-determined parameters, and the data χ² equals N − γ. Polynomials show an “Occam hill” in k, and the true Hermite model wins on data drawn from it. | Read |
| NOTE-472 | Natural Gradient Works Efficiently in Learning | Natural gradient ∇̃L = G⁻¹∇L is steepest descent under metric G (Theorem 1); for a statistical model G is the Fisher information. Online learning w_{t+1} = w_t − (1/t)∇̃l is Fisher efficient, Ṽ_t = G⁻¹/t + O(1/t²) (Theorem 2). Explicit G and G⁻¹ for a perceptron (Theorems 3–4) and the natural gradient ∇L·WᵀW on the matrix group (Theorem 6). The plateau claim for multilayer perceptrons is a conjecture resting on Yang & Amari (1997). | Read |
| NOTE-473 | A Widely Applicable Bayesian Information Criterion | The Bayes free energy of a singular model is nL_n(w0) + λ log n − (m − 1) log log n + O_p(1), with λ the RLCT. The posterior mean of nL_n(w) at inverse temperature 1/log n (WBIC) reproduces the first two terms without knowing λ, equals BIC for regular models, and two temperatures estimate λ. In reduced-rank regression WBIC chose the true rank 100/100 times, and estimated RLCTs within about 0.5 of theory. | Read |
| NOTE-474 | Traces of Class/Cross-Class Structure Pervade Deep Learning Spectra | G = Gclass + Gcross + Gwithin + Gc=c′ (Eq. 6.4); knockouts give C outliers to Gclass, a C² mini-bulk to Gcross, the bulk to Gwithin, in log-spectra. Gˡ = Σ w (hhᵀ) ⊗ (δδᵀ) (Eq. 7.8), so gc ≈ hc ⊗ δc. K-FAC Hˡ ⊗ Δˡ misaligns G’s outliers; CFAC Ave_c Hˡc ⊗ Δˡc aligns them at deep layers. For multinomial logistic regression on a Gaussian model the expected Fisher has C outliers, C(C−2) mini-bulk and a bulk (Theorem 8.1). | Read |
| NOTE-475 | Deep Equals Shallow for ReLU Networks in Kernel Regimes | For κ(xᵀx′) on S^(d−1), µ_k = (ω_(d−2)/ω_(d−1)) ∫ κ(t)P_k(t)(1 − t²)^((d−3)/2) dt (Eq. 8), shared by N(d, k) ~ k^(d−2) harmonics. Theorem 1: an endpoint expansion κ(1 − t) = p(t) + c t^ν + o(t^ν) with ν non-integer gives µ_k ~ C k^(−d−2ν+1), parity-dependent. ReLU kernels have ν = 1/2 (NTK) and 3/2 (random features) at any depth, so the deep NTK decays as k^(−d) and the deep RF kernel as k^(−d−2) (Corollaries 2–3). MNIST and Fashion-MNIST accuracy is flat in depth from L = 2 to 5 (Table 1). | Read |
| NOTE-476 v2 | Prevalence of Neural Collapse during the terminal phase of deep learning training | NC1 Σ_W → 0 (Tr(Σ_WΣ_B†)/C falls), NC2 centred means → simplex ETF (cosines → −1/(C−1)), NC3 W ∝ Ṁᵀ, NC4 nearest class mean; 7 datasets × 3 nets, 480 models. Median TPT gains: +0.35 points test accuracy, +0.0252 DeepFool robustness. NC1–2 ⇒ NC3–4 for Webb–Lowe and max-margin (Theorems 2, 4). Optimal small-noise error exponent C/(C−1)·1/4, only at simplex ETFs (Theorem 5). | Read |
| NOTE-478 | The Full Spectrum of Deepnet Hessians at Scale | Hess = H + G (Gauss–Newton). At 28M parameters the Hessian has a bulk and about C outliers; outliers are in G, the bulk mostly in H; H is symmetric and power-law, φ ∝ |λ|⁻²·⁷ (R² 0.99), not Marchenko–Pastur or semicircle. G = A₁ + A₂ + B₁ + B₂ (Eq. 5): C class means give the outliers, cross-class spread and within-pair spread give two bulks. FastLanczos costs O(Mnp) time and O(p) memory. | Read |
| NOTE-479 | Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians | G = (1/n)ΔΔᵀ with δᵢ,c,c′ = column c′ of diag(√p)(I − 1pᵀ)∂f/∂θ. C² group means δc,c′, C cluster centres δc; G = G₀ + G₁ + G₂ + G₃ (Eq. 28). Top-C eigenvalues of G ≈ those of G₁ = (C−1)Ave_c δcδcᵀ, from a C×C Gram matrix, with λc(G) ≥ λc(G₁₊₂) ≥ λc(G₁). 18,000 CIFAR/MNIST models plus ImageNet VGG16/ResNet50. Group means switch from clustering by logit c′ to by class c during training. | Read |
| NOTE-481 | The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies | For uniform data the wide two-layer ReLU Gram matrix H∞ is a convolution on the sphere, so its eigenvectors are Fourier modes or spherical harmonics. On S¹, bias-free: λ_k = 1/π², 1/4, 2(k²+1)/(π²(k²−1)²) and 0 for k = 0, 1, even k ≥ 2 and odd k ≥ 3 (Eq. 12). With zero-initialised bias, odd k ≥ 3 get 1/(π²k²) (Eq. 13). Learning time grows as k² on S¹ and about k³ on S², as measured for shallow, deep and residual networks (Figs. 6–7). | Read |
| NOTE-483 | Towards Understanding the Spectral Bias of Deep Learning | Theorem 4.2: n^(−1/2)‖V_(r_k)ᵀ(y − ŷ(T))‖ ≤ 2(1 − λ_(r_k))^T n^(−1/2)‖V_(r_k)ᵀy‖ + ε for any labels, given n ≥ Ω̃(ε^(−2) max{(λ_(r_k) − λ_(r_k+1))^(−2), M⁴r_k²}) and m ≥ Ω̃(poly(T, λ_(r_k)^(−1), ε^(−1))). Theorem 4.3: on uniform S^d the NTK’s eigenfunctions are spherical harmonics, µ_k = 0 for odd k ≥ 3, and µ_k = Ω(max(k^(−d−1), d^(−k+1))) for even k. Experiments in R¹⁰ learn degrees 1, 2, 4 in that order, also on three non-uniform densities. | Read |
| NOTE-516 | Taxonomizing local versus global structure in neural network loss landscapes | mc(θ, θ′) = ½(L(θ) + L(θ′)) − L(γ(t*)) on a trained Bezier curve, in 0-1 training error (Eq. 4); mc < 0 is a barrier, mc ≈ 0 well connected, mc > 0 unconverged ends. With Hessian top eigenvalue and trace and output CKA on mixup points, a load by temperature grid splits into phases I–IV, with IV-B (flat, connected, similar) the most accurate. Sharpness alone mispredicts across phases; with 10% label noise, the sharp phases beat flat but poorly connected phase III, and double descent appears along the Hessian transition. | Read |
| NOTE-518 | Exact expressions for double descent and implicit regularization via surrogate random design | Surrogate design S^n_μ = Det(μ, K), density ∝ pdet(XXᵀ), K Poisson(γn) truncated at d. E[#rows] = n (Lemma 1); E[I − X̄⁺X̄] = (γnΣ + I)⁻¹ (Lemma 2); E[tr((X̄ᵀX̄)⁺)] = γn(1 − det((I/γn + Σ)⁻¹Σ)) (Lemma 3); λn = 1/γn. These give exact MSE in all regimes (Theorem 1) and E[X̄⁺ȳ] = (Σ + λnI)⁻¹v for n < d, with n = tr(Σ(Σ + λnI)⁻¹) (Theorem 2). For sub-Gaussian rows the i.i.d.-design MSE converges to the surrogate formula (Theorem 3), at an observed O(1/d) rate. | Read |
| NOTE-519 | A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent | Q̄ = ((N/n)(Kcos/(1+δcos) + Ksin/(1+δsin)) + λI)⁻¹ with δσ = (1/n) tr KσQ̄ is a deterministic equivalent for E_W[(ΣXᵀΣX/n + λI)⁻¹] (Theorem 1); Ē_train and Ē_test follow (Theorems 2–3). As λ → 0, δ ~ 1/λ for 2N < n and O(1) for 2N > n; det(Ω⁻¹) ~ λ, so Ē_test → ∞ at 2N = n unless the test set is within σ² ≲ λ of the training set. N/n → ∞ recovers Gaussian kernel regression. Theory matches MNIST, Fashion- and Kannada-MNIST. | Read |
| NOTE-525 | Does Data Scaling Lead to Visual Compositional Generalization? | (n, k) framework: two concepts with n values, k seen combinations per value. From-scratch ResNet-50s: near-100% ID, large OOD drops; 4× ID data leaves 60–80% drops; more values or combinations help. Features go from spurious, to decodable but entangled, to linearly factored (R² > 0.8, cosine < 0.1–0.2). Proposition 4.1: with linearly factored embeddings spanning 2n − 1 dimensions, k = 2 suffices for a linear classifier to be correct on all (n − k)·n unseen pairs. DINO, DINOv2, CLIP: partly factored, above chance, not perfect. | Read |
| NOTE-529 | Unveiling Mode Connectivity in Graph Neural Networks | GCN node-classification solutions from different seeds show linear loss barriers that vary by graph (small on Cora, Citeseer; large on Coauthor-CS, Squirrel) and vanish along fitted quadratic Bezier curves. GCN, GraphSAGE and GAT give similar barriers, MLPs different ones. On CSBM graphs barriers fall with density and feature separability and peak at middling homophily. Stated without proof: a barrier bound through the spectral gap, a generalisation bound proportional to the barrier, and a Wasserstein distance between graphs’ interpolation-loss curves that bounds the domain-adaptation gap. | Read |
| NOTE-536 | The Generalization Ridge: Information Flow in Natural Language Generation | I(Zℓ; Y) = H(G_Z) + H(G_Y) − H(G_Z ∘ G_Y), with H(G) = −tr(G log G) on trace-normalized Gaussian Gram matrices (bandwidth 1) of ℓ2-normalized last-token states and target-token embeddings. It rises, peaks at layers 10/12 (GPT-2-S, synthetic: 0.2721) and falls (0.0188 at layer 12), where OOD early-exit accuracy peaks (56.90%) and ID accuracy keeps rising (93.17%). Middle residual updates add most; OOD-fitted residual scales downweight the last layers. The profile’s shape persists over 50 decoding steps. | Read |
| NOTE-541 | Intermediate Layer Classifiers for OOD generalization | ILC_l(x) = W_l r_l(x) + b_l on frozen layer-l features, l ≤ L − 2, layer chosen on OOD validation data. Few-shot, best ILC minus last-layer retraining: +16.8, +6.3, +1.6, +6.3 points (ResNets on CMNIST, CIFAR-10, CIFAR-100C, MultiCelebA); +27.0 on MultiCelebA at π ≤ 0.03. Zero-shot worst-group accuracy: Waterbirds 79.4 → 87.1, CelebA 56.0 → 82.0, MultiCelebA 20.8 → 46.0. Layer 7 beats 8 everywhere in Figure 8. Intermediate features are less displaced by shift for minority groups. | Read |
| NOTE-542 | Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior | VSDL model: f = f(x; α, τ), α = m_eff/N lowered by label noise, τ raised by early stopping. Thermodynamic limit m, N → ∞ with α = m/N fixed. Continuous perceptron: s(ε) ~ ln ε, so 1/ε − α = 0 gives ε ~ 1/α (Eqs. 6–8). Ising perceptron: s(ε) ~ −(π²/2)ε² ln ε, and −π²ε ln ε = α has no solution for large α, so ε falls discontinuously to 0 at αc (Eqs. 9–13). Rigorous bound: error ≤ ε* + ε_τ, ε* the rightmost crossing of s(ε) and −α log(1 − ε) (Eqs. 14–18). No new theorem, no experiment. | Read |
| NOTE-544 | Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets | ε-dropout-stable ReLU nets are ε-connected by a piecewise-linear path (Theorem 1); ε-noise-stable nets by 10 segments with barrier Õ(ε) (Theorem 2), or 13 through a narrow low-loss net (Theorem 3). For any width there is a teacher dataset on which a two-layer student’s global minima are disconnected (Theorem 4). MNIST convnets and a VGG-11 on CIFAR-10 satisfy the conditions roughly. | Read |
| NOTE-620 | Learning to (Learn at Test Time) | Recasts a sequence-modelling layer as a learner trained on the sequence it reads: hidden state as inner-model weights, update as a gradient step on a learned self-supervised loss. Proves that the linear, batch-GD case is linear attention and that a Nadaraya–Watson inner learner is softmax attention; shows TTT-Linear and TTT-MLP use long context better than Mamba at up to 1.3B parameters. | Read |
| NOTE-621 | Transformers learn in-context by gradient descent | Constructs weights for which one linear self-attention layer reproduces, on every token, the data change induced by one gradient step of a linear model on the in-context regression loss, so the query’s output equals the post-update prediction; shows a trained single layer finds these weights up to scale, and that deeper trained models implement a curvature-corrected variant (GD++) rather than gradient descent. | Read |
| NOTE-633 | Implicit Bayesian inference account of in-context learning | Proves that if pretraining text is a mixture of HMMs and a model fits it exactly, conditioning on a prompt of concatenated examples recovers the prompt’s latent concept by posterior concentration, and the in-context predictor is asymptotically Bayes-optimal, whenever each example’s KL signal about the concept beats the error from the improbable transitions between examples. The account is of the data distribution, not of any network’s computation. | Read |
| NOTE-637 | Test-Time Training for Few-Shot Learning | Shows that turning a task’s few-shot demonstrations into a temporary weight update (per-task LoRA on leave-one-out in-context tasks) improves an 8B model over conditioning on the same demonstrations: 50.5% → 57.8% on BIG-Bench Hard, and large gains on ARC. The update works best when it is trained in the in-context format, and gains concentrate on tasks with structural rules or distribution shift. | Read |
| NOTE-658 v2 | Exact Learning Dynamics of In-Context Learning in Linear Transformers | Solves the averaged gradient-flow dynamics of one linear-attention layer trained on in-context regression, when tasks and input covariance share an eigenbasis and the weights are assumed to stay in it: each mode is a logistic curve on timescale (ηP s_α²)⁻¹, so learning is staged by the input spectrum, and the fixed point is the known preconditioned predictor W Σ̂_x [((N+1)/N)Σ_x + (Tr Σ_x/N)I]⁻¹. A scaling symmetry conserves ‖p₂‖² − ‖q₁‖². The transfer to non-linear transformers and grokking is a set of timing coincidences in spectral measures. | Read |
| NOTE-660 | Closed-Form Training Dynamics in Word2Vec-like Models | Proves that word2vec’s loss, approximated to fourth order and reweighted so that every pair carries the same aggregate weight, is unweighted factorisation of M*, the relative deviation of co-occurrence from independence, whose rank-d minimisers are its top eigenvectors; derives, without full rigour, that gradient flow from small random initialisation learns those eigenvectors one at a time in sigmoidal steps; and shows on Wikipedia that the predicted embeddings match word2vec’s features and scores better than truncated PMI or PPMI. Its account of analogies is an empirical spiked-random-matrix fit. | Read |
| NOTE-661 | Single-Head Attention in High Dimensions | In a solvable model, one tied softmax attention layer trained by ridge-penalized ERM on Gaussian sequences with n ∝ d² samples, derives (non-rigorously, by AMP and random-matrix theory) the test error, interpolation and recovery thresholds, and the spectrum of the learned query–key map, η·ReLU(S0 + δZ − ε): outliers are recovered target directions, the bulk is finite-sample noise, and weight decay acts as a nuclear norm. Power-law targets are recovered mode by mode, giving heavy-tailed spectra and LASSO-rate scaling laws. | Read |
| NOTE-662 | Towards Understanding Grokking | In a model that decodes the sum of two learned embeddings, a held-out pair is answered correctly when its embedding sum coincides with a trained pair’s, and the training set’s same-answer pairs force such coincidences. Grokking’s critical training fraction is then where those equations first fix the embedding up to translation and scale, which a posited effective loss predicts for addition with p = 10. Threshold-defined phase diagrams over decoder learning rate and weight decay put grokking between comprehension and memorization, in the toy and, qualitatively, in a transformer and on MNIST. | Read |
| NOTE-666 | A mathematical theory of semantic development in deep neural networks | Shows that a two-layer linear network trained from small weights learns the singular modes of its input–output correlations in order of strength, each by a sharp sigmoidal transition, where a shallow network learns all modes together; and that the singular structure of data generated on trees, rings and clusters, plus a minimum-norm property, accounts for coarse-to-fine differentiation, transient errors, narrowing generalisation, typicality, coherence thresholds and conserved representational similarity. Exact only from decoupled, balanced initial weights with white inputs; random initialisation is simulated. | Read |
| NOTE-667 | Exact solutions to the nonlinear dynamics of learning in deep linear neural networks | Derives the coupled gradient-descent equations of a linear network with hidden layers and whitened inputs, and solves them exactly from decoupled starts: one sigmoid per singular mode of the input–output correlation, with conserved differences of squared layer strengths; balanced or not with one hidden layer, from equal layer strengths at any depth. Depth slows learning only through the initial end-to-end mode strength, so from strength of order one the iteration count stays finite as depth grows when the step size is scaled down with depth. Argues, with MNIST and random-matrix simulations, that orthogonal layers or suitable pretraining give such starts and scaled Gaussian layers do not, and that orthogonal tanh networks near gain 1 keep their Jacobians near-isometric. | Read |
| NOTE-677 | The Random Hierarchy Model | Introduces the Random Hierarchy Model, a random context-free grammar in which each symbol has m synonymic expansions, and shows by experiment that deep feature-learning networks learn it from about n_c m^L examples, polynomial in the input dimension, while shallow and lazy networks need an exponential number. That size coincides with the emergence of synonym-invariant hidden representations and, by a scaling argument, with the size at which the class statistics of input patches, equal for synonyms, exceed sampling noise; removing those statistics makes deep networks fail as well. | Read |
| NOTE-684 | The Sparse Random Hierarchy Model | Adds sparsity to the Random Hierarchy Model, so that labels are unchanged by discrete displacements of the informative features, and shows by experiment that deep networks learn it from a number of examples polynomial in the input dimension, (s0 + 1)^L n_c m^L up to a factor s^(L/2) without weight sharing and (s0 + 1)^2 n_c m^L with it, and that hidden layers become insensitive to synonym swaps and to feature displacements at about the same training-set size as test error falls. That coincidence is offered as the reason deformation stability tracks performance on images, which is not tested on images. | Read |
| NOTE-687 | How the structure of language is acquired | Extends the Random Hierarchy Model to predicting a masked last token. The correlation between two tokens shrinks by about a factor m per level of their common ancestor, a sample of P sequences resolves it only above a (v²P)^(−1/2) noise floor, and deep transformers and CNNs show loss steps at P_ℓ ≈ v m^(2ℓ−1), where their layers come to encode the level-ℓ hidden symbol. On character-level text, the correlation decay exponent predicts where the loss for a given context length levels off. The route from correlations to learned hidden variables is argued, not proved. | Read |
| NOTE-688 v2 | Why does deep and cheap learning work so well? | Argues that cheap networks suffice because physical data have low-order, local, symmetric Hamiltonians, and that depth pays because inference must compose the sufficient statistics of a Markov generative hierarchy; proves that one hidden layer needs exactly 2^n neurons to multiply n inputs. On renormalization it is right that a coarse-graining needs a stated target, and its early appendix shows that neither a matched partition function nor the exact trace condition supplies one; it is wrong that the target must come from supervision. | Read |
| NOTE-689 | Deriving neural scaling laws from language statistics | Predicts the data-limited scaling exponent of language-model test loss as γ/(2β), from two measured corpus statistics: the decay with lag of the top singular value of the token–token covariance (β), which sets the usable context n*(P) ~ P^(1/(2β)), and the decay of next-token conditional entropy with context (γ). The derivation rests on assumed scaling forms and a fast-learning condition; on TinyStories and WikiText-103 transformers match the predicted exponents up to about 10^8 tokens and horizons of a few tens of tokens. | Read |
| NOTE-693 | The power of deeper networks for expressing natural functions | Proves that a single hidden layer of smooth, bias-free units needs exactly ∏(rᵢ+1) neurons to Taylor-approximate x₁^r₁⋯xₙ^rₙ while a deep network needs O(Σ log rᵢ), extends the gap to sparse and univariate polynomials, and bounds a product of n inputs at depth k by about 2^(n^(1/k)). Its uniform-approximation lower bounds rest on an unproved step, the depth-k tightness is a conjecture, and the gap is set by degree, so bounded-degree polynomials show none. | Read |
| NOTE-711 | The Limiting Dynamics of SGD | SGD with momentum β, learning rate η, batch size S and weight decay λ is modelled as (η/2)(1 + β)θ̈ + (1 − β)θ̇ + λθ = −g(θ) + √(η/S) √Σ ξ(t). For linear regression with Σ = σ²H this is an OU process in phase space. Its stationary state is Gibbs on a modified loss, with inverse temperature κ = S(1 − β²), in broken detailed balance. Under a quadratic loss at the end of training the same holds for deep networks, and a ResNet-18 on ImageNet shows the predicted isotropy, velocity regularization, oscillations and speed. | Read |
| NOTE-712 | Symmetry in Neural Network Parameter Spaces | A symmetry is a group action on parameters preserving the network function (Def. 2.4) or the loss (Def. 2.6), possibly only on given data or in expectation (Defs. 2.8–2.9). Common components have GL, scaling, sign-flip, orthogonal, translation and permutation symmetries (Table 1). Continuous symmetries make minima connected manifolds, and give gradient flow conserved quantities that label trajectories and endpoints (§5). SGD’s finite steps, noise and weight decay break these, which is an open route to implicit bias (§7.2). | Read |
| NOTE-713 | Neural Mechanics | A symmetry ψ of the loss gives ⟨∇L, ∂_α ψ⟩ = 0 and a Hessian constraint. Under gradient flow, Theorem 1 conserves ⟨θ, ∂_α ψ⟩: for translation ⟨θ_A, 1⟩, for scale |θ_A|², for rescale |θ_A1|² − |θ_A2|². With weight decay λ and the modified loss L + (η/4)|∇L|², these become exponentially decaying memories plus integrals of gradient norms (Eqs. 18–20), matched on VGG-16 with Tiny ImageNet. The noise covariance annihilates the generators (§5, App. F). | Read |
| NOTE-714 | Noise Balance and Stationary Distribution of Stochastic Gradient Descent | SDE: dθ = −∇L dt + √(T C(θ)) dW, with T = η/S. With ℓ(u, w) = ℓ(λu, w/λ), d(‖u‖² − ‖w‖²)/dt = −T(uᵀC₁u − wᵀC₂w) (Theorem 1). The stationary point is Tr C(w) = Tr C(u). With weight decay γ the rate is TC₀ + γ (Corollary 2.1). Diagonal linear network ℓ = (Σᵢ ∏ₖ u_i^{(k)} x − y)²: sign coherence and balance for depth D > 1 (Theorem 3), exact stationary distribution (Theorem 4), collapse above T_c = β₂/α₃ for D = 1, tail ∝ v^{−5+3/(D+1)} independent of data. | Read |
| NOTE-715 | From Lazy to Rich: Exact Learning Dynamics in Deep Linear Networks | Two-layer linear network ŷ = W₂W₁x, MSE, full-batch gradient flow. Assumptions: whitened inputs (A1), λ-balanced start W₂ᵀW₂ − W₁W₁ᵀ = λI (A2), no bottleneck (A3). Then QQᵀ, with Q = [W₁ᵀ; W₂], obeys a matrix Riccati equation (Lemma 4.1), solved exactly (Theorem 4.3). For aligned starts, each singular value moves by a λ-dependent transition function: sigmoidal as λ → 0, exponential 1 − e^{−|λ|t/τ} as |λ| → ∞ (Theorem 5.1). | Read |
| NOTE-716 | Symmetry Induces Structure and Constraint of Learning | ℓ_γ = ℓ₀(θ, x) + γ‖θ‖². O-mirror symmetry: ℓ₀(θ) = ℓ₀((I − 2OOᵀ)θ). Theorem 1: (1) Oᵀθ = 0 implies Oᵀ∇ℓ_γ = 0; (2) at symmetric points the Hessian splits into ker(Oᵀ) and im(OOᵀ) blocks; (3) above some γ₀ the projection (I − OOᵀ)θ has lower loss; (4) above some γ₁ all minima satisfy Oᵀθ = 0. SGD near the symmetric set: Pθ_{t+1} = Pθ_t − λH(x)Pθ_t, attractive when the Lyapunov exponent E log|1 − λ(ξ + γ)| < 0. Corollaries: sparsity, low rank, homogeneous neurons (Theorems 2–4). | Read |
| NOTE-738 | Nielsen et al. — When Does Closeness in Distribution Imply Representational Similarity? | For softmax models p(y|x) ∝ exp(f(x)ᵀg(y)), equal distributions fix the embeddings up to an invertible linear map, but KL closeness does not: by making the unembedding norm large, two models’ KL divergence goes to zero while their embeddings stay fixed and are not linearly related. A log-likelihood variance distance does bound a representational dissimilarity, d_LLV ≤ ε ⇒ d_f,g ≤ 2Mε. Whether closeness in distribution implies similar representations depends on which distance is used. | Read |
| NOTE-740 v2 | HaoChen et al. — Spectral Contrastive Loss | On a finite augmentation space, the spectral contrastive loss L(f) = −2E[f(x)ᵀf(x⁺)] + E[(f(x)ᵀf(x⁻))²] equals the rank-k factorization loss ‖D^(−1/2)AD^(−1/2) − FFᵀ‖²_F up to a constant when the rows of F are w_x^(1/2) f(x), so its minimizers are the top-k eigenvectors of the normalized augmentation graph up to row scaling and a right rotation. A linear probe on them has error Õ(α/ρ²_⌊k/2⌋), where α is the label noise of augmentations and ρ the sparsest-partition conductance. | Read |
| NOTE-741 | Simon et al. — On the Stepwise Nature of Self-Supervised Learning | For a simplified Barlow Twins loss on a linear or kernel model trained by gradient flow from small initialization, the embedding learns the top eigenvectors of a symmetrized cross-correlation operator one at a time, each at a time set by its eigenvalue, and lands on the minimum-norm zero-loss solution: kernel PCA on K_Γ. Exact for aligned initialization; an informal derivation for generic small initialization. ResNets trained with Barlow Twins, SimCLR and VICReg show the same stepwise rank growth, which is an empirical finding, not a consequence of the theory. | Read |
| NOTE-742 | Sefidgaran, Zaidi & Krasnowski — MDL and Generalization Guarantees for Representation Learning | The expected generalisation error of an encoder–decoder classifier is bounded by 2√((2·MDL + K + 2)/n) + ε, where MDL is a KL divergence between the encoder’s joint law of train-and-ghost latents and a prior symmetric under label-preserving permutations. The bound holds for any decoder, stays finite for deterministic continuous encoders under lossy compression, and is never evaluated numerically. A VIB variant with label-dependent learned priors gains about 2.5 points on CIFAR-10. | Read |
| NOTE-751 v2 | Johnson, El Hanchi & Maddison — Contrastive Learning Can Find an Optimal Basis | On a finite augmentation space, the NT-Logistic and spectral losses are minimized over unconstrained kernels by K⁺ = p⁺/(p⊗p), and InfoNCE by K⁺ up to a factor constant on communicating classes. Kernel PCA under K⁺ returns the eigenfunctions of the positive-pair Markov chain (h_i = λ_i^(1/2) f_i). The top-d eigenfunctions span the subspace that minimizes worst-case L²(p) approximation error over targets with E_p⁺[(g(a₁) − g(a₂))²] ≤ ε; that error is ε/(2(1 − λ_(d+1))). | Read |
| NOTE-754 | Fischer — The Conditional Entropy Bottleneck | The MNI criterion asks for I(X;Y) = I(X;Z) = I(Y;Z), and CEB targets it by minimizing I(X;Z|Y) − γI(Y;Z), which is IB with γ = β − 1. CEB beats VIB at every ρ on Fashion MNIST for accuracy and robustness, and a CEB Wide ResNet beats Madry’s adversarially trained model on CIFAR-10 without adversarial training. That retained information causes the robustness failures is a hypothesis, supported only by these experiments. | Read |
| NOTE-760 | Grünwald & Roos — Minimum Description Length Revisited | A review of MDL since 2007. Each model is replaced by one universal distribution, chosen for small worst-case log-loss regret against the model’s best fit. NML is the minimax choice, with complexity (k/2) log(n/2π) + log ∫ v√|I| + o(1). Estimation is penalised ML with a luckiness function v. The switch distribution nearly resolves AIC–BIC, the RIPr gives tests safe under optional continuation, and MDL and Bayes can be inconsistent under misspecification. Results are cited, not proved. | Read |
| NOTE-762 | Kornblith, Chen, Lee & Norouzi — Why Do Better Loss Functions Lead to Less Transferable Features? | For ResNet-50 on ImageNet, every training objective that raises accuracy over softmax cross-entropy also raises penultimate-layer class separation, and fixed penultimate features with more class separation transfer worse to new-class datasets (Spearman ρ = −0.93 across nine objectives; one temperature knob moves both). The losses differ only in the last few blocks, and full fine-tuning erases the difference. For the pretraining classes themselves, more separation helps. | Read |
| NOTE-764 | Thrampoulidis et al. — Imbalance Trouble | In the unconstrained-features model with cross-entropy and vanishing regularization, the max-margin solutions have logits exactly equal to the simplex-encoded label matrix Ẑ (one-hot minus 1/k), whatever the class imbalance. The classifier and embedding Gram matrices are VΛVᵀ and UΛUᵀ from Ẑ’s SVD. This SELI geometry is the simplex ETF only for balanced or binary data. Under imbalance, majority classifiers are longer and minority classifiers closer together. No finite weight decay gives SELI, and SGD approaches it more slowly as imbalance grows. | Read |
| NOTE-770 v2 | Zhai — Contextures: The Mechanism of Representation Learning | For any joint law of an input X and a context A, symmetric or not, the conditional-expectation operator from L²(P_A) to L²(P_X) has a singular value decomposition (assuming Hilbert–Schmidt), and its top-d left singular functions are a d-dimensional encoder (not the unique one, as the thesis says; see version 2) that minimizes worst-case linear-probe approximation error over tasks of compatibility at least 1−ε. Several squared-error objectives reach that span at their optimum. The claims about scaling and about moderate association are argued and measured, not proved. | Read |
| NOTE-772 v2 | Kothapalli — Neural Collapse: A Review on Modelling Principles and Generalization | A survey, not a source of results. It sorts accounts of neural collapse into unconstrained-features models (the last-layer features are free variables) and local elasticity, and reports that every one of them derives the collapsed state or its dynamics only after removing the data. On generalization it finds the literature in conflict. Collapse on the training set does not guarantee good test error, test-set collapse is much weaker and dataset-dependent, and there is no agreed threshold for calling a network collapsed. It also reports that networks more collapsed on ImageNet transfer worse. | Skimmed |
| NOTE-774 | Kothapalli & Tirer — Can Kernel Methods Explain How the Data Affects Neural Collapse? | NC1, measured as tr Σ_W / tr Σ_B, is written for any kernel as a function of the kernel matrix. For two-class, one-dimensional Gaussian data with the classes on opposite sides of the origin, the ReLU NTK of a wide two-layer net is a scaled copy of the NNGP kernel within each class and zero across classes. So lazy-regime training leaves expected NC1 where it was at initialization. In higher dimensions the NTK is measured no more collapsed, and with ReLU less. A data-aware kernel lowers NC1 for separable data but tracks finite networks poorly when the classes overlap or are imbalanced. Erf collapses more than ReLU. | Read |
| NOTE-776 | Grünwald & Vitányi — Shannon information and Kolmogorov complexity | A survey pairing Shannon’s and Kolmogorov’s notions. Expected Kolmogorov complexity exceeds entropy by between 0 and K(f) + O(1), and expected algorithmic mutual information lies between I(X;Y) − K(f) and I(X;Y) + 2K(f). An algorithmic sufficient statistic is probabilistically nearly sufficient in expectation, one way only. The expected structure function brackets the distortion-rate function with a K(f, d, m, R) shift in rate. Each link holds only up to the complexity of the distribution. | Read |
| NOTE-777 | Belrose et al. — Neural Networks Learn Statistics of Increasing Complexity | An empirical paper. Vision networks trained on real images classify maximum-entropy samples that match only the class means, or means and covariances, well above chance early in training (peaks between about 2^4 and 2^12 steps), and the accuracy then falls, often below chance. First-order samples peak earlier and lower than second-order ones. Pythia models fit unigram-sampled text, then bigram-sampled text, then fit them worse, then better again. The n-gram/moment equivalence is an identity of one-hot indicators. The ordering argument is a heuristic. | Read |
| NOTE-780 | Sefidgaran, Gohari, Richard & Şimşekli — Rate-Distortion Theoretic Generalization Bounds | The expected generalisation error of any algorithm is at most √(2σ²·R/n) + ε, where R is the least mutual information I(S;Ŵ) of any surrogate output whose expected generalisation error is within ε. With ε = 0 this is Xu–Raginsky. With ε > 0 it stays finite where I(S;W) is infinite. For a Lipschitz loss R becomes the rate-distortion function of the output’s marginal law, and as ε → 0 its rate-distortion dimension. A tail bound replaces I(S;W) by its supremum over laws within log(1/δ) in KL. Every bound depends on the unknown data distribution. | Read |
| NOTE-783 | Han, Papyan & Donoho — Neural Collapse Under MSE Loss | Networks trained with MSE loss show neural collapse on five datasets and three architectures. The MSE loss splits exactly into a term for the least-squares classifier of the current features and a non-negative deviation term, and the deviation becomes negligible early in training. On that “central path”, in an unconstrained-features model with no weight decay and features continually renormalized to identity within-class covariance, gradient flow drives every singular value of Σ_W^(−1/2)M̃ to infinity as (4t/N)^(1/4), and drives them to equality. That gives NC1–NC4 in closed form. | Read |
| NOTE-787 v2 | Vereshchagin & Vitányi — Kolmogorov’s structure functions and model selection | For a string x of length n and every complexity bound α, the minimal two-part code length λ_x(α), the structure function h_x(α) + α and the best achievable fit β_x(α) + K(x) are one function to within O(log n), and any set witnessing λ_x or h_x also witnesses β_x. Every non-increasing shape occurs for some x. h_x and λ_x are upper semicomputable but not computable; β_x is not even semicomputable. Finite sets only; the extension to computable distributions costs O(log n). | Read |
| NOTE-790 | Vitányi — Meaningful Information | With total recursive functions as models, the shortest model that completes an optimal two-part code for a string (its sophistication) is a non-trivial split of its information into structure and noise. With partial recursive models the split collapses to zero for every string. The total-function, computable-distribution and finite-set classes agree to within logarithmic terms. Some strings of every length are almost all structure, and sophistication is not computable. | Read |
| NOTE-794 | Liu et al. — Physics of Skill Learning | Three toy models of skill learning. In the Geometry model, independent skills are orthogonal directions in parameter space weighted by frequency. Under SGD each is learned at its own rate, the second taking about 1/p₂ as long. Under sign descent they compete for coordinate signs, and each starts as the one before finishes (the Domino effect), so the n-th skill takes time ∝ n. A one-parameter Resource ODE fits these curves and has exact conserved quantities u_i^(1/p_i). A small MLP also shows the effect when one parity is the XOR of two others. | Read |
| NOTE-796 | Gu et al. — Data Mixing Can Induce Phase Transitions in Knowledge Acquisition | An optimal capacity-bounded learner, given a mixture of equally frequent random facts and a second domain, learns none of the facts until the second domain’s marginal loss reduction per unit of capacity falls below r·p/(1−r), then all of them within Htot more capacity. Pythia models trained on synthetic biographies mixed into web text show near-zero recall below a threshold model size and mixing ratio, and 4–16 times more training barely moves it. | Read |
| NOTE-800 | Noroozizadeh et al. — Deep sequence models tend to memorize geometrically | Transformers and Mamba trained only on a graph’s edge bigrams embed nodes so that multi-hop relations are readable, and solve an in-weights path-finding task built to defeat next-token learning. The authors argue that supervision, capacity, ease of optimization and succinctness each fail to explain why this geometry wins over an associative lookup. In a wide two-layer weight-tied model under unregularized cross-entropy the embeddings settle into the top Laplacian eigenvectors without a rank bottleneck, shown empirically, with an informal partial proof. Why deeper models prefer geometry is left open. | Read |
| NOTE-801 | Vitányi & Li — MDL induction, Bayesianism and Kolmogorov complexity | With the universal prior, the Fundamental Inequality puts −log Pr(D|H) − log P(H) within α = K(Pr(·|H)) + K(P) of K(D|H) + K(H) when D is random for H and H is random for P. So ideal MDL and MAP agree to a factor 2^{−α} among such “admissible” hypotheses. α can be as large as K(H), and outside the admissible set the two can pick different hypotheses. For finite-set models, MAP, ideal MDL and Kolmogorov’s minimal sufficient statistic coincide. | Read |
| NOTE-804 | Goldwasser et al. — A Theory of Unsupervised Translation Motivated by Animal Communication | With a plausibility prior over the target language and no parallel data, maximum likelihood learns a translator whose error is bounded like a supervised Occam bound divided by the common ground. In the common-nonsense model err = O(log|Θ| / (α·min(m,|T|))), tight up to a constant; in the knowledge-graph model more knowledge per node needs less agreement. Information-theoretic only, lossless, uniform languages. | Read |
| NOTE-805 | Defilippis et al. — Optimal scaling laws in learning hierarchical multi-index models | For Gaussian inputs, n = αd samples, and a target Σ_k a_k g_k(⟨w_k, x⟩) with even links and a_k ~ k^(−γ), direction k becomes weakly recoverable at α_k = Θ(a_k^(−2)) = Θ(k^(2γ)) for γ > 1/2. The Bayes-optimal weighted subspace error is Θ(α^(−1+1/(2γ))) before α ≍ m⋆^(2γ) and Θ(m⋆/α) after. A target-agnostic spectral estimator attains both, and a two-layer net given that estimator as its first layer, with a ridge readout, attains them in excess risk. The cascade is in sample size. The link to gradient descent is a remark. | Read |
| NOTE-806 | Sefidgaran & Zaidi — Data-Dependent Generalization Bounds via Variable-Size Compressibility | If the number of codewords allowed for covering a block of experiments may depend on the realised sample and output, generalisation bounds can be data-dependent. The general bounds are change-of-measure inequalities that cover tail, PAC-Bayes and in-expectation forms. With the rate set to log dP_{W|S}/dP(W) for a fixed prior P, the tail bound is the disintegrated PAC-Bayes bound. A new trajectory bound is data-dependent except for a coupling term, and its experiment drops that term. | Read |
| NOTE-807 | Gokhale — The semantic landscape paradigm for neural networks | A conceptual proposal with no experiment and no proof. Training is pictured as a walk on a graph of “heuristic models” (internal algorithms), ranked by a fallibility F. A critical dataset size for grokking and emergence with scale are each argued to be graph connectivity thresholds, and power-law scaling in time, data and size is derived from an assumed trap model of activated hops. The percolation is asserted, not shown, and the scaling laws rest on chosen assumptions. | Read |
| NOTE-815 | Gerstgrasser et al. — Is Model Collapse Inevitable? | In a fixed-design linear regression refit each round to labels drawn from the previous fit, keeping every earlier round’s data gives test error σ²d/(T−d−1)·Σ1/i², bounded by π²/6 times the first fit’s, where replacing the data gives σ²d/(T−d−1)·n. The error still rises every round. Small language models and a diffusion model on accumulated data hold their test loss over five to eight rounds; a VAE’s still rises, more slowly. | Read |
| NOTE-833 | Sun, Shi, Liang & Li — when known classes help discover novel ones | In a spectral-contrastive augmentation graph over labelled and unlabelled data, the linear-probe residual of a novel labelling is exactly the part of it outside the top-k eigenspace that the labelled rows of the discarded eigenvectors cannot absorb. Known classes that share the novel class’s attribute can make it zero, and a toy shows that known classes sharing a rival attribute make it worse. The general error bound (Theorem 5.6) is approximate and averages all known classes into one block. | Read |
| NOTE-836 | Schölkopf, Herbrich & Smola — A Generalized Representer Theorem | For any nonempty set X, real positive-definite kernel k, strictly increasing g and any cost c on the training triples, even coupled, non-convex or infinite-valued, every minimizer of c + g(‖f‖) over the class F of countable kernel expansions with finite RKHS norm is a finite expansion Σ α_i k(·, x_i) at the training points. The proof uses only the reproducing property and Pythagoras. Existence of a minimizer, the extension from F to the completed RKHS, and the semiparametric Theorem 2 are not proved here. | Read |
| NOTE-838 | Muandet et al. — Kernel Mean Embedding of Distributions | A survey whose load-bearing chain is short and explicit. An RKHS is a Hilbert space with bounded evaluation, so Riesz gives k_x (Thm 2.4, Prop. 2.1). If E_P√k(X,X) < ∞, the expectation functional is bounded and Riesz gives μ_P with E_P f = ⟨f, μ_P⟩ (Lemma 3.1, proved). MMD is ‖μ_P − μ_Q‖ (eq. 3.29), a metric on distributions exactly when k is characteristic. HSIC is the squared Hilbert–Schmidt norm of the centred cross-covariance. Every result is for a fixed kernel. | Read |
| NOTE-841 | Tosh, Krishnamurthy & Hsu — contrastive learning, multi-view redundancy and linear models | When two views X and Z are redundant for a label, the predictor that infers Z from X and then predicts, µ(x) = E[E[Y|Z]|X=x], is within εX + 2√(εXεZ) + εZ of the Bayes predictor. µ is linear in the density ratio g*(x,·) = p(x,z)/(p(x)p(z)), the optimum of the logistic contrastive problem, so m random landmark evaluations of g* support a linear predictor whose extra error falls as 1/m, scaled by a variance that is at most E[g*²] for bounded labels. Nothing requires the views to be exchangeable. | Read |
| NOTE-845 | Balestriero, Bottou & LeCun — regularization effects are class dependent | On ImageNet with ResNet-50, making random crop stronger or changing weight decay raises mean test accuracy while some classes lose 20 points or more, and the shift survives a frozen-backbone transfer to iNaturalist. The evidence is per-class curves for hand-picked classes over 10–20 runs, plus a Welch test with no multiple-comparison correction. Theorem 1 says only that a fit to augmentations that are not label-preserving cannot equal the true function. | Read |
| NOTE-848 | Dwork et al. — The reusable holdout (supplementary material) | From the Supplementary Material: if the max-information between the dataset and the analyst’s chosen function is at most log₂e·τ²n, the chance that the function’s empirical mean is more than τ above its true mean is at most e^{−τ²n}; pure ε-differential privacy bounds max-information by log₂e·εn. Thresholdout answers m adaptively chosen statistical queries on a holdout of size n = O(ln(m/β)/τ² · min{B, √(B·ln(m/β))/τ}) to accuracy τ with probability 1 − β, where B budgets the times the training estimate is found to overfit. The main text was not read. | Skimmed |
| NOTE-869 | Snell, Lee, Xu & Kumar — Scaling LLM test-time compute optimally | On MATH with PaLM 2-S*, which way of spending test-time compute works best (beam search against a process reward model versus best-of-N; sequential self-revision versus parallel sampling) depends on how hard the question is for the base model, and choosing the method per difficulty bin matches best-of-N with up to about 4× less test-time compute (the discussion says 2–4×). In a FLOPs-matched comparison with a ~14× larger model, the extra test-time compute a small model may spend is set by R, the ratio of total inference tokens to pretraining tokens: when R is small the larger model’s pretraining cost buys many samples per query and test-time compute wins on easy and medium questions; when R is large the budget per query falls toward the parameter ratio and the larger model wins, always on the hardest questions. Difficulty estimation (2048 samples per question) and verifier and revision-model finetuning are not counted in the compute, R is an aggregate token ratio with no term for which queries recur, and the evidence is one model family on one benchmark of 500 test questions. | Read |
| NOTE-873 | Lieder & Griffiths — Resource-rational analysis | Resource rationality defines the right cognitive mechanism as the one, among those a brain can execute, that maximizes expected utility of its result minus the expected opportunity cost of the time and resources it uses (Eq. 3), averaged over the environments consistent with what is known (Eq. 4); resource-rational analysis is a five-step iterate-and-refine method for deriving process models from that objective. The objective is per episode. It has no separate terms for storing a result, retrieving it later, or its going stale: the value of what a computation leaves behind is folded into the utility of the episode’s result, and the cost of finding the heuristic in the first place is assigned to evolution and learning and left out. Reuse appears only in the review, qualitatively: habits as reused action sequences, Dasgupta et al. 2018’s memorized hypotheses, Howes et al. 2016’s memorize-or-look-up trade, and “cognitive prostheses”. The framework is offered as a methodological device, not a claim that people are optimal. | Read |
| NOTE-879 | Hébert-Johnson, Kim, Reingold & Rothblum — Multicalibration: calibration for the computationally-identifiable masses | A predictor is α-multicalibrated on a collection C of subpopulations if, within every set S in C, the individuals given (roughly) the same prediction v have true probabilities averaging within α of v, except on an α-fraction of S. For any C whose sets have size at least γN, a simple iterative patching algorithm reaches multicalibration from O(log|C|/α^{11/2}γ^{3/2}) samples in time linear in |C|, and the result is a circuit only O(s/α⁴γ) in size when the sets of C are computed by size-s circuits. Learning it is equivalent, up to polynomial factors, to weak agnostic learning of C, so it is hard for rich C under cryptographic assumptions. Calibrating any predictor h on its own level sets as well as on C costs at most 6α in squared error. All guarantees are relative to the benchmark p*, which is itself defined relative to the features available, and they hold only for large sets; the paper offers no uniqueness for the predictor and does not state a theorem in indistinguishability form. | Read |
| NOTE-881 | Sardana, Portes, Doubov & Frankle — Beyond Chinchilla-optimal: accounting for inference in scaling laws | Fixing a target pre-training loss and adding inference FLOPs (2N per token over a known lifetime demand D_inf) to training FLOPs (6N per token), the compute-minimising model is smaller and trained on more data than Chinchilla-optimal, increasingly so as D_inf approaches and exceeds the training-set size; the optimum has no closed form and is found numerically. The savings are modest in FLOPs (for a 30B-Chinchilla-quality model with 10^13 inference tokens, 28% by training 13.6B on 2.84× the data) and larger in dollars once inference’s low hardware utilisation is priced in (17% to 58% in the paper’s examples). 47 training runs (150M–6B parameters, 10–10,000 tokens per parameter) find loss still falling at extreme ratios, but more slowly than Chinchilla-fitted laws predict, so the formula overstates the gain from long training. Demand is assumed known before training and fixed given quality; there is no term for uncertainty, discounting, obsolescence or a model being replaced. | Read |
| NOTE-884 | Jones — Scaling scaling laws with board games | Training AlphaZero on Hex at board sizes 3×3 to 9×9, the best Elo reachable for a given training compute follows one change-point curve across sizes: an incline of about 500 Elo per tenfold of training compute, with the compute for perfect play rising about 7× and the compute to leave random play about 4× per added board row, and fits on small boards predicting larger ones. On 9×9 only, train-time and test-time (tree-search) compute substitute at a fixed rate: at equal Elo, each 10× of train-time compute removes about 15× of test-time compute (fit: log test = −1.2·log train + 0.004·Elo + 29), down to a one-node search, over roughly 1e14–1e16 FLOPS-seconds of training. The trade is an iso-performance curve for a single search; the paper never counts how many games or moves the trained agent will play, so it does not price amortization, and it does not state the unit of test-time compute. One game, small boards, Elo anchored to a perfect player, and no uncertainty on the fitted trade-off coefficients. | Read |
| NOTE-885 | Dwork, Kim, Reingold, Rothblum & Yona — Outcome Indistinguishability | A predictor p̃ is outcome indistinguishable (OI) relative to a class A of distinguishers when no A ∈ A can tell an individual with Nature’s outcome from the same individual with an outcome drawn from Ber(p̃_i). The paper sets out four levels by how much access the distinguisher has to p̃: none, the prediction on the sampled individual, oracle queries, or the code. The lower two levels are equivalent to multi-accuracy and multi-calibration over closely related classes. At those levels OI predictors exist with size O(s/ε²), whatever Nature’s complexity. At the oracle level, under fine-grained hardness of clique counting or BPP ≠ PSPACE, some efficient distinguisher classes force any OI predictor to be nearly as expensive as Nature’s own predictor. That gives a strict separation between oracle access and sample access. OI never requires p̃ ≈ p*. A predictor is good only relative to A, and with the paper’s construction a weak A gives a coarse predictor that a richer A would refute. The paper covers binary outcomes, a fixed representation of individuals and single samples (multi-sample OI is left mostly to future work). | Read |
| NOTE-981 | Charvin, Catenacci Volpi and Polani — Exact and soft successive refinement of the IB | Defines successive refinement for the information bottleneck as extending a coarse optimum T₁ to a fine optimum (T₁, S), and shows it equivalent to some pair of optima forming X → T₂ → T₁. With an injective fine decoder, it is also equivalent to the coarse decoder points lying in the convex hull of the fine ones, which a linear programme checks. Refinability is proved for binary X and Y, for Y a function of X, and for jointly Gaussian variables. Numerically the hull test on computed optima often fails, and the loss, measured by unique information, stays under a few percent. Those failures are uncertified. Run here with certified optima, the test shows that the four-state source of CLAIM-387 is not refinable between β = 8 and β = 12: its stochastic optima do not nest either. | Read |
| NOTE-983 | Rahaman et al. — On the Spectral Bias of Neural Networks | A ReLU network is piecewise linear, so its Fourier transform falls as k^(−d−1) along almost every direction and as k^(−2) along the normals to the faces of its linear regions; that is proved for compactly supported networks only. Trained networks fit low frequencies first, even when high frequencies carry ten times the amplitude, and high-frequency components are the first to be destroyed by parameter noise; both are experiments. The tie from the decay to the order of learning is a heuristic bound, and the volume “proof” in Appendix D does not hold. On a curve embedded in the plane, high latent frequencies are fitted more easily as the curve gets more petals. The paper puts this down to the shape of the curve, but most of it comes from the curve getting longer. | Read |
| NOTE-1044 | Perdomo, Zrnic, Mendler-Dünner and Hardt — Performative prediction | When a deployed model’s predictions change the distribution they are scored on, D(θ), two solution concepts separate: a performative optimum minimizes the risk on the distribution it induces, and a performatively stable point is optimal for the distribution it induces, a fixed point of retraining. With a β-jointly smooth, γ-strongly convex loss and a map D(·) that is ε-Lipschitz in Wasserstein-1, retraining contracts at rate εβ/γ and converges to a unique stable point when ε < γ/β, and removing any one condition can break convergence. Stable points and optima are within 2L_zε/γ of each other, and can differ. | Read |
| NOTE-1048 | Xu, Zhao, Song, Stewart and Ermon — A theory of usable information under computational constraints | Defines predictive V-information, I_V(X → Y) = H_V(Y | ∅) − H_V(Y | X), where each V-entropy is the least expected log loss a predictor in the family V can reach. With V unrestricted it is Shannon mutual information; with linear-Gaussian V it is R² times the variance. It is non-negative and zero under independence because V must be able to ignore its input. Unlike Shannon information it can be asymmetric and can be raised by computing on X, and its empirical estimate is within 4R(G_V) + 2B√(2 log(1/δ)/N) of the truth with probability 1 − 2δ. It is not bounded by Shannon information unless V’s input-free predictions can match the marginal of Y. | Read |
| NOTE-1132 | Soma et al. — The hive mind is a single reinforcement learning agent | A short theoretical paper with simulations. In an infinite, well-mixed population, imitation of success has the expected update of Cross Learning, and the weighted voter model of the honey-bee waggle dance that of Maynard-Cross Learning, the Maynard-Smith replicator dynamic. The population’s type distribution is the policy of a stateless bandit agent, each member is one parallel sample of it, and no member learns. The authors keep the biology partial and the simulations qualitative. | Read |
| NOTE-1140 | Kaisers & Tuyls — Frequency adjusted multi-agent Q-learning | A short algorithmic paper with plotted experiments. The selection–mutation model of Boltzmann Q-learning (Tuyls et al. 2003, 2005) assumes every Q-value changes at rate α; in Q-learning only the chosen action’s does, so its expected change carries a factor x_i, and Q-learning departs from the model depending on initialization. A frequency-adjusted update removes the factor and matches the model. Three 2×2 games, one temperature, no quantitative measure of fit. | Read |
| NOTE-1141 | Son et al. — QTRAN: learning to factorize with transformation | Defines Individual-Global-Max (IGM): per-agent values factorise a joint value when the profile of individual argmaxes is the joint argmax. Additivity and monotonicity are sufficient conditions; QTRAN trains the sum of individual values plus a state value to equal the joint value at the greedy profile and bound it elsewhere, which is sufficient and, up to rescaling, necessary. Every single-state matrix game satisfies IGM; VDN and QMIX missed the optimum in 177 of 310 random 3×3 games. | Read |
| NOTE-1142 | Hart & Mas-Colell — A simple adaptive procedure leading to correlated equilibrium | A theorem with a proof. Regret matching, switching from one’s last action to each alternative with probability proportional to the positive regret for not having made that switch in the past, drives the empirical joint distribution of play almost surely to the set of correlated equilibria when every player uses it. Regrets vanish exactly when the empirical distribution approaches that set. A stylized variant is analysed by Blackwell approachability; the main procedure needs inertia and needs players to see one another’s past play. | Read |
| NOTE-1143 | Balduzzi et al. — Open-ended learning in symmetric zero-sum games | A framework paper with an algorithm and two small experiments. Symmetric zero-sum games between parametrized agents split into transitive and cyclic parts relative to a measure on agents. In a cyclic game an individual’s performance is meaningless, so evaluation moves to populations: the value of the game between them, which is invariant to redundant members, and the convex hull of their evaluation rows. Training each supported agent on what it beats grows that hull. | Read |
| NOTE-1144 | Sato & Crutchfield — Coupled replicator equations for the dynamics of learning in multiagent systems | A four-page letter. Two agents choose by softmax over reward memories that decay at rate α; with learning slow relative to play, each agent’s choice distribution follows a replicator dynamic in the other’s play plus α Σ_j x_j log(x_j/x_i), a pull towards uniform play. Without decay the system is conservative, Hamiltonian in zero-sum games; with decay it is dissipative. Rock–scissors–paper simulations show tori, Hamiltonian chaos, heteroclinic transients, limit cycles and chaotic attractors. Derivation plus numerics, no data. | Read |
| NOTE-1145 | Shazeer et al. — Outrageously large neural networks: the sparsely-gated mixture-of-experts layer | An engineering paper with large experiments. A sparsely-gated layer of up to 131,072 experts raises capacity over 1000-fold at roughly constant computation. Read here for one observation and one fix: without constraint the gate concentrates on a few experts, which the authors call self-reinforcing, and two auxiliary losses that penalize unequal importance and load remove it, which in one ablation also improves perplexity from 39.8 to 35.6. | Read |
| NOTE-1146 | Czarnecki et al. — Real world games look like spinning tops | A hypothesis paper with theorems and sampled empirical games. Where players can signal n bits before the outcome is settled, every win–loss pattern on 2ⁿ strategies occurs, so cycles are astronomically long. Nash clustering layers any symmetric zero-sum game, and beating a whole cluster guarantees climbing. Sampled games show cluster size peaking at middling strength. The body says the geometry is not proved, the abstract says it is. Two of the smaller results have defective statements or proofs. | Read |
| NOTE-1147 | Jacobs, Jordan, Nowlan and Hinton — Adaptive mixtures of local experts | A short paper that founds the mixture of experts. Scoring the error of a single, gate-selected expert, or the mixture’s negative log-likelihood, makes experts compete for cases, and an expert better than the gate-weighted average gains responsibility for the case. On a vowel task 4 or 8 linear experts learned in half the epochs of matched backpropagation networks at equal accuracy, divided the task by class pair, and left all but 2 or 3 experts with mixing proportion near zero. | Read |
| NOTE-1148 | Yang et al. — Mean field multi-agent reinforcement learning | An algorithms paper with a convergence proof and three experiments. Each agent’s Q-function is approximated by its interaction with the mean action of its neighbours, which makes many-agent RL tractable for hundreds of homogeneous agents. Mean field Q-learning converges to a Nash Q-value under strong assumptions, learns Gaussian Squeeze with 500 and 1000 agents where baselines fail, matches MCMC on a 20 × 20 Ising model, and wins a 64-versus-64 battle game. | Read |
| NOTE-1150 | Foerster et al. — Learning with opponent-learning awareness | A LOLA learner maximises its return after the opponent’s anticipated naive gradient step and differentiates through that step, adding a second-order term to its gradient. Two exact-gradient LOLA learners reached tit-for-tat-like reciprocity in the memory-one iterated prisoner’s dilemma where naive learners ended at mutual defection, and settled at the mixed equilibrium of iterated matching pennies where naive learners did not converge. A policy-gradient version cooperated in the Coin Game, less reliably with a learned model of the opponent. | Read |
| NOTE-1151 | Leibo et al. — Multi-agent reinforcement learning in sequential social dilemmas | A descriptive simulation study. It defines sequential social dilemmas, Markov games whose learned cooperative and defecting policies give social-dilemma payoffs, and runs independent deep Q-learners on two two-player games. Scarcity and costly conflict produce aggression in Gathering; group benefit produces joint hunting in Wolfpack; and network size moves defection in opposite directions in two games that both embed a Prisoner’s Dilemma. | Read |
| NOTE-1152 | Foerster et al. — Counterfactual multi-agent policy gradients | A centralised critic Q(s, τ, u) trains decentralised actors, and each agent’s action is scored against the critic’s average over its own alternatives under its own policy, the others’ actions fixed. The baseline does not change the expected gradient. On StarCraft micromanagement with a narrow field of view it beat independent and central-V/QV actor-critics on four maps. The counterfactual is the critic’s estimate, not a simulation, and it values alternatives the agents sometimes take. | Read |
| NOTE-1154 | Rashid et al. — QMIX: monotonic value function factorisation | Per-agent values Q_a(τ^a, u^a) are combined into a joint Q_tot by a mixing network whose weights, generated from the state, are kept non-negative, so ∂Q_tot/∂Q_a ≥ 0. Then the individually greedy actions form a greedy joint action and agents can act on their own values. It represents more than a sum and learned the optimum of a two-step game that a sum misses; it cannot represent a joint value in which one agent’s best action depends on the others’ current actions. | Read |
| NOTE-1159 | Kwon and Perchet — Blackwell approachability with partial monitoring: optimal convergence rates | Approachability of a polytope (reduced to the negative orthant) under partial monitoring, where the decision maker sees only a random signal whose law is known, can be achieved at rate O(T^-1/3) in expected distance for general signals and O(T^-1/2) when the signal law does not depend on the decision. The general algorithm lifts the problem to an auxiliary full-information approachability problem that is linear in the flags, and keeps a uniform exploration floor γ ∝ T^-1/3 so that the flags can be estimated by importance weighting. | Read |
| NOTE-1162 | Lattimore and Szepesvári — Cleaning up the neighborhood: a full classification for adversarial partial monitoring | Completes the classification of finite partial-monitoring games against oblivious adversaries to every game, degenerate and duplicate actions included: 0 with no neighbouring pair, Θ̃(√n) locally observable, Θ(n^2/3) globally but not locally observable, Ω(n) otherwise. The missing piece is NeighborhoodWatch2, which redistributes probability onto degenerate actions in proportion to the neighbours they lie between and has a high-probability √n bound. It corrects Bartók et al.’s T^2/3 lower-bound proof, whose separating direction ignored the degenerate actions’ signals. The preprint, not the published text, also says the earlier localisation argument exchanged an expectation and a maximum. RelExp3 gives point-locally observable games an asymptotic constant depending only on K_loc, F and log K, and a factor linear in F is shown to be necessary. | Read |
| NOTE-1164 v2 | Bartók, Foster, Pál, Rakhlin and Szepesvári — Partial monitoring: classification, regret bounds and algorithms | For finite partial-monitoring games the minimax regret takes exactly four rates: 0 with one non-dominated action, Θ̃(√T) when every pair of neighbouring actions is locally observable, Θ(T^2/3) when the game is globally but not locally observable, and Θ(T) otherwise. The conditions are linear algebra on loss and signal matrices: a loss difference must lie in the span of the row spaces of the signal matrices of the actions allowed to estimate it. The stochastic classification covers every game; the adversarial one covers non-degenerate games only. | Read |
| NOTE-1173 | Olsson et al. — In-context learning and induction heads | In 34 transformer language models, in-context learning (loss at token 500 minus loss at token 50) appears abruptly in one early window of training, together with induction heads, the only non-convex bump in the loss curve and a turn in the models’ per-token-loss trajectory; one-layer models show none of it. Letting one layer express induction (smeared keys) moves the jump, and ablating induction heads removes nearly all in-context learning in small attention-only models. The case is causal for small attention-only models and correlational or by analogy for large models with MLPs, as the authors grade it themselves. | Read |
| NOTE-1177 | Musat, Pimentel, Zucchet and Hofmann — Invariant learning dynamics of transformers in inductive reasoning tasks | For a class of “block-list” next-token tasks that includes associative recall, k-hop induction and in-context n-grams, population gradient descent keeps an attention-only transformer’s merged key–query and output weights in a subspace fixed by the data’s token-relabelling and position-shift symmetries, whose coordinates are elementary actions (“attend to the previous position”, “read the token retrieved by head 1”). On it, a saturated in-weights circuit suppresses the in-context circuit’s gradient by the fraction of data it does not solve, burstiness multiplies that gradient, initialization decides which of several induction circuits wins, and projecting a trained model onto the coordinates recovers its circuit, with “aiding” directions a head-level analysis would miss. | Read |
| NOTE-1188 | Wang, Hoogland, van Wingerden, Furman and Murfet — Refined local learning coefficients of attention heads | Restricts the local learning coefficient, singular learning theory’s measure of how degenerate the loss is near a parameter, to one component’s weights (weight-refined) or to another data distribution (data-refined), and tracks it per attention head over the training of a two-layer attention-only transformer. The heads’ curves start alike and diverge, and cluster by the heads’ functional types; refinement to code separates the two induction heads; refinement to a one-layer model’s outputs locates layer-0 heads giving up simple n-grams as a circuit with layer-1 bracket-matching heads forms. One model, one run in the main text, three more seeds in an appendix. | Read |
| NOTE-1225 | Spivak — Compositional dynamics in learning and mechanics | A category-theoretic syntax, the operad ArrSm of “smooth adaptive arrangements” (a responsive parameter space, a lens of output and input maps between manifolds, and a real potential), with two functorial semantics into polynomial coalgebras, i.e. discrete-time input-output machines. They differ only in the integrator: Φconf stores position and takes a descent step, Φphase stores position and momentum and takes a symplectic-Euler step. Φconf turns a parameterized map plus a loss into gradient descent with backpropagation, and a closed system with inverse-Hessian response into Newton’s method. One arrangement of harmonic particles on a finite directed graph gives the discrete wave equation under Φphase and the discrete heat equation under Φconf, both governed by the symmetrized graph Laplacian. The main technical result is lens internalization, a lax symmetric monoidal functor Lens_C → C. | Read |
| NOTE-1363 | Fedus, Zoph and Shazeer — Switch Transformers | Routing each token to one expert (top-1, “switch” routing) with a fixed per-expert capacity, a load-balancing auxiliary loss α·N·Σ f_i P_i (α = 10⁻²), router computation in float32 inside bfloat16 training, a tenfold smaller initialization and higher dropout inside experts lets sparse Transformers train stably. At equal FLOPs per token on C4, Switch-Base with 64 experts reaches T5-Base’s quality about 7 times faster in wall-clock time, gains hold on most fine-tuning tasks and all 101 mC4 languages, and a 1.6-trillion-parameter model is trained. The paper reports the gains; it does not study what experts specialize in. | Read |
| NOTE-1367 | Chizat and Bach — Global convergence of gradient descent for over-parameterized models using optimal transport | Training a sum of many units by gradient descent is, as the number of units grows, a Wasserstein gradient flow of a convex functional of the measure over unit parameters. A measure is a global minimizer exactly when the first variation F′(µ) is nonnegative everywhere and zero on its support. Under 2-homogeneity or partial 1-homogeneity, and an initialization whose support separates the domain, any limit of the flow is global, because mass in any region where F′ < 0 grows exponentially. The result is conditional on convergence and non-quantitative. | Read |
| NOTE-1368 | Power et al. — What can ecosystems learn? | In a competitive Lotka–Volterra community where individual selection lowers the competitive effect ω_ij of species j on species i at a rate proportional to x_i x_j, and a normalising trade-off holds each row and column sum of ω fixed, interactions change as Hebbian learning does. In simulation (400 species, symmetric ω) the community comes to hold attractors for two past forcing patterns, completes them from fragments and switches with hysteresis. The memory needs the imposed trade-off, and in the long run it degrades. | Read |
| NOTE-1380 | Li, Lin, Duan, Liang and Shroff — Theory on mixture-of-experts in continual learning | In a stylized continual-learning model, overparameterized linear regression tasks drawn from N ground truths, each carrying a feature signal a linear gate can read, a top-1 MoE whose gate is trained on a “locality” loss plus a Switch-style balancing loss sorts its experts into one set per task (or task cluster) within about M/η rounds. If gate training continues, the balancing loss eventually erases the gaps between experts’ gate outputs and routing goes wrong; stopping it once the gaps settle keeps specialization, and noise then spreads load within each set. Forgetting then decays as 1/t, and more experts only lengthen exploration. | Read |
| NOTE-1388 | Wang, Gao, Zhao, Sun and Dai — Auxiliary-loss-free load balancing for mixture-of-experts | Adds a per-expert bias b_i to the routing scores used only for top-K selection, not for the gate weights, and after each batch moves b_i by u·sign(mean load − load_i), so overloaded experts are selected less. On DeepSeekMoE-style models of 1B and 3B parameters trained on 100B and 200B tokens it gives slightly lower validation perplexity (9.50 vs 9.56; 7.92 vs 7.97) and much lower global load violation (0.04 vs 0.72 and 0.52) than an auxiliary loss with α = 0.001, one run each. Expert Choice routing is excluded because it leaks future tokens. | Read |
| NOTE-1462 | Chen, Lau, Mendel, Wei & Murfet — dynamical versus Bayesian transitions in TMS | In Elhage et al.’s toy model of superposition with two hidden dimensions, regular k-gons are critical points of a closed-form population loss, and their local learning coefficients predict, through the free energy formula, a Bayesian phase transition from the 5-gon to the 6-gon near n = 600 that MCMC confirms. SGD trajectories plateau at the same critical points and move to lower loss and higher estimated complexity. The paper’s Bayesian antecedent hypothesis is one-directional, that training’s transitions have Bayesian counterparts; it says outright that there is “no necessary relation” between the two kinds, and its main Bayesian transition, 5 → 6, was never seen in training. | Skimmed |
| NOTE-1466 | Saligrama — information before commitment in safe adaptive control | A safe adaptive controller must stay safe under every model it has not ruled out. Its first action that leaves no safe continuation under an alternative is a commitment, and the evidence for it must be in hand before the action: what that action reveals comes too late. With the information gathered before commitment measured as a KL divergence between stopped records, a data-processing argument bounds any uniformly safe policy’s regret below by the cost of not committing with probability ½e^{−I_pre} − α. So bounded pre-commitment information leaves a fixed fraction of the oracle gap, and a linear gap gives linear regret. Safe recovery at O(√(T log T)) is proved when a safe experiment is repeatable, informative and returns to a common state. | Read |
| NOTE-1467 | Hennick & De Baerdemacker — Almost Bayesian | Models late-training SGD as sub-diffusion on a “porous” loss landscape, with the local learning coefficient as the medium’s fractal dimension and a spectral dimension d_s fitted from displacement, R(t) ∝ t^(d_s/2λ). Where an effective scalar diffusion coefficient D_ξ is constant on a region, the steady state there is exp(−L/D_ξ), which is the Bayesian posterior tempered to an effective sample size 1/D_ξ. That within-region statement is all the derivation gives: how mass is shared between regions, which is where “accessibility” would act, is not derived, and in the one test it is fitted through a length scale. Displacement exponents are measured on MNIST MLPs, TinyStories models and ImageNet convnets. | Read |
| NOTE-1469 | Richens, Abel, Bellot & Everitt — general agents contain world models | In a fully observed, finite, communicating, stationary controlled Markov process, a deterministic goal-conditioned policy whose success probability is within a factor 1 − δ of optimal for every composite goal of depth up to n determines every transition probability to within √(2P(1−P)/((n−1)(1−δ))), and the estimate is computed from the policy alone, by asking it to choose between “at most k successes of this transition in n tries” and “more than k”. An optimal myopic policy determines nothing. “Contains a world model” means exactly this: the transition function is recoverable from the input-output map. The authors say it shows “the existence of a world model encoded in the agent’s policy, not its specific use”, and the recovery map runs from the policy, not the activations, so it holds of any implementation of the same map, a lookup table over histories and goals included. | Read |
| NOTE-1470 | Teoh — Multi-token prediction done right | The cross-entropy gradient of a multi-token-prediction head, taken at its hidden state under a shared output head, is exactly a forward-KL self-distillation gradient toward the model’s own position-aligned next-token prediction plus the next-token cross-entropy gradient at the aligned state; a straight-through routing removes the second from the heads and trunk at no cost, and at 167M–1.2B this improves next-token loss, speculative decoding and zero-shot accuracy by small margins in single runs. In the main (DeepSeek-style) experiments the student head sees the same tokens as its teacher, so the decomposition is not an information projection. | Read |
| NOTE-1471 | Wu, Yang & Sun — Self-training: denoising vs. signal forgetting | In overparameterized linear regression, iterating self-training with fresh covariates, noiseless pseudo-labels and minimum-norm students multiplies the estimate by a fresh random orthogonal projection each round. Noise inherited from the first fit decays geometrically; signal along a direction of variance s decays at the slower rate s/(s + τ). Risk is therefore U-shaped when the covariance is anisotropic, monotone when it is isotropic, and tends to the risk of predicting zero. Each student fits its teacher exactly on its own sample while losing the teacher’s function elsewhere. | Read |
| NOTE-1473 | Mandt, Hoffman & Blei — variational analysis of constant SGD | The first version of Mandt, Hoffman and Blei’s argument: constant-rate SGD as an Ornstein–Uhlenbeck process near a non-degenerate optimum, whose Gaussian stationary distribution can be fitted to a Gaussian posterior by choosing the rate, batch size and preconditioner, with SGFS analysed the same way and a variational EM scheme for hyperparameters. Every result reappears, with the same numbers, in the 2017 JMLR paper, which adds momentum, constant-rate SGLD and iterate averaging; this one has nothing the later one lacks. | Read |
| NOTE-1475 | Mandt, Hoffman & Blei — SGD as approximate Bayesian inference | Constant-rate SGD, modelled near a minimum with positive-definite Hessian A and constant gradient-noise covariance BBᵀ as an Ornstein–Uhlenbeck process, has a Gaussian stationary distribution with covariance solving AΣ + ΣA = (ε/S)BBᵀ. Choosing the rate, batch and preconditioner to minimise KL to the Gaussian posterior gives closed forms, and the preconditioner (2S/εN)(BBᵀ)⁻¹ matches the posterior at sample size N exactly. The paper is about the stationary regime of a regular model in one basin: it sets the search phase aside, and nothing in it relates training time to sample size beyond iterate averaging, whose covariance falls as 1/(examples processed). | Read |
| NOTE-1478 | Mobahi, Farajtabar & Bartlett — Self-distillation amplifies regularization | For ℓ2-regularized regression in a Hilbert space with a fixed training-error tolerance, refitting to one’s own predictions on the same inputs multiplies the labels’ eigencomponents by d_k/(c_t + d_k), where the multiplier c_t must grow as the labels shrink. Rounds therefore amplify regularization, relatively suppress small-eigenvalue components and collapse the solution to zero after finitely many rounds. A few rounds can help and more hurt, which ResNet and VGG runs on CIFAR echo by fractions of a point. The loss comes from the regularizer, not from any information withheld from the student. | Read |
| NOTE-1479 | Hossain, Kousar & Tourni — Overcoming scaling limits in on-policy self-distillation | On-policy self-distillation from a privileged-context teacher does most of its supervising on failed student trajectories, where the teacher’s advantage depends on the reference the student cannot see; Proposition 1 gives the forward-KL optimum as the context-averaged teacher with the conditional mutual information as irreducible loss. Restricting supervision to verified on-policy trajectories and using the student’s own failed attempt as the teacher’s context keeps the gain over the base model at 3.2–3.8 points from 1.7B to 8B, where standard OPSD’s falls to 0.14, in single runs. The trained objective clips each vocabulary entry and is not a forward KL. | Read |