We address the last comments about weaknesses and questions by the reviewer. The changes to the manuscript and supplemental material are highlighted blue.

Discussion about weaknesses

W6. We have now modified our manuscript to limit the reader's attention to the main works related to our paper at most three references.

Questions

Q1. We would like to mention that in the supp. material, in Sections I.3 and K we provide implementation details for the experiments presented in our manuscript. From these implementation details and the nature of Experiment 1, we just need to report the wall time (runtime) to compute the proximal of invex/quasi-invex regularizers. In the case of the fidelity term, we just need to compute its derivative as a close form, therefore the runtime is negligible in practice. We report the runtime of proximal solutions in Section I.3 of supp. material. We remark that these proximal solutions are the activation functions in the training process of Experiment 1. From the numerical results reported in Section I.3 we observe that computing the proximal of the $\ell_{1}$-norm is faster than the proximal of invex regularizers. However, this difference is given in milliseconds, potentially making it negligible in practice. These changes are highlighted in the revised manuscript in blue, and due to the length of the changes, we are not reporting the modified texts here.

Q2. Yes. It is our belief that invexity/quasi-invexity offers superior performance. To elaborate on this, we remark that the main purpose of this study is to provide a new theoretical approach that allows us to globally solve constrained optimization problems with higher reconstruction quality, than what existing convex approaches can offer. As we have pointed out in the manuscript, the essential breakthrough of our work lies in the fact that the proposed family of invex/quasi-invex functions is closed under summation (aspect that only convexity enjoys up to this point). The significance of this result manifests on two fronts. Firstly, Theorem 3 paves the way for establishing theoretical guarantees for global optima of program 1 beyond the realm of convexity. Secondly, it bestows practical benefits to practitioners, as both Definition 4 and the third statement of Theorem 3 offer a systematic methodology for constructing invex/quasi-invex functions. As a final remark, we have shown in our manuscript that our proposed family of functions do not increase the complexity in solving constrained optimization problems.

We believe that these comments addresses the concerns.

Q3. To address the comment related to the validity of Theorem 7, we have modified the manuscript by adding a numerical experiment in Section K.4 of supp. material. There, we explain how $\beta_{k}^{g}(x)$ and $\upsilon_{f}(x)$ can be estimated in a specific compressive sensing setting, therefore confirming numerically Theorem 7. Due to the length of the changes, we are not reporting the modified texts here. We kindly ask the reviewer to review the supp. material.

Thank you for the time reviewing our manuscript. We appreciate the reviewer's advice to improve our manuscript. We address the comments about weaknesses. The changes to the manuscript and supplemental material are highlighted blue.

Discussion about weaknesses

W1. Thank you for the time reviewing our manuscript. We appreciate the reviewer's advice to improve our manuscript. We believe we have reviewed the whole manuscript and performed major changes to improve writing, organization and presentation following the reviewer guidelines. These changes are highlighted in the revised manuscript in blue, and due to the length of the changes, we are not reporting the modified texts here. We kindly ask the reviewer to see the new version.

W2. We agree that there are many applications within the realm of signal recovery where the computational complexity is high such as matrix completion. We believe that to address the reviewer's comment properly a deeper and separate study has to be done since we purely rely on ADMM and APG methods, and as such, efficient implementation is beyond the scope of this paper. To clarify this we have modified Section 6 of our manuscript clearly stating that this is an interesting direction for a future work, which we intend to explore.

In contrast, what we have covered in this manuscript regarding computational complexity it is the convergence rate of ADDM and APG methods using our proposed family of invex/quasi-invex functions. Specifically, we have proven that both ADMM and APG methods using our proposed family of invex/quasi-invex functions are as efficient as solving the well-established convex optimization problems. We reported this in Theorems 9 and 11 (supp. material) by stating that ADMM and APG for our invex/quasi-invex functions have convergence rates of $\mathcal{O}(1/t)$ and $\mathcal{O}(1/t^{2})$ respectively, which are the same in the traditional convex case.

Therefore, considering reviewer's comment we have modified our manuscript to further clarify that ADMM and APG methods using our proposed family of invex/quasi-invex functions are as efficient as solving the well-established convex optimization problems. We kindly ask the reviewer to see the new Introduction and Conclusions sections.

