Active multiple matrix completion with adaptive confidence sets

• URL: http://arxiv.org/abs/2605.02458v1
• Date: Mon, 04 May 2026 11:03:28 GMT
• Title: Active multiple matrix completion with adaptive confidence sets
• Abstract summary: We formulate a new multi-task active learning setting in which the learner's goal is to solve multiple matrix completion problems simultaneously.<n>Our main practical motivation is market segmentation, where the matrices represent different regions with different preferences of the customers.<n>We provide and analyze a new algorithm, MAlocate that is able to adapt to the unknown ranks of the different matrices.
• Score: 59.421761942386944
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we formulate a new multi-task active learning setting in which the learner's goal is to solve multiple matrix completion problems simultaneously. At each round, the learner can choose from which matrix it receives a sample from an entry drawn uniformly at random. Our main practical motivation is market segmentation, where the matrices represent different regions with different preferences of the customers. The challenge in this setting is that each of the matrices can be of a different size and also of a different rank which is unknown. We provide and analyze a new algorithm, MAlocate that is able to adapt to the unknown ranks of the different matrices. We then give a lower-bound showing that our strategy is minimax-optimal and demonstrate its performance with synthetic experiments.

Related papers

• Truncated Matrix Completion - An Empirical Study [7.912206996605676]
  Low-rank Matrix Completion describes the problem where we wish to recover missing entries of partially observed low-rank matrix.<n>We consider various settings where the sampling mask is dependent on the underlying data values, motivated by applications in sensing, sequential decision-making, and recommender systems.
  arXiv  Detail & Related papers  (2025-04-14T04:42:00Z)
• Matrix Diagonalization as a Board Game: Teaching an Eigensolver the Fastest Path to Solution [2.239917051803692]
  Matrix diagonalization is at the cornerstone of numerous fields of scientific computing. We show how reinforcement learning, using the AlphaZero framework, can accelerate Jacobi matrix diagonalizations. Our findings highlight the opportunity to use machine learning as a promising tool to improve the performance of numerical linear algebra.
  arXiv  Detail & Related papers  (2023-06-16T03:31:58Z)
• Survey of Matrix Completion Algorithms [3.42658286826597]
  Matrix completion problem has been investigated under many different conditions since Netflix announced the Netflix Prize problem. We are going to visit some of the matrix completion methods, mainly in the direction of passive and adaptive directions.
  arXiv  Detail & Related papers  (2022-04-01T05:44:47Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root and the inverse square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP), and the other method is to use Matrix Pad'e Approximants (MPA) A series of numerical tests show that both methods yield considerable speed-up compared with the SVD or the NS iteration.
  arXiv  Detail & Related papers  (2022-01-29T10:00:35Z)
• A Deep Generative Model for Matrix Reordering [26.86727566323601]
  We develop a generative model that learns a latent space of diverse matrix reorderings of a graph. We construct an intuitive user interface from the learned latent space by creating a map of various matrix reorderings. This paper introduces a fundamentally new approach to matrix visualization of a graph, where a machine learning model learns to generate diverse matrix reorderings of a graph.
  arXiv  Detail & Related papers  (2021-10-11T02:55:24Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  We show how to design learned sketches for the Hessian in the context of second order methods. We show empirically that learned sketches, compared with their "non-learned" counterparts, improve the approximation accuracy for important problems.
  arXiv  Detail & Related papers  (2021-02-24T14:50:59Z)
• Improved Knowledge Distillation via Full Kernel Matrix Transfer [21.533095275253466]
  Knowledge distillation is an effective way for model compression in deep learning. We decompose the original full matrix with Nystr"om method. Compared with the full matrix, the size of the partial matrix is linear in the number of examples.
  arXiv  Detail & Related papers  (2020-09-30T04:03:09Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  We consider a class of bandit algorithms that implement a regularized version of the well-known OFUL algorithm, where the regularization is a square euclidean distance to a bias vector. We show both theoretically and experimentally, that when the number of tasks grows and the variance of the task-distribution is small, our strategies have a significant advantage over learning the tasks in isolation.
  arXiv  Detail & Related papers  (2020-05-18T08:41:39Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

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.