ADMM for Nonconvex Optimization under Minimal Continuity Assumption
Authors: Ganzhao Yuan
Venue: ICLR 2025 Poster (2025)
Keywords: Nonconvex Optimization
Proximal Linearized ADMM
Nonsmooth Optimization
Convergence Analysis
Primary area: optimization

Abstract: This paper introduces a novel approach to solving multi-block nonconvex composite optimization problems through a proximal linearized Alternating Direction Method of Multipliers (ADMM). This method incorporates an Increasing Penalization and Decreasing Smoothing (IPDS) strategy. Distinguishing itself from existing ADMM-style algorithms, our approach (denoted IPDS-ADMM) imposes a less stringent condition, specifically requiring continuity in just one block of the objective function. IPDS-ADMM requires that the penalty increases and the smoothing parameter decreases, both at a controlled pace. When the associated linear operator is bijective, IPDS-ADMM uses an over-relaxation stepsize for faster convergence; however, when the linear operator is surjective, IPDS-ADMM uses an under-relaxation stepsize for global convergence. We devise a novel potential function to facilitate our convergence analysis and prove an oracle complexity $\mathcal{O}(\epsilon^{-3})$ to achieve an $\epsilon$-approximate critical point. To the best of our knowledge, this is the first complexity result for using ADMM to solve this class of nonsmooth nonconvex problems. Finally, some experiments on the sparse PCA problem are conducted to demonstrate the effectiveness of our approach.

