Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing

Kangkang Deng (National University of Defense Technology) · Hongxia Wang (National University of Defense Technology) · Jiachen Jin (National University of Defense Technology) · Jiang Hu (University of California, Berkeley)

adaptive riemannian alternating direction method of multipliersauxiliary splitting variableconvergence convergence speed iteration complexitykkt pointnonsmooth convex regularizernumerical experimentspenalty parametersproximal updateriemannian gradient evaluationriemannian submanifoldrobust subspace recoverysmoothing techniquessparse pcastepsizes coordination

We study the problem of minimizing the sum of a smooth function and a nonsmooth convex regularizer over a compact Riemannian submanifold embedded in Euclidean space. By introducing an auxiliary splitting variable, we propose an adaptive Riemannian alternating direction method of multipliers (ARADMM), which, for the first time, achieves convergence without requiring smoothing of the nonsmooth term. In contrast to conventional Riemannian ADMM methods that require exactly solving a nested subproblem at each iteration, our approach involves only one Riemannian gradient evaluation and one proximal update per iteration. Through careful and adaptive coordination of the stepsizes and penalty parameters, we establish an optimal iteration complexity of order $\mathcal{O}(\epsilon^{-3})$ for finding an $\epsilon$-approximate KKT point, matching the complexity of existing smoothing technique-based Riemannian ADMM methods. Extensive numerical experiments on sparse PCA and robust subspace recovery demonstrate that our ARADMM consistently outperforms state-of-the-art Riemannian ADMM variants in convergence speed and solution quality.