W3. Thank you for highlighting this aspect. Considering the comment we have modified our manuscript and include limitations of our work. This reads as follows:

Modified text in Section 6: While the theoretical analysis presented here to handle signal restoration problems is the first of its kind and performs well on a number of imaging tasks, its applications beyond imaging tasks are yet to be explored. More specifically, the application of these algorithms around deep learning research yet to be explored, which can pave a way to improve several downstream applications, such as low-rank matrix recovery and alike. As a pure algorithm, a number of things can be improved, such as decoupling the $\eta$ from $\upsilon_{f,\eta}(x)$, improving the efficiency of the algorithm beyond what ADMM and APG can offer.

W4.1 We have reviewed the whole manuscript including the mentioned sentence, and performed major changes to improve writing, organization and presentation following the reviewer guidelines. These changes are highlighted in the revised manuscript in blue, and due to the length of the changes, we are not reporting the modified texts here. We kindly ask the reviewer to see the new version.

W4.2 We have now modified Table 3 only to highlight the best and worst results.

W4.3 In addition revising the whole manuscript, we have also improved this sentence (by breaking them into two sentences) and performed similar changes throughout the paper. These changes are highlighted in the revised manuscript in blue, and due to the length of the changes, we are not reporting the modified texts here. We kindly ask the reviewer to see the new version.

W4.4 We have modified our manuscript by removing "E-" from Section 4.3 and thus avoid any further confusions.

W4.5 We have modified our manuscript by referring to optimization problem in 1 like "Program 1" or "optimization problem in 1". These changes are highlighted in the revised manuscript in blue, and due to the length of the changes, we are not reporting the modified texts here.

W5. To address this comment we have provided a short background at the beginning of each experiment guiding the reader with meaningful references related to our work, instead of a separate section. We believe that this organisation ensures that the advances to the invexity/quasi-invexity within the field of optimization are valued than perceiving them as tied to specific imaging applications. These changes are highlighted in the revised manuscript in blue, and due to the length of the changes, we are not reporting the modified texts here.

Thanks for your response and detailed explanations. I had a quick pass on the revised version of your paper. I believe there is still room for improvement of the presentation. It might be a matter of preference, but equation numbers are not referred to in parenthesis which can cause confusion. Many long sentences exist which make the text hard to read. Many sentences can be easily shorten. For example, Under Definition 4:

"Definition 4 places a requirement on $f(x)$ and $g(x)$ in optimization problem 1 to operate element-wise on positive values."

can become

"Definition 4 requires $f(x)$ and $g(x)$ in (1) to operate element-wise on positive values."

I repeat that this was just an example and many of these kind of sentences exist in the paper. I keep my score unchanged. Thanks!

We address the questions by the reviewer. The changes to the manuscript and supplemental material are highlighted blue.

Questions

Q1. We have addressed this in the previous comment, and we kindly ask the reviewer to refer to the first part of our rebuttal.

Q2. As we mentioned in the manuscript, specifically in Section 4.1 and Theorem 7, the invex version of optimization problem in 1 for compressive sensing is when the constraint takes the form of $f(Ax-y)$ where $A \in \mathbb{R}^{m\times n}$ with $m\ll n$ ($f$ being an admissible function e.g. equation 4), and the regularizers $g(x)$ takes the form of admissible functions in Definition 4 (e.g. equation 3).

Regarding the question about the quantities $\beta_{k}^{g}(x)$ and $\upsilon_{f}(x)$, we have addressed this in the previous comment, and we kindly ask the reviewer to refer to the previous comment.

Lastly, to address the comment related to the scale of the mentioned quantities, we have modified the manuscript by adding a numerical experiment in Section K.4 of supp. material, where we explain how $\beta_{k}^{g}(x)$ and $\upsilon_{f}(x)$ can be estimated in a specific compressive sensing setting. Due to the length of the changes, we are not reporting the modified texts here. We kindly ask the reviewer to review the supp. material.

