paper a day : an LP inequality for concentration of measure

A Linear Programming Inequality with Applications to Concentration of Measure
Leonid Kontorovich
ArXiV: math.FA/0610712

The name “linear programming” is a bit of a misnomer –it’s not that Kontorovich comes up with a linear program whose solution is a bound, but more that the inequality relates two different norms, and the calculation of one of them can be thought of as maximizing an inner product over a convex polytope, which can be solved as a linear program. This norm inequality is the central fact in the paper. There are two weighted norms on functions at work — one is defined via a recursion that looks a lot like the sum of martingale differences. The other is maximizing the inner product of the given function with functions in a polytope defined by the weights. All functions in the polytope have bounded Lipschitz coefficient. By upper bounding the latter norm with the former, he can apply the former to the Azuma/Hoeffding/McDiarmid inequalities that show measure concentration for functions with bounded Lipschitz coefficient.

On a more basic level, consider a function of many random variables. For example, the empirical mean is such a function. A bounded Lipschitz coefficient means they are “insensitive” to fluctuations in one value. This intuitively means that as we add more variables the function will not deviate from is mean value by very much. To show this, you need to bound a probability with the Lipschitz coefficient, which is exactly what this inequality is doing. Kontorovitch thereby obtains a generalization of the standard inequalities.

What I’m not sure about is how I would ever use this result, but that’s my problem, really. The nice thing about the paper is that it’s short, sweet, and to the point without being terse. That’s always a plus when you’re trying to learn something.


Hamlet : Blood In The Brain

I got a chance to see the new Naomi Iizuka play, Hamlet: Blood in the Brain at Intersection for the Arts (15th and Valencia). The production is a collaboration between Iizuka, Intersection, Campo Santo, and CalShakes, and took about 5 years of workshops and fora to come to its current form. The nice thing about going to Campo Santo productions is that they are really about process and it shows. This play is a recasting of the Hamlet story in a 1980’s Oakland devastated by the internecine conflicts between rival drug-dealers. In this story “H” (all characters are initials) stands in the shadow of his father, who was a “legend” and who dealt drugs all across Oakland. Rather than coming back from University, he comes back from the penitentiary and has to cope with the demands of his “uncle” C, who has taken over the business, has married H’s mother G, and who has Big Plans to expand his operation. The gangsta mythos and drama of the street struggle is an appropriate fit for the largeness of Shakespeare’s story, but Iizuka doesn’t really romanticize it. We are very much inside H’s mind the entire time, from his first line “the pounding… of a BASS” to the end, in which the poisoned chalice is done away with and instead we have a real Mexican standoff.

The play is another must-see. Like Love is a Dream House in Lorin, the play deals with local issues and problems, but the focus here is on the dissection of H’s turmoil. He is well and truly stuck here, as opposed to the kind of angsty playboy you see in some productions. To a degree he brings it on himself, but when you see C plans to have L kill H at a club in Oakland you understand the degree to which he is ensnared by business and blood and family and pride and honor. The feeling in intensified by the Chorus, which appears in all the club scenes, taunts H about his own inadequacies. We see it also when H meets L’s sister O near Lake Merritt and tells her that he wants to take her far away but in a later scene when she gets in his car he is paralyzed and cannot leave. Those who want a scene-by-scene adaptation should stay away. It’s more the Iizuka has taken Hamlet, knocked out everything but some posts, sifted through the detritus to find some nuggets, and then found a story in which those can be strategically placed. It’s in those changes that the indictment of the culture itself comes. There’s no reason for O to drown herself here — far better to have her killed in a driveby orchestrated by L himself, who is supposed to take out H.

As with every Campo Santo productions, the performances are huge and powerful. Sean San Jose as H, Donald E. Lacy Jr. as C, and Tommy Shepherd as L were particularly good, I thought, but Margo Hall as G, Ryan Peters as O, and Ricky Marshall as H’s father were also excellent. The play’s been extended and tickets can be reserved in advance at Intersection.