PaperlayerView exact revision on arXiv

Source-linked AI summary

Nuclear Norm-Regularized Bayesian Matrix Completion

Calvin Tolbert

arXiv:2609.30078v1stat.MLcs.LG

TL;DR

Matrix completion methods often give point estimates without built-in uncertainty quantification, and a Bayesian nuclear-norm prior becomes log-concave when noise precision is known. The paper discretizes precision and uses thermodynamic integration to construct a sampler with an explicit non-asymptotic guarantee. It establishes a polynomial-time feasibility result, while noting that the resulting complexity is not intended for current problem scales.

  • Problem

    Nuclear-norm-regularized matrix completion often yields point estimates without built-in uncertainty quantification, while a fully Bayesian approach must handle unknown noise precision.

    Source: §1 · p. 1

  • Method

    The paper places a prior on precision, discretizes it, and uses thermodynamic integration with random-walk Metropolis to sample the joint posterior.

    Source: §1 · p. 2, §5 · p. 6

  • Results

    The paper gives an explicit non-asymptotic total-variation guarantee for its sampler, whose complexity is polynomial in the matrix dimensions and reciprocal target accuracy.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results establish that a polynomial-time Bayesian sampler for this model exists, as a feasibility result rather than a deployable algorithm at current scales.

    Source: §6 · p. 9

    The bound’s η4 denominator arises from Q, and whether Q can be tightened remains open.

    Source: §5 · p. 8

Abstract

from arXiv · show

Matrix completion, the problem of estimating missing entries in a matrix from noisily observed ones, underlies a diverse array of problems such as recommender systems and counterfactual outcome estimation in panel data. Many algorithms address the problem using regularized least squares, often with the nuclear norm as a regularizer, but this method yields a point estimate with no built-in uncertainty quantification. A Bayesian formulation is a natural alternative, and if the noise variance is known, the nuclear norm-based prior yields a log-concave posterior. Unfortunately, in practice, the noise variance will not be known a priori, so for a fully Bayesian approach, a prior must be imposed on it. We give the first sampler for this model with an explicit non-asymptotic guarantee: polynomial in the matrix dimensions and in the reciprocal of the target accuracy. Our technique is to discretize the distribution of the noise precision onto a grid and build a categorical posterior via thermodynamic integration. This extension is not specific to matrix completion and may be useful in other non-log-concave sampling problems where the non-log-concavity is restricted to a single variable and the joint distribution of the remaining variables is nonsmooth. Our contribution is a feasibility result: we show that a polynomial-time Bayesian sampler for this model exists at all, and the resulting complexity, while polynomial, is not intended as a deployable algorithm at current problem scales.

1 Introduction

Matrix completion methods often use nuclear-norm-regularized least squares but provide point estimates with limited uncertainty quantification. The paper gives a Bayesian sampler with an explicit non-asymptotic guarantee despite unknown noise precision, using thermodynamic integration and random-walk Metropolis.

1 Introduction

  • A prior on the unknown noise precision enables joint posterior sampling with an explicit non-asymptotic total-variation bound.The paper contrasts this with approaches that fix precision, use cross-validation, or integrate it out with Gibbs sampling without a non-asymptotic guarantee.Source: §1 · pp. 1–2
  • Thermodynamic integration replaces naïve importance reweighting, whose required sample count grows exponentially with observations as the likelihood tilt moves away from the prior.The estimator samples from the correctly tilted measure at each precision value.Source: §1 · p. 2
  • The paper extends random-walk Metropolis mixing analysis to smooth-plus-nonsmooth-Lipschitz potentials without requiring a proximal sampling oracle.The resulting bounds are polynomial in dimension and logarithmic in target accuracy, though conditioning depends exponentially on the ratio of the nonsmooth Lipschitz constant to smooth curvature.Source: §1 · p. 2
  • The work also asks whether random-walk Metropolis can obtain explicit non-asymptotic mixing bounds when the joint distribution is not strongly log-concave.The matrix-completion model serves as a testbed for this broader sampling question.Source: §1 · p. 2
  • The model assumes independent Gaussian residuals with mean zero and precision τ, the reciprocal of variance.The observations form a generally incomplete matrix, with unobserved entries denoted by □.Source: §1 · p. 2

2 Summary of existing models

Nuclear-norm regularization is used in matrix completion across applications including causal inference and recommender systems. Existing approaches differ in their assumptions, treatment of dependencies, and selection of regularization parameters.

2 Summary of existing models

  • Nuclear-norm regularization is used in matrix completion for applications including causal inference in panel data and recommender systems.The cited literature includes Negahban and Wainwright (2010), Athey et al. (2021), and Koren et al. (2009).Source: §2 · p. 3
  • Frequentist analyses may require incoherence, minimum sampling rates, or missing-completely-at-random assumptions, while Athey et al. (2021) allow time-series treatment dependency and propose cross-validation for λ.The paper says those frequentist error-control assumptions are not needed for its Bayesian sampler’s guarantee, which concerns reaching the posterior target.Source: §2 · p. 3

