Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise
This work bridges the gap between empirical success and theoretical foundation for constrained optimization in deep learning, providing principled tuning guidance.
The paper establishes that dual optimistic ascent (PI control) on the standard Lagrangian is equivalent to gradient descent-ascent on the Augmented Lagrangian, enabling the transfer of robust theoretical guarantees to prove linear convergence to all local solutions.
Constrained optimization is a powerful framework for enforcing requirements on neural networks. These constrained deep learning problems are typically solved using first-order methods on their min-max Lagrangian formulation, but such approaches often suffer from oscillations and can fail to find all local solutions. While the Augmented Lagrangian method (ALM) addresses these issues, practitioners often favor dual optimistic ascent schemes (PI control) on the standard Lagrangian, which perform well empirically but lack formal guarantees. In this paper, we establish a previously unknown equivalence between these approaches: dual optimistic ascent on the Lagrangian is equivalent to gradient descent-ascent on the Augmented Lagrangian. This finding allows us to transfer the robust theoretical guarantees of the ALM to the dual optimistic setting, proving it converges linearly to all local solutions. Furthermore, the equivalence provides principled guidance for tuning the optimism hyper-parameter. Our work closes a critical gap between the empirical success of dual optimistic methods and their theoretical foundation.