Blackwell’s proof of Wald’s identity

Every once in a while you come across a mathematical argument of such incredible beauty that you feel compelled to tell the whole world about it. This post is about one such gem: David Blackwell’s 1946 proof of Wald’s identity on the expected value of a randomly stopped random walk. In fact, even forty years after the publication of that paper, in a conversation with Morris DeGroot, Blackwell said: “That’s a paper I’m still very proud of. It just gives me pleasant feelings every time I think about it.”

ECE 299: regression with quadratic loss; stochastic simulation via Rademacher bootstrap

I gave the last lecture earlier today, wrapping up the semester. Here are the notes from the last two weeks:

• Regression with quadratic loss, mostly in reproducing kernel Hilbert spaces, with and without regularization.
• Case study: stochastic simulation via Rademacher bootstrap, where I discuss the work of Vladimir Koltchinskii et al. on efficient stopping algorithms for Monte Carlo stochastic simulation. The idea is to keep sampling until the empirical Rademacher average falls below a given threshold. Once that happens, you stop and compute a minimizer of the empirical risk. The work of Koltchinskii et al. was in turn inspired by the ideas of Mathukumalli Vidyasagar on the use of statistical learning theory in randomized algorithms for robust controller synthesis.

Monday’s lecture was on stochastic gradient descent as an alternative to batch empirical risk minimization. I will post the notes soon.

What have the Romans ever done for us?

In Alfréd Rényi‘s Dialogues on Mathematics, Archimedes says this to King Hieron:

… Mathematics rewards only those who are interested in it not only for its rewards but also for itself. Mathematics is like your daughter, Helena, who suspects every time a suitor appears that he is not really in love with her, but is only interested in her because he wants to be the king’s son-in-law. She wants a husband who loves her for her own beauty, wit and charm, and not for the wealth and power he an get by marrying her. Similarly, mathematics reveals its secrets only to those who approach it with pure love, for its own beauty. Of course, those who do this are also rewarded with results of practical importance. But if somebody asks at each step, “What can I get out of this?” he will not get far. You remember I told you that the Romans would never be really successful in applying mathematics. Well, now you can see why: they are too practical.

I couldn’t help but think of this little gem.