Monthly Archives: October 2008

Following the Perturbed Leader

Posted on by

I’m reading Cesa-Bianchi and Lugosi’s Prediction, Learning, and Games in more detail now, and in Chapter 4 they discuss randomized prediction and forecasting strategies. The basic idea is that nature has a sequence of states or outcomes (y_1, y_2, \ldots, y_n). You have a set of possible actions \{1, 2, \ldots, N\} to choose from at each time. If you choose action i at time t then you incur a loss \ell(i, y_t). After you choose your action the state of nature is revealed to you. The goal is to come up with a strategy for choosing actions at each time t, given the past states (y_1, \ldots, y_{t-1}).

One simple strategy that you might consider is to choose at time t to take the action i which would have resulted in the minimum loss so far:

I_t = \min_{i} \sum_{k=1}^{t-1} \ell(i, y_k).

This seems like a good idea at first glance but can easily be “fooled” by a bad state sequence (y_1, \ldots, y_n). This strategy is called fictitious play because you are pretending to play each action over the past and choosing the one which would have given you the best performance to date. Unfortunately, the strategy is not Hannan consistent, which loosely means that the gap between the average loss under this strategy and the average loss under the best fixed action does not go to 0.

So what to do? One option, proposed by Hannan, is to add noise to all of the empirical losses \sum_{k=1}^{t-1} \ell(i, y_k) and then choose the minimum of the noisy ones:

I_t = \min_{i} \sum_{k=1}^{t-1} \ell(i, y_k) + Z_{i,t}.

This strategy is Hannan consistent and is called follow the perturbed leader since the action you choose is the best action after a perturbation.

If you got this far, I bet you were thinking I’d make some comment on the election. We’ve been following a perturbed leader for a while now. So here is an exercise : how is this prediction model a bad model for politics?

Advertisement

prove as you go or scaffold first?

Posted on by

I had an interesting conversation two weeks ago about the working process for doing theory work in CS and EE. We discussed two extremes of working styles. In one, you meticulously prove small statements, type them up as you go along, getting the epsilons and deltas right and not working on the next step until the current step is totally set. I call this “prove as you go.” The other is that you sketch out some proofs to convince yourself that they are probably true (in some form) and then try to chase down the implications until you have the big result. When some deadline rolls around, you then build up the proofs for real. This could be thought of as “scaffolding first.” Fundamentally, these are internal modes of working, but because of the pressure to publish in CS and EE they end up influencing how people view theory work.

Continue reading →

conservative viewpoints in theater

Posted on by

The NY Times has an article about the puzzling lack of conservative playwrights. The lack of “fair and balanced” political perspectives in regional theaters and festivals is pretty clear, but the fact that interviewees couldn’t think of any contemporary conservative playwrights is a bit odd. I would argue that Neil LaBute is a little right of center — he addresses cultural politics and doesn’t construct paeans to Iraq war, though. I am thinking particularly of The Shape of Things.

I think a far bigger factor is the kind of resurgence and celebration of anti-intellectual and anti-“elitist” sentiment in the broader conservative movement. Going to see a play is definitely elitist, and the kind of Bill Buckley conservatives who would write theater are a bit rarer in the younger generation of playwrights. I’m surprised that some libertarian or objectivist playwright hasn’t popped up, but after reading Ayn Rand’s attempts at theater, it is tempting to think that the ideology doesn’t make for riveting drama.

Krugman on Interstellar Trade

Posted on by

While reading the comments over at Crooked Timber, I saw a link to one of our new Nobel Laureate Paul Krugman’s more insightful papers: The Theory of Interstellar Trade. The abstract reads:

This paper extends interplanetary trade theory to an interstellar setting. It is chiefly concerned with the following question: how should interest charges on goods in transit be computed when the goods travel at close to the speed of light? This is a problem because the time taken in transit will appear less to an observer travelling with the goods than to a stationary observer. A solution is derived from economic theory, and two useless but true theorems are proved.

a small point I noticed in the debate

Posted on by

A presidential debate is really another piece of theater, and so much is conveyed in the body language and tone of the participants. The first question last night came from Alan, an older white gentleman — McCain walked right up to the section, all but leaned on the railing, and talked to him, mano e mano. The second question is from Oliver, a young black man. In this case, McCain turns into story mode, a slight condescension with “you may not have heard of Fannie and Freddie.” He keeps a distance, he’s less direct.

What does that say to you?

UPDATE : I should replace “mano e mano” with “one on one.”