Published as a conference paper at ICLR 2025
ADMM FOR NONCONVEX OPTIMIZATION UNDER MINIMAL CONTINUITY ASSUMPTION
Ganzhao Yuan
Peng Cheng Laboratory, China yuangzhêpcl .c
ABSTRACT
This paper introduces a novel approach to solving multi-bloc nonconvex com- posite optimization problems through a proximal linearized Alternating Direction Method of Multipliers (ADMM). This method incorporates an Increasing Penal- ization and Decreasing Smoothing (IPDS) strategy. Distinguishing itself from existing ADMM-style algorithms,, approach (denoted (PDS-ADMM) imposes a less stringent condition, specifically requiring continuity in just one block the objective function. IPDS-ADMM requires that the penalty increases and the smoothing parameter decreases, both at a controlled pace. When the associated linear operator is bijective, IPDS-ADMM uses an over-relaxation stepsize for faster convergence; however, when the linear operator is surjective, IPDS-ADMM uses an under-relaxation stepsize for global convergence. We devise novel poten- tial function to facilitate our convergence analysis and prove an oracle complexity O(e (3 to achieve an e-approximate critical point. To the best of our knowledge, this is the first complexity result for using ADMM to solve this class of nonsmooth nonconvex problems. Finally, some experiments on the sparse PCA problem are conducted to demonstrate the effectiveness of our approach.
INTRODUCTION
We consider the following multi-block nonconvex nonsmooth composite optimization problem:
min Eii((E)) + (xxx)), s.t. A = b,
(1)
where E m A, E RRxd X; E Rd,x1, and i E [n] (1,2.....,,) n.. We assume f((-) [d + (-00, oo) differentiable and potentially nonconvex for all i E [n]. The function h,(-)= _d:x1 + (-o0, oo] is assumed to be closed, proper, lower semi-continuous, and poten- tially nonsmooth. While (.) is convex, we do not require convexity for h.)-) where E [n 1). Additionally, we assume the nonconvex proximal operator of h₂(-) is easy to compute for all i E [n].
Problem (I) has a wide range of applications in machine learning. The function fa(-) plays cru- cial role in handling empirical loss, including neural network activation functions (Liu et al. 2022 Zeng et al. 2021 Wang et al. 2019a, [Huang et al. 2019). Incorporating multiple nonsmooth reg- ularization terms h+(-) enables diverse prior information integration, including structured sparsity, low-rank, binary, orthogonality, and non-negativity constraints, enhancing regularization model ac- curacy. These capabilities extend to various applications such sparse PCA, overlapping group Lasso, graph-guidee guided fused Lasso, and phase retrieval.
ADMM Literature. The Alteratinn Direction Method of Multipliers (ADMM) is versatile optimization tool suitable for solving composite constrained problems as in Problem ( which pose challenges for other standard optimization methods, such as the accelerated proximal gradient method (Nesterov) (003) and the augmented Lagrangian method (Zeng et al.) [022] Lu & Zhang
2012 Zhu et | 2023). The standard ADMM was initially introduced in (Gabay & Mercier 1976).
and its complexity analysis for the convex settings was first conducted in (He & Yuan 2012 Mon-
teiro & Svaiter 2013). Since then, numerous papers have explored the iteration complexity of
Future versions of this paper be found at http://://aaaaiooggg//aaaa////// wttp://wwwwggg/a///////a.../ httpa//a/////////oo/////////////

---

Published as a conference paper at ICLR 2025
ADMM in diverse settings. These settings include acceleration through multi-step updates
(Poc
& Sabach 2016 Li et al. 2016, Ouyang et al.; 2015: Shen et al., 2017: Franca et al. 2018
Hien
et al.] 2022 Tran Dinh 2018). asynchronous updates (Zhagg & Xwwk][0012 Jacobi updates Deng
eet al. 2017). non-Fuclidean proximal updates (Cionçalves et al.) 2017b), and extensions to handle
more specific general functions such as strongly convex functions (Nishihara et al.; 2013 Lin
iet al. 2015a] Ouyang et al., 2015), nonlinear constrained functions (Lin et al. (022a). multi-block
composite functions (Lin et al. 2015b] Xu al. (011)), finite-sum functions (Bian et 2021 Liu
et al., [020), and expected-val value functions (Huang et al. 2019). For comprehensive overview, refer to the book (Lin et 2022b).
Nonconvex ADMM. Compared to the classical subgradient methods (Li ct al. 2021 Davis & Drusvyatskiy 2019) and Smoothing Proximal Gradient Methods (SPGM) (Böhm & Wright 2021
(024), designed for general nonconvex optimization, ADMM-type methods potentially offer faster convergence, enhanced parallelization, and greater numerical stability. However, the conver- gence analysis of the nonconvex ADMM is challenging due to the absence of Fejér monotonicity in iterations. In the past decade, significant research has focused on exploring various noncon- vex ADMM variants (Li & Pong 2015 Hong et al. 2016: Yang et al. 2017). (Li & Pong, 2015) establishes the convergence of a class of nonconvex problems when a specific potential function as- sociated with the augmented Lagrangian satisfies the Kurdyka-t.oasiewwiez inequality. (Yang al.) 2017) analyzes ADMM variants for solving low-rank and sparse optimization problems. (Hong al. 2016) investigates ADMM variants for nonconvex consensus and sharing problems. Some researchers have examined ADMM variants under weaker conditions, such as restricted weak con- vexity (Wang et al., 2019b), restricted strong convexity (Barber & Sidky 2024). and the Hoffmann error bound (Zhang & Luo 2020). However, existing methods typically assume that at least one block of the objective function is smooth. In contrast, our approach requires only continuity in one block, which is achieved through an Increasing Penalization and Decreasing Smoothing (IPDS) strategy.
Over-Relaxed and Under-Relaxed ADMM. Prior studies have analyzed ADMM using either under-relaxation stepsizes a E (0, 1). or over-relaxation stepsizes a E 2). for updating the dual variable. This contrasts with earlier approaches that employed fixed values, such as I or the golden ratio (v5 + 1)/2. In nonconvex settings, most existing works require that the associated matrix of the problem be bijective (Gonçalves et al., 2017a, Yang et al. 2017 Yashtini] 2022 202T Boj & Nguuen] 2020). However, the work of (Bot et al. 2019) demonstrates that ADMM can still be applied when the associated matrix is surjective. provided that an relextienn stepsize is employed. Inspired by these findings, our work shows that when the associated linear operator is bijective, IPDS-ADMM uses an over-relaxation stepsize for faster convergence. In contrast, when the linear operator surjective, we employ under-relaxation stepsizes to achieve global convergence.
Existing Challenges. We consider the linearly constrained optimization problem in Problem ( which involves (n - 1) potentially nonsmooth, nonconvex, and non-Lipschitz composite functions h.(+) for E [n 1], and one convex, nonsmooth composite function (-). Existing ADMM- type methods cannot solve this problem, as they require at least one of the composite functions to be smooth (i.c., (-) = 0). In the special case where n 2, A, I. h2(x)) = أ||x la with I > O, and (.) is the indicator function of orthogonality constraints, the Riemannian ADMM (RADMM) algorithm (Li et al., 2022) is the only known method capable of solving Problem (T) However, RADMM cannot handle linearly constrained problems, particularly when A, is bijective or surjective. Importantly, it results in suboptimal iteration complexity. A comparison of existing nonconvex ADMM approaches is provided in Table T
Our Contributions. Our main contributions summarized as follows. (i) We introduce IPDS- ADMM to solve the nonconvex nonsmooth optimization problem as in Problem (I). This approach imposes the least stringent condition, specifically requiring continuity in only one block of the ob- jective function. It employs an Increasing Penalization and Decreasing Smoothing (IPDS) strategy to ensure convergence (See Section 3 (ii) IPDS-ADMM achieves global convergence when the associated matrix is either bijective or surjective. We establish that IPDS-ADMM converges to an e-critical point with time complexity of O(e (See Section 4p. (iii) We have conducted exper- iments on the sparse PCA problem to demonstrate the effectiveness of our approach. (See Section
Assumptions. Through this paper, we impose the following assumptions on Problem
2

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of existing ADMM approaches for solving the nonconvex problem in Problem []. CVX: convex. NC: nonconvex. LCONT: Lipschitz continuous. WC: weakly convex. RWC: restricted weakly convex. F: the constraint set non-empty, II: A, identity. SU: A., is surjective with Amin (A, > O. II: A. is injective with Amin AA,, > O. BI: An is bijective (both surjective and injective). IMI Im([A), A2. , A An- C Im() with Im being the image of the matrix.
Optimization Problems and Main Assumptions
Reference
Blocks
Functions f.(-) and l.)-)"
Matrices A.
Complexity
Parameter
(He & Yuan 2012
= 2
CVX: Js, Vi 6 [2]
Oie 2
& Pong 2015
n = 2
NC: Na. Jaz J1 O; ltg
Ole
0
Yang et al.
n 3
CVX: fa; NC: leg, f1 fq
10:00 hg
O 2
8 E 21
Yashhing 217-22
2
NO: f1,
Ole
(0,1)
Yashiumi 2021
1
ki: Ji -1 0. =0
BI 1M
O
E (0,1)
(Wang et al. 2019b
n 2
RWC: 111 Pu, =
IN, IM
O
Bot & Nguyen 20200
n m 2
NC: Ju.25 Ji - 0: h2
Dle-2)
a E (1.
all 2019
n 2
NC: Joc.aa Ji = 0. log 102=00
SU
Ole
a E (0,1)
Huang al. 2019
n 222
No: f(..m- 0; CVX: 1 hn
Ole-2)
1.i et al. 2022
n n=2 2
NC: C19: CVX: by: fo = O: LOONT: hg * 0
Ole
This work
n n22
NC: NC:hii 1)- J1.d) CVX: No. LCONT: Ja. nn #0
Ol
a. 21,2)
This work
222 NC: Ap. fp.a]: CVX: h,s LCONT: f. h, of
Ole"))
a (0,1)
Note hn 0 denotes that the n-thh block has non-smooth part, making the objective function smooth.
Note b; The iteration complexity relies on the variational inequality of the convex problem.
Note We adapt their application model into our optimization framework in Equation [ with (L, S, 2)
(x,,X,, xa), their model additionally requires the linear operator for the first two blocks to be injective. Note This paper studies manifold optimization with fixed large penalty and small stepsize.
Assumption 1.1. Each function fa(.) is Lę-smooth for all E [m] such that [V(x), - Vx(()) Lil ||x;- x.|| holds for all x;, x; E gd.x1. This implies that (fi(x.) fi(ks)) (Vf((s;), xx)
x xz x1112 (cf. Lemma 1.2.3 in Nesterov (003))
Assumption 1.2. The functions fn(-)) and h-) are Lipschitz continuous with some constants Cj and Cn, satisfying f (xxn)))) S Cy and 11ōh (Xa))l S Cr all Xn.
Assumption 1.3. We define X 2 )mmor (A,, A A Amin (A, X Amin (A, (n)) Either of these two conditions holds for matrix An;
a) Condition Bll: A., is bijective (i.e., X = X > 0), and it holds that K & 2/1 <2
b) Condition SU: An is surjective (i.e., X > O, and X' could be zero).
Assumption 1.4. Given any constant 3 2 O, we let O' - *infx, X E Ei=lif(x; + h,(x,)) +
I A,x.] bll2. We assert that e' -c.
Assumption 1.5. For all E [n], the proximal operator (x,x,(x;;1) - ming; -1x; h1 can be computed efficiently and exactly for any given x; E IRdxx1 and 0.
A Assumption 1.6. If (x + +h(xx)) < +00, it follows that ||x:|| < +oo for all E [m].
Assumption 1.7. For any E [n]]. if the vector x, E [ddix1 is bounded, then the set Prox u1) is also bounded for all μ E (0, 00).
Remarks. (i) Assumption 1.1 is commonly used in the convergence analysis of nonconvex algo-
rithms. (ii) Assumption 1.2 imposes continuity assumption only for the last block, allowing other blocks of the function [1a [x, in-1 to be nonsmooth and non-Lipschitz, such as indicator functions of constraint sets. It ensures bounded (sub-) buub-)gradients for fn (.) and h,,()), ), a relatively mild require- ment that has found use in nonsmooth optimization (Li et al. 2022 2021 Huang et al. 2019: Böhm & Wrightt 202I). (iii) Assumption 1.3 demands condition on the linear matrix A, for the last block (2 = 12), while leaving A; unrestricted for i E [n 1]. (iv) Assumption L.4 eeesuuuues the well- defined nature of the penalty function associated with the problem, as has been used in (Gonçalves (x,))
et al. 2017a). Furthermore, Assumption 1.44can can be satisfied if >x (f((x) +
DC. (v)
Assumption 1.5 is frequently employed in nonconvex ADMM frameworks (Li & Pong 2015 Bo
ct al. 2019). Common examples of functions (x;) arising in practical applications include those
discussed in (Gong et al. 2013), fo regularization, fi/2 regularization (Zeng et al. 2014), and in-
dicator functions of cardinality constraints, matrices with orthogonality constrains LLa & Osher
2014]. and matrices with rank constraints, among others. (vi) Assumptions [.6 and are used to
guarantee the boundedness of the solution.
3

---

Published as a conference paper at ICLR 2025
Notations. We define [n] _ (1.2...., and _ X(n] {xi, "2,,,,,...,... For any i, denote [i,j]] - {xi, X,+ We define Amin (M) and Amax (M) as the smallest and largest eigenvalue of the given matrix M, respectively. We denote || | as the spectral norm of the matrix A; We denote Ax _ Σj= A, and ||x+ - x ΣE=1 |x x:1lē. Further notations and technical preliminaries are provided in Appendix
MOTIVATING APPLICATIONS
TT. Below, Many machine learning and data science models be formulated as Problem present two examples, with additional applications provided in Appendix
Sparse PCA. Sparse PCA (Chen et al. 2016 Lu & Zhang 2012) focuses identifying subset of informative variables with sparse gos to enhance interpretability and reduce model complex- [D DVVTIE + |I,, s.t. V E - VVIVTV= = I), where E Ruhxd is the data matrix, and ý 2 O. Introducing an additional variable Y, this problem can be formulated as: minv, Y 2m D DVV
ity. is formulated as: veRáx 2mh
V + (M(Y), s. -Y + V 0. It corresponds to Problem (T) with X1 vec( X2 = vec V). (x = 0, (x1) = LM(Y), fx(2)) 2 |D DVV (xg) V 1. A1 = I, A2 = I, b O, and Condition BII.
Structured Sparse Phase Retrieval. Sparse phase retrieval (Duchi & Ruan 2018 aims to re- cover sparse signal from the magnitudes of linear measurements. By incorporating additional linear constraints, recovery accuracy can be further improved. The problem is formulated as: R D Rexd with being surjective that DD 0. Introducing new variable y, this problem can be formu- lated as: mill.yy [l(Vv) @ (Gv) 21 + أ 1 (y), s.l.y Dv 0. This corresponds to Problem 1 with X1 X2 v. (x ) = 0, (x,) = (20 (y), (2(x) [ (Gv)
minl ( (Gv) ((c)-z2j 20 + 8. L. Dv 2 O, where ý 2 0, G E Rixxd,
h2(x2) = | 11. A = A2 = -D, b = O, and Condition SU.
THE PROPOSED IPDS-ADMA ALGORITHM
This section describes the proposed IPDS-ADMM algorithm for solving Problem ( featuring with using a new Increasing Penalization and Decreasing Smoothing (IPDS) strategy.
3.1 INCREASING PENALIZATION STRATEGY
We employ an increasing penalty update strategy that is crucial to our algorithm. A natural choice for this penalty update rule is to use functions from the lp family. Throughout this paper, we consider the following penalty update rule {33 J for any given parameters E, 6,p E (0, 1):
3r 8 + EIP), g (0X)
Here, L, and are defined in Assumption 1.1 and Assumption 1.3 respectively.
We obtain the following useful lemma regarding the penalty update rule.
Lemma 3.1. (Proof in Appendix C./) Given E, E (0,1), assume Formulation 2
is used to
choose {Ø 10 We have: (a) 3r < gt+ +) (b) L, < 8.
Remarks (i) The increasing penalty update strategy is closely coupled with the decreasing smooth- ing strategy and the diminishing stepsize approach in the literature. These strategies are frequently employed in subgradient methods (Li et al., 202T), smoothing gradient methods (Böhm Wright 2021|Sun & Sun 2023) Lei Yangl 2021). penalty decomposition methods (Lu & Zhang 2013). and stochastic optimization algorithms like ADAM (Kingma & Bal 2015 Chen et al. 2022) >. but are less commonly utilized in ADMM frameworks. We examine this approach within ADMM but limit our discussion to specific form and condition as in Formulation (2) (ii) The condition 33 > Ln/(dX) in Formulation (2) essentially mandates that the initial penalty value be sufficiently large. This condition be automatically satisfied since an increasing penalty update is used. (ii) The result 3++1 < (1 + Sf in Lemma 3.1 implies that the penalty parameter grows, but not excessively fast, with constant prevent rapid escalation.
4

---

Published as a conference paper at ICLR 2025
3.2
DECREASING SMOOTHING STRATEGY
IDDM is built upon the Moreau envelope smoothing technique (Li et al. 2022 Zeng et al.,
2022 Sun & Sun 2023 Böhm Wright 202T Our algorithm gradually decreases the smoothing
parameter at a controlled rate.
Initially, we provide the following useful definition.
Definition 3.2.
The Moreau envelope of proper convex and Lipschitz continuous function h(u))
[dx1 + R with parameter μa E (0, oo) is defined as h(u; μi) - minlygRax h(v))
We present several useful properties of Moreau envelope functions in the following lemmas.
Lemma 3.3. (Beck 2017 Chapter 6) Suppose the function h(u) C -ipschhcit continuous and convex w.r.f u. We have: (a) The function h(u; p)) is Cn-Lipschitz continuous w.rlf u. (b) The
function h(u: ji) is (1/u)-smooth w.r.t. u, and grudient can be computed as: V Vi(u;
Proxa (u: p))). where Prox, (u: arg miny h h(v)
2μ |V u--ul22 (c) h(u) h(u)-h(u: 200
Lemma 3.4. (Proof in Appendix
C.2
Assuming 0 < p2 < μa and fixing E gdx1, have:
0 5 b(u:/))) -h(nge)
C
#1-P2
Lemma 3.5. (Proof in Appendix
C.3 Assuming 0 P2 μi and fixing Rdxl, have:
|/V (u: p1) V H2); S
Cr-
Lemma 3.6. (Proof in Appendix
C.4 Given constants {c, H. p}, we consider the convex problem:
X, = arg minx, (X.i ()) +
{ Xn cl12. We have: (a) Rn T+pp (1 + +pc), where Xn =
arg minx, 1n, (xn) + I-pp | - clli Prox, (c; + 1/p). (b) plc xn.) E Oh()a) (c)
|xx,, - -x,ll S pCn-
Remark 3.7. (i) Lemmas 3.4 and 3.5 are derived using standard convex analysis techniques and
play key role in analyzing the proposed IPDS-ADMM algorithm. (ii) Lemma 3.6 is essential for establishing the iteration complexity of Algorithm [ in reaching a critical point. The results of
Lemma 3.0 are analogous to those of Lemma 1 in (Li al. 2022).
3.3 THE MAIN ALGORITHM
This subsection provides the proposed IPDS-ADMM algorithm. Initially, we consider the following alternative optimization problem:
milx,, Xa Nn (x; (1) + IEET h (x:)] + D f(xx)), s.t. D A,X, b,
(3)
where μ + 0, and (xxi u1)
millygra.x h(v)+ + 2y v-xx, is the Moreau envelope of ht, (xn) with parameter μ. Lemma 3.3 confirms that h, (Xn, μ}) is a
( (smoth function assuming (.)
convex. We present the augmented Lagrangian function for Problem (3) as follows:
L(x, 2; B, A Nr, (x,, + (E (x.)) + G(x, 2)
(4)
where G(x, z; B) is differentiable and defined as:
2( f(x.) (E:1 A.x, - b. z) + | Axx,] bl
Here, μ E (0, 3 (0, oo), and mmx1 are the smoothing parameter, the penalty parameter, and the dual variable, respectively. We employ increasing penalty and decreasing smoothing
update scheme throughout all iterations t {0, o0) with 8 + too and μ¹ x 3 - 0.
Notably, the function G(x², z²; (*)) Lf-smooth w.r.t. for all i [m]], where L; = L, + 8 |A 1|-
For notation simplicity, for all [ns]. we denote g! A Vx. Vx, G(x 1j. xc, 1, 2 8t) as the gradient of G(x, z'; 8*) w.r.f. x; at the point x(.
In each iteration, we select suitable parameters {B", {1*, and sequentially update the variables X2,,X,..... Xn, z). We employ the proximal linearized method to cyclically update the vari- ables {x1, X2.., Xa). Specifically, we update each variable x; by solving the following sub- problem for all i E [n]: x arg argmin L(x(1,i-11) Xz, xf ((11))) 2¹; Br, n²)). To address
5

---

Published as a conference paper at ICLR 2025
the x--subproblem, we employ proximal linearized minimization strategy for all i E [n 1]: 2
x; 4++ E arg minx, (x(x)) + " ||x; - xil1 + (x; - x K z';3%). However, for the final block of the problem, we consider a subtly different proximal linearized minimization strategy: x arg minx, hn (x)) + 4zLi
2 xx, - xx, 112 + (x, xx (%)) Importantly, we assign 0 to blocks [1, - 1] and 02 to block n. Our algorithm updates the dual variable z using either an under-relaxation stepsize a E (0, or an over-relaxation stepsize a E (1,
Algorithm 1: IPDS-ADMMN The Proposed Proximal Linearized ADMM for Problem (I).
Choose suitable parameters {p, E, 63 and for 01, 02) using Formula or Formula
Initialize (x": ; x ) Choose 30 2 (6)))
for / from 0 to T do
S1) IPDS Strategy: Set 1 = (1 {t"), ) n¹¹ = 1/(888))
We define /
Vx, ((+++ 11, x x [|| 21: 3²)
S2) x E arg minx, /1 (x1) + (x1 - xx g1) + 9 ||[] - -xil1
S3) x²+1 E arg minx, hz(x)) + (x2- x22 g5) + 8144
||x x3112
S4) x E arg milx,. hn- (x + (xn-1 - 1 8h-1) + 0,1.
-2 | x
S5) x E arg minx, ha (x.: (1) + (xn - x km) + Lghi |x,, - -x111 It can be solved
using Lemma 3.6 as x ++1 T+ap
(xh+1
2++ + ppp),, where x Prox,(c; 1/p),
J = n², p L. and c - x /h/Pp
S6) z +1 =z' - -03 (E) Azx}"
+1 -b)
end
We present IPDS-ADMAN in Algorithm and have the following remarks.
Remark 3.8. (i) Algorithm 7 can be viewed as a generalized cyclic coordinate descent method
applied to the augmented Lagrangian function in Equation ④ (it) The Moreau envelope smooth- ing technique has been used in the design of augmented Lagrangian methods [Zen et al. [002],
ADMMs (Li et al. 2202 Yuan 2025), and minimax optimization (Zhang et al. 2020 However, these algorithms lypically utilize constant penalties, whereas we adopt an Increasing Penaliza- tion and Decreasing Smoothing (IPDS) strategy improve the iteration complexity of RADMM Li et al. 2022), reducing it from ( to O 3). (üi) Algorithm is a fully splitting algorithm, where each step reduces computing a proximal operator. For the first (n 1) blocks, we have:
x,+1 E (x / p: p). where ò 0,Li. For the last block, Lemma 3.6 can be applied to compute the proximal operator of the smoothed function hn (Xni μ1) using the proximal operator of the original function h, (x,)) (iv) The point xt,1 in Step S5) of Algorihtm | plays crucial role. As will be seen later in Theorem 4.15 the point (x1, x2...., x/- X/, z²), ruther than the point x x- x,,,²" z²), will serve as an approximate critical point of Problem (7) in our com- plexity results. (v) RADMM [Li et al. 2022) uses a fixed large penalty parameter ((T7c) and a fixed small smoothing parameter O(e) to achieve an e-approximate critical point. However, this leads to overly conservative step sizes for the primal and dual updates, potentially hindering the algorithm's practical performance. (vi) We apply the smoothing strategy only to the last block to bound the dual variables via the primal ones. This leverages the Lipschitz continuity of the smoothed function to estimate || - z'112 and construct a suitable potential function. (vii) Some may be concerned that using an increasing penalty could cause the parameter to grow excessively fast. However, by setting & < 1, we ensure that gi+1 < (1+ E), meaning the penalty grows very slowly in practice.
X2.........
3.4 CHOOSING SUITABLE PARAMETERS (p. 6} AND {o. 01, 02}
Selecting appropriate parameters {p. 53 and {a, 0, is essential to ensuring the global con- vergence of Algorithm In our theoretical analysis and empirical experiments, we suggest the

---

Published as a conference paper at ICLR 2025
following choices for {..
E. 6) and far 01,021 02):
BI: p 3. { E (0, 00), 8 E (0, { 1)), [1,2),0 1.01,02
1/x-6 14.
(5)
20(1+072
SU: p = } { = 0.01 01 = 11011,1101 02 = 1.5.
(6)
Here, e GWOT 01 1111--|-- and w - 1+ 2/0 oo.. Notably, 02 in 5 depends on (E, 6, o).
Remark 3.9. (i) We obverse from O6 that the parameters (5, is inversely proportional to the condition number n. Such settings are partly consistent with those in (Bot et al. 2019) (refer to Lemma 5 in (Bog et al. 2019). (i)) Introducing the relaxation parameter a E (0. enables handling cases where the matrix is surjective. Specifically, when the matrix is bijective, we can use an over-relaxation step size for faster convergence, whereas for surjective matrices, the algorithm requires conservative step sizes to ensure global convergence.
4 GLOBAL CONVERGENCE
This section establishes the global convergence of Algorithm
We begin with a high-level overview of the proof strategy. First, using the Lagrangian function, we derive sufficient decrease conditions for the four parameter sets: primal variables, dual variables, the penalty parameter, and the smoothing parameter. Next, using the first-order optimality conditions and dual update rules, we bound the difference in dual variables using primal by the difference in primal variables. Lastly, show that the tail error term related to the smoothing parameter is constant, establishing the summability of the sequence linked to a potential function.
We provide the following three useful lemmas.
Lemma 4.1. (Proof in Appendix D.I A Sufficient Decrease Property) Fix E3 & & and A 101 - Let E2 R. For all 2 1, we have:
g+41 +0t1 -4-1-00 0 < (
02 82)
L
x 112 + न:अ ||z 21
where
gt+1 A |ai Em Li|
1 2g ||x|
x 1 + zz 2112
0 & L(x', z': 3r, ,p) +
1 Chip L L;
A 11 w w f + toE.
Lemma 4.2. (Proof Appendix D.2 First- Order Optimality Condition) Assume a E (0, 2). For all 1 2 I and i E [n- 1}, we have the following results.
(a) Let (+1 w(t1
Oh,(x; (1(xx+1)++0 +VV++++++V(())) and u ++1 & + -xx(x++xxx)-BB It holds that: O = A + A. (z) 1- -z') tow 1+1 + +ou
(x xf)1
(b) Let wi+1 & Vh,
V (x(x), and u+t1 e Q (x x(,, where Q' & 02LiI
B A'A,nn It holds that: 0 = o A + A z²) + +ow + +ou
(c) We have the following two different identities:
BL: AZ
2²) (1 a) (AT - zz11)) to (uh un 1+1
+ wh wa 4+1
(8)
Aat+1
Ax!
SU: AJ
x²)) + ou
(1 - o) (A - = + ou
w/ wnn
(9)
Aa
Ard
Lemma 4.3. (Proof in Appendix D.3 For all t 2 0, we have: (a) L < 8'T + 6): (b) |Q' < S4 where q e 01 + 5) X' A; (c) |n Σ T8
- -X
We provide convergence analysis of Algorithm I under two conditions: Condition IBI using Formu- lation (8) and Condition SU using Formulation We define 0 و L(x' z': 8r .px)t) + Crjrd, and W 1 20 og. We define 0 2 1- and 02 A || --- where E (0, We construct a sequence associated with the potential (or Lyapunov) function for different Conditions
7

---

Published as a conference paper at ICLR 2025
BI and SU follows:
BI: 0 Oj
902
||a 11
Swes
(Ln||xg Xx
I1 x1 11
(10)
A
51
Aa
AAA
4b
Age
SU 0 0
2wiz
||a*|] 1
Gwm
(Tm (mmllxp - x
11 + a 1
(11)
4b
Age
4.1 ANALYSIS FOR CONDITION BI
We provide convergence analysis of Algorithm [ under Condition BI, where An bijective matrix. We assume over-relaxation stepsize is used with E (1,
The subsequent lemma uses Equation (8 to establish an upper bound for the term - ||| z 113
Lemma 4.4. (Proof in Appendix D.4 Bounding Dual Using Primal) We define w as in Lemma 4.1
For all 2 have:
I|z ++1
zz S 0 -4 + +XL |xx+ -x, + U³
(12)
where X A 2(5 02 020 1/k)² 2 e - Gwo KK 04 aAt BB' and TJ & Ch (
1)2
Here, {a, A (a,,",, are defined in Equation 10
Assume Equation
used choose {p,E, o, 01 02]. We have the following lemma.
Lemma 4.5. (Proof in Appendix D.5)
We define (x, 2} in Lemma 4.4 We have the following results:
(a) holds that 5 A 1
2 > and E2 02 X
(b) For all 2 1, we have g+ < 0¹ r + U..
4.2 ANALYSIS FOR CONDITION SU
We provide a convergence analysis of Algorithm D under Condition SU, where A,, surjective matrix. We assume under-relaxation stepsize is used with E (0, 1).
The following lemma utilizes Equation establish an upper bound for the term w ||
1|3-
Lemma 4.6. (Proof in Appendix D.6 For all > have:
Bounding Dual Using Primal) We define w as in Lemma
4.1
Iz ++
z'
0 -0 +x (x - -x,,1 +
(13)
agc
where
2wx 10292 + 382 + 3(8 + )]) a 02 + O2ō, 0 & aA + DB and UJ
A
Ch b. (1- (4- - 1)2. Here. {a, A', b' are defined in Equation 111.
Assume Equation (6 is used choose {p,E, 8, 01, 02). We have the following lemma.
Lemma 4.7. (Proof in Appendix (.7) We define in Lemma 4.6 We have the following results:
(a) It holds that A 10 1/ > 0, and 82 02 -2 >>>0 0.
(b) For all 2 have; g++1 < - 0++1 Ut
4.3 CONTINUING ANALYSIS FOR CONDITIONS BI AND SU
Using Assumption 1.4 we show that O' is consistently lower-bounded by the following lemma.
Lemma 4.8. (Proof in Appendix D For all t. 2 1, there exists a constant 9 such that O 2 e.
The following lemma shows that both (E Ut) and (Eee gt+l) are always upper-bounded.
Lemma 4.9. (Proof in Appendix D.9 We define U as in Lemma 4.4 or Lemma 4.6 We define E as
Lemma 4. We have:
(a) There exists universal positive constant U such that Dee U U.
8

---

Published as a conference paper at ICLR 2025
(b) Letting & _ 0¹ -
+ + U. we have: Di= Eh 3.
The following lemmas are useful to provide upper bounds for the dual and primal variables.
Lemma 4.10. (Proof in Appendix
D.10 For all t 2 1, there exist constants {Z, 7 such that
3 #1 S Z, and Ex=1 $ |2/t1 z
2 < Z.
Lemma 4.11. (Proof in Appendix D.I For all E [n]] we have ||x| < +00.
Finally, we have the following theorem regrading to the global convergence of IPDS-ADMM. Theorem 4.12. (Proof in Appendix D.12 We have the following results.
(a) Ei= |zzt1 21: + (x x') 11 S KB", where K O some constant.
(b) There exists an index i with T such that ||2 ++ x x/112 + (x xx)113 K8T
Remark 4.13. (i) With the choice 33 = O(T)) with p E (0,1), we observe 22 - $112 x 11 +
(x x1 = O(TP-1), indicating convergence of τt towards O. (ii) In light of Theorem
4. 12 reusonable stopping criterion for Algorithm is || - z²11 + 1|3 (x x9)] S e, where
(0, 1) is user-defined parameter.
4.4
ITERATION COMPLEXITY
We now establish the iteration complexity of Algorithm We first restate the following standard definition of approximated critical points.
Definition 4.14. (e-Critical Point) We define Crit 2) ||A bll + E dist(O, (x(();) +
(x.( + A. 2). A solution (x, 2) is an e-critical point if it holds that:
Crit(X, ž) S
We obtain the following iteration complexity results. Theorem 4.15. (Proof in Appendix D.13 We define q' xf,, xx, 2.
Let the sequence
{q z TT be generated by Algorithm
For all p E (0,1), we have:
+ Crit( +1 O(T(P-1)/2) O(T
(14)
In particular, with the choice p = 1/3. we have + Σ Crit(q 1z S 1(33) In other words, there exists i <. T such that: Crit(q F+1 1) S e, provided that T 2 O(E-3).
Remark 4.16. (i) Minimizing the worst-case complexity of the right-hand side of Inequality (4) w.E.t. p yields: arg minpe(0.1) max(-p, 1)/2) = 1/3. Thus, choosing p = 1/3 achieves the optimal trade-off between the two terms, resulting in the best complexity bounds. (ii) To the best of our knowledge, this represents the first complexity result for using ADMM to solve this class of nonsmooth and nonconvex problems. Remarkably, we observe that aligns with the iteration bound found in smoothing proximal gradient methods (Böhm & Wright 20
-
4.5 ON THE BOUNDEDNESS AND CONVERGENCE OF THE MULTIPLIERS
Questions may arise regarding whether the multipliers z' in Algorithm are bounded, given that || < Z,3 as stated in Lemma 4.10 We argue that the bounedness of the multipliers is not an issue. We propose the following variable substitution:
2 for all Consequently,
can implement the following update rule to replace the dual variable update rule of Algorithm [ Bt
21+ = 2'
A(xx+I1 - b). Additionally, x' should be replaced with /Br 2' in ge+t
the remaining steps of Algorithm T Importantly, such substitution does not essentially alter the algorithm or our analysis throughout this paper.
We have the following results for the new multipliers 2²: Lemma 4.17. (Proof Appendix D.14) 14) We have: (a) Vt 2 O, 3 Z; (b) E 2 20 2( + Z). Here, {2, Z} are bounded constants defined Lemma 4.10 Remark 4.18. Thanks to the variable substitution, the new multiplier
|||| is bounded and conver-
gent with (min?_ [ 2111)) < + Et | 2111 < ((/T))

---

Published as a conference paper at ICLR 2025
5 EXPERIMENTS
This section assesses the performance of IPDS-ADMM in solving the sparse PCA problem, as shown in Section 2
Compared Methods. We compare IDDS-ADMM against three state-of-the-art general-purpose algorithms that solve Problem (I) (7) the Subgradient method (SubGrad) (Li et al.) 202 1 Davis
& Drusvyatskiy 2019), (ii) the Smoothing Proximal Gradient Method (SPGM) (Böhm & Wright
2021). (ii) the Riemannian ADMM with fixed and large penalty (RADMM) (Li al. (022).
Experimental Settings. All methods are implemented in MATLAB on an Intel 2.6 GHz CPU with 64 GB RAM. We incorporate a set of 8 datasets into our experiments, comprising both ran- domly generated and publicly available real-world data. Appendix Section E describes how to generate the data used in the experiments. For IPDS-ADMM, the relaxation parameter is set to be around the golden ratio 1.618, as suggested by (Li et al.) (0166). Additionally, we set (S, ō, 01,02) 02) (1/2, 1/3, 1/4, 1.01, 0. 0.60). We denote á as the regularization parameter for sparse PCA model. The penalty parameter for RADMM is set to reasonably large constant 8 = 100p. We fix 20 and compare objective values for all methods after running T" seconds, where T' is reasonably large to ensure the proposed method converges. The corresponding MATLAB code is available on the author's research wehpage.
IPDS ADMM
I..IPIG ABMM
I.-I ALMM
IR ALMM
RADMM
Okjestin
SpnGrad
Okgiettne
Ohiiedan
SunGrrd
10
10
(soconds)
Time (soconds)
(a) randn- 1500-500
(b) randn 2.00mm--5000000 500
mnnss- mmnist-1500 1500-780
mmiss 25000780
T 1-DS-PS--AA ADMM
-PDS ADMM RADIEM
IPDS ADMM RADMM
IPDS- ADMM
RADASM
RAADE
SPGM
SPUM
SPGM
SPGM
Objestne
Olggeliee
Sunindd
SalGrdd
Olgestie:
10
10
10
(e) TDT2-1500-500
(f) TDT2-3000-500
sector- 1500-500
(h) soctor-2500-500
Figure 1: Convergence curves of methods for sparse PCA with X 100 and ,00 50p.
Experiment Results. We set أ 100 and present the results for 5o 50, in IPDS-ADMM, as shown in Figure [ These experimental results provide the following insights: (i) Sub-Grad tends to be less efficient in comparison to other methods. (i)) SPGM, utilizing a variable smoothing strat- egy, generally demonstrates slower performance than the multiplier-baset variable splitting method. This observation corroborates the widely accepted notion that primal-dual methods are typically more robust and quicker than primal-only methods. (iii The proposed IPDS-ADMM consistently achieves the lowest objective function values among all methods examined.
Due to space limitations, additional experimental results are provided in Appendix Section t
CONCLUSIONS
In this paper, we introduce IPDM-ADMM, a proximal linearized ADMM that uses an Increasing Penalization and Decreasing Smoothing (IPDS) strategy for solving general multi-block noncon- vex composite optimization problems. requiring continuity in just one block of the objective function. It incorporates relaxed strategies for dual variable updates when the associated linear operator is either bijective or surjective. We increase the penalty parameter and decrease the smoothing parameter at controlled pace, and in- troduce a Lyapunov function for convergence analysis. We also derive the iteration complexity of IPDS-ADMM Finally, we conduct experiments to demonstrate the effectiveness of our approaches.
operates under a relatively relaxed condition,
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by NSFC (12271278, 61772570), and Guangdong Natural Science Funds for Distinguished Young Scholar (20188000306025)
REFERENCES
Rina Foygel Barber and Emil Y Sidky. Convergence for nonconvex admm, with applications to ct imaging. Journal of Machine Learning Research, 25(38):1 46, 2024.
Amir Beck. First-order methods in optimization. SIAM, 2017.
Dimitri Bertsekas. Convex optimization algorithms. Athena Scientific, 2015.
Fengmiao Bian, Jingwei Liang, and Xiaoqun Zhang. A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization. Inverse Problems, Problems, 37(7):075009, 2021.
Radu Ioan Bot and Dang-Khoa in the nonconvex setting: convergence analysis and rates. Mathematics of Operations Research, 45(2):682-712, 2020.
Khoa Nguyen. The proximal alternating direction method of multipliers
Radu Ioan Bot, Emno Robert Csetnek, and Dang-Khoo Nguyen. A proximal minimization algorithm for structured nonconvex and nonsmooth problems. SIAM Journal Optimization, 29(2): 1300- 1328, 2019.
Axel Böhm and Stephen J. Wright. Variable smoothing for weakly convex composite functions. Journal of Optimization Theory and Applications, 188(3):628-646 649, 2021.
E. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM, 58(3), May 2011.
Congliang Chen, Li Shen, Fangyu Zou, and Wei Liu. Towards practical adam: Non-convexity. convergence theory. and mini-batch acceleration. Journal of Machine Learning Research, 23 (229):1-47, 2022.
Weiqiang Chen, Hui Ji, and Yanfei You. An augmented lagrangian method for l ---reularideed opti- mization problems with orthogonality constraints. SIAM Journal on Scientific Computing, 38(4): B570-B592, 2016.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-239, 2019.
Wei Deng, Ming-Jun Lai, Zhimin Peng. and Wotao Yin. Parallel multi-block admm with o (1/k) convergence. Journal of Scientific Computing, 71:712-778 2017.
John Duchi and Feng Ruan. Solving (most) of set quadratic equalities: composite optimization for robust phase retrieval. Information and Inference: A Journal of the IMA, 8(3):471-529 2018.
Guilherme Franca, Daniel Robinson, and Rene Vidal. Admm and accelerated admm as continuous dynamical systems. In International conference on machine learning, pp. 1559-1567, 2018.
Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications, 2(1): 17-40, 1976.
Max LN Gonçalves, Jefferson Melo, and Renato DC Monteiro. Convergence rate bounds for proximal admm with over-relaxation stepsize parameter for solving nonconvex linearly strained problems. 1702.01880 2017a.
Max LN Gonçalves, Jefferson G Melo, and Renato DC Monteiro. Improved pointwise iteration- complexity of a regularized admm and of a regularized non-cuclidean hpe framework. SIAM Journal on Optimization, 27(1):3994407, 201

---

Published as a conference paper at ICLR 2025
Pinghua Gong, Changshui Zhang, Zhaosong Lu, Jianhua Huang, and Jieping Ye. A general itera- tive shrinkage and thresholding algorithm for non-convex regularized optimization problems. In International Conference Machine Learning (ICML), volume 28, pp. 37-45, 2013.
Bingsheng He and Xiaoming Yuan. On the O(1/n) convergence rate of the douglas-rachfone alter- nating direction method. SIAM Journal on Numerical Analysis, 50(2):700- 2012.
Le Thi Khanh Hien, Duy Nhat Phan, and Nicolas Gillis. Inertial alternating direction method of mul- tipliers for non-convex non-smooth optimization. Computational Optimization and Applications, 83(1):247-285, 2022.
Mingyi Hong, Zhi-Quan Luo, and Meisam Razaviyayn. Convergence analysis of alternating direc- tion method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization, 26(1):337-364, 2016.
Feihu Huang, Songean Chen, and Heng Huang. Faster stochastic alternating direction method of multipliers for nonconvex optimization. In International Conference on Machine Learning (ICML), volume 97, pp. 2839-2848, 2019.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), International Conference on Learning Representations (ICLR), 2015.
Rongjie Lai and Stanley Osher. A splitting method for orthogonality constrained problems. Journal of Scientific Computing, 58(2):431 1119,,44,,,00 2014.
Shuhuang Xiang Lei Yang, Xiaojun Chen. Sparse solutions of a class of constrained optimization problems. Mathematics of Operations Research, 2021.
Guoyin Li and Ting Kei Pong. Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization, 25(4):2434-2460, 2015.
Jiaxiang Li, Shiqian Ma, and Tejes Srivastava. arXiv:2211.02 2022.
riemannian admm. arXiv preprint
Min Li, Defeng Sun, and Kim-Chuan Toh. A majorized admm with indefinite proximal terms for linearly constrained convex composite optimization. SIAM Journal on Optimization, 26(2):922- 950, 2016.
Xiao Li, Shixiang Chen, Zengde Deng, Qing Qu, Zhihui Zhu, and Anthony Man-Cho So. Weakly convex optimization over stiefel manifold using riemannian subgradient-type methods. SIAM Journal on Optimization, 3103):1605-1634 2021.
Qihang Lin, Runchao Ma, and Yangyang Xu. Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization. Computational Optimization and Ap- plications, 12(1):175-224, 2022a.
Tian-Yr Yi Lin, Shi-Qian Ma, and Shu-Zhong Zhang. On the sublinear convergence rate of multi-block admm. Journal of the Operations Research Society of China, 3:251-274, 2015a.
Tianyi Lin, Shiqian Ma, and Shuzhong Zhang. On the global linear convergence of the admm with multiblock variables. SIAM Journal on Optimization, 25(3):1478- 1497, 2015b.
Zhouchen Lin, Huan Li, and Cong Fang. Alternating direction method of multipliers for machine learning. Springer, 2022b.
Dekai Liu, Song Li, and Yi Shen. One-bit compressive sensing with projected subgradient method under sparsity constraints. IEEE Transactions on Information Theory, 65(10))6650-6663, 2019.
Wei Liu, Xin Liu, and Xiaojun Chen. Linearly constrained nonsmooth optimization for training autoencoders. SIAM Journal on Optimization, 1233):1931 2022.
Yuanyuan Liu, Fanhua Shang, Hongying Liu, Lin Kong, Licheng Jiao, and Zhouchen Lin. Acceler- ated variance reduction stochastic admm for large-scale machine learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(12):4242-455 2020.
12

---

Published as a conference paper at ICLR 2025
Zhaosong Lu and Yong Zhang. An augmented lagrangian approach for sparse principal component analysis. Mathematical Programming, 15::149-13, 2012.
Zhaosong Lu and Yong Zhang. Sparse approximation via penalty decomposition methods. SIAM
Journal on Optimization, 23(4) 2444224488 2013.
Renato DC Monteiro and Benar F Svaiter. Iteration-complexity of ditoopiccoooooitionnn algorithms
and the alternating direction method of multipliers. SIAM Journal on Optimization, 23(1):475- 507, 2013.
Boris S. Mordukhovich. Variational analysis and generalized differentiation i: Basic theory. Berlin Springer, 330, 2006.
Y. E. Nesterov. Introductory lectures on convex optimization: a basic course, volume 87 of Applied Optimization. Kluwer Academic Publishers, 2003.
Robert Nishihara, Laurent Lessard, Ben Recht, Andrew Packard, and Michael Jordan. A general analysis of the convergence of admm. In International Conference on Machine Learning (ICML), pp. 343-352, 2015.
Yuyuan Ouyang, Yunmei Chen, Guanghui Lan, and Eduardo Pasiliao Jr. An accelerated linearized alternating direction method of multipliers. SIAM Journal on Imaging Sciences, 8(1):644-681) 2015.
Thomas Pock and Shoham Sabach. Inertial proximal alternating linearized minimization (ipalm) for nonconvex and nonsmooth problems. SIAM Journal on Imaging Sciences, 94): 2016.
R. Tyrrell Rockafellar and Roger J-B. Wets. Variational analysis. Springer Science & Business Media, 317, 2009.
Li Shen, Wei Liu, Ganzhao Yuan, and Shiqian Ma. Gsos: Gauss-seidel operator splitting algo- rithm for multi-term nonsmooth convex composite optimization. In International Conference Machine Learning (ICML), pp. 3125-3134, 2017.
Kaizhao Sun and Xu Andy Sun. Algorithms for difference-of-coneeen programs based on difference- of-moreau-envelopes smoothing. INFORMS Journal on Optimization, 5(4):321-339, 2023.
Quoe Tran Dinh. Non-ergodic alternating proximal augmented lagrangian algorithms with optimal rates. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018
Manolis C. Tsakiris and René Vidal. Dual principal component pursuit. Journal of Machine Learn- ing Research, 19:18:1-18:: 2018.
Junxiang Wang. Fuxun Yu, Xiang Chen, and Liang Zhao. ADMM for efficient deep learning with global convergence. In ACM International Conference on Knowledge Discovery & Data Mining (SIGKDD), pp. 111-119, 2019a.
Yu Wang, Wotao Yin, and Jinshan Zeng. Global convergence of admm in nonconvex nonsmooth optimization. Journal of Scientific Computing, 78(1):29-6) 63, 2019b.
Yi Xu, Mingrui Liu, Qihang Lin, and Tianbao Yang. Admm without fixed penalty parameter: Faster convergence with adaptive penalization. In Advances in Neural Information Process- ing Systems (NeurIPS), volume 30, 2017.
Lei Yang. Ting Kei Pong, and Xiaojun Chen. Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction. SIAM Journal on Imaging Sciences, 10(1):74-110, 2017.
Maryam Yashtini. Multi-block nonconvex nonsmooth proximal admm: Convergence and rates under kurdyka-lojasiewiczz property. Journal of Optimization Theory and Applications, 190(3):966- 998, 2021.
Maryam Yashtini. Convergence and rate analysis of proximal linearized ADMM for nonconvex nonsmooth optimization. Journal of Global Optimization, 84(4):913-95 2022.
13

---

Published as a conference paper at ICLR 2025
Ganzhao Yuan. Smoothing proximal gradient methods for nonsmooth sparsity constrained optimiza- tion: Optimality conditions and global convergence. In International Conference on Machine Learning (ICML), 2024.
Ganzhao Yuan. Admm for structured fractional minimization. In International Conference on Learning Representations (ICLR), 2025.
Jinshan Zeng, Shaobo Lin, Yao Wang, and Zongben Xu. 1/2 regularization: Convergence of it- erative half thresholding algorithm. IEEE Transactions on Signal Processing, 62(9):2317-2329, 2014.
Jinshan Zeng, Shao-Bo Lin, Yuan Yao, and Ding-Xuas Zhou. On ADMM in deep learning: Con- vergence and aaturation-avoidanee Journal of Machine Learning Research, 22:199:1-199:67, 2021.
Jinshan Zeng, Wotao Yin, and Ding-Xuan Zhou Moreau envelope augmented lagrangian method for nonconvex optimization with linear constraints. Journal of Scientific Computing, 91(2)661 2022.
Jiawei Zhang and Zhi-Quan Luo. proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal Optimization, 30(3):2272-2300 2020.
Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhi-Quan Luo. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. In Advances in Neural In- formation Processing Systems (NeurlPS), 2020.
Ruiliang Zhang and James Kwok. Asynchronous distributed admm for consensus optimization. In International Conference on Machine Learning (ICML), pp. 1701-1709, 2014.
Daoli Zhu, Lei Zhao, and Shuzhong Zhang. A first-order primal-dual method for nonconvex con- strained optimization based on the augmented lagrangian, Mathematics of Operations Research, 2023.
14

---

Published as a conference paper at ICLR 2025
Appendix
The organization the appendix is as follows:
Appendix
A
covers notations, technical preliminaries, and relevant lemmas.
Appendix
B
provides additional motivating applications.
Appendix contains proofs related to Section
Appendix D
offers proofs related to Section
Appendix includes additional experiments details and results.
A NOTATIONS, TECHNICAL PRELIMINARIES, AND RELEVANT LEMMAS
A.1 NOTATIONS
We use the following notations in this paper.
[n]: (1).
x: x - {x1, X2,...,...; Xn. = X/n]-
X X(ay] 2 {xi, Xi+1, .., XjJ, where 2 i.
4 L = I + 3r A [B. Note that the function G(x, , is L Li-smooth w.t. x,-
σ1 01 A a
E R. where a E (0, Refer to Lemma A.2
02: 02
-1-1ー-11 E IR, where E (0, Refer to Lemma A.2
|x|| Euclidean norm: ||x|| = ||x|| = v(x, (x,x)) x).
(a, b) Fuclidean inner product, i.e., (a, b) E, a.b,
A T the transpose of the matrix A.
X₁: the i-th block of the vector x E (di do with x; E Rdxx]
X: the largest eigenvalue of the matrix A, A.
A: the smallest eigenvalue of the matrix A,
X': the smallest eigenvalue of the matrix A, Ap
|| the spectral norm of the matrix A.
I, : I, E RREx,, the identity matrix; the subscript is omitted times.
(x()) Indicator function of a set Ω with (x(x) = if x E Ω and otherwise +00.
vec(V): Vector formed by stacking the column vectors of V with vec(V) E Rd'x"" xr'
mat(x) Convert x E (d'-r')x into matrix with mat(vec(V)) V with mat(x) e Rdx
dist(St R¹):
distance between two sets with dist 92) 2 infwent ||w- - w'].
A.2 TECHNICAL PRELIMINARIES
We present some tools in non-smooth analysis including Fréchet subdifferential, and limiting (Fréchet) subdifferential (Mordukhovich) 2006 Rockafellar & Wets. 2009 Bertsekas 2015). For
any extended real-valued (not necessarily convex) function F R
+00, its domain
defined by
dom( F)) A E R" -00 F(x) +00].
The Fréchet subdifferential of F at x E dom( F), denoted as Fx()). is defined as
åF(x) A E R" lim inf F(x) 2 0}.
x
x-x
z
The limiting subdifferential of F(x) at x E dom(F) is defined as:
aF(x) A (VER" * F(x*) F(x), & OFF(t)) vv
15

---

Published as a conference paper at ICLR 2025
These subdifferentials satisfy the following key properties:
(a) holds that (F(x) _ OF(x).
(b) If F(.) is differentiable at x, then (F(x) = 0F(x) = (VF(x)) with V (x) being the gradient of F.)) at x.
(c) When F(-) is convex, both (x) and (x) reduce to the classical subdiffretaal for convex functions, i.e., 0F(x) - 0F(x) - (v F(z) F(x) (v, x) 2 0, V.).
A.3 RELEVANT LEMMAS
We present several useful lemmas, each independent of context and specific methodology.
Lemma A.1. (Pythagoras Relation) For any vectors E RR. b E IR" E IR", we have:
5 bl - bll 1 |llc bll2 = b| - cl1 + c
|bbl2 1/1c- bll2 = / + (b- c.c).
Lemma A.2. Assume (0, Let b+ oa (1-o)b, where b+ E R", b R", and R". We have:
b 13 v の |aa|
+ b1 | (b-18))
a where 01 (1-11-a] )2, and 02 -
A
|| |--0|
-1-11--11-
Proof. Part (a). When o = 1, we have 01 = 1, 02 = 0, and b+ a. The conclusion of this lemma clearly holds.
Part (b). We now focus on the case when o * 1. Noticing |1 - -o| * 0 and 1 - |1 o * 0, we
rewrite b+ (1 (1-op o)b + into the following equivalent equality:
b+ = -
(1- |1- ol) 1-1-a| da
+ - 0| (1-r)b
T1-ol
Using the fact that the function
|| 11112 is convex and | 1 ol E (0, 1), we derive the following results:
|b+112 s
ol) ll 1-11-- 112 + |1 al 11 lB
||a|| + |1 - ol |bb/2.
Subtracting ([1 - al ||b+ from both sides of the above inequality, we have:
[1-11-o]] - bb - |ali + 11
(l] | bb+l)))
Dividing both sides by a11 - のه} we have:
|- 7 b 11 < و (1-1o-)-=laa13 + a(1-)1-o)
1
(1bbl
||b 113.
Using the definition of σ1 and d2, finish the proof of this lemma.
Lemma A.3. We let t 2 1, and q E 1). We have: } + 1)2 1 2 1.8
Proof. We let h(t)= A (1 + 1).8 1 41
Initially, we prove that f(4) 2 - - > 0 for all 2 0. Given vf(g) = 2 log(2) (2g(2)-5 -
20 log(2) 3 0.1931 0, the function s(g) is increasing for all 0. Combining with the fact that f(0) = Ó, we have: f(q) 2 0 for all q 2 0.
We derive the following inequalities:
Vh(() q1--1 ((= }} q(p-1 [28-1-- -9) 1 918-1 (9/2+1
3 9
2
16

---

Published as a conference paper at ICLR 2025
where step 1 uses 1+1 < 2 and 9 1 I 0; step 2 uses 2 2 + 1 for all q 2 0; step @ uses
1 - q 2 0. Therefore, h(t) is an increasing function.
Finally, noticing that h(1) = 2 1 y 2 O, we conclude that h(t) for all t 2
Lemma A.4. We let p E (0, 1) and 2 We have: (t+ 1)P to S pt
Proof. We notice that h(t) _ t" is concave for all t 2 and E (0, 1) since Vh(t) = pt and
htt(t p(p 1)th < 0. It follows that: Vr, y 2 1,h h(x) I (y I. Vh(x)). Letting x = / and y = + 1, for all 2 1 andd E (0, 1), we have: (t + 1)2 1p ppp-1
Lemma A.S. We let E 10. We huve: Et=
[++))--1P 1F
2
Proof. We have:
[++1)²- 12 )2 Disl 1o
12D-2
-1= 1-2 8 12
t=1
12
where step uses Lemma A.4 and p S 1; step @ uses Et=l
12 S 1==
1
00
<2
Lemma A.6. We let p E (0, 1). We have: 2 TT S ΣT t < p(1-p)
1-p
Proof. We define h(z) = x -P and g(x) = --pp r' Clearly, we have: Vg(z) = h(x).
By the integral test for convergence
we obtain: |+ h((x)de S E M(1) S h(1) + S M())d..
Part (a). We have: Σ P 2 S T+ Pdr (T+1) =1) (T+1)-
1-p 1 TT--P
where step @ uses Vg(x) = h(x) = p; step 2 uses Lemma
A.3 with 1 1
p and t TT
Part (b). We have: Etn 1 < h(1) + 1 x . _ 1+ (() -g(1) = =1 (1) - p) 1- 1-p where step @ uses h11) and Vg(x) = h(x) P
7 --
Lemma A.7. Lef E (0,2), and et+1 11 ale" S oyt for all L 2 1. We have: et S e 03 max (-1 p', where 1-l1-al E [1,
Proof. Given (0,2) 2), we define o, $ 911 0.1))
We derive the following results:
1, c²
s 0,e² +op'
= 2, e
< o,e² + top s ofet + t,,0p' top
= 3, e²
v 0,6² tap S soje² topo'' + topop' + op
t= T+1
I 0,e top sotel + I of -p.pp.
Therefore, we have:
T+1
V^
oT + T o. ip
et + 1/ 1Et of
v
e'+o/max --
17

---

Published as a conference paper at ICLR 2025
where step I uses o.= Σ 1; step @ uses the fact that:
T Σ o.= T- =o T-1 ... + 0- 1-0. S 1-0."
1-0!
Lemma A.8. Assume & E (1, (0, 3( 1)). For any 0 > O, we define
f(0)
o(6 + 88 1/k)²
We have f(0) 2 8ø' where 0 20(1+5)² + 1/--
841
Proof. Initially, given (1, E (0. ( _/ 1)), we have:
1/x-6 -- < 1.
(15)
Setting the gradient of ((0) w.r.f. yields:
20(6 0 + 50 - -1)))11k)(1 +1+ = It follows that the
1/x-6 solution 20(1+8)² + 6+1
the maximizer of the concave function f(0). We have:
f(0)
-
0 - - - 2(6+02 + 802 - 1/x)²
1/x-A
11
4(1+8)²e
6+1
IV IV8 IV8
T(1+8)=e +0
4(1+1/3)²e
where step @ uses the definitions of [0) and 0: step @ uses the first Inequality in 11): step @ uses the fact that 5 < 3: step ① uses x (1 + 1/3)² < 8.
B ADDITIONAL MOTIVATING APPLICATIONS
Robust Sparse Regression. Robust sparse regression (Liu et al. 2019) utilizes the f--nrr of the residuals to ensure robustness against outliers while enforcing sparsity via fo-morm constraints to identify key variables. The problem is formulated as: miny GG - z||1, s. t. v E f2 & {v || S s). where á 2 0 is an integer, G E I and z E Rrh By introducing new variable y, this problem can be formulated as: miny (v( + ||y||,, s.t. Gv + z. It corresponds to Problem (1 with x; v, X2 y. (x,,) = f2(x2) = 0. (x,)) (v),, (x())) = ||yll and -2 and Condition IBI.
A -I=
A2
Dual principal component pursuit Tsakiris & Vidal 2018) used primarily in subspace clustering and outlier detection, aiming to robustly repre- sent data structures across different subspaces in the presence of noise and outliers. The prob- Ω e (VIVTV ||l,2,1 A Σ, (i.)). By introducing a new variable Y, this problem can be formulated as: minv,y Y in (V) + Y 2,,1 s. - -GV + Y 0. It corresponds to Problem I with
Dual Principal Component Pursuit.
lem is formulated as: miny | 12,1, t.
I), where
R and
vec(V), X2 = vec Y). (x f2(x1) = 0, (x1) = (V))., h2(x2) = Y 2,1. and A = G
Ag I, b
and Condition BT.
Robust Low-Rank Approximation. Robust low-rank approximation (Candès et al., 2011
the {-normm of the residuals to ensure robustness against outliers while imposing a low-rank constraint the solution matrix The problem is formulated as: miny |[G(V) 2||1: V P
{V rank (V) S $). where 2 is an integer, G(-): : Raxi + R and z E R By introducing a miny,y y (a (v( |yll,, s.t. - G(V) +y -2. corresponds to Problem [ with x; = vec( (V, X2 = y. (x,) = f2(x,) = 0. h (xi) = (V()),
new variable y, this problem can be formulated
(xx))) = ||y]], A|x; GVV, A₂ = I, z, and Condition BB.
18

---

Published as a conference paper at ICLR 2025
C PROOFS FOR SECTION 3
C.I PROOF OF LEMMA 3.1
Proof. Consider the update rule 3 = EI,, where p E (0, 1).
Part (a). We have:
g++ 3 EB _ E + 1P) - - _ - 5 0,
2
where step ① uses the update rule 3r = 00 + Eth; step 2 uses the fact that the function h(t) - (t + 1)P - t" is monotonically decreasing w.z.. t that: h(t) - h())) =
@ Part (b).We derive: Ln S 3d0 S 8A8, where step 1 uses 3r 2 g
C.2 PROOF OF LEMMA 3.4
Proof. We let u E Rdd be fixed constant vector. We assume p2 < 111 We define: h(u;jn) min, h(v) 2p1 || ul3. and h(u; (2) _ min, h(vv 2p2
||
We define P1 A (1: A min h(v) + 2p11 ||v ul.
We define P2 A (1; arg min, h(v) + 2pz || ul 1/3-
We let gi E (h (u: )). and g2 E (h(Poox (u; n22)).
Initially, by the optimality of L1 A Prox, (1) and P2 - (u; we obtain:
u P1 E un (Poox (1; = 1111,
(16)
n1 - P2 E u22h (u: (2)) = P2g2-
(17)
Part (a). We now prove that 0 <
h(u:p))-h(upp)))
We have:
P1-
Mu: h(1;)1)
2j1
P
2pz
1
u
p2ll2 h(p:)) h(p2)
1
||u
- Pı
12
1
|1-p2 + (P1
P2. g1)
2j1
2
1
g
112
Ba
12
(1282 (1g1.g))
||g
1
Ma
11
2 |gg
182
12 (g2 g
2
4 gg 31
where step ① uses the definition of huu; u); step uses the convexity of lc()); step uses the
optimality of p1 & (1; and P2 - Proxa (u: (u2) as in 16 and 17 1 step @ uses μl2 < Ph1
Part (b). We now prove that Mu:zz))A(upp)
< 2 Ch.
We have:
P1-#2
Mu: h(1;)14)
118
Pa
12
1 u
P h(p2) - h(p1)
2pz
2p
P2
||u
1 + 1 -P.
2pz
2p1
4
4
12
+ (Migi #2B2.82) 82)
A 11
lg
12 + 14 (g2.g)) 81)
1
182
19

---

Published as a conference paper at ICLR 2025
where step ① uses the definition of h(u: μi); step @ uses the convexity of h(-); step 3 uses the
optimality of Pı - Prox (u; (41) and p2 Proxa (2) in (16) and 17); step
f the
inequality that: - 22llg: (g1, g2) S 2l 12 for all g1. 81.82 E TR step @ uses |gal S Ch- L
C.3 PROOF OF LEMMA 3.5
Proof. We let u fixed constant vector. We assume
< #2 < P11
We define: p(::p) & minverexi h(v) + 2/ l/ ul/2-
We define: Prox, (u: arg mi h(v) 2n l|v u 112-
Using Claim (b) of Lemma 3.3 we establish that huu; p)) is smooth w.t. u, and its gradient can be computed as:
Vh(u: = (m-
We examine the following mapping H(v) _ v(u Couu-Proxia (u: !)) with H(v) R ++ IR". We derive:
(u+8)(u- (u uto (o---uuu (u:
lims-v0 M(v+5)-HH(C H(()
lims-0
lims-o (u-(u+d) Prox, (u: Proxn
Prox,, (u: !).
Therefore, the first-order derivative of the mapping H(v) w.t. v always exists and can be computed as V.H(U) = u - -roox (u; t). leading to:
Vu, > 0, |[H())- R(O'll |w-v'l
& ||u - -Prox, !!I-
Letting 1//2 and v' 1/p2, we derive:
2 (V((raa)-VW(as)) |u Prox, (w; @ f4 (Prox, (u: $ l4 ChCh. 1//m
where step uses the optimality of Proxs. (u: μi) that @h(Poox (u: n)) + (Proxa (uroox(uupp (u: u) for all step @ uses the Lipschitz continuity of h(-). We further obtain:
| [() - v h(uu & 11/M1 1/1al piCh = (11/U2 - 1) Ch.
C.4 PROOF OF LEMMA 3.6
The proof of this lemma is similar to that of Lemma in al. 2022). For completeness, we include the proof here.
Proof.
We consider the following strongly convex problems:
Xn arg min h, (Xai μ1) + |x,, - cl12
X (Xn, Xn) = arg min h (*xn) +
+
24
1 |xn - x 112 + f cl12-
xn.8n
We have the following first-order optimality conditions:
0
1 (x,, xn,) + p(Xn - c)
(18)
o Th (Xn())n) + 1/2 (X., - x.).
(19)
Part (a). Using 18
we obtain: 8n. 1/utp's ( 12 + pc). Plugging this equation into
19 yields:
0 E Th, + [xx 1/uto 1 xx + pc))
Thn T (Xn -c).
20

---

Published as a conference paper at ICLR 2025
The inclusion above implies that:
Xn = arg min hn (xm)
Itup |x,, - c112.
P
Xn
Part (b). We derive:
p n, c)
1
22 12 (X Xn.
E
Oh (8k),
where step @ uses 18 step @ uses (19p.
Part (c). Using
19 we have: Xn X,, = ----ppp -n (Xx)) This leads to |x,, xn S μC
D PROOFS FOR SECTION 4
D.1 PROOF OF LEMMA 4.1
Proof. Part (a). We now focus on sufficient decrease for variables {x1, ,2..,, .n-1) We define
of = G(x 11 4+1 xf
[11 3²; - I xf
[1,1-1] xf.
[1 2
where
i E [m
Noticing the function G(x(1,i-1) 1]: xs x 1, z" ; (0) is L-smooth w.r.t x; for the t-th iteration, we
have:
G(x x [m] z'; )* G(x 1p xf, x;, xft+ 3';
S (xf++1 X Xx, G(x 11 x x 1,) 2 ())))) L ||x| -x/12
(20)
Given 1+1 is the minimizer of the following optimization problem:
x
++] E arg minx, hx(x:) + (x; x Vx, G(x 1] x,, x x| (²) + MLi
2 X - x
x The optimality of s+1 leads to:
h4(x]+1) (x{)) (x}
Xx G(x 1): x [1 z z9: S
PLLi
||x
x (21)
2
Combining equations 20 and 21). we derive the following expressions:
$ S ( 2) x[lx x 1l2
Telescoping the above inequality over from 1 to (n 1) leads to:
E Φf Σー= (C} ()) L[|lx x11
Therefore, we obtain:
C(x 11: x zt: 8r x²) L(x', zt; 8 n²) < >E ( 4) L1|lx x21
(22)
Part (b). We now focus on sufficient decrease for variable {x,}. Noticing the function
G(x [1,= Xn, (() is L -mooth w.r.t. x, for the t-th iteration, we have:
((x(it--11 x-+1 22:85 G(x [1m-1] x², z²: 8
6+1 < (xt+1 x Vx, G G(x(LLn-))= x 22:18))) + 44 ||x ++1 1
(23)
Since (X,' p²) ) is convex, we have:
hn [x((+++1 11 n.) - hop (x 10))
xt1 x11 Vhn (x} ((²)
(x/+1 x,+11 - G(x]+1 1 (x,,1 -x,)).
(24)
21

---

Published as a conference paper at ICLR 2025
where step ① uses the the first-order optimality condition of x that:
0 Vhn (x n²)) + xx.. G( x z²; ;²)) (xx+1 x²).
Adding Inequalities
23 and
together, we have:
Ni (x, n2 ;14
++1
hnn (x)) + G( [1m-1)) x+1 ,²2:3") - G( [1, X,x 21;
< 2 | x 112 42L
( 02) || x || x
L'
This results in the following incquality:
L(x 3 ,²) - [( +++
1]: 2'; B (() S ( - 02) L [ - x,
(25)
Part (c). We now focus on sufficient decrease for variable {z}. We have:
C(x++1, 211 3 n²) [(x +1 31;
(Ax b, z²)
(a (2' =2'), z²)
o ||z - =2.
(26)
where step @ uses zz+1 = z' + (Ax*+1 b) with Ax & Σラ= A,x,t!
Part (d). We now focus on sufficient decrease for variable (B). We have:
C(x++1,
z gt+1
1²) [(x 2zt11 12)
(8
8¹
A - -b113
2
2
1
(8111
2
g'
2
|ll
7,
(z -+ x2)112
(1+))3*
gr ||
(xl+1 zz" x2)112
03
||z +1 z² 211
(27)
where step uses +1 = z' + 0 (Ax b): step uses Lemma 3.1 that Be+ (1
Part (e). We now focus on sufficient decrease for variable {u]) We have:
L(xt+1 "art,,z* 21t11,8t gt41 11t111,t1))) [(x ,z gtt2 g(42,1() ,1²²
(x/+ :1tt1) hnn hx (x++1; k²)
C - 10dd-x(t)) t²))
(28)
where step uses Lemma
3.4
Combining Inequalities
22
125
26 27
and 28
we have:
L(x +1 z + gr+1 11+1)=
C(x' 2'; ,1²)
< - [(} 4)
- + (1 02) L1 - x
+(1 + 5 o (+1 10-1-11 21113 + Ch - pp(t1).
(29)
We define 0 A L(x', (1.3%.1))) + 2 Cnjus 63 A E1 A 201 1. and E++1
6s || - z0113 +
e2L - x 12 81 E Li|[ ++1 xt We have:
g1+3 + 0 (+1 0
S L 02 + 82) L [x|+ x + (1+
20 + o
1 2 - =2.113
22

---

Published as a conference paper at ICLR 2025
D.2 PROOF OF LEMMA 4.2
Proof. For any i E [n]] we define u - 0,L,[x!-1 x - 3' A' A,(x) - -x3]
and let
wit (x, 1 + fi(()))
We notice that x
1 is the minimizer of the following problem: ++1 arg migg, oii
||x, - x + (x. x Vx, (1 x [in) [.n].22:177 (8)
Using the necessary first-order optimality condition of the solution x we have:
Vx. Gx 3²: E -Oh,(x ( -x x().
(30)
Using the definition of the function G(x, z: B) [|===111: - b, + 1 A
Σj=1 (x,), we have:
Vx, (1) x [im] 39)
= V((((()) + A7zz z + A 3
b}
= ((((()) + A72x + 3" AT (Ax -A [-}= A, Ax(x }|
b+
V((x() + + [
Ay(x) }}
(31)
where step 1 uses the update rule of z11 that -z' 3 (Ei=) Axt ++ b). Combining
the Equalities (30) and BT., we obtain the following result:
0 E 0h,(x:+) + 0,L - x41 + V
+AT + A'
- )] + (z -z').
Using the definition of w and ni+1 for all i E [n]]. we have: 0 wet1 + uut1 + AJz +
A (z" ++1 z²). Multiplying both sides by E (0, for all t 2 O, we have:
0 ow? A, + (z
2²) + tou
(32)
Given that can take on any integer value, for all / 1, we derive:
0 = ow! + AA. + A (z' - x² -² + on
(33)
Combining Equality 32 and Equality (3) for all t 2 1, we have:
A! (zl +1
z²)= = (1 - 0 A (z' x' 1 - a (w wi) an - nn)).
(34)
In view of 34 we let = n and arrive at the following two distinct identities:
BT: :
z²) = (1 - σ) (A x 1)) to (11 11
1+1 + w w 1+1
Aaa
SU: ; A (z 1+ - 2²) + outt1 = (1 (AT -z--1) ouu)) + olou' + wy - w 1+1)
Batil
Aat
D.3 PROOF OF LEMMA 4.3
Proof. We denote Q' 8 - B' A.A.A. E Rd:xd;
We assume A A,A,, has the singular value decomposition A,A., = ÚT ddaag(A( where U e Rdd xd; X E Rd,x1 and Ü = ūūT = Ia. Here, diag(A) denotes diagonal matrix with X as the main diagonal entries.
Part (a). We derive:
T L Im BB < xx5 + +1,
(35)
23

---

Published as a conference paper at ICLR 2025
where step T uses Lemma 3.1 that Ln I 6
Part (b). We have:
@ QQ = 1022 - 11 = 02l,, min( S A/35 (02(1 + 8) - 21/2),
where step @ uses
|02
100--3'AT0 A = | (02L B || = ||02 B² > step 2
uses the fact that |1 step @ uses Inequality
1x-
x 00 max(p - -x)
-x)= p min(x) whenever p 2 max(x) for all p and x;
33
Part (c). Given u
(x - xx) as presented in Lemma 4.2
we have: || S ||
||x| x I 9/
|
1-1
xl1
D.4 PROOF OF LEMMA
Proof. For any [1, we define σe (1-11-aパ3) and 02 - ||-0|
a1-11--]
We define wh-1 hh (xx+ ++1 2² + V fn (x
We define a a+ _ A (z ++1 z²), and xt u 1
x++
+ b. -v
We define a = w and A' - 1
3r 11.
We define b 3w0 A
and B A # (1all - x +1-1++11000 111
We define U b
(4- / 1)2.
First, we bound the term ||ee1 ||. For all 2 1, we have:
||0||| = ||w - wht1
1+1 + uh - n
/hn, (x+++ n1)) (x : p " ||| + (z,, fx 1]| + || =
Vhn (xc/+ 11)) Vh, /1"
Ln 1x - -x,--1 +/un - u
(x +1, ; - (x : 22²) ) + Vh (x 11²) - Vh, (x 1ا""
+Lm|lx -x,-1| + |/u u
# ||
++1 - x + ( 1) + L,,lix - x + || || + || ||.
(36)
where step ① uses the triangle incquality; step @ uses the fact that (x) is L,, smooth; step @ uses Lemma and Lemma 3.3
Second, we bound the term
wai
||.1 For all t 2 1, we have: Aat
| Xpt
3we, Agt
(1
|x+++
x1, + || 1)) +
Swa,
A0 4² - 1)2 +
Ch
3wos
(I - + ||
A0
Les
A3* ((#11x
x 11 + 11)2 + (L ||| || 1++1 - -x,,1 + || 1 11)] + U + b(B' B
3wsi
2( + T) ||x 4-1 - 11 + U + 6(13' - -
6wo ix + q)2 A ||x
- - u' - b(B' - BI+1)
=
x
1+1 x 12 + U + MIB BB+11,
(37)
24

---

Published as a conference paper at ICLR 2025
where step @ uses Inequality 40 and the fact that (a (a+bb + + c)² < 3a² + 3b3 + 3c for all a, R;
step @ uses the definitions of {b, B 3 step @ uses Lemma 4.3 that: ar - 6AB', Ln 8A8 and
||a || < || ||x - -x, - |x - x |l: step @ uses B < L 8*X+ Ln.
Finally, we derive the following inequalities for all t 2 1:
I I iie
agt ||
2/11
|AT
++1 - =21112 .コ |
10.5
Row
||a'
# ||a
+ X 1|0112
|| l12
mew /मP || + 1/3 + 2 # 1
Eakt
a(A' A + x - x 12 - U b(IB" - -B* B )
where step uses and o, that:
2/ 1 || 2| for all z: step @ uses Lemma A.2
with b = =a, b = at+1
oge aa 11 - क (|| 1 + st ||c 13:
step @ uses-
S मिा. step @ uses Inequality (37).
D.5 PROOF OF LEMMA 4.5
Proof. We define čι A 10 2. and A 02 X.
We define f(02) 2 (02 - 4 e(ō + 02 + 502- 1/K)², and x A e(6 + 02 + 020 1/x)².
We define 0' - 0 + Oμ, where 04 _ a& + DB
We define g++1 [2] E L x
++1 x + + - x2,11 + S 1z 2/112
Part (a). With the choice 01 = 1.01, it clearly holds that _ 1 - 0.
Using Lemma
A.8 with 0 02. we have f(02) ž
1 82
0, leading E (02 - 0.
Part (b). Using Lemmas 4.1 and 4.4
we derive the following two respective inequalities:
g++1
+
04+1
0
( 0g + E2) + x + ~ه || 2'11
(38)
1z
++
0¹ -t xL |x x", U
(39)
Adding Inequalities 38 and
39 together, we have:
g1+1 01+1 0- - NJ < L4 |x x 1/ 02 + 82 + x] 0
where step I uses the definition of E2 - 8₂ -x- X-
D.6 PROOF OF LEMMA 4.6
Proof. For any E (0, 1), we define σi A a [1-1--0]- and 02 A |1-
We define w Vh (x (+1 nz) + (x
We define a 1+1 A A. (z ++ z²) ou and at A out w/, wtt1
We define a A 2w0z and A 3r | -2g2 2
We define 6 6was and B' (Ln 1xc - x +
25

---

Published as a conference paper at ICLR 2025
We define U
CRb gr
(4==" =² 1)2.
First, we bound the term ||a* For all 2 1, we have:
| = | - ,, [+[+1 + ou'
hnn (x
(+1 (x==t(1'²) :1'²) (x H² " II| + II - (xx(x)) I|| + +
V hn (x +1 ;1') - Vhn (x 1111 + Izn || X2 - -x,--,,,,-
)]|
+1 x1=
a |
Vhn (x 11, 14) - Vhn (x)) + Whn (x n2) hh (x : || + Lnlixh - x + o
x
x || + (+ 1)C,, + Ln |
x || o||uا|1
(40)
where step @ uses the triangle inequality; step @ uses the fact that (x) is In smoothh; step 3 uses Lemma 3.3 and Lemma 3.5
Second, we bound the term
2 X
|
- 1, For all 1 2 1, we have:
2wir A ||
1++ 112 +
2 A
|
11
2we A
|1
112 +
twes XB
ب+ي ||x ||xx++1111 - xt, 11) +
Buas (
(4-- - C) +
Buds
(Lnllx) x + o
AB
A3
U1
18
20m
|| 1 + 3( ||x - x 11) 3 [| x x 1|) U + b(BB' - 1B
2
2wm 3'
x²(33)2 12 + 38 + 3(5 + og)² ) || xx 11 + U + b - B
@
2nm. 10²9² 2 + 30 3(6 + + A3 | x x1, + U + b(B' B
S X- - 112 + U2 + b(BB - B(B'-B'(1) BL+1),
(41)
where step @ uses Inequality (40) and the fact that (a + b-bb+c) c)² < 3a² + +3 3x for all a, b, E R;
+
step @ uses the definitions of (b, BB U'): step @ uses | || < Q ||| - - S 3 >gllx xfll and In S X3 as has been shown respectively in Lemma
4.3 and Lemma 3.1 as well as the
fact that pe Nd; step @ uses K= X/2, and the fact that 01 when o E (0, 1); step @ uses
T L. A x Ln.
Finally, for all t Z 1, we derive:
o ||z +1
zz 112
I^
[z 2z)
x
8
|| ++ - -ou
X a33
2w
1 ||a
11 o 11 112)
A
2/
a +1 11
11 + x
1
2n de
A /
||a'l1
2e - |la +
113
2 2 ||
1
1
++1
P
aA*
- rh! 1-|
aA' - at
1+1 + || - x
+
+BB
6B' - BB
where step C uses the fact that x|| < ||A 3 for all x; step 2 uses the definition of +11 step
@ uses the inequality ||a + bll S 2|aa||3 + 2| |/ for all a and b; step uses Lemma A.2 with
b = a², b+ = + and et that
t3 12 S
3100 (1a 11
26

---

Published as a conference paper at ICLR 2025
step S uses Bi S geir and 01 1 when (0, 1); step @ uses Inequality (41).
D.7 PROOF OF LEMMA 4.7
Proof. We define g1+1 s i-l L +1 x(1le +2
x
- 1|
zz
We define O' 0 0 where O - aA + bB*.
Part (a), We assume Ç = = f. where E (0,1). We have:
w 1 $ =
(42)
02 + 028 v 02 + 02c.
(43)
where step uses c/N S since R 2 1. We further obtain:
02 f3 q² (6 + 09) + +
E2
02
9 (c+ eq) + +
00 2
77 + (1++1) q)² +1
V@ IV
00
12cl (lg))))) 3
+ (1+ + 02 + 02c)² + 1}
0.02,
where step ① uses (22 8g- = 1.5. Part (b). Using Lemmas 4.1 and 4.6 we derive the following two respective incqualities:
S c, 8
S
e
step
uses
43 step uses the choice c 0.01 and
g(+
0/+1
0
S
02
wi 1 x² 113.
aBt | 11 + 0/+1 o
S
x - x², 112 U..
Adding the two inequalities above together leads to:
gh. + O -
θ - U - LA |xx -x x2, 13 02 + + x} _ 0,
where step O uses the definition of - 02 2/2 X.
D.8 PROOF OF LEMMA 4.8
Proof. The proof of this lemma closely resembles that of Theorem 6 in (Bot et al. 2019).
We denote θ Ø' - 1 C where @' is defined in Assumption 1.4
Initially, for all & > 1, we have:
cr
[(x², zi : (', + Cnpp + ak' bB
f(xt, 3 31,
18 hn( n²) 1- 14 (xt) + E [i(x)) + (Ax b, 2) + 2 1I - -b12
C2OC3 + {E/ (x+)))) } + (E f(()) (Ax b, 2) + g ||x bll2
(Ax' b. z²) + + - cC
(44)
θ
27

---

Published as a conference paper at ICLR 2025
where step ① uses the definition of θ¹; step 2 uses Chpp' + a& + 6B* z 0: step 3 uses the
definition of (xx', z²; "; n²)) in Equation 44 step @ uses 0 < h, (u)
h (u: S pC2 as shown
in Lemma 3.3 and the fact that 1 S μº: step @ uses Assumption 1.4
We now conclude the proof of this lemma through contradiction. Suppose that there exists to such that @ < ④. We derive the following inequalities:
Σt - + =
Σ t=
-4p (0r - θ) + 1Ei=, (0' - -9]]
in ws
Σ 1=1 (0l -e] + (T + tu) maxi (0' 2
E (0 -)]
to) (0% -),
(45)
where step 1 uses O' < @ for all f 2 lg- We closely examine Inequality (45) As ln is finite,
the sum _ > (o' - θ) is upper bounded. Considering the negativity of the term (0 +) we
deduce from Inequality (45
1om (0'
9) -00
(46)
Meanwhile, for all t 2 1, the following inequalities hold:
IV8
θ -
zz-1 z²)
1
(p-
||
3 ||z ||2 3 1|z 11/1
2o
Ive
1 20
|2
-i- |||l'|113
112 0},
(47)
where step uses Inequality
44 and 2 z'+1 z¹ (Ax b): step uses the Pythagoras
relation in Lemma A.I step
uses उ 3
Telescoping Inequality (47) over / from 1 to T, we have:
(0' - ()' 2
| | 1
1
2
2 12
(48)
The finiteness of the right-hand-side in 48
contradicts with (46)
Therefore, we conclude that O+ 2 for all 1.
D.9 PROOF OF LEMMA 4.9
Proof. We define U á 3C%
b
We define U A C म7 (4 - 1)2, where 8 - 31 + ((P), n¹ x 3r.
Part (a). Letting T' E o0), we obtain:
Σ t=1 / 1)2
11
ΣT 1= h-T 1)2 =
A+
- 1)2 + ΣT 3
(
- 1)2
118
(1 + {1P 1)2 + Σ ΣT-1
gr+l
3 1)2
18
1+ >e
18(1+1-660
(1+50))
1+ Eee
(11))-0 y2
1'
$ <
1+2,
(49)
where step D uses 1 x + step @ uses B¹ = 80 (1 + { step 3 uses the definition of 3 =
3o + EEP step uses [I. I र i step K uses Lemma A.5
We further obtain:
M U
C. b 1 a 1)2) <
3C2 b 2 U.
h
28

---

Published as a conference paper at ICLR 2025
where step T uses 3r 2 3 step 2 uses Inequality (49
Part (b). For both conditions III and SU, we have from Lemmas
4.5 and
g++ I O' - +
Telescoping this inequality over t from 1 to T, we have:
I
gh
v o
G D U 0
(50)
where step ① uses Lemma 4.8 that O O for all I, and Lemma 4.9
D.10 PROOF LEMMA
Proof. Given 2), we define 03 A
1-11-0| E [1,)0))
We define wh-1
1+++1 A Vh, (x (+1 /1) (x
We define u = A Q' x where Q' 02L - 3r A
We define Z
3 A ( 113 + 20 20 xz We define ž a E/es-
First, we have:
max 1=1 (1|
max ( (x,,, , V (xx)(x))) (x)
20% + 207
(51)
where step C uses
la + bl12 K 2/|a|
+ bl2. and Assumption 1.2
Second, have:
max 11 1
++
max 1
Q (x,
x111
Me IA8 Ie
max
x
q2t
(
||
113
92>
(52)
where step ① uses ||0'|| < 8 Ag for all as shown in Lemma 4.3 b); step @ uses 3 L ( Tap step @ uses
Σ E2 [| x 11
Eの gt+1 E.
Part (a). Using Lemma 4.2 b), we have:
A I +1 (1- AJZ' - o ++1 + 1t
For all 8.2 1, have:
AA 2 ++
5 11 a A + + + 1+1 + ||u ||}.
Applying Lemma
A.7 with e¹
- || and pt
|| || + || [|, for all t 2 1, we obtain:
A z'
1 I^3 IA
(1AAZ) || + Ty max
|| + || 11
3 [5] 2 || + og max | 112 + oy maxi=l || 112)
38.3 (T 2 1 + 03 max # || 1| + dg max I z (
3. ( 2
o3 max / 1 0g max 1|
38. 3. 1
113
+ 20.C2 20, 203 + +
22A
29

---

Published as a conference paper at ICLR 2025
where step 1 use (a + + c)² < 3(a² b² c²) Assmmtiin 1.3 that ||,,1 - X; step @ uses
3 I 3 for all i I t; @ uses Inequalities (51) and 52 This further leads to
2 12 -
2 AZB"
Part (b). We have:
$ Eh
z 1
-i=
S <E/E3 - Ž.
c3
where step ! uses the definition of gh+1 A |s Σ
LiIl [
x
+ +
x +
12 21 in Lemma 4.1 step @ uses Lemma
b.).b).
D.11 PROOF OF LEMMA
Proof. We let a E 20,
First, we derive the following inequalities:
(Ax++1 b, b,
0gg (z ++
z zz 2
+1 11
#1 1
+
|
z
20 3r
20 |22'122
(53)
where step uses the Pythagoras relation Fact A.1
In view of Lemmas 4.5 and 4.7 given g++1 2 0 for all i 2 1, we have:
0 2 O' 0++ + U
Telescoping this inequality over i from 1 to t, we have:
0 - + + U < - 0 + U,
where step @ uses Lemma b.). For all t 2 1, we derive the following results:
2¹ U
11 IV
0/ + a bB++1
1
f(x't1, 2/gHt,2/111100 /
gi+1 +1) + C ++ + aA
1+1 + UB'+1
1
Σn= f( + (Ax ++ b, z +2 + gr+1
2 | 11 - -b12
+E h
+1 +2) + 1/2 1/ 1+1 + aa2+11 + 6B4
I IV IV
Ef h, (x
(Ax++1
b, +1 - -//htt
Σ [f( (1 hx
Iz" 1| 2/2²* ++ C
2
Σ. [M(x +1 + h, ( 2 | | - 1 Cr.
where step ① uses the definition of e0+1, step @ uses uses the definition of 0 in Lemma 4.1 g++: 2 | - bl2 2 0.
step @ uses the definition of L(x ; 11)1) in step @ uses
Ch,p++1 + aAt+1 1+ b 0, and the fact that hn (x+++ 11 hn (xx++1) 2 C2: step 3
uses Inequality 53 step c uses n² & nr0 for all
We further obtain:
EL + h. (x
< U
205 1Z J
T
+00,
where step @ uses the boundedness of _ 1 for all 1 2 0, as shown in Lemma 4.10 According
to Assumption 1.4 we have ||x < +oo for all i E [n]].
30

---

Published as a conference paper at ICLR 2025
D.12 PROOF OF THEOREM 4.12
Proof. We define K _ &
where K' A min(min(s1 22)A2,,.)) and A f min || ||
K7.
We define gH+1 _ (ei E Lillx - x(Il + +22 - x 11/tt11 - 2/
Part (a), We have:
E gh
8 IV8 11
Eizle
+2
xx, g1 z1113)
EL fl - 1-
-x)
+ 3 (1 x111 + +E||z=+ - =1
11 2 1V
# E [|5 1= 2
1|
x + 11 (x ++ + - - -21133
# K' K'
1=1 | (x
-x)1 + || x21133
2/. K' T 1=1 (x
x²) 112
||z ++1 2'1
where step ! uses Lemma 4.9 (b); step @ uses the definition of gt+1, step @ uses 8r 2 g for all S T; step uses g
L.+ | 2 ||A,1| 2 A?; step uses the definition of
K" & min (min c3): step @ uses Eis | x ||x x² Therefore, obtain:
- - 2t < K
3 3 KB"
Part (b). By dividing both sides of the above inequality by T, we obtain:
K&T
T - (1= x² 11 + ||x - x 11))
min
- - ||
- zz 111)
We conclude that there exists an index ē with f S such that ||z -1113 + 11,3(xx² r- - S
Kg
D.13 PROOF OF THROREM 4.15
To prove this theorem, we first provide the following lemma.
Lemma D.I. We define q' A {x] x5, .., x J. We have:
(a) ||q (1 bll S ei || ++ - 2z 02 (39)-
(b) dist(0, Ohn (x--1) ) V fm (x (x(++))+++)) A
S C3 - +|
(c) Σ dist(0, Oh, (x)
1+1
+ Vx, (x
A. T 2 I co|lz'+ z'll + c> - x') )l-
Here, Ci 730 02
A
C3 (1 - A, C4 = qx Att..o c6
LuCa, co (1- )--))((n 1), and 52
5x
C7
Tyn-T + 01(
1
g0
I
A
+ A (n 1). Furthermore, A max; || and I & max Li-
|| and L. e max" Li. We define u +1 = (x !+ x() 3 AT ( - -x3)) with i In 1].
Proof. We define A  max;
We define n1t11 Q'(xt-1 - x with Q' e 1ZL B¹ A.A...
31

---

Published as a conference paper at ICLR 2025
Part (a). We have:
|| Aqqt1
++1 bll
| A A +x x An b
Ei= A, 1+1 bl + || (x (+1
x
||Ax bl| + Ap! Ci.
W l1e
11 (z"+1 -z')ll || + A Cn
688i1
||z zz1l A (B+)
where step uses |A,l < A and Lemma c) step @ uses z++1 z' + ('x((xxx+1 -b), and /² 3āge step @ uses 3 < B".
Part (b). We first have the following inequalities:
(x - (
| (x,, - V. + + -
I IA IA
| [ (x(,, fx ||| + VV. - (x
Ln||x [+x xx,11 + Ln | x 11
L. |n - x Lnjd' Cn
Ln 4+1 - x/11 |l + In (6x)
Ch
(54)
gF..
Ecs
where step ① uses the fact that fn fx(2)) is La smooth; step @ uses Lemma 3.6c)) that: |
x S μ Cn; step @ uses μ² 5xgi.
We further obtain:
dist(0, 0h, (x++1) + V + )
118
[1024,,c'
1+1
+ 1T2--11
[ B2L
1 nt
+ (x + AT
1
[[ - -''A x )
V).((()) (1-)))) AA - -z')
11Q(xh: - x(++)++ + ATT
| v/x(x(I
(1 [A|z++1=z1] + |[0(x - ||| + VV V
)) ++ - -z'll + (ap + I.m 30
18
x ||| + 3+.
(55)
A
where step ① uses the optimality condition as shown in Lemma 3.6(b) b) that:
p(c'
++1 E Oh, (x+1), with p OzL
step @ uses c¹ = x², / p as shown in Algorithm step @ uses the fact that:
af Sx AJ ( 2²) 3' A, (x x(+1),
step 4 uses the definition of Q 82L1T - AAA.A n. in Lemma 4.2 step @ uses |AA|| S A;
step K uses || Q'1l B Xg as shown in Lemma 4.3 Inequality (4 and the fact that 80 < 3
32

---

Published as a conference paper at ICLR 2025
Part (c), We first have the following inequalities:
E
1 1|
+1 xt) - 3 A D -X0+*
XDIHI
VA
Li(x -x)]1 8
AT (x x5)11
IA I
0, I Lí) Ei= ||* X || + 3 A (n - ||| - xx11
(max 1 49 /n n 1|x x | + A (n- 1)11 x+ x1I|
( A²) 11 (x x1|| + A 2 (n 11) x'Il
= 10: + A ) + A² (n - 1)) -1 11 - xx)Il
(56)
where step ① uses the definition of u for all i E [n - 1]; step @ uses A - max; || 11: step @
uses 25 ||x -x] S -I - x²|| step @ uses L = L, + | I 3
+ A S
30
B'I Jot + A for all i.
We have the following results:
Σ
11l
I1(1 - A (2 - z') - Vx((x) m + (
V^
[1(1 A (z'+1 - z')]l + Σ [ Vxi(x )|| E |utt'|
i8
) 1) | 22 113 + I. vn 11 11 - x(+1)|| Σ 1a |
Ecs
o/ callz ++1
21113 +
[vv-I g0
+ c) (1- )12
A
where step ① uses Part (a) in Lemma 4.2 that:
E [n - 1}, (hx(x 3 - (+1 AT - A - xz') - Vs(({);
step @ uses | S A, f((;,) is Ly-smooth, L, S I, and 8o S Br: step & uses Inequality (56)
Now, we proceed to prove the theorem.
Proof. We define Crit(x, 2) e ||xx bll + En d0, V((()) + ax, + ATz).
We define q' e {x{ x².
First, we deduce from Theorem
4.12 a) that
K3T
Σt || |
T
2² 12 + 11
IV
2T 1=1 ||z -z'll || - 1)
1
T
where step @ uses the inequality ||a| 2 _ (2 for all E R2T _ leads to:
Σ (1la(11 2'1 1| x0)| KBT 2T ((T(++)//2)
(57)
Second, using lemma D.I for all 1 0, we have:
Crit(q +1 +1)
(a + 03 + cz) ||z +1 - z'1l + (c1 + c7) (x - x'Il + (cz + (3) (58)
Ad
Ad
A
33

---

Published as a conference paper at ICLR 2025
We further derive:
+ + Crit(q"*),z"* (z
I IA IV
$ maxx(d) d2) Ei= f - z''l + -
x')l3 + 4 Σ E
O(T(0-1)/2) + 4 Σ (99)-1
O(T
Here, step O uses Inequality 58, step uses Inequality 57 : step uses S Ott),, and the fact
that T0-2
1-p p E (0, 1) (refer to Lemma A.6
In partieular, with the choice p 1/3, we have: + E% Crit(q 1(t(("+t12"/)) =) - O(T-1/3).
D.14 PROOF OF LEMMA 4.17
Proof. We let z'
z' for all t.
V3
Initially, we derive:
Ei= (1
V
8 341
2
116
Eis (1
[(++1) )
I+
Ee [++TTP
(141)//2_p//2
= E (1+1)²
(B-1002--122
Ie M IA
E
D
(l0-2)
1/2,
(59)
where step 1 uses ,3 = (1 + {(P) for all 2 0; step @ uses
I+5(++1FF S :(++5アア' step uses
1+81"
Lemma A.4 that (t + 1)p/2 tp/2 < 2 ft(p/2-1) 1) for all t 2 and E (0, 1); step + uses p S 1 and
#I S 7: step b uses Σt=1 1 2.
Part (a). We have: ||2-|/ = /
1/
S Z < +00, where step uses Lemma |
B
Part (b). We derive the following inequalities:
Σ 00 t== z
Σ 00
2
11
[=1
B1+1
Vgi
Σ
z¹(
)13
18
2 > 12'li_g
1 + 22
00
||z
VBc
V3s
V
IV
8
E ge
| -z'113 + 2 Σ 1=
1
11(1
8"
z
Be
ge+1
27 +2 Ei
V
g 3ाा
)
2ž 1
2( + 7),
34

---

Published as a conference paper at ICLR 2025
where step C uses the definition
- 2² for all step @ uses l| bl12 $ 2//a|12 + 2 step
uses शिन # step @ uses zzz z' 2 and | Z, as shown in Lemma
4.10
step 3 uses Inequality (59)
E ADDITIONAL EXPERIMENT DETAILS AND RESULTS
We offer further experimental details Sections E.1 and and include additional results in
Section E.
E.1 DATASETS
We incorporate four datasets in our experiments, including both randomly generated data and pub- licly available real-world data. These datasets as data matrices D Rixd The dataset names are follows: 'TDT2-m--'' 'sector-ri-d"' 'mnist-ri-d", and 'randn-ri-dd. Here, randn(m, n)) refers to a function that generates standard Gaussian random matrix with dimensions m The matrix D Ri constructed by randomly selecting in examples and d dimensions from the original real-world dataset (http: www. cad. zju edu. cn www.://wwwccc//////e/////aeee//e denpocaamme/ng///////// Data/TextDataa html https: /www. csie ntu. edu, tw tttpt///i///lls/aaa/eeaee normalize each column of D to have a unit norm and center the data by subtracting the mean.
We
E.2 PROJECTION ON ORTHOGONALITY CONSTRAINTS
When (x) = LM (mat(x)) with & (V/VTV = 1}, computing the proximal operator reduces to the following optimization problem:
arg ming 5
#||x - -x11 s.t. mat(x) M a (V VVV
This is the nearest orthogonality matrix problem, and the optimal solution can be computed as vec(ÜVV), where mat(x') (s) is the singular value decomposition of the matrix mal (x'). Please refer to (Lai & Osher 2014).
E.3 ADDITIONAL EXPERIMENT RESULTS
We present the convergence curves of the compared methods for solving sparse PCA with varying [1, 10, 100, 1000) and .o = {10p, 50p, 100p, 500p). shown in Figures 2 to 17 Please refer to Table 2 for the mapping between (ø, (8) and the corresponding convergence curves. The results demonstrate that the proposed
consistently outperforms the other methods in terms of speed for solving the sparse PCA problem, particularly for the ranges ò = {1, 10, 100, 1000} and gg (50p, 1000}.
Table The mapping between (Ø, ) and the corresponding convergence curves for sparse PCA.
8a 10p
8
50p
f
100p
g0
500p
Figure
Figure
Figure
10
Figure 14
I = 10
Figure
Figure
Figure
11
Figure
15
I 100
Figure
Figure 8
Figure
12
Figure
16
1000
Figure
Figure
Figure
13
Figure
17
35

---

Published as a conference paper at ICLR 2025
ORiustion
10
SahiGrrdd
Oliiatioe
SonGod
SahGrad
Olicotions
SunGrad
16
Time (soconds)
Time (soconds)
Time (soconds)
Time (seconds)
randn-1500-500
(b) randn.2500-500
mnist-15000 1500-780
momist-5500-700
SPGM
Olopstive
Olooodiee
Time (seconds)
Time (seconds)
Time (seconds)
Time (secords)
(e) TDT2-1500- 1500-500
(I)
TDT2-3000-50X
sector 1500-500
(h) sector 2500-500
Figure 2: Convergence curves of methods for sparse PCA with 1 and 300 = 10p.
AUMM
PEYIPES ALMM
ALMM SPOM SahGrrd
SPOM
Oliestie
SahhCrrd
Oliestiie:
Olgastin
SunGrdd
10
TO
Time (seconds)
Time (seconds)
Time (seconds)
Time (seconds)
(amdd-1500-500
(b)
randn 2500-500
1500-780
mmist 25000-780 750
RAUOMM
Oljestive
5
Olgjetiiee
SunCrrad
Clojesive
5
Olgeelive
SubGrra
Time (eeconds)
Time (seconds)
Time (seconda)
Time (saconds)
(e) 1DT2-1500-500
(I) 3002-3000-50
sector- 1500-500
(h) soctor-2500-500
Figure 3: Convergence curves of methods for sparse PCA with ò = 10 and 8 = 10pp
36

---

Published as a conference paper at ICLR 2025
CR-IPDS
SPOM SunGrad
SahhGrad
Oliestio:
Oliention
SahGrad
10
Time (soconds)
Time (soconds)
Time (soconds)
Time (seconds)
150d--1500-500
(b) randn-2500.500
m 1500-780
somist-5000-70
RADNM
Oloostive
Olgestie
10
Time (eeconds)
Time (seconds)
Time (seconds)
Time (seconds)
(e) IDT2-1500-500
(I)
TDT2-3000-50X
sector- 1500-500
(h) sector 2500-500
Figure 4: Convergence curves of methods for sparse PCA with ò p= 100 and 50 = 10pp
AUMM
ALMM
ALMMI SPOM SahGrrd
THMIPLS
SPOM
Oliacioe
SahhGrrd
Oliestire:
Olaasioc
Oliastie
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (seconds)
1undn-1500-500
(b)
randn 2500-500
1500-780
mmist 25000-780
RAUOMM
RADDDM
IRADMM
Oliestive
Okgietlie
SunGraa
Clojstive
Olgrolive
10
10
Time (eeconds)
Time (seconds)
Time (seconda))
Time (saconds)
(e) TDT2-1500-500
(I) TDT2-3000-500
scctor- 1500-500
(h) soctor-2500-500
Figure 5: Convergence curves of methods for sparse PCA with ý = 1000 and 5 = =10p.
37

---

Published as a conference paper at ICLR 2025
IRHIPDS
SPOM SahGrad
ORpustion
SaniGrrd
SanGrdd
Oliistion
SinGrdd
10
16
Time (soconds)
Time (soconds)
Thme (soconds)
Time (ceconds)
randn-1500-500
(b) mandn.2500.500
mnist-1500 1500-780
mmmist22500-780
- ARMMM
Va-IPIX-- ATMMN
Olipstive
Olojodiee
Ohoeotive
10
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (secords)
(e) IDT2-1500-500
(I) IDT22-3000550
sector 1500-500
(h) sector 2500-500
Figure 6: Convergence curves of methods for sparse PCA with 1 and 300 = 50p.
IPLS AUMMI
TRYIPES ALMM
SPOM
SPOM SahGrdd
Oliesiie
10
SahhCrrd
Olizostie:
10
Oltastiee
SunGrd
T0
Time (seconds)
Time (seconds)
Time (seconds)
Time (seconds)
(a) randn- randn-1500 1500-5000
(b) randn 2500
1500-780
mmist 25000-780
ALDMMN
-
RAUMMM
RALDDM
Olijstive
Okgjesliee
SunGraa
Clojetive
Ohgeelive
SubGrra
Time (eeconds)
Time (seconds)
Time (seconda)
Time (saconds)
(e) 15T2-1500-500
(I) TDT2-3000-500
sector- 1500-500
(h) 100000-5500-500
Figure 7: Convergence curves of methods for sparse PCA with ò = 10 and 8 = 50pp
38

---

Published as a conference paper at ICLR 2025
-R-IPDS SPOM
ORieetion
SahiGrra
Oliention
SanGidd
Clicetion
SahGraad
ORiestios
SunGrd
20
1O
Time (soconds)
Time (soconds)
Thme (soconds)
Time (seconds)
m0nd--1500-500
(b) mandn:25005500
mnist-1500 1500-780
mmist-2500-775
- ATMMM
ATMMI
Oloostive
Oltgodiie
Oloedtive
20
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (secords)
IDT2-1500-500
(I) IDT22-3000-00
sector 1500-500
(h) sector 2500-500
Figure 8: Convergence curves of methods for sparse PCA with ò p= 100 and 300 = 50p.
AUMM
ALMM
ALMMI SPOM SahGrad
TAMIPES
SPOM
Oliactie
SahhGrrd
Olizntiee:
Olaecios
Oliastiee
SunGrda
10
TO
TO
Time (seconds)
Time (seconds)
Time (seconds)
Time (seconds)
randn-1500.55 1500-500
(b)
randn 2500-5000000
1500-780
mmist 25000-780
ALDMM
ALMMM
RAUOMM
RALDDM
IRADMM
Olojstive
SunGrad
Clopstive
Charelive
10
TO
10
TO
Time (eeconds)
Time (seconds)
Time (seconda)
TIME (saconds)
(e) TDT2-1500-500
(I) TDT2-3000-500
sector- 1500-500
(h) 50c101-2500-500
Figure 9: Convergence curves of methods for sparse PCA with ý = 1000 and 5 = =50p.
39

---

Published as a conference paper at ICLR 2025
-R-IPDS SPOM
SanGGrad
Olicetion:
SanGrod
SahGrrd
Oliextions
SunGrad
10
10
10
Time (soconds)
Time (soconds)
Thme (soconds)
Time (seconds)
15000-1000-50
(b) mandn-25005500
m 1500-780
mmiis-25500-800
-a-IPIX-- ATMMN
RADNM
RADMM
SPGM
Olojotive
Olgestiie
Olgesticc
Oloeodive
SunGrdl
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (secords)
UDT2-1500-835 1500-500
(I) IDT22-0000-50
sector-
1500-500
(h) sector 2500-500
Figure 10: Convergence curves of methods for sparse PCA with ò = 1 and 30 = 100p.
AUMMI
TRYIPES ALMM
ALMMI SPOM
TAMIPES
SPOM
Oliastie
SahhGrrd
Oliestiies
SahGrrd
SuNGrd
10
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (seconds)
(a) ramddn115000 1500-500
(b)
randn 2500
1500-780
mmist 25000-780 750
AUDMM
-a AUMMM
RAUOMM
RALDMM
IRADDM
Oloystive
Okgjetlie
SunGrnd
Olgjetive
SunGraa
Time (secords)
Time (seconds)
Time (seconda))
Time (saconds)
(e) 1DT2-1500-500
(I) TDT2-3000-500
soctor- 1500-500
(h) 50ct01-2500-500
Figure 11: Convergence curves of methods for sparse PCA with ò = 10 and 8 = 100p.
40

---

Published as a conference paper at ICLR 2025
IR-IPDS
-R-IPDS SPOM SahGrrd
SahiGrrd
SunGrad
10
Time (soconds)
Time (soconds)
Thme (soconds)
Time (seconds)
randn-1500-500
(b) mandn-2500-500
mnist-1500 1500-780
mmist-2500-775
- ATMMM
VaMIPIN- ATMMN
RADAM
RADAM
RADDM
Oloestive
Olgostive
Ologodive
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (secords)
IDT2-1500-500
(I)
TDT2-3000-550
sector 1500-500
(h) sector 2500-500
Figure 12: Convergence curves of methods for sparse PCA with ò - 100 and 300 = 100p
AUMM SPOM
SPOM SahGrad
Olgacioe
Sahhrrad
Olientiee:
SunGrd
10
TO
TO
Time (seconds)
Time (seconds)
Time (seconds)
Time (seconds)
randn- 1aaddn-150050000
(b)
randn 2500
1500-780
mmist 25000-70
AAMMM
- AUMMM
RAUOMM
RALDDM
RAUDMM
IRADMM
Olojstive
Ohgjetlke
SunGraa
Clupstive
Olgyetive
Time (eeconds)
Time (soconds)
Time (seconda))
Time (saconds)
(e) 1DT2-1500-500
(I) TDT2-3000-500
sector-
1500-500
(h) 50ct01-2500-55
Figure 13: Convergence curves of methods for sparse PCA with ý = 1000 and 5 = 100p.
41

---

Published as a conference paper at ICLR 2025
SPOM SahGrdd
SanGrnd
Oliientoos
SonGod
SpnGrdd
10
10
10"
Time (soconds)
Time (soconds)
Time (soconds)
Time (seconds)
randn-1500-500
(b) mandn-2500-500
mnist-15000 1500-780
Somist-5500-70
-I-IPIN-- ATMMN
RADAM
Olopetine
Olgestiee
Choostive
Time (seconds)
Time (seconds)
Time (seconds)
Time (secords)
(e) 1DT2-1500--4 1500-500
(I)
TDT2-3000-50X
sector 1500-500
(h) sector 2500--250000000
Figure 14: Convergence curves of methods for sparse PCA with ò = 1 and 300 = 500p.
TRIIPES ALMM
ALMMI SPOM SahGrad
SPOM SahGrrrd
Oliastie
Oliesties:
Oliastiee
SuNGrd
10
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (seconds)
randn-1500.
(b) rundn 25000500 5000
1500-780
(d)
mmist 25000-70
RADDDM
RAUDMM
RRADMM
Oljestive
Ohgjetine
SunGraa
Cljjstive
Olgeelive
SubGraa
Time (eeconds)
Time (seconds)
Time (seconda)
Time (saconds)
(e) TDT2-1500-500
(I) TDT2-3000-500
sector- 1500-500
(h) sector-2500-500
Figure 15: Convergence curves of methods for sparse PCA with ò = 10 and 8 = 500p.
42

---

Published as a conference paper at ICLR 2025
ALMMI
16"
-.-SPOM
SahGGrad
Oliiettoos
SonGod
ORieetion
10"
SahGrrad
Olcistiv:
SunGrad
10"
10
10
10
Time (soconds)
Time (soconds)
Time (Soconds)
Time (scconds)
150d--1500-500
(b) randn:2500.500
1500-780
mmist-2500-780
10"
TIMIPINS- ATMMI
RADAM
10
Oloestive
Olgestive
Olojodive
10
10
10
Time (seconds)
Time (seconda)
Time (seconds)
Time (seconda)
(e) IDT2-15000550
(I)
1DT22-0000-50X
sector 1500-500
(h) sector 2500-500
Figure 16: Convergence curves of methods for sparse PCA with ò - 100 and 30 = 500
SPOM
16
SahCirrd
Oliestiee:
SonGrd
Olgastie
SahGrad
Olasstic
SunGra
10
10
10
Time (seconds)
Time (seconds)
Time (seconds)
Time (peconds)
ramdn-15500 1500-50000
(b)
randn 2500-50000000
1500-780
mmist 25000-780
10
RAUOMM
RALDDM
RALDMM
16
Oljeetive
Okgjotlke
SunGraa
Olgeetike
10
10
Time (eeconda
Time (slconda)
Time (seconda)
Time (eeoonda)
(e) 1DT2-1500-500
(1) TDT223000-500
sector- 1500-500
(h) 500501-2500-500
Figure 17: Convergence curves of methods for sparse PCA with ý = 1000 and 5 =500p.
43


Reviews:
[{"review_id": "t4YmnnLA5v", "reviewer": "Reviewer_KMzj", "summary": "This paper investigates the ADMM for multi-block composite optimization problems. An adaptive penalization technique is employed to enhance convergence. The global convergence result of the proposed proximal linearized ADMM is derived under mild smoothness conditions.", "questions": "1. Could you provide more insight into the increasing $\\beta$ update rule in (2)? I notice in line 1809 that there is a trade-off between two terms to derive the best complexity results. However, can it be shown that such type of $\\beta$ update rule is optimal? A discussion or analysis regarding the optimality of this approach would be valuable.\n\n2. In the numerical experiments section, the function used in the sparse PCA example does not appear to satisfy the smoothness assumption. It would be beneficial to conduct further analysis that incorporates the properties of the orthogonal constraints, leading to an equivalent formulation that fully aligns with the assumptions and supports the theoretical analysis.\n\n3. Given that the algorithm involves several parameters, is it straightforward to determine their values in practice? It would be helpful if additional experiments were conducted to demonstrate the robustness of the algorithm with respect to parameter selection and to provide guidance on how to choose these parameters effectively.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This theoretical paper provides complete theoretical results to prove the proposed algorithms achieve competitive complexity under mild smoothness conditions. The analysis covers a broad range of problems, including those with linear constraints and problems that involve explicit proximal operators (e.g., manifold optimization). This approach encompasses a wide variety of problem categories.", "weaknesses": "The paper is written in a way that compiles all the technical material with complex notations, making it difficult for readers to follow. It would be beneficial if the author could summarize the results more effectively and provide insights and discussions. \n\nIn the numerical section on sparse PCA, it is unclear why the parameters $\\dot{\\rho} = 10$ and $\\beta^0 = 50\\dot{\\rho}$ are used consistently. These values appear to be dependent on the Lipschitz constant as suggested in the theoretical section. Given that the problem scales differ in the experiments, it would be more consistent with the theoretical results to adjust the parameters accordingly.\n\nAdditionally, there are notational errors and typos that should be corrected. For example, in line 1565, the RHS should include coefficient 2. I have noticed several similar issues throughout the paper that should be rechecked.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PiHzQ6qe2b", "reviewer": "Reviewer_GkTh", "summary": "This paper introduces a novel proximal linearized ADMM algorithm with an Increasing Penalization and Decreasing Smoothing (IPDS) strategy, termed IPDS-ADMM. The proposed method tackles multi-block nonconvex composite optimization problems under a less stringent assumptions, requiring continuity in only one block of the objective function. Additionally, this work provides the first complexity result for nonconvex, nonsmooth minimax problems.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The algorithm guarantees convergence for ADMM under less stringent conditions.\n\n* It establishes the first convergence results for solving nonconvex, nonsmooth minimax problems.\n\n* The IPDS strategy ensures convergence for matrices $A$ that are either bijective or surjective.", "weaknesses": "* It remains unclear whether the IPDS strategy can be extended to handle inequality or more general constraints.\n\n* In Section 4, given the compact results and dense notation, it would be helpful to emphasize the role of the IPDS strategy in the analysis, with additional explanatory comments to enhance clarity.\n\n* A suggestion is to use alternative notation in Lemma 4.8 for $\\epsilon_1,\\epsilon_2,\\epsilon_3$, as these are typically reserved for sufficiently small constants.\n\n* While the sparse PCA experiments provide valuable insights, demonstrating the method’s effectiveness across a broader range of applications could further support its effictiveness in diverse problem settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BmNHIE3Wmo", "reviewer": "Reviewer_ARrq", "summary": "This paper proposes a variety ADMM algorithm called IPDS-ADMM for multi-block nonconvex composite optimization problems, introducing an Increasing Penalization and Decreasing Smoothing strategy using Moreau envelope technique to further decrease the smoothness conditions on the objective function of previous works. The authors also conducted some experiments on sparse PCA problem to show the effectiveness of the proposed method.", "questions": "1.  The iteration complexity of the proposed algorithm seems to be not outstanding compared to previous nonconvex ADMM approaches mentioned in Table 1. Also, in section 3, the authors claim that IPDS-ADMM improve the complexity from O(ϵ^(-4)) to O(ϵ^(-3)) compared with RADMM, but it is unclear whether the comparison is fair due to RADMM focus on the manifold optimization problem and have the different assumptions with the proposed algorithm.\n\n2. Regarding the experiments, how did the author choose the hyper-parameters of the other compared algorithms and are those hyper-parameters optimized for each algorithm? Further details are needed to ensure the fairness of the comparison. Also, the authors conduct the experiment on some small-scale datasets. Is the proposed algorithm efficient in such tasks with large-scale datasets?\n\n3. A typo. ‘Mereau Envelope’ in Line 221 should be Moreau Envelope.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe proposed IPDS-ADMM weaken the smoothness assumption for nonconvex multi-block composite optimization that requiring continuity in only the last block of the objective function.\n\n2.\tThe convergence analysis of the proposed algorithm is given for the case that the associated matrix is either bijective or surjective.", "weaknesses": "1.  The iteration complexity of the proposed algorithm seems to be not outstanding compared to previous nonconvex ADMM approaches mentioned in Table 1. Also, in section 3, the authors claim that IPDS-ADMM improve the complexity from O(ϵ^(-4)) to O(ϵ^(-3)) compared with RADMM, but it is unclear whether the comparison is fair due to RADMM focus on the manifold optimization problem and have the different assumptions with the proposed algorithm.\n\n2. Regarding the experiments, how did the author choose the hyper-parameters of the other compared algorithms and are those hyper-parameters optimized for each algorithm? Further details are needed to ensure the fairness of the comparison. Also, the authors conduct the experiment on some small-scale datasets. Is the proposed algorithm efficient in such tasks with large-scale datasets?\n\n3. A typo. ‘Mereau Envelope’ in Line 221 should be Moreau Envelope.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)