Michael Mahoney

Life and career

Michael Mahoney came to machine learning from statistical physics, and that origin explains almost everything distinctive about him — including the fact that when the rest of the field was arguing about deep learning generalization from a learning-theory standpoint, he was looking at the eigenvalue distributions of trained weight matrices and recognizing the shapes from random matrix theory and the physics of strongly correlated systems.

His doctorate is in physics, from Yale, in computational and theoretical statistical mechanics — work on molecular models of water, of all things, which sounds like an unrelated life until you notice what it trains you to do: handle enormous systems where you cannot compute the exact answer, extract the right coarse-grained summary, and reason about which fluctuations matter. He moved into applied mathematics and theoretical computer science, spent time at Yahoo Research during the period when web-scale data was forcing algorithmic questions nobody had needed to ask, and held a position at Stanford before settling at the University of California, Berkeley, where he is affiliated with the International Computer Science Institute, the statistics department, and Lawrence Berkeley National Laboratory. At Berkeley Lab he leads work on machine learning for scientific computing, which keeps him honest about scale: the matrices in a climate simulation or a genomics pipeline do not fit in memory, and no amount of theoretical elegance changes that.

The intellectual arc has three phases, and they are recognizably the same person each time. First, randomized numerical linear algebra: how to compute good approximate answers to enormous matrix problems by looking at a small random piece. Second, the empirical structure of large networks, where he and collaborators produced results that annoyed a lot of people by showing that the thing everyone assumed was there — large, well-separated communities — mostly is not. Third, the spectral analysis of deep neural networks, where he and Charles Martin argued that the weight matrices of well-trained networks develop heavy-tailed spectra, and that this is diagnostic.

What ties them together is a physicist's question: what does the spectrum tell you? Not what does the bound say, or what does the algorithm guarantee, but what is the empirical distribution of the eigenvalues actually doing, and what does that imply about the system?

Key contributions

**Randomized numerical linear algebra.** The founding problem: you have an m × n matrix too large to decompose, or even to read more than a couple of times. You want its dominant subspace, or a good low-rank approximation, or a least-squares solution. Mahoney, working extensively with Petros Drineas, built the theory of doing this by random sampling and sketching, with provable error guarantees.

The core insight is that **not all rows are equally important**, and the right notion of importance is **statistical leverage**. For a matrix A with thin SVD A = UΣVᵀ, the leverage score of row i is the squared norm of the i-th row of U — the same quantity regression diagnostics have used for decades to identify influential observations. Sampling rows in proportion to leverage scores, rather than uniformly, gives relative-error approximation guarantees where uniform sampling gives only additive-error ones, and the difference is enormous when the matrix has a few structurally important rows. Their work then showed how to *approximate leverage scores fast*, which is the practical crux — computing them exactly requires the SVD you were trying to avoid.

This machinery produced a family of results: fast approximate matrix multiplication with additive error bounds; randomized low-rank approximation via sketching (multiply by a random test matrix, compute an orthonormal basis for the resulting range, project, decompose the small matrix); and randomized least-squares solvers that beat classical direct methods on large overdetermined systems by preconditioning with a sketch.

**CUR decompositions.** A distinctively Mahoney contribution, motivated by interpretability. The SVD gives you optimal low-rank approximation, but its factors are dense linear combinations of everything — in a genomics matrix, a singular vector is a weighted mixture of all twenty thousand genes and means nothing to a biologist. A **CUR decomposition** approximates A ≈ CUR where C is a subset of *actual columns* of A and R a subset of *actual rows*, chosen by leverage-score sampling, with U a small connecting matrix. You lose a little approximation quality and you gain factors that are real genes and real patients. This is one of the clearest cases in the literature of a method designed around what a domain scientist can interpret.

**The structure of large networks.** With Jure Leskovec, Kevin Lang, and Anirban Dasgupta, Mahoney conducted a large empirical study of community structure across many real social and information networks, introducing the **network community profile plot**: for each size scale, the best achievable conductance of a set of that size. The finding was uncomfortable and important. Real networks have excellent small communities — up to roughly a hundred nodes — and above that scale the best communities steadily get worse, until the best "community" of size n/2 is barely better than a random cut. The picture is not a hierarchy of nested modules but a core-periphery structure with good small pieces hanging off a large expander-like core. A great deal of community-detection methodology had implicitly assumed otherwise.