Thank you for the time reviewing our manuscript. We appreciate the reviewer's advice to improve our manuscript. We address the comments about weaknesses. The changes to the manuscript and supplemental material are highlighted blue.

Discussion about weaknesses

W1. As this comment concerns multiple aspects, please allow us to respond these in turn, as follows: We start by clarifying that we have provided two different algorithms to compute these points: the alternating direction method of multipliers (ADMM) and accelerated proximal gradient methods (APG). Given that ADMM and accelerated APG are well-established convex optimization algorithms, we believe this answers the question of finding an implementation. As for the efficient implementation, we purely rely on ADMM and APG, as efficient implementation is beyond the scope of this paper. To clarify this, we prove that both ADMM and APG methods using our proposed family of invex/quasi-invex functions are as efficient as solving the well-established convex optimization problems. We reported this in Theorems 9 and 11 by stating that ADMM and APG for our invex/quasi-invex functions have convergence rates of $\mathcal{O}(1/t)$ and $\mathcal{O}(1/t^{2})$ respectively, which are the same in the traditional convex case. Additionally, realizing the significance of the implementation details, we have included additional details on the implementation for the proximal expressions in Section I.3 of the Supplementary Material.

Secondly, we included a text in Section 4 stating that Appendix I includes details around how the ADMM algorithm can be used to solve problems in the form of Eq. 1 (Section titled "Remarks on Equation 1").

We write here how Eq. 1 is expressed in the form needed for Theorem 9. We recall that Eq. 1 is in the form of $\text{minimize } g(x) \text{ subject to }f(x)<\epsilon.$

This means Eq. 1 can be equivalently rewritten as $\text{minimize } g(x) + \lambda f(x),$ for some $\lambda > 0$ that helps to satisfy the condition $f(x)<\epsilon$ (please see [R1, R2] provided below that supports this argument). Thus, by introducing a variable $z=x$, Eq. (1) can be finally rewritten as $\text{minimize } g(x) + \lambda f(x) \text{ subject to } z=x,$ which is in the optimization form of Theorem 9, where $h_1(x)=g(x)$, and $h_{2}(z)=\lambda f(z)$.

R1 Atomic decomposition by basis pursuit.

R2 Orthogonal matching pursuit for sparse signal recovery with noise.

We have also mentioned in the second paragraph of Section 4, stating that Appendix J presents the extended APG.

Regarding the comment on solving Eq. 1 efficiently, we remark that both Theorem 9 (about ADMM), and Theorem 11 in Appendix J (about APG) mentioned that the convergence rate of ADMM and APG when $f$, and $g$ in Eq. 1 are the invex/quasi-invex functions studied in this work is the same as in the convex traditional case.

Taking these comments, we have now modified the manuscript (changes are in blue) to further clarify this aspect.

W2. This question concerns multiple aspects, and as such, please allow us to respond to these in turn.

W2.1. Considering the comments, we have now modified the statement of Theorem 7, mentioning the extension over quasi-invex functions in earlier part of the statement of Theorem 7.

W2.2. The constants $\beta_{k}^{g}(x)$ and $\upsilon_{f}(x)$ are indeed universal because they depend on the unknown desirable underlying signal $x$. To support this statement, we highlight that our Theorem 7 is in the same form as the well-established and known convex recovery result (Foucart, Rauhut, 2013, Theorem 6.12). For the sake of completeness, we present below Theorem 6.12 from (Foucart, Rauhut, 2013).

Theorem 6.12 Suppose that the $2k$th restricted isometry constant of the matrix $A\in \mathbb{R}^{m\times n}$ satisfies $\delta_{2k}<\frac{4}{\sqrt{41}}$. Also, the noise vector $\eta$ satisfies $\lVert Ax -y\rVert_{2}<\epsilon$ for $\epsilon>0$ and $x\in \mathbb{R}^{m}$ is a noisy measurement vector. If $g(x)$ is the $\ell_{1}$-norm, then the solution $x^{\star}$ of program~1 holds $\lVert x - x^{\star} \rVert_{1} \leq C \sigma_{k}(x) + D\sqrt{k}\epsilon$, where the constants $C,D>0$ depend only on $\delta_{2k}$. Additionally, we have that $\sigma_{k}(x) = \inf_{\lVert z\rVert_{0}<k} \lVert z - x\rVert_{1}.$

