Curvature, Scaling, and Complexity in Riemannian Projection-Free Optimization
Abstract
Projection-free methods replace projections by linear minimization oracles, making their convergence fundamentally sensitive to the geometry of the feasible region. We develop a geometric framework for this dependence in Riemannian Frank--Wolfe optimization. A power-type double-geodesic modulus quantifies the intrinsic geometry of the feasible set, and an exact transfer principle shows that this modulus induces a Frank--Wolfe scaling margin modulated by the differential of the Riemannian logarithm map. The resulting factorization separates the contributions of feasible-set geometry and ambient Riemannian distortion. Rauch comparison provides explicit curvature-dependent certificates for this distortion, while on the positive-definite cone equipped with the affine-invariant metric the logarithm differential admits an exact spectral characterization in terms of relative eigenvalue spread. Combined with a quadratic error bound, the power-type geometry yields the convergence rate O(t−p/(p−1)) for the gap-feedback short-step policy. For every fixed p>3, a compact feasible set in a hyperbolic plane attains the matching rate Θ(t−p/(p−1)) under the same policy. The geometry-derived exponent p/(p−1) is therefore sharp for the gap-feedback short-step policy over the geometry-controlled class considered here.
Related
- Local Topology of Riemannian Manifolds with Lower Intermediate Ricci Curvature Bounds
- Hopf type theorem for surfaces of constant weighted mean curvature in Riemannian manifolds
- Biharmonic Wintgen ideal submanifolds in Riemannian manifolds of constant sectional curvature
- Interior gradient estimates for mean curvature equations on Riemannian manifolds
- Curvature Decomposition for Riemannian Lie Algebroids
BibTeX
@misc{nguyen2026curvature,
title = {{Curvature, Scaling, and Complexity in Riemannian Projection-Free Optimization}},
author = {Binh T. Nguyen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05272},
eprint = {2610.05272},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05272},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Curvature, Scaling, and Complexity in Riemannian Projection-Free Optimization
AU - Binh T. Nguyen
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05272
UR - https://arxiv.org/abs/2610.05272
AB - Projection-free methods replace projections by linear minimization oracles, making their convergence fundamentally sensitive to the geometry of the feasible region. We develop a geometric framework for this dependence in Riemannian Frank--Wolfe optimization. A power-type double-geodesic modulus quantifies the intrinsic geometry of the feasible set, and an exact transfer principle shows that this modulus induces a Frank--Wolfe scaling margin modulated by the differential of the Riemannian logarithm map. The resulting factorization separates the contributions of feasible-set geometry and ambient Riemannian distortion. Rauch comparison provides explicit curvature-dependent certificates for this distortion, while on the positive-definite cone equipped with the affine-invariant metric the logarithm differential admits an exact spectral characterization in terms of relative eigenvalue spread. Combined with a quadratic error bound, the power-type geometry yields the convergence rate O(t^−p/(p−1)) for the gap-feedback short-step policy. For every fixed p>3, a compact feasible set in a hyperbolic plane attains the matching rate Θ(t^−p/(p−1)) under the same policy. The geometry-derived exponent p/(p−1) is therefore sharp for the gap-feedback short-step policy over the geometry-controlled class considered here.
ER -