An Inexact Proximal Framework for Nonsmooth Riemannian Difference-of-Convex Optimization

Bo Jiang, Meng Xu, Xingju Cai, Ya‐Feng LiuarXiv 2025 · DOI · arXiv

Abstract: Nonsmooth Riemannian optimization has attracted increasing attention, especially in problems with sparse structures. While existing formulations typically involve convex nonsmooth terms, incorporating nonsmooth difference-of-convex (DC) penalties can enhance recovery accuracy. In this paper, we study a class of nonsmooth Riemannian optimization problems whose objective is the sum of a smooth function and a nonsmooth DC term. We establish, for the first time in the manifold setting, the equivalence between such DC formulations (with suitably chosen nonsmooth DC terms) and their $\ell_0$-regularized or $\ell_0$-constrained counterparts. To solve these problems, we propose an inexact Riemannian proximal DC (iRPDC) algorithmic framework, which returns an $\epsilon$-Riemannian critical point within $\mathcal{O}(\epsilon^{-2})$ outer iterations. Within this framework, we develop several practical algorithms based on different subproblem solvers. Among them, one achieves an overall iteration complexity of $\mathcal{O}(\epsilon^{-3})$, which matches the best-known bound in the literature. In contrast, existing algorithms either lack provable overall complexity or require $\mathcal{O}(\epsilon^{-3})$ iterations in both outer and overall complexity. A notable feature of the iRPDC algorithmic framework is a novel inexactness criterion that not only enables efficient subproblem solutions via first-order methods but also facilitates a linesearch procedure that adaptively captures the local curvature. Numerical results on sparse principal component analysis demonstrate the modeling flexibility of the DC formulation and the competitive performance of the proposed algorithmic framework.

1. Introduction

Many real-world problems in machine learning and signal processing involve finding sparse solutions while adhering to specific geometric structures, such as spheres or Stiefel manifolds. While the $\ell_0$-norm is the ideal measure for sparsity, its discrete nature makes it notoriously difficult to optimize directly. Researchers often turn to "Difference-of-Convex" (DC) functions—such as the capped-$\ell_1$ penalty—as continuous proxies.

Optimizing these nonsmooth DC functions on Riemannian manifolds adds significant complexity, as the standard "straight" optimization paths become curved. Existing algorithms for these problems often require solving difficult subproblems to high precision at every step or lack robust theoretical convergence guarantees. This paper introduces the inexact Riemannian proximal DC (iRPDC) framework to bridge this gap.

2. Methodology and Theoretical Contributions

The iRPDC framework introduces several key innovations to handle the challenges of Riemannian DC optimization:

  • Theoretical Equivalence: The authors prove that DC-based models on the sphere are exactly equivalent to $\ell_0$-regularized or constrained models, provided parameters are chosen correctly. This justifies the use of DC models as more than just heuristics.
  • Inexactness Criterion: Unlike previous methods, iRPDC utilizes a novel inexactness rule. It allows the algorithm to proceed even if internal subproblems are only partially solved, significantly reducing total computation time.
  • Adaptive Linesearch: The framework incorporates a linesearch procedure that adaptively adjusts to the local curvature of the manifold, enhancing robustness and efficiency.

Based on this framework, three practical variants were developed: iRPDC-NFG (Fast Gradient), iRPDC-BB (Barzilai-Borwein), and iRPDC-AR (Accumulative Regularization).

3. Complexity Analysis

A primary advantage of the iRPDC framework is its superior iteration complexity. As shown in the comparison below, the iRPDC variants achieve an outer iteration complexity of $\mathcal{O}(\epsilon^{-2})$. Specifically, the iRPDC-AR variant achieves an overall complexity of $\mathcal{O}(\epsilon^{-3})$, matching the best-known theoretical bounds while requiring fewer expensive outer iterations than competing methods like RALM or RADA.

Comparison of iteration complexities for various Riemannian optimization algorithms.

4. Experimental Results

The framework was evaluated using Sparse Principal Component Analysis (SPCA) on both synthetic data ($500 \times 4000$) and the cifar10 dataset.

  • Efficiency: On the cifar10 dataset with a subspace dimension of $r=100$, the iRPDC-BB variant completed the task in 52 seconds, compared to 138 seconds for the OADMM baseline.
  • Sparsity and Accuracy: DC formulations (Capped-$\ell_1$ and $\ell_1-\ell_{[k]}$) consistently identified solutions with higher variance and more accurate sparsity structures than standard $\ell_1$ relaxations.
  • Stability: The iRPDC algorithms demonstrated stable performance across various settings without requiring the delicate manual tuning of penalty parameters often needed by existing methods.

5. Conclusion and Future Work

The iRPDC framework provides a theoretically sound and computationally efficient approach for nonsmooth Riemannian DC optimization. While the equivalence between DC and $\ell_0$ models was demonstrated for the sphere, future work may extend these proofs to more complex manifolds like the Grassmann manifold. Additionally, the authors suggest exploring cases where nonsmooth terms are applied to nonlinear compositions of the variables.

Reference: Jiang, B., Xu, M., Cai, X., & Liu, Y.-F. (2025). An Inexact Proximal Framework for Nonsmooth Riemannian Difference-of-Convex Optimization. arXiv:2509.08561v1.

Summary updated

Abstract

Nonsmooth Riemannian optimization has attracted increasing attention, especially in problems with sparse structures. While existing formulations typically involve convex nonsmooth terms, incorporating nonsmooth difference-of-convex (DC) penalties can enhance recovery accuracy. In this paper, we study a class of nonsmooth Riemannian optimization problems whose objective is the sum of a smooth function and a nonsmooth DC term. We establish, for the first time in the manifold setting, the equivalence between such DC formulations (with suitably chosen nonsmooth DC terms) and their $\ell_0$-regularized or $\ell_0$-constrained counterparts. To solve these problems, we propose an inexact Riemannian proximal DC (iRPDC) algorithmic framework, which returns an $ε$-Riemannian critical point within $\mathcal{O}(ε^{-2})$ outer iterations. Within this framework, we develop several practical algorithms based on different subproblem solvers. Among them, one achieves an overall iteration complexity of $\mathcal{O}(ε^{-3})$, which matches the best-known bound in the literature. In contrast, existing algorithms either lack provable overall complexity or require $\mathcal{O}(ε^{-3})$ iterations in both outer and overall complexity. A notable feature of the iRPDC algorithmic framework is a novel inexactness criterion that not only enables efficient subproblem solutions via first-order methods but also facilitates a linesearch procedure that adaptively captures the local curvature. Numerical results on sparse principal component analysis demonstrate the modeling flexibility of the DC formulaton and the competitive performance of the proposed algorithmic framework.
BibTeX
@misc{jiang2025inexact,
  author = {Bo Jiang and Meng Xu and Xingju Cai and Ya‐Feng Liu},
  title = {{An Inexact Proximal Framework for Nonsmooth Riemannian Difference-of-Convex Optimization}},
  year = {2025},
  eprint = {2509.08561},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.08561},
  howpublished = {arXiv},
}
Figure