In summary, the above result highlights the significance of our Theorem 7 since it follows the same form of (Foucart & Rauhut, 2013, Theorem 6.12), and we have modified our manuscript to mention this.

However, we agree with the reviewer that $\upsilon_{f}(x)$ also depends on $\eta$. Therefore, we have corrected this typo by changing $\upsilon_{f}(x)$ to $\upsilon_{f,\eta}(x)$.

W2.3. We agree with the reviewer that Theorem 8 h is convex for a range of $\lambda$. We have corrected this typo by adding this change to the statement of Theorem 8.

Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing.

Thank you for the time reviewing our manuscript. We appreciate the reviewer's advice to improve our manuscript. We address the comments about weaknesses. The changes to the manuscript and supplemental material are highlighted blue.

Discussion about weaknesses

W1. As mentioned in the manuscript, Theorems 7, 8, and 9 present global optimality results that impact many applications for the family of quasi-invex functions stated in Theorem 3. More specifically, Theorem 7 and 8 include the sentences "We show that a similar result holds for quasi-invex constructs as in Theorem 3", and, "Consider the optimization problem in 11 for invex and quasi-invex TV regularizers as in Theorems 4 and 6, respectively", respectively. Moreover, in the case of Theorem 9, the sentence "Let $h_{1}(x)$, $h_{2}(z)$ be any of the constructs in Theorem 3,..." was intended to point out the systematic methodology for constructing invex/quasi-invex functions studied in this work in Theorem 3. With these, we assumed the notion of global optimality of the results for quasi-invex functions are obvious.

We also remark that quasi-invex functions do not share the property that every local minimizer is a global minimizer (as in the case of invex functions). The global optimality of Equation 1 when $f(x)$, and $g(x)$ are the family of quasi-invex functions stated in Theorem 3 is covered in Theorem 9 (by solving the primal-dual problem). This statement is explained in Appendix I (see Section titled "Remarks on Equation 1"). For completeness, we write here how Equation 1 is expressed in the form needed for Theorem 9.

We recall that Equation 1 is in the form of $\text{minimize } g(x) \text{ subject to }f(x)<\epsilon.$. This means Equation 1 can be equivalently rewritten as $\text{minimize } g(x) + \lambda f(x),$ for some $\lambda > 0$ that helps to satisfy the condition $f(x)<\epsilon$ (please see [R1, R2] provided below that supports this argument). Thus, by introducing a variable $z=x$, Eq. (1) can be finally rewritten as $\text{minimize } g(x) + \lambda f(z) \text{ subject to } z=x,$ which is in the optimization form of Theorem 9, where $h_1(x)=g(x)$, and $h_{2}(z)=\lambda f(z)$.

R1. Atomic decomposition by basis pursuit.

R2.Orthogonal matching pursuit for sparse signal recovery with noise.

Therefore, considering the above response and the reviewer's comment, we have modified the manuscript to make more explicit the global optimality results related to the family of quasi-invex functions in Section 4 and Theorem 9. We believe the statements of Theorems 7 and 8 clearly invoke the proposed family of quasi-invex functions, and thus, we are leaving their statements intact.

W2. In order to answer the question about the significance and impact of our work over (Pinilla, 2022a), we list the notable differences between this work and (Pinilla, 2022a) as follows:

• Studies in (Pinilla, 2022a) are limited to five invex functions; here, we report a family of invex and quasi-invex functions suitable for optimization.
• Theorem 3 of this manuscript reports a systematic methodology for constructing invex/quasi-invex functions, an important aspect missing in (Pinilla, 2022a) and the current optimization literature.
• We proved in Theorem 3 that the sum of two of these invex/quasi-invex constructs is again invex/quasi-invex. As we pointed out in our manuscript, this is a very significant breakthrough with the first family of invex/quasi-invex functions closed under summation identified and is the first family of functions beyond convexity that we can prove global optima in constrained optimization problems. This is not covered in (Pinilla, 2022a) or the existing optimization literature.
• As highlighted here, we have extended the convergence guarantees of ADMM for the proposed family of invex/quasi-invex functions. This result is missing in (Pinilla, 2022a).
• Theoretical results for Theorem 7 in our paper, which is a counterpart or equivalent to Theorem 4 (Pinilla, 2022a), are reported for the proposed family of invex/quasi-invex functions, including the noisy case. These results far exceed those presented in (Pinilla, 2022a), where the focus has only been on five invex functions and a noiseless case.
• We report in Theorems 4 and 6 on how to build invex/quasi-invex-like total variation regularizers. This is a missing aspect not only in (Pinilla, 2022a) but also in the current optimization literature.
• Collectively, the contributions here in this paper, the techniques more applicable to more practical cases, opposed to the technique presented in (Pinilla, 2022a).

We have taken these comments and have modified the manuscript to clarify the contributions of this paper over (Pinilla, 2022a).

We address the questions and the minor comments by the reviewer. The changes to the manuscript and supplemental material are highlighted blue.

Questions

Q1. Yes, the invex functions considered in this paper are, indeed, prox-friendly. Realizing the significance of the implementation details, we have included additional details (as part of the Supp. Material) surrounding the implementation for the proximal expressions presented in Section I.3 of the Supp. Material. There we have presented as example the implementation of the proximal solution for the $\ell_{p}$-quasinorm. The text reads as follows:

Implementation details: In order to efficiently compute the proximal solutions, which is an entry-wise operation, in Table 4, we use the Python library CuPy. The reason is that this library allows the creation of GPU kernels in the language C++ from Python (quick guide on how to create and use these kernels). Therefore, inside this GPU kernel, we implemented the entry-wise operation from the Proximal Operator column of Table 4. We remark that this implementation is efficient because it runs in parallel and at the GPU speed. Additional features of the CuPy library are the flexibility to connect both TensorFlow and PyTorch libraries for training neural networks.

In addition to this, we have also highlighted this as part of the main text in Section 4 with the following modified text

Modified text: Appendix I also provides the proximal solution for the studied invex/quasi-invex functions along with their computational time. These solutions are used to perform the numerical experiments in Section 5.

Please see Appendix I for the implementation details around the proximal solution for the studied invex/quasi-invex functions.

Q2. As this question concerns multiple aspects, please allow us to respond these in turn.

To begin with, we would like to clarify that the statement of Theorem 9 includes "Let $h_{1}(x)$, $h_{2}(z)$ be any constructs in Theorem 3,...", which was meant to point out the systematic methodology for constructing invex/quasi-invex functions studied in this work in Theorem 3. As such, Theorem 9, indeed, assumes both invex and quasi-invex family of functions.

Notwithstanding this, it is correct that prox-regularity implies merely quasi-invexity, as we stated in the manuscript. However, the critical disparity between our proposed invex/quasi-invex family of functions and prox-regularity is that prox-regularity does not imply uniqueness in the update steps for $x^{(t+1)}$ and $z^{(t+1)}$ in Equation (13), which is the key aspect to prove convergence of ADMM. In contrary, our family of invex/quasi-invex functions ensure uniqueness in the update steps for $x^{(t+1)}$ and $z^{(t+1)}$ as can be read in the proof of Theorem 9. This property ensures uniqueness and critical to the proof. This difference also highlights the importance of our proposed family of functions.

We have now modified the manuscript to reflect these changes and to make this aspect clearer in Section 4 and Appendix I. Below we show only the modified sentence in Section 4 due the space limitations, and we kindly ask the reviewer to see Appendix I of supp. material.

Added sentence at the end of Section 4: Proof of Theorem 9 relies on Theorem 8, which ensures uniqueness in the estimations of $x^{(t+1)},z^{(t+1)}$ in Equation 13. This uniqueness is cannot be obtained by prox-regular functions, and thus highlights the significance of our proposed family of invex/quasi-invex functions.

Minor

Thank you for your careful review. We have corrected all the typos pointed out by the reviewer. Additionally, we have changed the mentioned sentence to "the uniqueness result in Theorem 8".