Deep Distributed Optimization for Large-Scale Quadratic Programming

Authors: Augustinos D Saravanos, Hunter Kuperman, Alex Oshin, Arshiya Taj Abdul, Vincent Pacelli, Evangelos Theodorou
Primary area: optimization
Keywords: Learning-to-Optimize, Distributed Optimization, Large-Scale Quadratic Programming

Abstract:
Quadratic programming (QP) forms a crucial foundation in optimization, appearing in a broad spectrum of domains and serving as the basis for more advanced algorithms. Consequently, as the scale and complexity of modern applications continue to grow, the development of efficient and reliable QP algorithms becomes increasingly vital. In this context, this paper introduces a novel deep learning-aided distributed optimization architecture designed for tackling large-scale QP problems. First, we combine the state-of-the-art Operator Splitting QP (OSQP) method with a consensus approach to derive **DistributedQP**, a new method tailored for network-structured problems, with convergence guarantees to optimality. Subsequently, we unfold this optimizer into a deep learning framework, leading to **DeepDistributedQP**, which leverages learned policies to accelerate reaching to desired accuracy within a restricted amount of iterations. Our approach is also theoretically grounded through Probably Approximately Correct (PAC)-Bayes theory, providing generalization bounds on the expected optimality gap for unseen problems. The proposed framework, as well as its centralized version **DeepQP**, significantly outperform their standard optimization counterparts on a variety of tasks such as randomly generated problems, optimal control, linear regression, transportation networks and others. Notably, DeepDistributedQP demonstrates strong generalization by training on small problems and scaling to solve much larger ones (up to 50K variables and 150K constraints) using the same policy. Moreover, it achieves orders-of-magnitude improvements in wall-clock time compared to OSQP. The certifiable performance guarantees of our approach are also demonstrated, ensuring higher-quality solutions over traditional optimizers.

Decision: accept (poster)
Reviewer scores: 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1729998433039

thread_type:
official_review

<thread_object>
creator: reviewer_eeug

<content>
summary:
This paper proposes two frameworks -- Distributed Quadratic Programming (DistributedQP) and Deep Distributed Quadratic Programming (DeepDistributedQP). The former combines the state-of-the-art operator splitting method in optimization with distributed optimization, and the latter further introduces deep neural networks into the framework. The authors theoretically prove the convergence guarantees and the generalization bounds of the algorithms. Some numerical simulations are provided to empirically verify the effectiveness of the algorithms.

strengths:
1. The organization of the paper is clear -- the authors first introduce distributed version of operator splitting, and then combine explain how to incorporate deep learning techniques into the proposed framework to solve optimization problems more effectively.

2. The theoretical proof is well-structured and easy to follow.

weaknesses:
Major:

1. (Lack of Motivation) In DEEPDISTRQP framework, the authors aimed to combine distributed optimization, in particular distributed quadratic programming, with deep learning. However, it lacks motivation of why one should study this type of problems. It is true that distributed QP part has the advantage of interpretability, while the deep learning part has stronger generalization capabilities. However, the experiments are only limited to relatively small-scale problems like optimal control, portfolio optimization, etc. It is unclear if this framework can handle large-scale deep learning problems effectively, and thus a optimization journal, instead of a machine learning conference, might be a better fit for this paper.

2. (Lack of Novelty) The design of the frameworks as well as the theoretical analysis are more like a combination of existing techniques, such as local and global updates, primal dual updates, the generalization bounds, etc. It is unclear if there is any novelty of simply combining these techniques, especially provided that the experiments are only conducted on some simple ones.

3. (Unfair Comparison in Experiments) All figures of the experiments section have the iteration number as the horizontal axis, and the curves showcase better performance of DeepDistributedQP. However, different model architectures have different per-iteration complexities, and thus it is unfair to simply plot the optimality gap vs iteration numbers.

Minor:

1. The term 'OSQP' is first introduced in the abstract without additional context. It is unclear what OS is for the audience outside of optimization community.

questions:
I am wondering if the authors could explain the motivation and the novelty of this paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730456749073

thread_type:
official_review

<thread_object>
creator: reviewer_y4sr

