Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise

• URL: http://arxiv.org/abs/2509.22500v1
• Date: Fri, 26 Sep 2025 15:41:20 GMT
• Title: Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise
• Authors: Juan Ramirez, Simon Lacoste-Julien,
• Abstract summary: We show that dual optimistic ascent on the Lagrangian is equivalent to gradient descent-ascent on the Augmented Lagrangian.<n>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.<n>Our work closes a critical gap between the empirical success of dual optimistic methods and their theoretical foundation.
• Score: 16.383773324475538
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
  Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations.<n>Existing methods for solving these relaxations are computationally intensive, limiting their scalability.<n>We develop a unified proximal framework that is both linearly convergent and computationally efficient.
  arXiv  Detail & Related papers  (2026-03-01T22:26:09Z)
• AL-CoLe: Augmented Lagrangian for Constrained Learning [79.45233551350152]
  Despite the non-ity of most modern machine learning parameterizations, Lagrangian duality has become a popular tool for addressing constrained learning problems.<n>We demonstrate its effectiveness on constrained classification tasks.
  arXiv  Detail & Related papers  (2025-10-23T20:46:49Z)
• Alignment of large language models with constrained learning [93.2264691508005]
  We study the problem of computing an optimal large language model (LLM) policy for a constrained alignment problem.<n>We employ Lagrangian duality to develop an iterative dual-based alignment method that alternates between updating the policy via Lagrangian and updating a dual variable via dual descent.
  arXiv  Detail & Related papers  (2025-05-26T01:04:56Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• Learning Lagrangian Multipliers for the Travelling Salesman Problem [12.968608204035611]
  We propose an innovative unsupervised learning approach that harnesses the capabilities of graph neural networks to exploit the problem structure. We apply this technique to the well-known Held-Karp Lagrangian relaxation for the travelling salesman problem. In contrast to much of the existing literature, which primarily focuses on finding feasible solutions, our approach operates on the dual side, demonstrating that learning can also accelerate the proof of optimality.
  arXiv  Detail & Related papers  (2023-12-22T17:09:34Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• A Surrogate Objective Framework for Prediction+Optimization with Soft Constraints [29.962390392493507]
  Decision-focused prediction approaches, such as SPO+ and direct optimization, have been proposed to fill this gap. This paper proposes a novel analytically differentiable surrogate objective framework for real-world linear and semi-definite negative quadratic programming problems.
  arXiv  Detail & Related papers  (2021-11-22T17:09:57Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  We consider the linear programming (LP) formulation for deep reinforcement learning. The augmented Lagrangian method suffers the double-sampling obstacle in solving the LP. A deep parameterized augment Lagrangian method is proposed.
  arXiv  Detail & Related papers  (2021-05-20T13:08:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.