Doubly robust nearest neighbors in factor models

In the vast landscape of modern data, information is rarely complete. Whether tracking the health of a patient over months, predicting what a customer might buy next, or understanding how a product performs across different regions, researchers often face a matrix of numbers with significant gaps. Some entries are missing because a sensor failed, a user skipped a survey, or a treatment was not applied. The challenge is to fill in these blanks with enough accuracy to make reliable decisions. To do this, statisticians often rely on the idea that the world is governed by hidden patterns. They assume that the data we see is shaped by a few underlying forces—like a user's general preference or a specific time of day—that repeat across the dataset. If we can find these hidden patterns, we can guess what the missing numbers should be.

For decades, a popular way to make these guesses has been to look for "neighbors." If you want to know what a specific user would think of a product, you look at other users who are very similar to them and see what those neighbors liked. This is the logic of nearest neighbors. However, this method has a fatal flaw: it only works if you can actually find a good neighbor. If the user in question is unique, or if the time period is unusual, the method fails because there is no one similar enough to copy. The new work by Raaz Dwivedi and his colleagues addresses this vulnerability by creating a smarter way to combine two different types of neighbor searches. Instead of relying on just one type of similarity, their new method, called Doubly Robust Nearest Neighbors, succeeds as long as there is either a similar user or a similar time period available. If both exist, the method becomes even more precise, offering a level of accuracy that was previously out of reach.

The researchers were working with a specific mathematical puzzle known as matrix completion, where the goal is to reconstruct a full grid of data from a scattered collection of observed points. They focused on a scenario where the data is generated by a hidden function that mixes two sets of factors: one set representing the "units" (like people or products) and another representing "time" (like days or hours). In this setup, the value at any specific intersection is determined by how the unit's hidden traits interact with the time's hidden traits. The standard approach involves two separate strategies. The first, called unit-nearest neighbors, looks for other rows in the data that look like the target row. The second, called time-nearest neighbors, looks for other columns that look like the target column. Both strategies work well when the data is dense with similar patterns, but they struggle when the data is sparse or when the target is an outlier.

The team realized that these two strategies were not mutually exclusive but could be combined to cover each other's weaknesses. They developed a new estimator that effectively asks two questions at once: "Do I have a similar user?" and "Do I have a similar time?" If the answer to either question is yes, the new method produces a reliable estimate. This is what they mean by "doubly robust." It is robust to the failure of the first strategy as long as the second works, and vice versa. The researchers proved mathematically that if both strategies find good neighbors, the new method does not just average their results; it multiplies their strengths. This leads to a dramatic improvement in accuracy, reducing the error rate significantly more than either method could achieve alone. In technical terms, this improvement translates to a near-quadratic reduction in error, meaning the estimate becomes much sharper with very little extra data.

To verify their theory, the researchers ran extensive simulations using synthetic data that mimicked real-world scenarios, including both simple linear relationships and more complex, non-linear ones. They tested their new method against the traditional unit-nearest neighbors, time-nearest neighbors, and other standard matrix completion algorithms. The results were clear: the new method consistently outperformed the others. In cases where the data was generated by a simple linear rule, the new method reduced the error by a factor that grew with the size of the dataset, far surpassing the performance of the older methods. Even in more complex scenarios where the relationships between factors were non-linear, the new approach maintained a significant advantage, often matching or beating the best of the traditional methods while avoiding their worst-case failures.

The team also applied their method to a real-world dataset from a mobile health clinical trial called HeartSteps. In this study, participants wore activity trackers and received random notifications to encourage physical activity. The goal was to estimate how many steps a participant would take in an hour if they received a notification versus if they did not, even for times when that specific condition was not observed. The data was naturally sparse because notifications were sent randomly. When the researchers used their new Doubly Robust Nearest Neighbors method to fill in these gaps, the estimates were more accurate than those produced by the standard methods. The error distribution was tighter, meaning the guesses were consistently closer to the true values. This demonstrated that the method works not just in theory or on computer-generated numbers, but on messy, real-world data where missing information is the norm.

A key insight from the study was the trade-off involved in how the data is processed. To prove their mathematical guarantees, the researchers initially split the data into separate chunks to avoid a specific type of statistical bias. However, in their practical experiments, they found that using the entire dataset without splitting it actually produced better results. While splitting the data helped with the theoretical proof, it reduced the amount of information available to find neighbors, which increased the noise in the estimate. In practice, the benefit of having more data to find similarities outweighed the theoretical risk of bias, suggesting that for real-world applications, using all available information is often the superior choice.

The implications of this work extend beyond just filling in missing numbers. The ability to make reliable estimates even when data is sparse or heterogeneous is crucial for fields like personalized medicine and targeted advertising. In these fields, decisions are often made for individuals who are unique or for situations that have not been seen before. If a method fails because it cannot find a perfect match, the consequences can be poor recommendations or ineffective treatments. By ensuring that the estimation process remains robust even when one type of similarity is missing, this new approach provides a safety net for decision-making. It allows systems to learn from the data that is available, rather than failing because the data is not perfectly structured.

The researchers also noted that their approach could be extended to more complex data structures, such as three-dimensional tensors, which might involve units, time, and a third factor like a specific intervention or location. The logic of combining multiple sources of similarity to create a robust estimate could be applied there as well, potentially leading to "triply robust" methods. This suggests a broader path forward for statistical inference, where the focus shifts from finding a single perfect match to intelligently combining multiple imperfect sources of information. The work stands as a demonstration that by rethinking how we combine simple, intuitive ideas like "finding a neighbor," we can build tools that are far more resilient and accurate than the sum of their parts.

Ultimately, this paper offers a practical solution to a common problem: how to make sense of incomplete information. It shows that we do not need to wait for perfect data or a perfect match to make a good guess. By acknowledging that different types of similarities exist and learning to use them together, we can build models that are more reliable in the face of uncertainty. The method is simple in its logic but powerful in its execution, providing a new standard for how we handle missing data in a world that is increasingly driven by large, complex datasets.