<content>
summary:
This paper combines the interpretability of distributed optimization with the strong empirical performance of deep neural networks to enhance optimization efficiency. The authors propose a distributed method for QPs with theoretical convergence guarantees. They then unfold this method into a deep neural network, leveraging it to accelerate QP solutions. The paper includes both theoretical proofs and numerical results to demonstrate effectiveness. The author claim that the proposed approach outperforms conventional optimization softwares.

strengths:
The mathematical aspects of the paper are technically correct.

weaknesses:
The primary concern revolves around the novelty of the unfolded network. 
A similar approach can be found in [1], which also predicts parameters for ADMM in conventional OSQP using reinforcement learning, where this work seems to be a straightforward substitution of tuning efforts with basic MLPs. 
This also raises questions about the fairness and completeness of the experiments, as the authors only compare their method against OSQP without considering other learning-based frameworks that could potentially yield better performance.
Additionally, the presentation in Section 6 is somewhat difficult to follow. For example, the implementation of the performance metrics is not clearly explained, and it would be helpful for the authors to provide more details on how improvements are quantified. Another minor issue is that some notations are quite confusing and not adequately introduced

[1]Jeffrey Ichnowski, Paras Jain, Bartolomeo Stellato, Goran Banjac, Michael Luo, Francesco Borrelli, Joseph E. Gonzalez, Ion Stoica, and Ken Goldberg. Accelerating quadratic optimization with reinforcement learning, 2021..

questions:
Questions:
In addtion to those mentioned in weakness, there are some specifc questions regarding this paper.
1. What does r^k_i in Figure 1 and subsection **Learning feedback policies** represent? This notation is not defined elsewhere in the paper. Additionally, a complete update formulation would greatly aid in understanding the unfolding process.
1. The author mentions that distributed methods are effective for large-scale decision-making; however, the tested problems are relatively small. Can the authors discuss the feasibility of extending the numerical results to larger problem sizes?
3. The specific number of layers used in the neural network is not mentioned. From the description, I assume it corresponds to $K$. Do these layers share the same weights? Additionally, how does DEEPDISTRQP perform with varying numbers of layers?
4. Why does Figure 6 use the relative optimality gap as a metric, while other figures utilize the absolute optimality gap? What is the rationale behind this choice?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730639320444

thread_type:
official_review

<thread_object>
creator: reviewer_fvd1

<content>
summary:
The authors present an optimization technique for solving quadratic programming problems distributed across multiple compute nodes. The methods use a extend OSQP methodology to a distributed framework which has similarities to a two-block ADMM approach. The authors identify that selecting hyperparameters in this methodology can greatly influence convergence rates. As a result, the authors propose learning the hyperparameters through a deep learning model that has the iterations of the distributed OSQP algorithm embedded as layers.

strengths:
Using solved QP problems to train the deep learning model, the authors are able to select optimal hyperparameters that greatly improve the convergence for solving new distributed QP problems.

weaknesses:
A limitation of this approach seems to be the amount of training data required to train the neural network.

questions:
1.	 Can the authors provide specific details about the dataset size used in each experiment, and comment about how much data would be needed for a user to implement this strategy.
2.	Can the authors discuss if they have separate models for each experiment, or if a single model was used across all problems. If multiple models are used, can the authors comment on the ability of models to generalize to other problems.
3.	Theorem 3 depends on a set of problems drawn from a distribution. Can the authors provide any empirical evidence or discussion on how well the bounds hold for different types of problems?
4.	The authors require knowing the maximum number of iterations, K, apriori. Generally, the maximum number of iterations is quite large with the intention that the optimization solver finds a solution before reaching the limit. Is choosing an appropriate value of K required to construct a deep neural network model that is memory and time efficient? 
5.	In many of the experiments the authors evaluate the optimality gap up to the maximum number of iterations. However, often we care about the number of iterations to reach the optimum. Does this change the methodology implementation?

Some minor points are:
1.	The authors should define some terms like $r$, $\theta$ in equation (10).
2.	Can the authors provide more detail about the known mapping G on page 6, line 282.
3.	Spelling mistake on “non-distrubuted” on page 6 line 290.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732929132720

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Message to Reviewers and Area Chair after Revision (part 1/2)

comment:
We sincerely thank all three reviewers for their time and effort in thoroughly reviewing our work. We deeply appreciate their constructive feedback and valuable suggestions, which have significantly contributed to improving the quality of our paper. In the revised version, we have carefully considered the suggestions of the reviewers on expressing the motivation for addressing large-scale QP problems and the novelty of the proposed DeepDistributedQP framework more clearly. Additionally, we have addressed the concerns of the reviewers regarding the scalability of our framework by significantly increasing the dimension of the illustrated problems to ones with up to 50K variables and 150K variables and showing the orders-of-magnitude improvements in wall-clock time that our approach offers compared to conventional solvers such as the state-of-the-art OSQP method.

We provide a summary of our revisions and responses to the main concerns expressed by the reviewers below: 

- **Motivation (Reviewer EEUg).** We agree with Reviewer EEUg that the initial version of our paper did not sufficiently emphasize the critical importance of developing effective methods for tackling large-scale QP problems. To address this concern, we have revisited the introduction section so that we more clearly articulate why it is vital to develop scalable and effective methods for solving such problems. In summary, QP serves as a fundamental cornerstone in optimization, with applications spanning a wide range of fields. On top of that, it also frequently serves as a subroutine in many advanced non-convex optimization methods. Hence, as the scale of modern applications is continuously increasing, the development of scalable and effective methods for addressing large-scale QP problems is becoming increasingly urgent. We hope that the reviewer recognizes the importance of the problem this work is addressing. 

- **Novelty (Reviewer Y4sR and EEUg).** We thank the reviewers for encouraging us to explain more clearly the novelty of our work.

   -   *Similarity with RLQP (Reviewer Y4sR)*. We appreciate reviewer’s Y4sR feedback regarding the need to better clarify any similarity between our work and RLQP. In our response to the reviewer, we have emphasized the minimal connection between the proposed DeepDistributedQP and RLQP by clearly explaining the distinct differences between these approaches. We have also more clearly expressed these fundamental differences in the related work section to ensure that any such unnecessary confusion is avoided. Again, we are really thankful to the reviewer for pointing out that these differences were not clearly stated in the original version of our paper. 

    - *General novelty (Reviewer EEUg)*. We are really thankful to reviewer EEUg for their feedback to place more emphasis on explaining the novelty of our work. We have addressed this concerns through both revisiting the statement of contributions in the revised version of our paper and in our individual response to the reviewer. In summary, the novel aspects of this work are the following:

         1) We introduce DistributedQP, a ***novel decentralized optimization method for tackling large-scale QP problems.***
         2) We propose DeepDistributedQP, a ***novel deep learning-aided distributed architecture for large-scale QP, which relies on unfolding DistributedQP as supervised learning framework and learning policies for the algorithm parameters***. To our best knowledge, this is the ***first work to present a learning-to-optimize method for distributed QP***. In addition, despite the widespread applicability of ADMM for deriving distributed methods, this is also the ***first work to present a deep unfolded framework of distributed ADMM for large-scale constrained optimization*** towards addressing some of its main shortcomings such as its need for rigorous tuning, lack of generalization capabilities and potential computational/communication limitations. 
         3) We establish ***novel performance guarantees for learned optimizers on unseen problems through PAC-Bayes theory.***
         4) Our framework can ***effectively handle large-scale QP problems with up to 50K variables and 150K constraints, while being trained exclusively on much lower-dimensional ones.*** To our best knowledge, ***this is the first work to present a distributed learning-to-optimize method with such generalization capabilities.***  Hence, these results constitute a key step towards the future development of effective distributed learning-to-optimize methods that can be trained on low-dimensional problems and be applied on much higher-dimensional ones.

       We truly hope that the reviewer is able to appreciate the novel aspects and importance of the results of this work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733185000465

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Follow-up Message to Reviewers and Area Chair - Last Day of Author-Reviewer Discussion Phase

comment:
As today is the last day of the discussion period, we kindly request the remaining reviewers (Reviewers Y4sR and EEUg) to clarify whether their concerns have been addressed. We would also like to express our gratitude to Reviewer fvD1 for recognizing the significance of our work and raising their score.

For convenience, we provide a summary of the raised concerns from Reviewers Y4sR and EEUg, as well as how we have addressed them through the revised version of our paper and responses:

-  **Reviewer Y4sR**: While the primary concern of the reviewer was a potential similarity between our work and RLQP, we have clearly emphasized the minimal connection between RLQP and the proposed DeepDistributedQP framework. Furthermore, we have addressed the concerns of the reviewer regarding scaling to high-dimensional problems, through our new experiments which showcase that DeepDistributedQP can effectively address problems with up to 50K variables and 150K constraints, while being trained exclusively on much lower-dimensional ones. In addition, we have illustrated the effectiveness of our framework under a varying number of layers per request of the reviewer. Given that we have fully addressed all the concerns of the reviewer, we would greatly appreciate the reconsideration of their rating.
- **Reviewer EEUg**: The primary concern of the reviewer was on the motivation and novelty of this work. We hope that the revised version of the introduction of our paper as well as our response have revealed both the vital importance of developing effective methods for large-scale quadratic programming (QP) problems, as well as the significant and multi-faceted novelty of our work.

   - In terms of motivation, QP serves as a fundamental cornerstone of optimization, appearing in a wide array of applications and frequently acting as a subroutine in many advanced optimization methods. As the scale and complexity of modern applications continue to grow, it is urgent to develop effective methods for solving large-scale QP problems efficiently.

   - In terms of novelty, the contributions of this work include the following:
       1. We introduce DistributedQP, a novel decentralized optimization method for tackling large-scale QP problems.
        2. We propose DeepDistributedQP, a novel deep learning-aided distributed architecture for large-scale QP, which relies on unfolding DistributedQP. To our best knowledge, this is the first work to present a learning-to-optimize method for distributed QP. In addition, despite the widespread applicability of ADMM for deriving distributed methods, this is also the first work to present a deep unfolded framework of distributed ADMM for large-scale constrained optimization towards addressing some of its main shortcomings.
       3. We establish novel performance guarantees for learned optimizers on unseen problems through PAC-Bayes theory.
       4. Our framework can effectively handle large-scale QP problems with up to 50K variables and 150K constraints, while being trained exclusively on much lower-dimensional ones. To our best knowledge, this is the first work to present a distributed learning-to-optimize method with such generalization capabilities.

       We sincerely hope that this exposition effectively conveys the importance of the motivation and the multi-faceted novelty of this work, and is sufficient to address the reviewer’s concerns.

Overall, we truly appreciate the insightful comments of all reviewers, as they have highlighted parts of our work that required further emphasis. As a result, their comments have significantly contributed to improving the clarity and quality of our paper. 

If Reviewers Y4sR and EEUg agree that we have fully addressed their concerns, we would greatly appreciate the reconsideration of their rating to reflect these improvements. We also remain at the disposal of the reviewers and the area chair for any additional clarifications.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a novel framework, DeepDistributedQP, which combines distributed optimization techniques with deep learning to address large-scale Quadratic Programming (QP) problems. The key strength of this work lies in its innovative integration of the Operator Splitting QP (OSQP) method into a distributed architecture (DistributedQP) and subsequently unfolding this method as a deep learning framework (DeepDistributedQP). The proposed approach demonstrates significant improvements in scalability, achieving solutions for problems with up to 50K variables and 150K constraints, while maintaining rigorous convergence guarantees. Experimental results highlight the practicality and computational efficiency of the method, achieving orders-of-magnitude improvements in wall-clock time over traditional solvers like OSQP.
The primary contributions of the paper are multi-faceted and impactful: (1) it pioneers a learning-to-optimize approach tailored for distributed constrained optimization, (2) it introduces a novel methodology for tackling large-scale QP problems using limited training data, and (3) it extends the applicability of distributed optimization to high-dimensional problems with significant computational savings. 
The paper makes valuable theoretical and practical contributions to the optimization and machine learning community.