首次实现黎曼流形上强测地凸函数的去中心化在线优化，达到最优对数级误差。
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
- 提出时变步长下的网络误差分析框架，解决去中心化场景中步长衰减与通信误差的冲突。
- 建立首个去中心化梯度下降的 $O(\log T)$ 静态后悔界，匹配欧氏强凸最优率。
- 在两点反馈带宽设置下，通过平滑损失的强次凸性论证，同样获得 $O(\log T)$ 后悔界。
我们研究了在具有有界截面曲率的黎曼流形（包括正曲率流形）上的去中心化在线优化问题，针对强测地凸（strongly g-convex）损失函数。在集中式黎曼优化中，强测地凸性将最优后悔率从 $O(\sqrt{T})$ 提升至 $O(\log T)$，其中 $T$ 为时间范围；然而，在去中心化黎曼设置中，现有方法仅处理测地凸损失，尚未探索强测地凸情形。主要挑战在于：集中式中所需的衰减步长与通常假设固定步长的现有网络误差分析不兼容。首先，我们提供了适用于时变步长策略的一般性网络误差分析。接着，基于该分析，建立了首个去中心化在线黎曼梯度下降的 $O(\log T)$ 静态后悔界，匹配欧氏强凸在线优化的极小最大后悔率。最后，通过损失函数平滑版本的新强次凸性论证，证明了在两点带宽反馈设置下同样可达到 $O(\log T)$ 后悔界。
原文摘要 · Abstract (English)
We study decentralized online optimization for strongly geodesically convex (strongly g-convex) losses on Riemannian manifolds with bounded sectional curvature, including positively curved manifolds. In centralized Riemannian optimization, strong g-convexity tightens the optimal regret from $O(\sqrt{T})$ to $O(\log T)$, where $T$ is the time horizon; in the decentralized Riemannian setting, however, existing methods address only g-convex losses, leaving the strongly g-convex regime unexplored. One challenge is that the required decaying step size in the centralized regime is incompatible with existing network-error analyses, which typically assume a fixed step size. First, we provide a general network-error analysis for time-varying schedules. Next, we build on this analysis to establish the first $O(\log T)$ static regret bound for decentralized online Riemannian gradient descent, matching the minimax-optimal rate for strongly-convex Euclidean online optimization. Finally, we prove the same $O(\log T)$ regret bound for the two-point bandit feedback setting using novel strong subconvexity arguments for the smoothed versions of the loss functions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。