Doubly robust nearest neighbors in factor models

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Doubly robust nearest neighbors in factor models".

Jane: The paper was written by Raaz Dwivedi, Caleb Chin, Sabina Tomkins, Predrag Klasnja, Susan Murphy et al. from Harvard University and Massachusetts Institute of Technology and University of Michigan.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: Alright, welcome back to the show, everyone! Today we're digging into a fresh arXiv paper that's got a mouthful of a title: "Doubly Robust Nearest Neighbors in Factor Models." Jane, I gotta say, just reading that title made me think of two things — old-school recommendation algorithms and a statistical superpower.

Jane: Tom, you're not wrong on either count. Let's unpack it. The paper comes from a big team — folks at Harvard, MIT, and the University of Michigan. And the core problem is something we all bump into daily: missing data. Think of a streaming service where you know what some users watched, but not all of them, and you want to guess what a specific person would rate a specific movie.

Tom: Right, and that's the "factor model" part. The idea is that there's some hidden reason — like a user's taste and a movie's style — that determines the rating. But here's the catch: the authors are dealing with a non-linear relationship between those hidden factors, which is way more realistic than the simple linear stuff.

Jane: Exactly. And "nearest neighbors" is the classic fix. You find similar users or similar movies and average their ratings. But the paper's title says "doubly robust," which is the clever twist. It means the method works even if you only have good neighbors on one side — say, similar users but no similar movies.

Tom: So it's like having two flashlights in a dark room. If one dies, you still have light from the other. But if both work, you get a much clearer picture. That's the gist of the "doubly robust" part — it's not just a backup; it actually combines both sources to do better than either alone.

Jane: And that's a big deal for real-world applications, not just movies. The paper mentions digital health, like deciding when to send a reminder to a patient. You might have lots of similar patients but few similar time points, or vice versa. This method handles both gracefully.

Tom: So, the title is a promise: robust to missing neighbors, and robust in a way that improves accuracy. I'm already excited to see how they pull it off mathematically. What do you think the actual algorithm looks like?

Jane: Well, Tom, that's exactly what we're going to dig into next. The paper doesn't just wave its hands; it gives a concrete recipe. And trust me, the recipe is surprisingly intuitive once you see it.

Paper discussion segment 2: Tom: So, Jane, we've got the title and the big idea. Now let's talk about the actual method. The paper introduces something called the DR-NN estimate, and I have to say, the construction is almost elegant in its simplicity.

Jane: It really is. So, imagine you want to estimate the outcome for user *i* at time *t*. The unit-NN approach finds similar users and averages their outcomes at time *t*. The time-NN approach finds similar times and averages user *i*'s outcomes at those times. Each of these has a bias — they're approximations.

Tom: And the DR-NN estimate is like a clever correction. It takes the time-NN estimate, but then subtracts a bias term that's estimated using the unit neighbors. And symmetrically, it can be seen as correcting the unit-NN estimate using the time neighbors. The paper shows that this correction makes the bias much smaller.

Jane: Right. In the paper, they show that for a simple bilinear model, the error of the DR-NN estimate is roughly the *product* of the errors of the two vanilla approaches, not the sum. That's a huge difference. If each vanilla method has an error of, say, zero point one, the product is zero point zero one, which is a hundredfold improvement.

Tom: And that's not just a theoretical trick. The paper proves it with non-asymptotic bounds — that's math-speak for "guarantees that hold with high probability for finite data, not just when you have infinite data." They also show that if one of the vanilla methods is useless, the DR-NN still performs as well as the other one. That's the "doubly robust" property in action.

Jane: Exactly. And they don't stop there. They also provide a confidence interval for the estimate, which is crucial for decision-making. If you're a doctor deciding on a treatment, you don't just want a point estimate; you want to know how uncertain it is.

Tom: And the confidence interval is also narrower than the vanilla ones, again by roughly a quadratic factor. So you get better estimates and tighter uncertainty. That's a win-win.

