Riemannian Inexact Gradient Descent for Quadratic Discrimination

Uday Talwar, Meredith Kupinski, Afrooz JalilzadeharXiv 2025 · arXiv

Abstract: We propose an inexact optimization algorithm on Riemannian manifolds, motivated by quadratic discrimination tasks in high-dimensional, low-sample-size (HDLSS) imaging settings. In such applications, gradient evaluations are often biased due to limited sample sizes. To address this, we introduce a novel Riemannian optimization algorithm that is robust to inexact gradient information and prove an $\mathcal O(1/K)$ convergence rate under standard assumptions. We also present a line search variant that requires access to function values but not exact gradients, maintaining the same convergence rate and ensuring sufficient descent. The algorithm is tailored to the Grassmann manifold by leveraging its geometric structure, and its convergence rate is validated numerically. A simulation of heteroscedastic images shows that when bias is introduced into the problem, both intentionally and through estimation of the covariance matrix, the detection performance of the algorithm solution is comparable to when true gradients are used in the optimization. The optimal subspace learned via the algorithm encodes interpretable patterns and shows qualitative similarity to known optimal solutions. By ensuring robust convergence and interpretability, our algorithm offers a compelling tool for manifold-based dimensionality reduction and discrimination in high-dimensional image data settings.

Introduction

High-dimensional, low-sample-size (HDLSS) data presents a significant challenge in modern medical imaging. With millions of pixels and limited training samples, traditional classification methods often struggle. A common approach is to project these high-dimensional images onto a lower-dimensional subspace, a process that can be framed as an optimization problem on a Grassmann manifold. However, the scarcity of data leads to biased estimates of covariance matrices, which in turn results in inexact gradients. Standard Riemannian optimization algorithms, which rely on exact or unbiased gradient information, often fail to converge or provide reliable results in these settings.

Riemannian Inexact Gradient Descent

We introduce Riemannian Inexact Gradient Descent (RiGD) to overcome the limitations of standard methods in the presence of biased gradients. The core idea is to perform optimization directly on the manifold by projecting the inexact gradient onto the tangent space and updating the current point along a geodesic.

Geometric representation of optimization on a manifold $\mathcal{M}$. The algorithm computes a search direction in the tangent space $\mathcal{T}_x \mathcal{M}$ and moves along a geodesic $\gamma$ to a new point $y$.

The algorithm's convergence is guaranteed under a relative error condition, where the norm of the gradient error is bounded by a fraction of the true gradient's norm. To enhance practical utility, we also propose a line search variant, RiGD-LS. This version employs a backtracking strategy to dynamically determine the optimal step size. By utilizing exact function evaluations to verify the descent direction provided by the inexact gradient, RiGD-LS ensures robust performance without the need for extensive hyperparameter tuning.

Convergence Analysis and Grassmannian Specialization

Theoretically, we demonstrate that both RiGD and RiGD-LS achieve an $\mathcal{O}(1/K)$ convergence rate. This result is significant as it establishes that the use of inexact gradients does not inherently degrade the fundamental convergence speed compared to exact Riemannian gradient descent.

To facilitate application in imaging, we specialize the algorithm for the Grassmann manifold (GiGD). This specialization leverages the manifold's specific geometric structure, providing efficient, closed-form matrix operations—such as SVD-based exponential maps—that are suitable for high-dimensional data processing.

Experimental Evaluation

The performance of RiGD was validated using simulated heteroscedastic images. These 2,500-dimensional synthetic images were generated with varying correlation lengths to simulate different classes. By adjusting the sample size from 10 to 10,000, we explicitly modeled the bias inherent in HDLSS covariance estimation.

The results indicate high robustness:

  • Perturbation Robustness: When subjected to intentional uniform bias, RiGD-LS achieved an Area Under the Curve (AUC) of 97%, nearly matching the 99% theoretical maximum.
  • Sample Bias Resilience: In realistic HDLSS scenarios using sample covariance matrices, the algorithm maintained a 90% AUC, demonstrating its effectiveness when data is scarce.
  • Subspace Interpretability: Beyond numerical performance, the algorithm produces interpretable results. Back-projecting the learned subspaces into the image domain reveals the visual patterns and frequency structures used for discrimination, providing qualitative validation of the optimization process.

Conclusion

Riemannian Inexact Gradient Descent offers a theoretically sound and practically robust solution for optimization on manifolds when gradients are biased. By maintaining standard convergence rates and providing interpretable dimensionality reduction, RiGD is well-suited for complex imaging tasks in data-limited environments. Future research will explore extending this framework to other manifold-constrained problems, such as geometry-aware neural networks and low-rank matrix completion.

Summary updated

Abstract

We propose an inexact optimization algorithm on Riemannian manifolds, motivated by quadratic discrimination tasks in high-dimensional, low-sample-size (HDLSS) imaging settings. In such applications, gradient evaluations are often biased due to limited sample sizes. To address this, we introduce a novel Riemannian optimization algorithm that is robust to inexact gradient information and prove an $\mathcal O(1/K)$ convergence rate under standard assumptions. We also present a line search variant that requires access to function values but not exact gradients, maintaining the same convergence rate and ensuring sufficient descent. The algorithm is tailored to the Grassmann manifold by leveraging its geometric structure, and its convergence rate is validated numerically. A simulation of heteroscedastic images shows that when bias is introduced into the problem, both intentionally and through estimation of the covariance matrix, the detection performance of the algorithm solution is comparable to when true gradients are used in the optimization. The optimal subspace learned via the algorithm encodes interpretable patterns and shows qualitative similarity to known optimal solutions. By ensuring robust convergence and interpretability, our algorithm offers a compelling tool for manifold-based dimensionality reduction and discrimination in high-dimensional image data settings.
BibTeX
@misc{talwar2025riemannian,
  author = {Uday Talwar and Meredith Kupinski and Afrooz Jalilzadeh},
  title = {{Riemannian Inexact Gradient Descent for Quadratic Discrimination}},
  year = {2025},
  eprint = {2507.04670},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.04670},
  howpublished = {arXiv},
}
Figure