Research map / Optimization / Nonconvex and smooth optimization

Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing

NeurIPS 2025 · Optimization › Nonconvex and smooth optimization · approach: Nonconvex minimax and constrained methods · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes adaptive Riemannian ADMM (ARADMM) that solves smooth-plus-nonsmooth-convex problems over compact Riemannian submanifolds directly, without smoothing, with O(ε^-3) complexity to an ε-KKT point.

Problem

Nonsmooth composite optimization f(x)+h(Ax) over a compact Riemannian submanifold, where prior Riemannian ADMM convergence analyses required smoothing the nonsmooth term.

Approach

An auxiliary splitting variable with an adaptive penalty rho_k = c_rho k^{1/3} and adaptive dual step size gamma_k that bounds multiplier differences by primal iterate differences, letting a single-loop ADMM with one Riemannian gradient step and one proximal step per iteration converge without smoothing.

Key results

• ARADMM attains O(epsilon^-3) iteration complexity for an epsilon-approximate KKT point without smoothing, matching smoothing-based Riemannian ADMM methods.
• On sparse PCA (Table comparisons with RSG and AManPG, e.g., (300,20,8)), ARADMM reaches objective -4.4071 in 0.4264 s versus -4.2671 (AManPG, 0.8555 s) and -3.9517 (RSG, 0.7970 s).
• On DPCP robust subspace recovery, ARADMM achieves lower objective than SOC, MADMM and RADMM in all tested settings with much shorter CPU time (e.g., 286.3336 in 0.0057 s vs SOC 286.5284 in 1.4835 s for p=4, (30,100,500)).

Measured effects reported in the paper

Surprising findings

• The paper notes that the condition c_rho >= 1 used in the analysis is not essential; c_rho=0.6 also works well empirically.
• Results in the DPCP experiments are reported with CPU times that are often substantially shorter for ARADMM than for baselines, while the baselines with fixed parameters are tuned by grid search in the original papers.

Limitations

• Analysis restricted to general nonconvex nonsmooth setting; does not exploit KL inequality which could give sharper rates.
• Parameter conditions (e.g., c_tau, c_rho >= 1) are needed in the theory and parameters are tuned differently per experiment.
• Experiments are limited to synthetic data and three problem families.

Experimental setup

Datasets: synthetic Gaussian data for sparse PCA synthetic data for regularized linear classifier synthetic data for robust subspace recovery (DPCP)

Benchmarks: sparse PCA (synthetic) regularized linear classifier on sphere (synthetic) DPCP robust subspace recovery (synthetic)

Metrics: objective value CPU time sparsity level

Baselines: SOC MADMM RADMM OADMM RSG AManPG ALMSSN ALMSRTR

Builds on: ADMM manifold ADMM Riemannian ADMM retraction-based Riemannian gradient descent

Closest papers by meaning

• An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2025 · similarity 0.88)
• Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms (ICML 2024 · similarity 0.88)
• Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point (ICML 2024 · similarity 0.87)
• Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.87)
• SERENA: A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization (ICML 2025 · similarity 0.87)
• Decentralized Projected Riemannian Stochastic Recursive Momentum Method for Nonconvex Optimization (AAAI 2025 · similarity 0.87)