3 Regularization as Bayesian inference

The section connects regularized least-squares estimators with Bayesian maximum a posteriori estimation. It then explains how the Bayesian framing changes the assumptions needed for the paper’s sampling guarantee.

3.1 Regression

  • With known residual precision τ, no latent factors, and a likelihood supplied by the Central Limit Theorem, regularized least squares is the posterior negative log-density.This gives the estimator a maximum a posteriori interpretation.Source: §3.1 · p. 3

3.2 Latent factor models

  • The nuclear norm sums singular values and penalizes high-rank matrices, linking nuclear-norm regularization to a Bayesian latent-factor model.The section also gives a sparse-outlier extension with an entrywise 1-norm penalty and a Laplace prior on S.Source: §3.2 · p. 4
  • The sampler’s guarantee holds for the posterior induced by μ for any sampling mask Ω, without frequentist assumptions used to bound estimator error.The guarantee concerns reaching the posterior target, not how close its mode is to the truth.Source: §3.2 · p. 4

4 Our prior

The paper combines nuclear- and Frobenius-norm priors, random-walk Metropolis sampling, and a discretized prior on noise precision. The Frobenius term makes the latent-factor prior strongly log-concave, while the precision grid supports the later posterior computation.

4 Our prior

  • The prior combines nuclear-norm shrinkage for near-low-rankness with Frobenius-norm shrinkage for strong log-concavity and entrywise shrinkage.A user focused solely on low-rankness can set B large relative to λ.Source: §4 · p. 4
  • The residual precision receives a prior because it is generally unknown; the paper starts from the improper Jeffreys prior p(τ) ∝ 1/τ.The Jeffreys prior is invariant to monotone reparameterization, but its improper form would make the posterior improper, so the support is truncated.Source: §4 · pp. 4–5

4.1 Random-walk Metropolis

  • Random-walk Metropolis is selected for the nonsmooth prior because it needs potential evaluations rather than a proximal sampling step.The section contrasts it with samplers that do not meet the required high-accuracy setting; the paper’s broader mixing bound for smooth-plus-nonsmooth-Lipschitz targets depends exponentially on a conditioning ratio.Source: §4.1 · p. 5

4.2 Discretizing the precision

  • The prior on precision is discretized at logarithmically spaced quantiles, approximating it with a uniform categorical distribution over the grid.The grid has Q points, with each point chosen as a quantile of the prior.Source: §4.2 · p. 6

5 Our posterior

The section develops a sampler for the joint posterior over the precision and low-rank factor by approximating the precision’s marginal posterior on a grid. Its guarantees include a Wasserstein-distance result under the stated corollary setting, while tightening one factor in that bound remains open.

5 Our posterior

  • Thermodynamic integration estimates marginal log-likelihoods across candidate precision values, replacing a naïve importance-reweighting approach that can require exponentially many samples.The estimates induce a categorical distribution over the precision grid; the sampler then draws a precision and samples the low-rank factor conditionally.Source: §5 · pp. 6–7
  • The approach targets the joint posterior by first sampling the precision from the constructed marginal distribution, then sampling the low-rank factor conditioned on that precision.The section notes that general convergence-rate guarantees for Gibbs sampling across variable groups are difficult to obtain.Source: §5 · pp. 6–7
  • The observations are standardized and scaled to match the scale given by the prior.The text characterizes standardization as common in empirical studies, while specifying a prior-matched scaling here.Source: §5 · p. 8
  • Corollary 2 gives an n1n2η Wasserstein-distance guarantee under the setting of Corollary 1.The section relates this tolerance to average entrywise error, and notes that the η^4 denominator comes entirely from Q; how much Q can be tightened remains open.Source: §5 · p. 8

6 Numerical illustration

The illustrations examine whether thermodynamic integration avoids importance-sampling degeneracy and whether its practical-budget posterior agrees with heuristic Gibbs sampling.

6 Numerical illustration

  • Across N of roughly 2–200, naive importance sampling’s effective-sample-size fraction collapses by about two orders of magnitude, while thermodynamic integration’s relative Monte Carlo error stays bounded and improves at comparable budget.The two panels use different metrics and units, so their values should not be compared on one axis.Source: §6 · pp. 9–10, Figure 1 · p. 10
  • At n = 12 on a rank-2 ground truth with λ = 0.2, the practical-budget samplers’ posterior-mean gap for L is smaller than each method’s split-half Monte Carlo noise.This supports agreement with the heuristic Gibbs target, not the stated convergence rate.Source: §6 · p. 10, Figure 2 · p. 11
  • Three implementation checks—the symmetry-implied zero mean, a Brascamp–Lieb variance bound, and an expected-risk bound—held empirically.Full details are in the supplementary code.Source: §6 · p. 10

