Inexact Augmented Lagrangian Methods for Conic Optimization: Quadratic Growth and Linear Convergence
Authors: Feng-Yi Liao
Lijun Ding
Yang Zheng
Venue: NeurIPS 2024 poster (2024)
Keywords: convex optimization
augmented Lagrangian method
quadratic growth
error bound
linear convergence
Primary area: optimization

Abstract: Augmented Lagrangian Methods (ALMs) are widely employed in solving constrained optimizations, and some efficient solvers are developed based on this framework. Under the quadratic growth assumption, it is known that the dual iterates and the Karush–Kuhn–Tucker (KKT) residuals of ALMs applied to conic programs converge linearly. In contrast, the convergence rate of the primal iterates has remained elusive. In this paper, we resolve this challenge by establishing new $\textit{quadratic growth}$ and $\textit{error bound}$ properties for primal and dual conic programs under the standard strict complementarity condition. Our main results reveal that both primal and dual iterates of the ALMs converge linearly contingent solely upon the assumption of strict complementarity and a bounded solution set. This finding provides a positive answer to an open question regarding the asymptotically linear convergence of the primal iterates of ALMs applied to conic optimization.

Inexact Augmented Lagrangian Methods for Conic Programs: Quadratic Growth and Linear Convergence
Feng- Yi Liao'
Lijun Ding²
Yang Zheng!*
'Deparmment of Electrical and Computer Engineering, UC San Diego Department of Mathematics, UC San Diego
Abstract
Augmented Lagrangian Methods (ALMs) widely employed in solving strained optimizations, and some efficient solvers are developed based on this framework. Under the quadratic growth assumption, it is known that the dual iter- ates and the -urnssekuunnTuuker (KKT) residuals of ALMs applied to semidefi- nite programs (SDPs) converge linearly. In contrast, the convergence rate of the primal iterates has remained clusive. In this paper, we resolve this challenge by establishing new quadratic growth and error bound properties for primal and dual SDPs under the strict complementarity condition. Our main results reveal that both primal and dual iterates of the ALMs converge linearly contingent solely upon the assumption of strict complementarity and a bounded solution set. This finding provides positive answer to an open question regarding the asymptotically linear convergence of the primal iterates of ALMs applied to semidefinite optimization.
1 Introduction
We consider the standard primal and dual semidefinite programs (SDPs) the form
pz = min X
X)
d' = max
(b, y)
yER" ZE8"
subject to
A(X) =x)==b. =, X $
(P)
subject
(2 +
(D)
2 E ST
where the problem data consists of a cost matrix S", constant vector b R.. a linear map + R. A(X) [A,, .... (Am, X)) with A1. Am E S", and its adjoint operator 1mm Sd as (y) = Em Agy that satisfy (A(X). = (X), VX ES" E Rm
A
A
SDPs broad and powerful class of conic programs, which include linear programs and second- order cone programs as special cases. The class of SDPs has found an extensive list of applications, including control theory M. combinatorial optimization 2 polynomial optimization [ machine learning 44)) and beyond [7]. Meanwhile, many algorithms have been developed to solve (P) and (D) ranging from reliable interior point methods 88 10 to scalable first-order methods [1
In particular, it is demonstrated that Augmented Lagrangian methods (ALMs) [13] [6] are suitable for solving large-scale optimization problems. Some efficient ALM-based algorithms have been developed to solve (P) and (D). For example, the celebrated low-rank matrix factorization (17) was integrated with ALM for efficient algorithm design. A semi-smooth Newtown-CG algorithm was proposed for ALM to solve SDPs with many affine constraints in 18 An enhanced version was introduced in [19 tackle degenerate SDPs by combining warm starting strategy. The algorithms
18 [9] have been implemented into solver, SDPNAL+, which has shown very impressive numerical performance in benchmark problems. Other recent ALM-based algorithms include 20
"Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Despite the impressive practical performance, theoretical convergence guarantees of applying ALMs
to (P) and (D) are less complete. Thanks to the seminal work [23], it is well-known that running
ALMs for the primal (P) is equivalent to executing the proximal point method (PPM) for the dual D
Thus, the classical convergences of ALM are typically inherited from PPM, which only guarantees that the dual iterates converge linearly when Lipschitz continuity property is satisfied [24]. The
Lipchitz condition requires (P) to have a unique solution. The uniqueness assumption was relaxed in [25]. which allows multiple optimal solutions but requires an error bound property. Recently, this error bound property was established in [26) in a general conic optimization setup. The work 26 also proves linear convergence of KKT residuals when applying ALM to convex composite conic programmingg However, due to the connections between ALM and PPM, all these results only guarantee linear convergence for the dual iterates, while the convergence rate of the primal iterates in ALM remains unclear. Indeed, it is noted in 21 26 that the problem of whether the primal sequence generated by the ALM can also converge asymptotically linearly is open.
This asymmetry in convergence guarantees notably dissatisfying, especially considering the elegant duality in (P) and (D). In this paper, our main goal is to establish linear convergence guarantees for both primal and dual iterates when applying an inexact ALM to SDPs (either (P) or (D), under the usual assumption of strong duality and strict complementarity.
Our contributions. To resolve the challenge, we have made novel contributions from two aspects. On the problem structure side:
Under the standard strict complementariy assumption, we establish the quadratic growth and error bound for both primal and dual SDPs (P) and (D) over any compact set containing an optimal solution (see Theorems T [and]] 2 Our results not only extend the findings of [27] from small (yet unknown) neighborhood to any compact set, benefiting the analysis of iterative algorithms, but also improves the recent results in [28/30]; see Remark [ for a comparison. (b) To establish the quadratic growth, we unveil a new characterization of the preimage of the subdifferential of the exact penalty functions for SDPs. This reveals a useful connection between exact penalty functions and indicator functions (see (1] in Lemma
(a)
We believe that this new
characterization is of independent interest.
(c) Using the new characterization, we further provide a new and simple proof for the growth properties in the exact penalty functions of ST. (see Appendix B). and clarify some subtle
differences in constructing exact penalty functions (see Section 3. and Remark B.
On the algorithm analysis side:
(a) By leveraging the established quadratic growth and error bound, we show that applying ALM to solve either the primal dual SDPs (P) and (D) has linear convergence for both the primal and dual iterates (see Theorem 33
(b) We establish symmetric versions of inexact ALMs for solving both the primal and dual conic programs (see Section and Appendix [E.3), which is less emphasized in the literature.
(c) We clarify the subtlety concerning the (in)reasibility of the dual iterates by inexact ALMs (see Section 4.2). which is an important issue concerning the relationship between PPM and ALM.
Related works: We here review some closely related results in the literature.
Quadratic growth and error bound. Many studies have been dedicated to establishing quadratic growth or error bound for conic optimizations under various assumptions 22 27 35) Starting from the famous Hoffman's 's lemma (36), a global error bound for linear systems has been established, partially infinite-dimensionall case (37) Sturm investigated the error bound for SDPs, in which the exponent term is bounded by 2d with d being the sigularity degree that at most n [32] Zhang provided simple proof of error bound for feasibility system under Slater's condition [33]. Zhou and So provided a unified proof to establish error bound for a class of structured convex optimization [35]. The results in (35] are generalized to convex problems with spectral functions BI. Drusvyatskiy and Lewis discussed quadratic growth for a convex problem
which was later extended
of the form ming (Ax) g(x) under dual strict complementarity [34] Section 4]. Very recently,
Ding and Udell established an error bound property for general conic programs via an elementary framework using strici complementarity (28). All the aforementioned results have slightly different assumptions, resulting in different forms of quadratic growth properties. They are not directly applicable to our purpose of establishing linear convergences of primal and dual iterates in ALM; a detailed comparison will be provided in Remark [ after introducing our main result.

---

Augmented Lagrangian method (ALM) and Proximal point method (PPM). The ALM is first introduced in [15] [6] to improve numerical performance of penalty methods. It is shown by Rockafellar that the augmented dual function is continuously differentiable [8,, and the ALM can be viewed as an augmented dual ascent method (24), thus the convergence of ALM can be analyzed via dual ascent. The seminal work [23] established a strong relation between ALM and PPM: the dual iterate by ALM is the same as the proximal update on the dual function by PPM. From the convergence of PPM, we know that the dual iterates of ALM converge linearly when the preimage of the subdifferential map of the dual function is Lipschitz continuous at the origin [24]. However, the Lipchitz condition requires the solution to be unique, which is not suitable for many practical applications. Luque made an important extension in PPM to allow multiple solutions while maintaining linear convergence (25 Recently, Cui et. al relaxed the Lipschitz assumption to upper- Lipschtiz continuous which allows multiple primal and dual solutions [66] In addition, the KKT residuals of convex composite conic programs are shown to converge linearly under the assumption that the dual function satisfies quadratic growth [26]. The primal iterates of ALM are also known to converge linearly under much stronger Lipschitz assumption on the augmented Lagrangian function 23 26). As pointed out in [26] Section 3], the Lipschitz property of the Lagrangian function is more conservative than the quadratic growth of the primal or dual function. To the best of our knowledge, when applying ALM to conic optimization (P) and (D), the problem of whether the primal iterates converge linearly under the normal quadratic growth condition remains open.
Paper outline. The rest of this paper is structured as follows. Section reeviews some preliminaries in SDPs and PPM. Section B establishes quadratic growth and error bound properties. Section 4 establishes the linear convergence of primal and dual iterates of ALMs under standard assumptions. Section 5 presents numerical experiments, and Section cooocludes the paper. While all results are presented for SDPs, analogous versions exist for other conic programs, such as LPs and SOCPs.
2 Preliminaries
2.1 Strong duality and strict complementarity
In this paper, we assume the linear mapping A to be surjective (or A" is injective, thus y and have a unique correspondence). This is equivalent to AI, Am being linear independent. We here introduce two important regularity conditions: strong duality and strict complementarity
Definition (Strong duality). We say (P) and (D satisfies strong duality if we have p" = d
Strong duality only requires the optimal values to be the same. The existence of optimal primal and dual variables (X+, y," -z*) is ensured by the primal and dual Slater's condition
(8] Theorem 3.1], there exist primal and dual feasible points X and y satisfying X E int and C (y) E int(
Let S2 C S" and 2tp S I TM S" denote the optimal solutions of (P) and D respectively,
22 = (X E S" (C, = A(X) = = S
(la)
Qp {(y, Z) E Rd
x THh (b, A" + C, CE)
(1b)
Under the primal and dual Slater's 's condition, the solution sets Ωp SDp are nonempty and compact (see e.g., (30 Section 2] 29 Prop. 2.1]). We further have (Z+ X+) = 0, VX* Esp, (v", 2*) Elp which is called complementary slackness.
Next, introduce another regularity condition: dual strict complementarity, which is the key to ensuring many nice properties in a range of conic problems 34
35
Definition 2 (Dual strict complementarity for SDPs). Given a pair of optimal solutions X* E
Qp. (y" Z E Qp. we say that (X*, y"" Z**) satisfies dual strict complementarity X* E relint (sp)) ) (- 2))), where ($ is the polar cone of S Nige (-Z") denotes the normal
cone of (Sa)
-z, and relint denotes relative interior. If P and D have one such pair, we say
that and (D) satisfy dual strict complementarity.
We note that the usual notion of strict complementarity for SDPs is equivalent to Definition 2 as pointed out in [28] Appendix B]. For completeness, we also review the standard notion of strict complementarity in Appendix 1 The notion of (dual) strict complementarity is not restrictive, and
holds generically for conic programs (39 40 Theorem 15]. Recently, it has been revealed that
many structured SDPs from practical applications also satisfy strict complementarit [41. One can also define primal strict complementarity, and the primal and dual strict complementarity are not equivalent in general, but they are equivalent for the so-called self-dual cones, such as S7.
3

---

2.2 Proximal point methods (PPMs)
It is now well-known that running ALMs for the primal (P) is equivalent to executing PPM for the dual D). and vice versa [23]. We here give a quick review of PPMs and their standard convergences. Let IR" + R be proper closed convex function, and consider the problem f min fxx.. Let = argmin, f(x), which we assume to be nonempty. We define the proximal operator as
1 2a lly - x=|??
prox f (2)
argmin f(v) yER"
(2)
where 0. Starting with initial point 20 E IR. the PPM generates sequence of points as 0, 2,....... where {c* h220 is a sequence of positive numbers
follows Ø1+1 = prox ox bounded away from zero. The proximal operator (2) is always well-defined thanks strong convexity.
(x),), (2)e)
In practice, the proximal operator (2) may not be easily evaluated, and thus an inexact version is often used 42 In particular, an inexact PPM generates sequence of points as
#b+1 s ,r (xx)) = 0, 2.......
(3)
Two classical types of inexactness, originating from the seminal work 42 are
| cr. (Ix) & ex: Ex= Ex: < oc,
(a)
|z6+1 pr (r+) S 5% bx|1= rxll,
Σx= 64 00,
(b)
where f22 and (dx Jk20 are two sequences of inexactness for (3) The classical work 42) has established asymptotic convergence of the iterates 2y from 33) when using criterion (a). Fast linear convergences have also been established under various regularity conditions, such as the inverse of the subdifferential (ff) -1 is locally Lipschitz 0 42 (or relaxed to be upper Lipschitz continuous at 0 12,)), and more generally O is metrically subregular (27 43 (or f satisfies quadratic growth Recall that I satisfies quadratic growth at x S if there exists a constant N4 > such that
f(x) f" H2/2 dist (z, S), Vx E U,
(QG)
where 4/ is neighhorhood containing the optimal solution x² Convergence results for (3) Lemma 1. Let S = aargmingeR> fz) and suppose S + Q. Let {I trkhk2 be sequence from
(a) If criterion (a) is used, then limg- It = Io ES, iee, 2i converges to an optimal solution.
(b) In addition to a. if bb is used and f satisfies QQG at E S, then there exists is > 0 such that dist(x=41.5 5) Oxdist((x,, S), Vk k, where 02 0. with O2. CC <1 1-
The first asymptotic convergence is taken from 42 Theorem 1], and different proofs for the second linear convergence under (QG) are available, and simple one can be found in (44 Theorem 5.3]. Criterion aal guarantees the iterate 24 will arrive within neighbor ' where (QG) holds after some
number k then criterion (b) ensures the linear convergence; see 44 Theorem 5.3] for details.
Note that Lemma 1 only guarantees the (linear) convergence of iterates Tk. which corresponds to the dual iterates in the ALM (23) (see Lemma 4 in Section 4. Thus, once a suitable condition like (GG) is established for (P) and (D). applying the ALM will enjoy linear convergence for dual iterates
21125 25 26). In this paper, we aim to establish linear convergences of both primal and dual iterates in
ALM, when applied to (P or (D). For this, we first establish quadratic growth Section
Quadratic Growth in SDPs
In this section, we identify favorable quadratic growth and error bound properties for both primal and dual SDPs in (P) and (D) under the usual assumptions of strong duality and strict complementarity (cf. Definitions I and (2). These favorable structural properties will allow to establish linear
convergences of both primal and dual iterates of inexact ALMs applied to either (P) or (D).
3.1 Growth and error bound properties
To analyze PPM or ALM, consider an equivalent reformulation of (P D in the following form

---

min f=(X):= + +X()
==== min JD(U, 2): (-b,)) + +(()) VERT,ZESS
X
(4)
(5)
subject to
A(X) = b,
subject to
(1 Z = C,
where (and h, respectively) is chosen as either an indicator function dsg or an exact penalty function,
defined a
g = p pmax (0, Amax (x))
with p > tr(Z*).
where (x") E &DD can be any optimal solution. In (5) the exact penalty function h is designed in the same way as (6) where the lower bound on p is replaced by p tr(X*) and X* is any optimal solution in 2p. The common feature in (4) and (5) is to move the difficult conic constraint X St and Z E S as nonsmooth term gXX and hTZ) in the cost function. It is clear that for both indicator and exact penalty functions, we have g(X) = O, VX E 84 and h(Z) = 0, VA E sn. For
clarity, we state the following technical result.
Lemma 2. Suppose strong duality holds for (P) and (D. Under the choice of an indicator function or an exact penalty function in (6. the set of optimal solutions for (4) is the same as Slp in Ia and the set of optimal solutions for (5) is the same as PD in (bb.
The equivalence with an indicator function is obvious, and the equivalence with an exact penalty Propositions 3.1 Their proof's rely on a general character- ization in exact penalty methods 5 Theorem 7.21J. In Appendix B we present simple, different,
function has appeared in [30] and (29
and self-contained proof without relying on prior results. Our proof uses a new characterization of the subdifferential of exact penalty functions (Proposition [B.1]. which might be of independent interest.
Our first main theoretical results are the following growth and error bound properties for primal and conic programs. The proofs will be outlined in Section 3.2
Theorem 1 (Growth properties in the primal). Suppose strong duality and dual strict complementarity hold for P and D) Consider the primal conic programs (P) and (4). Let (X*,8', -*) satisfy strict complementarity, and the exact penalty parameter is chosen as p tr( zr(ZZ). ). For any compact set CS containing an optimal solution X* E Slp, there exist positive constants K, 7, a > such that
Jr(X) - p² + (X) bll 2 K. (x, AX
(7a)
(C,X) D2 + +l)) bll + dist dists (X, s4) 2 K dist" VX
(7b)
If Up is further compact, then set U in (7 and 7b can be chosen as any sublevel set of fp, i.e.
{X E S" fx(X) S B, A(X) = b} with a finite 5.
In 7ap. the impact of the conic constraint X E St is reflected in the reformulated cost fX) When using the indicator function as fp(X) (C, X) + døz (X), the left-hand side of 7ab implicitly
requires X E : otherwise fr(()= = +o0 and thus the inequality 77 holds trivially. If using the exact penalty function (6). we have fx( (C, + 9(X) < +oo for X & S which is closer to (7b). Indeed, our proof of (7b) utilizes a characterization of the exact penalty function (6).
Both (7a and 7b give useful bounds when X moves away from the optimal solution set Qp in terms of suboptimality (x) p¹ or (C- - p", affine feasibility [[A(X) - b/l. and conic feasibility dist(X, They are closely related to quadratic growth in (QG). and are also referred to error bound propertics [46 [3 28) The error bound plays a vital role in proving fast linear convergence for many iterative algorithms 34 35 47). Indeed, some previous studies (27-30) have established similar results to Theorem for conic optimization, especially SDPs. As we will detail in Remark [ below, results more general and unified. Similarly, the growth and error bound properties also hold for the dual conic program.
Theorem 2 (Growth properties in the dual). Suppose strong duality and dual strict complementarity hold for (P) and (D). Consider the dual problems (D) and (). Let (X* ",""" ,,*) satisfy strict comple- mentarity, and the penalty parameter is chosen as p > tr(X*). For any compuct set V C R. SS
containing optimal solution (y" 20 E QD, there exist constants K. 7, > 0 such that
foly, Z) -
(00-((d)) (-d") + A (v) 211 2 k dist? ((y, Rp)), V(y, 2) E V,
(8a)
"This penalty parameter P guarantees that 4 and (P) are equivalent. To further ensure the dual problem of P is equivalent to the dual of (4), we need to choose p >> sup s,, tr(Z*). This subtle point is less
emphasized in the literature [30] 29 see Remark B.I in the appendix for details.
5

---

d' (b,)) +r11 (v) ZlI + a dist(Z, 2 k- dist' di. Z), V(v, Z) E V. (8b) If is further compact, then set V can be chosen as any sublevel set of fD. ie. {(y, Z) E R S" [D(y, 2) S 3 Z A (y)} with a finite B.
The compactness of S2p and QD in Theorems and is not restrictive, as it can be ensured by the dual and primal Slater's ' conditions (and A is injective) respectively; see e.g., [29 Proposition 2.1].
Remark 1. Our results in Theorems T and are more general and unified than previous ones (27430]. Theorems and 2 hold for both the indicator function and the penalty function (6). while all previous
results (27 have only discussed either one of them. We provide more comparisons below. The
guarantees in (7a) and (8b) directly lead to a quadratic growth property of fP and fD:
[x(X) - D" k. dist (X, Rp), AX S E S" (A(X) bb; [D 2) + dt 2= dist ((v: 2), PD). Vly, 2) E (1v, Z)ERT X
(9a)
A I
+ == (9b)
When considering indicator functions, this property ( is more general than 27 Corollary 3.1] since we allow for any compact set U (and also any sublevel set of fr or fD). In contrast, the size of the neighborhood around an optimal solution X in (27 Corollary 3.1] depends on the eigenvalues of an optimal dual solution Z Thus the neighborhood only exists but its size might be unknown. Furthermore, our results (7a) and (8a) allow for the residual of the affine constraints A(X) b and C A' (v) = Z, while 227 Corollary 3.1] requires strict affine feasible points.
When considering exact penalty functions, similar quadratic growth properties appear in [29] 30] However. the penalty p
[29 30 needs to be as large as p 2 su Jed tr tr(Z*). Our results in Theorems and 2 only require a smaller constant as p > tr(Z*) where 2* is an optimal dual solution satistying striet complementarity. and this result is established via new and simple argument (see Proposition B.2 in the appendix). Finally, an error bound similar to (7b) was also established in 28 Corollary 1] under similar assumptions of strong duality and strict complementarity. Our error bound (7bp does not require the absolute value of (P(X) p², and our proof strategy relies on a new characterization of exact penalty functions (see Lemma which offers a new (possibly simpler)
perspective than [28, Corollary 1]. The dual property (8b) is new and not discussed in (28)
Remark (Conic programs). Theorems and 2 are stated specifically for SDPs and (D). is known that linear programs (LP) and second-order cone programs (SOCP) are special cases of
SDPs. Therefore, results similar to Theorems and 2 when replacing S by nonnegative orthant or second-order cone also exist. Theorems and hold for general class of conic programs.
3.2 Proof sketches for Cheorems[aadd
We here provide key proof sketches for Theorems I and 2 properties of an indicator function and a penalty function.
One key step is the following growth
Lemma 3. Let X, Z E S satisfying (X, Z) = 0 (i.e., both X and Z are on the boundary unless one of them is zero). Ifl: S - is either an indicator function = ógg, or a penalty function
(X)) = p m0 Amax Amax(-X)) with p > tr(2),
(10)
then we have that
) (a1) (a1) [(0ōgr) -2 -1 = -N
(11)
Moreover, for any positive value μ E (0, oo), there exists a positive constant K such that
1(x) 2 1(x) + (- X) + k. dist? (xI)
B(X,(X
(12)
Note that / in 10 is related to, but not identical to, the exact penalty function in (6). The proof of
Lemma 3 heavily exploits the nice delf-dual structure of the cone S.. For better clarity, we provide the prools of and (12) in Proposition] B.I and Appendix crrrdidciieeeetillll....
Remark 3. We believe that the results in Lemma 3 are of independent interest, especially in terms of
the penalty function (TO). Building upon (2). one can further show is metrically subregular [48 Theorem 3.3]. The most closely related characterization is 27 Proposition 3.3]. which focuses solely on the indicator function of the positive semidefinite cone S However, even in this scenario, the
result in 27 Proposition 3.3] only guarantees the existence of a small neighborhood around X. In
contrast, our result (12 works for any closed ball BXX,, u) around X with finite radius μ >> 0. D

---

Upon establishing Lemma B with bounded linear regularity (see Appendix A.4) that is guaranteed by
dual strict complementarity, we can establish the following growth properties for and (
Proposition 1. Consider primal and dual conic programs PP) and (D) and their equivalent forms in
(4) and (5) respectively. Suppose strong duality and dual strict complementarity hold (P) and (D)
Let (X*, V T²) be pair of primal and dual optimal solutions, i.e., X* E Pop and (y² 7²) S2p.
For any y > O, there exist positive constants K1, "/,, K22, 7/2 such that
fp -p 71lAA(X) b11 z K1 (X, VX E B(X*, .N), - [D 2) 13 + 7 (1) 2 K2 dist ((,, 2), AD)) V(V, 2) E B(y"" ""ll",z"), z)),
The proof of Proposition 1 is given in Appendix D.I. We now see that Theorems and 2
direct consequences of Proposition D as max Amax (-X)] S dist(X,,") for all X E S". The compactness statement in Theorems and end2[com comes from the fact that the solution set Spp (resp. ?2p)
compact if and only if any sublevel set of fr (resp. fD) is compact (see, e.g., 229 Lemma D.1J).
Augmented Lagrangian Methods (ALMs) for SDPs
In this section, prove that both primal and dual iterates of ALMs, when applied to and (D).
enjoy linear convergence under the usual assumption of strict complementarity.
4.1 Inexact Augmented Lagrangian Method
In principle. ALM can be applied to solve both P and (D. However, most existing results focus on solving D) [8 19]. For simplicity, we here focus on one formulation of the augmented Lagrangian function for P The dual formulation is presented in Appendix [E.3] for completeness.
We start by introducing two dual variables y E R th and Z E $ and defining the Lagrangian function for (P) as (xX, y. Z) (C, XX + (y. b A(X)) + (Z. X).
The corresponding Lagrangian dual
function and dual problem read as
go(y, 2) = inf X
Lo(X, v; Z) and
max MER "EE""
go Z).
(13)
It can be verified the dual 13 the same as the dual conic program DD. Given penalty parameter r >> O, the Augmented Lagrangaan function of (P) corresponding to Lo is defined as
(X, y, 7) X) 2, (Iv rbb A(X))
gg (Z rx)11 |lvl |z|]3) (14)
where Tgg (.) denotes the orthogonal projection onto the cone S7. Note that L,, is continuously differentiable as ||Is (2) is continuously differentiable [18] Section 1]. Given initial points
(yo, Zo) E 1 x $4 and a sequence of positive scalars r < +00, the inexact ALM generates a sequence of {Xx} (primal variables) and (yk. Z } (dual variables) as
Xa+1 min Lrs (X, yk. Zz),
(15a)
Xe8
Mh+1 = + Tb V Lry (X4+1, Mk. Zx) = 3/k + rb - A(Xx+1),, 7 7x TA V z Ter, (X++1. Wk: 7x) Mg (7x xx4x+1).
(15b)
(15c)
For notational convenience, we write w = (y, Z) and wi = (yı,: Zx) and consider the following two inexactness criteria for solving [15a] (since it can be challenge to solve (15a) exactly):
Tere (XE+1, Wk) min T., (X, wx) S (2rk)) Σ 6k < 20,
(A))
x
Lye (Xe+1,
min L,, (X, wx) < 6 b w 12 (2rx), X
E Oz
co.
(B')
The two stopping criteria above are suggested by the seminal work of Rockafellar 23
4.2 Linear convergences of primal and dual iterates in ALM
After 23 one classical method for analyzing the convergence of the inexact ALM 15 is to utilize the connection between ALM and PPM. We review the following important lemma.
7

---

Lemma 4 (233 Proposition 6]). The dual iterates wk+1 = (Vk++1, Zx+1) in 15b and 15c the following relationship
satisfy
||w,+ prox (wx=) (2rx) S Lo 1,
inf Lrg (X, wx), Xe8"
where go is the Lagrangian dual function in
13
If (15a) is updated exactly, Lemma 4 confirms that wh+1 prox F1 (wx):: ): the dual iterate of the
ALM agree with the PPM iterate the dual problem
If (5aa) updated inexactly, the iterate
Wk+1 may not satisfy the affine constraint C = Z + A (2k+1). Moreover, viewing Lemma 4 the
stopping criteria (A)) and (B') naturally imply that the dual iterate wk+1 satisfies
|| p.. 90 (wx)l I Ck and || -rroxx. 20 (wx)
S 6 1114111 wull-
Then, can establish the convergence of the dual sequence {wx} in (15) from Lemma via PPM.
In particular, this observation was first discovered in [23] and later tailored in convex composite conic programmings in [26]. We summarize asymptotic convergences of (15) below.
Proposition 2 (Asymptotic convergences), Consider (P) and (D). Assume strong duality holds and
QD A 0. Let {Xa, 3 be a sequence from the ALM (15 under (A The following hold.
(a) The dual sequence }w is bounded. Further, limg-+0o Wik = w E EDp (i.e., the whole sequence converges to dual optimal solution).
(b) The primal feasibility and cost value gap satisfy
dist(Xx+1,, < || 12 Zk+1 l1/T + O, [|A(X*+1) bll 1y yk+ 11/rk + 0, - p" S L (x wk) min Lra (X, wx) + (1| || / (2rk)) - O. X
(c) If the primal solution set Dip in (1a) is nonempty and bounded, then the primal sequence { is also bounded, and all of its cluster points belongs to Dtp.
Proof. We give the sketch of proof for parts (a) and (b). A complete proof can be found in Ap-
pendix E.T Part (a) comes directly from the PPM convergence Lemma [ as Lemma and the
stopping criteria (A') naturally imply the dual iterate wk+1 satisties |x++ ceci--pree prox,,.-00 (wk) )| SE
and Σk=1 E 00.
In part (b), the first inequality uses the fact that Zk+1 + (X++1 Xx)/TK E S by performing
Moreau decomposition [49 Exercise 12. on Xx+1 Zz and using the update rule (1b) The
second inequality comes directly from [5ch: The last inequality uses the definition of T.r, k we)
in (14) and the fact minxes" Lr. (X, wk) S p".
Part (c) a consequence of part (b) and the fact that Qp is bounded if and only if for any 7 E R the set {X E S" dist((X SX 8T) < 71, ||((X) - bll I 72, X) ) S 73 } is bounded 23 page 110]. O
Proposition 2 establishes the asymptotic convergences for both the primal and dual variables. The linear convergence of the dual iterates can also be deduced when the negative of the dual defined in (13 satisfies (QG). However, the rate of the primal iterates remains unclear. Here, leveraging the error bound (8b), we also derive a linear convergence of the primal iterates, which is one main technical contribution of this work. We summarize linear convergence results below.
Theorem 3 (Linear convergences). Consider (P) and (D). Assume strong duality and dual strict complementarity holds (implying 52p + 0 and fip + 0). Let {Xu, wk} be sequence from the ALM A' and B The following statements hold.
15
under
(a) (Dual iterates and KKT residuals) There exist constants & > such that for all 2 k we have dist(X S u/s dist (wk, Slp; (C, - p- S 4% dist Up),
dist (ast(wx+1,, s2p) S mu - dist(wk, Up); || b1l S ph dist(ws Wk, Up), where 0 < 1k < 1, 14g > 0, and 16l > are positive finite constants. (b) (Primal iterates) If Spp is bounded, then the primal sequence {Xx} } also converges linearly to the solution set Qp, i.e, there a constant k. > such that for all k > k.
(16)
dist 3 (Xx+1, 92p) I Tk fist(wwk, 9p),
(17)
where Tk > 0 is finite constant.
8

---

Proof. The proof of part (a) is largely motivated by the techniques in [26] that focus on ALMs on dual SDPs. Part (b) is a consequence
the error bound (7b). Here, we highlight the key steps of the proof of part (a) due to the page limit, and detailed arguments about part (a) can be found in Appendix F.22 Note that if dual strict complementarity holds, Theorem 2 (with h in (5) as an indicator function) guarantees the following two nice properties: 1) -90 in (13) satisfies quadratic growth in (9b): 2) the error bound (bb) holds.
1. By the discussion after Lemma 4 since A and B' are in force, the dual sequence {wx} satisfies
||wx+1 po (wx) S Ck: || prox, r.. 90 (ux))l - 6 w&ll, Wk 2 0.
Applying the convergence result of PPM in Lemma I yields the linear convergence of the dual distance, ie., there exists a k 2 0 such that
dist (wst(w+++) S2p) S ps dist PD); Me <1, Ak 2 l1.
Using part (b) in Proposition 2 and ||wx+1 wvll T- dist (wk SDD) ) if 6% 1, show
1
max X k+1 ST),, [A((T++1) - bll} (1 rr
dist(wk: (kk SlD),
Wk+1 wp + || || + || dist(ww, Up).
(C, (x+1) - -p"
2r (1 5k)
Finally, as 6g + 0, there exists h2 2 0 such that 6g < 1 and for all & 2 12. Thus, part (a) then follows from taking k = max (ki, k2).
2. Note that the error bound (7b) and the assumption that Ωp is bounded guarantee that for any bounded set U containing Up, there exist constants 01, 022 03 > such that
(C, - (C, + (o)))((X) - bll + 02 (ist(X,,T) 2 ag dist? dist?(XX,(p))
VX EX (18)
By Proposition - part (c), the sequence {Xx} bounded. Let U S s" be a bounded set that contains Dp and all the iterates {X&}. Combing (18) with (16). we have
ag dist² (X&+1. S2p) S (44 + (an + (2))4) dist (wk, Pp),, Dividing both sides by az leads to the desired result in part (b). This completes the proof.
Vk 2
To our best knowledge, achieving linear convergence for the primal iterates of inexact ALMs requires a significantly stronger condition on the Lagrangian function [23 Theorem 5] and implementing an additional stopping criterion
[26] Proposition 3]. Unfortunately, as highlighted in [26] Section 3].
such an assumption in
23 Theorem 5] can easily fail for general conic programs.
Our result Theorem E] however, reveals that the linear convergence of the primal iterates also happens under the standard assumption of strict complementarity and bounded primal solution set. This suggests that primal linear convergence often expected since strict complementary is a generic property of conic programs 40 Theorem 15]. Our result not only completes theoretical convergences
of inexact ALMs but also offers insights for practical successes in 18 19
Remark 4 (Strict complementarity). As we in the proof of Theorem 3
strict complementarity is the key to ensure that 1) the negative of the function in (13) satisfies quadratic growth; 2) the error bound property (E.2) holds for the primal conic program. The quadratic growth is used derive the dual linear convergence (16), and the error bound is to conclude the primal linear convergence. 0
Numerical experiments
In this section, present numerical experiments to examine the empirical performance of ALM introduced in Section 4 We consider two applications in combinational problems and machine learning, including the SDP relaxation of maximum cut (Max-Cut) problem [50] and linear Support Vector Machine (SVM). The Max-Cut problem and the linear SVM can be formulated as
min X
X),X)
min *ER" CEERm
A1T ||01
2
subject to
Diag(X) =1,
subject to
(b) + S
X S4,
t R
where 1 is all one vector, A mx and b E I are problem data in the linear SVM, diag(b)

---

Primal east value gap
Dual cost value gap
KKT Residuals
10P
10"
10
4
10
10%
10
10-33
10
Iteration
Iteration
Iteration
Max-Cule - Maxe-Cul-2 -
Max- Cut-3
Primal value gap
Dual value gap
Residuals
10
10
10"
10-22
10-3
10-4
00060
10:
10
20
10
20
5
15
Iteration
Iteration
Iteration
SVM-1
SVM-2
- SVM-3
Figure Numerical convergence behavior of inexact ALM 15 for Max-Cut and linear SVM. The symbol ea denotes the KKT residuals 63 max/711 T2, 778, 77,, 1/5.
denotes the diagonal matrix with as the diagonal elements, and À >> 0 is a constant. We can see that Max-Cut is of the same form as (P). Despite linear SVM is not in the form of SDP (P) but quadratic program, the corresponding ALM with similar convergence guarantees can also be derived since a quadratic program is special case of SDP. For Max-Cut problem,
select the graph G1, G2, and
Gg from the website https: st stanfor ord. edu/ "olu/"yyyeyyylll yyye/ wyye/Gset////eeeeoe and only take the first 20 20 submatrix as the considered problem data C. For linear SVM, we randomly generate the problem data A E I 1210x100 100 and b E { 1, 1 100, We then apply the ALM (15) for those instances and compute the relative primal and dual cost value gap and the relative feasibility residuals follows
11,, Xx) p"
(bb yn)
d"1
||A(Xa)) bll
X Msg (Xx)ll
1+
pp1
.2
1
d
71
1+ |6
1 ||xx|l
||C A (yk)
1
Is. (Zx)
775 (C,, Xx) (b. vk)
173
+
||C||
774
1 Zx
1 1+ |d*1
The numerical results are presented in Figure In all cases, the primal and dual cost value gap and the KKT residuals all converge linearly to at least the accuracy of 10-5, The oscillation or flattening behavior that appears in the tail (when the iterates are close to the solution set) could be due the inaccuracy of the subproblem solver and computational impreciseness. A detailed theoretical analysis of such behavior is interesting, and we leave it to future work.
Further details on the algorithm parameters, problem instances, and more numerical experiments for machine learning applications can be found in Appendix F
6 Conclusion
In this paper, we have established the quadratic growth and error bound of two different variants ( and (5) of SDPs under the condition of strict complementarity. Central to our approach is the examination of the growth properties of the indicator and exact penalty functions. By leveraging these new quadratic growth and error bounds, we establish the linear convergence of both primal and dual iterates of inexact ALMs when applied to semidefinite programs, under the usual assumption of strict complementarity and a bounded solution set on the primal side. Our result not only fills void the convergence theory of inexact ALMs but also offers valuable insights into the exceptional numerical performance solvers rooted ALMs, such as SDPNAL+ [19]. We expect further interesting applications in machine learning and polynomial optimization
||| for inexact ALMs.
10

---

Acknowledgments and Disclosure of Funding
This work is supported by NSF ECCS 2154650, NSF CMMI 2320697, and NSF CAREER 2340713. We would like to thank Dr. Xin Jiang for the discussions on exact penalty functions, and Mr. Pranav Reddy for his assistance in proofreading the manuscript and contributions the appendix.
References
[1] Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. Linear matrix inequalities in system and control theory. SIAM, 1994.
[2] Renata Sotirov. SDP relaxations for some combinatorial optimization problems. In Handbook on Semidefinite, Conic and Polynomial Optimization, pages 795-819. Springer, 2012.
[3] Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas. Semidefinite optimization and convex algebraic geometry. SIAM, 2012.
[4] Gert RG Lanckriet, Nello Cristianini, Peter Bartlett, Laurent Ghaoui, and Michael Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine learning research, 5(Jan):27-72, 2004.
[5] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. Advances in neural information processing systems, 31, 2018.
[6] Ben Batten, Panagiotis Kouvaros, Alessio Lomuscio, and Yang Zheng. Efficient neural network verification via layer-based semidefinite relaxations and linear cuts. In Zhi-Hus Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 21 119-2190. International Joint Conferences on Artificial Intelligence Organization, 8 2021. Main Track.
[7] Lieven Vandenberghe and Stephen Boyd. Applications of semidefinite programming. Applied Numerical Mathematics, 29(3):283-22) 1999.
[8] Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM review, 38(1):49-95, 1996.
[9] Farid Alizadeh. Interior point methods in semidefinite programming with applications combinatorial optimization. SIAM journal on Optimization, 5(1):13-51, 1995.
[10] Henry Wolkowicz,
Romesh Saigal, and Lieven Vandenberghe. Handbook of semidefinite programming: theory, algorithms, and applications, volume 27. Springer Science & Business Media, 2012.
[11] Yang Zheng, Giovanni Fantuzzi, and Antonis Papachristodoullu. Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization. Annual Reviews in Control, 52:243-279, 2021.
[12] Zaiwen Wen, Donald Goldfarb, and Wotao Yin. Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Compur.,
2010.
[13] Brendan O'Donoghue, Eric Chu. Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogencous self-dual embedding. Journal of Optimization Theory and Applications, (69(3):1042- 1068, June 2016.
[14] Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn. Chordal decomposition in operator-splitingg methods for sparse semidefinite programs. Math. Program., 180(1):489-55 2020.
[15] Magnus R Hestenes. Multiplier and gradient methods. Journal of optimization theory and applications, 4(5):303-320, 1969.
[16] Michael JD Powell. A method for nonlinear constraints in minimization problems. Optimization, pages 283-298, 1969.

---

[17] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program., 95(2):329-33333 2003.
[18] Xin- Yuan Zhao, Defeng Sun, and Kim-Chuan Toh. A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim., 20(4): 2010.
[19] Liuqin Yang, Defeng Sun, and Kim-Chuan Toh. Sdpnal+: a majorized semismooth Newton- augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Computation, 7(3):331-366, 2015.
[20] Alp Yurtsever, Joel A Tropp, Olivier Fercoq, Madelcine Udell, and Volkan Cevher. Scalable semidefinite programming. SIAM Journal on Mathematics of Data Science, 3(1:1111-200, 2021.
[21] Ying Cui, Chao Ding, Xu-Dong Li, and Xin- Yuan Zhao. Augmented Lagrangian methods for convex matrix optimization problems. Journal of the Operations Research Society of China, 10(2):305-342, 2022.
[22] Ling Liang, Defeng Sun, and Kim-Chuan Toh. An inexact augmented Lagrangian method for second-order cone programming with applications. SIAM J. Optim., 31(3):1748-1773 2021.
[23] R Tyrrell Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of operations research, 1(2)977-16,, 1976.
[24] Tyrell Rockafellar. The multiplier method of hestenes and powell applied convex program- ming. Journal of Optimization Theory and applications, 12(6)5555-562, 1973.
[25] Fernando Javier Luque. Asymptotic convergence analysis of the proximal point algorithm. SIAM Journal on Control and Optimization, 22(2):277-293, 1984.
[26] Ying Cui, Defeng Sun, and uals generated by the augmented Lagrangian method for convex composite conic programming. Math. Program., 178:381-411 2019.
Toh. On the R-superlinear convergence of the KKT resid-
[27] Ying Cui, Defeng Sun, and augmented Lagrangian method for semidefinite programming with multiple solutions. arXiv preprint arXiv: 1610.00875, 2016
Toh. On the asymptotic superlinear convergence of the
[28] Lijun Ding and Madeleine Udell. A strict complementarity approach to error bound and sensitivity of solution of conic programs. Optimization Letters, 17(7):155111574 2023.
[29] Feng- Yi Liao, Lijun Ding, and Yang Zheng. An overview and comparison of spectral bundle methods for primal and dual semidefinite programs. arXiv preprint arXiv:2307.07551, 2023. 2023.
[30] Lijun Ding and Benjamin Grimmer. Revisiting spectral bundle methods: Primal-dual (sub) linear convergence rates. SIAM Optim., 3302):100-1133,, 2023.
[31] Ying Cui, Chao Ding, and Xinyuan Zhao. Quadratic growth conditions for convex matrix optimization problems associated with spectral functions. SIAM J. Optim., 27(4)22332-2355, 2017.
[32] Jos F Sturm. Error bounds for linear matrix incqualities. SIAM Optim., 10(4):1228-1245: 2000.
[33] Shuzhong Zhang. Global error bounds for convex conic problems. SIAM J. Optim., 10(3):836- 851, 2000.
[34] Dmitriy Drusvyatskiy and Adrian Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Mathematics of Operations Research, 43(3):919 998,, 2018.
[35] Zirui Zhou and Anthony Man-Cho So. A unified approach to ervor bounds for structured convex optimization problems. Math. Program., 165:689-728, 2017.
[36] Alan J Hoffman. On approximate solutions systems of linear inequalities. Journal of Research of the National Bureau of Standards, 49(4), 1952.
12

---

[37] James V Burke and Paul Tseng. A unified analysis of hoffman's bound via fenchel duality. SIAM Optim., 6(2):265-288)) 1996.
[38] Tyrrell Rockafellar. A dual approach to solving nonlinear programming problems by uncon- strained optimization. Math. Program. 5(1):354-373, 1973.
[39] Mirjam Dür, Bolor Jargalsaikhan, and Georg Still. Genericity results in linear conic program- ming- a tour horoizz.. Mathematics of operations research, (2(1)777,94 2017.
[40] Farid Alizadeh, Jean-Pierre Haeberly, and Michael Overton. Complementarity and nonde- generacy in semidefinite programming. Math. Program., 77(1)111-125) 1997.
[41] Lijun Ding and Madeleine Udell. On the simplicity and conditioning low rank semidefinite programs. SIAM J. Optim., 31(4):2614-2633 2021.
[42] R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
[43] Leventhal. Metric subregularity and the proximal point method. Journal of Mathematical Analysis and Applications, 360(2):681-688 2009.
[44] Feng-Yi Yi Liao, Lijun Ding, and Yang Zheng. Error bounds, PI. condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. arXiv preprint arXiv:2312.16775, 2023.
[45] Andrzej Ruszezynski. Nonlinear optimization. Princeton university press, 2011.
[46] Jong-Shi Pang. Error bounds in math, program. Math. Program., 79(1-3):299-33,, 1997.
[47] Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Math. Program., 175:69-107, 2019.
[48] FJ Aragón Artacho and Michel H Geoffroy. Characterization of metric regularity of subdiffer- entials. Journal of Convex Analysis, 15(2):365, 2008
[49] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009.
[50] Michel X Goemans and David Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1 1156::115-11455 1995.
[51] Tyrrell Rockafellar. Convex analysis, volume 11. Princeton university press, 1997.
[52] Eduardo H Zarantonello. Projections on convex sets in Hilbert space and spectral theory: Part i. Projections convex sets: Part ii Spectral theory. In Contributions nonlinear functional analysis, pages 237-424. Elsevier, 1971.
[53] Heinz H Bauschke and Jonathan M Borwein. On projection algorithms for solving convex feasibility problems. SIAM review, 38(3):367-426, 1996.
[54] Heinz H Bauschke, Jonathan Borwein, and Wu Li. Strong conical hull intersection property, bounded linear regularity, Jameson's 's property (G), and error bounds in convex optimization. Math. Program., 86: 135-160, 1999.
[55] Michael L Overton. Large-scale scale optimization of eigenvalues. SIAM J. Optim., 2(1):88 -200 1992.
[56] MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 9.0., 2019.
13

---

Contents
Introduction
2
Preliminaries
Strong duality and strict complementarity
2.2
Proximal point methods (PPMs)
3
Quadratic Growth in SDPs
3.1
Growth and error bound properties
3.2
Proof sketches for Thheorems) and
4
Augmented Lagrangian Methods (ALMs) for SDPs
Inexact Augmented Lagrangian Method
4.2
Linear convergences of primal and dual iterates in ALM
5
Numerical experiments
Conclusion
10
Optimization Background
15
Standard notion of strict complementarity SDPs
15
A.2
Augmented I Lagrangian Methods (ALMs) for inequality constraints
16
A.3 Augmented Lagrange functions for inequality constraints
17
Bounded Linear regularity and regularity conditions
17
B
Exact penalty forms of conic optimization
18
B.
I Subdifferential of the exact penalty function
18
B.2 Proof for Proposition B.1
19
Growth properties of indicator and exact penalty functions in Lemmal
20
Proof of Lemma C.I
20
C.2 Growth property of the exact penalty function in 10)
21
D Growth growth under strict complementarity
22
D.I Proof of Proposition]]
23
D.2 Illustration of quadratic growth
24
Proofs and supplemental discussions Section 4
25
Proof of Proposition
25
Proof of Theorem 3
26
ALMs for dual conic program (D)
28
Details of the numerical experiments
30
14

---

Appendix
The appendix is divided into the following seven sections:
1. Appendix A
presents some preliminaries in conic optimization and standard ALMs.
Appendix presents a self-contained proof for the exact penalty functions and a new characterized of the preimage of the exact penalty functions.
3. Appendix C
completes the proof of growth properties of the indicator function and exact penalty function.
4. Appendix D details the proof of Proposition T and presents a simple example to illustrate the growth property.
5. Appendix completes the missing proofs in Theorem 3
Appendix discusses the convergence of ALMs applied to the dual problem (D).
7. Appendix
presents further details of numerical experiments in Section
A Optimization Background
Notations For clarity, we summarize common notations here. We use R" to denote the n- dimensional real space and S to denote the space real n x n symmetric matrices. The cone of nonnegative orthant is denoted as RT {ir E RR z; 0, vi .......... The cone of positive and negative semidefinite matrices
defined S {X E S" xTxu 2 V. R") and s2 -St respectively. For vectors in R", the inner product (:: defined (r.y) x y and the normal || stands for the l2 norm. For matrices in S", the inner product (--) is defined as (X, Y) = YY) and the norm |lap- |l. and || denote the operator two norm, nuclear norm, and Frobenious norm respectively. Given set S S IR", the relative interior of S is denoted as rS), and (z(z) is defined as the indicator function of S, i.e., 55(x) = 0 x E and (5()) oc otherwise. The closed ball with a radius i around the center I R is written as B(x, n)) {y E Re |y - x < nJ.
A.1 Standard notion of strict complementarity in SDPs
In this subsection, we review the standard algebraic notion definition for SDPs which is equivalent to Definition 2 A proof of the equivalence can be found 28 Appendix B].
Definition A.1 (Strict complementarity for SDPs). Consider the pair of primal and dual SDPs (P and (D). We say the strict complementarity holds if there exists pair of primal and dual solutions (X* y =*) satisfying
X 2t E S4 or rank(X*) + rank(Z*)
(A.1)
With the complementarity slackness (X*, -²) O. we have X 2 X = 0. This means there exists an orthonormal matrix Q E Rx" with QQQ = I, such that
X Q diag())...... An) ) QT, Z Q diag(w).....
w,) QQQ
(A.2)
and A,u; 0, = 1, ........ ; n. Then, (A.I) implies that exactly one of the two conditions X, = 0 and wi = 0 is true in (A.2). In other words, the eigenvalues of X and Z* have complementary sparsity pattern.
Remark A. (Dual strict complementarity in the general case). The dual strict complementarity in Definition 2 is consistent with [28] Defnition 2]. A variant of dual strict complementarity in the general case is given in [34 Section 4], which requires that
0 E relint (Og(")))
(A.3)
where (2y) = (b, v) 637 (C (v)) Definition 2 is also consistent with A.3).. Indeed, let dual
optimal solution (y", ) satisfy (A.3 Considering dg(y) + A(Ns (C (v))) and using
[5T Corollary 6.6.2 and Theorem 6.6], we have
0 E relint((b + A(Ngr ))) = relint(AAWsg: (z*))) = + A(relint (Z*))) which means there exists point & E relint(Ngg: (Z*)) such that 0 = b b+ A(s). Equivalently, there exists X - relint (ainnt(NNr)) (-Z*)) (recall that ( - such that A(X*) = b. This is
equivalentt to Definition 2
15

---

A.2 Augmented Lagrangian Methods (ALMs) for inequality constraints
We here review some classic results of ALM. Consider a constrained convex optimization problem
min zEAo
f(x)
(A.4)
subject to f1(x)) S 0, Vi 1121,2.....
where Ro S I" is a closed convex set and fs EE + R are proper closed convex functions. We associate each incquality constraint in (A.4) with a dual variable 2 2 0, and the Lagrangian function
for (A.4) is Lo(x, 2) = f(x) + i= Z:J (z). The corresponding dual function is
90(2) inf Lo(ar, =).
(A.5)
zEAt
One way to define the augmented Lagrangian for (A.4) is to transform the inequality constraints into equality constraints [45] Chapter 4.7]. After some manipulation (see [45] Equation 4.79] or
Appendix A.33), the classical augmented Lagrangian with parameter r > 0 for (A.4) reads as
L, =) - f(x) + 2r (Ile (= +r(())) - 11=11
(A.6)
where Hgy (-) denotes the Euclidean projection onto RT. Note that L, is differentiable in æ [52
Given an initial point 2g E Rd and a sequence of positive scalars ro r= < +00, the inexact ALM generates a sequence of {2x}} (primal variables) and {zt} } (dual variables)
Ik+1 RJ min Lyz 2x).
(A.7a)
zE
+++1 2/ + Pk V Lr, (1R+1, =A. T (=k + rx (E((( k = 0,
(A.7b)
The convergence of 23 and ž depends on the inexactness in (A.7a). For this, the seminal work by Rockafellar [23] points out an important connection between PPM and ALM, summarized below. Lemma A.1 (3 Proposition 6)). The dual iterate 2k+1 in (.76 satisfies the following relationship
|x+1 proxx..-so (2))) (=x)11/((rr)) /(2rk) S Tirn (IK+1, 2x) inf
Lr, (x. 2k);
=EAo
where go is the Lagrangian dual function in A.5) and L,, denotes an extended form of the augmented Lagrangian L,, as [I, (x, 2), i Lo. otherwise I, 2) oc.
Note the subtle difference between Lemmas 4 and A.T If (A.7a) updated exactly, Lemma A.
confirms that + pro (z&). In other words, the dual iterates of the ALM are the same as the iterates from PPM on the dual problem (A.5). Moreover, by controlling the inexactness (A.7a).
the convergence of the dual variables 2ạ can be naturally guaranteed from Lemma] Motivated by (a) and (b). the following two criteria are commonly used in (A.7a)
Trey (IX+11, =k) min T.r, (I,, =x) S (2rx), Ek=1 ER < C0,
(A)
Tee, 2x) min L.,, (x, =x) S 02 1 -2x
2x /
k= 6x < 00,
(B)
=EXo
where fesJas and {8x 1220 are two sequences of inexactness. Note that A and B guarantee the dual variables 2y from ALM (A.7) satisfy (a) and (b) with the inexact PPM
( respectively. Let
S = argmax.20 =20 9o (z) denote the set of optimal dual solutions for (A.4. Combining Lemma A.
with Lemma [
the iterates from the inexact ALM (A.7) has the following convergence guarantees.
Lemma A.2. Assume S + 0. Let {IK, 2 be a sequence generated by the inexact ALM (A.7p.
(a) If criterion A is used, then limg-+00
Zoo ES (i.e., 21 converges to dual optimal solution), 1,...,m m (primal
and the primal sequence {2t} satisfies fi(xx-1) S 1|24 - -b+1ll/ck.
feasibility), and (c. (x41))
S (ek + || = /l11)/ (cost value gap).
(b) If both criteria (A) and (B) are used, and the dual function -9o in (A.5) further satisfies QG) with a coefficient pq > O. then there exists a > 0 such that dist(z*41, S ps:
dist(zk, S), wk 2 k. where Pa 1-8
4,+26x with 0 1/ 3////// /capt+1<1.
The first asymptotic convergence for limg- 24 = 2ec E S directly comes from Lemma and the asymptotic convergence in terms of primal feasibility and cost value gap is taken from 22 Theorem 4]. The second linear convergence in Lemma A.2 is only guaranteed for the dual iterates zg. which is also implied by Lemma However, the rate of the primal iterates d& is unclear even with the quadratic growth condition. With a much stronger condition on the Lagrangian, the classical result in
23 Theorem 5] can ensure linear convergence of zg.
16

---

A.3 Augmented Lagrange functions for inequality constraints
One straightforward way to define the augmented Lagrangian for the inequality form (A.4) is first transform (A.4) into the following equivalent problem
min
f(z)
=E2o.120
(A.8)
subject to +())+o==0
1,.......
Then the augmented Lagrangian for the above > 0 is defined as
problem with a penalty term
(=( Σ =(Ji(s)+ ub) + Σ (J((z) + u;)²
= =((x) + 2r
(1 + r(f (z) +)]l ||
Note that Ly a decoupled quadratic function in terms of u. Minimizing Lr v, 2) with respect e 2 0 with a fixed and y, we derive the optimal as
max - vi
1,...,m.
Upon plugging the optimal in the Ly with some arrangements, arrive the classical augmented Lagrangian for the problem with inequality constraints (A.4)
1 (I -|=112) 2r
A.4 Bounded Linear regularity and regularity conditions
We review an important concept: bounded linear regularity of collection of closed convex sets.
Definition A.2 (Bounded linear regularity [53] Definition 5.6]). Let DI...., Dm R be closed convex set. Suppose D == Dj n. n Dm is nonempty. The collection [DI,..., Dm } is called boundedly linear regular for every bounded V R", there exists a constant x > 0 such that
(as D) I x max(dist(z,, D1), ... dist(æ, Dm)). Vx V.
Bounded linear regularity allows us bound (up some constant) the distance to the intersection D (which can be complicated) by the maximum of the distance to D,, which often easier to compute. The following result shows sufficient condition for bounded linear regularity.
Lemma A.3 (154] Collorary 3)). Let DI, Di...., Dm C RR be closed convex set. Suppose that DI,..., (r S m) are polyhedra. Then (D,,..., is boundedly linear regular if
(Ni=1.2.....D) N (O relim relim((D))) + 40,
where relint denotes the relative interior:
This result indicates that collection of closed convex sets is boundedly linear regular if the rela- tive interiors non-polyhedral sets have a non-empty intersection with the rest of the polyhedra. Lemma A.3 plays key role in the proof of Theorems and 2 In particular, as will see in Appendix D.I. the optimal solution set (P) i.c., Ωp, can be characterized as
Op X, n (8g) (00g)"((2"") (-z*), V(y" 2*) E Sp,
where X, = (X A(X) = b). Thus, assuming dual strict complementarity (there exists
X* E relint (0gg) 3)) given compact set C S" containing X*, Lemma A.3 ensures the following holds
dist X, 1p) < distsst +
VX Eu,
where 0i and 02 are two positive constants.
17

---

B Exact penalty forms of conic optimization
In this section, we characterize the connection between exact penalty functions and indicator functions (6). Most importantly, we give simple proof for the exact penalty functions. The main result is stated in Proposition B.2. We first state the preimage characterization of subdifferential mapping of the exact penalty function in Proposition B.T which is more general result of the first part of
Lemma 3 (i.e. (TI). The second part of Lemma (i.c., (12) is postponed to Appendix C
B.1 Subdifferential of the exact penalty function
Proposition B.1. Let Z S7. and define
1(x) = p pmxx (0, Amax (-X) with p > tr(Z).
(B.1)
Then for all 84 satisfying p > tr(S), holds that
(-S)= ((o)) (-S).
(B.2)
One can see that 11 is special case of Proposition B. with S = Z. We postpone the proof of Proposition B.I to Appendix B.2 Be aware that (B.2) does not mean the mappings (at)-1 and (ds; )- are the same for each point in the domain, while the equality only holds for certain points satisfying the relationship with the penalty coefficient p in B.I). We use simple example to illustrate this subtlety.
Example B.1. Consider 1 IR R as ((x) 2 ma, -x} which is the scalar version of the function in B. with 2. The subdifferential Øl : R = IR and 0ōR, =NR, can be computed as
0,
if > 0, if x = 0, and 0öR, (x) = (-00, 0},
if x > 0,
0,
0l(x)
[-,,
if x = 0, if x O.
-2
if O,
0,
Thus, the preimages can be verified as
0,
if > 2, if 2 2,
(-,0,),
0,
if > 0, if 0,
0,
if < 2, and 0(62,)-1(
10,
[0,
if = 0, i O,
0,
if 0.
0,
This shows that (01)-1(-))) = ( holds only when z < 2.
With the preimage characterization in Proposition B.1 the following result on the exact penalty functions follows easily by choosing the penalty term p correctly.
Proposition B.2 (Exact penalty function). Assuming strong duality holds for P and D
equivalent to the primal SDP (P) if the function g in 4 is chosen to be the corresponding indicator
function, i.e., g = 6gy, or the exact penalty function
((X) pmax(0, Xmax ( X)} with p tr(Z*),
(B.3)
where (v*Z*) E Pp is optimal dual solution of D
Proof. The case for the indicator function ōsg is clear. We consider the case for the exact penalty function. Note the dual of (4 is
max n.2
(b,
subject to
A'(y) + Z = C,
(B.4)
tr(Z) S P,
Z E ST.
18

---

Let S2p, and ΩD, denote the optimal solution of (4) and B.4 respectively. First, it is clear that
DD S 2D as there is an extra constraint BB.7 compared with (D) Second, as the problem convex, a pair of primal and dual solutions following KKT system holds
( 9" -*) solves (4 and (B.4) if and only the
A(8*) b, Z = A A0)) 0 2 + =g((X*)
Then the primal solution set can be written
Rp. = Xy n (0y)
v(j" 2*) E PDz-
where No = X E S"
|A = b). Note that (y", -²) is an optimal solution to (B.4) as (y", Zz) is feasible in (.44) and (b, y²) m (B.4) S d² {b, y²) by construction. We can write Slp, as Ap N, n (0g) (-Z") 2, n (0ōg7) (--2",
where the last equality uses On the other hand, we can write Qpp as
(ōōgy - (-Z*) in B.2 as tr(z*) and Z E EST.
Spp = Ao n (ōōsy) >- (-Z").
It is clear that S2p, S2p and the proof is complete.
Remark B.1 (Dual problem). Note that Proposition B.2 only guarantees the cost value and solution sets of ④ and (P) to be the same, while the solution sets of (D) and the dual of (4) may differ, as seen in the proof of Proposition B.2. To fully equate (D) and the dual of 4 one can choose the penalty coefficient p as p > sup Een tr tr())). This choice of p can guarantee every optimal solution in
(D) is also an optimal solution in (B.4) as the extra constraint in (B.4) (compared with (D) does not
affect the solution set. Combining this with the fact ΩD2 C 2Dp we conclude that Up = S2p.
B.2 Proof for Proposition B.1
The following proposition showcases the subdifferential calculation of the function ((X) m0, ( with 2 0. It is a standard result of the subdifferential of the maximal eigenvalue of symmetric matrices and standard subdifferential calculus.
Proposition B.3
(55 Theorem 2] and [45] Theorem 2.87]). Let p 2 and X S" with
having t multiplicity. The subdifferential (X) = m0, Amax (-X) is characterized by
if Xmmin (X) > 0,
OI(X)
(-pPSPT S (r(S) > (X) = 0,
(B.5)
-PSP S tr())) 13 Amin (X) < O,
where columns of P Buxt are orthonormal eigenvectors corresponding Amax (X).
A
0
P Pz
Proposition B.4. Let E St \ (0} and write Z = [PI
Pa]
with A1 E S Let
0
1(x) = pmax (0, Amaxx (-)) with > tr(Z). We have
(01) (0) ST,
(at) (Nsg) ) (-
Proof. The case (0) St can be easily observed from the first two cases in (B.5). We then consider the case Z E S \ (0). Given a X E S", orthonormal eigenvectors corresponding to Amax (-X) where is the multiplicity of Amax (-X). It follows that
the matrix Px E Ruxt denote the
(-1) = (X E 5.
Z E (((X)}
(a)
{X E ST.
ST
IZ E PPxSPX
S tr(() <1}
(b)
[PI
Pa
0 0
P
10 R rxy
B St
0
B
P
No: (-Z)
(Nog) ) (-
19

---

where the domain $ \ and the strict inequlaity tr(S) < in (a) is due to the choice p > tr( and (c) is common form of Ngn Z) [28 Complementary face Section 3.3]. We argue (b) is correct by verifying the following two sets are equivalent.
D1 {X E
S
S"
Z E
PPx S E tr(() <1),
0
0
P
D2
PP
P₂
IER B BEST
O
P
(Di) = (D2) Let X E DT. Write X = P.OP! + PRApP3 with Po E Raxt and Ps. E Rax(n-0, As (Pi) S span we have span(Pa) S span(P2). Thus, there exists U pax(n-r) such that U In-r and P3 = P.U. We then have PsAgP3 Ps(UAAU*))P
This means X D2- (D2) = (Di): Let X D2. is clear that span is in the eigenspace of 0 of the matrix X.
Choosing S = A E 44 we can recover Z as p
A PT = Z. pP
Also, tr(S) tr(A))/p so we conclude X E DT.
C Growth properties of indicator and exact penalty functions in Lemma 3
One key step in the proof of Theorems T and 2 is the growth properties of the indicator function or the penalty function (IO), summarized in 112 in Lemma In this section, complete its proof details. We first establish a lower bound of Z2 x) in terms of the distance dist (ist(X,Nssp Z)).
Our proof uses some techniques in (27).
Lemma C.1. Let X, Z $4 satisfying (X, 2) 0 (i.e., both X and Z are on the boundary unless one of them is zero). For any positive μ E (0, 20). there exists constant such that
(2, 2 K dist?
(X,N
E nB(X
(C.1)
where BB ((X,1) = (X Th ||| X1I S n1 denotes a closed ball with radius μ and center X.
Note that C.I is the reformulation of
0 2 0 - - + k. dist? (x.Noz))(-2)) AX EXESTn(XX,,.
(C.2)
Indeed, C.2 is the same as 12 Lemma 3 when choosing ógg (recall that we have 6g (X)
and the relationship in consequence of Lemma
Therefore, Lemma 3 for the indicator function 1 ōg. is a direct
The proof of Lemma C. is given in Appendix [.I In Appendix C.2
we will use Lemma
C.I to prove the growth property for the exact penalty function in (10).
C.1 Proof of Lemma
We only need to consider the case where 7 * 0, since the case Z 0 is true by observing that
(x, Z) 0, dist(X, y- (0) = dist(XX ST) = 0, VX E ST n B(),
We first introduce the following useful inequality for positive semidefinite matrices.
A
B
Lemma C.2. Suppose
BT
D
E
St. Then | op tr(A) B
We now proceed with the proof. Fix a p > 0. Consider X, Z E Sy and (X,2) 0. Let X E ((X ns? and write
A
0
P
2 - =
PJ
0
0
P
20

---

where A1 E , is a diagonal matrix containing the positive eigenvalues of Z. Let P = [P] Pa] be the orthonormal eigenvectors matrix. The projection of X onto N(83)0 (- 2) can be verified as
0 P
0 P
O
PT
||X - Y|1. YENopo
argmin
Hence, the distance dist. 2 (X, N8973 3 Z)) can be computed as
0
dist (x77) =
X P
PT
0
P
(C.3)
P X
=|
P. XPI
0
where the second equality uses the unitary invariance. It remains to estimate the terms || 2112 and |PTxP22'''' By the assumption
X E B( 14) nst and unitary invariance, we have
# 2 X X| = PT (X XIP z max (X XX -X- X)PII (C.4)
Z max [1] XP, [lop. [|] - Pa)pp))
where the last inequality uses the fact that P1 relationship || 2 Ilop- It follows that
(X, 0 and X, 2 S and the
|P] x (P. XP, P!PP) S XPP P. XPI S tr tr XP1);
(C.5)
where the second inequality uses the generalized Cauchy-Schward inequality (ll |l. and || lop norms dual to each other; have (X, Z) || op: VX, Z S"), and the last inequality uses
(C.4) and IPPPPP tr XP X S7.
On the other hand, applying Lemma C.2 on PT XP yields
x < x2 ol tr tr(P[xP)) S +|*|] XT())
(C.6)
where the last inequality is due to
Moreover, we have
(2.x) = PPIIIPT x) (A,,PT 2 Amin(Ai) tr())
(C.7)
where Amin (At) > 0. Putting C.3 CC.5) and (C.6 together and choosing K x
(A1)
gives us
dist (X, (8 (-Z)) k: <x3pp 2| tr(T S (Z,x),
where the last inequality is due to
C.7 This completes the proof.
C.2 Growth property of the exact penalty function I in 10
Throughout this section, we fix a pair of matrices (X, 2) S x s satisfying (X, = 0. We
need to prove for any positive value E (0, oo), there exists positive constant k > 0 such that
((x) (())+ + (- + dist? (x1) (-))- VX ((X,,) (C.8)
Note that it is equivalent to showing that there exists a k >> 0 such that
((X) > (-Z, +x dist? XXNNByyo (-2)
VX ((X,(X
(C.9)
R
has already applied a non-trivial fact (at) -1 (-Z) Z) (N 1 Z = N for the exact penalty function (10) which has been
as ((X) and (2 0 by assumption. This result C.9
established in Proposition B.1
21

---

In the following, we will bound the terms R₁ and R2 in (C.9). The term R2 will rely on Lemma C.1 One key difference between (C.9) and (C2) is that the penalty function ((X) < oo when ç S while dgn (X) 0o, vX E S
Let us fix a μ 0, consider X E B(X, p)), and write p 8 + tr tr We first consider the case when 2 = O. Note that (Z, x 0 and Mo (0) = S.. The distance dist X, (8 (0)) can be upper bounded dist (i,tt (0)) ||X Msp (X) 22 max Amax (-X)²² < (mass (-X))
Choosing
yields
(-Z* X) k
dist (X, (Ns33 (0)) < p1, (000)mXx)x-)) = (((), AA VXEB(X,I))
We then consider the case Z + 0.
We first bound R₁ = {)
(-Z,x) -(Z, 1ssy (X) - x) - ( 2 (X))
1ls.
S || Ig (X) - X1lop (2,
Iss (x))
tr(Z) max A (-X)) (z, 11 (x))
(C.
where the inequality applies the general Cauchy-Schwarzz inequality (II ||| and llop norms dual to each other; we have (X, 2) < || ol, V.,, 2 S
We then bound R2 dist (x, . (0)))) (- Z)): Let Y be the projection of Ng (X) on to
Nisgyo (-Z), i.e., Y veN MMs (X) - VII. We then have
dist? (X.N(17yo0 (-) $ - s 2 Ig; (x) 2| (X) YI (C.11)
The first term ||- - 11s7 (x) can be bounded by
|X Uss (x) < max Amax (3X np max (-x)x-XX)
where the last inequality comes from Amin (X) Aminn
(X) >minn
|mmax (-X) /t Amiu (X)
and ||X - X|| S μ.
The second term [[Tge (X) - Y122 can be bounded by Lemma C.1 i.e., there is a 13' > 0 such that
|1s (X) 2112 Isg (X),
Putting everything together and choosing x = mint 5 2mp 5 yields
(-Z,x) + dist? (x,N(18)-(-211
< tr ()) max (0, Amax (X)] ( 2, 1gg (x))
+ x2mp max (0, Amare (-x] + 2k
k¹ (IIsy (X), 2)
< tr( (Z) ma Amax (-xx + 8 mmax Amax (-X)
= p max (0, ( X)} = 1(X), VX E
D Growth growth under strict complementarity
As mentioned in the main text, the key step to prove Theorems and 2 is to establish the growth property (12) in Lemma Sonmaawwhic which we have proved in Appendix C
Once Lemma is established, with In this appendix, we first provide proof for Proposition in Appendix [D. and use a simple example to illustrate the quadratic growth property in Appendix D.2
strict complementarity assumption, we can deduce Proposition
22

---

D.1 Proof of Proposition 1
The following proof is adapted from 27 We first prove the primal case. Fix a a and X E Qp.
As the problem convex, a pair of primal and dual solutions (X*, , 2-) solves ( and its dual problem if and only if the following KKT system holds
A(X*) = b, 2" = A0' 0 2- + 0g(X*)
Combined with the fact that any primal and dual solution forms a pair, the optimal primal solution Ap can be characterized
2p = N n (8g) , E Sdp
where X. = E S" A(X) = b}. Let (X", 2*) be a pair of primal and dual solutions satis-
rying X relint((0g) (1(00))((--0) ))) (strict complementarity assumption). There exist ai Ki, 82
such that for all X E B(X*, ,4 the following holds
dist (x, Rpp dist (X, No n (0g) (-
S ai (ddstt(( Xo) dist(X (X, (-
(D.1)
< <m ( (n) + dist (X, (0g) (-)))))(2))))))))
3 {xx b1| + dist 2 (X, (0y) --(-"))))
where the first inequality applies Lemma A.3 the second inequality applies (A B) S 2 + 2B for all A, B 2 0, the third inequality uses the fact that Xg is an affine space. On the other hand, we
know (X,22)
0 for all X E Qp naturally, so Lemma 3 can be applied here on 2* and 2+ (the
proof of Lemma is provided in Appendix C.2 For all X B(X*, 11) holds that
fr(X) = (C, x) + (X))
2
(A()(((()(((())00))))0)))))()))) C, X²) + 16 dist 2 (X, (0g) (-22))
2 +(A -x K
dist (X, (x)(p) xI(A(()) - b112
K2
2 fx -100 [IIA(X) b11 xI|A(X) b112 +
dist (X, 2p)
K2
= =/((x'- (115" +0]++|AAXX* xI) - bI)))((())-- - b1 +
K
dist dists(Xx (x, 2p)
12
2 2/((X)) - [| 7)) bll + K2
dist 2 (X, Stp),
where the first inequality uses the growth property on for X and Z. 12). the second inequality uses (D.I). the third inequality uses the definition of the adjoint operator and Cauchy-Schward Schwarz inequality, and the last inequality uses the fact that X is in bounded set (BX* 11) so there exists some 7 2 0 such that x xi||A(X) bll 7. This completes the proof.
We move on to prove the dual case. Similarly, we let (y*, 22) E Up and μ > 0 and characterize the optimal dual solution as
2D = 2n n (TT x (ah) (ah)
XX* E Sp:
where Zo - ((v, 2) E RT x 8r C -C-A' (1) Z). Let (X*,"*, 2*)) be pair of primal and dual solution satisfying Z E -- Note that
relint(RR" x (0h) ( = R. x relint((ah)
Therefore, the existence of such a pair of strict complementarity solution implies
Zo n relint(R" x (ah) 0.
Hence, following the same argument to (D.I) we know there exists a constant > 0 such that
dist? ((v, Z), Kg ks([IC (y)) -11 + dist diist((y,,))) 2), (-x) (D.2)
23

---

for all (v. Z) E =B((", . (.) Also, as (8*,2* = 0, we have
fD(U, Z) = - (b, + +(Z)
2 - (b, + (-X, + dist (iy (), (-X))
=b(Z*)+ (-X", - - + dist ((y, 2), (0h)) (-XX))
2 2 |8 - 2|| x: x|IC A - - dist ((v 2), Sp)
K3
= =fD("',2 -² - (IXI + x|IC - -y - -IIIIC (v) - + dist 2 ((y, 2), 2p)
2 fo(y", .-' - (11111 + 1/IC - (v) 2 + K3
dist ((y LD))
where the first inequality uses the growth property h, the second equality rewrites (b, v) (X*,A" (y)) and Z = C (w"). and the last inequality uses the fact that (v. 2) is in a bounded set B(()",( 2, 11) so there exists a 7 2 0 such that x=|CC - AA - Z11 S
D.2 Illustration of quadratic growth
In this subsection, (9). In particular, we choose the exact penalty formulation for dual SDP (5) (the proof for the exact penalty function can be found in Appendix [B.. Moreover, the following example shows that even simple 2 x 2 SDP can not have sharp growth in the objective function.
simple example to illustrate the quadratic growth property discussed in
Example D.I. Consider a SDP (P) and (D) with the problem data
1
C -1 1
- 1
A1
0
1
1
0
A2
0 0
0
1
and =
1
It can be verified that both primal and dual SDP have a unique solution
1 1
1
1
0
-
-1 1
X*
1
2
0 and Z
Therefore, the optimal cost value is O. Moreover, it also satisfies strict complementarity as rank(X*)
rank ) 11+11 1 = 2 (see Definition (..7). (8b) and (9b) then ensure the following exact penalized
formulation having quadratic growth property
fly == -byy y + pmax Amax (y) - -O)},
where p can be chosen as any number satisfying p >> tr (+*) = 2. Let S = {(0, 0)} be the optimal dual solution and f===
= 0 be the optimal cost value. Figure 2a shows the landscape of the function
I with 4 and verifies that the function value f'y) is growing at least quadratically away from the distance to the solution set S = {{0,, 0)} with the quadratic constant K 0.3. In Figure 2a the yellow area indicates the part where only the linear component of fyy, i.e. bT y. is active while the nonlinear penalty component p pmxx(0 (0, Xmax (A" (y) - C}} is O and the blue region is the part active. The black line in Figure 2a is the boundary where Amax (A* (y) C) = O which can be characterized by the nonlinear equation y1 y) 1/2 0 with y1 < 1. This nonlinear direction also indicates that sharp growth of is impossible. Indeed, let y1 E [0, 1) and y/2
where both the linear and nonlinear components of f(y)
Vi Note that this choice of y satisfiss the nonlinear
-1
equation y1V/2 811 822 and thus only the linear part -Tyy y in f(y is in force. We then have
f(y) f = v1
y2 =
v1
31
y1 y4
V1
On the other hand, the distance to the solution set can be verified
91 B1 1 + (y1 1)2
2/2
dist(y, S) = V
+
(y1
1)2
V1 -
1/
It becomes clear that it is impossible have constant
0 such that
1/1
-
K
< 2/ - = f(y) ft Vy E 10
V1
1
24

---

Pppmmseaaat 03,0]
A D.Da 9)
0.5
0.4
1.5
0.3
0.6
0.2
0.1
.0.5
0.5
-1
-0.5
0.5
(a) 3-dimensional view
(b) Sectional view
Figure 2: The quadratric growth property of the exact penalty function f(y) -b" y+ max(0, Amax (AA (v) C}} where = 4 and f = 0. The optimal solution set {((0, 0) Figure 2a the yellow region represents the linear part where only bb is active, resulting mmax Amax (AA
the blue region encompasses both the linear and the nonlinear parts, and the green surf is the square of the distance the optimal solution set with x = 0.3. Figure[b]shove shoss the sectional view of f along the direction y/3/ V/1 3/2 which can be characterized as the rational function ((n =
C)}
w1-1"
as the quadratic therm vi will dominant when y1 is small, let alone the sharp growth K x- distt(y S) S ff ft) Moreover, the quadratic growth of indicator function formulation -b¹ -byyy y+ (C-A
has also been verified as we only need to consider the linear component -b y. which has already been confirmed in the previous case. Lastly, it is worth pointing out that the sublevel sets of the functions and -b y + 653 (C (y)) are different. Indeed, given a finite value 3 > 0, the sublevel set ty E R² f() S B] contains both parts of yellow and blue regions in Figure 2b In contrast, the sublevel set {y R -b + 659 (C A (1)) S B} only contains the linear part in Figure 2b
E Proofs and supplemental discussions in Section 4
In this section, we complete the missing proof Section and discuss the ALM applied (D) with its corresponding convergence properties. This section is divided into three subsections. Appendix E. completes the proof of Proposition 2 Appendix H2.2
F.nendixE..221i finishes the proof of Theorem Appendix
discusses the ALM applied to (
E.1
Proof of Proposition 2
The proof of Proposition requires a nice characterization of the ordinal dual function and the augmented dual function defined as
gr (w) = inf Lx(XX, w) X E
(E.
where J,, the augmented Lagrangian function 14), recall that we write w (v. 7). Proposition E.1 (338 Theorem 3.2]). Letr >> For all T x S", it holds that
gr (w)
min L,(XX, w) Xes*
max a XS*
go(u)
2r ||u w 1
where go is the dual function
(13
Proposition E.1 not only shows the augmented dual function gr is go with a prior but also shows gr is continuously differentiable. comparison, the ordinary dual function go can highly nonsmooth. We are ready to prove Proposition 2
25

---

Part (a) of Proposition 2 comes directly from the PPM convergence Lemmal 1 as Lemma 4 and the stopping criteria (A') naturally imply the dual iterate Wk++1 satisfies
|w/++1 prox Thr 90 (wk. S Ck
and _x=1 E < DC.
The proof of (b) in Proposition 2 is in fact straightforward. Firstly, by Moreau decomposition 49
Exercise 12.22] and (15c), we have
Fk 1x+x++1- 2 Ig (rx Zk) Hs (Zx rx*x++1 N3 (rx Zk) Zk+1-
Diving both sides by rk. we conclude N (7x+1 7x)/rrx E S Therefore, follows that
1 8 - || - (Xu+1 + (Zx+1 - Zz)/ra)ll = || [1 Z
Secondly, [|A((*+1) x+1+ bll 11ye 3/4+1l//rr comes directly from the update (15b) Lastly, note that
1
Le (X++1, wx) (C, xx+1)
(1104+1112 1/ 113)
25k
On the other hand, we have
min Le wx) = Ira (wx) = go(uu) X
||"= wx 2 go(u") S pp
2rk
where w² is the point that achieves the maximum in Proposition weakly duality. Therefore, we have
E. and the last inequality uses
1 (11ux+11' -|/r== ||wxx/12)
(C, Xk+1) p² S Tir (XK+1, mxk
min Teg (X, wx)
X
2rk
Since the convergence of (wx) is guaranteed in (a), the quantities dist(Xx+1, ST.), ||A(XXX++) bll, and (C, Xx+1) - p¹ also convergence to zero.
Part (c) is direct consequence of part (b) and the fact that Qp is bounded if and only if the
X E S" dist((XS)) ) I n. [|A((X) bll S 72, (C,X) p" S S33 is bounded for any E Rs
23
page 110].
E.2
Proof of Theorem 3
In this subsection, we provide a complete proof of part (a) in Theorem The proof is motivated by
126 Thcorem 1] which focuses on dual SDPs only. To facilitate proof, we first introduce a standard result in proximal mapping that upper bounds the step length of the proximal step by the distance to the optimal solution set, which be found in [42 Proposition by setting We give a simple proof below.
and z' [s(x).
Proposition E.2. Let f R - TR. be convex function. Denote S C R the of minimizers of i.e. S = arginin.eR= f(x). Suppose S + O. Given point x E IR" and a constant >> 0, the proximal mapping holds that
Iproxx.., (2) - x dist(z, S).
Proof. From the optimality condition of proximal mapping, we have
a (proxx,, 2 Iprox,,, x1| fIIs(=)) α [Is(x) x|
2 prooxx, (2) . {()s (prox (x)) [Ts()) x|1
proxx (x) æ|| S dist(x,
which completes the proof.
Using Proposition E.2 and B' we arrive at the following key inequality to show the linear conver- gence of KKT residuals. Proposition 2 It bounds the step length of the dual update by the current distance to the solution set.
Proposition E.3. 126) Lemma 3] Let (Xy, way be the sequence generated by under for all k 2 1 with dg <. 1, holds that
Then
||w++1 - wxll <
dist(wk. Pp)-
1 8z
26

---

Proof. From the triangle inequality and the stopping criterion
B
we have
|1++11 will -
||00 prox - (w*) S
|10++1
prox r.. (wx)ll S 6x w - wxll-
Rearranging terms and using Proposition
E.2 yields
(1 5x [ wxll S |w prox (wa)l S dist(wk, StD).
This completes the proof.
L
We are ready to start the proof of part (a) here. As dual strict complementary holds, the negative
of the dual function [13 i.e., -o. satisfies quadratic growth (9b). Using Lemma and and stopping
criteria (B"). we have | prox (w*)]l S 6& W++1 wk
Therefore, the linear reduction
on dist (w, SD) comes directly from the PPM convergence Lemma for all k 2 ki, it holds that
i.c. there exists kj such that
dist(wa+1. QD) S p Sp), Pk 0g + 20g
1, 0% V2rk/u +1
< 1.
We move to show the bound for residuals dist X 84), [|A((*+1) - bl1, and (C,x)+1) p". Specifically, when dy < holds that
Z Zu+ill
[ukk wk+il
1 dist (wk, StD);
(X 87)
3
S
rk
Tk
(1 dR)rk
lik yk+1l ||
| Wk+1ll
|A(x++1) bll
<
dist(wk: Sp),
Tk
Fk
(1 8x Tk
where we use part (b) in Proposition 2
11 yk+1l || S | - wk++ ||.
1| Zk+1l S |wws - wk+1ll.
and Proposition E.3 Again, using part (b) in Propositions 2 and
E.3 when 8x 1, we have
0 11111111 wk 112 || ||w++1l
(C, Xk+1) - p¹ s
2rk
02 11144 wx112 + (11 ||
||
([ | II)
2rk
11k+1 wall + (1lexl || + || -wx+11))
2rk
wkll + ||wk|l + | dist(wx, Sp).
2rx 5%)
Since dg - O, there exists a h2 such that 6g < 1 for all l 2 12. Taking & = max{fax k2) completes the proof for part (a) with the constants
1
- 1//00 1
5k)rk
p 11|wh+11 - wxll + +1lwwll + ||0+1ll
|| Noo
1%
2r Ōk)
We move on to part (b). By Theorem 2 we know that the error bound (b))
holds as dual strict
complementary holds, i.e., for any bounded set S S containing any X Ωr, there exist constants 01, Q22 Or > O such that
X) - X*) + on [|A(X) bll + 02 - dist(XX x, 2 ag dist d (x,
AA E u. (E.2)
From the assumption that Up is bounded, Proposition 2 confirms that the sequence { (X is bounded. Thus, we can choose a bounded set l4 2 Sp Uuzz! {x Combing (E2) with (16), we have
03 dist? (Xe+1, Up) < (44 + (01 az)p%) dist(wk, Up)
Dividing both sides by as leads to the desired result in part (b). This completes the proof.
27

---

E.3 ALMs for dual conic program (D)
In aiming offer a comprehensive understanding of ALMs for solving (P) and (D). this subsection,
we provide the algorithm of ALM applied to solving the dual problem (D) along with the convergence analysis. This can be considered as an extension of the work [26] and a counterpart the ALM
for solving (P) discussed in Section
We first reformulate (D) the equivalent minimization problem
d"
min vER 2es
(-b, y)
subject to C Cy)
We then introduce dual variable X 8t and define the ordinary Lagrangian function Lo X) (b, v) + (X, C - (v)). The corresponding dual function and dual problem become
go (x) inf Lo X) and max EB
9o (X).
(E.3)
*
Then, the augmented Lagrangian with parameter
0, analogous to (1). is
(y, X) = (-b, v)
(1) (X - r(C - (-))- 1|
2r
Given an initial point Xu E S" and a sequence of positive scalars Tk f Too, the ALM generates a sequence of {yk} and {X&} following
gk++1 2 argmin Lyx Xx) yERm
(E.4a)
X Xx rh v V (3R+1, Xa)
1ss - (()++)))),,,
k= 0, I,....... (E.4b)
Many of the same properties discussed in Section Jhold. We will provide the precise statement in the remainder this section. Similarly, we can consider the analogous stopping criteria (A' and B')
Log (J1+1, Xx) min Lig (v, Xx) S <f/((2r)) VERm
ΣE= Ex < 0C,
(A))
Lrg (11+1, XB+1)
min Lrg Xx) - Σk=1 8n < <0.
(B'))
BERm
Proposition E.4. Consider and D Assume strong duality holds and Spp + 0. Let {yk Xx) be sequence from the ALM E.4) under and write Zμ C (yxx for all k 2 0. The following statements hold.
(a) The dual sequence X₃ is bounded. Further, limg-+oo Xx X Sp (i.e., the whole sequence converges to a primal optimal solution).
(b) The dual feasibility and cost value gap satisfy
dist (7,41,, S | - Xxt1ll/re - O,
d' - (b, & Trr, (Jk+1, Xx) min I., (v. Xx) + -|[x/|=-||x++1 (1))2r1))((2r)) + 0. yERm
(c) If the solution set Up in (bb is nonempty and bounded, then the primal sequence yk is also bounded, and all of its cluster points belongs to Ωp.
Proof. The proof of many of these statements a change of the notations in the proof Proposition 2
Part (a) comes directly from the PPM convergence by noting Lemma and the stopping criterion
(Ap) imply the dual iterate X satisfies [| prox,,, (Xx) S ck.
By the Moreau decomposition 49 Exercise 12.22], we have
Th Z X = Ng (rx Za+1
Xx) 1gg (Xx- Th Z=+ = Ng (rx Xx+1 Za) Xx+11-
Thus, Zu+1 + X sp. Therefore.
76
(ist(Zx+1,$)) S Zu+1 1x+1 + X4+1 Xx ) = ||x+11 - Xxll
28

---

From the definition of the augmented Lagrangian function, we have
Lr (y Xx) = (-b, yk+1) + 2r
(1|X++1l1 -1|x|l1))
On the other hand, we know
1 - X S 90(U*)) -d",
min Lr, (U. Xx) 90 90(U*) yER
2rk
where U denoted as the point that achieves the maximum in the identity 38 Theorem 3.2]
min Lyg (y, = max X (x(
| -
112
yERm
2rx
and the last inequality comes from the definition of the dual problem
E.3 Thus,
1
d' - (b, Mk+11) S Le (yK+1, Xx) min Lrg (u, *ERRT
x|| |xx
2r
Part (c) is consequence of part (b) and the fact that Up is bounded if and only if the set ((y, 2) E R. x S" d² (b. y) S Yi, dist,,, 84) S 72, ||C (r) - 2 S na) is bounded for any 7 E R3 23
page 110].
Theorem E.1 (Linear convergences). Consider primal and dual SDPs ( and (D) Assume strong
duality and strict complementarity holds (implying Qp + and Up 7 (). Let {u) be
sequence from the ALM (E.4) under (Ap) and BBp and write Z₁ C (yk) for all l 2 0. The following statements hold.
(a) There exists constants
1: 0, < Ma < and p/s p4 > 0 such that for all k: 2 k
dist (i s2p) I Pk dist(Xx. Stp), dist Zz= 1: S4) S 14 (iis((x,, Stp), d= (b, yk+1) S pk dist((x, Stp).
(E.5)
(b) IfSp is bounded, then the primal sequence {yk} also converges linearly to SD, i.e., there is constant is 2 0 such that for all k: 2 k
dist? dist? Rp) I Th
Proof. Similar to Proposition
E.3 if is used, we have
[|x++1 Xx S 1
8k (Xist(X,,90
Vog <
(E.6)
Therefore, there exists a k > 0 such that vk 2 R 62 < and
dist ( S4 X - Xxll
1
dist (X Sp),
Fx(1 5x)
where the first inequality uses part (b). Then, once again using (E.6) and part (b), we have
0 XK+1
1 + | 2 ||
d' (b.
2rk
52 X
xx112 + X1Il - 1all--xx |X++1)((X+ + ||
2rk
| xx + (1lXx (x+1Il) + 1|)++
2r
X k+1 X
1+||| ||xx|
||
(Xx,1,111,
2r
5x)
If strict complementarity holds, Theorem [ (with g in (5) as an indicator function) guarantees that 9o in E.3 satisfies quadratic growth in (9b). Thus, the línear convergence of dist(XX, 2p. comes
from the PPM convergence Lemma] [ i.c., there exists A such that for all & > k, it holds that
02 + 28
dist(Xx+1. s2p) S Madist(Xa,,n Pp), Mh
1, Og /2rkHg+1
< 1.
8k
29

---

Since 69 - 0, there exists hy such that 65 < 1 for all & 2 l2. Taking max k completes the proof for part (a) with the constants
u rh 0k) + M/20 Toc
14 Xx+11 - Xx ||xxll + |[
X
2r 6k)
On the other hand, Theorem also guarantees that the error bound (bb) holds, i.c., for any bounded set V 2 LDD there exist constants a1, 02, 0g > such that
d' +a (a1 -I - 1iitta--is(224 (iitt(Z,35) 2 ag dist ((v, Rp), v(y. Z) V. (E.7)
By the design of (E.4), we always have ||C - A" (31+) Z 0. By Proposition E.4 part (c), the sequence {yk, Zx. is bounded. Thus, choosing a bounded set V 2 Pp U (vk. Z&} and
combing (E.7 with (E.5p we have
0g diitt (1++1, (1% + 0214) dist S2p), vk 1226 k.
Dividing both sides by ag leads to the desired result. This completes the proof.
Details of the numerical experiments
In Section 5
consider the classical SDP relaxation of the Mac-Cut problem and the linear SVM. In this section, along with another popular signal processing problem Lasso, we detail the problem formulation and report the numerical performance of ALM applied to those problems.
The SDP relaxation of Max-Cut:
min Xes
(C, X)
subject to
Diag(X) =
X S
where C' E S" the problem data representing a weighted undirected graph, 1 E TR" is an all one
vector, and Diag(X) = [X11. .Xmm]' This type of problem has been shown to satisfy
strict complementarity and has unique primal and dual solutions for almost all data matrix 41 Corollary 2.3].
Linear SVM:
min ZE24
max b4
b;(a.x)) x)}
|
where a, TR" is the feature of the i-th data point, E (-1,1} is the corresponding label, and A >> O is constant. Equivalently, the problem can reformulated in the following standard conic form
min ZERo
| + +
2
subject to Diag(b) Ar 1 1,
0 1
where = (a,.... 0m E mxn and Diag(b) E mm denotes the diagonal matrix with the diagonal elements being Lasso:
min ZER"
2 11 - b11 A||2|11-
where A 1 Rm are problem data and À 0 is the weighted parameter balancing the sparsity the solution and the accuracy of the linear solution. Equivalently, the problem can be rewritten in the conic form
min *ER"
2 |lyl2 + A
subject to
Ar y,
t < x St. t.
30

---

Primal east value gap
Dual cost value gap
KKT Residuals
10P
10"
10
4
10
10%
10
10-33
10 10
15
Iteration
Iteration
Iteration
Max-Cula - Maxe-Cute -
Max- Cut-3
Primal value gap
Dual gap
Residuals
10F
100
10-1
e
10
0000
10
10-11
pood
10 Iteration
20
10
20
5
15
Iteration
Iteration
1010
Figure 3: Nuremical experiments for Max-Cut with different instances and various augmented Lagrangian
parameter r > O.
All numerical experiments are conducted on PC with 12-core Intel i7-12700K CPU@3.6IGH2 and 32GB RAM. For Max-Cut problem, we select the graph G1, G2, and G3 from the website https://web stanford. wwtpeyyyeeaaee/eeeaeaaeeaaeaeeae weweeeyyyeGGGseeee and only take the first 20 20 submatrix as the considered problem data C. For both the linear SVM and Lasso, we randomly generate the problem data with the dimension = 100 and 10, and set the constant X = 1. We use Mosek [56] to get the optimal cost value. In each application, we consider the following two scenarios 1) fixing the same augmented parameter r& for all & for three different problem instances; 2) fixing a problem instance and varying different augmented parameter r. The numerical results are presented in Figures 3 to For each Figures to the first shows the evolution of the primal cost gap, dual cost gap, and KKT residuals for three different instances with a fixed augmented parameter (scenario one), and the second parameter (scenario two). In the setting of a fixed augmented parameter, the augmented term is set as 5, 20 for Max-Cut, linear SVM, and Lasso respectively. the setting of various augmented parameters, the parameter is chosen as r = {1, 5, 10), r = {1,5, 10}, and r {10, 20, 30} for Max-Cut, linear SVM, and Lasso respectively.
compares the different numerical behaviors when varying the augmented
We observe that, in all cases, ALM enjoys linear convergence in the primal cost value gap, dual cost value gap, and KKT residuals to the aceuracy of at least 10 which is consistent with our theoretical findings in Theorem 3 We believe the oscillated or flattening behavior that appears in the tail (when the iterates close the solution set) is due the inaccuracy of the subproblem solver and computational errors. The numerical result also indicates that when the augmented term r increases, ALM favors the decrease of the feasibility more, leading faster convergence in the beginning phase. However, a large may not lead to the best convergence in the long term.
Note that the projection term ||I| (Z- rx) in the subproblem (15a) can not be directly modeled by Yalmip. Therefore, reformulate the problem as the following
argmin (C,X) X
(lly + (
A(x)) [g (Z - xxx
|///| 2 11/2-1101 1
2r
1
argmin (C, + (1ly ru(6 ((00-((())) 11 (rrX -)]1²)
X
1
argmin (C, X) + 2r XE
(1lu+
ra -(0)) - 2 - -U11))
ru
31

---

where the first equality drops two independent terms and uses -s7 = S and |[ss (Y)
- 11 [ [ for all Y E S", and the last equality uses minyres || - Ui y Mgs (Y)l = || (Y)ll for all Y S".
Primol value gAg
Dual gAp
KKT Residuaals
10
10"
10
10-1
10-t
10
10
10
10
15
20
10
15
20
5
10 Iteration
15
20
Iteration
Iteration
SVM-1
SVM-2
SVM-3
Primaal cast value
Dual cost, value
KKT Residuals
10
10a
10:2
10
10
10
10
10
10-
10 Iteration
20
20
5
15
Iteration
Iteration
10
Figure 4: Nuremical experiments for linear SVM with different instances and various augmented Lagrangian parameter > O.
Primual yay
Duxl gap
Residuals
100
10-
7000000000000
10-5
10
10-13
10
15
20
10
15
20
5
10
15
20
Iseration
Iteration
Iteration
LASSO-1
LASSO
Primul cast. value
Dual coss, value
KKT Residuals
100
100
10
10-2
10
10-18
10-41
10 Beration
20
20
5
15
Iteration
Iteration
Figure S: Nuremical experiments for Lasso with different instances and various augmented Lagrangian parameter
> 0.
32

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We have clearly and accurately stated the contributions and scope of this paper in the abstract and introduction. We have also made proper assumptions and presented clear comparison with results in the existing literature.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: have clearly stated the assumptions on conic optimization order to guarantee the quadratic growth properties and the linear convergence of inexact ALM.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
33

---

Answer: [Yes]
Justification: All the theorems, formulas, and proofs in the paper are numbered and cross- referenced. We have provided completed proofs for all theorems/lemmas. In the main text, a proof sketch is provided, and the details can be found in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided a separated section in the supplementary material for experimental details.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
34

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We plan to make all code open access after the review period.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
desceeuuus///ooeuubbiiii 7/nips cc/ wtc/ppbliic// subbbic/guides gww.///ieee//eee// Codeeoomiiieeeee SanSSuubissss issionn ssionnoiccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have separate section in the supplementary materials for experimental setting.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided the type of computer and memory for reproducing our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics huttps://neurs htt.a//ggg/////.rrr.....cooooo/a
Answer: [Yes]
Justification:
We have followed closely the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:[Yer Yes]
Justification: We have discussed the positive societal impacts from efficient algorithms to solve conic optimization. We do see negative societal impacts of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
36

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
37

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "Ny9mkiPPM5", "reviewer": "Reviewer_K87V", "summary": "The paper addresses the convergence of primal and dual iterates in Augmented Lagrangian Methods (ALMs) for conic optimization, particularly under quadratic growth assumptions. The authors establish that both primal and dual iterates of ALMs demonstrate linear convergence solely based on the strict complementarity assumption and a bounded solution set. This addresses a significant gap in the literature concerning the linear convergence of primal iterates, providing a theoretical foundation that has been previously unresolved.", "questions": "Theorem 3 Proof: Can the authors provide a detailed proof of Theorem 3 within the main text or an enhanced appendix to help readers understand its foundational role in the paper's theoretical framework? \n\nNumerical Experiments: Could the authors expand on the range and depth of the numerical experiments presented? Specifically, how do the proposed methods perform under varying conditions and parameter settings?", "limitations": "The paper does not explicitly discuss the limitations or potential negative societal impacts of the research, which is a critical component of scholarly communication.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper attempts to establish the conditions under which both primal and dual iterates of Augmented Lagrangian Methods (ALMs) for conic optimization exhibit linear convergence.\n\nClarity: The paper is well-structured and written with a clear narrative that guides the reader through the complex theoretical developments. Definitions, theorems, and proofs are delineated, making the complex content accessible to readers unfamiliar with the subject area. \n\nSignificance: The findings have potential implications for both the theoretical and practical aspects of optimization.", "weaknesses": "Presentation of Key Contributions: One significant issue with the paper is the placement and treatment of one of its key contributions, Theorem 3, which appears towards the very end of the document. This theorem, which is central to the paper's claims and theoretical framework, is not proven within the main text, and the appendix provided does not sufficiently validate or elaborate on it. This placement and lack of rigorous proof within the main discourse may detract from the impact of the contribution, as it might be overlooked or undervalued by readers. To improve, the authors could consider integrating Theorem 3 more prominently within the main discussion and ensuring that a complete and accessible proof is included either in the main text or more comprehensively in the appendix.\n\nNumerical Validation: Another area where the paper falls short is in its numerical section. The section dedicated to numerical validation of the theoretical results is very brief and lacks depth/sufficient validation through several diverse problems. A more extensive set of numerical experiments is crucial to demonstrate the practical effectiveness and robustness of the proposed methods under varied conditions. The current numerical validation does not sufficiently cover the scope of the potential applications discussed in the paper. Readers are referred to Appendix H, where additional testing is still missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors are very thankful to the reviewer for taking the time and effort to review our manuscript. We sincerely appreciate all your valuable comments. All your comments are carefully addressed below.\n\nWe have provided [some general responses](https://openreview.net/forum?id=Sj8G020ADl&noteId=WyA13MOOMr) in the Author Rebuttal by Authors above to two of your major concerns: 1) Presentation of Key Contributions; 2) Numerical Validation. In the following, we provide more specific responses to your comments on Theorem 3 Proof and Numerical Experiments. \n\n> **Theorem 3 Proof: Can the authors provide a detailed proof of Theorem 3 within the main text or an enhanced appendix to help readers understand its foundational role in the paper's theoretical framework?**\n\nThanks for your nice suggestion. We will revise the introduction and incorporate further discussions about Theorem 3. Currently, Theorem 3 has two parts (“Dual iterates and KKT residuals” and “Primal iterates”). The first part “Dual iterates and KKT residuals” can be considered a primal version of [27, Theorem 1]. Due to the page limit, we provide the proof for the first part in Appendix E.2. The second part “Primal iterates” is one of our main contributions, and the proof relies on the error bound property for the primal conic problem established in Theorem 1 - (7b). In the updated version, we will highlight the key steps of the proof in the main text and provide a comprehensive and self-contained proof in the appendix. \n\nMoreover, we would like to point out that we have two main contributions to this work \n\n-  **Problem Structures:** We establish new quadratic growth and error bound properties for primal and dual conic programs (Theorem 1 and Theorem 2).\n- **Algorithm Analysis:** Utilizing our error bound properties, we prove that both primal and dual iterates of the ALMs converge linearly under mild assumptions (Theorem 3).\n\nThus, Theorem 3 represents only one of the main theoretical contributions. The quadratic growth properties in Theorems 1 and 2 are equally important, and their proofs may be of independent interest (as noted in Remark 1 of the manuscript). The lack of presentation of Theorem 3 in the main content may be due to the page limit. To enhance the readability of the paper and better present Theorem 3,  we will follow the reviewers' suggestions and focus on the general problem class—SDP—in the main manuscript. This will not only improve clarity but also give us more space to ensure that Theorem 3 is well-integrated into the main discussion.\n\n[27] Ying Cui, Defeng Sun, and Kim-Chuan Toh. On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming. Mathematical Programming, 178:381–415, 2019.\n\n> **Numerical Experiments: Could the authors expand on the range and depth of the numerical experiments presented? Specifically, how do the proposed methods perform under varying conditions and parameter settings?**\n\nThank you for this suggestion. We have added more numerical experiments in the attached PDF file under the section of Auther rebuttal, and the results also support our theoretical contributions. \n\nIn particular, we consider two classical machine learning applications: linear SVM and Lasso. Both the linear SVM and Lasso can be reformulated as standard conic programs with free, nonnegative, and second-order cone variables. For each application, we randomly generate three instances and run ALM for those three instances with various augmented penalty parameters $\\rho>0$. The numerical results show that the three quantities (primal cost value gap, dual cost value gap, and the KKT residuals) all converge to zero with a linear rate. The convergence speed of the primal feasibility and conic constraints also depends on the value of the penalty parameter $\\rho$. The larger the penalty parameter $\\rho$, the faster the convergence of the residuals. The oscillated or flattening behavior that happens in the tail (when the iterates are close to the solution set) is due to the inaccuracy of the subproblem solver and computational errors. \n\nOne key difference between the experiments on semidefinite programs (SDP) and the added experiments is the report of primal solution quality. In the considered SDP applications, “the SDP relaxation of maximum cut (Max-Cut) problem” and “the SDP relaxation of matrix completion” have been shown to have a unique primal solution with high probability [43]. Therefore, we can report the primal distance for SDP applications. On the contrary, the uniqueness of the primal solution for linear SVM and Lasso is not guaranteed, so we report the primal cost value gap instead.  \n\n[43] Lijun Ding and Madeleine Udell. On the simplicity and conditioning of low rank semidefinite programs. SIAM Journal on Optimization, 31(4):2614–2637, 2021.\n\n> **Limitations: The paper does not explicitly discuss the limitations or potential negative societal impacts of the research, which is a critical component of scholarly communication.**\n\nThanks for pointing out this issue in our writing. Our paper focuses on theoretical analysis of the structures of conic programs and linear convergence of ALM. We do not expect negative societal impacts in these aspects. \n\nRegarding limitations, our paper first establishes the growth property and error bound for three commonly used self-dual cones. Building upon the established growth property and error bound, our paper established the convergence rate of the primal iterates. The current theoretical guarantees do not apply to other cones. It will be interesting to see how to use the current proof techniques to establish the growth property and error bound for other non-symmetric cones. In addition, as solving the subproblem is the main step in the ALM, it will be interesting to develop an efficient subproblem tailored to the problem structures, such as sparsity or manifold structure.", "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": "hGJYrVsyPt", "reviewer": "Reviewer_Vd1D", "summary": "This paper develops Inexact Augmented Lagrangian methods (ALM) for conic optimization problems with focus on Linear Programming (LP) or the non-negative orthant cone, Second-Order Cone (SOCP) problems and Semidefinite programming (SDP) given a linear objective. Under assumptions of strict complementarity and strong duality, the authors show local linear convergence for these problems by first showing quadratic growth property within a compact subset around the optimal solution for both the primal and dual programs and then leveraging the well-established concept that running ALM for the primal is equivalent to running Proximal Point Method (PPM) for the dual. The experiments show linear convergence for the SDP relaxation for the MaxCut problem, the SDP relaxation for matrix completion, and the moment relaxation of binary quadratic program (BQP) given the following metrics: primal distance, dual cost gap and the KKT-based residuals.", "questions": "1. Why were LPs and SOCPs not evaluated as part of the experimental evaluation but discussed in the theoretical sections and appendix?\n2. Have you considered showing the local linear convergence given different random starting points for Inexact ALM? \n3. Did you use inexact evaluation of the subproblem in Equation (15a)?\n4. Have you considered showing the local linear convergence given different error tolerance schedules for $\\epsilon_k$ and $\\delta_k$ for all k?\n5. Have you considered choosing the $\\mathcal{A}$ operator to hold non-convex constraints in the experimental evaluation? The MaxCut SDP and Matrix Completion SDP both have linear constraints and the BQM has a convex constraint of $x_i^2 = 1$ but your guarantees only only assume that $\\mathcal{A}$ is surjective.", "limitations": "There were no discussions of limitations in the work or adequate discussion of future directions of work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The biggest strength of the paper is the theoretical contribution to understanding of local linear convergence of inexact ALM methods for a variety of conic problems. Previous works have only shown local linear convergence of dual iterates but this work shows local  linear convergence for both primal and dual iterates. The authors provide a thorough theoretical discussion and provide all the proofs in the appendix section.", "weaknesses": "One weakness of the paper is the lack of characterization of how inexact evaluation of the proximal operator affects convergence. The authors use the property of linear convergence for Proximal Point Method (PPM) given inexact evaluation of proximal operator and quadratic growth assumption to show similar linear convergence for Inexact ALMs but there are no guarantees based on chosen error tolerance schedule (i.e. choice of $\\epsilon_k$ and $\\delta_k$ for all k). Another weakness of the paper is the lack of experimental evaluation of conic problems other than SDPs. The work shows theoretical guarantees of local linear convergence under strict complementarity and strong duality for three different types of conic problems: LPs, SOCPs and SDPs but experimental evaluation of LPs and SOCPs are lacking. It maybe because SDPs are a more general class than LPs or SOCPs but it would be good to have a variety of experiments that cover both convex/non-convex constraints as well as different LPs and SOCPs in addition to SDPs. There is also a lack of experimental evaluation to claim that there is local linear convergence given inexact evaluations of the subproblem in Equation (15a).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in evaluating our manuscript. Your comments helped further improve the quality of our work. We provide detailed responses below\n\n> **Lack of characterization of how inexact evaluation of the proximal operator affects convergence.**\n\nThanks for the valuable comment. It will be interesting to see how the inexactness ($\\epsilon_k$ and $\\delta_k$) propagates to the guarantee on the primal cost value gap, affine feasibility, and conic feasibility, similar to the work [1]. Our analysis considers the ALM as the dual side of the Proximal Point Method (PPM). Despite the lack of an analysis of the error propagation, the analysis based on PPM is simpler and more intuitive. We will incorporate the discussion on this part into the updated version of our paper.\n\n[1] Xu, Yangyang. \"Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming.\" Mathematical Programming 185 (2021): 199-244.\n\n>**Lack of experimental evaluation of conic problems other than SDPs.**\n\nMotivated by this comment, we have added more numerical experiments other than SDPs in the attached PDF file under the section of Auther rebuttal, l. The results also support our theoretical contributions.\n\nIn particular, we consider two classical ML applications: linear SVM and Lasso. Both the linear SVM and Lasso can be reformulated as standard QP or SOCP. For each application, we randomly generate three instances and run ALM for those three instances with various augmented penalty parameters $\\rho>0$. The numerical results show that the three quantities (primal cost value gap, dual cost value gap, and the KKT residuals) all converge to zero with a linear rate. The convergence speed of the primal feasibility and conic constraints also depends on the value of the penalty parameter $\\rho$. The larger the penalty parameter, the faster the convergence of the feasibilities. We believe the oscillated or flattening behavior that happened in the tail (when the iterates are close to the solution set) is due to the inaccuracy of the subproblem solver and computational errors. \n\n[43] Ding and udell. On the simplicity and conditioning of low rank semidefinite programs. SIAM Journal on Optimization, 31(4):2614–2637, 2021.\n\n>**Lack of experimental evaluation to claim that there is local linear convergence given inexact evaluations of the subproblem**\n\nThe linear convergence does happen under the inexactness (see conditions A' and B’ in the paper). This has been empirically verified in  SDPNAL+ [20]. Instead of directly dealing with the non-implementable conditions A’ and B’ (as A’ and B’ require the knowledge of the true cost value), they propose other alternative and implementable conditions and incorporate them into their subproblem solver.  \n\nAs our main focus is to establish the theoretical convergence guarantee for the primal iterates, we use the package YALMIP to formulate the subproblem and call MOSEK to solve the subproblem. It IS difficult to control the subproblem solution quality using a third-party package (MOSEK), as the subproblem is also solved to $\\epsilon$-accurately by the conic solver. This is also revealed in our additional numerical experiments in the attached PDF. Specifically, the numerical experiments show some flattening behaviours in the tail when the iterates are close to the optimal solution set. We believe this is due to the computational error and the inexact subproblem solution.\n\n[20] Liuqin Yang, et al. Sdpnal+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Computation, 331–366, 2015.\n\n>**Have you considered showing the local linear convergence given different random starting points for Inexact ALM?**\n\nThroughout our numerical experiments, different random starting points all lead to the same convergence behavior as guaranteed by our theoretical result Theorem 3 which works for any initial points. \n\n>**Did you use inexact evaluation of the subproblem in Eq. (15a)?**\n\nWe use the package YALMIP to formulate the subproblem and call the conic solver MOSEK to solve the subproblem. Therefore, the subproblem is solved to $\\epsilon$-accuracy by the conic solver. Note that we can not guarantee the $\\epsilon$ goes to zero as the ALM proceeds.\n\n>**Have you considered showing the local linear convergence given different error tolerance schedules for $\\epsilon_k$ and $\\delta_k$ for all $k$?**\n\nWe did not investigate this part, as our main focus is the theoretical guarantee. We believe this will be more important in the algorithm development for solving the subproblem.\n\n>**Have you considered choosing the operator $\\mathcal{A}$ to hold non-convex constraints in the experimental evaluation? The BQM has a convex constraint of $𝑥_𝑖^2=1$ but your guarantees only assume that $\\mathcal{A}$ is surjective.**\n\nWe did not solve the nonconvex BQM directly. Instead, we apply the moment relaxation with degree two to turn the nonconvex BQM into an SDP relaxation [61], and then solve the resulting SDP. \n\n[61] Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM  Journal on optimization, 11(3):796–817, 2001.\n\n>**Limitations**\n\nThanks for pointing out this issue in our writing. Our paper first establishes the growth property and error bound for three commonly used self-dual cones. Building upon the established growth property and error bound, our paper established the convergence rate of the primal iterates. The current theoretical guarantees do not apply to other cones. It will be interesting to see how to use the current proof techniques to establish the growth property and error bound for other non-symmetric cones. In addition, as solving the subproblem is the main step in the ALM, it will be interesting to develop an efficient subproblem tailored to the problem structures, such as sparsity or manifold structure.", "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": "sBBWATjsiT", "reviewer": "Reviewer_X2mJ", "summary": "The paper presents the convergence rate of the primal iterates of the augmented Lagrangian Methods (ALMs) which are widely employed in solving constrained optimizations. The authors develop new quadratic growth and error bound properties for primal and dual conic programs under the standard strict complementarity condition and then reveal that both primal and dual iterates of the ALMs converge linearly contingent upon the assumption of strict complementarity and a bounded solution set. The specific contributions include:\n1. Under the standard strict complementarity assumption, the quadratic growth and error bound for both primal and dual conic programs (P) and (D) over any compact set containing an optimal solution (see Theorems 1 and 2) are established.  \n2. A new characterization of the preimage of the subdifferential of the exact penalty functions is unveiled. \n3. They provide new and simple proof for the growth properties in the exact penalty functions and clarify some subtle differences in constructing exact penalty functions.\n4. They show the linear convergence for both the primal and dual iterates of  ALM to solve either the primal or dual conic programs.", "questions": "1. Lines 184-185: If the linear constraints $\\mathcal{A}(x)=b$ is empty, how to define the exact penalty function?\n2. Line 226: Why is there $\\mathbb{F}\\times \\mathbb{E}$ instead of $\\mathbb{F}$?\n3. Please consider citing the paper \"Rockafellar, R.T. Convergence of Augmented Lagrangian Methods in Extensions Beyond Nonlinear Programming. Math. Program. 199, 375–420 (2023). https://doi.org/10.1007/s10107-022-01832-5,\" and compare it with your work.\n\nTypos:\n1. Line 238: Should (8b) be replaced by (8a)?\n2. The notation $\\mathbb{R}^n$ should be changed to $\\mathbb{R}_{+}^n$.", "limitations": "NA", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Originality: The paper introduces novel quadratic growth and error bound properties for primal and dual conic programs, addressing long-standing challenges in the field. The development of symmetric inexact ALMs for primal and dual problems is a creative extension of existing methods.\n\nQuality: The paper is of high quality, featuring a robust theoretical framework and rigorous mathematical proofs.\n\nClarity: The paper is clearly written and well-organized.\n\nSignificance: By addressing open questions and providing new theoretical insights, the work could influence future research.", "weaknesses": "1. The authors claim in Remark 1 that the results in Theorems 1 and 2 are more general and unified compared with known results since they allow for any compact set $\\mathcal{U}$. However, let $\\mathcal{U}=\\mathcal{U}_1\\cap \\mathcal{U}_2$ where $\\mathcal{U}_1$ and $\\mathcal{U}_2$  are compact, and there is not any optimal solution in $\\mathcal{U}_1$. If it is known that the error bound is constrained with a pair $\\gamma, \\kappa$ for $x\\in\\mathcal{U}_2$. For $x\\in\\mathcal{U}_1$, it is natural to get a $\\kappa$ through the minimizatin of the fraction $$\\frac{f(x)-p^*+\\gamma\\|\\mathcal{A}(x)-b\\|}{dist^p(x,\\Omega)}$$ since $\\mathcal{U}_1$ is compact and $dist^p(x,\\Omega)>0$. We can just take the minimizer of two $\\kappa$(s). The advantages of this error bound form in this paper is doubtable.\n2. Aftrer Definition 2, the authors claim that the notion of strict complementarity is not restrictive, and it holds generically for conic programs. After that,  the authors also presented: that it has been revealed that many structured SDPs from practical applications also satisfy strict complementarity. There are contradictions and misunderstandings in these two assertions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in evaluating our manuscript. Your comments helped further improve the quality of our work. We provide detailed responses below.\n\n> **The authors claim in Remark 1 that the results in Theorems 1 and 2 are more general and unified compared with known results since they allow for any compact set $\\mathcal{U}$**\n\nThanks for this insightful comment. However, the error bound is usually more informative when a point is close to the solution set, as it characterizes the relationship between the distance to the complex solution set and the computable residuals. Ideally, a useful error bound should always be defined on a region containing an optimal solution so that when the computable residuals go to zero, we can deduce the distance to the solution is also zero. Our result for any compact set $\\mathcal{U}$ containing an optimal solution is particularly useful in estimating the iteration number for local convergence. For example, suppose we have an algorithm that has a sublinear convergence rate of $\\mathcal{O}(1/\\epsilon)$ for any convex functions and linear convergence $\\mathcal{O}(\\log(1/\\epsilon))$ for convex functions satisfying quadratic growth. Given the optimization problem, $\\min_x f(x)$ with $f$ being convex and satisfying quadratic growth in the sublevel set $f_\\nu = \\\\{ x \\mid f(x) \\leq \\min_x f(x)   + \\nu \\\\} $  with $\\nu > 0$. In this case, one can infer the number of iterations that guarantee the iterate to reach the sublevel set $f_\\nu$ using the $\\mathcal{O}(1/\\epsilon)$ convergence rate and claim the local linear convergence after iterates are within $f_\\nu$.\n\n> **Aftrer Definition 2, the authors claim that the notion of strict complementarity is not restrictive, and it holds generically for conic programs. After that, the authors also presented: that it has been revealed that many structured SDPs from practical applications also satisfy strict complementarity. There are contradictions and misunderstandings in these two assertions.**\n\nThanks for pointing out our contradicting statements. We will rewrite the paragraph to avoid misunderstandings in our updated version. For the statement regarding the generic property of conic programs, we mean that strict complementarity holds for almost all (in the sense of the Lebesgue measure) linear conic problems. For the statement regarding the structured SDPs, we mean that strict complementarity has been shown to hold for almost all SDPs with a specific structure, such as SDP relaxation of Max-cut and Matrix completion.\n\n> **Lines 184-185: If the linear constraints $\\mathcal{A}(x) = b$ is empty, how to define the exact penalty function?**\n\nThanks for this nice question. If the linear constraint $\\mathcal{A}(x) = b$ is empty, then any penalty parameter will work for the penalty function for the conic constraint as the problem is infeasible.\n\n> **Line 226: Why is there $\\mathbb{F} \\times \\mathbb{E}$ instead of \\mathbb{F}?**\n\nHere, we follow our definition of the optimal solution set (1b). We write the dual solution set into the two spaces, so, in Line 226, $\\mathbb{F}$ denotes the space where $y$ lives, and $\\mathbb{E}$ denotes the space where $c-\\mathcal{A}^*(y)$ lives. \n\n> **Please consider citing the paper \"Rockafellar, R.T. Convergence of Augmented Lagrangian Methods in Extensions Beyond Nonlinear Programming. Math. Program. 199, 375–420 (2023). https://doi.org/10.1007/s10107-022-01832-5,\" and compare it with your work.**\n\nThis paper discusses a more general setting of ALM, including nonconvex problems and convergence to a local minimum. However, as their setting is more general, the linear convergence of the primal variables also requires a strong assumption about the uniqueness of the primal and dual solutions.\n\n> **Typo: Line 238: Should (8b) be replaced by (8a)?**\n\nThank you. This is a typo. It should be replaced by (8a).\n\n> **Typo: The notation $\\mathbb{R}^n$ should be changed to $\\mathbb{R}^n_+$.**\n\nWe will double-check our paper and fix the typo. Thanks for your careful reading of our work.", "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": "39ry1tJaYc", "reviewer": "Reviewer_rMRz", "summary": "This paper presents new theoretical results on the convergence of primal iterates in inexact augmented Lagrangian methods (ALMs) for conic optimization. The idea is to use strict complementarity (which is a standard assumption in conic optimization) to establish quadratic growth and error bound conditions for the primal and dual programs. These bounds are then used to show linear convergence for both the primal and dual iterates in inexact ALMs. The linear convergence of the primal iterates is shown in (brief) experiments.", "questions": "* Are there problems for which the dual iterates can converge linearly, but the primal iterates converge sublinearly? If so, could this be demonstrated in an experiment?\n\n* Line 265: What exactly is meant by “nice self-dual structure”?", "limitations": "Please see “Weaknesses”", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The work provides a thorough introduction to the problem background \n* The theory is presented rigorously!", "weaknesses": "I found the main weakness of the paper to be in its presentation of results.\n\n* The paper takes too long to reach the main results. Perhaps an informal version of Theorem 3 could be stated in the introduction?\n\n* There is a lot of notation/specific terminology in the paper, which makes it difficult to follow. One suggestion to reduce the complexity would be to focus on a particular problem class (LP, SOCP, or SDP) in the main paper. For example, if focusing on LPs, the authors could move the discussion of strict complementarity of LPs to earlier in the paper, which would give more intuition for the assumptions in the paper. Furthermore, the theorems in the main paper could be simplified to address LPs, which would make the results easier to understand for a wider audience. The general results for LPs, SOCPs, and SDPs could then be presented in the appendix.\n\n* I would have liked the paper to expound upon how their work relates to machine learning (outside of some brief citations in the introduction). Ideally, this could be done by showing linear convergence of primal iterates on a conic program from machine learning. One idea could be to solve an SVM problem (QP, which is a special case of SDP). \n\n* While Figure 1 suggests that primal iterates are converging linearly, I would like to see more iterations (say 20) in the plots to really verify this claim.\n\n* I found it hard to follow how the author’s results compare to previous convergence results in the literature. I’d suggest providing a more in-depth comparison in lines 341-349.\n\n* The paper takes too long to discuss inexact augmented Lagrangian methods (these are not discussed in-depth until page 7). This makes the flow of the paper confusing — I’d suggest covering inexact ALMs closer to the introduction.\n\nMinor comments: \n\n* Discussion of scalable first-order methods (line 28) should cite PDLP [1, 2]\n\n* “Lipschitz” is misspelled on lines 100 and 103\n\n[1] Applegate, David, Mateo Diaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan ODonoghue, and Warren Schudy. 2021. “Practical Large-Scale Linear Programming Using Primal-Dual Hybrid Gradient.” In Advances in Neural Information Processing Systems, edited by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan, 34:20243–57. Curran Associates, Inc.\n\n[2] Applegate, D., Hinder, O., Lu, H. et al. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Program. 201, 133–184 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors are very thankful to the reviewer for taking the time and effort to review our manuscript. We sincerely appreciate all your valuable comments. All your comments are carefully addressed below.\n\n> **Suggestion focusing on a specific cone, for example, LP. This will make the paper easier to read**\n\nThanks for the suggestion. This will definitely make the paper more accessible. In this paper, we aim to make the paper as general as possible. In addition, there are some differences in terms of the construction of the penalty function and region/power term for the error bound. In our current manuscript, we have incorporated LP, SOCP, and SDP in our main text. Detailed proofs and individual discussions for each case are provided in the Appendix. \n\nHowever, we do agree with the reviewer the it will improve the paper clarity by focusing on one problem class. If the paper is accepted, we will follow the reviewer' suggestions and focus on the general problem class—SDP—in the main manuscript. This will not only improve clarity but also give us more space to ensure that Theorem 3 is well-integrated into the main discussion. \n\n> **Expound upon how their work relates to machine learning.**\n\nWe have added more numerical experiments in the attached PDF file under the section of Auther rebuttal. We consider the application of linear SVM and Lasso. Both the linear SVM and Lasso can be reformulated as standard conic programs with free, nonnegative, and second-order cone variables. For each application, we randomly generate three instances and run ALM for those three instances with various augmented penalty parameters $\\rho>0$. The numerical results show that the three quantities (primal cost value gap, dual cost value gap, and the KKT residuals) all converge to zero with a linear rate. The convergence speed of the residuals also depends on the value of the penalty parameter $\\rho$. The larger the penalty parameter $\\rho$, the faster the convergence of the residuals. We believe the oscillated or flattening behavior that happens in the tail (when the iterates are close to the solution set) is due to the inaccuracy of the subproblem solver and computational errors.\n\n> **While Figure 1 suggests that primal iterates are converging linearly, I would like to see more iterations (say 20) in the plots to really verify this claim.**\n\nThanks for pointing this out. However, as we use the modeling package YALMIP to formulate the subproblem and call the conic solver MOSEK to solve the subproblem. It will be difficult to control the subproblem solution accuracy. There exists oscillated and flattening behavior when the iterates are close to the solution set due to the computational error. This is reflected in our additional numerical experiments.\n\n> **I found it hard to follow how the author’s results compare to previous convergence results in the literature. I’d suggest providing a more in-depth comparison in lines 341-349.**\n\nThanks for the comments. We will revise the comparison in lines 341-349. Specifically, we mean that\n* [24, Theorem 5] requires two things: \n  1. The Lagrangian function is Lipschitz continuous at the origin, which requires both the primal and the dual solution to be unique. This assumption can easily fail, as pointed out in  [27, Section 344 3].\n  2. One more subproblem stopping criterion in addition to $A^{'}$ and $B^{’}$\n\n Our result in Theorem 3, however, suggests that the linear convergence of the primal iterates also can happen under the standard assumption of strict complementarity and bounded primal solution set.\n\n* As strict complementarity is a generic property of semidefinite programs  [42, Theorem 15] and a bounded primal solution set happens when a dual slater point exists, which is a common assumption, therefore, our result suggests that the linear convergence of the primal iterates is likely to happen under many nicely behaved problems.\n\n[24] R Tyrrell Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of operations research, 1(2):97–116, 1976.\n\n [27] Ying Cui, Defeng Sun, and Kim-Chuan Toh. On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming. Mathematical Programming, 178:381–415, 2019.\n\n[42] Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton. Complementarity and nondegeneracy in semidefinite programming. Mathematical programming, 77(1):111–128, 1997.\n\n> **The paper takes too long to discuss inexact augmented Lagrangian methods (these are not discussed in-depth until page 7). This makes the flow of the paper confusing — I’d suggest covering inexact ALMs closer to the introduction.**\n\nThanks for your nice suggestion. We will revise the introduction and incorporate further discussions about Theorem 3. \n\n> **Minor comments:**\n> 1. Discussion of scalable first-order methods (line 28) should cite PDLP [1, 2]\n> 2. “Lipschitz” is misspelled on lines 100 and 103\n\nThanks for the detailed examination of our paper. We will add the reference in the final version and fix the typo.\n\n> **Are there problems for which the dual iterates can converge linearly, but the primal iterates converge sublinearly? If so, could this be demonstrated in an experiment?**\n\nThanks for this insightful question. We believe it is a difficult task as strict complementarity holds for almost all conic problems; thus, for many instances, both primal and dual iterates are expected to converge linearly. Right now, we are struggling to find an explicit example for which the dual iterates can converge linearly, but the primal iterates converge sublinearly. \n\n> **Line 265: What exactly is meant by “nice self-dual structure”?**\n\nWe simply mean the cones of nonnegative orthant, second-order cone, and the positive semidefinite cones are self-dual. As a result, both the primal and the dual problem are the same class of problems.", "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:
The authors would like to thank the four reviewers for their valuable time reading our manuscript and providing helpful comments. While the scores from the reviewers are mixed (3, 5, 8, 3), we find that their comments are generally positive and some are very constructive. In particular, all four reviewers appreciated the soundness of our work (all rated as good), and three reviewers (K87V, Vd1D and X2mJ) rated the contributions of our work as good or excellent. 

Two major concerns raised by reviewers (K87V, Vd1D and rMRz) are 
- **Presentation of one main theoretical result** (the linear convergence of inexact ALM in Theorem 3). Two reviewers (K87V and rMRz) pointed out that one key contribution in Theorem 3  appears very late in the paper  (Page 7). Reviewer K87V commented that the proof for Theorem 3 in the main text is not easy to follow. Reviewer rMRz also suggested that we could use a particular problem class (LP, SOCP, or SDP) to improve paper clarity. 
- **Lack of sufficient numerical validations**. Reviewers K87V, Vd1D and rMRz requested more in-depth numerical validations using problems from a diverse range of applications. Reviewer Vd1D specifically suggested that experimental evaluations of LPs and SOCPs would be beneficial in validating the theoretical results.

In addition, Reviewer X2mJ provided many detailed comments which are useful to clarify our contributions further (the comment on Remark 1 and the suggestion of Rockafellar’s recent paper are very appreciated). All the four reviewers’s comments helped us further improve the quality of our work. 

Here, we would like to respond to the two major concerns mentioned above (all other comments from the four reviewers have been carefully addressed below). 

**Regarding the paper presentation**, we would like to emphasize that the contributions of this work have two key aspects:
1. *Problem Structures*: We establish new quadratic growth and error bound properties for primal and dual conic programs (**Theorem 1** and **Theorem 2**).
2. *Algorithm Analysis*: Utilizing our error bound properties, we prove that both primal and dual iterates of the inexact ALMs converge linearly under mild assumptions (**Theorem 3**).

Thus, Theorem 3 represents only one of the main theoretical contributions. The quadratic growth properties in Theorems 1 and 2 are equally important, and their proofs may be of independent interest (as noted in Remark 1 of the manuscript). In the paper presentation, we have attempted to balance these contributions. However, we agree with the reviewers that it would be beneficial to integrate Theorem 3 more prominently within the main discussion and provide a more complete and accessible proof in the appendix. In the updated version, we will follow the reviewers' suggestions and focus on the general problem class — SDP — in the main manuscript. This change will not only improve clarity but also give us more space to ensure that Theorem 3 is well-integrated into the main discussion. We will revise the proof of Theorem 3 to make it more accessible in the appendix. 

**Regarding the numerical validations**: as the reviewers correctly pointed out, the major contributions of this work are theoretical. Due to the page limit, we have provided experiments on three problem classes (Max-Cut, matrix completion, binary quadratic program) to validate the practical convergence performance of ALM. We agree with the reviewers that more in-depth numerical validations will further demonstrate our theoretical contributions. To address this, we have conducted new experiments on two classical machine learning applications—linear SVM and Lasso. The results also supported our theoretical findings, and they are summarized in the attached PDF. In the final version, we will incorporate these new numerical results in the appendix.

We hope that the changes and responses will be sufficient to address the reviewers’ concerns. Please let us know if you have any additional questions or require further clarification. Any feedback will be highly appreciated.

Meta-review: This paper introduces Inexact Augmented Lagrangian Methods (ALM) for addressing conic linear optimization problems. Under the assumptions of strict complementarity and strong duality, the authors establish local linear convergence by demonstrating the quadratic growth property within a compact neighborhood of the optimal solution for both the primal and dual problems.

I believe that the paper makes a significant contribution by proving the quadratic growth and error bounds for both primal and dual conic programs (P) and (D) over any compact set containing an optimal solution under standard assumptions, thereby extending existing results. Furthermore, the authors demonstrate that both primal and dual iterates converge linearly, a result that was previously unavailable for primal iterates. Most reviewers support the publication of the paper following the rebuttal. I recommend acceptance.
Decision: Accept (poster)