Efficient Optimization on the Euclidean Sphere: Riemannian Gradient Alignment as a Unifying Principle
Abstract
Euclidean sphere-constrained optimization problems represent perhaps the most basic class of nonconvex-constrained problems for which there exist efficient optimization algorithms for specific problem instances, such as the eigenvalue problems and learning problems arising in the recent literature. However, when and why we can efficiently optimize on the sphere using simple first-order methods is poorly understood. We introduce Riemannian Gradient Alignment (RGA) as a unifying structural condition enabling fast convergence. RGA is a parameterized directional error bound requiring a tangent vector to sufficiently align with a target solution vector. We prove that Riemannian Gradient Descent with diminishing step sizes converges linearly when RGA holds with order r=1, and at rate O(k−1/(2r−2)) for r>1. The result applies even to tangent vector fields that are not gradients of any objective. Our main technical contribution is a family of derivative-based sufficient conditions for RGA. We prove these conditions for a range of learning problems, including multi-instance learning/max pooling, Gaussian halfspaces, single-index and generalized linear models, phase retrieval, complete orthogonal dictionary learning, and (sparse) PCA. The provided examples span distributional families that include standard Gaussian, conditionally Gaussian, and more general structured distributions. The provided guarantees cover objectives that are generally not (geodesically) convex, may be nonsmooth, and may arise from discrete distributions. These results establish tractability of problem classes where no prior error bound conditions were known, as well as unify, strengthen, and generalize several prior results.
Related
- A converse bound for dGH vs. dH for Euclidean space and Riemannian manifolds
- Personalised federated learning for Riemannian and Euclidean EEG decoding
- Centered Weak Discrete Riemannian Gradients: A Unified Framework for Riemannian Optimization
- Shape Optimization and Bernoulli Free Boundary Problems for the Riemannian p-Laplacian
- MPFA: A Pareto Front Approximation Method for Riemannian Bi-objective Optimization
BibTeX
@misc{wang2026efficient,
title = {{Efficient Optimization on the Euclidean Sphere: Riemannian Gradient Alignment as a Unifying Principle}},
author = {Puqian Wang and Nikos Zarifis and Jelena Diakonikolas},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07723},
eprint = {2609.07723},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07723},
}
RIS
TY - UNPB
TI - Efficient Optimization on the Euclidean Sphere: Riemannian Gradient Alignment as a Unifying Principle
AU - Puqian Wang
AU - Nikos Zarifis
AU - Jelena Diakonikolas
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07723
UR - https://arxiv.org/abs/2609.07723
AB - Euclidean sphere-constrained optimization problems represent perhaps the most basic class of nonconvex-constrained problems for which there exist efficient optimization algorithms for specific problem instances, such as the eigenvalue problems and learning problems arising in the recent literature. However, when and why we can efficiently optimize on the sphere using simple first-order methods is poorly understood. We introduce Riemannian Gradient Alignment (RGA) as a unifying structural condition enabling fast convergence. RGA is a parameterized directional error bound requiring a tangent vector to sufficiently align with a target solution vector. We prove that Riemannian Gradient Descent with diminishing step sizes converges linearly when RGA holds with order r=1, and at rate O(k^−1/(2r−2)) for r>1. The result applies even to tangent vector fields that are not gradients of any objective. Our main technical contribution is a family of derivative-based sufficient conditions for RGA. We prove these conditions for a range of learning problems, including multi-instance learning/max pooling, Gaussian halfspaces, single-index and generalized linear models, phase retrieval, complete orthogonal dictionary learning, and (sparse) PCA. The provided examples span distributional families that include standard Gaussian, conditionally Gaussian, and more general structured distributions. The provided guarantees cover objectives that are generally not (geodesically) convex, may be nonsmooth, and may arise from discrete distributions. These results establish tractability of problem classes where no prior error bound conditions were known, as well as unify, strengthen, and generalize several prior results.
ER -