在线镜像下降（OMD）的性能高度依赖于其镜像映射所诱导的几何结构。传统实现几乎只使用欧氏几何和熵几何两种范式，但当损失梯度稀疏时，这两者往往远非最优。我们提出了一族随机块范数镜像映射，它在欧氏与熵几何之间平滑插值，并能够自适应中等稀疏度的结构。
对若干常见凸集（包括 $\ell_p$ 球、椭圆体、盒子以及范数球的 Minkowski 和）我们证明，基于块范数的 OMD 在维度 $d$ 上的后悔上界可比标准的投影梯度下降或指数梯度方法提升多项式因子。
我们进一步构造了具体的在线凸优化实例以展示该提升：在一个简单多面体上，选取适当的中间块几何可实现与欧氏和熵几何均相差 $\text{poly}(d)$ 的后悔；在概率单纯形上则可得到 $\Omega\bigl(\sqrt{\log d}/\log\log d\bigr)$ 级别的分离。
当稀疏度未知时，直接在不同镜像映射之间交替会导致线性后悔，尽管单独使用任一映射仍能保持次线性。为此我们设计了 Hedge 元算法，可在有限的镜像映射组合中竞争最佳者。对于随机块几何，该算法的后悔仅比事后挑选的最佳随机均匀块范数多 $O(\sqrt{\log\log d})$ 因子。
点评