CEOInterviews.AI
Start App
Get an email when Ankur Moitra gives a new interview
One email per new interview. Unsubscribe in one click.
Ankur Moitra
Professor of Mathematics, MIT

Ankur Moitra @ Theory Lunch

📅 Oct 13, 2026 Princeton TCS 59 MIN 213 VIEWS 70 SEGMENTS · 2 SPEAKERS
Title: Learning Markov Random Fields from Dynamics Abstract: The problem of learning markov random fields from iid data is widely studied, but unfortunately strong computational lower bounds are known when there are higher order dependencies. I will show how assuming the data is generated by a natural process called the Glauber dynamics allows us to circumvent these barriers, by harnessing the dependencies. This is based on joint work with Jason Gaitonde and Elchanan Mossel.

What Ankur Moitra said

Written from the verified transcript and checked against it. Every figure links to the moment it was said.

Ankur Moitra discussed learning Ising models from Glauber dynamics, contrasting it with the IID learning setting. He explained that while IID learning of higher-order Markov random fields is hard (due to sparse parity with noise), learning from temporal dynamics overcomes this. He introduced the concept of 'good sequences' in Glauber dynamics to estimate conditional distributions, and used the statistical idea of 'population of means' to show that squaring the difference of conditional probabilities can detect higher-order interactions. He highlighted that this approach yields a fixed polynomial-time algorithm for learning order-k Markov random fields from a length n log n trajectory, with exponential dependence on k and d only as a constant factor. He also mentioned learning from state evolutions and scan dynamics, and concluded that modeling data generation more authentically can make learning easier, not harder.

Key takeaways

  1. Learning higher-order Markov random fields from Glauber dynamics is possible in fixed polynomial time, unlike IID learning which is hard.
  2. The key insight is using 'good sequences' in Glauber dynamics to estimate squared differences of conditional probabilities, enabling detection of higher-order interactions.
  3. Learning from dynamics can be strictly easier than IID learning, suggesting that richer models of data generation may simplify learning problems.

Numbers and commitments

FigureWhat it refers toTypeAt
2^n Number of possible configurations in Ising model metric 1:38

Chapters

  1. 0:00Introduction to Ising models
  2. 8:08Learning Ising models from IID data
  3. 10:58Hardness of higher-order Markov random fields
  4. 14:38Sampling and Glauber dynamics
  5. 20:44Phase transitions and correlation decay
  6. 30:06Learning from Glauber dynamics
  7. 40:23Population of means and shrinkage estimators
  8. 48:04The five-letter proof
  9. 52:05Learning from state evolutions
  10. 53:18Conclusion and open questions

Questions asked in this interview

2
  1. 12:34Is there a quick example of a distribution that I can express with like three, like with D3 or not D2, just like to get some intuition?
  2. 19:29So is that if the clock is not transitive or symmetric, is it obvious?
