Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling

• URL: http://arxiv.org/abs/2403.00184v1
• Date: Thu, 29 Feb 2024 23:24:43 GMT
• Title: Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
• Authors: Xumei Xi, Christina Lee Yu and Yudong Chen
• Abstract summary: We show that it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities.
• Score: 10.824999179337558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-rank matrix completion concerns the problem of estimating unobserved entries in a matrix using a sparse set of observed entries. We consider the non-uniform setting where the observed entries are sampled with highly varying probabilities, potentially with different asymptotic scalings. We show that under structured sampling probabilities, it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. In particular, we prove error upper bounds customized to each entry, which match the minimax lower bounds under certain conditions. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities. We provide numerical experiments that confirm our theoretical findings.

Related papers

• Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows [9.631640936820126]
  Matrix completion tackles the task of predicting missing values in a low-rank matrix based on a sparse set of observed entries. We introduce a matrix completion algorithm based on network flows in the bipartite graph induced by the observation pattern. Our results show that the minimax squared error for recovery of a particular entry in the matrix is proportional to the effective resistance of the corresponding edge in the graph.
  arXiv  Detail & Related papers  (2024-09-06T02:01:03Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Entrywise Inference for Missing Panel Data: A Simple and Instance-Optimal Approach [27.301741710016223]
  We consider inferential questions associated with the missing data version of panel data induced by staggered adoption. We develop and analyze a data-driven procedure for constructing entrywise confidence intervals with pre-specified coverage. We prove non-asymptotic and high-probability bounds on its error in estimating each missing entry.
  arXiv  Detail & Related papers  (2024-01-24T18:58:18Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Matrix Completion from General Deterministic Sampling Patterns [28.116011361245224]
  We establish theoretical guarantee for the exact and approximate low-rank matrix completion problems. We show that the algorithm can be successful as the observation graph is well-connected and has similar node degrees.
  arXiv  Detail & Related papers  (2023-06-04T07:01:31Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Pure Exploration and Regret Minimization in Matching Bandits [19.205538784019936]
  We prove that it is possible to leverage a rank-1 assumption on the adjacency matrix to reduce the sample complexity. Finding an optimal matching in a weighted graph is a standard problem.
  arXiv  Detail & Related papers  (2021-07-31T12:37:51Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion [2.0257616108612373]
  We deal with matrix compressed sensing, including lasso as a partial problem, and matrix completion. We propose a simple unified approach based on a combination of the Huber loss function and the nuclear norm penalization.
  arXiv  Detail & Related papers  (2020-10-25T02:32:07Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

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.