Maroon: classical ML and numerical methods work list

[sigilante]

Summary

This is a work list for classical ML and numerical methods under Maroon, alongside the tinygrad/autodiff retarget in #85. It is simpler than the autodiff work, much of it runs on existing jets, and it gives #85 pieces it will need (gradient-descent optimizers, reductions along an axis, norms).

Where things go: linear algebra and solvers in Saloon (saloon/desk/lib/saloon.hoon); models and algorithms in Maroon; shared array primitives in Lagoon.

What already exists (2026-09-13)

• Lagoon:
  • Array and linear-algebra arms: mmul, dot, dotc, add/sub/mul/div, the *-scalar ops, argmax/argmin, max/min, cumsum, prod, stack/hstack/vstack, transpose, diag, trace, reshape, submatrix.
  • Most of the basic vector arms are jetted, including mmul (SoftBLAS gemm) and add (axpy).
• Saloon:
  • Symmetric Jacobi eig/eigvals/eigvecs and Hermitian eig-herm.
  • Elementwise transcendentals: exp, log, sqrt, pow, and others.
  • fill-uniform, fill-normal, fill-expon.
  • Only one Saloon arm carries a jet hint, so eig runs as plain Hoon.
• librand: shuffle, permutation, choice/choices, sample-n, reservoir, categorical, normal, normal-mv, dirichlet, bernoulli, gamma/beta/chi2/student-t, poisson, binomial. This is enough for k-means++ seeding, bootstrap sampling, minibatch shuffling, and mixture-model initialization.
• Missing:
  • Lagoon: reductions along an axis, broadcasting, norms, sort/argsort, pairwise distances.
  • Saloon: LU, QR, Cholesky, solve, inv, det, least squares, SVD, conjugate gradient.

Design rules

1. Build every algorithm from whole-array Lagoon operations. Never write a Hoon loop over individual elements. Measured with sdblas gemm, jetted kernels run at about 4 ns per float op (about 250M ops/s on one core). The scalar benchmarks in this repo show per-element unjetted Hoon about 250× slower than jetted.
   • Example: pairwise squared distances as ‖x‖² + ‖y‖² − 2·X·Yᵀ is a single jetted mmul, not an n² loop.
2. Every iterative method takes a hard iteration cap as well as a tolerance, so a directed rounding mode cannot keep it from terminating. Return the iteration count and the final residual.
3. Determinism: randomized algorithms take an explicit librand generator, never a hidden seed, so the same seed gives the same model on vere and NockVM.
4. Tests: check each algorithm against NumPy/SciPy/scikit-learn reference values within a tolerance, plus exact-result tests where the answer is exact (integer-valued systems, identity inputs).
5. Kinds: target %i754 first. Consider %unum/%fixp only where they come cheaply through fun-scalar.

Work list

1. Lagoon foundation

• Sum, mean, variance and standard deviation along an axis (dim=@ud), plus full reductions
• Min, max, argmin and argmax along an axis
• Norms: L1, L2, L∞, Frobenius, along an axis or over the whole array
• Broadcasting for elementwise binary ops (NumPy rules), or at least a row/column broadcast add/sub/mul
• Sort, argsort and top-k (along an axis)
• Pairwise squared-distance matrix via mmul
• Jets for the hot ones: reductions along an axis, norms, pairwise distances (C and NockVM)

2. Saloon linear algebra

• Conjugate gradient for symmetric positive-definite systems: one mmul, two dots and a few scaled adds per iteration, all jetted today. Do this first to prove the vectorized pattern.
• Preconditioned CG, with the Jacobi (diagonal) preconditioner
• Cholesky factorization, with triangular forward and back solves
• LU with partial pivoting, giving solve, inv and det
• Householder QR, giving least squares
• One-sided Jacobi SVD, reusing eig's column-rotation machinery (rot-cols)
• Power iteration and Lanczos for leading eigenpairs of large sparse-ish problems (optional)

3. Maroon: models and algorithms

Unsupervised

• PCA: covariance plus the existing eig; later, SVD
• k-means (Lloyd) with k-means++ seeding via librand
• Gaussian mixture models via EM: k-means init, normal-mv, logsumexp
• Spectral clustering: graph Laplacian plus eig
• DBSCAN and agglomerative clustering from the pairwise distance matrix (small n)

Supervised

• Linear regression: normal equations via Cholesky, and least squares via QR
• Ridge regression: Cholesky, or CG on AᵀA + λI
• Logistic regression: gradient descent, or IRLS with a CG inner solve
• Linear SVM (Pegasos-style SGD)
• k-nearest neighbors (classification and regression)
• Gaussian naive Bayes
• Fisher LDA
• Decision trees, then random forests with bootstrap via librand

Optimization and time series

• Gradient-descent optimizers: SGD, momentum, Adam (shared with Maroon: audit, viability, and retarget to current tinygrad #85)
• Kalman filter: predict and update with mmul plus solve

Evaluation

• Metrics: MSE, MAE, R², accuracy, confusion matrix, log loss, silhouette score
• Utilities: train/test split and k-fold splits via librand shuffle, standardization

Suggested order

1. Conjugate gradient in Saloon
2. The Lagoon reductions along an axis, norms and pairwise distances, with jets
3. PCA and k-means++
4. Cholesky and QR, then linear and ridge regression
5. Gradient-descent optimizers, then logistic regression (feeds Maroon: audit, viability, and retarget to current tinygrad #85)
6. The rest of the models, in any order

Milestones

• M1: CG solves a 256×256 SPD system with all kernels jetted, and matches SciPy within tolerance.
• M2: k-means++ and PCA on Iris reproduce scikit-learn's clusters and components (up to label permutation and sign), with bit-identical results for the same seed on vere and NockVM.
• M3: Linear and logistic regression on a standard small dataset match scikit-learn coefficients within tolerance.

🤖 Generated with Claude Code

https://claude.ai/code/session_01TgBnKsUPYzkoPZonjePnaq