Technical Summary: Relaxation of Projected Prior with Continuous Gap Shrinkage

Problem Statement

Modern statistical inference often requires parameters to lie within structured, low-dimensional sets (e.g., sparse vectors, low-rank matrices, or transport plans) rather than a full Euclidean space. While projected priors offer a principled way to enforce such structures by mapping a continuous latent variable $\beta$ to a constrained set $C$ via a projection operator $T(\beta)$, they face significant computational hurdles.

The primary challenge is that computing the projection $T(\beta)$ often requires solving an iterative optimization problem (e.g., alternating projections or Dykstra's algorithm) at every step of a Markov Chain Monte Carlo (MCMC) sampler. This nesting of optimization within MCMC renders posterior computation expensive and computationally intractable for complex constraints. Furthermore, numerical differentiation of these iterative projections (via unrolled differentiation) is costly. This mirrors the historical trade-off in Bayesian variable selection between exact discrete priors (spike-and-slab) and computationally efficient continuous shrinkage priors.

Methodology: Gap-Shrinkage Priors

The authors propose a continuous relaxation of projected priors, termed the gap-shrinkage prior. Instead of enforcing the hard constraint $\theta = T(\beta)$, the method introduces a probabilistic prior that shrinks the duality gap between the primal projection loss and its dual objective toward zero.

Core Framework

1. Primal-Dual Formulation:
   Let the projection be defined as the minimizer of a primal loss $f(z; \beta) = \min_{z \in C} f(z; \beta)$. Using convex duality, the authors define a dual function $d(u; \beta)$ such that the duality gap $G(z, u; \beta) = f(z; \beta) - d(u; \beta)$ is non-negative and equals zero if and only if $z$ is the exact projection and $u$ is the optimal dual variable.

2. The Prior Specification:
   The gap-shrinkage prior is defined on the augmented space $(\theta, u, \beta)$ as:
   $$\Pi_0(\theta, u, \beta) \propto \exp\left[ -\alpha \{ f(\theta; \beta) - d(u; \beta) \} \right] \pi_0^\beta(\beta)$$
   where $\alpha > 0$ is a hyperparameter controlling the strength of shrinkage.

   • Mechanism: As $\alpha \to \infty$, the prior mass concentrates on the set where the gap is zero, recovering the exact projected prior. For finite $\alpha$, it assigns high density to points near the projection, effectively relaxing the hard constraint.
   • Tractability: Crucially, the dual function $d(u; \beta)$ often admits a closed-form expression (e.g., via Fenchel conjugates), allowing the gap to be computed without iterative optimization.

3. Generalization to Proximal Mappings:
   The framework extends beyond Euclidean projections to general proximal mappings (minimizing $f(z; \beta) = \frac{1}{2}\|\beta - z\|^2 + g(z)$).

   • Fenchel-Young Gap: The gap is expressed as $g^*(u) + g(\theta) - u^\top \theta$, where $g^*$ is the Fenchel conjugate.
   • Variational Gap: For complex settings where the conjugate is intractable (e.g., sums of regularizers or nuclear norms), the authors introduce a variational gap function $\tilde{G}$ that serves as a tight upper bound, enabling tractable computation via auxiliary variables (e.g., matrix factorization for low-rank constraints).

4. Posterior Computation:
   The resulting posterior is a continuous density on Euclidean space. The authors recommend blocked Gibbs samplers (or Metropolis-within-Gibbs) rather than Hamiltonian Monte Carlo (HMC). This is because the near-deterministic relationship between $\theta$ and $u$ (induced by large $\alpha$) creates a nearly singular Hessian, which causes standard HMC trajectories to be inefficient without specialized preconditioning.

Key Contributions

• Computational Efficiency: The method eliminates the need to solve an iterative optimization subroutine within each MCMC iteration, replacing it with closed-form or simple variational updates.
• Theoretical Guarantees:
  • Consistency: The authors prove that if the exact projected prior is consistent, the gap-shrinkage prior is also consistent, provided the base prior assigns sufficient mass near the truth.
  • Contraction Rates: They establish conditions under which the relaxed posterior achieves the same contraction rate as the exact projected prior. This requires the shrinkage parameter $\alpha_n$ to scale appropriately with the sample size $n$ (specifically, $\alpha_n + \kappa_n \gtrsim n$ in regular parametric models) to ensure the duality gap vanishes at the correct rate.
• Connection to Global-Local Shrinkage: The framework is shown to be a generalization of global-local shrinkage priors (like the Bayesian Lasso), where the dual variables act as local scale parameters allowing coefficients to escape the constraint when the data strongly supports it.

Empirical Results

The paper validates the method through simulation studies and a real-world data application:

1. Sparse Regression ($n=200, p=500$):

   • The gap-shrinkage prior successfully identified the sparse support and concentrated mass near the ground truth, matching the performance of the exact $\ell_1$-ball projected prior.
   • Efficiency: The gap-shrinkage Gibbs sampler achieved a median Effective Sample Size (ESS) per second of ~82, significantly outperforming the exact projected prior (fit via NUTS with repeated projections), which achieved only ~2 ESS/sec.

2. Low-Rank and Sparse Matrix Smoothing:

   • Applied to a matrix denoising problem with simultaneous low-rank and sparsity constraints.
   • The method correctly recovered the true rank and sparsity structure.
   • Efficiency: The gap-shrinkage Gibbs sampler completed 6,000 iterations in 29 seconds, whereas the exact projected prior (using ADMM for projection) required 4 hours for the same number of iterations.

3. Marketing Data Application (Nielsen Consumer Panel):

   • Task: Modeling multivariate binary grocery purchase decisions with a taxonomy-based smoothing prior on a coefficient matrix.
   • Findings: The model successfully learned that smoothing should be strong within product departments but negligible across them (cross-department weight $\approx 0$).
   • Performance: The gap-shrinkage model outperformed a Bayesian fused-lasso prior and an independent Gaussian prior in terms of predictive accuracy (AUC) and interpretability, avoiding the over-smoothing of the fused-lasso and the high dispersion of the Gaussian prior.

Significance and Claims

The paper claims that the gap-shrinkage prior offers a practical compromise between the statistical desirability of exact projection (concentrating mass on structured, interpretable boundaries) and computational tractability.

• Relaxation without Loss: By shrinking the duality gap, the method retains the interpretability of projected priors (e.g., inducing sparsity or low-rank structures) while bypassing the computational bottleneck of iterative projection.
• Theoretical Robustness: The authors demonstrate that this relaxation does not compromise asymptotic consistency or convergence rates, provided the shrinkage strength is tuned correctly.
• Broad Applicability: The framework is general, applicable to any projection defined by a convex set or proximal mapping, including complex constraints like group sparsity, low-rank matrices, and transport plans.

The authors position this work as a bridge between structured Bayesian inference and continuous shrinkage models, suggesting that "exact" constraints can often be effectively approximated by continuous priors that penalize the deviation from optimality (the gap) rather than enforcing the constraint directly.