Markov chain Monte Carlo (MCMC) algorithms are commonly used to fit complex hierarchical models to data. In this talk, we shall discuss some recent efforts to scale up Bayesian computation in high-dimensional and shape-constrained regression problems. The common underlying theme is to perturb the transition kernel of an exact MCMC algorithm to ease the computational cost per step while maintaining accuracy. The effects of such approximations are studied theoretically, and new algorithms are developed for the horseshoe prior and constrained Gaussian process priors in various applications.