Complexity-Adaptive Stein Transport for Parallel Tempering

Sampling from complex distributions with parallel tempering can be limited by poor exchange between neighboring temperatures. Transport can improve these exchanges, but a fixed expressive map may be unnecessary when cross-temperature changes have simple structure. We introduce CAT-PT, which organizes transports into a hierarchy of structured velocity classes. CAT-PT fits a candidate in each class by minimizing a Stein residual that measures the annealing variation left unexplained by the corresponding motion. CAT-PT then tests increasingly expressive transports and stops as soon as one achieves a prescribed exchange-acceptance target. We show that the accumulated Stein residual directly controls finite-gap exchange rejection. In structured regimes, CAT-PT achieves round-trip performance governed by the residual variation after transport rather than by the ambient dimension. Under additional conditions, this residual scaling is order-optimal within the same transport class. This adaptivity can avoid the cost of a fixed high-capacity accelerator when a simple transport is sufficient. Numerical experiments validate the predicted communication and computational performance.