# Spectral-gap regularized doubly stochastic attention

- ID: 2144
- Canonical URL: https://synthcore.org/idea/2144/spectral-gap-regularized-doubly-stochastic-attention
- API JSON: https://synthcore.org/api/idea/2144.json
- API Markdown: https://synthcore.org/api/idea/2144.md
- Verification status: unverified
- Source: [arXiv:2608.11760](https://arxiv.org/abs/2608.11760)
- Category: regularization
- Solves: speedup, stability, accuracy
- ML areas: attention, transformer, training, regularization
- Math tags: spectral-theory, linear-algebra, optimization
- Ratings: usefulness 5/10; difficulty 6/10; novelty 6/10

## Idea description

Train attention logits so that the associated Sinkhorn-scaled operator has a favorable local spectral gap, making iterative normalization contract faster. Add a differentiable penalty on the second eigenvalue of the normalized operator while retaining the task loss and marginal-feasibility loss.

## Mathematical statement

The relevant operator is $$B=P^{-1/2}A^{\star}Q^{-1}(A^{\star})^{\top}P^{-1/2},$$ with P=diag(p), Q=diag(q), and A^{\star}=diag(u^{\star})A diag(v^{\star}) the Sinkhorn-scaled kernel. The paper's local contraction factor is \rho=1-\sigma_2, where \sigma_2=\lambda_{m-1}(B) is the second-largest eigenvalue. A larger spectral gap \sigma_2 means a smaller contraction factor and therefore faster local convergence. In a neural network, A=exp(S/    au) depends on attention logits S, so penalize \lambda_{m-1}(B) or maximize the gap surrogate \sigma_2. Estimate the second eigenvalue using power iteration after projecting away from the dominant eigenvector. For robustness, use a squared penalty on excess eigenvalue rather than maximizing the gap without bounds.

## Key formulas

- $$1-\sigma_{2}=\lambda_{m-1}(B),\qquad B=P^{-1/2}A^{\star}Q^{-1}(A^{\star})^{\top}P^{-1/2}.$$
- $$\mathcal{L}_{\mathrm{gap}}=\left[\widehat{\lambda}_2(B)-\lambda_{\mathrm{target}}\right]_{+}^{2},\qquad \mathcal{L}=\mathcal{L}_{\mathrm{task}}+\beta\mathcal{L}_{\mathrm{gap}}+\gamma\|r\|_2^2,$$
- $$z_{t+1}=\frac{(I-ww^{\top})Bz_t}{\|(I-ww^{\top})Bz_t\|_2},\qquad \widehat{\lambda}_2=z_t^{\top}Bz_t,$$
- $$r=\begin{bmatrix}A^{\star}\mathbf{1}_n-p\\(A^{\star})^{\top}\mathbf{1}_m-q\end{bmatrix}.$$

## Implementation notes

Insert the regularizer in a Sinkhorn-based attention layer during training. For each batch element, form A=exp((S-c)/tau), run a detached or low-iteration Sinkhorn pass to obtain A_star=diag(u)A diag(v), and define B=P^{-1/2}A_star Q^{-1}A_star^T P^{-1/2}. For square self-attention with uniform marginals p=q=1/L, P and Q are scalar multiples of the identity; for general marginals use the supplied diagonal vectors. Estimate the dominant eigenvector w with 5 power iterations on B, normalize it, then run 3-5 projected power iterations z <- (I-ww^T)Bz followed by normalization. Estimate lambda2=z^T Bz and add L_gap=[lambda2-lambda_target]_+^2 to the task loss. Set lambda_target initially to 0.7 or to the median lambda2 observed during a warm-up epoch; use beta between 1e-4 and 1e-2 so the regularizer cannot dominate language-model loss. Compute the marginal residual r and optionally include gamma||r||^2, but do not backpropagate through more Sinkhorn iterations than the baseline. The eigenvalue estimate and regularizer come from the paper's contraction formula; lambda_target, beta, and power-iteration count are empirical hyperparameters. First test on a 2-layer, 4-head Transformer on a synthetic permutation/assignment dataset and WikiText-2, comparing ordinary Sinkhorn attention with the regularized version at the same fixed iteration budget. Track estimated lambda2, actual residual decay per iteration, task accuracy or perplexity, gradient stability, and wall-clock overhead. The hypothesis is that training lowers lambda2, produces steeper residual decay, and permits reducing fixed Sinkhorn iterations by 25-50% without increasing marginal error or validation loss.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.