Ankur Moitra 0:00 ↗
All right. Thanks everyone for coming. So I'm going to be talking about learning Ising models from dynamics. This is based on joint work with some really awesome collaborators, so Jason Gandy and Elchanan Mossel. So this seemed like a fun talk to give for, you know, a theory lunch because, you know, we start late, we're all eating, and it's really just going to be a collection of stories. And the fun thing about it is that this will be the shortest proof you see in quite some time. I'll tell you right now, once I've told all the stories that are going to come together, the proof will be five letters. Okay? So we'll get there.
So as I mentioned, this will be, you know, mostly a bunch of surveys that are going to come together in an interesting way, but it'll really be about perspectives from two related things: learning and sampling, and how when we synthesize these perspectives it's going to get around certain computational obstructions that, you know, I and others thought were really there for some time. So let me start off with models. So Ising models, if you haven't seen these before, these are a class of graphical models. And the way you should conceptually think about them is that they're a language for describing high-dimensional distributions based on their pairwise interactions. So somehow when you think about high-dimensional distributions, you don't really want to define them exhaustively by writing down the probability of every particular configuration. Instead, you want to build them in some sort of more economical way. And the Ising model is the simplest example of this principle in action. It's something that's been studied for, you know, decades and decades. It originated in physics.
And so the idea is I want to define a distribution on plus minus one to the n. Right? So there are 2 to the n possible outcomes. But the way that I'm going to describe it is based on this expression right here. And we're going to parse this expression slowly just to think about what all the pieces mean. Now the most important thing is the interaction matrix. So we've got this vector capital X of random variables. Each of its coordinates is going to take on a plus minus one value. We've got little x which is some particular realization. So the probability that this vector of random variables takes on this particular realization is equal up to a constant of proportionality to the exponential of some kind of energy function. Now, what's going on in here is that you've got this interaction matrix that's symmetric. It's an n by n matrix. And the way to think about it is that the J entry describes some kind of affinity or disagreement between spins because whether it's positive or negative tells you whether you're rewarded or penalized for having the spins be the same or differ. So, it describes the pairwise interactions between these random variables. That's what gives Ising models interesting structure, but it's not a product distribution. It's really about, you know, these interactions between these different sites.
We've also got this vector of external fields. That's a vector of length n. And the way to think about it is in the absence of any interactions, all that would do is it would change the bias of each individual bit. And that's called an external field because it describes the preference for a random variable pointing up versus pointing down. Now the entire thing needs to be properly normalized. So that's summed over all the little x's, the right hand side equals one. And the way you do that is you just define a constant Z which is called the partition function. It's just chosen so that the entire distribution is properly normalized. And this is what an Ising model is. It's a description and a toy model for exploring all kinds of things. It really originated in physics as a way to understand the relationship between temperature and spontaneous magnetization, because as you change things like how strong the interactions are and how much you want to favor high energy distributions, these things kind of go in tension with each other. But for our purposes, what's really important is that this is an expressive language for describing interesting distributions in the world around us. Everything from physics to social networks. So we'll talk more about that.
Okay. So wide-ranging applications in science and engineering. And, you know, I mentioned that an Ising model was an example of something called a graphical model. Now the reason for that is if you take the description I gave you, the formula I gave you on the previous slide, and you write down an associated graph, that graph's combinatorial properties can tell you lots of structural properties about the underlying distribution. So what do you do? I've got a vector of n random variables x1 to xn. So I'm going to form a graph on those variables. So the nodes are x1 to xn. And I'm going to put an edge between a pair xi and xj if the corresponding entry in the interaction matrix is non-zero. Remember my interaction matrix is symmetric. So this is producing an undirected graph. And the important thing about this is really the Markov property that it turns out that graph separators teach you a lot about the independence properties of whatever distribution you're describing. So in particular, if you have two nodes, they'll turn out to be independent conditioned on another set of random variables if those variables separate them when you delete them from the graph. So more precisely, you know, Xi the variable is conditionally independent of Xj conditioned on the set X capital U if U blocks all of the paths in the graph that go between i and j. So this is a one-directional. It's not an if and only if statement. But whenever you have a separator, you get this kind of Markov property.
Okay. Now I want to give you at least one more running example to keep in mind because this will be an example that we can use to sort of connect the learning and sampling perspectives. So this one's not from physics. It's a more modern one. It's from social networks. So one of the things that people like doing in, you know, computational social science are doing things like modeling the adoption of a technology across a social network. So, you know, most people when they have smartphones, they have either an iPhone or an Android phone. And it's not that we make these choices completely independently of which one to choose, but it might actually depend on our underlying social network. So, in fact, my own choice of whether I select an iPhone or an Android phone might depend on if I create a graph describing, you know, who else I'm connected to, it might depend on what decisions they make, right? So many works actually formalize this as a type of Ising model because instead of having a product distribution that describes the realization of who buys an iPhone, who buys an Android phone, maybe you think about the realization of who buys what as actually being a sample from some kind of Ising model and maybe the weights on the edges represent the strength of our different connections. So this is a really beautiful model, you know, in computational social science because, you know, you can use it as a test bed for studying things like, you know, viral marketing. If I'm going to pay for ad exposures, you know, who are the people that I actually want to, you know, affect their choice the most that are going to have the most externalities on the rest of the network. So people study all kinds of wonderful things like influence maximization in these settings and, you know, we can think about the Markov property in this context as being a very natural thing. We're saying my choice of whether I select an iPhone or an Android phone is not independent of the rest of the graph. But if you told me all of the choices of my neighbors in the social network, then my choice actually would be independent because I'm not directly interacting with any of those people. So the Markov property is very natural and this is really just my attempt to make good on this assertion I made that the Ising model is this wonderful language for describing things you care about in the world around you. Everything from magnetism to social networks.
Okay. And as I mentioned, this is really just going to be a collection of surveys with one five-letter proof at the end. So, you know, now we know what models are and we might be interested in the learning problem. You know, if Ising models are a good model for the world around me, they might be a good model for the data I'm trying to learn from. If someone is generating samples from an Ising model, you know, can I learn the underlying description, right? You know, maybe I can observe through Facebook or Twitter some kind of graph-theoretic connections, but maybe by observing actual samples, I could hope to even infer the edge strengths in this interaction matrix. So if someone is giving me samples from an Ising model, you know, and I get a polynomial number of samples and polynomial running time, what can I say about algorithms for actually learning the underlying graph structure or the interactions? And this also is a very old question. It goes back, you know, to 1968 due to this famous work of Chow and Liu. So they gave an algorithm that runs in polynomial time provided that the underlying graph structure is a tree.
That's very beautiful. It turns out that, you know, what you do is you just compute things like mutual information between two different nodes. And the intuition is that things which are neighbors are going to have the strongest mutual information. So you just look for some max weight spanning tree and you can show that that actually identifies the underlying structure. Now people took a break from working on it for several decades and then they came back to it and in 2001, Abbeel and Seeger gave algorithms that worked in much more generality on something called bounded treewidth graphs. And, you know, actually this amazing work of Guy Bresler, really beautiful work from 2015, they showed that there were polynomial-time algorithms that work provided you have graphs of bounded degree. So if you've got a graph on size n and it's got max degree d, then what his algorithm gives you is an f of d times poly n algorithm for solving the underlying learning problem. And it turned out his f of d was not so good. So it was doubly exponential in the degree and then afterwards, you know, people worked on improving it down to singly exponential in the degree which turns out to be information-theoretically tight. Now I'll explain a little bit more when we get into things like sampling about why I found this result so surprising, but this is some of the state-of-the-art of what you can do. You know, you can learn Ising models in cases where you have some bounded topology like a graph of bounded treewidth or you can even do it even on things like expanders provided that you've got a bound on the max degree. So there are lots of beautiful algorithms for learning Ising models.
But what I want to ask about is something a little bit more technical. So I told you that Ising models are really the starting point of this whole area of graphical models. Now what happens if my interactions are not happening at an edge-by-edge basis, right? What if they're happening over hyperedges? So what if instead of, you know, pairwise interactions I've got three- or four-wise interactions? The same way these things were introduced very shortly after Ising models because there are lots more processes that can be described with this even more general language, but it turns out that the story of what you can do computationally here is quite a bit more nuanced and pessimistic. So first let me be precise. So what is a Markov random field? You know, you'll see the same structure as for an Ising model. You know, it's describing a distribution even still on plus minus one to the n just for simplicity and it's defining the distribution up to this normalizing constant depending on the partition function. And even the form of it looks about the same. It's the exponential of something, right? The only difference was that for an Ising model I took the exponential of a degree-2 polynomial, that's where the pairwise interactions came from, but nothing stops me from ending the story there. I could talk about, you know, what goes upstairs as being a degree-k polynomial and the question is that as I increase k and increase the expressivity of this class of distributions, how is that going to interfere with the computational complexity of learning? So that's the operative sort of question.
Audience Member 12:34 ↗
Is there a quick example of a distribution that I can express with like three, like with D3 or not D2, just like to get some intuition?
Ankur Moitra 12:45 ↗
Yeah, there is and let's do it in a second. But very good. Okay. So here the operative question is how do higher-order interactions affect learning? And I'll kind of answer your question volitionally when we answer this question. Okay. So it turns out, yeah, Chatterjee and McAllester and then myself and some other folks showed that there are poly-time algorithms but a much worse polynomial. So here as you increase k you pay for it very steeply because it goes upstairs, you get n to the k time algorithms for learning order-k bounded-degree Markov random fields. And the trouble is that that really is necessary. So it turns out that under standard cryptographic assumptions, namely that the k-sparse parity with noise problem requires n to the omega k time, forces your hand that Markov random fields really are just genuinely very, very hard to learn from iid data. Now to answer you all's question, what's the world's simplest example? This is kind of almost a triviality statement that it's hard. The idea is that what would create a k-sparse parity with noise? You just create a single hyperedge that has a preference that these k things should have a better chance of having their parity be one, but you just don't know which is the hidden k-wise dependence and everything else is independent. So somehow these problems that are really thought of as being hard barriers in classical computational learning theory tell you something very strong that you cannot do because they can represent sparse parity with noise even in very simple settings where it's just a single hyperedge and instead of it being a degree-k polynomial it's just a single monomial with degree k upstairs. So that sucks, right? That's the first story and the punchline was that sucks.
Okay. So that was the story about learning. You know, what is the landscape of learning? We know many surprising statements but somehow they're limited to pairwise interactions and yet we would have this desire to be able to handle higher-order interactions. Now I want to tell you another story and I claim that these two stories will come together. So let's also talk about sampling. In a lot of ways, you know, sampling and learning are just different sides of the same coin. See, in learning, I'm assuming that nature is generating the data for me, and that's the thing that I want to learn from. I want to learn a description of what nature is based on the data that I'm being provided. Now, somehow there's the reverse problem, which is someone gives me a description of nature, of the underlying mechanisms for the interactions. This is the interaction matrix. This is the external field. And the question is, can you pretend to be nature? Can you generate those samples yourself? That's the sampling problem. So these two things we think of as being different, but they're really, you know, different sides of the same coin. And the way to think about it is that we've already assumed that, you know, algorithms for learning that we're given iid samples. But where on earth could these iid samples come from algorithmically?
Okay. And what I claim is that there's actually a very natural dynamics that, you know, eventually would be able to produce samples from an Ising model or for a Markov random field. So that's maybe probing a little deeper about what kind of mechanism we think nature might be running to generate those samples we're assuming we were given to begin. So now I want to tell you a little bit about that. So there's something very popular, very well studied in a giant subarea of theoretical computer science and it's called the Glauber dynamics. It's really, you know, the main character in approximate counting and sampling. So the idea is that I've got this high-level, you know, this high-dimensional distribution I want to sample from the Ising. I'm not describing the distribution to you by writing down 2 to the n probabilities, one for every possible realization. Instead I'm describing it to you in this very concise way based on the interaction matrix and the vector of external fields. So one way that you can generate a sample is you can set up a Markov chain. Now this isn't a small Markov chain because this is a Markov chain that's running on the full state space. So it's really running on a state space of 2 to the n possibilities. And all you have to do is describe the transition probabilities in such a way that eventually when you mix you're generating samples from the desired target distribution. So the Glauber dynamics, you know, without all of the parameters and equations, is really quite simple. You know, you start off with a graph, right? And maybe along each one of these edges I've got interaction strengths and I start off in some initial state. So maybe nodes are colored black or red depending on whether the corresponding variable is plus one or minus one. And what does Glauber dynamics do? You know, this is just the starting configuration. But eventually I have to have stochastic transitions so that I'm generating the desired samples I want. Glauber dynamics does the most obvious thing you can think of which is you choose a node uniformly at random. You erase it. And now there are two choices for what to fill in that node to. I could fill it in to red or black, right? I could set that missing variable that I've deleted to plus one or minus one. And the important thing is that it may be very hard to compute what is the probability of this configuration because that formula that I wrote down depended on this partition function. It's very hard to compute a normalizing constant. It may be very hard to compute the probability of the configuration upstairs for the same reason because the partition function. But what I really care about when I'm deciding among these two options is the ratio of their two probabilities. And in that situation, the partition function doesn't matter. And when I look at the ratio of, you know, their probabilities, because of the Markov property, the only thing that matters is this one node whose spin I've erased. He looks out on the world and it's just his neighbors that he sees. So that's the crux of what's going on is you just have to update the state with the right probability which you can trust me is a very simple computation when you use that formula I gave you on the second slide. And the important point is that this is a Markov chain that's running on an exponentially large state space. I can easily compute the transition probabilities. It's easy to show that the unique distribution it mixes to is actually the Ising model. The hard part is why should it mix rapidly? Why should it mix in time polynomial in n as opposed to exponential in n? Yes.
Audience Member 19:29 ↗
So is that if the clock is not transitive or symmetric, is it obvious? No. I just wanted to flag that fact. I assume if you're a Glauber this never comes up for the, but...
Ankur Moitra 19:52 ↗
It never comes up. I mean it's a bit of a technicality. So can I just say two words and then you can ask me more later. Detailed balance. So somehow if you choose the nodes non-uniformly, the thing you really have to check is just a detailed balance condition that, you know, at the actual steady state you want to sample from, that you've got the same amount of probability flow going in both directions. And that's really what's going on under the hood here. As long as you have that and it's sort of irreducible. This is just a general statement. But, you know, the difficulty is not really in showing that there's a unique steady state distribution. The difficulty is understanding, you know, qualitatively and quantitatively when do you get rapid mixing because the state space is exponentially large and getting a mixing time that's polynomial is really quite a miraculous thing. Right. Okay. Any other questions? All right.
Okay. So, you know, I'm going to tell you one more property about this because I'm trying to give you sort of an impressionistic view actually quite a few areas in theoretical computer science. So, you know, there's a whole area of study. You can do your PhD, you can get tenure, you can work your entire life at approximate counting and sampling. And, you know, from a broad-strokes perspective, one of the things which is really cool about it are notions like phase transitions and structural properties of distributions. So on the one hand, you know, we have this question when do these Markov chains mix rapidly and it turns out that structural properties of the distribution really play a very key role in our understanding of when they do and don't. So there's this amazing property called correlation decay, spatial mixing. The idea is that imagine we're working in an Ising model. Again, I'm depicting nodes where the corresponding variable is plus or minus black and ones where it's red as being minus one. And imagine I'm interested in the random variable at some node little x. And what if I told you, you know, the realizations of a whole bunch of other random variables that are very far away. So I told you the boundary condition: this node is black, this node is red, but somehow they're all distance r away from the node whose marginal I really care about. So there's something very cool called correlation decay, which is, you know, it's basically the idea that sometimes the marginal, you know, is very insensitive to the choices of how you're pinning the configuration very far away. So what can happen sometimes depending on your model is that, you know, actually telling me this configuration of what's black and what's red has very little effect, has vanishing effect on the marginal x as you send the radius to infinity. So this is a structural property about how long-range the correlations are. And, you know, this is really one of the things that people study in physics. So you do the same type of distribution we've been doing before. You take this, you know, polynomial h of x upstairs that's a degree-2 polynomial that describes the pairwise interactions, you just add a little knob that you can tune which is beta which is called the inverse temperature. And the idea is that, you know, now when I send beta off to infinity, my distribution is going to be very well concentrated only on the minimizers of h of x, right? And when I send beta to zero, that's like sending the thing to a really high temperature because all of a sudden they don't care about their interactions. What they care about is maximizing the entropy of the underlying distribution. But it turns out that, you know, as you vary this inverse temperature you get all of these exotic phenomena together. They happen all at once that, you know, for large beta you have these long-range correlations. Correlation decay fails. For small beta everything mixes very well. And the same thing, you know, happens for spatial mixing. So just to go back to our physical picture, you know, the original use of the Ising model was in understanding phase transitions in physics. So imagine I take a 2D grid and everyone wants to be the same spin as their neighbors. So they have a preference there but as I tune beta I'm tuning the strength of that preference. And what I can do is I can depict what a typical sample from that model looks like just by creating a picture with little black dots every time you've got a plus one, little white dots every time it's a minus one. And it turns out that, you know, as you increase beta, remember that means that you're concentrating your distribution on the minimizers of h of x. So in that case what happens is you want to completely agree with all your other neighbors. So in the very extreme case where everyone wants to be like their neighbors and you have a huge penalty for being different, you get exactly these sort of beautiful pictures where they sort of look like the night sky. They're mostly black with a little speckling or maybe they might be almost entirely white with a little black speckling instead. So this is, you know, the example of what I was talking about, about correlation decay in action, right? As you tune this knob all of a sudden you change the fact that maybe the dependencies die out on very short length scales to the property that these correlations, they actually persist for very long length scales. And this is the way that people study things like magnetization because really you've got some material and you think about those black and white dots as being their own tiny little magnets, right? And as you change the temperature all of a sudden, you know, when you go to really low temperature, then everything spontaneously aligns for the most part and you get global magnetism. But at the other end of the spectrum, when you heat it up and you've got this big preference for maximizing entropy, things converge to something that looks much more and more like a product distribution. So this is, you know, a really beautiful area of theoretical computer science that you can study phase transitions per sample. You know, for what value of beta can I computationally solve the problem of generating random samples? When does the Glauber dynamics mix rapidly? When does, you know, when are there long or short-range correlations? And it turns out that the Glauber dynamics actually has polynomial mixing time beneath some critical threshold and somehow above it the problem becomes NP-hard to generate samples. So it's kind of amazing in this area is I like to call it the confluence of different thresholds because everything goes right together or everything goes wrong together. You know, as soon as you have these long-range correlations the problem becomes computationally hard to sample and then the Glauber dynamics really does not mix. It really takes exponentially long to do its thing.
Okay, so now I want to come back and start to give a hint about where these threads are unified. Right? So what was my first narrative was Ising models and Markov random fields are really expressive distributions for the world around us and that's why it's very interesting to study the learning problem. Nature is generating the samples for me and I want to learn the underlying process, the dependencies. But now I have this weird quirk that somehow, you know, when I think about how nature could be generating those samples, it turns out that in some cases nature is actually seemingly solving a very computationally hard task because actually this critical temperature tells me that nature had better not be generating iid samples because these things are often NP-hard. So I think I want to connect it to, I remember when I was starting off in grad school, you know, mechanism design and HGT were, you know, all the rage. Maybe they still are. But I love this quote. You know, this was right around the time that, you know, Costas and company proved that Nash equilibrium is hard to compute. And, you know, if you think about it, like economists love using Nash equilibrium as a solution mechanism. You know, what equilibrium is this system going to converge to? Well, maybe Nash, right? But what does it mean when Nash is actually hard to compute? Then maybe it's not such a good selection mechanism. And that's a very long-winded way of saying something that I think Kimal James put really well. You know, I can't be as articulate, but if my laptop can't find it, then neither can the market. You know, what an amazing insight about the value of computational complexity and how we see the natural world. If that's your solution concept for what happens in systems and games, well, you might have a problem in cases where my laptop can't find it. Now, I'm going to have to like totally mess up this quote and create my own version. But, you know, I spend a lot of time thinking about beyond worst-case analysis, right? You know, what kinds of distributions are easy to learn from? Because, you know, LLMs solve everything under the sun. Somehow, you know, why that works must be some sort of reflection of how natural language is structured, right? But sometimes there's this problem that we try to write down a very clean learning problem as clean as possible, we learn it under Gaussian, we learn it under iid, and that's, you know, the simplest setting where we can study the computational complexity. But sometimes we've painted ourselves into a corner because the simplest version is actually the hardest, right? So in fact, you know, maybe there's a variant...
of this that's you know much less well phrased but if my laptop can't find it maybe it's not a good defensible generative model for the world. I said Ising models are really rich ways to describe things like magnets but if they're really hard to sample from I don't know if they're always a good way to model you know the way that our data is being generated.
So I want to you know again sorry we're going to go descent into the different stories today so this isn't a new idea. But you know the idea that somehow is that maybe learning from IID data is simple to state and simple to formulate but makes the problem much harder than it could be.
You know and one of the ways people have studied is like what happens if instead of learning from IID data you learn from like a trajectory of Glauber instead the way that the system is evolving over time. So this also has a nice manifestation in this running example that we talked about earlier. You know it's not just that we once all of us decide once and for all are we going to have an iPhone or an Android phone actually can study the dynamics of these models because people's you know phone sometimes breaks and they need an upgrade and then they you know decide which one they're going to buy right and in fact the Glauber dynamics is you know something that people use as a model for exactly those types of dynamics.
This idea that you choose a node at random, you erase its choice and now it reconsiders its choice and chooses from the right conditional distribution. This is a way that you can then not just study like you know which node should I influence have the most effect but also what are the time scales at which you know these kinds of decisions manifest across a network. So there's some beautiful work of like Montanari and Saberi that study these kinds of things and it leads you to a very different kind of question right instead of studying learning from IID samples you can ask the question can I learn from some kind of temporal samples instead like namely the Glauber dynamics.
So this is the you know maybe the last story I'll tell you before we start getting to the meat. So what can you say not about learning Ising models from IID data but from the trajectory of Glauber and people have been working hard at this question over the last few years. There's a work of Wrestler, Garnick and Sha they gave polynomial time algorithms for learning the underlying graph of a bounded degree Ising model from the Glauber dynamics and Gaitand and Muscle showed that you can do parameter learning too. So you can actually estimate the interaction strengths not just the zero nonzero pattern.
And you know just to be clear what does learning from Glauber mean? This is a somewhat strong definition. The idea is that you see the sequence of updates that Glauber is doing. So you see every time which node it chose to erase and then the decision of what spin it filled it in. Right? And I know that that's not actually mixing all the time for the Ising model. But now I've got interesting temporal dependencies that I can harness for learning.
And somehow here you know I want to take a step back and you know instead of framing these questions as boy we you know we can't generate IID data so maybe we should study learning from dynamics and let's hope we can get the same results we got for IID data in the dynamic case. What if we hope for more? So maybe actually learning from dynamics is actually strictly easier than learning in the IID case. So this I think is a really neat moral that you know I hope that there are other manifestations of this moral that sometimes when we work really hard to create the world's most sanitized and simplistic model well actually modeling the problem in a richer and more authentic way might actually give us structure that makes the learning problems easier not harder.
So what happens you know if we're learning from Glauber dynamics can we hope to do better. So here's the fun little surprise that I promised you we'll have a five-letter proof once we get to it. Is that it turns out that we are learning a Markov random field of order k remember in the IID case that's the setting in which we had the strong n of the k lower bound. So sparse parity with noise tells me you cannot learn higher order Markov random fields from IID data but when you're learning it from the Glauber dynamics those n of the k bounds are no more in fact there's a fixed polynomial time algorithm for learning it so you get everything you wanted and more in fact it's even just from a length n log n trajectory which is odd just by coupon collection.
Audience Member 34:05 ↗
You want...
Ankur Moitra 34:08 ↗
So it's an f of k in front. So it's exponential in k and d, but it's in front as opposed to the n of them. All right. Any other questions? All right.
Okay. So, what I want to do is I want to tell you at least a bit about how people were thinking about this before. This is just relevant context for getting to this ultra-short proof. So, let me tell you how the Wrestler, Garnick and Sha paper worked. And remember what they're trying to do is they're trying to learn Ising models from the Glauber dynamics. Okay. And it's based on a very simple idea which is what I want to do is just for each pair of nodes you know XU and XV I want to decide if there's an edge. So are they interacting or not?
Now again, I can't just decide this based on their correlations because they might be correlated even if they don't directly interact with each other because maybe there's some other node XW that they're both interacting with and that, you know, gives you the correlation. So the key is really, you know, to think about this a bit more from a causal standpoint about can you really pin down that V is influencing the distribution of U.
So the key is a good definition. So we'll say a good sequence. Maybe we just happen to get really really lucky and a bunch of things happen in a row. So in our Glauber dynamics that's picking a node at random. Maybe what happens is first XU attempts to update. [clears throat] So we erase the spin from XU and then we resample it, right? And then we resample XV. We erase the spin for XV. We resample it. But maybe it actually switches. It actually switches from +1 to minus one. And then we get lucky again because the very next update we erase XU and resample it yet again.
So the point is that we're getting two samples from XU. One in the world where XV was set to +1 and one in the world where XV is set to minus. So this is our mechanism for figuring out whether XV has any effect on XU because the whole rest of the world is remaining constant. Whatever effect they have is the same effect in both of these two worlds. And that's exactly the intuition is we're getting samples from the conditional distribution of XU when XV is plus one and one when XV is minus one. So we can do is we can just think about it in terms of the difference of two quantities P and P prime.
So P is the probability that XU is reset to +1 in the world where XV is +1 and P prime same thing but in the world where XV is minus one. Now here I've kind of abused notation because p and p prime are actually functions of the rest of the configuration right they depend on things besides xu and xv but you know even though those are themselves random I'm getting many resamples of this because every time I have a good sequence the rest of the world remains the same right so every time I have a good event P and P prime might be changing but for that good event I get an unbiased estimate of P minus P prime.
And so the idea is just that if xu and xv if their interaction is positive then I should really expect you know p minus p prime to be biased in one direction and if it's negative I expect it to be biased in the other direction and that as I average over more and more good events it might change what p minus p prime is but they'll all be biased the same way. So I'm adding up a bunch of things whose expectation is positive or I'm adding up a bunch of things whose expectation is negative. And that's the basic idea. You take a long trajectory of Glauber dynamics. You measure all of these good events. They give you unbiased estimators of this varying quantity p minus p prime. And you just set all of the edges to be wherever that statistic is sufficiently large.
Now I should mention when we were writing this paper we unfortunately found that there was a bug. So if you believed that argument I lied to you. That's not very nice. I told you this was going to be very friendly lunch talk. So there's a bug in it. It's not such a big bug. It's kind of minor but it is worth pointing out because see the problem is that if I condition on XV actually flipping that changes the first flare for XU, right? Whether it's likely or not, it's not an independent sample because that happened before. So you just have to be careful with it. We'll fix that. But just in case you're wondering, don't literally believe that proof.
But now let me try and grapple with this issue. You know the question is all about the challenge of higher order dependencies. When you move from pairwise interactions to hypergraph interactions something very nasty happens here that looks like it's just a death note, right? It looks like we should just give up. That's the end of the problem. Sorry I lied to you. So the issue is that you know if you've got a higher order interaction like maybe u v and w you know all interact right the trouble is that you know sometimes like if I'm trying to decide if xu and xv are together in any hyperedge they might not have a consistent influence on each other.
You know sometimes xu and xv want to be the same sign sometimes they want to be different that might depend on what the choice is for xw. That's exactly what caused the hardness for sparse parity with noise is the fact that you create a parity constraint among these others. So now instead of having P minus P prime having a consistent sign the trouble is that sometimes it's positive sometimes it's negative and it might all come out in the wash the zero as we average over it. So that would be a complete death blow right we should just give up.
Okay. And even worse, you know, it could be that there are multiple hyperedges and that their effects like U and V interact with each other but through two different pathways and those pathways might actually, you know, cancel each other out.
So I lied when I said I was done with my stories. I have one more story. This kind of my favorite one of it. I want to tell you about something in statistics that makes you know that I certainly did not know about before this. It's a really surprising and simple statement and it's going to completely change the way we think about this problem. So, let me tell you about something really cool from statistics. It has the most boring name you could think of. Population of means. I'm already asleep. Okay. In fact, the formulation will also not get me excited, but then I'll tell you some cool examples of this in action which are really surprising.
Okay, so I guess we can do this mathematically first. So imagine that I've got a bucket of points and they might have different biases. I don't know, there's a whole population of them. So what happens is I dig into my bucket. That's like sampling theta for mu because mu is the distribution of biases of those coins. And then I take that coin. I don't know it's biased, but I flip it once, twice, k times, I don't know. I observe what the outcomes were, you know what those flips were and then I put it back in the basket and then I redo the same thing again. So this is called the population of means because mu is my population of means.
And you know this has its origins in statistics because you know of assessment you want to figure out like if you're assessing people on some test right what you can learn about the underlying population of their ability levels right and so one of the questions I often ask myself is are students just randomly guessing, right? So, you know, maybe I had the world's shortest exam from an undergrad class. I just have one true false question and then it comes back and you know, half the people got it right, half people got it wrong. So, I don't actually know. Were they all guessing? Or maybe, you know, half the students have a perfect chance of getting the right answer and the other half just always get the wrong answer. So I can never tell whether all the coins are biased exactly 50/50 or there's some very different population.
What I claim, and this is a magical fact, is that that completely changes when K goes from 1 to 2. I claim that figuring out whether the students are randomly guessing, you can determine completely with that same experiment as long as when you pick up the coin, you flip it twice. That's kind of a remarkable thing. It's really surprising but you know the intuition for it is that you know you can actually estimate the first k moments. So it turns out that if you give me k flips of the coin you can estimate the first k moments of mu. And the point is that the only way that mu would be a point mass on a half is that the mean is a half and the variance is zero.
And you know this is actually an example of something in statistics that's very beautiful but again has a not so exciting name. It's called the shrinkage estimate. So your first guess at what to do is you know you take the coin you flip it k times and then you try and estimate the bias of that coin. The trouble is that you know that's something you can never do. I flip the coin twice. I really have no idea what its bias is. I get a very crude estimate. So shrinkage is based on the idea that sometimes when you parameterize things in a much more compact way. I'm not trying to learn the bias of this individual coin and estimate it. I'm trying to estimate the population of biases over the entire set of coins. Then the maximum likelihood estimator can be much better statistically behaved because of the fact that I'm more compactly parameterizing it.
But just to be perfectly clear, right? What is the mathematical statement I'm making? You take a bucket of coins and infinitely you do the following experiment. You take a random coin, you flip it twice and I tell you what the outcomes were and then you put it back. I claim that literally the only way that you can get a quarter heads heads, a half heads tails, a quarter tails tails is if it's exactly 50/50 for every coin.
And so let me tell you a really fun you know application of this. So I learned about this from Greg Valiant who told me this amazing biological application he had in mind. This is probably not where you expect that I was going. So it turns out there's this very interesting open question in biology that goes back at least you know 40 50 years which is whether the gender of your kid is related to the date of conception relative to ovulation.
Okay? Because you see the Y chromosome is lighter than the X chromosome. So in principle there are all these theories that it can swim faster up the fallopian tubes right and you can find these studies in biology on like ultra small sample sets with like 12 people where they're like trying to make this argument that you know there is an effect right and then if you search for these things you find all these articles online with all these old wives tales right up there with like date of conception and if your head is pointing in the northwest direction okay so who knows now this is a very hard thing to measure because you don't know the date of conception relative to ovulation unless you have twins that they have the same relative date to ovulation. Right? That's kind of like, you know, the bias of the coin. I don't know, you know, which sample it was because I don't know the date of conception relative to ovulation.
But if I have heterozygous twins, then it's like getting two independent flips from this coin. So in principle, you can decide this fact. So Greg was very excited. He told me about shrinkage estimators. I was happy to learn them once I woke up again. And then obviously there's a problem which is privacy. That's a big problem, right? Who's going to give you data on heterozygous twins in the US? But there's another thing you can do which is dog cats. You know, dogs have very big litters. So I guess you could do that. It turns out the obstruction is also privacy. So the only place you could get data was somehow from Swedish dog kennels and kind of unfortunately it basically looks 50/50.
But the other one I really enjoyed was you can do this also in other settings. So is anyone a basketball fan?
Audience Member 46:58 ↗
Oh my god.
Ankur Moitra 47:00 ↗
I'm going to stop making sports references. No one. Yes. Okay. One. All right. So what you do is you know some basketball players you know on any given night they might be a great shooter and other nights they might be terrible. So again you get multiple flips right because they've taken many three-pointers that night and I want to know the population of biases for this individual player. So, if you take over the entire NBA and ask, you know, fit the population of means of their three-point shooting, how it varies over game by-game basis, who is the most consistent shooter?

10 more exchanges in this transcript

Sign in free to read the rest of this interview. No card required.

Sign in to read the full transcript

Cite this transcript

APA, MLA, BibTeX
APA

Moitra, A. (2026, October 13). Ankur Moitra @ Theory Lunch [Interview transcript]. Princeton TCS. CEOInterviews.AI. https://ceointerviews.ai/interview/3143460/

MLA

Ankur Moitra. "Ankur Moitra @ Theory Lunch." Princeton TCS, 13 Oct. 2026. Transcript, CEOInterviews.AI, https://ceointerviews.ai/interview/3143460/.

BibTeX
@misc{moitra2026_3143460,
  author       = {Ankur Moitra},
  title        = {Ankur Moitra @ Theory Lunch},
  howpublished = {Interview transcript, Princeton TCS. CEOInterviews.AI},
  year         = {2026},
  month        = {oct},
  url          = {https://ceointerviews.ai/interview/3143460/},
  note         = {Speaker-attributed transcript with timestamps}
}