CS Paper Radar

Nuclear Norm-Regularized Bayesian Matrix Completion

Calvin Tolbert

cs.LG stat.ML ·submitted 2026-09-24 16:29 UTC · v2

Abstract

Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.

Comment
40 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Optimal Nonconvex Matrix Completion

cs.LG math.NA ·2026-09-15 ·Jian-Feng Cai, Xiliang Lu, Juntao You
similarity 0.66
Abstract

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an $n\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with high probability from $O(μnr\log n\log(nκ))$ and $O(μnr\log n\log(2μrκ))$ observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

0.38

Singularities of Non-negative Matrix Factorization and their application to Bayesian inference

cs.LG stat.MLmath.ST ·2026-09-28 ·Naoki Hayashi, Yota Maeda, Yasushi Esaki
theory similarity 0.65
Abstract · 23 pages

Non-negative matrix factorization (NMF) is a singular statistical model whose Bayesian asymptotics are governed by the real log canonical threshold (RLCT). We study the local geometry of the factorization map and derive an upper bound for the RLCT of NMF. Let $H$ be the model inner dimension and $H_0$ the non-negative rank of the true $M\times N$ matrix. Assuming that the true matrix admits a strictly positive factorization of inner dimension $H_0$ in the interior of the parameter domain, we prove, for smooth positive priors, that $λ\leq \{(H-H_0)\min(M,N)+H_0(M+N-H_0)\}/2$. This bound strictly improves the previous bound when $H_0\geq3$. The proof uses a local analytic normal form that separates independent linear coordinates from a residual matrix product. When $H=H_0$ also equals the ordinary rank of the true matrix, we obtain the exact value $λ=H_0(M+N-H_0)/2$. Under the standard assumptions of singular learning theory, these results bound the leading coefficients of the expected Bayesian generalization error and the Bayesian free energy.

0.22

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.65
Abstract · 36 pages

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.

0.13

Fast rates in Bayesian online learning with approximate posteriors

cs.LG stat.ML ·2026-08-26 ·Ilsang Ohn
theory similarity 0.63
Abstract

Exact Bayes prediction enjoys fast predictive regret guarantees, but exact posterior updating or representation may be too costly for online use. We study when these statistical guarantees are preserved by computational approximations. We show that the cumulative price of posterior approximation can be governed by the interaction between the contraction radius of the exact Gibbs posterior and the Wasserstein distance between the approximate and exact posteriors. Our general theorem shows that whenever exact Bayes prediction achieves a fast regret bound, any approximate posterior method that tracks the exact posterior with sufficient accuracy inherits the same fast regret, up to an additive term determined by the approximation error. Three online learning examples are developed. For linear models with strongly convex regularized losses, a projected Langevin algorithm yields an approximate posterior that achieves logarithmic regret. For an infinite-dimensional canonical exponential family sequence model over a Sobolev ellipsoid, a prior-preserving truncation method attains the minimax predictive regret rate with sublinear memory and constant update cost per observation. For random-design Gaussian process (GP) regression, a sparse variational posterior with inducing variables achieves the same predictive regret rate as the exact GP, but at substantially lower computational cost.

0.44

Robust Latent Variable Graphical Models: Exact Recovery and Fundamental Limits

cs.IT stat.MLcs.LG ·2026-10-19 ·Chuansen Peng, Xiaojing Shen
theory similarity 0.62
Abstract

We study robust estimation of a Gaussian precision matrix that decomposes as a sparse matrix minus a symmetric, possibly indefinite, low-rank matrix, a structure that arises when latent-variable marginalization is combined with conditioning on linear measurements. The proposed convex estimator replaces the sample covariance by the centered Gaussian measure-transformed (MT) covariance, which preserves the signed graph of the sparse component under the nominal model, and penalizes the low-rank component by the nuclear norm of a congruence transform, an atomic norm that encodes structural side information. Our main result is a primal--dual witness theorem: under restricted invertibility and irrepresentability conditions on the Fisher information, the raw convex optimizer is unique, has no false edges, recovers the signs of all sufficiently strong edges, and has exactly the true rank and inertia. These conditions reduce to the graphical-lasso conditions when the low-rank part is absent, and we verify them from primitive incoherence and near-isotropy assumptions. Over a class on which they hold uniformly, we prove information-theoretic limits for Frobenius estimation, signed graph recovery, and inertia recovery. In particular, inertia recovery requires $N\gtrsim p/ν_{\min}^2$ samples, where $ν_{\min}$ is the smallest nonzero eigenvalue modulus of the low-rank part; the spectral beta-min condition of the witness theorem is necessary up to a $\sqrt{\log p}$ factor; and the Frobenius risk attains the minimax rate up to a factor $\sqrt{μ(1+\min\{d,r\})\log p}$, where $μ$ is the incoherence parameter, $d$ the maximal degree, and $r$ the rank. We further quantify robustness under Huber contamination, with a bias bound that is sharp for the MT functional and vanishes for remote outliers, and give a globally convergent linearized ADMM with closed-form updates.

0.23

Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials

cs.DS math.STmath.PR ·2026-09-07 ·Zhangsong Li
theory similarity 0.62
Abstract · 29 pages, 2 figures; extended the results and added a detailed description of AI usage

