Week long post

Week was short; two days studying for ML midterm, two and a half days spent hacking on PCFS (it works!!!), one day spent thinking about homeworks. More tomorrow when I actually have time to do some math.

Twelf and Agda Tutorial and randomized ID3

So, today Rob Simmons, Chris Martens, William Lovas and I (with help from Dan Licata) hosted a Twelf/Agda school. Since I typed for a few hours with Rob's normally-bound keys for Agda mode, I'm going to save my wrists and keep this post short. Basically, we showed a few basic encodings of addition in Agda and one in Twelf, proved a few things like commutativity, and generally treid to show off a bunch of the useful and interesting features these languages provide. I'll post the code later tonight.

Also, there appears to be a workshop paper about randomized decision trees which are differentially private; related to what I want to do but not quite the same because I suspect the organization of randomized trees will make difficult post-pruning without substantial information loss.

Differentially private decision trees, part 0

Today, I set out to figure out what several good mechanisms for generating differentially private decision trees ("good" here being relative, since generating decision trees is NP-hard in almost all settings). Despite this, shallow trees are used frequently in machine learning, so the problem seems somewhat practically motivated.  Step 0 for tomorrow: figure out a good metric on trees. Step 1 for tomorrow: figure out a good measure for a tree's "usefulness" given the data it was derived from. With these two things (or sets of things) in hand, using McSherry's exponential method (a mechanism which outputs differentially private structures which outputs structures with probability exponential in the utility of the structure).


 Also, I am left wondering what kind of regularizer I could come up with for ID3. While ID3 is a heuristic, and not the solution to some minimum loss function, each step does minimize the entropy of the attribute it chooses to split on, so there are some similarities. If there were some way to formalize this, there might be some nice connections with Chaudhuri, and Monteleoni's work on empirical risk minimization.

Parser success, and load balancing

This morning, I fixed a bug in the back-end parser of my extension of a Proof-Carrying File System (D. Garg) to include support for linear file access and revocation. I had changed the front-end to write out procaps (proofs of capability) in a slightly different format, and hadn't altered the MAC signatures to match. Fortunately, was an easy bug to catch.

I worked a bit on finding a bound on the correlated equilibrium of noisy load-balancing. Up to this point, I have shown that this game is not smooth (a la Roughgarden) and Aaron Roth has shown that the coarse correlated equilibria can be arbitrarily bad. So, we've decided to look at the simplest setting we can think of to try and bound the cost of the correlated equilibria: two machines, with each player costing 1 on their optimal machine and B on the other. In this instance, the correlated equillibria and the coarse correlated equilibria will coincide. Today, I tried breaking the expected sum cost of the players into four components: the expected cost of players playing on their optimal machine and those playing on their non-optimal machine (for each machine). Each of these I subdivided further into the cost each player of each type pays, which is the sum of the expected cost incurred by the other players on that machine plus the cost of that player. I'll post a link later when I get the TeX looking good.

Pranjal and I also talked a little about how smoothness is (and is not) related to stability. It looks like the weaker notion of stability (e.g., that all e-approx. equilibria fall within a d-ball of some nash equilibrium) might have some connections to smooth games. Unclear at the moment, but seems that lambda close to 1 would be the primary case where this would be interesting.