Tracking and Regret Bounds for Online Zeroth-Order Euclidean and Riemannian Optimization
研究了在黎曼流形上使用零阶信息最小化时变测地凸代价函数的算法，给出了期望瞬时跟踪误差界和动态遗憾界，并通过数值模拟展示了在线Karcher均值问题的应用。
We study numerical optimization algorithms that use zeroth-order information to minimize time-varying geodesically convex cost functions on Riemannian manifolds. In the Euclidean setting, zeroth-order algorithms have received a lot of attention in both the time-varying and time-invariant cases. However, the extension to Riemannian manifolds is much less developed. We focus on Hadamard manifolds, which are a special class of Riemannian manifolds with global nonpositive curvature that offer convenient grounds for the generalization of convexity notions. Specifically, we derive bounds on the expected instantaneous tracking error, and we provide algorithm parameter values that minimize the algorithm's performance. Our results illustrate how the manifold geometry in terms of the sectional curvature affects these bounds. Additionally, we provide dynamic regret bounds for this online optimization setting. To the best of our knowledge, these are the first regret bounds even for the Euclidean version of the problem. Lastly, via numerical simulations, we demonstrate the applicability of our algorithm on an online Karcher mean problem.