We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is \[ \boldsymbol{Y}=\frac{1}{\sqrt{n}} \boldsymbolθ \boldsymbolθ^{\top}+\boldsymbol{W}, \] where the coordinates of $\boldsymbolθ$ are independent with a common, fixed sub-Gaussian distribution $π_Θ$ satisfying $\mathbb E[Θ]\neq0$, and $\boldsymbol{W}$ is symmetric with independent standard Gaussian upper-triangular entries. For every such prior, we give an explicit finite-dimensional bound implying that every sequence of polynomial estimators of degree $D(n)=o(n^{1/60})$ has normalized mean-square error with limit inferior at least $\mathbb E[Θ^2]-q_{\mathsf{amp}}$, the limiting error of Bayes approximate message passing (AMP). This extends the constant-degree equivalence of Montanari and Wein~\cite{montanari2025equivalence} to growing degree under the same prior assumptions. Combined with their polynomial approximation of fixed-iteration AMP, the bound identifies the exact limiting low-degree MMSE whenever $D(n)\to\infty$ within this range. It thereby answers the growing-degree AMP-equivalence question discussed in~\cite{wein2025computational, maleki2026high} for nonzero-mean sub-Gaussian priors in the stated degree range. We also obtain a moment-dependent finite-dimensional lower bound for any nonzero-mean prior with all moments finite. The proof bounds low-degree MMSE using \emph{conditional} joint cumulants and a refined application of Jensen's inequality. The conditional cumulants are defined using an auxiliary Gaussian channel $\boldsymbol{R}$ calibrated to the AMP fixed point. This retains signal dependence that is lost in unconditional cumulant bounds and produces the cancellations needed for quantitative control as the degree grows.

0.19

Certified Bayesian optimal experimental design: from Expected Information Gain to Signal-to-Noise Ratio

cs.IT ·2026-09-26 ·Mohamed Doumbouya, Arthur Vidard, Olivier Zahm
code/datahot direction similarity 0.61
Abstract

Optimal experimental design is often formulated as the maximization of the Expected Information Gain (EIG), which measures the expected reduction in uncertainty about a parameter of interest after observing the data. For nonlinear forward models and nonGaussian priors, computing the EIG typically requires costly nested Monte Carlo estimators or sophisticated density-approximation techniques. In this work, we derive new upper and lower bounds on the EIG using dimensional logarithmic Sobolev inequalities. The proposed bounds are expressed in terms of signal-to-noise ratios (SNR), preserving the simple matrix-based structure of the EIG in the linear-Gaussian setting and depending solely on covariance matrices and Fisher information matrices. We introduce two families of bounds: conservative bounds, designed to retain the entire information content, and incremental bounds, that prioritize early information acquisition for sequential experimental design. When model gradients are available, we further derive computable approximations of the Fisher-information terms that require only a small number of gradient evaluations, yielding substantial computational savings. The tightness of these bounds is controlled by the nonlinearity of the forward model, and in the linear-Gaussian setting, these bounds recover the exact value of the EIG. By eliminating the nested-sampling bottleneck, the proposed framework offers a tractable and theoretically grounded alternative to direct EIG estimation for large-scale Bayesian experimental design, while retaining the interpretability of the SNR-based bounds.

0.41

Geometry-Aware Score-Repellent Monte Carlo

cs.LG stat.ML ·2026-11-06 ·Jie Hu, Lingyun Chen, Do Young Eun
top venuetheory similarity 0.61
Abstract · To appear at NeurIPS 2026

The recently proposed Score-Repellent Monte Carlo (SRMC) method improves MCMC sampling by tilting the target density $π$ in $\mathbb{R}^d$ with the factor $\exp(-α\,θ_n^\top s(x))$, where the score function $s(x) = \nabla_x \log π(x)$, and $θ_n$ is the score average from past samples. However, a single scalar repellence strength $α\ge0$ cannot handle both the steep and the flat directions in anisotropic energy landscapes at once. We introduce \emph{Geometry-Aware SRMC} (GA-SRMC), which generalizes the Euclidean alignment to $θ^\top M s(x)$ for any symmetric positive-definite matrix $M$. A stochastic-approximation central limit theorem under a trace constraint on $M$ identifies the trace-normalized inverse Fisher $M_{\rm opt}\propto S^{-1}$ as the unique minimizer of the worst-direction covariance bound, elevating the Fisher information $S=\text{Cov}_π(s,s)$ from a proposal-side preconditioner (e.g., FisherMALA, natural gradient) to the bound-optimal repulsion-side matrix, with a single online estimate $\widehat S_n$ serving both roles at no additional computational cost. The full-Fisher online metric $M_n$ converges almost surely to $M_{\rm opt}$ and satisfies a CLT, providing a theoretical guarantee for the online implementation of the GA-SRMC framework. On an $8$-target simulation spanning the condition number $κ\in[1.3,100]$ and dimension $d\in[2,785]$, GA-SRMC dominates SRMC in ESS by $\boldsymbol{4.3\times}$ on anisotropic Gaussian ($κ=100$) and $\boldsymbol{6.8\times}$ on MNIST under the MALA baseline, by $\boldsymbol{16\text{--}32\%}$ on three well-conditioned logistic-regression posteriors, and by up to $\boldsymbol{+48\%}$ under FisherMALA; gains peak on the most anisotropic targets, and posterior-mean MSE is lower than with SRMC in all $16$ full-Fisher implementations.

0.33