Adaptively-weighted Nearest Neighbors for Matrix Completion

• URL: http://arxiv.org/abs/2505.09612v1
• Date: Wed, 14 May 2025 17:59:17 GMT
• Title: Adaptively-weighted Nearest Neighbors for Matrix Completion
• Abstract summary: AWNN is an adaptively weighted nearest neighbor method for performing matrix completion.<n>We provide theoretical guarantees for the proposed method under minimal assumptions and support the theory via synthetic experiments.
• Score: 6.6157730528755065
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this technical note, we introduce and analyze AWNN: an adaptively weighted nearest neighbor method for performing matrix completion. Nearest neighbor (NN) methods are widely used in missing data problems across multiple disciplines such as in recommender systems and for performing counterfactual inference in panel data settings. Prior works have shown that in addition to being very intuitive and easy to implement, NN methods enjoy nice theoretical guarantees. However, the performance of majority of the NN methods rely on the appropriate choice of the radii and the weights assigned to each member in the nearest neighbor set and despite several works on nearest neighbor methods in the past two decades, there does not exist a systematic approach of choosing the radii and the weights without relying on methods like cross-validation. AWNN addresses this challenge by judiciously balancing the bias variance trade off inherent in weighted nearest-neighbor regression. We provide theoretical guarantees for the proposed method under minimal assumptions and support the theory via synthetic experiments.

Related papers

• Harnessing the Potential of Optimizing Data Mixtures via Bayesian Domain Reweighting [63.86964530167364]
  This paper presents a Bayesian domain weighting method to infer the weights from a Dirichlet distribution via introducing Gamma prior information learned from observations.<n> Experimental results demonstrate that proposed method could achieve stable and efficient domain weights learning, and identifies optimal mixtures while consuming substantially less data than search-based function-fitting methods, revitalizing optimization-based domain weighting for large-scale applications.
  arXiv  Detail & Related papers  (2026-07-30T09:41:02Z)
• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
  arXiv  Detail & Related papers  (2025-11-27T06:16:17Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [68.43987626137512]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• N$^2$: A Unified Python Package and Test Bench for Nearest Neighbor-Based Matrix Completion [6.526117652113461]
  This paper introduces N$2$, a unified Python package and testbed that consolidates a broad class of NN-based methods.<n>We also release a benchmark suite of real-world datasets, from healthcare and recommender systems to causal inference.<n>Our experiments demonstrate that while classical methods excel on idealized data, NN-based techniques consistently outperform them in real-world settings.
  arXiv  Detail & Related papers  (2025-06-04T17:04:34Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [56.92178753201331]
  We tackle average-reward infinite-horizon POMDPs with an unknown transition model.<n>We present a novel and simple estimator that overcomes this barrier.
  arXiv  Detail & Related papers  (2025-01-30T22:29:41Z)
• Equivariant Deep Weight Space Alignment [54.65847470115314]
  We propose a novel framework aimed at learning to solve the weight alignment problem. We first prove that weight alignment adheres to two fundamental symmetries and then, propose a deep architecture that respects these symmetries.
  arXiv  Detail & Related papers  (2023-10-20T10:12:06Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• pNNCLR: Stochastic Pseudo Neighborhoods for Contrastive Learning based Unsupervised Representation Learning Problems [7.967118716309239]
  Nearest neighbor (NN) sampling provides more semantic variations than pre-defined transformations for self-supervised learning (SSL) based image recognition problems. We show that the quality of the support set plays a crucial role in any nearest neighbor based method for SSL. We introduce pseudo nearest neighbors (pNN) to control the quality of the support set and employ a sampling strategy to improve the performance.
  arXiv  Detail & Related papers  (2023-08-14T07:35:43Z)
• Online Laplace Model Selection Revisited [0.6355355626203273]
  Online variants of the Laplace approximation have seen renewed interest in the Bayesian deep learning community. This work re-derives online Laplace methods, showing them to target a variational bound on a mode-corrected variant of the Laplace evidence. We demonstrate that these optima are roughly attained in practise by online algorithms using full-batch gradient descent on UCI regression datasets.
  arXiv  Detail & Related papers  (2023-07-12T11:36:27Z)
• Adaptive Nearest Neighbor Machine Translation [60.97183408140499]
  kNN-MT combines pre-trained neural machine translation with token-level k-nearest-neighbor retrieval. Traditional kNN algorithm simply retrieves a same number of nearest neighbors for each target token. We propose Adaptive kNN-MT to dynamically determine the number of k for each target token.
  arXiv  Detail & Related papers  (2021-05-27T09:27:42Z)
• Canny-VO: Visual Odometry with RGB-D Cameras based on Geometric 3D-2D Edge Alignment [85.32080531133799]
  This paper reviews the classical problem of free-form curve registration and applies it to an efficient RGBD visual odometry system called Canny-VO. Two replacements for the distance transformation commonly used in edge registration are proposed: Approximate Nearest Neighbour Fields and Oriented Nearest Neighbour Fields. 3D2D edge alignment benefits from these alternative formulations in terms of both efficiency and accuracy.
  arXiv  Detail & Related papers  (2020-12-15T11:42:17Z)
• Effective multi-view registration of point sets based on student's t mixture model [15.441928157356477]
  This paper proposes an effective registration method based on Student's t Mixture Model (StMM) It is more efficient to achieve multi-view registration since all t-distribution centroids can be obtained by the NN search method. Experimental results illustrate its superior performance and accuracy over state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-12-13T08:27:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.