标题： 曲率与复杂性：地凸优化更好的下界 显示英文标题

标题： Curvature and complexity: Better lower bounds for geodesically convex optimization

摘要： 我们研究了流形上测地凸（g-凸）优化的查询复杂性。 为了孤立流形曲率的影响，我们主要关注双曲空间。 在各种设定下（光滑或非光滑；强g-凸或非强g-凸；高维或低维），已知的上界会随着曲率变差。 很自然地会问，这是否合理，或者是一种人为现象。 对于许多此类设定，我们提出了第一组下界，确实证实了（负）曲率对复杂性有害。 为此，我们基于最近的下界（Hamilton和Moitra，2021年；Criscitiello和Boumal，2022年）针对平滑且强g-凸优化的特殊情况。 通过多种技术，我们也获得了能够捕获条件数和最优间隙依赖性的下界，而这之前并未实现。 我们认为这些界未必是最优的。 我们推测更优的界，并用一类算法（包括次梯度下降法）的匹配下界以及一个相关博弈的下界来支持它们。 最后，为了阐明证明下界的难度，我们研究了负曲率如何影响（有时阻碍）用g-凸函数进行插值。 显示英文摘要

摘要： We study the query complexity of geodesically convex (g-convex) optimization on a manifold. To isolate the effect of that manifold's curvature, we primarily focus on hyperbolic spaces. In a variety of settings (smooth or not; strongly g-convex or not; high- or low-dimensional), known upper bounds worsen with curvature. It is natural to ask whether this is warranted, or an artifact. For many such settings, we propose a first set of lower bounds which indeed confirm that (negative) curvature is detrimental to complexity. To do so, we build on recent lower bounds (Hamilton and Moitra, 2021; Criscitiello and Boumal, 2022) for the particular case of smooth, strongly g-convex optimization. Using a number of techniques, we also secure lower bounds which capture dependence on condition number and optimality gap, which was not previously the case. We suspect these bounds are not optimal. We conjecture optimal ones, and support them with a matching lower bound for a class of algorithms which includes subgradient descent, and a lower bound for a related game. Lastly, to pinpoint the difficulty of proving lower bounds, we study how negative curvature influences (and sometimes obstructs) interpolation with g-convex functions.