Nathan Srebro

Life and career

If you want to know what a modern learning theorist's career looks like, Nathan Srebro's is close to the canonical example. He was educated at MIT, where he took his doctorate in the early 2000s working on machine learning with matrix factorizations — a thesis that turned out to be extraordinarily well-timed, arriving just as recommender systems were about to become the most commercially visible application of statistical learning in the world. He did postdoctoral work in Toronto in Geoffrey Hinton's orbit, at a moment when neural networks were deeply unfashionable and the people still working on them were a small community, and then settled at the Toyota Technological Institute at Chicago, the small research institute embedded on the University of Chicago campus, where he holds a professorship with a joint appointment in the university's computer science department.

TTIC is an unusual institution — a handful of faculty, no undergraduates, funded to do fundamental machine learning — and it suits him. Srebro's output has the character of someone with time to think about the same question from many angles over fifteen years. That question, stated at its most general, is: *why does a learning algorithm generalize?* Not "what is the capacity of this hypothesis class" in the abstract Vapnik–Chervonenkis sense, but the sharper and more uncomfortable version — given that the models we actually fit have far more parameters than data, and given that they interpolate the training set exactly, what is the thing that is being controlled?

He has been an unusually productive advisor, and a lot of his most cited work carries a student's name first: Behnam Neyshabur on implicit regularization and path norms, Suriya Gunasekar on implicit bias in matrix factorization and linear networks, Daniel Soudry and collaborators on the implicit bias of gradient descent. His collaborations with Shai Shalev-Shwartz and Ohad Shamir on stochastic optimization and learnability form a second major thread. And with Moritz Hardt and Eric Price he co-authored one of the papers that gave algorithmic fairness its working technical vocabulary. He is, in the taxonomy of the field, a theorist — but a theorist whose theorems keep turning out to be about things practitioners are already doing and cannot explain.

Key contributions

**Maximum-margin matrix factorization and the trace norm.** With Jason Rennie and Tommi Jaakkola, Srebro proposed replacing the hard rank constraint in collaborative filtering with a convex surrogate: penalize the trace norm (nuclear norm, the sum of singular values) of the predicted matrix rather than fixing its rank. This is the matrix analogue of the lasso's relaxation of the L0 penalty to L1, and it does the same work — it converts an intractable non-convex problem into a semidefinite program while still inducing low-rank solutions. He paired this with generalization bounds: the trace norm, not the rank, is the quantity that controls how well a factorization learned from a sparsely observed matrix will predict the unobserved entries. That reframing — *the norm is the complexity measure, not the parameter count* — is the seed of everything he did later.

**Implicit regularization and implicit bias.** The central modern contribution. In heavily overparameterized models, the training objective has an enormous set of global minima that all fit the data perfectly; the algorithm chooses among them, and that choice *is* the inductive bias. Srebro's group made this precise in several settings. In the paper with Neyshabur and Tomioka, they argued that the effective complexity control in deep networks is norm-based rather than size-based, and introduced path norms as a scale-invariant measure suited to ReLU networks. With Soudry, Hoffer, Nacson, Gunasekar and others, they proved the cleanest result in this line: gradient descent on logistic loss with separable data has iterates whose *direction* converges to the maximum-margin separator — extremely slowly, logarithmically, which is why continuing to train long after the training error hits zero keeps improving test error. With Gunasekar, they showed that gradient descent on matrix factorization problems, from small initialization, converges toward the minimum-nuclear-norm solution: the trace-norm regularizer he had once written down explicitly turned out to be what the optimizer was imposing on its own. For a graduate student this is the key conceptual takeaway: in the overparameterized regime, you cannot separate "optimization" from "regularization," because the optimizer's trajectory selects the estimator.

**Stochastic optimization and learnability.** With Shalev-Shwartz, Singer and Cotter he developed Pegasos, a primal stochastic sub-gradient method for SVMs whose runtime does not grow with dataset size — an early and influential argument that in the large-data regime you should optimize the objective loosely and the statistics will forgive you. With Shalev-Shwartz, Shamir and Sridharan he showed that in general stochastic convex optimization, uniform convergence can fail while learnability still holds, and that stability rather than capacity is the right characterization: a result that pulled apart two notions the field had treated as interchangeable.

**Equality of opportunity.** With Hardt and Price, he formalized fairness criteria for supervised classification in terms of a predictor's error rates conditional on the protected attribute — equalized odds, and its relaxation requiring equal true-positive rates across groups — along with a post-processing construction that derives a fair predictor from any existing score. The paper's contribution was as much conceptual as technical: it showed that "fair" is not one thing, that plausible criteria conflict, and that the choice is a modeling decision to be argued for explicitly.

In battle

Srebro's sheet reads exactly like a theorist's: mean 35.1 with a median of 30, five dominant problems, and a long tail of thirty-four problems at or below 20. He is not broadly useful; he is devastating in a narrow band and nearly inert outside it.

The two 92s are the band's center. "The matrix with 99% holes" is the Netflix-Prize matrix-completion problem, which is his dissertation's subject matter; he formalized the low-rank assumption, connected it to generalization through matrix norms, and reasoned about which observation patterns permit recovery. He sits just below Candès there only because the exact-recovery guarantees under incoherence were pushed further in the Candès–Recht line. "The interpolator that should have failed" is the double-descent/benign-overfitting puzzle, and it is the problem his entire second career was built to answer — implicit bias is the reason a model with more parameters than data does not simply memorize noise. Around those, "Prove the descent" (83) is convergence analysis for gradient methods, "What can be learned at all?" (80) is learnability characterization where his stability-versus-uniform-convergence work lives, "Learn from the stream, one at a time" (78) is online/stochastic optimization, "The line between two clouds" (76) is max-margin classification, and "Sketch the enormous matrix" (76) is randomized low-rank approximation — an adjacent but genuinely connected literature. His best categories follow: high-dimensional problems at 50.1 across eleven, optimization at 46.3 across nine, classification at 43.6 across sixteen.

The failures are total and they are all of one kind: problems whose substance is *discrete, linguistic, or historical* rather than continuous and geometric. "The spam in the inbox" (6) is naive Bayes with Laplace smoothing over word counts — a technique with no relationship to anything he has written. "The grammar beneath the sentence" (8) is syntactic structure; "Who wrote the disputed papers?" (10) is Bayesian authorship attribution; "The document that links anywhere" (10) is PageRank-era link analysis. "Roll the dice at Los Alamos" (9) is the birth of Monte Carlo, and "Regression when the outcome is censored" (9) is classical econometric survival/Tobit modeling — two mid-century statistical traditions he simply does not intersect. His NLP average of 20.9 across twelve problems and search average of 14.0 are the reliable places to beat him.

Two things to watch. First, his perception average is only 24.2 across thirteen problems, which surprises people who know he works on deep learning — the game is scoring *whose toolkit built the answer*, and vision architectures are not his. Second, his fairness average of 40.0 arguably undersells the real record, since he is a co-author of equalized odds; on the specific fairness problems drawn here, the carriers whose whole program is fairness edge him out. Read that as a lesson about the matrix: it rewards the person who owns the method the problem is asking for, not the person with the most impressive adjacent CV.