Skip to main content
Back

CBAOAB Slashes AI Sampling Costs With 17x Fewer Gradient Calculations

A new pair of unadjusted Langevin samplers cuts gradient evaluations by up to 17x on constrained distributions while staying stable at larger steps.

Paper, Full Access
  • New CBAOAB and CABOBA splitting integrators for constrained kinetic Langevin sampling.
  • Five to seventeen times fewer gradient evaluations than Euler-type baselines at matched accuracy.
  • Stable at step sizes several times larger than existing methods, up to h√(M^λ)=1.2.
  • Empirically shows O(h²) bias under squared-distance penalty, better than first-order theory predicts.
  • Includes stochastic-gradient variants (SG-CBAOAB, SG-CABOBA) for mini-batched Bayesian posteriors.
  • RMM still holds better asymptotic complexity bounds; splitting wins on constants and stability.

Constrained distributions arise in models with non-negative coefficients, probabilities on a simplex, or physical parameters confined to a box. Sampling from these targets is costly because smooth approximations to hard boundaries create stiff gradients, forcing conventional Langevin integrators to take small steps.

Neil K. Chada and Lu Yu propose two unadjusted kinetic Langevin integrators, CBAOAB and CABOBA, in a new paper. Across four benchmarks, the splitting schemes used five to 17 times fewer gradient evaluations than the tested Euler-type methods at comparable accuracy. They also remained stable at larger step sizes. The gains are empirical: the constrained randomized midpoint method, or RMM, retains stronger asymptotic complexity guarantees.

Hard boundaries create stiff gradients

A constrained target can be written as a density proportional to exp(-U(x)) for x ∈ C, where C is a convex set. A common workaround replaces the hard boundary with a squared-distance penalty:

Uλ(x) = U(x) + dist(x, C)2 / (2λ)

For a convex set, the penalty gradient is (x - ΠC(x)) / λ, where ΠC denotes projection onto the constraint set. Reducing λ makes the surrogate closer to the hard-constrained target while increasing its curvature. That stiffness limits the stable step size of Euler-style integrators and raises the number of gradient evaluations required per effective sample.

RMM is a strong existing method for this setting and is essentially optimal in the kinetic Langevin regime covered by its theory. It evaluates the gradient twice per time step, which can dominate runtime for large Bayesian models or other expensive potentials.

Split the dynamics into solvable moves

Kinetic Langevin sampling augments the position with momentum. BAO methods divide its dynamics into three operations and compose them symmetrically: