Archive for log-concave functions

proximal sampler

Posted in Books, pictures, R, Statistics, Travel, University life with tags , , , , , , , , , , , , on April 28, 2025 by xi'an

At the Columbia workshop last week, Andre Wibisono presented work related with a recent arXival on the exponentially fast convergence of both unadjusted Langevin and  proximal sampler algorithms under strong [definitely strong] log-concavity assumptions. The idea behind the proximal sampler is to target the demarginalised density

g(x,y) \propto \exp\{\log f(x) - ||x-y||^2/2\eta\}\quad\eta>0

by introducing an auxiliary Gaussian vector y, which preserves f(x) as the marginal distribution on the first component vector X. While the auxiliary Y is (obviously) conditionally Gaussian, the conditional of X is at least as challenging as simulating from f. Unless η is chosen small enough to regularize log g(x) into a strongly log-concave function, since

\log g(x,y) \le \log g(x^\star,y) -\beta||x-x^\star||^2

when x*=x*(y) is the maximiser of log g(x,y) (for a given value y) and β>0 is the appropriate log-concavity constant. This inequality means that an accept-reject can be implemented to simulate from the conditional of X given Y but it requires both the factor β and the derivation of x*(y), hence a pretty good understanding and a rather high regularity of the actual target f(x). Besides, the regularization term ||x-y||² means that y is approximately the previous value of the (sub)chain X, hence it creates a rappel force that slows down the exploration of the target.

Since the arXival does not contain numerical comparisons, I attempted one using the (2D) banana shaped distribution,

target=function(x,sig,B,mu)-x[1]^2/2/sig-(x[2]+B*x[1]^2-mu)^2/2

with μ=σ=B=10. Comparing with a vanilla random walk Metropolis with three potential scales, chosen randomly at each iteration. Since I did not want to check whether or not the target was log-concave (and derive the corresponding β), I used the Normal distribution centred at proposal x*(y) of a Metropolis step, again with several scales. The following is the representation of the samples (sienna for MCMC, navy blue for proximal with β=50, dark green for β=5), with a lesser rate of tail exploration for the proximal samplers. It is thus unclear to me the theoretical characterisations of the method translate into practical efficiency beyond the most regular cases.

1 Comment »

scalability of Metropolis-within-Gibbs schemes

Posted in Books, Statistics, University life with tags , , , , , , on July 17, 2024 by xi'an

My friends Filipo Ascolani, Gareth Roberts, and Giacomo Zanella recently arXived a paper on the scalability (in the dimension) of Gibbs and Metropolis-within-Gibbs sampling schemes. Which is celebrating a sort of return of the Gibbs sampler as a dimension resistant device (when compared with other solutions), witness the following extract:

“….we provide bounds on the approximate conductance of a generic coordinate-wise scheme in terms of the corresponding quantity for the Gibbs sampler. Working with the approximate version of the conductance is crucial for our purposes and subsequent applications. The general theory naturally applies to Metropolis-within-Gibbs schemes, such as those targeting conditionally log-concave distributions. In the second part, we analyze performances of coordinate-wise samplers for relevant statistical applications, combining the bounds discussed above with specific model properties, statistical asymptotics and some novel auxiliary results on approximate conductances and perturbation of Markov operators. Much emphasis is placed on coordinate-wise schemes for generic two-levels hierarchical models with non-conjugate likelihood for which we are able to prove dimension-free behaviour of total variation mixing times, under warm and feasible starts.” F. Ascolani, G.O. Roberts, and G. Zanella

Here, M -warm starts meaning a starting measure bounded by the target, i.e., not too far in the tails, while conductance Φ is a measure related with the probability that the Markov chain exits an arbitrary set A in one step, given that it starts from the target π restricted to A. The paper quantifies the loss of efficiency incurred by substituting an exact Gibbs update with a π¹-invariant one, e.g. M-within-G, that is

\Phi_s(P)\ge\min_i\kappa(P_i, X)\Phi_s(G)

following from

G_i(\partial A)\ge P_i(\partial A)\ge \kappa_i(P_i, X)G_i(\partial A)

In the (rather unrealistic) case of an independent Metropolis-within-Gibbs proposal enjoying an upper bound M on the Radon-Nykodym derivative between target and kernel, the conductance of Metropolis-within-Gibbs is at least one M-th of the conductance of Gibbs, ie a constant slowdown relative to exact Gibbs if the dimensionality is fixed but arbitrary.

The paper further studies a hierarchical Bayes model when the number J of groups goes to infinity and only top (of the hierarchy) parameter is of interest. In that setting, only two requirements need be satisfied for the Metropolis-within-Gibbs kernel P to mix fast: namely that the Gibbs kernel G mixes fast and  that the conditional conductance of P around true ψ is good enough. A further point of relevance is the demonstrated O(J) computational cost, ie the Metropolis-within-Gibbs algorithm with kernel P produces a sample with ϵ-accuracy in TV distance with O(J) cost when initialized from a warm start, a better magnitude than alternatives like the Metropolis-Adjusted Langevin (MALA) and the Hamiltonian Monte Carlo (HMC) algorithms. When checking for connections with other papers, I came across the nearly completed book by Sinho Chewi on long-concave sampling, which seems to be exploring similar ground.

 

Leave a comment »

ARS: when to update?

Posted in Books, Kids, Statistics, University life with tags , , , , , on May 25, 2017 by xi'an

An email I got today from Heng Zhou wondered about the validity of the above form of the ARS algorithm. As printed in our book Monte Carlo Statistical Methods. The worry is that in the original version of the algorithm the envelope of the log-concave target f(.) is only updated for rejected values. My reply to the question is that there is no difference in the versions towards returning a value simulated from f, since changing the envelope between simulations does not modify the accept-reject nature of the algorithm. There is no issue of dependence between the simulations of this adaptive accept-reject method, all simulations remain independent. The question is rather one about efficiency, namely does it pay to update the envelope(s) when accepting a new value and I think it does because the costly part is the computation of f(x), rather than the call to the piecewise-exponential envelope. Correct me if I am wrong!

Leave a comment »

sampling from time-varying log-concave distributions

Posted in Statistics, University life with tags , , , , , on October 2, 2013 by xi'an

Philadelphia downtown from Ben Franklin bridge, Oct. 31, 2020Sasha Rakhlin from Wharton sent me this paper he wrote (and arXived) with Hariharan Narayanan on a specific Markov chain algorithm that handles sequential Monte Carlo problems for log-concave targets. By relying on novel (by my standards) mathematical techniques, they manage to obtain geometric ergodicity results for random-walk based algorithms and log-concave targets. One of the new tools is the notion of self-concordant barrier, a sort of convex potential function F associated with a reference convex set and with Lipschitz properties. The second tool is a Gaussian distribution based on the metric induced by F. The third is the Dikin walk Markov chain, which uses this Gaussian as proposal and moves almost like the Metropolis-Hastings algorithm, except that it rejects with at least a probability of ½. The scale (or step size) of the Gaussian proposal is determined by the regularity of the log-concave target. In that setting, the total variation distance between the target at the t-th level and the distribution of the Markov chain can be fairly precisely approximated. Which leads in turn to a scaling of the number of random walk steps that are necessary to ensure convergence. Depending on the pace of the moving target, a single step of the random walk may be sufficient, which is quite an interesting feature.

Leave a comment »