You can download the new chapter here.

I look forward to your comments!  None of the chapters have been properly edited yet, so I apologize in advance for the typos you’ll surely find…

I’ve been working on a book “The Fundamentals of Heavy Tails” for more years than I’d like to admit now, but progress has been very slow — especially since I became department chair.  Well, this summer I finally managed to put aside a day a week for book writing and it paid off!  We’ve completed drafts of two chapters and have two more that are nearly complete!

Many of the other chapters just require polishing too! So, hopefully, we’ll be able to continue to release chapters during the fall…

In the meantime, I’d love to get comments on the completed chapters, so please take a look and then write to me.  You can download chapters here. (We ask that you fill out a form so that we can contact you with updates as we release more chapters and complete the book.)

Enjoy!

What is an alumni college you ask?  Well, instead a homecoming game or something like that, we get alumni back to Caltech by promising a day of research talks, well really thinks like TED talks!  So, Alumni College focuses on a different theme each year, and then does a day of provocative talks on that topic.  This year the theme was “Disrupting Science and Engineering with computational thinking” i.e., the disruptive power of CS+X.

As I’ve written about before, we view “CS+X” as what makes Caltech’s approach to computer science so distinctive compared to other schools.  We pride ourselves on inventing fields and then leaving them for others once they’re popular so that we can invent the next field.  So, “seeding fields and then ceding them”…

In any case, the alumni college was a day filled with talks on CS+X from researchers at Caltech that are leading new fields…  We covered CS+Astronomy, CS+Physics, CS+Biology, CS+Economics, CS+Chemistry, CS+Energy, and so on…

You can watch all of them on Youtube here.  Enjoy!

The idea is that hacks, breaches, monitoring behavior, etc. are so common and hard to avoid that relying on tools from crypto or differential privacy isn’t really enough.  Instead, if someone really cares about privacy they probably need to take that into account in their actions.  For example, you can assume that google/facebook/etc. are observing your behavior online and that this is impacting prices, advertisements, etc. Tools from privacy, encryption, etc. can’t really help with this.  However, tools that add “fake” traffic can.  If an observer knows that you are using such a tool then you always have plausible deniability about any observed behavior, and if these are chosen carefully, then they can counter the impact of personalized ads, pricing, etc.  There are now companies such as “Plausible Deniability LLC” that do exactly this!

On the research front, we looked at this in the context of the following question: If a consumer knows that their behavior is being observed and cares about privacy, can the observer infer the true preferences of the consumer?  Our work gives a resounding “no”.  Using tools from revealed preference theory, we show that the observer not only cannot learn, but that every set of observed choices can be “explained” as consistent with any underlying utility function from the consumer.  Thus, the consumer can always maintain plausible deniability.

If you want to see the details, check it out here!   And, note that the lead author (Rachel Cummings) is on the job market this year!

P.S. The NSDI PC meeting was really stimulating!  It’s been a while since I had the pleasure of being on a “pure systems” PC, and it was great to see quite a few rigorous/mathematical papers be discussed and valued.  Also, it was quite impressive to see how fair and thorough the discussions were.  Congrats to Aditya and Jon on running a great meeting!

The last workshop was on “Beyond worst-case analysis” and the organizers (Avrim Blum, Nir Ailon, Nina Balcan, Ravi Kumar, Kevin Leyton-Brown, Tim Roughgarden) did a great job of putting together a really unique program.  Since there’s not “one way” to go beyond worst-case, the week included a huge array of interesting ways to get results beyond what is possible from worst-case analysis, whether it be learning commonalities of different types of instances, semi-random / smoothed analysis models, or extracting features that enable learning what algorithmic approach to use.

If you’re interested in getting a broad overview of the approaches, I highly recommend watching Avrim’s introductory talk, which gave a survey of a ton of different approaches for going “beyond worst-case” that have received attention recently.  Tim also has a great course on the topic that is worth checking out…

