تقرير
Open Problem: Polynomial linearly-convergent method for geodesically convex optimization?
| العنوان: | Open Problem: Polynomial linearly-convergent method for geodesically convex optimization? |
|---|---|
| المؤلفون: | Criscitiello, Christopher, Martínez-Rubio, David, Boumal, Nicolas |
| المصدر: | Proceedings of Thirty Sixth Conference on Learning Theory (COLT 2023): https://proceedings.mlr.press/v195/criscitiello23b.html |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control, Computer Science - Computational Complexity, Mathematics - Differential Geometry, Mathematics - Numerical Analysis |
| الوصف: | Let $f \colon \mathcal{M} \to \mathbb{R}$ be a Lipschitz and geodesically convex function defined on a $d$-dimensional Riemannian manifold $\mathcal{M}$. Does there exist a first-order deterministic algorithm which (a) uses at most $O(\mathrm{poly}(d) \log(\epsilon^{-1}))$ subgradient queries to find a point with target accuracy $\epsilon$, and (b) requires only $O(\mathrm{poly}(d))$ arithmetic operations per query? In convex optimization, the classical ellipsoid method achieves this. After detailing related work, we provide an ellipsoid-like algorithm with query complexity $O(d^2 \log^2(\epsilon^{-1}))$ and per-query complexity $O(d^2)$ for the limited case where $\mathcal{M}$ has constant curvature (hemisphere or hyperbolic space). We then detail possible approaches and corresponding obstacles for designing an ellipsoid-like method for general Riemannian manifolds. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2307.12743 |
| رقم الأكسشن: | edsarx.2307.12743 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |