Accelerating Multi-Block Constrained Optimization Through Learning to Optimize

Thank you very much for the valuable comments and suggestions. Below is our response.

Originality of the Algorithm

We appreciate the reviewer's request for clarification on the originality of our algorithm. The framework presented in this paper extends the MPALM framework proposed in [1] by incorporating a novel Learning to Optimize (L2O) approach to handle multi-block constrained optimization problems, a domain where traditional L2O methods face limitations. Our framework is more inclusive in the sense that it adapts parameters dynamically through learning, which enhances flexibility and performance MPALM. This is indeed supported by our numerical experiments, which motivates further potential applications in various domains that can be modeled as constrained multi-block optimization problems.

Lack of Strong Theoretical Guarantees and Detailed Computational Cost

We acknowledge the reviewer’s concern regarding the lack of specific convergence guarantees. While the primary focus of this paper is to introduce a novel L2O framework for addressing multi-block constrained optimization problems, we agree that establishing rigorous theoretical guarantees for the adaptive/restarted MPALM is crucial for fully validating the approach. We regret that we are unable to provide comprehensive theoretical results at this stage. However, we view this work as an important initial step in this research direction, laying the groundwork for future studies to develop and formalize these guarantees.

We appreciate the reviewer's request for a more thorough assessment of the computational cost and practicality of our method. However, we shall argue that since the proposed framework is quite general, and the computational cost is highly problem dependent. The main computational bottlenecks are: (1) Cost in obtaining the true solution $x*$ which can be expensive and problem-depending. As a data-driven approach, we think this is an issue commonly seen in practice. (2) Cost in updating each block at each iteration of the MPALM. This can be relatively small, since the MPALM is able to fully explore the multi-block structure of the underlying problem. (3) Cost in solving the optimization in selecting the parameters $\{\sigma_j\}$. However, once a strategy is learned, it can be used for future tasks, which could save a significant amount of future computational cost. We have placed the above discussions in the revised paper.

Presentation

We apologize for the lack of detailed definitions to MPALM and LMPALM in the main text. This was an oversight, and we will revise the manuscript to address these issues. We also add further insights on why LMPALM performs betters at the end of the paper. Data-driven approaches work well because they have the potential to leverage the ability to learn patterns and structures from data without explicitly programming those patterns, thus providing appealing generalization capabilities from data.

Thank you for your thorough review and valuable feedback. Below, we address the weaknesses, minor issues, and questions you have raised.

Comparison with FISTA

We acknowledge that FISTA is a strong baseline for the LASSO problem due to its acceleration properties. However, based on our numerical experience and the numerical results provided in [Figure 6, Chen et al., 2022], one observes that LISTA outperforms FISTA empirically. For simplicity, we refrain from presenting the computational results for FISTA and focusing on comparing L2O approaches.

Novelty of the Work

While the proposed framework focuses on learning parameters rather than introducing a completely new algorithm, we argue that the novelty lies in developing a unified learn-to-optimize (L2O) ADMM-type framework tailored for multi-block constrained optimization problems. These problems are complex and underexplored in the current literature. Furthermore, the L2O approach introduces a novel perspective on how machine learning approaches can enhance the efficiency of existing optimization methods.

Convergence

We apologize for the omission of references and proofs for Theorem 1. In the revised version, Theorem 1 have been properly referenced. We also understand the concern regarding Assumption 3 and its role in provable convergence. The convergence for the adaptive MPALM remains an open question, which we defer in future research.

Typos

We appreciate you pointing out the grammatical issues. These have been corrected in the revised manuscript to improve clarity and readability.

Issues in Back-Propagation

The statement regarding back-propagation failing in practice applies to scenarios where gradient-based methods struggle, such as cases with non-differentiable operations. We clarify that if the updating rule for each block only involves almost surely differentiable operations, such as ReLU, then our framework will be applicable through back-propagation in modern libraries such as PyTorch and JAX.

Chen T, Chen X, Chen W, Heaton H, Liu J, Wang Z, Yin W. Learning to optimize: A primer and a benchmark. Journal of Machine Learning Research. 2022;23(189):1-59.

Thank you for your thoughtful review and feedback, which have helped to improve the quality of the paper. Below are our responses to your points:

Presentation

In the revised manuscript, we will streamline the introduction of MPALM and move some background information to the appendix. This will allow us to present the key contributions earlier in the paper, providing readers with a clearer understanding of the proposed method and its significance. We would also like to thank you for pointing out the issue with the font size and visual appeal of Figures 1 and 2. We will redesign these figures with larger, more legible fonts and an improved layout to enhance clarity and visual quality.