My own contribution was the final talk of the week, which gave an overview of our work on how to use properties of prediction noise to help design better online optimization algorithms.  The idea is that predictions are crucial to almost all online problems, but we don’t really understand how properties of prediction error should influence algorithm design.  Over the last few years we’ve developed some models and results that allow initial insights into, e.g., how correlation structure in prediction errors changes the “optimal” algorithm form.  Check out the video for more details!

Of course this is perfectly suited to what we do in RSRG at Caltech!  We missed the first year of the call due to bad timing, but we submitted this year and I’m happy to say it was funded (over the summer when I wasn’t blogging)!

The project is joint with Steven Low, Venkat Chandrasekaran, and Yisong Yue and has the (somewhat generic) title “Algorithmic Challenges in Smart Grids: Control, Optimization, and Learning.”

For those who are curious, here’s the quick and dirty summary of the goal…taken directly from the proposal.

We are at the cusp of an historic transformation of our energy systems. Driven by the goal of sustainability, the management of the electricity grid is becoming more distributed, dynamic, and open. Over the coming decade the grid will grow into the largest and most complex example of the internet of things, with hundreds of millions of active endpoints that introduce frequent, random, and large fluctuations in supply, demand, voltage and frequency. However, there are significant challenges facing grid operators as this transformation begins. A key bottleneck in this transformation is algorithmic. In particular, the current algorithms managing the design and operation of the grid often do not scale or are not appropriate for such an enormous, distributed, dynamic, network of distributed energy resources. Further, the development of algorithms that do apply to this emerging smart grid requires pushing the boundaries of control, optimization, and learning. The goal of the proposal is to tackle the algorithmic challenges underlying the transformation of the power grid. Concretely, we focus on three core algorithmic challenges facing the power grid during this period of transformation: control, optimization, and learning.

Control: Control problems in power systems are crucial and varied, e.g., frequency and voltage control. What makes these problems so difficult is the physical laws that define the dynamics of the system. We propose to study an optimization-based approach to the design of feedback controllers for cyber-physical networks such as smart grids. The method designs the controller state, information structure of the cyber network, and distributed control policies so that the closed-loop system is asymptotically stable, and every equilibrium point of the closed-loop system is an optimal solution of a given optimization problem.

Optimization:Optimal power flow problems underlie numerous power system applications; however they are challenging because the power flow equations that define them are nonconvex. Such problems belong to a class of optimization problems termed exponential programs (EPs). In preliminary work we have developed, for a special class of EPs called signomial programs, a new hierarchy of convex relaxations based on relative entropy optimization. Our goal in the proposed work is to extend this approach to develop a complete hierarchy of convex relaxations for EPs based on relative entropy optimization. This will immediately yield a fundamentally new approach for solving optimal power flow problems in power systems, one with the potential to have enormous practical impact.

Learning:One of the biggest challenges in cyber-physical networks in general, and power systems in particular, is that data about the system is too expensive (or simply impossible) to obtain in real time. This leads to challenges for control and optimization because even simple optimization and control algorithms usually involve evaluating the objective value for many (even all) possible options, e.g., greedy algorithms. Clearly, this is prohibitively expensive. Our preliminary results have shown that it is often possible to learn a policy that is near-optimal efficiently, despite not having access to the objective function at run time. Our goal in this proposal is to extend these preliminary results to optimization and control problems facing power systems in order to allow them to “learn to optimize” in real time.

So, if you’re thinking of where to apply for grad school or a postdoc and these projects appeal to you — apply to Caltech!  We’re hiring…

We’re in the middle of workshop season in the LA area where every week or so there is a Socal X workshop.  We’ve already had the Socal Control Workshop, next up is the Socal Network Economics and Game Theory (NEGT) symposium (next Friday).  The week after, we have the Socal Theory Day, and the week after that we have the Socal Machine Learning day! (The last two are being hosted at Caltech this year.)

So, if you’re in the area — I’ll probably see you at least once over the next few weeks!  Be sure to register for the ones you want to attend ASAP…

