# Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints

arXiv: https://arxiv.org/abs/2604.04130 · HTML: https://mlsanity.com/paper/2604.04130/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 49 references that are in the map.
- First posted on arXiv 5 Apr 2026.

## Builds on (most cited first, 24 of 24)

- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Unitary Evolution Recurrent Neural Networks](https://mlsanity.com/paper/1511.06464/) (2015)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Fast and accurate optimization on the orthogonal manifold without retraction](https://mlsanity.com/paper/2102.07432/) (2021)
- [Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matrices](https://mlsanity.com/paper/1507.02772/) (2015)
- [Understanding Notions of Stationarity in Non-Smooth Optimization](https://mlsanity.com/paper/2006.14901/) (2020)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2303.16510/) (2023)
- [Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints](https://mlsanity.com/paper/1810.03930/) (2018)
- [A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group](https://mlsanity.com/paper/2009.07514/) (2020)
- [A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization](https://mlsanity.com/paper/1812.10229/) (2018)
- [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020)
- [MADMM: a generic algorithm for non-smooth optimization on manifolds](https://mlsanity.com/paper/1505.07676/) (2015)
- [A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/2207.05650/) (2022)
- [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022)
- [A Constraint Dissolving Approach for Nonsmooth Optimization over the Stiefel Manifold](https://mlsanity.com/paper/2205.10500/) (2022)
- [A Semismooth Newton based Augmented Lagrangian Method for Nonsmooth Optimization on Matrix Manifolds](https://mlsanity.com/paper/2103.02855/) (2021)
- [Rotation Group Synchronization via Quotient Manifold](https://mlsanity.com/paper/2306.12730/) (2023)
- [Error bound and exact penalty method for optimization problems with nonnegative orthogonal constraint](https://mlsanity.com/paper/2111.03457/) (2021)
- [Riemannian Smoothing Gradient Type Algorithms]{Riemannian Smoothing Gradient Type Algorithms for Nonsmooth Optimization Problem on Compact Riemannian Submanifold Embedded in Euclidean Space](https://mlsanity.com/paper/2212.03526/) (2022)

## Built on by (most cited first, 1 of 1)

- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)

## Abstract (arXiv)

Recent advancements in data science have significantly elevated the importance of orthogonally constrained optimization problems. The Riemannian approach has become a popular technique for addressing these problems due to the advantageous computational and analytical properties of the Stiefel manifold. Nonetheless, the interplay of nonsmoothness alongside orthogonality constraints introduces substantial challenges to current Riemannian methods, including scalability, parallelizability, complicated subproblems, and cumulative numerical errors that threaten feasibility. In this paper, we take a retraction-free primal-dual approach and propose a linearized smoothing augmented Lagrangian method specifically designed for nonsmooth and nonconvex optimization with orthogonality constraints. Our proposed method is single-loop and free of subproblem solving. We establish its iteration complexity of O(ε-3) for finding ε-KKT points, matching the best-known results in the Riemannian optimization literature. Additionally, by invoking the standard Kurdyka-Lojasiewicz (KL) property, we demonstrate asymptotic sequential convergence of the proposed algorithm. Numerical experiments on both smooth and nonsmooth orthogonal constrained problems demonstrate the superior computational efficiency and scalability of the proposed method compared with state-of-the-art algorithms.