Source-linked AI summary
MADMM: a generic algorithm for non-smooth optimization on manifolds
Artiom Kovnatsky, Klaus Glashoff, Michael M. Bronstein
TL;DR
Manifold-constrained non-smooth optimization arises in several machine-learning problems, but existing approaches involve tradeoffs or manifold-specific designs. MADMM splits each problem into smooth manifold-constrained and non-smooth unconstrained subproblems; experiments show strong convergence and robustness across applications.
Problem
The paper addresses manifold-constrained minimization of non-smooth functions arising in robust PCA, compressed modes, embedding, synchronization, and functional correspondence.
Method
MADMM extends ADMM by alternating between a smooth manifold-constrained X-subproblem and a non-smooth unconstrained Z-subproblem.
Results
Across the reported applications, MADMM converged independently of initialization, achieved the best performance among compared methods for compressed modes, and outperformed subgradient descent in robust embedding convergence speed.
Takeaways & Limitations
MADMM provides a simple, generic, and largely parameter-free approach that was effective across machine-learning, computer-vision, pattern-recognition, and data-analysis problems.
Takeaways & Limitations
The functional-correspondence formulation assumes volume preservation, which requires the correspondence matrix to be orthonormal.
Abstract
from arXiv · showhide
Numerous problems in machine learning are formulated as optimization with manifold constraints. In this paper, we propose the Manifold alternating directions method of multipliers (MADMM), an extension of the classical ADMM scheme for manifold-constrained non-smooth optimization problems and show its application to several challenging problems in dimensionality reduction, data analysis, and manifold learning.
1 Introduction
Manifold-constrained non-smooth optimization arises across machine learning and related fields, but existing approaches use smoothing, subgradients, or specialized splitting methods. MADMM extends ADMM to provide a generic alternative for these problems.
- Manifold-constrained optimization supports applications including multi-view clustering, matrix completion, eigenvalue problems, and compressed sensing.
- Non-smooth manifold optimization has been applied to robust PCA, compressed modes, robust Euclidean embedding, rotation synchronization, and functional correspondence.
- Prior work: Existing non-smooth methods use smoothing, subgradients, or splitting, with smoothing trading approximation accuracy against convergence speed.
- Contributions: MADMM extends classical ADMM by splitting manifold-constrained non-smooth optimization into a smooth constrained problem and a non-smooth unconstrained problem.
- Contributions: The proposed method is presented as generic across manifolds, simple to implement, minimally assumption-dependent, and potentially parallelizable.
2 Manifold optimization
Manifold optimization performs descent directly on a Riemannian manifold rather than in the surrounding Euclidean space. It uses tangent-space gradients, projection, step-size selection, and retraction to generate feasible iterates.
- A manifold is locally represented by a Euclidean tangent space, although it is not itself a vector space with global coordinates.
- Manifold optimization treats the objective as a function on the manifold and performs descent on the manifold itself.
- The intrinsic gradient is obtained by projecting the Euclidean gradient onto the tangent space.
- After selecting a step along the intrinsic gradient, a retraction maps the tangent-space point back onto the manifold.
- The conceptual smooth-manifold algorithm repeats gradient computation, projection, step-size selection, and retraction until convergence.
3 Manifold ADMM
MADMM reformulates manifold-constrained non-smooth optimization with an auxiliary variable and linear constraint, then alternates between smooth manifold optimization and non-smooth unconstrained optimization. The resulting scheme updates the auxiliary and dual variables using ADMM-style iterations.
- Non-smooth objectives prevent direct use of smooth manifold optimization, motivating a formulation that separates smooth and non-smooth terms.
- MADMM introduces an artificial variable Z and a linear constraint so the problem can be handled with ADMM.
- The X-subproblem is smooth optimization with manifold constraints, while the Z-subproblem is non-smooth optimization without manifold constraints.
- MADMM alternates the X- and Z-updates, then updates the dual variable U and, when needed, the penalty parameter ρ.
- The method is simple to implement: the X-step can use standard manifold solvers and need not be solved exactly, while some cases admit closed-form updates.
4 Results and Applications
MADMM is evaluated on compressed modes, functional correspondence, and robust Euclidean embedding, using manifold-constrained non-smooth formulations across dimensionality reduction, correspondence, and data analysis. Across these applications, the experiments report favorable convergence, scalability, correspondence quality, and robustness to outliers.
- 4.1 Compressed modes: MADMM computes localized orthonormal compressed modes by solving an L1-regularized Laplacian problem on the Stiefel manifold.The L1 norm induces sparsity, while the Dirichlet energy imposes smoothness.
- 4.1 Compressed modes: MADMM shows the best convergence performance among compared methods on compressed modes at n = 8K.The compressed-modes experiments also report favorable scalability relative to methods.
- 4.3 Robust Euclidean embedding: Robust Euclidean embedding remains insensitive to doubled distances between 500 US cities, whereas classical MDS is completely ruined by the sparse noise.MADMM also outperforms subgradient descent in convergence speed on this dataset.
- 4.3 Robust Euclidean embedding: MADMM scales better than subgradient and SDP approaches for robust Euclidean embedding, while SDP is not applicable to large problems.The typical iteration counts were 20 for SDP, 50 for MADMM, and 500 for the subgradient method.
5 Discussion and Conclusions
The paper presents MADMM as a generic method for manifold-constrained non-smooth optimization and reports broad practical utility, simplicity, and initialization-independent convergence in experiments.
- MADMM efficiently handles non-smooth optimization with manifold constraints across machine learning, computer vision, pattern recognition, and data analysis.
- The method is simple, requires no parameters to tune, and worked out-of-the-box in all reported experiments.
- MADMM converged independently of initialization in the experiments, while theoretical convergence analysis remains an important direction for future work.