**Implicit regularization.** Related and characteristic: Mahoney and Lorenzo Orecchia showed that approximate graph algorithms — truncated diffusions, early-stopped power iterations, approximate PageRank — are not merely fast approximations to an exact spectral computation. They are *exactly* solving a different, regularized optimization problem. The approximation is the regularization. This reframes a large amount of practical algorithmic folklore ("run it a few iterations, it works better") as principled, and generalizes to the observation that computational shortcuts often implicitly encode statistical assumptions.

**Heavy-tailed self-regularization in neural networks.** With Charles Martin, an empirical program on the weight matrices of trained deep networks. Fit the empirical spectral density of each layer's weight matrix and ask what random-matrix universality class it resembles. Poorly trained or under-regularized networks look close to Marchenko-Pastur, the random-matrix null. Well-trained networks develop pronounced heavy tails, with power-law exponents that correlate with test performance. The striking practical claim is that you can predict a model's relative quality **from the weights alone**, without any test data — a capability they packaged into a tool and validated across hundreds of publicly available pretrained models.

**Second-order optimization at scale.** A further line applies the same sampling philosophy to optimization: sub-sampled Newton methods with convergence guarantees, and practical tools for computing and using Hessian information in deep networks.

In battle

Mahoney's profile is a scale specialist's: mean 36.0, median 27, six problems above 80, with `networks` at 69.0, `high-dim` at 65.8 across fifteen problems, and `optimization` at 54.8.

**P044 — Sketch the enormous matrix** at 97 is his own research program handed back to him — random test matrices, a few passes, dominant subspace from the sketch, with the additive- and relative-error guarantees the problem demands, worked on out-of-core scientific data rather than toy matrices. He beats Candès (86) here, and the reason is the right one: Candès has the recovery theorems, Mahoney has the sketching algorithms and the survey that codified them.

**P279 — Squash the dimensions, keep the distances** (92) is Johnson-Lindenstrauss and random projection, the primitive underneath everything he does. **P287 — The router's memory is smaller than its traffic** (90) is streaming and sketching under a memory bound — note that Partha Niyogi scores 8 on this same problem, a good illustration of how sharply the roster separates geometry-of-data from algorithms-under-constraint. **P286 — The interpolator that should have failed** (85) puts him second to Bartlett's 96, and legitimately so: the spectral view of why overparameterized models generalize is one of the two live accounts, and it is his. **P273 — Cut the image, weight the graph** (80) and **P282 — The eigenvalues are lying** (79) are spectral methods and random matrix theory. **P290 — Anonymous, except for everything about you** (80) is re-identification, where the relevant fact is that high-dimensional records are almost surely unique. **P097 — Does your pipeline reproduce?** (78) puts him respectably behind Bin Yu's 99.

`systems` at 45.0 is unusually high for this cohort and is earned — he has actually run these methods on real out-of-core data at a national lab, and the game credits that.

The weaknesses form a clean pattern: symbolic, linguistic, and discrete-logical problems, where there is no matrix to sketch. **P195 — Let the machine find the proof** at 6 is automated theorem proving — continuous linear algebra offers nothing to symbolic proof search. **P083 — The grammar beneath the sentence** (8) is formal language theory, **P255 — Translate Russian by machine** (8) and **P256 — The parallel text is the teacher** (8) are machine translation, and `nlp` at 18.7 across eighteen problems is the largest and weakest block he carries. **P143 — The coefficient that flips sign** (7) is causal confounding, with `causality` at 21.0. **P155 — Three machines, one class** (8) is a computability-hierarchy problem, and `computability` sits at 14.0.

His battle identity is exact: he wins massive matrix computations by sampling smartly, and loses exact-answer demands where approximation is forbidden. That is the real limit. Every guarantee he has is of the form "with high probability, within ε" — which is the right answer for a terabyte matrix and the wrong answer for a proof, a protocol, or a compiler.