Research map / Learning theory and algorithms / Combinatorial and search optimization
Deep Distributed Optimization for Large-Scale Quadratic Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DistributedQP (consensus ADMM combined with OSQP using local iteration-varying penalties, with convergence proof) and unfolds it into DeepDistributedQP, learning feedback policies for penalty and over-relaxation parameters, with PAC-Bayes generalization bounds on the optimality gap.
Problem
Large-scale convex quadratic programs with networked/decentralized structure need efficient distributed solvers, but ADMM-based methods require meticulous parameter tuning, lack generalization guarantees, and must work under iteration budgets.
Approach
Combines OSQP with consensus ADMM into a distributed QP solver with local iteration-varying penalties and over-relaxation, proves its convergence, then unfolds it as a supervised deep network whose penalty/relaxation parameters are set by learned closed-loop (residual-feedback) policies, trained on small problems and scaled to much larger ones, with PAC-Bayes bounds on the final optimality gap.
Key results
- DeepQP requires 1.5-3x fewer iterations than OSQP for centralized QPs.
- DeepDistributedQP trained on problems with n=160-1,100 variables scales to up to 50K variables and 150K constraints with 1.5-3.5x fewer iterations than DistributedQP.
- PAC-Bayes bounds with 99% probability are tight relative to actual performance and outperform standard optimizers on random QP (N=16) and coupled pendulums (N=10).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use learned DeepQP policies instead of standard OSQP | Centralized QPs · Centralized QPs | iterations to desired accuracy: 1.5-3 times fewer iterations | Helped |
| Use closed-loop rather than open-loop policies (ablation) | DeepQP · Centralized QPs | iterations to desired accuracy | Helped |
| Use DeepDistributedQP rather than DistributedQP | Large-scale distributed QPs · Large-scale distributed QPs | iterations to same accuracy: 1.5-3.5 times fewer iterations | Helped |
| Use DeepDistributedQP rather than OSQP | Large-scale distributed QPs · Large-scale distributed QPs | wall-clock time to same accuracy: orders of magnitude | Helped |
| Use DistributedQP rather than OSQP | Large-scale distributed QPs · Large-scale distributed QPs | wall-clock time to same accuracy: orders of magnitude | Helped |
| Use local rather than shared policies (ablation) | DeepDistributedQP · Coupled pendulums | performance | Helped |
| Use local rather than shared policies (ablation) | DeepDistributedQP · Random QPs | performance | Helped |
Limitations
- Relies on a supervised loss requiring pre-solved problems.
- PAC-Bayes gives probabilistic average-case guarantees, not robustness guarantees for safety-critical use.
Experimental setup
Datasets: randomly generated QPs optimal control (double integrator, oscillating masses, coupled pendulums) portfolio optimization LASSO regression network flow distributed LASSO
Benchmarks: random QPs coupled pendulums coupled oscillating masses network flow distributed LASSO portfolio optimization LASSO regression
Metrics: normalized optimality gap iterations to accuracy wall-clock time PAC-Bayes generalization bound
Baselines: OSQP DistributedQP DeepQP (open-loop)
Builds on: OSQP consensus ADMM deep unfolding PAC-Bayes
Closest papers by meaning
- Differentiation Through Black-Box Quadratic Programming Solvers (NeurIPS 2025 · similarity 0.88)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.88)
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.87)
- BayeSQP: Bayesian Optimization through Sequential Quadratic Programming (NeurIPS 2025 · similarity 0.87)
- Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence (AAAI 2025 · similarity 0.87)
- BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.