Jane: But, Tom, I should mention that the paper does make some assumptions. The noise has to be bounded, and the missingness is completely at random. Those are standard in the field, but they're worth keeping in mind.

Tom: Sure, but the authors are pretty upfront about that. And they show that the method is still a big step forward. Now, I'm curious about the practical side. How does this actually perform in the examples they give?

Jane: That's the perfect segue to our next segment. They run through a couple of concrete examples — one with discrete factors and one with continuous factors — and the improvements are pretty striking.

Paper discussion segment 3: Tom: So, Jane, let's get into the concrete numbers. The paper gives two main examples. First, the discrete case, where users and times come from a finite set of types. Second, the continuous case, where the factors are drawn from a uniform distribution.

Jane: Right. In the discrete case, with a constant observation probability, the DR-NN error scales like M over N, where M is the number of types and N is the number of users. That's a parametric rate — it decays as fast as possible. The vanilla unit-NN, on the other hand, scales like one over the square root of N plus M over N. So the DR-NN is a quadratic improvement in the leading term.

Tom: And in the continuous case, it's even more interesting. The vanilla NN error scales like N to the power of negative two over (d+two), where d is the dimension of the latent factors. The DR-NN error scales like N to the power of negative four over (d+four). For a fixed dimension, that's a much faster decay.

Jane: Let's put that in plain terms. If d is, say, four the vanilla error decays like N to the minus one-third, while the DR-NN error decays like N to the minus one-half. That's the difference between needing a thousand users versus a hundred users to get the same accuracy.

Tom: And that's not just a theoretical curiosity. The paper also shows that the confidence intervals shrink accordingly. So you get better point estimates and tighter intervals, which is exactly what you want in applications like personalized medicine or recommender systems.

Jane: But, Tom, there's a subtlety. The paper shows that the DR-NN is never worse than the better of the two vanilla methods. But to get the full quadratic improvement, you need both unit and time neighbors to be reasonably good. If one is terrible, you still get the performance of the other.

Tom: That's the "doubly robust" property we talked about. It's like having a car with two engines. If one fails, you can still drive on the other. But if both work, you get twice the speed. And the paper proves this rigorously, not just with simulations.

Jane: And they also extend the analysis to non-linear factor models, which is a big deal. The bilinear case is nice, but real-world data is rarely that simple. The paper shows that the DR-NN still provides a significant improvement, though the gains are a bit more modest.

Tom: So, the takeaway is that this isn't just a tweak. It's a fundamentally better way to combine information from two axes of a matrix. And the math is solid. I'm really impressed by the depth of the analysis.

Jane: Me too. And it makes me wonder about the broader impact. We've got a method that's simple to implement, has strong guarantees, and works in realistic settings. That's a recipe for adoption.

Conclusion: Tom: Alright, Jane, let's wrap this up. We've been talking about "Doubly Robust Nearest Neighbors in Factor Models" from Harvard, MIT, and Michigan. And I think the big takeaway is that this isn't just a new estimator; it's a new way of thinking about robustness in matrix completion.

Jane: Absolutely. The paper shows that by combining unit and time neighbors in a clever way, you get an estimate that's never worse than the best of the two vanilla approaches, and often much better. The math is rigorous, the examples are concrete, and the potential applications are everywhere — from recommender systems to digital health.

Tom: And let's not forget the confidence intervals. They're tighter, which means better decision-making under uncertainty. That's the kind of thing that can actually change practice.

Jane: Right. And while the paper makes some standard assumptions, like missingness at random, the core idea is robust enough that it's likely to inspire follow-up work in more complex settings, like adaptive experiments or causal panel data.

Tom: So, we're saying goodbye to this paper, but not to the ideas. I'm already thinking about how this could be extended to tensors or to settings with side information.

Jane: Definitely. But for now, we've got a solid understanding of a really clever piece of work. Thanks for joining us, everyone. We'll be back soon with the next paper.

Tom: Until then, keep your neighbors close, and your doubly robust ones closer. See you next time!