A Chi-squared mixing bounds for high-accuracy samplers

This appendix develops mixing bounds for random-walk Metropolis on strongly convex smooth-plus-nonsmooth-Lipschitz targets, then applies concentration and moment bounds to control initialization and thermodynamic integration.

A.1 Setup

  • The target is a Metropolis-sampled distribution with potential F + G, where F is strongly convex and smooth, while G is convex, nonsmooth, and Lipschitz.The section frames this composite setting as harder than the smooth, strongly convex case.Source: §A.1 · p. 14

A.2 The general recipe

  • The mixing analysis follows an isoperimetric-profile recipe and bounds close-coupling by separating proposal stability from a lower bound on acceptance probability.These two components provide the ingredients for the coupling parameters used in the mixing bound.Source: §A.2 · p. 15

A.3 The target-side ingredient

  • Strong convexity gives the target a Gaussian isoperimetric profile scaled by the square root of its curvature parameter.Source: §A.3 · p. 15

A.4 The algorithm-side ingredients

  • For random-walk Metropolis, Gaussian proposal stability is bounded through a KL identity and Pinsker’s inequality, while a growth bound supports the acceptance-probability analysis.Source: §A.4 · p. 16

A.5 Assembling the mixing bound

  • The assembled bound chooses coupling distance and TV tolerance from a lower bound on acceptance probability, then tunes a parameter to reduce the required step count.The resulting bound pays a conditioning cost for using the general growth-bound approach instead of a proximal method tailored to the nuclear norm.Source: §A.5 · p. 17

A.6 A bound on the initial chi-squared divergence

  • For the applications considered, a tractable initialization measure can bound the initial chi-squared divergence; strong log-concavity and concentration inequalities support this control.Source: §A.6 · pp. 17–18

B Some moment bounds and transport inequalities

B.1 The thermodynamic integration step

This section bounds thermodynamic integration’s error by separating deterministic quadrature and discretization errors from random estimation error, then controlling the latter across grid points.

B.1 The thermodynamic integration step

  • Thermodynamic integration estimates the log-normalizing-constant change using derivatives of the log partition function, with moment bounds supplying derivative and curvature controls.The section records a uniform centered fourth-moment bound for R across the tilted family.Source: §B.1 · pp. 20–21
  • Strong log-concavity and Gaussian concentration control moments of the Frobenius norm under each tilted measure, which are used to bound moments of R.Source: §B.1 · p. 21
  • The estimator’s error is split into fixed-expectation, deterministic quadrature, and random terms; only the random term requires probabilistic control.Source: §B.1 · p. 22
  • Fresh independent chain batches at each grid point make the stochastic errors a martingale, allowing a maximal inequality to bound their largest cumulative deviation.Combining that bound with the deterministic terms yields the claimed thermodynamic-integration bound.Source: §B.1 · p. 23

C Proofs of the main results

The proofs combine sampler convergence with bounds on how changes in the precision distribution affect the posterior. They use total variation for Theorem 1 and Wasserstein distance for Theorem 2.

C.1 Proof of Theorem 1

  • Theorem 1’s proof bounds the posterior error by separating sampler convergence from the error in the discretized precision distribution, using total variation and a Wasserstein-1 bound.Source: §C.1 · p. 24

C.1 and C.2 Proofs

  • In both proofs, monotonicity of the expected risk under tilted measures and the earlier moment and thermodynamic-integration bounds control the residual precision-distribution error.Source: §C.1 · p. 24, §C.2 · pp. 25–26

C.2 Proof of Theorem 2

  • Theorem 2’s proof follows a corresponding decomposition using Wasserstein distance and Talagrand’s T1 inequality to control changes across precision values.Source: §C.2 · pp. 25–26

C.3 Proof of Corollary 1

Under the standardization regime, A(t) scales as Θ(n1n2). The proof sets M=1 because its term declines slowest, then considers the RWM steps needed under ε⋆=Θ(η).

C.3 Proof of Corollary 1

  • Under the standardization regime, A(t)=Θ(n1n2).Source: §C.3 · p. 26
  • The proof sets M=1 because the M-term declines slowest, then chooses Q to bring overall TV distance below η.Source: §C.3 · p. 26
  • When ε⋆=Θ(η), the proof states the number of RWM steps needed.Source: §C.3 · p. 26

C.4 Proof of Corollary 2

When B=Θ(1), Theorem 2’s convergence result has the same big-O terms as Theorem 1’s; the proof obtains it by replacing η with n1n2η in Corollary 1’s result.

C.4 Proof of Corollary 2

  • For B=Θ(1), Theorem 2’s convergence result has the same big-O terms as Theorem 1’s, obtained by replacing η with n1n2η in Corollary 1.Source: §C.4 · p. 26
Loading 2609.30078v1…