A Probabilistic Basis for Low-Rank Matrix Learning

• URL: http://arxiv.org/abs/2510.05447v1
• Date: Mon, 06 Oct 2025 23:26:56 GMT
• Title: A Probabilistic Basis for Low-Rank Matrix Learning
• Authors: Simon Segert, Nathan Wycoff,
• Abstract summary: We study the distribution with density $f(X)propto e-lambdaVert XVert_*$, finding many of its fundamental attributes to be analytically tractable via differential geometry.<n>We use these facts to design an improved MCMC algorithm for low rank Bayesian inference as well as to learn the penalty parameter $lambda$.
• Score: 2.1485350418225244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low rank inference on matrices is widely conducted by optimizing a cost function augmented with a penalty proportional to the nuclear norm $\Vert \cdot \Vert_*$. However, despite the assortment of computational methods for such problems, there is a surprising lack of understanding of the underlying probability distributions being referred to. In this article, we study the distribution with density $f(X)\propto e^{-\lambda\Vert X\Vert_*}$, finding many of its fundamental attributes to be analytically tractable via differential geometry. We use these facts to design an improved MCMC algorithm for low rank Bayesian inference as well as to learn the penalty parameter $\lambda$, obviating the need for hyperparameter tuning when this is difficult or impossible. Finally, we deploy these to improve the accuracy and efficiency of low rank Bayesian matrix denoising and completion algorithms in numerical experiments.

Related papers

• Efficiently Solving Discounted MDPs with Predictions on Transition Matrices [6.199300239433395]
  We study Discounted Markov Decision Processes (DMDPs) under a generative model.<n>We propose a novel framework to investigate how a prediction on the transition matrix can enhance the sample efficiency in solving DMDPs.
  arXiv  Detail & Related papers  (2025-02-21T09:59:46Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
  A generic online learning algorithm is developed for a class of ''monotone'' problems.<n>Our framework applies to several fundamental problems such as prophet inequality, Pandora's box, single-resource revenue management and posted pricing.
  arXiv  Detail & Related papers  (2023-12-24T07:46:37Z)
• Online non-parametric likelihood-ratio estimation by Pearson-divergence functional minimization [55.98760097296213]
  We introduce a new framework for online non-parametric LRE (OLRE) for the setting where pairs of iid observations $(x_t sim p, x'_t sim q)$ are observed over time. We provide theoretical guarantees for the performance of the OLRE method along with empirical validation in synthetic experiments.
  arXiv  Detail & Related papers  (2023-11-03T13:20:11Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  We show that Prospect, a gradient-based algorithm, enjoys linear convergence for smooth regularized losses. We also show that Prospect can converge 2-3$times$ faster than baselines such as gradient-based methods.
  arXiv  Detail & Related papers  (2023-10-21T00:03:54Z)
• 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)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Low-Rank Sinkhorn Factorization [45.87981728307819]
  We introduce an explicit factorization of low rank couplings as a product of textitsub-coupling factors linked by a common marginal. We prove the non-asymptotic stationary convergence of this algorithm and illustrate its efficiency on benchmark experiments.
  arXiv  Detail & Related papers  (2021-03-08T13:18:45Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Differentiable Linear Bandit Algorithm [6.849358422233866]
  Upper Confidence Bound is arguably the most commonly used method for linear multi-arm bandit problems. We introduce a gradient estimator, which allows the confidence bound to be learned via gradient ascent. We show that the proposed algorithm achieves a $tildemathcalO(hatbetasqrtdT)$ upper bound of $T$-round regret, where $d$ is the dimension of arm features and $hatbeta$ is the learned size of confidence bound.
  arXiv  Detail & Related papers  (2020-06-04T16:43:55Z)
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
  This paper establishes a precise high-dimensional theory for boosting on separable data. Under a class of statistical models, we provide an exact analysis of the universality error of boosting. We also explicitly pin down the relation between the boosting test error and the optimal Bayes error.
  arXiv  Detail & Related papers  (2020-02-05T00:24:53Z)

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.