CS Paper Radar

Geometry-Aware Score-Repellent Monte Carlo

Jie Hu, Lingyun Chen, Do Young Eun

cs.LG stat.ML ·submitted 2026-11-06 02:49 UTC · v1
top venuetheory

Abstract

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.

Comment
To appear at NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

cs.LG stat.MLmath.NAmath.OC+1 ·2026-09-11 ·Xinchen Du, Elizaveta Rebrova, Michał Dereziński, Sen Na
theory similarity 0.61
Abstract · 52 pages, 3 figures, 4 tables

We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and-project solver (GAS), thereby mitigating the computational bottleneck of classical second-order methods. The GAS solver improves upon vanilla, unaccelerated sketch-and-project solvers by achieving accelerated convergence through Nesterov momentum updates, and accommodates a flexible projection metric whose proper choice further reduces computational cost. Building on this design, we establish asymptotic normality of the averaged sketched Newton iterates and characterize their limiting covariance matrix. The resulting covariance recovers that of the unaccelerated sketched Newton method under a specific choice of acceleration parameters, converges more rapidly (in the number of sketching steps) to the minimax-optimal covariance in general, and is smaller than that of the last iterate produced by the accelerated method. Finally, we strengthen these results by establishing a functional central limit theorem for the Newton iterates, which allows us to bypass explicit covariance estimation and develop an online inference procedure based on random scaling. Specifically, we construct a pivotal test statistic by appropriately rescaling the averaged iterates, so that its limiting distribution is free of any unknown parameters, enabling asymptotically valid online inference. Numerical experiments demonstrate superior performance of the proposed inference procedure.

0.34

Penalized Nonreversible Langevin for Constrained Sampling

cs.LG stat.MLmath.PR ·2026-09-21 ·Pervez Ali, Weihao Dong, Xiaoyu Wang
similarity 0.61
Abstract · 68 pages, 8 figures

We propose penalized nonreversible Langevin algorithms for sampling from $π(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrtη)$ neighborhood, where $η$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.

0.17

Nuclear Norm-Regularized Bayesian Matrix Completion

cs.LG stat.ML ·2026-09-24 ·Calvin Tolbert
similarity 0.61
Abstract · 40 pages, 7 figures

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.

0.26

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in $\ell_p$ Geometries

cs.LG math.OCstat.ML ·2026-11-16 ·Zhengyun Nie, Anant Shyam, Brian Bullins
similarity 0.61
Abstract

We consider the fundamental problem of parallel stochastic convex optimization (SCO), whose aim is to approximately minimize a convex objective when given the ability to query a moment-bounded stochastic gradient oracle multiple times in parallel per round. Whereas most previous results have focused on the variance-bounded Euclidean ($\ell_2$-norm) setting, meaning the objective is Lipschitz with respect to the $\ell_2$-norm over an $\ell_2$-bounded feasible set in $\mathbb{R}^d$, in this work we study parallel SCO in $\ell_p$ settings for $2 \le p < \infty$ under a heavy-tailed noise model. We begin by introducing a new class of $\ell_p$-optimal-distance-convergence (ODC$_p$) algorithms, drawing on prior stochastic bias-reduced techniques [ACJ+21], which combine with multilevel Monte Carlo methods to efficiently estimate the optimum of uniformly convex objectives. As a consequence of our ODC$_p$ algorithms, we first establish rates for projection-efficient $\ell_p$-Lipschitz optimization, composite convex minimization, and efficient $\ell_p$-proximal point estimation. Combining our ODC$_p$ algorithms with a new $\ell_p$-generalized Gaussian-based stochastic gradient estimator ($p$-GREG), we provide two efficient $\ell_p$ parallel algorithms, EpochDA and $\ell_p$-AC-SA, which achieve optimization error $ε> 0$ with at most $\tilde{O}(d^{\frac{p}{2p + 2}} ε^{-\frac{p}{p + 1}})$ query depth, improving upon the sequential heavy-tailed stochastic query depth of $O(ε^{-p})$ for $ε\leq \tilde{O}(d^{-1/(2p)})$. We also establish dimension-dependent lower bounds of $Ω\bigl(\min\{ε^{-p},d^{p/(3p-2)}\}\bigr)$ adaptive rounds for nonsmooth convex optimization over a subset of the unit $\ell_p$ ball. Our results improve upon the $Ω(\min\{ε^{-p},ε^{2/3}d^{1/3}\})$ bounds of [DG19], when adapted to the same feasible set.

0.11

A Free Lunch: Gradient Averaging Achieves Optimal Statistical Efficiency in Newton Sketch

cs.LG stat.MLmath.OCstat.CO ·2026-11-18 ·Haoxuan Wang, Jianliang Ye, Sen Na
theory similarity 0.60
Abstract · 58 pages, 5 figures, 6 tables

