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.

Suggestion focusing on a specific cone, for example, LP. This will make the paper easier to read

Thanks 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.

However, 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.

Expound upon how their work relates to machine learning.

We 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.

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.

Thanks 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.

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.

Thanks for the comments. We will revise the comparison in lines 341-349. Specifically, we mean that

• [24, Theorem 5] requires two things:
  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].
  2. One more subproblem stopping criterion in addition to $A^{'}$ and $B^{’}$

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.

• 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.

[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.

[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.

[42] Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton. Complementarity and nondegeneracy in semidefinite programming. Mathematical programming, 77(1):111–128, 1997.

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.

Thanks for your nice suggestion. We will revise the introduction and incorporate further discussions about Theorem 3.

Minor comments:

1. Discussion of scalable first-order methods (line 28) should cite PDLP [1, 2]
2. “Lipschitz” is misspelled on lines 100 and 103

Thanks for the detailed examination of our paper. We will add the reference in the final version and fix the typo.

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?

Thanks 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.

Line 265: What exactly is meant by “nice self-dual structure”?

We 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.

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.

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}$

Thanks 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$.

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.

Thanks 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.

Lines 184-185: If the linear constraints $\mathcal{A}(x) = b$ is empty, how to define the exact penalty function?

Thanks 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.

Line 226: Why is there $\mathbb{F} \times \mathbb{E}$ instead of \mathbb{F}?

Here, 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.

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.

This 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.

Typo: Line 238: Should (8b) be replaced by (8a)?

Thank you. This is a typo. It should be replaced by (8a).

Typo: The notation $\mathbb{R}^n$ should be changed to $\mathbb{R}^n_+$.

We will double-check our paper and fix the typo. Thanks for your careful reading of our work.

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.

We have provided some general responses 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.

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?

Thanks 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.

Moreover, we would like to point out that we have two main contributions to this work

• Problem Structures: We establish new quadratic growth and error bound properties for primal and dual conic programs (Theorem 1 and Theorem 2).
• 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).

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). 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.

[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.

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?

Thank 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.

In 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.

One 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.

[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.

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.

Thanks 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.

Regarding 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.

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

Lack of characterization of how inexact evaluation of the proximal operator affects convergence.

Thanks 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.

[1] Xu, Yangyang. "Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming." Mathematical Programming 185 (2021): 199-244.

Lack of experimental evaluation of conic problems other than SDPs.

Motivated 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.

In 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.

[43] Ding and udell. On the simplicity and conditioning of low rank semidefinite programs. SIAM Journal on Optimization, 31(4):2614–2637, 2021.

Lack of experimental evaluation to claim that there is local linear convergence given inexact evaluations of the subproblem

The 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.

As 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.

[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.

Have you considered showing the local linear convergence given different random starting points for Inexact ALM?

Throughout 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.

Did you use inexact evaluation of the subproblem in Eq. (15a)?

We 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.

Have you considered showing the local linear convergence given different error tolerance schedules for $\epsilon_k$ and $\delta_k$ for all $k$?

We 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.

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.

We 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.

[61] Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):796–817, 2001.

Limitations

Thanks 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.

The authors would like to thank the reviewer for positive feedback and for directing us to the MOSEK documentation. We appreciate the reviewer's understanding of the challenges involved in conducting numerical experiments with varying schedules for $\epsilon_k$ and $\delta_k$.

• Following the reviewer's suggestion, we conducted new numerical simulations to assess the impact of subproblem accuracy by varying the accuracy settings of the MOSEK solver.
• We ran the inexact ALM on one instance of SVM and one instance of LASSO, adjusting the MOSEK accuracy settings (primal feasibility, dual feasibility, and relative complementarity gap) from $10^{-2}$ to $10^{-8}$.
• Since we cannot include figures in this response, we present the numerical results in the following tables. The results indicate that higher accuracy in the subproblem solver leads to faster convergence of the residuals. For instance, with an accuracy setting of $10^{-2}$, the inexact ALM fails to converge to a high-accuracy solution after 20 iterations. With an accuracy setting of $10^{-4}$, the residuals converge to the order of $10^{-3}$. At $10^{-6}$ for the subproblem accuracy, the residuals decrease to the order of $10^{-6}$, and at $10^{-8}$, they decrease to around 4.62$\mathrm{e}$-08 after 20 iterations, showing linear convergence as expected by our theoretical analysis.
• A similar effect of subproblem accuracy was observed in the LASSO experiments.

Some detailed numerical results are shown below. We will add the corresponding figures to the final version of our work. We believe these extra numerical experiments further validate our theoretical analysis.

SVM - Primal cost value gap

Lasso - Primal cost value gap