Stochastic Momentum ADMM for nonconvex and nonsmooth optimization with application to PnP algorithm

Kangkang Deng, Shuchang Zhang, Boyu Wang, Jiachen Jin, Juan Zhou, Hongxia Wang · 2025

Read Stochastic Momentum ADMM for nonconvex and nonsmooth optimization with application to PnP algorithm by Kangkang Deng, Shuchang Zhang, Boyu Wang, Jiachen Jin, Juan Zhou, Hongxia Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08223.txt.

Introduction

Kangkang Deng and co-authors present a computing paper from 2025 on hard optimization problems. Many tasks mix smooth and jagged parts and curve the wrong way for easy math. A splitting method that swaps between subproblems is popular, but chance-based versions were slow or hungry for data.

Their single-loop method adds momentum to the swaps and needs just one sampled gradient per step. It hits the best known rate for this problem class without big batches or restarts. Step sizes and penalties adjust on the fly while the rate holds. A plug-and-play version uses image priors inside the loop, with proof of settling under mild rules. Tests on sorting, scan rebuilding, and phase recovery beat past methods in speed and accuracy.

Catalog record

CREATORKangkang Deng, Shuchang Zhang, Boyu Wang, Jiachen Jin, Juan Zhou, Hongxia Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08223

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stochastic Momentum ADMM for nonconvex and nonsmooth optimization with application to PnP algorithm Kangkang Deng, Shuchang Zhang, Boyu Wang, Jiachen Jin, Juan Zhou, Hongxia Wang Abstract This paper proposes SMADMM, a single-loop Stochastic Momentum Alternating Direction Method of Multipliers for solving a class of nonconvex and nonsmooth composite optimization problems. SMADMM achieves the optimal oracle complexity of 𝒪 ( ϵ − 3 / 2 ) \mathcal{O}(\epsilon^{-3/2}) in the online setting. Unlike previous stochastic ADMM algorithms that require large mini-batches or a double-loop structure, SMADMM uses only 𝒪 ⁡ ( 1 ) \mathcal{O}(1) stochastic gradient evaluations per iteration and avoids costly restarts. To further improve practicality, we incorporate dynamic step sizes and penalty parameters, proving that SMADMM maintains its optimal complexity without the need for large initial batches. We also develop PnP-SMADMM by integrating plug-and-play priors, and establish its theoretical convergence under mild assumptions. Extensive experiments on classification, CT image reconstruction, and phase retrieval tasks demonstrate that our approach outperforms existing stochastic ADMM methods both in accuracy and efficiency, validating our theoretical results. keywords ADMM, nonconvex, stochastic, momentum, iteration complexity † † runningheads: Stochastic Momentum ADMM / Kangkang Deng et al. AMS 65K05, 65K10, 90C05, 90C26, 90C30 1 Introduction In this paper, we study a class of nonconvex and nonsmooth constrained optimization problems of the form: \min_{x,y}\mathbb{E}_{\xi\in\mathcal{D}}[f(x,\xi)]+h(y),\quad\text{s.t.}\quad Ax+By=c, (1.1) where f(x,\xi):\mathbb{R}^{n}\to\bar{\mathbb{R}} is continuously differentiable but not necessarily convex, and h:\mathbb{R}^{d}\to\bar{\mathbb{R}} is a convex function; A\in\mathbb{R}^{p\times n} and B\in\mathbb{R}^{p\times d} ; \mathcal{D} is a distribution over an arbitrary space \Xi . We denote F(x):=\mathbb{E}_{\xi\in\mathcal{D}}[f(x,\xi)] . This formulation arises in a variety of machine learning applications, including statistical learning [ 6 ] , distributed learning [ 50 , 29 , 32 ] , computer vision, and 3D CT image reconstruction [ 4 , 16 ] , among others. In this paper, we focus on an online setting. Specifically, we do not know the entire function F , but we are allowed to access f through a stochastic first-order oracle (SFO), which returns a stochastic gradient at a queried point. That is, given any x , we may compute \nabla f(x,\xi) for some \xi drawn i.i.d. from \mathcal{D} . This SFO mechanism is particularly relevant in many online learning and expected risk minimization problems, where the noise in the SFO stems from the uncertainty inherent in sampling from the underlying streaming data. Our primary interest lies in analyzing the oracle complexity, defined as the total number of queries to the SFO required to attain an \epsilon -KKT point pair, as shown in Definition 1 . A widely-used method for solving problem ( 1.1 ) is the ADMM [ 14 , 13 , 6 , 15 ] . The popularity of ADMM stems from its flexibility in splitting the objective into a loss term f and a regularizer h , making it particularly effective for handling complex structured problems commonly encountered in machine learning. In recent years, stochastic variants of ADMM [ 19 , 18 , 57 , 51 , 58 , 52 ] have been extensively studied, addressing both convex and nonconvex settings. These works primarily focus on improving iteration complexity by employing stochastic variance-reduced gradient estimators such as SVRG [ 22 ] and SARAH [ 33 ] , etc. However, these methods are typically restricted to the finite-sum setting. A notable exception is SARAH-ADMM [ 18 ] , which achieves an optimal oracle complexity of \mathcal{O}(\epsilon^{-3/2}) in the online setting. However, it suffers from a double-loop structure, requiring expensive large-batch gradients at each outer iteration. This significantly limits its practical deployment in streaming environments or when large batches are unavailable. Moreover, existing stochastic ADMM methods often rely on fixed penalty parameters, which can severely affect performance and convergence. There is a lack of understanding on how to design adaptive penalty schedules while maintaining optimal theoretical guarantees. Table 1 : Comparison of the oracle complexity results of Online ADMM algorithms. The oracle complexity means the total number of queries to the SFO given in Definition 7 . We do not list the work in [ 51 , 52 ] since they focus on the finite-sum setting and do not apply to the online setting. Algorithm Batchsize Penalty parameter Single loop Oracle complexity [ 19 ] \mathcal{O}(1) fixed ✓ \mathcal{O}(\epsilon^{-2}) [ 18 ] \mathcal{O}(\epsilon^{-1}) or \mathcal{O}(\epsilon^{-1/2}) fixed ✗ \mathcal{O}(\epsilon^{-\frac{3}{2}}) Ours (Theorem 8 ) \mathcal{O}(\epsilon^{-1/2}) then \mathcal{O}(1) fixed ✓ \mathcal{O}(\epsilon^{-\frac{3}{2}}) Ours (Theorem 9 ) \mathcal{O}(1) dynamic ✓ \tilde{\mathcal{O}}(\epsilon^{-\frac{3}{2}}) 1.1 Contributions We summarize our main contributions as follows: • Single-loop stochastic ADMM with optimal oracle complexity. We propose SMADMM, a novel single-loop stochastic ADMM algorithm that leverages momentum-based gradient estimators [ 9 , 26 ] . SMADMM achieves the optimal oracle complexity of \mathcal{O}(\epsilon^{-3/2}) for nonconvex composite problems, using only \mathcal{O}(1) stochastic samples per iteration (except for the first iteration, which requires a mini-batch of size \mathcal{O}(\epsilon^{-1/2}) ). Unlike SARAH-ADMM [ 18 ] , which relies on a double-loop structure with large batch sizes, SMADMM is the first single-loop stochastic ADMM algorithm to match the optimal oracle complexity in the online setting. • SMADMM with dynamic penalty parameter. To eliminate the need for large batch sizes, we further analyze SMADMM under time-varying parameters, including dynamic step sizes, momentum, and penalty parameters. We show that the algorithm still retains the optimal complexity of \mathcal{O}(\epsilon^{-3/2}) . Notably, SMADMM is the first stochastic ADMM method that supports dynamic penalty scheduling, enhancing both convergence and robustness. A detailed comparison of oracle complexities is presented in Table 1 , where SMADMM consistently outperforms existing online stochastic ADMM algorithms [ 19 , 18 ] . • PnP-integrated stochastic ADMM. Finally, we extend our method by integrating it with PnP priors, resulting in the PnP-SMADMM algorithm. Under mild assumptions, we prove that PnP-SMADMM achieves the optimal oracle complexity of \mathcal{O}(\epsilon^{-\frac{3}{2}}) , outperforming existing PnP with stochastic (PnP-SADMM) algorithms. Numerical experiments on classification, CT image reconstruction and phase retrieve tasks demonstrate the practical effectiveness of our approach and validate the theoretical findings. 1.2 Related works Stochastic ADMM algorithm. Large-scale optimization problems ( 1.1 ) typically involve a large sum of N component functions, making it infeasible for deterministic ADMMs to compute the full gradient at each iteration. Early stochastic ADMM algorithms focus on the convex case, such as [ 34 , 45 , 40 ] . There are also many works for considering variance reduction (VR) techniques into ADMM, including [ 59 , 41 , 57 , 49 , 11 , 28 ] . So far, the above discussed ADMM methods build on the convexity of objective functions. In fact, ADMM is also highly successful in solving various nonconvex problems such as tensor decomposition and training neural networks. the nonconvex stochastic ADMMs [ 19 , 58 ] have been proposed with the VR techniques such as the SVRG [ 22 ] and the SAGA [ 10 ] . In addition, [ 17 ] have extended the online/stochastic ADMM [ 34 ] to the nonconvex setting. [ 18 ] propose a SPIDER-ADMM by using a new stochastic path-integrated differential estimator (SPIDER). [ 51 ] propose a unified framework of inexact stochastic ADMM. [ 52 ] propose an accelerated SVRG-ADMM algorithm (ASVRG-ADMM), which extends SVRG-ADMM by incorporating momentum techniques. However, the method depends on a double-loop structure,

Read the complete text