• The von Karman Postdoctoral Instructorship Program in Applied and Computational Mathematics
• The DOLCIT (Decision, Optimization, and Learning at Calif. Inst. of Tech.) Postdoctoral Fellowship Program
• The Center for the Mathematics of Information (CMI) Postdoctoral Fellowship Program
• Linde Postdoctoral Fellowships in Economics and Computation
• IQIM (Inst. for Quantum Information and Matter) Postdoctoral Scholars

I am personally looking for postdocs as part of the first four programs.  Don’t worry too much about which program is best suited for you when you apply, the backend of the application site is unified so that all faculty can easily see all the applicants.  Just be sure to mark the names of the faculty that you are most interested in working with when you go through the application process.

I’m generally looking for postdocs in the areas of Network Economics, Smart Grid, and Online Algorithms, but a few areas that I’m particularly hoping to find people in are: (i) digital platforms (any flavor of research, from measurement to modeling to economic analysis), (ii) markets surrounding data, (iii) electricity markets for demand response and renewables, (iv) online optimization or, more broadly, online algorithms.  So, if you’re interested in these areas please apply (and send me mail)!

“Data Markets” is one of those phrases that means lots of different things to lots of different people.  At its simplest, the idea is that data is a commodity these days — data is bought and sold constantly. The challenge is that we don’t actually understand too much about data as an economic good.  In fact, it’s a very strange economic good and traditional economic theory doesn’t apply…

• Data has zero marginal cost.  Once you have it, you can sell it as many times as you want without additional cost.  This it’s a so-called “digital good”.
• Data has strange complementarities and externalities.  The value of a piece of data depends on who else knows it and what other data the buyer has.
• Data is extremely hard to value.  How do you value every possible query or combination of data?
• Once data is sold, it can’t be “used up” — selling creates competitors!
• Releasing data can have unexpected social consequences.  Leakage can have huge privacy consequences!

We have more questions than we have answers at this point, but our vision, which I outlined recently in a talk at an MSR workshop on “System design for cloud services”(see the 15min mark of this video), is that within 5-10 years data will move from a commodity to a service in the cloud.  This transition is similar to what happened as computing infrastructure moved from a commodity to a service rented from the cloud.

There’s lots of challenges before cloud data markets can become a reality though.  All the things that make data a strange economic good, make it extremely hard to price and value in an automated way.  The transition has already started via companies like Factual, which seeks to be a clearinghouse for data.  But, there’s a lot of research that needs to be done before we can truly have automated cloud markets for data…

Also, I want to highlight that we adopted a unique way of running our searches last year, and it worked out wonderfully so we’ll be doing it again this year — we’re organizing our interviews as hiring symposiums.  

In my opinion, the traditional mode of faculty hiring does a disservice to both candidates and departments.  Candidates come and give talks to audiences that are exhausted from attending dozens of job talks and often end up scheduled on days when many faculty are out of town (sometimes the most important faculty).  Then, they have to wait for feedback/offers until after all the other candidates go through — all the while learning very little about how they did and what their status is.  On the other had, departments often end up making decisions by comparing candidates who did not see the same set of faculty (do to people being out of town) and who came through over months.  So the hazy memories and varying faculty in attendance lead to poor decision making.

Our approach, which we adopted from the Biology community, is to organize our interviews in two “symposiums”, where ~5 candidates come in for each symposium.  The first day of the symposium is all research talks and candidates can choose whether to attend each others talks or visit around campus.  The second day is one-on-one interviews.  Because the dates of the symposiums are picked well in advance every faculty member can be present — even faculty from other related departments.  As a result, we end up with audiences of around 100+ people, which is huge for a small place like Caltech.  Further, the symposiums are scheduled close together so that within a couple weeks of the interviews the faculty can finish discussions and all candidates can know exactly where they stand.  This additionally means that the discussions can be much more fair and balanced since they happen when the talks are all equally fresh and all the faculty were present for all the talks.  An added bonus is that the candidates can get quick feedback with which to improve their later interviews!

As I said, the initial test of this model last year was a resounding success from all accounts (both from our faculty and the candidates we interviewed) and so I’m excited to announce that we’ll be doing it again this year!