A Penalty Approach for Differentiation Through Black-Box Quadratic Programming Solvers
This addresses a bottleneck in differentiable optimization for researchers and practitioners needing efficient and robust gradient computations, though it is incremental as it builds on existing differentiation approaches.
The paper tackles the problem of differentiating through quadratic programming (QP) solutions, which is computationally costly and numerically unstable at scale with existing KKT-based methods, by proposing dXPP, a penalty-based framework that decouples QP solving from differentiation, resulting in substantial speedups on large-scale problems.
Differentiating through the solution of a quadratic program (QP) is a central problem in differentiable optimization. Most existing approaches differentiate through the Karush--Kuhn--Tucker (KKT) system, but their computational cost and numerical robustness can degrade at scale. To address these limitations, we propose dXPP, a penalty-based differentiation framework that decouples QP solving from differentiation. In the solving step (forward pass), dXPP is solver-agnostic and can leverage any black-box QP solver. In the differentiation step (backward pass), we map the solution to a smooth approximate penalty problem and implicitly differentiate through it, requiring only the solution of a much smaller linear system in the primal variables. This approach bypasses the difficulties inherent in explicit KKT differentiation and significantly improves computational efficiency and robustness. We evaluate dXPP on various tasks, including randomly generated QPs, large-scale sparse projection problems, and a real-world multi-period portfolio optimization task. Empirical results demonstrate that dXPP is competitive with KKT-based differentiation methods and achieves substantial speedups on large-scale problems.