Theoretical Contribution of Theorems 1 and 2

Theorems 1 and 2 are foundational results that establish the convergence properties of MPALM and how we can fully explore the block structure of the optimization problem, a core building block of our proposed L2O framework. These results are crucial to the overall framework, but are not novel in themselves. We included them in the main text to provide a complete and coherent description of MPALM. However, we will revise the manuscript to clearly distinguish these results from our original contributions and explicitly reference their sources.

Non-Asymptotic Convergence

Under a suitable error-bound condition, one can establish the linear convergence rate of the method in terms of Karush-Kuhn-Tucker (KKT) residues; see [Chen et al., 2021]. However, we shall mention that for many practical problems, the error-bound condition cannot be verified before the optimal solution has been computed.

Theoretical Contributions Beyond Theorems 1 and 2

The primary contribution of this paper is the introduction of the L2O framework tailored for multi-block constrained optimization problems, specifically using MPALM as the foundation. While Theorems 1 and 2 describe properties of MPALM, our original contribution lies in formulating a learn-to-optimize framework that can generalize across problem instances. One interesting future direction will be analyzing the convergences restarted/adaptive variants of the MPALM. For instance, one may try to characterize conditions on {\sigma_j\} so that the restarted/adaptive is convergence.

Applicability to Popular Machine Learning Tasks

The proposed method has the potential to be extended to popular machine learning tasks. Although our experiments focus on the Lasso and discrete optimal transport problems to validate the framework, its flexibility allows for broader applications as long as one is able to formulate the problem as the constrained multi-block convex optimization problems, including the multi-marginal optimal transport problems that are challenging to solve by existing methods in the literature.

Use of Bilevel Optimization for Hyperparameter Learning

We appreciate the suggestion to explore bilevel optimization for hyperparameter learning. While the current work does not mention the bilevel optimization explicitly, we acknowledge its potential relevance. We refrain from adding related discussions on the bilevel optimization approach since we want to focus more on L20 for ADMM-type algorithms and its applications.

Liang Chen, Xudong Li, Defeng Sun, and Kim-Chuan Toh. On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming. Mathematical Programming,185(1-2):111–161, 2021.

Thank you for your prompt reply.

Regarding the theoretical guarantees, we appreciate your comments and have addressed them in the response to the reviewer YmSS. For the applicability of this work, we would like to highlight an example in federated learning, which involves solving optimization problems of the form:

$$\min_{x} \frac{1}{N}\sum_{i=1}^N f_i(x) + r(x)$$

which can be formulated as

$$\min_{x, x_1,\dots, x_N} \frac{1}{N}\sum_{i=1}^N f_i(x_i) + r(x) \quad \mathrm{s.t.} \quad x = x_i, i = 1,\dots N.$$

This reformulation aligns with the multiblock constrained optimization framework studied in our work. For further details and applications of federated learning, we refer you to the review article:

Li L, Fan Y, Tse M, Lin KY. A review of applications in federated learning. Computers & Industrial Engineering. 2020 Nov 1;149:106854.

Regarding the readability of the paper, we would greatly appreciate your further feedback on specific areas that could be improved. While we have endeavored to address all the issues raised by the reviewers, we welcome any additional suggestions to enhance the clarity and presentation of our work.

Thank you for your constructive input, and we look forward to hearing your thoughts.

We acknowledge the reviewer's concerns regarding the limitations of our experimental setup, including the use of a small dataset, the absence of real-world datasets, and the challenges in obtaining the exact $x^*$. These are valid points, and we recognize them as areas for improvement in future work.

However, we would like to emphasize that the primary focus and contribution of our research lie in the development of a novel "Learning to Optimize" (L2O) ADMM-type framework specifically designed to handle multiblock constrained optimization problems. These problems are inherently challenging and represent an area of L2O that remains underexplored in the current literature.

Our work lays the methodological foundation for addressing these issues, which we believe is a critical first step before scaling the approach to larger and more complex datasets or applying it directly to real-world scenarios. Furthermore, while the current experiments are designed to validate the feasibility and effectiveness of the proposed framework in a controlled setting, we argue that they still provide meaningful insights. This approach allows us to isolate and analyze the core contributions of our method, providing a solid basis for future extensions. We want to mention that in the experiment on optimal transport, we indeed used the MNIST image data set, which we recognize as a real-world dataset that is commonly used in the ML community.

We also appreciate your suggestions to improve the structure and clarity of our manuscript. To address this, we will consider relocating some of the background material to the appendix. We will also ensure that Theorem 1 is properly referenced in the revised version of the paper.