We study statistical inference for online sketched Newton methods, in which each Newton system is approximately solved by an inner randomized sketching solver. Existing work reveals a computational--statistical trade-off: the sketching solver (and its accelerated variants) reduces the per-step cost of Newton methods from $O(d^3)$ to $O(d^2)$, but the randomness introduced by sketching also inflates the limiting covariance of both the last and the averaged Newton iterates. In this work, we address this trade-off via gradient averaging. We show that simply replacing the stochastic gradient with a moving average at each step can mitigate, and in some cases eliminate, the trade-off in Newton sketch. Importantly, gradient averaging requires no additional oracle evaluations and leaves the contraction bound of the inner sketching solver unchanged. In particular, we prove that the last sketched Newton iterate with gradient averaging attains a limiting covariance no larger than that without gradient averaging, while the averaged iterate even attains the minimax optimal limiting covariance, matching that of the exact Newton method. To our knowledge, this is the first analysis showing that randomness introduced to improve computational efficiency need not compromise statistical efficiency as long as proper gradient estimates are used. The key analytical challenge is that gradient averaging destroys the crucial martingale difference structure underlying central limit theorem arguments. We overcome this challenge by analyzing the coupled two-timescale recursions governing the iterate and the gradient estimator. Numerical experiments on linear and logistic regression support our theoretical covariance comparisons.

0.20

Riemannian Newton Methods with Statistical Inference

cs.LG stat.ML ·2026-10-31 ·Xiaotian Chang, Qirui Hu, Yangdi Jiang, Nan Qiao
similarity 0.60
Abstract

We develop online statistical inference for Polyak-Ruppert averages of inexact Newton iterates on Riemannian manifolds. A local asymptotic representation separates observation noise, solver randomization, and accumulated implementation bias, and yields one-pass covariance estimators and asymptotically valid Wald regions under local regularity and centering conditions. Independent fresh solves add a positive semidefinite term to the score-sandwich covariance; averaging solver replicas reduces this term in inverse proportion to their number. Slowly varying predictable gains instead cancel from the first order law. Product torus simulations show how Newton scaling shortens an ill-conditioned transient and how retaining solver variation restores coverage. Intrinsic means and principal subspaces provide geometric applications, with a streaming data illustration.

0.29

EGGROLL, Unrolled: Understanding and Improving Low-Rank Evolution Strategies at Scale

cs.LG cs.AImath.OC ·2026-09-10 ·Ege C. Kaya, Abolfazl Hashemi
similarity 0.59
Abstract · 38 pages, 5 figures

EGGROLL (Sarkar et al., 2026) makes evolution strategies (ES) practical for LLMs by replacing dense Gaussian weight perturbations with low-rank Gaussian products, often of rank one. This choice is computationally attractive but geometrically severe: Each rank-one perturbation lies in a zero-volume subset of the ambient matrix space, despite having identity covariance. We characterize the EGGROLL update mean field at finite rank and nonzero perturbation radius as a resolvent applied to the gradient of the perturbation-smoothed objective. This transformation can make the mean field nonconservative and reverse the local stability of an optimum. EGGROLL nevertheless recovers the gradient exactly on quadratic objectives at every rank and radius. In finite populations, the additional sampling variance of rank-one perturbations relative to dense Gaussian ES decays inversely with matrix width under a local affine model, and is only $0.098\%$ at width $4096$. Finally, we introduce LOO-ROLL, a leave-one-out estimator that replaces EGGROLL's two antithetic evaluations per direction by one. At equal evaluation cost, LOO-ROLL halves estimator MSE in transformer blocks. Across fourteen post-training settings up to 14B parameters, matched-time comparisons with EGGROLL yield eleven improvements in individual paired tests and no significant loss. At 1.7B, 8B, and 14B parameters, matched-time gains are $2.9$, $14.1$, and $7.9$ percentage points on GSM8K and $12.2$, $8.4$, and $8.1$ points on MATH-500.

0.32

Gradient-Free Sampling from Generative Models via Stochastic Bounded Extremum Seeking

cs.LG stat.MLmath.OCstat.CO ·2026-10-03 ·Alexander Scheinker
theory similarity 0.59
Abstract

We introduce a sampling approach for energy- and score-based generative models that requires no gradient evaluations of the model. Replacing the drift term that would normally contain the score $\nabla_\mathbf{x} \log p_θ(\bf{x})$ with a high-frequency dithered cosine of the model's \textit{value}, $\sqrt{αω}\,\cos(ωt + k \log p_θ(\bf{x}))$, produces, in the high-frequency averaging limit, Langevin Markov chain Monte Carlo for energy-based models and the reverse-time SDE of score-based diffusion. We prove that trajectories of the dithered Itô SDE converge to those of the target SDE, driven by the same Brownian motion, uniformly on compact time intervals in probability, by an averaging argument that extends bounded extremum seeking (ES) to Itô processes, with an explicit $O(ω^{-1/2})$ mean-square rate under global bounds. The approach is not confined to smooth targets: it extends to $C^{1,1}$ energies with discontinuous curvature (without ellipticity requirement) and to Sobolev energies whose Hessians exist only off measure zero sets; for Lipschitz energies with gradient kinks the averaged limit remains well posed; the Krylov-Röckner integrability class is the boundary of provability. The approach provides a hard \textit{a priori} bound on the per-step update rate and applies to explicitly time-varying targets on finite horizons. Gradient-free pixel-space sampling is not competitive with well-tuned backpropagation-based samplers at practical evaluation budgets; the regime where the approach offers an advantage is latent-space sampling when the model is a black box and the target drifts in time. We demonstrate latent-space tracking for time-varying images on CelebA-HQ ($256{\times}256$) from limited 1D projection measurements and latent-space EBM sampling on CIFAR-10.

0.41