I have been recently reading about mirror descent, which essentially generalizes gradient descent to non-Euclidean spaces.
Nearly every reference I find on this subject gives the same example for when mirror descent is better than gradient descent. Specifically, assume your objective function $f$ is such that $\|f\|_\infty \leq 1$, and assume the feasible set is the unit simplex in $\mathbb{R}^n$. Then by choosing the Bregman divergence to be the KL divergence, gradient descent converges like $n/\sqrt{T}$ whereas mirror descent converges like $\log(n)/\sqrt{T}$. In the mirror descent algorithm, the Bregman projection onto the simplex is simply a rescaling $x \mapsto x / \| x\|_1$. The mirror descent algorithm is equivalent to "exponentiated gradient descent".
What is frustrating me is that I am struggling to find many other examples in the literature. In particular, I'm interested in the setting where the feasible set is not an $n$-dimensional simplex, but rather is the unit ball with respect to the $1$-norm, $B_{1,n}$. It seems that with this feasible set, the KL divergence is no longer appropriate. I am interested in...
(1) Is there an appropriate Bregman divergence (and associated generating function) for this $B_{1,n}$ setup?
(2) If so, is the Bregman projection efficiently computable, as in the case of the simplex setup?
Any references would be much appreciated. I have failed to find this question addressed in the literature, but I feel it must be there somewhere.