Robert Nowak

Life and career

Most of machine learning assumes the data has already arrived. Robert Nowak has built a career on the prior question: given that measurements cost something — a photon, a blood draw, a probe packet, an hour of a human labeler's time — which measurements should you take? That question has a different shape in every field it appears in, and Nowak has followed it through signal processing, networking, statistics, biology, and crowdsourcing without ever quite leaving it.

He is an electrical engineer by training, with all three degrees from the University of Wisconsin-Madison, and the engineering formation is the key to reading him. He thinks in terms of sensing systems, measurement budgets, and inverse problems, and he brought that framing into machine learning at a moment when the field was mostly thinking about fixed datasets. After early faculty appointments including a period at Michigan State, he spent several formative years at Rice University, where the signal processing group — Richard Baraniuk's orbit — was becoming one of the epicenters of what would shortly be called compressed sensing. He then returned to Wisconsin, where he has been a chaired professor in electrical and computer engineering ever since, with strong ties to Wisconsin's statistics and computer sciences departments and its optimization community.

Wisconsin suited him. It is a place where the boundary between engineering and statistics is unusually porous, and Nowak's work has always needed both: an engineer's willingness to design the experiment and a statistician's insistence on knowing what the resulting estimate is worth. His group has produced a long line of students who now hold faculty positions across the active-learning and bandit literature.

A recurring feature of his research is that it lands in genuinely applied settings without being watered down. He worked on photon-limited imaging, where the measurements are literally counted photons and the noise is Poisson, for medical and astronomical instruments. He worked on internet tomography for network operators who could not instrument the interior of the network they were responsible for. He built systems for adaptive data collection from crowdsourced human judgments, used to gather comparison and similarity data efficiently for psychology and machine learning experiments. In each case the theory came with a working method.

Key contributions

**Network tomography.** Suppose you can send and receive packets at the edges of a network but cannot instrument its interior — no access to the routers, no cooperation from the operators in between. What can you learn about internal link loss rates, delay distributions, and topology from correlations among end-to-end measurements? Nowak, with Mark Coates, Rui Castro, Michael Rabbat and others, developed this into a coherent inverse-problem theory in the early 2000s. Multicast probes sent to multiple receivers share a path prefix, so their loss events are correlated in a way that identifies where on the tree the loss occurred; unicast probe pairs sent back to back can be made to approximate the same effect. The theory characterizes which internal parameters are identifiable from which measurement patterns, which are irretrievably confounded, and how to design the probing scheme to maximize information under a traffic budget. This is the purest statement of the Nowak question: the interior is unobservable, so choose your exterior measurements well.

**Active learning theory.** In passive learning, examples arrive labeled at random and the excess risk decays polynomially in the sample size. In active learning, you choose which points to have labeled. Nowak's work with Rui Castro established **minimax rates for active learning**, characterizing precisely when adaptive querying yields a genuine improvement — including regimes where label complexity drops exponentially — and when it does not. The determining factor is the geometry of the decision boundary and the noise level near it: with clean boundaries you can binary-search your way to the answer, and with heavy noise near the boundary you have to pay repeatedly for the same information. He also developed **generalized binary search** for learning from noisy queries, giving algorithms and bounds for the general case where each query is a noisy test rather than a clean bisection.

**Sparse recovery and adaptive sensing.** Nowak contributed to the sparse-recovery literature both on the algorithmic side and on the design side. His work on **distilled sensing**, with Jarvis Haupt and Castro, made a striking point: if you can allocate your sensing budget sequentially rather than all at once, you can detect and localize far weaker sparse signals than any non-adaptive scheme can. The mechanism is refinement — spend a fraction of the budget coarsely, discard the locations that look empty, and concentrate the remaining budget on the survivors, iterating. The gain over non-adaptive sensing is not constant-factor; it changes the achievable signal-to-noise threshold.

**Poisson inverse problems and multiscale methods.** In photon-limited imaging, the data are counts, often very small counts, and Gaussian noise models are simply wrong. Nowak developed multiscale, wavelet-domain methods tailored to Poisson likelihoods — including multiscale partition-based estimators that adapt their resolution to the local photon flux — for applications in medical imaging and astronomy where you cannot simply collect more light.

**Group testing.** The problem of identifying a few infected samples among many by pooling — testing mixtures rather than individuals — is a combinatorial-statistical problem with a long history, and Nowak's contributions concern the adaptive and noisy versions: how many pooled tests are needed, how sequential designs beat one-shot designs, and what the information-theoretic limits are.

**Pure-exploration bandits and adaptive data collection.** With Kevin Jamieson and others he worked on best-arm identification — the version of the bandit problem where you are not accumulating reward but trying to find the best option with as few samples as possible — producing algorithms with near-optimal sample complexity based on the law of the iterated logarithm. This theory was deployed in systems for adaptive collection of human judgments, where each query costs a person's attention and the sequence of queries should depend on what has been learned so far.

In battle

Nowak's profile is that of a hard specialist with an unusually clean signature: mean 34.4, four dominant problems, and a category table with `networks` at 87.0 towering over everything else.

**P276 — X-ray the network from its edges** at 98 is the reason for that 87.0, and it is not an analogy — it is the field he helped found. Infer the internals of a network from correlated end-to-end measurements between controllable endpoints, characterize what is identifiable and what is confounded, and design the probing pattern to extract the most under a budget: that is network tomography, and the year the problem is set in is the year he was publishing on it.

**P285 — Test the many with the blood of few** at 90 is adaptive group testing, and **P063 — The two slot machines** at 85 is pure-exploration bandits — both direct hits. **P018 — p = 20,000, n = 200** at 81 is sparse recovery in the p ≫ n regime, where he will contend with Wainwright and Candès and land credibly among them. **P274 — A hundred sensors for a city's water** (76) is sensor placement, **P094 — Reconstruct from too few measurements** (70) is compressed sensing proper — a good score that will nonetheless lose decisively to Candès at 98 — **P020 — The smooth curve, honestly** (64) is nonparametric estimation, and **P234 — Where did every pixel go?** (60) draws on the photon-limited imaging work.

His secondary categories tell you where he is respectable rather than dominant: `high-dim` 51.7, `information` 47.5, `rl` 43.0 (bandits), `classification` 43.3, `experimental-design` 41.0, `perception` 31.4. That last figure is worth dwelling on — nineteen problems in `perception` and a mean of only 31.4, despite a career in imaging. The explanation is that his imaging work is about *reconstruction under a measurement constraint*, not about recognition or representation, and the game's perception problems are mostly the latter.

The losses are sharp. `games` at 10.0 is his floor category. **P246 — Small tools, loosely joined** (6) is Unix design. **P143 — The coefficient that flips sign** (8) is causal confounding — a weakness he shares with almost every engineer-trained figure on this roster. **P156 — Every interesting property is undecidable** (8) is Rice's theorem. **P205 — Auction the airwaves** (8) is mechanism design, which is instructive: spectrum auctions are an optimization-and-incentives problem, and having spent a career on wireless-adjacent signal processing buys nothing when the difficulty is strategic behavior. And **P255 — Translate Russian by machine** (8) and **P256 — The parallel text is the teacher** (8) are both machine translation, with `nlp` sitting at 18.1 across eighteen problems — the largest and weakest category he carries. Nowak has essentially no language-processing record, and the game does not pretend otherwise.

His battle identity puts it well: he wins label-scarce problems by choosing what to measure, and loses when queries are free and brute force is fine. That is the honest boundary. Adaptive sensing is a lever with a fulcrum — a measurement budget. Remove the budget and the lever does nothing.