a16z Podcast
Original podcast
Where to listenCopy share link
5,060 words · 2 speakers
Okay, thanks.
Good morning. Mike Jordan from uh from Berkeley. Uh so let me start with a slide that I've been using for about 10 years now, in some form or another. Uh I'm gonna skip over it actually somewhat quickly. I got some better slides I like better. Um but this is a little bit of a history, uh thumbnail history. Um so you know, big data I actually, even though it's mostly talked about in the technology um realm these days. Um I I at least was more aware of it from the sciences about 10, 20 years ago. Um and so the volumes are already very large and the velocities and so on and so forth. And I think there's been uh great deal of discussion about volumes and velocities and so on. But to me, it was always about the inferential issues at play. And um we already have seen a fair amount of that in the discussion this morning, I'm happy about that. Um so just quickly, uh one of the first examples of big data was particle physics. You gathered huge amounts of data.
And what was the inferential issue? Well, I was decided whether there's a Higgs boson or not. It was one hypothesis test, and you had to make sure the type one and error and the type two areas were small together, here's amounts of data to do that. So inferentially there we that's where you are. Another uh areas where you know some of the more exploratory things, genomics, astronomy, and so on. So you're just looking for cool new phenomena, right? And so it's not a hypothesis test. It's it's you got zillions of hypotheses, you're trying to see which of them might be true. And you're pretty much happy if 90% of your answers are good. So that's kind of a you know, classical false discovery rate sort of thing. 95 is good. All right, inferentially completely different from the previous big data problems. Now let's go to technology. Now you're trying to serve, you're trying to personalize the service. I mean, you're trying to serve vast numbers of people.
You are not happy if you serve 90% of the people correctly in most of these business models. Because the 5% that you serve incorrectly or badly are going to write to the newspaper and complain and bitch and moan. Okay? So now you're in a completely different inferential world. We're trying to call uh control the L infinity norm, not the L2 norm. All right, so completely different mathematically and conceptually. So if we don't start making those distinctions, we're just not even talking about the big data problem seriously. We're just building software and hoping it works. And I do think that's actually where we are mostly. We're building lots of software hoping it works, and we're not really thinking about the harder intellectual issues at play. So here's another set of little sequence of slides that uh brings this home a little bit more. Um it's gonna sound kind of fanciful, but it's it's trying to get it some intellectual academic issues.
Uh so you know, one of my students might graduate, come down Silicon Valley, and someone says, uh, I need a big data system, and I wanted to replace our classical service with a personalized service. Actually, that's the key word. A lot of these, the business models here are you know, personalized something that came before. Because you have so much data, now you have data about every individual. So it seems like you could just build more lots of models and you know and make them faster and so on and paralyze it, and everything should be great. Um, well, you see a lot of these business models failing. People actually can't personalize very well, and it's because of statistical issues. You've got huge amounts of data about some people and very little about lots of people, and you don't know how to transfer the statistics amount around that. It's still hard intellectual problem to solve. All right. But your boss believes you can do it. He believes you just write it download some software and chart it and it'll run, it'll be great.
That's what the boss believes. And moreover, I can tolerate a few errors, but not too many dumbs old embarrasses. That starts to get more challenging. That's alluding to this L-infinity error. You want to make sure you you don't make 95% errors. Now you're sort of scared your head, you know, I'm sure you can do this. All right, but it only gets worse. Now that was kind of statistics. What about computer science? Well, it should run just as fast as our previous system because people are logging in and they're getting the service and they don't want it to slow down. Of course, behind the scenes, you've got billions of models instead of one omnibus model. So you got to do a lot of scrambling behind the scenes to make sure the computer science helps the statistics that your error rates still stay small, and you do it in the same amount of time. All right, now that gets to be a big engineering challenge, which you know maybe we're starting to face, but it's really not clear we know how to face it.
But it gets only worse because now in 10 years we're gonna have you know thousands times more data, and it you should never slow down. How do you build systems that never slow down as you get more and more data? All of our theory in computer science says that as I n gets larger, I go up by n cubed, n squared, n log n or whatever. All right. Um it goes up. How could you stay constant as the amount of some some computer science resource gets larger in? How could you keep error rates the same and time the runtime the same? You know, well, you know, paralyze and so on. We do have some knobs out of our play. We don't know the engineering principles to make all that happen. We cannot build systems that know how to dial all those things. So we are just hacking around building systems hoping they work. All right, it gets only worse because your boss says, well, there's lots of privacy concerns too. You better bring in these externalities. You gotta care about who uses the data and who owns it, who transfers it around.
All right, and now you have to bring in new mathematical constructs of privacy and bring them into the same equations that keep control over all these other variables. So I think we're decades away from being able to do what this boss is asking to do in some principal way. You could occasionally build a one-off system that does some of these things. We're decades from uh from having the real principles. So I want equations that do all these things. Big O is fine, but I want real equations that do these things that have real principles underlying. All right, and I think to do that, we're gonna have to do a fural blend of what I like to call computational thinking and inferential thinking, not just computer science statistics. That's a little too narrow. All right, but computational thinking, you know, modularity, abstraction, robustness, the principles we're used to from computer science, but blend those with inferential thinking, which is taking the data and going behind the data and thinking about the sampling patterns and thinking about the robustness issues.
So not enough just to build a piece of software that runs machine learning algorithms, that's not inferential thinking. Okay, it's not inferential thinking. Um it's really hard. I think it's it's it's more than just kind of bringing together two mindsets. Uh if you look at core statistical theory, it's statistical decision theory. I teach it all the time. You never see the word runtime. You see numbers of data points, you have sort of surrogates for comp you know runtime, but that's that number of data points, it's not runtime. You know, is in order this is n. Runtime might be n log n, n cubed, and whatever. It's not, you know, it's completely different concept. So that's a big problem. You don't have it. And then if you look at complexity theory, the theory in computer science, there are several versions of it. You never see the risk, or rarely. Okay, you control other things like you know, worst-case complexity and you know, geometric variables and all kinds of surrogates, but that's that's not a risk.
It's not errors. Okay, so we just don't we have a we have a oil and water problem. You can't, it's hard to glue these things together. Um so before we get a new new Turing level theory that blends all these things, at least we can try to be good engineers and build you know a mathematical trade-offs that combine statistical quantities, things like risk, dimension, et cetera, with computational quantities. Can we get some equations that start to guide practice? Okay, so this is what we've been doing in my group for about 10 years now. Um and I have a whole bunch of little vignettes and examples. You can go to my website and see a bunch of them. Let me just pick a couple for this talk. Um here's one that we've worked on the last three or four years. Let's let's uh as all of you know, it's important to try to bring privacy into statistical data analysis. Uh differential privacy is kind of a uh worst case, but you know, um particularly powerful notion of privacy.
So let's just borrow that. Um but now let's think about this inferentially. Okay, so differential privacy is mostly not been thought about inferentially, and that's what I want to do on the next few slides to bring that home to you. Maybe it's already clear, but I think that people aren't getting this. All right, so here's a way to think about privacy in CS. Uh this is kind of differential privacy perspective or related things. A query comes into a database, and out comes the answer to a query, which I'm gonna maybe unusually know it as a theta-tilde, some answer to a query. All right. Um privacy stories, you have an operator Q that somehow smudges up the data and gives you a privatized database, so that I can't look at the privatized database and say who was in the original database with high probability. Okay. Um maybe do a little PLOS noise or randomized response or you know, various mechanisms that you can prove, you know, make that statement.
So now you the query goes to the privatized database, and you get an unanswered theta hat. And the theory is that uh is to show that theta hat and theta twiddle are close with high probability over Q where Q meets the conditions on differential privacy. So there's a beautiful, you know, lots of papers, beautiful theory about all that sort of stuff. Okay, so there's probabilities here. Uh the query might be compute the median or the mean or the standard deviation. It looks very statistical. All right, but I don't think of this as inferential. All right, so let's so why? Well, so the database, let's just take an example. So the database is maybe uh, you know, bank accounts, it's you know, where you live and and and so on, and then how much money you have. And the queries are things like the the mean or the maximum or something like that. I care about how how big my accounts are. All right. And I want to protect the privacy, obviously, of the people on the bank.
So now I just want to do lookups against that database and do things that look statistical, but they're descriptive statistics. They're not inferential. Inferential is when I think there's more people in the world that I'm trying to apply my model to. All right, so let's take a different example. So suppose these databases now people who came in for medical tests, and I gave them a drug or I didn't. Alright? And then I see how long they live. All right. And uh so I want to protect the privacy of those people, surely. But let's suppose those people are dead and gone. Is my database meaningless? Well, in the banking case, it's kind of meaningless. Maybe you know, for you know, tax reasons it's not, but pretty much meanness. But in the medical case, it's not at all meaningless. I'm gonna use those for new people who come in and see if I should give them the drug or not. That's an inferential thing. So the inferential perspective is that I have a uh database, a query comes in and all, but behind the data is a population.
That's what a statistician always wants to do, is think about where the data come from. There's a population. And the population is gonna generate new people about which I want to answer queries. I don't care about the people in the database at all. Maybe they're dead. Okay. So lookup problem is just of no interest to me. The inferential problem is the interest. So I applied the query to the population, i.e. to a new person from the population, and then with high probability over the sampling pattern, S. I want to say that theta and theta twiddle are close. That's statistical inference. That's not descriptive statistics, that's statistical inference. Okay? And inference isn't just computing conditions of marginal. Probabilities, by the way. That's that's that's a computational problem. But inference is this. It's saying that theta and theta twiddle are high are close with high probability over the sampling pattern S. And over uh P, because I don't even know what P is.
All right. Now I think you can see where I'm going with this. Uh we want to put the two together. All right. So now we're doing computer science and statistics. Inference meets computational thinking. All right. So I want to say, given an underlying population that's generating my data, and giving that I want to protect the people in the database, because they gave me the data. I want to protect them. Alright, so with high probability over Q and over S and over all P and over all queries, right? I want theta to be close to theta hat. Alright. So there's one of our grand, that's a good that's a grand challenge. That's one we can solve as a good engineers and mathematicians. All right, and uh so we've written a paper, uh John Duchy, Martin Witner and I have written one recently, that it offers such a theory. Uh so it's a mini-max theory, it's take statistical mini-max theory, so it's statistical statistical decision theories being brought together with differential privacy in an integrated way.
So we end up getting equations that have number of data points, dimension, the alpha parameter of differential privacy all wrapped up in one little equation. I didn't write it down, I wrote down the generating principle that you write down, you do the mathematics on to get that equation. But the equation is uh number of data points uh in the non-private situation becomes numbered to pay beta points times alpha squared where alpha squared is the differential privacy problem or divided by the dimension of the statistical problem. Okay, that's the effective sample size you need to achieve differential privacy in this theory. Okay. Um so that was one vignette, and we worked on kind of communication constraints, meeting inference and so on and so forth. Let me turn to the really hard problem, which is how do you combine computation in some sense, probably not the Turing sense, but in some sense with statistics. And I think this is just hard.
Um, you know, Turing complexity is just not the right tool to to combine with statistical risk. I just don't think that's the way to go. Um you know you want to get lower and upper bounds, lower bounds are particularly hard in the Turing model. You know, you have these machine constants that depend on the statistical quantities. Uh so uh I think we're at the beginning of this. I don't think we have really uh that good much of an idea. So we you know in my group we've been trying all kinds of ideas, right? You know, just little vignettes of how you bring together various ideas from various disciplines to link statistics and computation. Often the intermediate thing is geometry, information theory, even some database ideas like concurrency control, try to find pathways between these two really and challenging intellectual areas. Um I have seven minutes and thirty-seven seconds left, so I'm gonna pick one of these uh near the bottom, parallel distributed computing, and you know, I think as everyone in the room is not only aware, but you've all contributed to it, is kind of one of our big knobs.
We can, you know, buy lots more computers, and so how do we bring that into the statistical theory and into the computational theory in a nice integrated way? So uh I'm gonna talk about the bag of little bootstraps just because um I did hear a lot about error bars and so on and so forth. Um these are frequentist error bars. And most of the error bars I've heard about today, and I hear about often in the computer science context are Bayesian error bars. All right, where you put in a prior and outcomes a lot and with a likelihood you get a posterior error with it which is error in it. But you gotta get the prior right. And a lot of times you have no idea what the prior should be. You don't know what the tail should be in particular. And you're in high dimensions, you really have no idea how the tail behavior should be. And the whole inference is highly sensitive to the tails. All right, so if we're gonna be good engineers, we need we need to be aware of that at least and start really thinking about when we can protect ourselves and make good inferences and so on.
So the frequency perspective is it tries to get around, you know, you don't need how you don't have to put in a prior. And it also is extremely parallelizable. Uh so that's what the whole uh uh drift behind this project called bag of little bootstraps was. Um, aerial uh perna and meet and I have worked together on this for uh quite a quite a number of years. Uh so error bars, uh maybe I don't have to stress this, but I think I still do that you know, machine learning databases and often are these black boxes, an input comes in and out comes an output, and you want to make it fast, and you wanna you know show that you do well on hold out sets and so on and so forth. Um but in real life, you have to make decisions you really often want an error bar. Um if you're gonna do a battery of medical tests, and you say that some number comes out to be over 10, I'm gonna have a heart operation, and that number came out to be 10.01, you know, I'm probably gonna say, well, wait a minute, what's your error bar on that?
Because it's in there is an error bar. You're uncertain, as the previous talk emphasized. You're uncertain. All right, and if that error bar is really big, I might say, well, I want a second opinion. Or I want to say get some more data, or I want to get, say, get some better machines or something, uh, until that error bar is clearly over 10. And real life decisions that mean something, you need error bars. If they don't mean anything, you're just trying to serve customers and hope that everybody comes to your website, you know, I don't know, who cares? But in real life, you need error bars. Um, so let's let's talk about error bars. So maybe this is a little bit too tutorial, but this is an academic day, I guess. So I want to uh explain what frequentist error bars are. Um they're they're less understood, I think, than the Bayesian ones. So you have some data that come in, it goes into a black box, which I'm gonna call theta, maybe it's a neural net, maybe it's uh decision tree or whatever.
Outcomes a parameter estimate, which might be a prediction, it doesn't have to be a parameter estimate. Um and most of the attention is going into building boxes that make that kind of thing fast and easy to program and so on and so forth. But I don't care about that at all today. Um I want to get an assessment of the quality of the estimate. I want to say you gave me an answer out, how good is that estimate? I want an error bar on that thing. All right, how do I get and that's a computational problem itself? So how do I do that? Okay, so again, the statistician goes back to the notion that there was an odd running population that generated the data, and error bars are reflective of the underlying population. Okay. Um and so uh here's oh my slides are coming out a little messy on, ooh, that's really bad. On your laptop. Those were PowerPoint slides. How did they get all messed up? Hmm. That's so disastrous that I can't even talk about the slide.
Let me go forward. No, no, it's next to the next slide. Uh okay, you have to imagine a whole slide here that was beautifully drawn and designed. Up in Berkeley, and it doesn't work in Palo Alto for some reason. Yeah, it's that's it's maybe it's PowerPoint, maybe it's VCs. Um, so here's the picture that on the left-hand side, there's the population which generates data. And the first upgoing arrow goes to a little box, which uh is gonna be the data set, x1 through xn, number one in perins. Okay, so it's a data set that goes up there. That goes into a box which gives me a theta hat, all right. And uh if I only had one data set and I want to run it, you know, get out one answer, that's what I would have. But this is the unachievable ideal, which I say I want an error bar, I'm gonna run, I'm gonna get multiple data sets. So you imagine God could do this because God has the population. So God can generate multiple data sets and see how the how you're gonna fluctuate over the data sets.
So in more of it is going to be done in parallel. This is a cloud computer up in heaven. So you get uh M different computers in parallel, getting M different data sets, putting it through the estimator and getting fluctuations in the estimators, known as a sampling distribution, and plotting that and seeing what my errors are gonna be. Right now, on Earth, we only have one data set. We don't we can't uh generate multiple data sets. All right, but uh that one data set is a sample from the underlying population, and now I've made a histogram out of it. It's not just a table, it's a histogram. And that histogram is close to the underlying population. There's a theorem that says that, Glovingo Cantelli, uniformly close. Um I can take that population, and which I don't have and ignore the fact that I don't have it and say, well, there's my estimate of the population, and I can plug that in wherever the supreme beam was sampling from the popular true population, I'm gonna sample from my histogram.
So I'm gonna take my original data and sample, make a histogram out of the data and sample from that repeatedly. Okay, that's the idea of the bootstrap. If you've never heard of that before, now you've heard of you know, maybe you've heard about it in other context. But it says take your original data and sample with replacement, the computer can do this, and you're acting as if you're getting multiple data sets. And now you can get your estimator to apply those multiple data sets and get error bars. Now I started thinking about this is a 40-year-old, 50-year-old idea. I started thinking about this again. I first started hearing about cloud computers in the context of what was called the RAD lab at Berkeley. Um, you know, we were talking about data, you know, parallelism and everything, and so this felt perfect to me. Now I can run on multiple computers my estimator, and I can get the bootstrap going at scale, and it's win-win. All right.
And that's sort of true. And now there's the better picture. There's the bootstrap. Um now on the left, though, we have not the population, we have the histogram. But everything else is the same. It's as if you were really the supreme being, but you're using a histogram to drive your your error bars. Okay, but gotcha, big gotcha, which is you can't do this on a terabyte of data. All right, because each resampling of the original data set on it, if we have a terabyte is about 632 gigabytes. So you're sitting there on your terabyte of data, the central computer, you sample with replacement a few thousands of times, that's what you need to do. And you get these 632 gigabyte data sets, thousands of them, you're sending out your network to get out to your machines. Hopeless. Way too slow. All right, so our big principle in statistics, which is really is the bootstrap of how to get error bars in some generality without priors, just can't it doesn't scale.
All right, so this is the end of the story. Are we kind of sunk? We can't do good statistics and good computer science. So we worked on this, and uh the answer is basically no. We came up with a new idea, which people hadn't thought about before in the stat literature because they weren't thinking about the computational consequences. Uh so basically here, really quickly is the picture. I got 51 seconds. Uh, there is a population, a histogram, you're gonna subsample from that histogram, and but now you're gonna ignore the fact that you took a subsample of size B. Uh, sorry, you're gonna know you ignore the fact that it came from an intermediate step where you had the whole um whole histogram. B itself is an approximation to the population. A subsample also came from the population indirectly, but it came from the population. Okay. So you could ignore the fact that you don't know the population and use your subsample, which might be really, really small, and now you can re-sample from that as many times as you want.
Okay? So people have thought about subsamples before, but they thought because it was based on B points, you had to resample at B times. No, You could resample it in times. Use on your one computer a small thing and you generate lots of data as much as you want. And so you can get error bars now on the correct scale with a small uh footprint. Okay, so let me just show you the picture. This is now a nested loop, and this is a totally paralyzable thing. We implemented this. One of the first things that was done on Spark, besides just kind of core machine learning, was this. This is done uh very quickly and on Spark. Um so you know, data comes in on the left, it's huge, it's a terabyte, and we get now small subsamples going up to our multiple servers. Each one of these servers then is gonna have a whole bootstrap inside, which is more multiple threads, again on multiple processors, totally paralyzable, where you resample with replacement from a small footprint, and each one of those boxes is going to create an error bar.
Now we have multiple error bars, and they're just gonna aggregate the error bars. Yes, please. Can you use different subsamples? Yeah, you do. In fact, I uh good question. That's a that's a copy and paste error. It looks like I got I got the same subsamples because I just was too lazy to create different ones. But yeah, you definitely need to. You have to. You have to to get the theory to be correct. So I'm now out of time. But here's my last slide, in fact. Here's one of my favorite slides of all time. So, this is how much the how well this works. So uh this is on the Amazon EC2, this was with a terabyte scale data set. The blue curve is uh sequentially running the bootstrap of resampling with replacement, then putting it on the Amazon EC2, paralyzing logistic regression with SGD, and getting that to be as fast as possible, and then doing that again and again and again to get the air bar. You can see the air bar quality after about 15,000 seconds comes down to some level, and it took about 15,000 seconds to get it so no one's gonna do that in real life.
Here's the new algorithm, you know, again, implement on Spark, is that little red box there? It took about a couple hundred seconds to get it, and the answer quality is better than the bootstrap after 15,000 seconds. So this is really surprising. Bootstrap seems so natural, so paralyzable, so net naive, so correct. How could you get orders of magnitude improvement? Just reorganize the computation. So thank you, I'm done.
Page updated August 25, 2026 · transcript and summary are machine-generated